SDE - 1

Approach : 

1) Create a visited array that keeps track of states already included in MST. Initially mark all states as unvisited.

2) Create a weight array.Initialize all weight values as INFINITE.

3) Assign the weight value as 0 for the first state so that it is picked first.

4) Create a set of size N where N is the number of states in the country. Every element of the set contains the weight value of state and the state number.

5) Until set is not empty, do the following.
5.1) Extract the min weight value state from the set. Let the extracted state be U.
5.2) Mark this state as visited.
5.3) Update weight of all adjacent states of U which are not visited yet.
5.4) For every adjacent state V, if the cost of the road from U to V is less than the current weight value of V, update the weight value of V.


TC : O( M * log N) , where N is the number of states and M is the number of roads.
SC : O( N + M)

Approach : 

1) Create a String ans to store the reversed string.
2) Initialize a variable i to 0 and iterate the whole string through a while loop.
3) Skip initial spaces by just incrementing i.
4) Create a String that will store the current word.
5) Add the currentword and space at the beginning of ans.
6) After traversing the whole string, check if the length of ans is greater than 0 then return ans after removing the last space otherwise return an empty string.

TC : O(N^2), where N = length of the string
SC : O(N)

Approach 1 (Naive Solution) :

1) Use two loops: The outer loop picks all the elements one by one.
2) The inner loop looks for the first greater element for the element picked by the outer loop.
3) If a greater element is found then that element is printed as next, otherwise, -1 is printed.


TC : O(N^2), where N=size of the array
SC : O(1)


Approach 2 (Using Stack) :

1) Push the first element to stack.
2) Pick rest of the elements one by one and follow the following steps in loop.
2.1) Mark the current element as next.
2.2) If stack is not empty, compare top element of stack with next.
2.3) If next is greater than the top element, Pop element from stack. next is the next greater element for
the popped element.
2.4) Keep popping from the stack while the popped element is smaller than next. next becomes the next
greater element for all such popped elements.
3) Finally, push the next in the stack.
4) After the loop in step 2 is over, pop all the elements from the stack and print -1 as the next element for them.


TC : O(N), where N=size of the array
SC : O(N)

Approach (Using DP) : 

1) Create a 2D integer matrix ‘dp’ of size n*m, where dp[i][j] stores the length of the longest path ending at ‘mat[i][j]’. Fill the entire matrix ‘dp[][]’ with INT_MIN initially.

2) Assign dp[0][0]:= 1

3) Run a loop where ‘i’ ranges from 1 to ‘m-1’ and for each ‘i’ if ‘mat[0][i]’ > mat[0][i-1], then assign dp[0][i] := dp[0][i-1] + 1, otherwise break the loop.

4) Run a loop where ‘i’ ranges from 1 to ‘n-1’ and for each ‘i’ if ‘mat[i][0]’ > mat[i-1][0]’, then assign dp[i][0] := dp[i-1][0] + 1, otherwise break the loop

5) Run two nested loops, In outer loop ‘i’ ranges from 1 to n-1, and inner loop ‘j’ ranges from 1 to m-1, and for each (i, j) do the following.
5.1) If mat[i][j] > mat[i][j-1], then assign dp[i][j] = max(dp[i][j], dp[i][j-1] + 1).
5.2) If mat[i][j] > mat[i-1][j], then assign dp[i][j] = max(dp[i][j], dp[i-1][j] + 1).

6) The largest value of the matrix ‘dp[][]’ will be the length of the longest path starting from (0, 0), we need to return this value.


TC : O(N*M), where N, M represents the number of rows and columns respectively.
SC : O(N*M)

The term “inheritance” means “receiving some quality or behavior from a parent to an offspring.” In object-oriented programming, inheritance is the mechanism by which an object or class (referred to as a child) is created using the definition of another object or class (referred to as a parent). Inheritance not only helps to keep the implementation simpler but also helps to facilitate code reuse.

1) A C++ virtual function is a member function in the base class that you redefine in a derived class. It is declared
using the virtual keyword.
2) It is used to tell the compiler to perform dynamic linkage or late binding on the function.
3) When the function is made virtual, C++ determines which function is to be invoked at the runtime based on the
type of the object pointed by the base class pointer.


Some rules regarding virtual function :

i) Virtual functions must be members of some class.
ii) Virtual functions cannot be static members.
iii) They are accessed through object pointers.
iv) They can be a friend of another class.
v) A virtual function must be defined in the base class, even though it is not used.
vi) We cannot have a virtual constructor, but we can have a virtual destructor

The approach is to use the preorder traversal of the tree to traverse the tree and check that we have visited the
current vertical level and if visited then we can check for the smaller horizontal level node and store it. Else we can
just update the vertical level as visited and store the node and horizontal level of the current node.


1) We have to create the map to check whether the horizontal level is visited or not as it will state the horizontal
distance of the node from the root node. Where key will represent the horizontal distance and the value is the pair
containing the value and level of each node.

2) We will traverse the tree using the preorder traversal.

3) Every time we check if the level of the current horizontal distance is less than the max level seen till now then we
will update the value and the level for this horizontal distance.

4) We will pass level-1 for the left child and level+1 for the right child to get the vertical level.

5) Print the values present in the map.

Answer :

Structure of an LRU Cache :

1) In practice, LRU cache is a kind of Queue — if an element is reaccessed, it goes to the end of the eviction order.
2) This queue will have a specific capacity as the cache has a limited size. Whenever a new element is brought in, it
is added at the head of the queue. When eviction happens, it happens from the tail of the queue.
3) Hitting data in the cache must be done in constant time, which isn't possible in Queue! But, it is possible with
HashMap data structure
4) Removal of the least recently used element must be done in constant time, which means for the implementation of
Queue, we'll use DoublyLinkedList instead of SingleLinkedList or an array.


LRU Algorithm :

The LRU algorithm is pretty easy! If the key is present in HashMap, it's a cache hit; else, it's a cache miss.

We'll follow two steps after a cache miss occurs:
1) Add a new element in front of the list.
2) Add a new entry in HashMap and refer to the head of the list.

And, we'll do two steps after a cache hit:
1) Remove the hit element and add it in front of the list.
2) Update HashMap with a new reference to the front of the list.


Tip : This is a very frequently asked question in interview and its implementation also gets quite cumbersome if you
are doing it for the first time so better knock this question off before your SDE-interviews.

UNION and UNION ALL are used to join the data from 2 or more tables but UNION removes duplicate rows and picks
the rows which are distinct after combining the data from the tables whereas UNION ALL does not remove the
duplicate rows, it just picks all the data from the tables.

For four dices in order to get sum >=22 we should get

6,6,6,6 = 1 (6666)
6,6,6,5 = 4C1 = 4 (5666,6566,6656,6665)
6,6,6,4 = 4C1 = 4 (4666,6466,6646,6664)
6,6,5,5 = 4C2 = 6 (5566,5656,5665,6655,6565,6556)
So there are 15 favorable cases.

The total cases is 6*6*6*6=1296.

So we’ll get 15/1296 = 5/432

To be divisible by 4, the number has to end with the last two digits forming a number divisible by 4. Since there are only 5 digits: 1, 2, 3, 4, 5.
So, possible last two digits according to divisibility by 4:
12
24
32
52

For each of them we now have to put the remaining numbers in front: 3x2x1, therefore 6 combinations for each number set = 6×4 (we have 4 sets from above) = 24.

So, required probability is:

P = Number of desired outcomes / number of possible outcomes
= 24 /(5*4*3*2*1)
= 24 / (5!)
= 24 / 120
= 1/5

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.

If you get this question, it's an opportunity to choose the most compelling information to share that is not obvious from
your resume.

Example :

Strength -> I believe that my greatest strength is the ability to solve problems quickly and efficiently, which makes me
unique from others.

Ability to handle Pressure -> I enjoy working under pressure because I believe it helps me grow and become more
efficient.


Tip : Emphasize why you were inspired to apply for the job. You can also explain that you are willing to invest a great
deal of energy if hired.

These are generally very open ended questions and are asked to test how quick wit a candidate is. So there is
nothing to worry about if you have a good command over your communication skills and you are able to propagate
your thoughts well to the interviewer.