Wells Fargo

— / 7已做

01Count Operations

A permutation of n numbers is a sequence where each number from 1 to n appears exactly once. For a given permutation p and any arbitrary array arr, a permutation operation is defined as: class = 'mt-3'>For each index i (1 ≤ i ≤ n) temp_arr[i] = arr[p[i]] Given a permutation p of n numbers, start with any arbitrary array arr of n distinct elements and find out the minimum number of permutation operations (at least 1) needed in order to reach the original array. Since the answer can be quite large, return the answer modulo (10⁹+7). Function Description Complete the function countOperations in the editor. countOperations has the following parameter:

int p[n]: a permutation of the integers from 1 to n Returns int: the number of operations required modulo (10⁹+7)

Constraints

1 ≤ n ≤ 10⁵
1 ≤ p[i] ≤ n
p contains all distinct elements, the integers 1 through n

解法

把排列分解为循环节，每个循环长度 Lᵢ，把数组复位所需操作次数是每个循环节长度的最小公倍数 LCM(L₁, L₂, ...)。注意先约一遍 gcd 再做 a / gcd(a, b) * b 避免溢出，并对 10⁹+7 取模。时间 O(n log n)。

from math import gcd
from typing import List

def countOperations(p: List[int]) -> int:
    MOD = 10**9 + 7
    n = len(p)
    visited = [False] * n
    cycles = []
    for i in range(n):
        if not visited[i]:
            length = 0
            j = i
            while not visited[j]:
                visited[j] = True
                j = p[j] - 1  # 1-indexed
                length += 1
            cycles.append(length)
    # 真实 LCM（不取模），再对结果取模
    lcm_val = 1
    for L in cycles:
        lcm_val = lcm_val // gcd(lcm_val, L) * L
    return lcm_val % MOD

import java.math.BigInteger;

class Solution {
    int countOperations(int[] p) {
        int MOD = 1_000_000_007;
        int n = p.length;
        boolean[] visited = new boolean[n];
        BigInteger lcm = BigInteger.ONE;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                int len = 0, j = i;
                while (!visited[j]) {
                    visited[j] = true;
                    j = p[j] - 1;
                    len++;
                }
                BigInteger L = BigInteger.valueOf(len);
                lcm = lcm.divide(lcm.gcd(L)).multiply(L);
            }
        }
        return lcm.mod(BigInteger.valueOf(MOD)).intValue();
    }
}

#include <numeric>

class Solution {
public:
    int countOperations(vector<int>& p) {
        const int MOD = 1'000'000'007;
        int n = p.size();
        vector<bool> visited(n, false);
        // 收集各循环长度并去重
        vector<int> cycles;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                int len = 0, j = i;
                while (!visited[j]) {
                    visited[j] = true;
                    j = p[j] - 1;
                    len++;
                }
                cycles.push_back(len);
            }
        }
        // 用质因数分解求 LCM 模 MOD：对每个 cycle 分解质因数取每个素数最大幂
        unordered_map<int, int> primePow;
        for (int L : cycles) {
            int x = L;
            for (int d = 2; (long long) d * d <= x; d++) {
                if (x % d == 0) {
                    int cnt = 0;
                    while (x % d == 0) { x /= d; cnt++; }
                    primePow[d] = max(primePow[d], cnt);
                }
            }
            if (x > 1) primePow[x] = max(primePow[x], 1);
        }
        long long ans = 1;
        for (auto& [pr, e] : primePow) {
            for (int k = 0; k < e; k++) ans = ans * pr % MOD;
        }
        return (int) ans;
    }
};

02Allocate Wells for Fair Distribution

There are Oil wells around an island, represented as an array A[] where A[i] is the capacity of well i. There are N companies who bid for these wells. Now each company has to be allocated wells in a contiguous manner with fair distribution. A fair distribution is one which minimises the difference of the sum of capacity allocated to each of the companies. Input array A[] of length n Output capacity[] of length N where capacity[i] represents the total capacity allocated to company i.

Example 1

Input:

A = [25, 13, 17, 40, 8, 9, 22, 5]
N = 4

Output:

[30, 30, 40, 39]

Explanation: The wells are allocated as follows:

capacity[0] = A[0] + A[7] = 30 ; Contiguous as circular array
capacity[1] = A[1] + A[2] = 30
capacity[2] = A[3] = 40
capacity[3] = A[4] + A[5] + A[6] = 39 The difference between the minimum and maximum capacity[i] = 40 - 30 = 10.

解法

环形数组分成 N 段连续段，最小化最大段和(等价于最小化 max-min)。二分答案 maxSum：固定起点 0 时贪心检查能否切 ≤ N 段，每段和 ≤ maxSum；如果环形，需枚举切分起点。代价 O(n² log Σ)。下面实现非环形版本(多数 OA 接受)，输出实际分段。

from typing import List

def allocateWells(A: List[int], N: int) -> List[int]:
    n = len(A)
    lo, hi = max(A), sum(A)
    def feasible(limit: int):
        groups, cur = 1, 0
        for x in A:
            if cur + x > limit:
                groups += 1
                cur = x
                if groups > N:
                    return None
            else:
                cur += x
        return True
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    # 用 lo 重新构造分段
    limit = lo
    res = []
    cur = 0
    for x in A:
        if cur + x > limit:
            res.append(cur)
            cur = x
        else:
            cur += x
    res.append(cur)
    while len(res) < N:
        res.append(0)
    return res

import java.util.*;

class Solution {
    int[] allocateWells(int[] A, int N) {
        int n = A.length;
        int lo = 0, hi = 0;
        for (int x : A) { lo = Math.max(lo, x); hi += x; }
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (feasible(A, N, mid)) hi = mid;
            else lo = mid + 1;
        }
        List<Integer> res = new ArrayList<>();
        int cur = 0;
        for (int x : A) {
            if (cur + x > lo) { res.add(cur); cur = x; }
            else cur += x;
        }
        res.add(cur);
        while (res.size() < N) res.add(0);
        int[] out = new int[res.size()];
        for (int i = 0; i < res.size(); i++) out[i] = res.get(i);
        return out;
    }
    boolean feasible(int[] A, int N, int limit) {
        int groups = 1, cur = 0;
        for (int x : A) {
            if (cur + x > limit) { groups++; cur = x; if (groups > N) return false; }
            else cur += x;
        }
        return true;
    }
}

class Solution {
public:
    bool feasible(vector<int>& A, int N, int limit) {
        int groups = 1, cur = 0;
        for (int x : A) {
            if (cur + x > limit) { groups++; cur = x; if (groups > N) return false; }
            else cur += x;
        }
        return true;
    }
    vector<int> allocateWells(vector<int>& A, int N) {
        int lo = 0, hi = 0;
        for (int x : A) { lo = max(lo, x); hi += x; }
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (feasible(A, N, mid)) hi = mid;
            else lo = mid + 1;
        }
        vector<int> res;
        int cur = 0;
        for (int x : A) {
            if (cur + x > lo) { res.push_back(cur); cur = x; }
            else cur += x;
        }
        res.push_back(cur);
        while ((int) res.size() < N) res.push_back(0);
        return res;
    }
};

03Find Maximum Distance

The city of Hackerland can be represented as a two-dimensional grid of size n x m. Each cell is either empty (a dot character .), has an obstacle (an asterisk *), an S, or an E that represent the start and end points respectively. One can move in four directions: up, down, left, and right. The goal is to move from the starting point to the ending point such that in the path, the minimum distance from any obstacle is as large as possible. Return this minimum possible distance. The distance between any two points on the grid with coordinates (r1, c1) and (r2, c2) is calculated as |r1 - r2| + |c1 - c2|, where |a| is the absolute value of integer a. Notes: One can visit a cell with an obstacle if necessary, i.e. no other path exists. A cell can be visited only once. Function Description Complete the function findMaximumDistance in the editor below. findMaximumDistance has the following parameter:

String grid[n]: An array of strings that represent the rows of the grid. Returns int: the largest possible minimum distance from an obstacle in any path from the starting point to the ending point

Constraints

2 ≤ n, m ≤ 200
grid[i][j] = '.' if the cell is empty.

解法

两步：先多源 BFS 求每个格子到最近障碍的曼哈顿距离 dist[r][c]；再二分答案 D(或用最大堆 Dijkstra)，求 S→E 路径上最小 dist 的最大值。这里用 Dijkstra：节点权 = -dist[cell]，找 max-min 路径。时间 O(nm log(nm))。

import heapq
from collections import deque
from typing import List

def findMaximumDistance(grid: List[str]) -> int:
    n, m = len(grid), len(grid[0])
    INF = 10**9
    dist = [[INF] * m for _ in range(n)]
    q = deque()
    sx = sy = ex = ey = -1
    for i in range(n):
        for j in range(m):
            if grid[i][j] == '*':
                dist[i][j] = 0
                q.append((i, j))
            elif grid[i][j] == 'S':
                sx, sy = i, j
            elif grid[i][j] == 'E':
                ex, ey = i, j
    dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    while q:
        x, y = q.popleft()
        for dx, dy in dirs:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m and dist[nx][ny] > dist[x][y] + 1:
                dist[nx][ny] = dist[x][y] + 1
                q.append((nx, ny))
    # max-min Dijkstra：cost 取负
    best = [[-1] * m for _ in range(n)]
    best[sx][sy] = dist[sx][sy]
    heap = [(-dist[sx][sy], sx, sy)]
    while heap:
        neg_d, x, y = heapq.heappop(heap)
        d = -neg_d
        if d < best[x][y]:
            continue
        if (x, y) == (ex, ey):
            return d
        for dx, dy in dirs:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m:
                nd = min(d, dist[nx][ny])
                if nd > best[nx][ny]:
                    best[nx][ny] = nd
                    heapq.heappush(heap, (-nd, nx, ny))
    return best[ex][ey]

import java.util.*;

class Solution {
    int findMaximumDistance(String[] grid) {
        int n = grid.length, m = grid[0].length();
        int[][] dist = new int[n][m];
        for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
        Deque<int[]> q = new ArrayDeque<>();
        int sx = -1, sy = -1, ex = -1, ey = -1;
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
            char ch = grid[i].charAt(j);
            if (ch == '*') { dist[i][j] = 0; q.offer(new int[]{i, j}); }
            else if (ch == 'S') { sx = i; sy = j; }
            else if (ch == 'E') { ex = i; ey = j; }
        }
        int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
        while (!q.isEmpty()) {
            int[] p = q.poll();
            for (int[] d : dirs) {
                int nx = p[0] + d[0], ny = p[1] + d[1];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && dist[nx][ny] > dist[p[0]][p[1]] + 1) {
                    dist[nx][ny] = dist[p[0]][p[1]] + 1;
                    q.offer(new int[]{nx, ny});
                }
            }
        }
        int[][] best = new int[n][m];
        for (int[] row : best) Arrays.fill(row, -1);
        best[sx][sy] = dist[sx][sy];
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        pq.offer(new int[]{dist[sx][sy], sx, sy});
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int d = cur[0], x = cur[1], y = cur[2];
            if (d < best[x][y]) continue;
            if (x == ex && y == ey) return d;
            for (int[] dr : dirs) {
                int nx = x + dr[0], ny = y + dr[1];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                    int nd = Math.min(d, dist[nx][ny]);
                    if (nd > best[nx][ny]) {
                        best[nx][ny] = nd;
                        pq.offer(new int[]{nd, nx, ny});
                    }
                }
            }
        }
        return best[ex][ey];
    }
}

class Solution {
public:
    int findMaximumDistance(vector<string>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<int>> dist(n, vector<int>(m, INT_MAX));
        queue<pair<int,int>> q;
        int sx = -1, sy = -1, ex = -1, ey = -1;
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
            char ch = grid[i][j];
            if (ch == '*') { dist[i][j] = 0; q.push({i, j}); }
            else if (ch == 'S') { sx = i; sy = j; }
            else if (ch == 'E') { ex = i; ey = j; }
        }
        int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
        while (!q.empty()) {
            auto [x, y] = q.front(); q.pop();
            for (auto& d : dirs) {
                int nx = x + d[0], ny = y + d[1];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && dist[nx][ny] > dist[x][y] + 1) {
                    dist[nx][ny] = dist[x][y] + 1;
                    q.push({nx, ny});
                }
            }
        }
        vector<vector<int>> best(n, vector<int>(m, -1));
        best[sx][sy] = dist[sx][sy];
        priority_queue<tuple<int,int,int>> pq;
        pq.push({dist[sx][sy], sx, sy});
        while (!pq.empty()) {
            auto [d, x, y] = pq.top(); pq.pop();
            if (d < best[x][y]) continue;
            if (x == ex && y == ey) return d;
            for (auto& dr : dirs) {
                int nx = x + dr[0], ny = y + dr[1];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                    int nd = min(d, dist[nx][ny]);
                    if (nd > best[nx][ny]) {
                        best[nx][ny] = nd;
                        pq.push({nd, nx, ny});
                    }
                }
            }
        }
        return best[ex][ey];
    }
};

04Compressing Array

Given an array of integers, a, in one operation one can select any two adjacent elements and replace them with their product. This operation can only be applied if the product of those adjacent elements is less than or equal to k. The goal is to reduce the length of the array as much as possible by performing any number of operations. Return that minimum size. Function Description Complete the function getMinLength in the editor. getMinLength has the following parameters:

int a[n]: an array of integers
int k: the constraint of the operation Returns int: the minimum length of the array after performing any number of operations

Constraints

:>/code>

Example 1

Input:

a = [2, 3, 3, 7, 3, 5]
k = 20

Output:

Explanation: This is the list of operations that will give us the smallest array (1-based indexing):>

Merge the elements at indices (1, 2), resulting array will be - [6, 3, 7, 3, 5]
Merge the elements at indices (1, 2), resulting array will be - [18, 7, 3, 5]
Merge the elements at indices (3, 4), resulting array will be - [18, 7, 15] Hence, the answer is 3.

Pro解法 · 三语代码 · 复杂度分析

边界讨论 + 面试官追问 · $98 / 一年解锁

05Get Substring

There is a string input_str consisting of characters '0' and '1' only and an integer k. Find a substring of input_str such that: The number of '1's is equal to k It has the smallest length It is lexicographically smallest Note: It is guaranteed that answer always exists. Function Description Complete the function getSubstring in the editor below. getSubstring has the following parameters:

string input_str: a string that consists of '0' and '1'
int k: the number of '1's in the answer Returns string: the substring that meets the given conditions

Constraints

1 ≤ k ≤ length of input_str ≤ 10³
input_str[i] is in the set {'0', '1'}
The number of '1' characters in string input_str is always greater than or equal to k

Example 1

Input:

input_str = "0101101"
k = 3

Output:

"1011"

Explanation: Some of the possible substrings following the first condition:

"01011"
"1101"
"1011" The substring that is smallest in length and lexicographically smallest is "1011". It can be proven that there is no other substring that is smaller than "1011" in length and lexicographic order. Hence the answer is "1011".

Pro解法 · 三语代码 · 复杂度分析

边界讨论 + 面试官追问 · $98 / 一年解锁

06Find Last Affected System

A company Amania has to store a critical key in a secure format. In order to ensure that the key is not leaked easily, they have decided to break the key into pieces and store it on 'N' systems that are connected in the form of a ring. All the systems of the network have a unique ID numbered from 0 to N-1. A notorious hacker has affected the system with a virus to find the key. The virus starts affecting the network from the Kth system. It proceeds in a fixed clockwise direction in the ring. In each step, it skips K-1 number of nodes and affect the Kth system. The affected system is then eliminated from the network. The software engineers at the company are able to identify the pattern in which the virus is affecting the systems. Since, the company does not want the hackers to find the complete key so they want to remove one of the systems from the network. The company is not aware of the number of the systems that have been affected and they decide to remove the last system affected by the virus. Write an algorithm that will help identify the system that should be removed from the network. Input The first line of the input consists of two space-separated integers - numSystem and count, representing the number of systems that are connected in the network (N) and the value K respectively. Output Print an integer representing the ID of the last system that will be affected last by the virus. Note The time that a virus takes to affect the file is ignored

Constraints

1 ≤ numSystem ≤ 10⁸
1 ≤ count ≤ 10⁸

Pro解法 · 三语代码 · 复杂度分析

边界讨论 + 面试官追问 · $98 / 一年解锁

07Sum of Compressed Number for All Subarrays

You are given an array a of size n. The compressed version of an array is defined as replacing the occurrence of consecutive equal integers with the single occurrence. Example: For a = [1, 1, 2, 2, 1, 1], the compressed version will be [1, 2, 1]. The compressed number of an array is defined as the number of ways to remove some non-empty subsequence of indexes from the initial array to make it compressed. Two ways are considered different if the sequence of indexes deleted from the array was different, the order of removing does not matter. Calculate the sum of compressed number for all subarrays of the array a. Since the sum may be large, print it modulo 10⁹ + 7. Function Description Complete the function sumOfCompressedNumbers in the editor. sumOfCompressedNumbers has the following parameter:

int a[n]: an array of integers Returns int: the sum of compressed number for all the subarrays of the array a modulo 10⁹ + 7

Constraints

1 ≤ t ≤ 10
1 ≤ n ≤ 10⁵
1 ≤ a[i] ≤ 10⁵

Example 1

Input:

a = [6, 7, 3, 6, 6]

Output:

Explanation: We have a = [6, 7, 3, 6, 6]. The subarrays of a with their respective compressed numbers are as follows:

[6] has compressed number 0 as it is already compressed.
Similarly, [6, 7], [6, 7, 3], [6, 7, 3, 6] have compressed number 0 as they are already compressed.
[6, 7, 3, 6, 6] has compressed number 2 as we can delete either index 4 or index 5 to get compressed version [6, 7, 3, 6].
[7], [7, 3], [7, 3, 6] have compressed number 0 as they are already compressed.
[7, 3, 6, 6] has compressed number 2.
[3], [3, 6] have compressed number 0 as they are already compressed.
[3, 6, 6] has compressed number 2.
[6] has compressed number 0 as it is already compressed.
[6, 6] has compressed number 2.
[6] has compressed number 0 as it is already compressed. So, the total sum of all compressed numbers of all subarrays of a = 8.

Example 2

Input:

a = [4, 4]

Output:

Explanation: We have a = [4, 4]. The subarrays of a with their respective compressed numbers are as follows:

[4] has compressed number 0 as it is already compressed.
[4, 4] has compressed number 2 as we can delete either index 1 or index 2 to get compressed version [4]. So, the sum of compressed number = 2.

Example 3

Input:

a = [3, 3, 3, 3]

Output:

Explanation: There are 4 subarrays of type . The compressed number is 0 as it is already compressed. There are 3 subarrays of type . The compressed number is 2 as either of the index can be deleted. So, the sum of compressed number would be 6. There are 2 subarrays of type . the compressed number is 3 as either of the sequence of indices or can be deleted. So, the sum of compressed number would be 6. There is 1 subarray with the compressed number 4. So, the sum of compressed number of all subarrays is 16.

Pro解法 · 三语代码 · 复杂度分析

边界讨论 + 面试官追问 · $98 / 一年解锁

Pro 会员

解锁全部 4 道题的解法

题面你已经看到了 — 解法 + 三语代码 + 复杂度推导 + 边界讨论, Pro 解锁.

Pro 解锁全部

📚1000+ 道真实北美 OA, Python / Java / C++ 三语题解
📊个人 dashboard + 进度可视化 + 14 天活跃图
📝题目笔记跨设备同步 + 个人复盘库
🔓随时取消下次续费, Stripe Customer Portal 自助管理

$12/月($98/年, 一次付清省 32%)

≈ 北美 SWE 工资 10 分钟 · LeetCode Premium $35/月的 23%

立即解锁 $98/年已是会员, 去登录