Google interview prep
7 practice questions on the topics candidates reported from Google interviews, with answers. The questions are ours; each one links to the interview report that names its topic.
DSA 6
-
Count the pairs i < j with a[j] - a[i] = j - i in [3, 4, 5, 2, 6, 7]. Rewriting it as a[j] - j = a[i] - i turns it into counting equal values. How many pairs are there?
- 3
- 5
- 6
- 4
Show the answer
D. 4
a[i] - i gives [3, 3, 3, -1, 2, 2]. Three 3s make 3 pairs and two 2s make 1, so 4. Counting values in a hash map makes it O(n) instead of checking every pair.
This topic is named in a candidate’s interview report: SDE-1 fresher interview, 2024, on Reddit.
-
A and B are both sorted, of lengths n and m. How fast can you count the pairs (a from A, b from B) with a > b?
- O(n * m)
- O(1)
- O(n log n * m)
- O(n + m), walking both arrays with two pointers
Show the answer
D. O(n + m), walking both arrays with two pointers
As a grows, the number of b values below it can only grow, so one pointer into B moves forward and never back. Each step of either pointer is O(1), giving O(n + m) in all.
This topic is named in a candidate’s interview report: SDE-1 fresher interview, 2024, on Reddit.
-
Messages arrive with timestamps. Print each one unless the same text was printed in the previous 10 seconds, without memory growing forever. What works?
- Keep every message ever seen in a set
- Compare each message with every earlier one
- Sort all messages at the end
- A hash map from text to the time it was last printed, plus a queue that drops entries older than 10 seconds
Show the answer
D. A hash map from text to the time it was last printed, plus a queue that drops entries older than 10 seconds
The map answers "printed in the last 10 s?" in O(1). Expiring old entries in arrival order through the queue keeps memory to the messages inside the current window.
This topic is named in a candidate’s interview report: SDE-1 fresher interview, 2024, on Reddit.
-
Match results say who beat whom. Which algorithm produces a ranking that respects every result, if one exists?
- Dijkstra's shortest path
- Union-find
- Binary search
- A topological sort of the graph with an edge from each winner to each loser
Show the answer
D. A topological sort of the graph with an edge from each winner to each loser
A consistent ranking is a topological order of the "beats" graph. Kahn's algorithm finds one in O(V + E); if a cycle remains (A beat B, B beat C, C beat A) no such ranking exists.
This topic is named in a candidate’s interview report: SWE L3 interview, 2024, on Reddit.
-
With a difference array, adding 1 to every element from l to r is diff[l] += 1 and diff[r + 1] -= 1, then a prefix sum. Starting from five zeros, apply the ranges (0, 2) and (1, 3). What is the array?
- [2, 2, 2, 1, 0]
- [1, 1, 1, 1, 0]
- [1, 2, 2, 2, 1]
- [1, 2, 2, 1, 0]
Show the answer
D. [1, 2, 2, 1, 0]
diff becomes [1, 1, 0, -1, -1] and its prefix sums are [1, 2, 2, 1, 0]. Each range costs O(1), so q ranges cost O(n + q), the line-sweep idea.
This topic is named in a candidate’s interview report: SWE L3 interview, 2024, on Reddit.
-
Root r has children x (edge cost 4) and y (edge cost 3). x has two leaf children, p (edge cost 1) and q (edge cost 2); y is a leaf. Cutting an edge costs its weight. What is the cheapest way to disconnect every leaf from r?
- 7
- 5
- 10
- 6
Show the answer
D. 6
For each child take min(cost of its edge, cheapest way to cut its own leaves). x: min(4, 1 + 2) = 3; y is a leaf, so its edge, 3. Total 6, in one post-order pass.
This topic is named in a candidate’s interview report: SWE L3 interview, 2024, on Reddit.
Aptitude 1
-
Die A has faces 1, 4 and 7, and die B has faces 2, 5 and 6. Both are rolled once. In how many of the 9 equally likely outcomes does A show the higher number?
- 3
- 5
- 4
- 6
Show the answer
C. 4
A = 1 beats nothing, A = 4 beats only 2, and A = 7 beats 2, 5 and 6: 0 + 1 + 3 = 4. Sorting both dice and counting with two pointers does this for large dice.
This topic is named in a candidate’s interview report: SWE L3 interview, 2024, on Reddit.