SDE - 1

This problem was actually a variation Unbounded Kanpsack Problem . I first gave the interviewer a naive recursive approach and then later optimised it using memoisation .

Naive Recursive Approach :
1) Create a recursive function ( int minCost(cost, idx , w) ) which returns the optimal answer for an array which starts with index idx and for a given weight w.
2) Now for every index idx , if cost[idx]!=-1 then I have three options : 

option1 -> Take that particular element and then recursively call for the whole array again (we won't increment idx here as we can take an element infinitley many times) with the same idx and a reduced weight w-idx-1(assuming 0-based indexing) . i.e.,
option1=cost[idx]+minCost(cost,idx,w-idx-1);

option2 -> Take that particular element and then recursively call for the rest of the array with index as idx+1 and a reduced weight w-idx-1(assuming 0-based indexing) . i.e., 
option2=cost[idx]+minCost(cost,idx+1,w-idx-1); 

option3-> Do not take that element at all and then recursively call for the rest of the array with index as idx+1 but with the same weight w.
option3=minCost(cost,idx+1,w);

Now , return the min({op1,op2,op3})

3)If cost[idx]==-1 , we have only one option - To not take that element at all and then recursively call for the rest of the array with index as idx+1 but with the same weight w.
i.e. return minCost(cost,idx+1,w)

4)Base Cases : 
a) If weight , w==0 then we can simply return 0 (do not take any element)
b) If index >= cost.size() or weight<0 , then simply return the max value of integer (INT_MAX in C++)

TC : O(3^n)
SC:O(n*w)


Dynamic Programmming (Using Memoisation ) : 
As we can observe , this problem has both optimal substructure as well as optimal subproblem properties and hence can be easily memoised using a map (key->pair of index and weight , value->answer for this state) i.e. 

dp[{idx,w}= min({op1,op2,op3})

Check if we have previously visited this state or not . If yes simply return the dp value

TC : O(n*w)
SC : O(n*w)

The idea is simple: along the path, record all prefix sums in a hash table. For current prefix sum x, check if (x - target) appears in the hash table.

Steps : 
1) We will be using a unordered map which will be filled with various path sum.
2) For every node we will check if current sum and root’s value equal to k or not. If the sum equals to k then increment the required answer by one.
3) Then we will add all those path sum in map which differs from current sum+root->data value by a constant integer k.
4) Then we will be inserting the current sum + root->data value in the map.
5) We will recursively check for left and right subtrees of current root
6) After the right subtree is also traversed we will remove the current sum + root->data value from the map so that it is not taken into consideration in further traversals of other nodes other than the current root’s.

TC : O(n) where n is the total number of nodes in the tree
SC : O(n)

If we light a stick, it takes 60 minutes to burn completely. What if we light the stick from both sides? It will take exactly half the original time, i.e. 30 minutes to burn completely.

1) 0 minutes – Light stick 1 on both sides and stick 2 on one side.
2) 30 minutes – Stick 1 will be burnt out. Light the other end of stick 2.
3) 45 minutes – Stick 2 will be burnt out. Thus 45 minutes is completely measured.

Collision doesn’t happen only in following two cases
1) All ants move in counterclockwise direction.
2) All ants move in clockwise direction.

Since every ant has two choices (pick either of two edges going through the corner on which ant is initially sitting), there are total 23 possibilities.

Out of 23 possibilities, only 2 don’t cause collision. So, the probability of collision is 6/8 or 3/4 and the probability of non-collision is 2/8 or 1/4.

General Tip : Before an interview for any company , have a breif insight about the company , what it does , when was it founded and so on . All these info can be easily acquired from the Company Website itself .

Tip 1 : The cross questioning can go intense some time, think before you speak.
Tip 2 : Be open minded and answer whatever you are thinking, in these rounds I feel it is important to have opinion.
Tip 3 : Context of questions can be switched, pay attention to the details. It is okay to ask questions in these round, like what are the projects currently the company is investing, which team you are mentoring. How all is the work environment etc.
Tip 4 : Since everybody in the interview panel is from tech background, here too you can expect some technical questions. No coding in most of the cases but some discussions over the design can surely happen.