Round 1: DSA Round
There are n players, each with a distinct rank from 1 (highest) to n (lowest).
A player with a better (lower-numbered) rank always beats a player with a worse (higher-numbered) rank.
We are given m match results (a, b) meaning player a defeated player b.
Based on these results, we must determine which players' ranks can be precisely inferred.
Sol:
A player's rank can be precisely determined if:
We know exactly how many players are stronger (better rank) and weaker (worse rank) than that player.
If stronger_count[i] + weaker_count[i] = n - 1, then we can deduce their rank uniquely.
Used a graph traversal approach:
Treat each player as a node.
Draw a directed edge from winner → loser for each match result.
For each player:
Count how many players are stronger (can beat them) by traversing the reverse graph (edges reversed).
Count how many players are weaker (they can beat) by traversing the original graph.
If the sum of stronger and weaker players equals n-1, we can deduce their exact rank.
n = 5
matches = (4 beats 3), (4 beats 2), (3 beats 2), (1 beats 2), (2 beats 5)
Build graphs:
Win Graph:
Copy code
4 → 3, 4 → 2
3 → 2
1 → 2
2 → 5
Loss Graph (reverse):
Copy code
3 → 4
2 → 4, 2 → 3, 2 → 1
5 → 2
For player 4:
Weaker BFS: from 4 → {3, 2, 5} → count = 3
Stronger BFS: from 4 → {} → count = 0
Total: 0 + 3 = 3 ≠ 4 → rank not precise.
For player 2:
Weaker BFS: {5} → count = 1
Stronger BFS: {4, 3, 1} → count = 3
Total: 1+3=4 = n-1 → Rank is precise (Rank 4).
Similarly check all players.
Verdict: Hire (Very Positive)
Round 2: DSA Round
An office issues license plates in 6 consecutive ranges, each range having a fixed number of letters (A–Z) and digits (0–9).
All license plates are exactly 5 characters long.
The ranges are issued in the following order:
0 letters + 5 digits
00000 ... 99999
1 letter + 4 digits
A0000 ... Z9999
2 letters + 3 digits
AA000 ... ZZ999
3 letters + 2 digits
AAA00 ... ZZZ99
4 letters + 1 digit
AAAA0 ... ZZZZ9
5 letters + 0 digits
AAAAA ... ZZZZZ
Task
string getNthPlate(long long n);
that returns the n-th license plate in the global sequence (0-indexed).
Examples
Input: n = 0
Output: "00000"
Input: n = 1
Output: "00001"
Input: n = 100000
Output: "A0000"
Input: n = 100001
Output: "A0001"
Solved using Brute and optimised it further with storing the ranges in a vector and then looping over ranges (which are fixed ) to check in which range sequence n lies,
to get the no of digits - n/10^digits of this seq range
to get no of words - n%10^digits of this seq range
n-=count (so we consumed this range count of sequences)
will do it until n is > 0
once zero , will just call the encode function to return the string of sequence, of this particular range.
gave dry run as well properly.
Verdict: Hire (Positive)
Round 3: DSA Round
We have multiple application versions, each defined by the OS version range they support.
A query gives us a specific OS version, and we need to return the latest app version (highest release order) that supports it.
Each app has:
name (e.g., "v1", "v2", "v3")
minOS (lower bound, or -∞ if no bound)
maxOS (upper bound, or +∞ if no bound)
Example
Applications:
v1: min=14, max=+∞, order=1
v2: min=-∞, max=8, order=2
v3: min=12, max=16, order=3
OS = 3 → v2 (falls in [-∞,8])
OS = 11 → None (no version covers it)
OS = 14 → v3 (v3 covers [12,16] and is newer than v1)
OS = 7 → v2 (covered by v2)
OS = 20 → v1 (covered only by v1)
Brute Force Approach
For each query, scan all apps and check if minOS <= os <= maxOS.
Track the one with highest releaseOrder.
Complexity: O(N·Q).
Gave optimised little bit to sort based on release versions order and then start checking from the latest version.
Interviewers asked to code it just without asking to further look for optimal soln. (I was not able to think of more optimistaion at that time)
Verdict: No Hire (got the feedback, he was not able to optimise it with some advanced data structures).
Later on cliked in my mind , actually its a complex one for me to think of Sweep line with the Disjoint segments at that time
Convert all app ranges into “events”: (minOS, START, app) and (maxOS+1, END, app).
Sweep line from left to right:
Maintain a max-heap of active apps by releaseOrder.
At each step, record the best (latest) app covering the current span.
This produces disjoint segments where each segment has a fixed “latest app.”
Query resolution becomes O(log K) with binary search on segments.
but still dont know the exact solution what it could be for this, either segment tree or not(as it can be overkill for this problem).
Round 4: Googlyness Round
Behavioral questions , went for 40 mins
Verdict: Hire (positive)
Final Verdict: Rejected (just because of Round 3)
Note: It seems Google have started taking 3 DSA interviews now rather than 4 earlier, as told by HR as per change in process.
But I think complexity of questions have been increased with this.
Let me know if anyone wants code for any of the problems above.
Had other offer at that time of Microsoft
read here - https://leetcode.com/discuss/post/7126106/microsoft-l61-interview-experience-11-ju-2zdp/
Tip: Cover the advanced topics as well if looking for MAANG especially Google.
