Just finished it recently Google 26NG OA, the overall feeling is: the question itself is not particularly biased, but it is very demanding on coding basics, boundary processing ability and time management.
Google's OA is different from many companies. It does not deliberately create weird and unpopular questions, but it will go crazy on implementation details and code stability. Many people thought they had written it, but the hidden cases exploded as soon as they ran out. The questions I encountered this time were generally LeetCode Medium, the amount of data was quite large, and violence was basically impossible to pass.
Question 1: Collecting chessboard coins
The core of the question
The string board contains ‘T’ (chess piece), ‘C’ (coin), and ‘.’ (empty). Each time, any ‘T’ can jump exactly 3 spaces to the right. The target position must be empty (cannot fall on another ‘T’). Collect it when it lands on 'C' (only collect each one once). Ask how many coins can be collected at most.
Problem-solving ideas
Each chess piece can only take +3 steps, so the coins that a chess piece can collect must satisfy (coin position – chess piece position) % 3 == 0 and be on the right.
Since chess pieces cannot overlap, the order of moves is important, but N is usually small (the example is only about 10). The following simple and effective method can be used:
- Extract the positions of all T and C.
- Search with DP or BFS: The state records the set of positions of all current pieces + the set of collected coins (with a bit mask or set).
- Because the number of chess pieces is generally very small and the number of states is controllable, the maximum collection number can be obtained by searching for all legal moves.
Recommended implementation direction(Python): Use recursion + memo. The parameters are the current position of each chess piece (sorted tuple) and the bit mask of the collected coins. Try to jump 3 steps to the right for each chess piece. If the target is legal, update the status and continue the search. Record the maximum number of collected coins.
Question 2: Number selection
The core of the question
Given N two-digit numbers, you want to select as many numbers as possible so that all the selected numbers share at least one same number (any one from 0-9). Return the maximum number.
Problem-solving ideas
Any legal group must contain the same number d (one of 0~9). So directly:
Int solution(vector& numbers) {
int ans = 0;
for (int d = 0; d <= 9; d++) {
int cnt = 0;
for (int x : numbers) {
if (x / 10 == d || x % 10 == d) {
cnt++;
}
}
ans = max(ans, cnt);
}
return ans;
}This is the optimal answer, time O(10*N), N≤100 is completely sufficient.
Example verification:
- [52,25,11,52,34,55] → There are 4 numbers containing 5 → 4
- [11,33,55] → each d covers at most 1 → 1
The pitfalls I stepped on when I was preparing
When I first started preparing for Google, I just brushed up LeetCode without thinking. Later I found out that the efficiency was actually average. Because many questions on Google are not “original questions”. It's the kind where you've seen similar ideas, but implemented in even more disgusting variations. Later, I started to focus on real OA interviews and high-frequency classification, and the efficiency was obviously much higher.
I was atProgramhelp I have read a lot of Google 26NG’s OA compilation online, and there are many in it:
- High frequency graph question type
- Google style string questions
- Hidden test points that are easy to get stuck
- Common BFS variants
Some directions are really close to the actual exam.
