Software Engineer

I have done this problem earlier so got the DP based approach during the test and this approach passed all the test cases.

I simply decrypt the string by reading substring and their frequency and append current substring to the decrypted string and after the end of traversal of given string our answer will be kth element of the decrypted string.

I asked for some clarifications whether I should print all distinct x‘s or if I should print an x if a pair of +x and -x is encountered. The first approach I told was to use a map and I was keeping a flag for +x and -x if it’s found once. Later he asked me to print all pairs, so I stored the frequencies of all the elements in the map and iterated through the negative elements and for each element x , I would print x min(count[-x],count[+x]) times. He said he can’t afford that much space and he wanted me to optimise space further. So I told him a 2 pointer approach where I sort the array once and then keep two pointers to the start and end. I would move the start pointer forward if the sum is less than 0 and I’ll move the end pointer backward if the sum is greater than 0. He was fine with the solution and asked me to code it in a paper. I wrote the code and walked him through it.

Here the interviewer told me about an app called splitwise which i had used once. In the application each user adds the amount he spends and it’s shared equally among users of the app. The aim is to minimise the number of give and take operations. I initially thought of a very naive approach where I wanted to create classes for each person and expenditure and iterate through the expenditures of other people to find how much a person should give or take. When I took a closer look I got the idea of modelling it as a directed graph and adding directed edges for transactions. With the graph, I thought of taking the difference between the pair of edges between two people to reduce a give-and-take operation to a single give/take operation. There was a catch, if A has to give B Rs.10, B has to give C Rs.10, and A has to give C Rs.10, the minimum operation to do is to give Rs.20 from A to C. B is not involved here as he has to spend all he gets. So I said we could preprocess the graph with the numbers on the incoming and outgoing edges. If the total flow is 0, we could remove that node. He seemed convinced with the approach. He gave me a graph after all the preprocessing done and finally asked me how to minimize it.

Tip 1: This is the most basic question of OS and I explained it very well using a tabular representation.
Tip 2: I firstly told him the necessary conditions for deadlock and then explained to him that if we don’t let all conditions fulfilled for deadlock then it may be prevented.
Tip 3: I wrote a class to implement a character Trie using a vector of nodes as children. He asked me to improve on space. So I used a hashmap to store the child nodes only if a child exists. I wrote the code for insertion and finding a word and walked him through.