Phone Screen Round
Questions:
You are given 4 patterns
F1 - *
F2 - 192.168.*
F3 - 192.168.2.*
F4 - 192.168.2.1
You are given queries
192.168.7.1
192.168.2.1
192.168.2.7
192.167.1.1
You have to return pattern name which is most precisely matching with the query.
Answer: [F2, F4, F3, F1]
Candidate's Approach
I suggested to use Trie, and the interviewer agreed. I was able to finish coding with 5 minutes to spare.
Interviewer's Feedback
Solved the question optimally, but the interviewer didn't have time to ask follow-up questions. Good to go for the next round.
Onsite 1
Questions: You have a wooden table of square shape, you are provided with a list of cakes. Cakes are square in shape and placed randomly on the table. You are given the bottom left corner's coordinate for the cake and the length of a side of the cake. You need to find a y-coordinate such that the area of cakes is divided into exactly half.
Candidate's Approach
I suggested using the Line Sweep Algorithm and did a couple of dry runs with the interviewer. I was able to solve this with a small hint using Binary Search.
Interviewer's Feedback
Overall feedback was positive, but the interviewer mentioned he had given a hint. (Hire)
Onsite 2
Questions:
You are given an integer array nums of length n and a 2D array queries, where queries[i] = [l, r].
For each queries[i]:
- Select a subset of indices within the range [l, r] in nums.
- Decrement the values at the selected indices by 1.
A Zero Array is an array where all elements are equal to 0. Find out whether the array can be made a zero array after applying the queries.
Candidate's Approach
I suggested the line sweep algorithm again, which was working correctly with a time complexity of O(n). However, the interviewer updated the question to find out the first query where the array will be made a Zero Array. I was not able to solve this problem optimally and suggested an O(n^2) solution, but the interviewer wanted an optimal approach. As we were running out of time, I was asked to code the Line Sweep code for the first question. I later searched and think the optimal solution involves using Segment Trees, which I hadn't practiced before.
Interviewer's Feedback
Negative feedback. (Leaning No Hire/ No Hire)
Onsite 3
Questions: MK Average - MK Average Problem
Candidate's Approach
I solved this using TreeMap. I made one error in the code, which was pointed out by the interviewer as I was explaining my code, but I quickly fixed it. I provided a solution with an overall time complexity of O(M * log (k)). The interviewer asked if I could optimize it further, but I couldn't think of a better solution.
Interviewer's Feedback
HR mentioned that the feedback was average, and the interviewer noted that there was an error in the code.
Googlyness
Standard situation-based questions.
Self Verdict
Strong Hire.
Currently, waiting for further steps, but the recruiter mentioned that due to the feedback not being great, I might have to give additional coding rounds, so I need to keep practicing DSA. Chances are slim, but fingers crossed for now.