SDE - 1

Problem approach
I used the Kadane algorithm to solve this question and wrote a clean code with which could work on negative numbers also.

I solved this question using a priority queue(max heap) by inserting all elements in the priority queue and then taking the maximum two out of them and pushing their sum again to the priority queue.

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.

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 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’l