SDE - 1

Steps: 

1) Create a recursive function that takes index of node of a graph and the destination index. Keep a global or a static variable count to store the count. Keep a record of the nodes visited in the current path by passing a visited array by value (instead of reference, which would not be limited to the current path).
2) If the current nodes is the destination increase the count.
3) Else for all the adjacent nodes, i.e. nodes that are accessible from the current node, call the recursive function with the index of adjacent node and the destination.
4) Print the Count.

Approach : This problem was based on Topological Sorting .

The first node in the topological ordering will be the node that doesn't have any incoming edges. Essentially, any node that has an in-degree of 0 can start the topologically sorted order. If there are multiple such nodes, their relative order doesn't matter and they can appear in any order.

Algorithm : 

1) Initialize a queue, Q to keep a track of all the nodes in the graph with 0 in-degree.
2) Iterate over all the edges in the input and create an adjacency list and also a map of node v/s in-degree.
3) Add all the nodes with 0 in-degree to Q.
4) The following steps are to be done until the Q becomes empty.
4.1) Pop a node from the Q. Let's call this node, N.
4.2) For all the neighbors of this node, N, reduce their in-degree by 1. If any of the nodes' in- 
degree reaches 0, add it to the Q.
4.3) Add the node N to the list maintaining topologically sorted order.
4.4) Continue from step 4.1.

Steps : 

1) First, we sort the list as described. 
2) Then, we insert the first interval into our merged list and continue considering each interval in turn as follows - 
2.1) If the current interval begins after the previous interval ends, then they do not overlap and we can 
append the current interval to merged. 
2.2) Otherwise, they do overlap, and we merge them by updating the end of the previous interval if it is 
less than the end of the current interval.

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

Follow Up : Prove your Greedy solution .

A simple proof by contradiction shows that this algorithm always produces the correct answer. First, suppose that the algorithm at some point fails to merge two intervals that should be merged. This would imply that there exists some triple of indices i, j, and k in a list of intervals ints such that i < j < k and (ints[i],ints[k]) can be merged, but neither (ints[i],ints[j]) nor (ints[j],ints[k]) can be merged . We have following inequalities from this scenario : 

ints[i].endints[j].endints[i].end≥ints[k].start
​


We can chain these inequalities (along with the following inequality, implied by the well-formedness of the intervals: ints[j].start <= ints[j].end ) to demonstrate a contradiction:


ints[i].end < ints[j].start ≤ ints[j].end < ints[k].start
ints[i].end ≥ ints[k].start
​


Therefore, all mergeable intervals must occur in a contiguous run of the sorted list.

1. The idea is to reduce the problem from finding a path from source to destination to finding a path from some node to destination and building our answer up.
2. From the current cell, we look if there exists a neighbor from where I can reach the destination if no such neighbor exists we return -1.
3. Else if a path exists we take the longest path then add 1 in it ( to account for the transition from the current cell to a neighbor).
4. In the end, we change the visited current node to false and return the answer

Approach 1 (Using DP ) :

This is a classic Dynamic Programming problem.
Steps : 
1) Let dp[i] is the longest increase subsequence which ends at nums[i] . 
2) For every i from 0 to n , traverse backwards from j=i-1 to j=0 and check if nums[i]>nums[j].
3) If nums[i]>nums[j] , update dp[i]=max(dp[i] , dp[j]+1)
4) Finally return the maximum element from the DP array

TC: O(N^2)
SC: O(N)

Approach 2 (Using Binary Search and Greedy ) :

Steps:
1) Maintain a vector v (this will remain sorted at all times) .
2) Push the first element into the vector v.
3) Run a loop from 1 to n and for every element check if nums[i]>v.back()
4) If nums[i]>v.back() , simply push nums[i] into v .
5) Else , find the lower_bound position of nums[i] in vector v and replace that element with nums[i] .
6) Finally , the length of the vector v gives us the length of the LIS.
7) To get the final sequence we can maintain a path vector where path[i] stores the index of the previous number in LIS


TC : O(N*Log(N))
SC : O(N)

This was a preety standard Binary Search Question and I had solved this question before on platforms like LeetCode and CodeStudio . I was asked this question to test my implementation skills and how well do I handle Edge Cases .

Approach :
1) The idea is to find the pivot point, divide the array in two sub-arrays and perform binary search.
2) The main idea for finding pivot is – for a sorted (in increasing order) and pivoted array, pivot element is the only element for which next element to it is smaller than it.
3) Using the above statement and binary search pivot can be found.
4) After the pivot is found out divide the array in two sub-arrays.
5) Now the individual sub – arrays are sorted so the element can be searched using Binary Search.

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

Step 1- Making the ‘BST’ :

Let insert(TreeNode* <int> ROOT, int VAL) be a function which insert data into ‘BST’.

Now consider the following steps to implement the function :

1. If ‘ROOT’ is NULL then make a new Node with data and return it.
2. If 'VAL' is less than data of ‘ROOT’ then do:
   1. Make a recursive call with the left child of ‘ROOT’ as ‘ROOT’.
   2. Increase the size of the left subtree of ‘ROOT’ by 1.
3. Otherwise do:
   1. Make a recursive call with the right child of ‘ROOT’ as ‘ROOT’.

Now iterate over the ‘ARR’ and feed vales in ‘ARR’ to insert to generate ‘BST’.

Step2 -Find Rank of ‘ARR[K]’ say ‘NUM’ from ‘BST’:

Let getRank(TreeNode* <int> ROOT, int NUM) be a function that returns the size of the left subtree of the node with the value ‘NUM’ or we can say Rank of ‘NUM’. 

Now consider the following steps to implement the function :

1. If data at ‘ROOT’ is equal to ‘NUM’ then return the size of the left subtree.
2. If data at ‘ROOT’ is less than ‘NUM’ then do:
   1. Make a recursive call with the left child of ‘ROOT’ as ‘ROOT’.
3. If data at ‘ROOT’ is greater than ‘NUM’ then do:
   1. Let RIGHT_SIZE = Make a recursive call with the right child of ‘ROOT’ as ‘ROOT’.
   2. Return (size of the left subtree+RIGHT_SIZE+1).

Approach : 

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.