谷歌 OA 合集

第一题:

Several coupons are placed in a row, and to win the prize you need to pick at least 2 coupons of the same value. You can only pick consecutive coupons from the row. Each coupon costs 1 coin, find the minimum number of coins needed to obtain the prize or, -1 if it’s not possible.

Example 1:

Input: coupons = [5, 3, 4, 2, 3, 4, 5, 7]
Output: 4
Explanation:
Because you can buy coupons with values [3, 4, 2, 3] or [4, 2, 3, 4]
Example 2:

Input: coupons = [3, 6, 1, 9]
Output: -1

第二题
You are given a tree-shaped undirected graph consisting of n nodes labeled 1...n and n-1 edges. The i-th edge connects nodes edges[i][0] and edges[i][1] together.
For a node x in the tree, let d(x) be the distance (the number of edges) from x to its farthest node. Find the min value of d(x) for the given tree.
The tree has the following properties:

  • It is connected.
  • It has no cycles.
  • For any pair of distinct nodes x and y in the tree, there’s exactly 1 path connecting x and y .

Example 1:
Input: n = 6, edges = [[1, 4], [2, 3], [3, 4], [4, 5], [5, 6]]

Output: 2

Example 2:
Input: n = 6, edges = [[1, 3], [4, 5], [5, 6], [3, 2], [3, 4]]

Output: 2

Example 3:
Input: n = 2, edges = [[1, 2]]

Output: 1

Example 4:
Input: n = 10, edges = [[1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [6, 7], [7, 8], [8, 9], [9, 10]]

Output: 5

Example 5:
Input: n = 10, edges = [[7, 8], [7, 9], [4, 5], [1, 3], [3, 4], [6, 7], [4, 6], [2, 3], [9, 10]]

Output: 3

You can assume that input is always valid and satisfies all constraints.

我碰到这两题

第一题:

There are some processes that need to be executed. Amount of a load that process causes on a server that runs it, is being represented by a single integer. Total load caused on a server is the sum of the loads of all the processes that run on that server. You have at your disposal two servers, on which mentioned processes can be run. Your goal is to distribute given processes between those two servers in the way that, absolute difference of their loads will be minimized.

Given an array of n integers, of which represents loads caused by successive processes, return the minimum absolute difference of server loads.

Example 1:

Input: [1, 2, 3, 4, 5]
Output: 1
Explanation:
We can distribute the processes with loads [1, 2, 4] to the first server and [3, 5] to the second one,
so that their total loads will be 7 and 8, respectively, and the difference of their loads will be equal to 1.

第二题

You are a gardener and you take care of your plants. The plants are planted in a row and each of them needs a specific amount of water. You are about to water them using a watering can. To avoid mistakes like applying too much water, or not watering a plant at all, you have decided to:

  • water the plants in the order in which they appear, from left to right;
  • water each plant if you have sufficient water for it, otherwise refill your watering can;
  • water each plant in one go, i.e. without taking a break to refill the watering can in the middle of watering a single plant. This means that you may sometimes have to refill your watering can before or after watering a plant, even though it’s not completely empty.

You start at the water container, which is positioned one step before the first plant. How many steps will you take, in order to water all the plants in the row? You must take one step to move to the next or the previous plant (all plants are positioned one step apart from each other).

Given an array plants of n integers (for the amount of water needed by each plan) and the watering can capacity , return the number of steps needed to water all the plants.

Example 1:

Input: plants = [2, 4, 5, 1, 2], capacity = 6
Output: 17
Explanation:
First you water plants[0] and plants[1] (2 steps). Then you have to go back to refill (2 steps) and water
plants[2] and plants[3] (4 steps). Then again you have to refill (4 steps) and water plants[4] (5 steps).

我遇到这题

Imagine you have a special keyboard with all keys in a single row. The layout of characters on a keyboard is denoted by a string keyboard of length 26. Initially your finger is at index 0. To type a character, you have to move your finger to the index of the desired character. The time taken to move your finger from index i to index j is abs(j - i).

Given a string keyboard that describe the keyboard layout and a string text, return an integer denoting the time taken to type string text.

Example 1:

Input: keyboard = “abcdefghijklmnopqrstuvwxy”, text = “cba”
Output: 4
Explanation:
Initially your finger is at index 0. First you have to type ‘c’. The time taken to type ‘c’ will be abs(2 - 0) = 2 because character ‘c’ is at index 2.
The second character is ‘b’ and your finger is now at index 2. The time taken to type ‘b’ will be abs(1 - 2) = 1 because character ‘b’ is at index 1.
The third character is ‘a’ and your finger is now at index 1. The time taken to type ‘a’ will be abs(0 - 1) = 1 because character ‘a’ is at index 0.
The total time will therefore be 2 + 1 + 1 = 4.

Constraints:

length of keyboard will be equal to 26 and all the lowercase letters will occur exactly once;
the length of text is within the range [1…100,0001];
string text contains only lowercase letters [a-z].

我报下我的吧

第一题

Given 2 arrays a and b, each containing n integers. You can swap elements at the same index. Return the minimum number of swaps needed for all elements in either a or b to be the same or -1 if that is not possible.

Example 1:

Input:
a = [1, 2, 3, 6, 3, 2]
b = [2, 1, 2, 2, 2, 4]

Output: 2

Explanation:
You can swap elements at index 1 and 5, so that all elements in b will be equal to 2.
a = [1, 1, 3, 6, 3, 4]
b = [2, 2, 2, 2, 2, 2]
Example 2:

Input:
a = [1, 2, 1, 2]
b = [2, 6, 1, 2]

Output: -1
Constraints:

n is an integer within the range [1…100,000];
each element of arrays a and b is an integer within the range [1…6].

第二题

There are n guests who are invited to a party. The k-th guest will attend the party at time S[k] and leave the party at time E[k].

Given an integer array S and an integer array E, both of length n, return an integer denoting the minimum number of chairs you need such that everyone attending the party can sit down.

Example:

Input: S = [1, 2, 6, 5, 3], E = [5, 5, 7, 6, 8]
Output: 3
Explanation:
There are five guests attending the party.
The 1st guest will arrive at time 1. We need one chair at time 1.
The 2nd guest will arrive at time 2. There are now two guests at the party, so we need two chairs at time 2.
The 5th guest will arrive at time 3. There are now three guests at the party, so we need three chairs at time 3.
The 4th guest will arrive at time 5 and, at the same moment, the 1st and 2nd guests will leave the party.
There are now two (the 4th and 5th) guests at the party, so we need two chairs at time 5.
The 3rd guest will arrive at time 6, and the 4th guest will leave the party at the same time.
There are now two (the 3rd and 5th) guests at the party, so we need two chairs at time 6.
So we need at least 3 chairs.

1 Like

第一题

A pizza shop offers n pizzas along with m toppings. A customer plans to spend around x coins. The customer should order exactly one pizza, and may order zero, one or two toppings. Each topping may be order only once.

Given the lists of prices of available pizzas and toppings, what is the price closest to x of possible orders? Here, a price said closer to x when the difference from x is the smaller. Note the customer is allowed to make an order that costs more than x.

Example 1:

Input: pizza = [800, 850, 900], topping = [100, 150], x = 1000
Output: 1000
Explanation:
The customer can spend exactly 1000 coins (two possible orders).

Example 2:

Input: pizza = [850, 900], topping = [200, 250], x = 1000
Output: 1050
Explanation:
The customer may make an order more expensive than 1000 coins.

Example 3:

Input: pizza = [1100, 900], topping = [200], x = 1000
Output: 900
Explanation:
The customer should prefer 900 (lower) over 1100 (higher).

Example 4:

Input: pizza = [800, 800, 800, 800], topping = [100], x = 1000
Output: 900
Explanation:
The customer may not order 2 same toppings to make it 1000.

Constraints:

Customer’s budget: 1 <= x <= 10000
Number of pizzas: 1 <= n <= 10
Number of toppings: 0 <= m <= 10
Price of each pizza: 1 <= pizza[i] <= 10000
Price of each topping: 1 <= topping[i] <= 10000
The total price of all toppings does not exceed 10000.

第二题

Given an array of integers nums and an int target, return indices of the two numbers such that they add up to a target - 30.

Conditions:

  • You will pick exactly 2 numbers.
  • You cannot pick the same element twice.
  • If you have muliple pairs, select the pair with the largest number.

Example 1:

Input: nums = [1, 10, 25, 35, 60], target = 90
Output: [2, 3]
Explanation:
nums[2] + nums[3] = 25 + 35 = 60 = 90 - 30

Example 2:

Input: nums = [20, 50, 40, 25, 30, 10], target = 90
Output: [1, 5]
Explanation:
nums[0] + nums[2] = 20 + 40 = 60 = 90 - 30
nums[1] + nums[5] = 50 + 10 = 60 = 90 - 30
You should return the pair with the largest number.

我的解法

public class Main {
    
    public static int[] findPair(int[] nums, int target) {
        target -= 30;
        Map<Integer, Integer> map = new HashMap<>();
        int[] result = {-1, -1};
        for (int i = 0; i < nums.length; i++) {
            Integer idx = map.get(target - nums[i]);
            if (idx != null) {
                // first valid pair
                if (result[0] == -1) {
                    result[0] = idx;
                    result[1] = i;
                }
                // we already have a valid pair
                // need to choose the pair with the largest value
                else if (Math.max(nums[idx], nums[i]) > Math.max(nums[result[0]], nums[result[1]])) {
                    result[0] = idx;
                    result[1] = i;    
                }
            }
            map.put(nums[i], i);
        }
        return result;
    }

    public static void main(String[] args) {
        test(new int[]{1, 10, 25, 35, 60}, 90);
        test(new int[]{20, 50, 40, 25, 30, 10}, 90);
        test(new int[]{5, 55, 40, 20, 30, 30}, 90);
    }
    
    private static void test(int[] nums, int target) {
        System.out.println(Arrays.toString(findPair(nums, target)));
    }
}

Time complexity: O(n).
Space complexity: O(n).

第三题

Given an undirected graph with n nodes labeled 1…n. Some of the nodes are already connected. The i-th edge connects nodes edges[i][0] and edges[i][1] together. Your task is to augment this set of edges with additional edges to connect all the nodes. Find the minimum cost to add new edges between the nodes such that all the nodes are accessible from each other.

Input:

  • n, an int representing the total number of nodes.
  • edges, a list of integer pair representing the nodes already connected by an edge.
  • newEdges, a list where each element is a triplet representing the pair of nodes between which an edge can be added and the cost of addition, respectively (e.g. [1, 2, 5] means to add an edge between node 1 and 2, the cost would be 5).

Example 1:

Input: n = 6, edges = [[1, 4], [4, 5], [2, 3]], newEdges = [[1, 2, 5], [1, 3, 10], [1, 6, 2], [5, 6, 5]]
Output: 7
Explanation:
There’re 3 connected components [1, 4, 5], [2, 3] and [6].
We can connect these components into a single component by connecting node 1 to node 2 and node 1 to node 6 at a minimum cost of 5 + 2 = 7.

我的解法用了Kruskal’s MST algorithm

public class Main {
    public static void main(String[] args) {
        int n = 6;
        int[][] edges = {{1, 4}, {4, 5}, {2, 3}};
        int[][] newEdges = {{1, 2, 5}, {1, 3, 10}, {1, 6, 2}, {5, 6, 5}};
        System.out.println(minCost(n, edges, newEdges));
    }
    
    public static int minCost(int n, int[][] edges, int[][] newEdges) {
        UF uf = new UF(n + 1); // + 1 because nodes are 1-based
        for (int[] edge : edges) {
            uf.union(edge[0], edge[1]);
        }
        
        Queue<int[]> pq = new PriorityQueue<>(newEdges.length, (e1, e2) -> Integer.compare(e1[2], e2[2]));
        pq.addAll(Arrays.asList(newEdges));
        
        int totalCost = 0;
        // 2 because nodes are 1-based and we have 1 unused component at index 0
        while (!pq.isEmpty() && uf.count != 2) {
            int[] edge = pq.poll();
            if (!uf.connected(edge[0], edge[1])) {
                uf.union(edge[0], edge[1]);
                totalCost += edge[2];
            }
        }
        return totalCost;
    }
}

class UF {
    private int[] parent;  // parent[i] = parent of i
    private byte[] rank;   // rank[i] = rank of subtree rooted at i (never more than 31)
    public int count;      // number of connected components

    public UF(int n) {
        if (n < 0) throw new IllegalArgumentException();
        parent = new int[n];
        rank = new byte[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        count = n;
    }

    public int find(int p) {
        while (p != parent[p]) {
            parent[p] = parent[parent[p]];
            p = parent[p];
        }
        return p;
    }

    public void union(int p, int q) {
        int pr = find(p);
        int qr = find(q);
        if (pr == qr) return;
        if (rank[pr] < rank[qr]) {
            parent[pr] = qr;
        } else {
            parent[qr] = pr;
            if (rank[pr] == rank[qr]) rank[pr]++;
        }
        count--;
    }

    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }
}

参考