SDE - Intern

• First I gave the interviewer brute force approach by checking each interval starting and ending time with other every interval. Then I gave him sorting solution with complexity O(N log N) in which I sort all intervals according to start time and then compare them in O(n) time.

• I  basically use the relation between a(n+1) and a(n) to find a(n). Replace n with n-1, then with n-2 then with n-3 and so on. After this, we have to multiply all these substituted relations. And after multiplication, most of the terms will cancel and we will get a relation between a(n+1) and a1, also substitute the value of a1 from the given statement. After this, we have a(n+1) in form of power of 2. Now replace n+1 with n, hence we will get a(n), now take log2 both side and you will get log2(a(n)). So I just simplify the relation and used some mathematics.

• I made a graph in between the first mismatched character of every adjacent alphabet pair and applied topological sorting.

• I implemented hashmap using hashing with chaining technique in C++ and interviewer further extended discussion on hashing with chaining.

• Firstly I gave the interviewer a completely brute force approach, and then I gave him max heap solution by implementing it through priority queue.

• I took examples there and got the logic of the puzzle. Answer will be yes. Make 2 piles with equal number of coins and in total there will be 5 heads and 5 tails. Now, flip all the coins in one of the pile.Now both piles have the same number of heads. Take an example: suppose one pile have H H T T H and another pile have T H T H T. Now flip the pile one, so pile one will become T T H H T, now both the piles will contain the same number of heads that is 2.

I solved this puzzle using a short example. I took 8 bottles and feed three rats with wine. I fed each rat 4 bottles. Now, suppose three rats have the following wine configuration:

Rat 1 - 3 6 7 8 (0 0 1 0 0 1 1 1)

Rat 2 - 2 5 7 8 (0 1 0 0 1 0 1 1)

Rat 3 - 4 6 5 8 (0 0 0 1 1 1 0 1)

If no rat die then we can say that poison is in bottle 1, if rat 1 dies then we can say that poison is in bottle 3 as it was first bottle to fed by rat 1, similarly, if Rat 2 dies than bottle 2 was poisoned and if Rat 3 dies bottle 4 was poisoned. If both Rat 1 and Rat 3 die, then bottle 6 has poison. If Rat 1 and Rat 2 die, then we can say that bottle 7 has poison. If both Rat 2 and 3 dies, then bottle 5 have poison, and if all rats die then bottle 8 was poisoned. So making combinations, we can see that for 8 bottles you need 3 rats. Similarly, for 4 bottles you need 2 rats or in general, for 2^n bottles, you need  n rats. So for 1000 bottles, you will need Log2(1000) which approximately comes out to be 10 ,so 10 was the answer of that puzzle. So just by taking shorter example I solved this puzzle and the interviewer was satisfied with my answer.

• I gave him a brute force type approach by starting from the second drop and comparing it with the previous one and after checking the condition of speed and time if they can mix or not. Similarly, this was done for each drop. But I can’t come up with an optimal solution which the interviewer wanted. The interviewer wanted a greedy approach by me.

I told him about the normalization process starting from definition and gave him an example of normalization. I only remember 2-3 purposes of normalization, which I told to interviewer like to minimize redundancy, to break bigger tables in smaller and form links between them.

• I told the interviewer about the ACID property by giving its full form and explaining each and every property through real-life example of ATM transaction.

• I gave a definition of Virtual private network to the interviewer which allows a secure tunnel to be created across a network. I also gave him an example of dial up connection to the server using VPN.

• I told him few points which I remembered there like basic definitions of both, layers on which they are working ( hub on physical layer & switch on data link) and mode of transmission used by them.

 Following are the two characteristics of red-black trees.

1. The nodes in a red-black tree are colored. Each node can be either red or black.

2. When a node is inserted or deleted in a red-black tree. certain rules have to be followed to ensure that the tree remains balanced after the node deletion or insertion.

Explained him through the diagram and all properties of the RB tree.

• I started discussion  by giving information about the features of my projects. Then told him about the tech stack used in the project , and then about the database used. Also told him about the flow of the project through pictorial representation.

• Project Tip - Also do prepare for the most challenging task in your projects as this is the most frequent question asked by the interviewer.