Background
Two years of full-stack development experience, and a competitive programmer (Codeforces Master). Applied through Google Careers, but did not pass the referral process. Received a call from a recruiter during the first week of April, who asked about my background, experience, and salary expectations. She requested that I provide five available dates for interviews, with a maximum of two weeks between each interview to prepare. However, the actual interview dates were much later than the dates I provided.
Screen Interview
*Problem: *
I was asked a MEX kinda problem where there are sequence numbers (or frames) of type long long int and some initial sequence number x. There are two types of queries:
· Add some sequence number y
· Out of all the sequence numbers that are missing, fetch the minimum
*Solution I gave: *
Used a HashSet to store each incoming sequence number and a variable that indicates the current missing sequence number. At every insertion, the increment of the current minimum gets triggered where it gets incremented by 1 till it encounters a missing sequence number. Return this number for the query type 2. Discussed the time complexities later.
Follow up
· Why don't you trigger the increment in the get minimum call?
My answer: We can have the increment in any one of the two functions; optimal placement can be dependent on query patterns. If there are less frequent calls of query type-2, then we can place it in the get function.
· What is the real-world application of this problem? Why are we having an initial sequence number?
My answer: This is a classical video loading problem where the initial sequence number represents the starting frame of the current window and video frames < that timestamp are deleted. The missing number represents the frame that got missed and requires a retransmission.
· How do you identify the frames that are received but we are not able to process (corrupted)?
My answer: By pushing them into a HashSet whenever received and deleting from it when processed.
· How do you distinguish between the corrupted ones and the ones that are being processed?
My answer: Timestamp-based invalidation
Interview Process
Round 1：Technical Interview
Problem:
Given a garland represented by an array of size n where there are exactly d (even) diamonds and r (even) rubies, you are allowed to make at most 2 cuts to divide the array into different portions and group them into two parts such that the number of rubies and diamonds is the same in both parts.
My response:
If 1 cut: Only possible at the middle.
If 2 cuts: First and the last segment belong to the same part, so do a sliding window of fixed length n/2. O(n) solution with O(1) extra space.
Follow up:
What if there is a stone of one more type and you can make at most 3 cuts?
My response: Check for <= 2 cuts: same process as earlier.
For 3 cuts: First and third segments belong to the same part, so fix the first segment and do a similar process as earlier, yielding an O(n^2) solution. (Did not implement)
Round 2：Technical Interview
Problem:
There is an undirected graph where each node represents the home of a person. Two persons represented as nodes a and b. a and b should reach a node c while traveling independently, or both of them can club at some point and reach c. Find the minimum cost required for both of them to reach the destination (edges traversed). Note: If a and b both traverse an edge together, it is counted as cost 1.
My response:
Pre-calculate all the shortest paths from every node to every other node. Then iterate for each node and consider that a and b come to this point independently and go from here to the destination. Compare and update this distance with the answer.
Time complexity: O(n^2) (for calculating the minimum distance between each pair)
Follow up:
What if there are 3 (a, b, and d) friends that are reaching the destination c?
My response: 3 combinations: (a, b first meet, club and then meet d), (b, d first and then a), (d, a and then b). Iterate for each pair of possible joining points of the path for each combination and update the answer. (Did not implement)
Round 3：Technical Interview
Problem-1:
Given a linked list, remove a node with the given value
My response: Implemented it quickly
Problem-2:
Construct a maze of size n*m by drawing lines in canvas in such a way that there should be exactly one path possible between any two pairs of cells in the maze
My response: Initially came up with an approach where we start in the first cell (1,1), go straight if possible else turn left. This will give a spiral path in the maze. Draw lines between every two pairs of cells if there is no edge between them. Spent 10 mins explaining this idea before realizing (by self) that there is a simpler approach where we draw all the horizontal lines except for one column in each row. Explained this idea. (Did not implement)
Round 4：Technical Interview
Problem:
Given a set of lines inside an n*m rectangle, find the number of squares that can be formed.
My response: Gave solution with preprocessing and stored values in a data structure that stores the maximum length of continuous lines that are ending at the given point for each point (in both the horizontal and vertical directions). Iterate through each point and each length and check if a square can be formed using the pre-computed values. Interviewer said he was satisfied with the solution.
Interview Summary & Suggestions
Recruiters indicated that they had received negative feedback in the first two rounds. The last interviewer said he couldn't understand my solution. However, during the interview, he consistently agreed with my proposal and gave me constant affirmation. I thought I would pass the interview smoothly, but I was unexpectedly rejected. Those preparing for interviews should practice thoroughly. Don't get too excited if the interviewer gives you positive feedback, and don't doubt yourself if the interviewer is serious. Anything is possible. If you encounter any difficulties or confusion, feel free to come here to find solutions!
Top comments (0)