Round 1
Question: You are given a graph of cities where each vertice denotes a city, and the edges represent the connectivity between two cities. You can assume that the cost to travel from one city to another connected by a single edge is 1 unit. There are two friends Alice and Bob who live in two different cities and want to reach to destination city to attend a concert. Both Alice and Bob plan to take cabs from their cities to reach the destination. They may decide to share a cab in order to minimize the total cost to travel the destination city. Your task is to find the minimum cost for both Alice and Bob combined to reach destination.
Example:
A - B | | D - C | | E - F
Alice=A, Bob=E, destination=C
Output: 3 (Alice go from A to D, cost=1. Bob go from E to D, cost=1. Then both Alice and Bob share a cab from D to C, cost=1. Hence, total cost = 1+1+1 = 3)
Candidate's Approach
I was not able to solve this problem as I was too fixated on trying to come up with an optimal approach so just kept ignoring the interviewer asking me to implement the brute-force solution. Would appreciate a lot if someone could provide an optimal solution for this problem, and how one should approach it!
Interviewer's Feedback
No feedback provided.
Round 2
Question: You have to write a function fn(value: int), which takes an integer as input and stores it in a data stream. You are also given a distance. After each insertion your method must return a triplet (x,y,z) of values from the data stream that satisfy the following condition: abs(x-y)<=distance && abs(y-z)<=distance && abs(z-x)<=distance. If no such triplet exists then return None.
Example: distance=3, input=[1,5,-2,3,2]
Output: [None, None, None, None, (1,2,3)]
Candidate's Approach
Started by thinking DP, but quickly realized that it won't be the most optimal approach. In the meantime, the interviewer gave the hint that think of this data stream as a number-line, so came up with an approach to sort the data stream after every insertion and find the triplets by doing a linear scan for a subarray of length 3 where the abs difference of the first and last element is less than or equal to distance. To get rid of sorting, I gave an optimized approach to maintain a sorted order of the data stream while insertion using a monotonic stack and a temporary stack. Interviewer was good with this approach.
Interviewer's Feedback
No feedback provided.
Round 3
Question: You are given a list of words, and you need to return the list of ambigrams. You will be given a dictionary of characters and their ambigram.
Example: [pod, swims, xyt]
Output: [pod, swims]
Candidate's Approach
It was straightforward, I iterated over each word and converted each character into its ambigram on the way using a two-pointer approach. The interviewer was satisfied and asked a follow-up.
Follow-up: You are given a list of words and you need to find the list of interesting words. A word is interesting if its ambigram is present in the input list. I updated my above approach and converted the input list into a set for quicker look-up. And could solve it in an optimized manner.
Interviewer's Feedback
No feedback provided.
Final Thoughts
I got a call from the recruiter the very next day of my interviews, but I couldn't pick it up because I was in a meeting, and since then I haven't heard back from the recruiter. I've emailed them but no response from the recruiter, even though the person who scheduled the interviews tagged them for asking for a reply but the recruiter didn't reply. So, don't know.