SDE - 1

• 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 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.

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

I initially tried a 2D DP solution where dp[i][j] indicates the length of the longest sequence with ending at i containing j as a digit. It’s a N X 10 DP matrix. The interviewer asked me why I needed a 2D DP solution and I struggled to convince him. I wrote the code for it. It wasn’t completely correct. I was missing something. After thinking for a while I narrowed down to a solution containing only 10 elements dp[0], dp[1], dp[2].. dp[9] which is updated every time I see a new number. I take a number, I go through all digits in the number and find value = 1 + max(dp[d] for all digits d in the number). Set this value to dp[d] for all digits in the number. He gave a hint to take the max and finally gave a solution to the interviewer and he was satisfied with that solution.

I drew a few trees and asked him the output for those examples. He asked me to say it myself and I did. I thought of doing a post-order traversal as we need to visit the root’s left and right child before visiting root. In the post-order traversal, we keep the sum of root’s left and right child in a variable sum. We take the difference of this sum and root data. If the sum is greater than root’s data, we replace the root with the sum. Otherwise, we have to distribute the root’s value to the root’s left and right child so that all the three conditions are satisfied. (We can’t reduce the value at any node). He asked me to write the code for it and I did. 

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

This is most basic question of OS and I explained it very well using a tabular representation.

I firstly told him necessary conditions for deadlock and then explained him that if we don’t let all conditions fulfilled for deadlock then it may be prevented.

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.

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