Total Years of experience: 1.5 yrs
Date: December 29, 2020
Position: SDE-1

First Round

Design Splitwise (similar to https://workat.tech/machine-coding/article/how-to-design-splitwise-machine-coding-ayvnfo1tfst6)

I was given 1 hour to implement splitwise with object oriented approach and production ready code. I choose cpp for my code. It took longer than 1 hour, and due to some issue in my parsing logic for input, I wasn't able to test it. Had follow up questions for edge cases, each of the use case mentioned in the doc was checked.

Second Round

1. https://leetcode.com/problems/find-the-duplicate-number/, I gave approach 1 (sorting) & approach 2 (using map) to the interviewer but he didn't seem satisfied since he wanted me to solve it in O(1) space complexity (approach 3) of the solution - Floyd's Tortoise and Hare (Cycle Detection)

2. Given a stream of numbers, find nth recurring recently used number.
   Example - [1, 1, 2, 3, 2, 4] Suppose n = 2

   2nd recurring most recently used after 0th index = -1 (since only one item is there that is 1)
   2nd recurring most recently used after 1st index = -1 (since only one item is there that is 1)
   2nd recurring most recently used after 2nd index = 1 (we have 2 items, 1 occurs twice)
   2nd recurring most recently used after 3rd index = 1 (we have 3 items, 1 occurs twice, 2 & 3 occurs once)
   2nd recurring most recently used after 4th index = 2 (we have 3 items, 1 occurs twice & 2 occurs twice, but 2 is the most recent one so answer is 2)
   2nd recurring most recently used after 5th index = 2 (we have 4 items, 1 occurs twice & 2 occurs twice, but 2 is the most recent one so answer is 2)

   I gave a solution where we maintain a data structure similar to map<int, set<pair<int, int> > > mp such that - each element goes to it's respective count index. mp[x] -> where x is the number of times an element occurs, with value equal to list of all the items with that count. If x occurs again, we can delete it from mp[x] list & add it in mp[x + 1]. After last item, it would look like -
   1-> 3,4
   2-> 1, 2
   Also we would need to maintain some sort of "id" to maintain order in set of whether it's recent used or not, in that case it would look like -

   1-> (4, 3), (6, 4)
   2 -> (2, 1), (5, 2)

   the last element of nth item would be the answer.
   I was running short of time, so could only tell the approach. Didn't get time to implement.