SDE - Cloud Developer

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

s1 - I simply decrypt the string by reading substring
s2 - 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.

s1 - 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.
s2 - 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.

s1- 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. 
s2- 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. 
s3- He seemed convinced with the approach. He gave me a graph after all the preprocessing done and finally asked me how to minimise it. So I used a greedy method. I was settling the amount of the person who has to get the largest amount by giving the amount of the people who has to give lesser amounts and he said that’ll work.

s1- I suggested to do a depth first search keeping a set which contains all elements upto a given node. Once I reach a particular node, I check if it’s already in the set. If its already in the set, I return because that element has already been visited and is not a special node.
s2- Otherwise, I increase the count of a global variable by 1 and push that element to the set. Then I go through the adjacency list of that element and call this function recursively. Once I return from the element after visiting its neighbors, I pop the element from the set. I told him the approach and he asked me to write the code for it. He was convinced with the approach and he liked the code.

s1- I solved this question using three-pointers and this problem was a variation of dutch national flag problem.
s2- The interviewer was satisfied by my approach as this was the most optimal approach.

s1- I implemented it first by sorting two strings and comparing them. 
s2- He asked me to write a better approach. So I used a hashmap to do it.