SDE - 1

Steps:
1) Sort all the words in descending order of their lengths.
2) Initialise res with first word in the vector + "#"
3) Now we just need to find, if other words in the vector + # are substring of res or not. if not, append that word to res.

Steps:
1) The idea is to sort the input , then we move forward from the beginning of the array till the end.
2) As soon as we found a condition that the current element is less than or equal to the previous elements then we need to update the current array element by adding 1 to its prev element .
3) At the same time we need to keep track of result by result += A[i-1]- A[i]+1;

Instead of counting all unique characters and struggling with all possible substrings,
we can count for every char in S, how many ways to be found as a unique char.
We count and sum, and it will be out answer.

Let, index[26][2] record last two occurrence index for every upper characters.
1) Initialise all values in index to -1.
2) Loop on string S, for every character c, update its last two occurrence index to index[c].
3) Count till loop ends . For example, if "A" appears twice at index 3, 6, 9 seperately, we need to count:
-For the first "A": (6-3) * (3-(-1))"
-For the second "A": (9-6) * (6-3)"
-For the third "A": (N-9) * (9-6)"

Time Complexity : O(N)
Space Complexity : O(1)

Approach 1 : 

Every position in the string has a depth - some number of matching parentheses surrounding it. For example, the dot in (()(.())) has depth 2, because of these parentheses: (__(.__))

1) Our goal is to maintain the score at the current depth we are on. 
2) When we see an opening bracket, we increase our depth, and our score at the new depth is 0. 
3) When we see a closing bracket, we add twice the score of the previous deeper part - except when counting (), which has a score of 1.

For example, when counting (()(())), our stack will look like this:

[0, 0] after parsing (
[0, 0, 0] after (
[0, 1] after )
[0, 1, 0] after (
[0, 1, 0, 0] after (
[0, 1, 1] after )
[0, 3] after )
[6] after )

TC : O(N)
SC: O(N)

Approach 2 (Space Optimised) :

Observe that the final sum will be a sum of powers of 2, as every core (a substring (), with score 1) will have it's score multiplied by 2 for each exterior set of parentheses that contains that core.

1) Keep track of balance (the number of ( parentheses minus the number of ) parentheses) of the string.
2) For every ) that immediately follows a (, the answer is 1 << balance, as balance is the number of exterior set of parentheses that contains this core.

TC: O(N)
SC:O(1)

Demand paging is a method that loads pages into memory on demand. This method is mostly used in virtual memory. In this, a page is only brought into memory when a location on that particular page is referenced during execution. The following steps are generally followed:

1) Attempt to access the page.
2) If the page is valid (in memory) then continue processing instructions as normal.
3) If a page is invalid then a page-fault trap occurs.
4) Check if the memory reference is a valid reference to a location on secondary memory. If not, the process is terminated (illegal memory access). Otherwise, we have to page in the required page.
5) Schedule disk operation to read the desired page into main memory.
6) Restart the instruction that was interrupted by the operating system trap.

We will preorder to generate TreeNodes, push them to the stack and perform postorder to pop them out.

1) Iterate on pre array and construct node one by one.
2) Stack saves the current path of the tree.
3) node = new TreeNode(pre[i]), if not left child, add node to the left. otherwise add it to the right.
4) If we meet a same value in the pre and post, it means we have completed the construction for current subtree. We pop it from stack.

TC : O(N)
SC: O(N)

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)

Static polymorphism (static binding) is a kind of polymorphism that occurs at compile time. An example of compile-time polymorphism is method overloading.

Runtime polymorphism or dynamic polymorphism (dynamic binding) is a type of polymorphism which is resolved during runtime. An example of runtime polymorphism is method overriding.

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.

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 .