SDE - 1

Approach : 

1) Take the variables 'MINJUMP' to store the minimum number of jumps,’curEnd’ to store the farthest index we can go from the current index and 'CURFARTHEST' to store the farthest we can go with the help of elements we have encountered till now.

2) We initialise the value of 'CUREND' and 'CURFARTHEST' to be 0.

3) Let's say the range of the current jump is ['CURBEGIN', 'CUREND'].

4) 'CURFARTHEST' is the farthest point that all points in ['CURBEGIN', 'CUREND'] can reach.

5) Once the current index ‘i’ reaches the 'CUREND' we have reached the maximum possible index we could have reached in 1 jump, therefore, we trigger another jump.

6) We then set the new 'CUREND' with 'CURFARTHEST', until 'CURFARTHEST' is equal to the last index of the given sequence.


TC : O(N), where N = length of the sequence
SC : O(1)

Approach (Using BFS) : 

1) Declare an empty array say, ‘answer’ to store all nodes that don’t have a sibling node.

2) Declare an empty queue and push the root node of the binary tree to it.

3) Run a loop until the queue is not empty.

4) Pop the front element from the queue, say ‘current’.

5) If both, left and the right child of ‘node’ are not NULL, then push ‘node -> left’ and ‘node -> right’ in the queue.

6) Else two conditions will occur:

7) If the right child of ‘node’ is not NULL, then add data of the right child to ‘answer’ and push ‘node -> right’ in the queue.

8) If the left child of ‘node’ is not NULL, then add data of the left child to ‘answer’ and push ‘node -> left’ in the queue.

9) Sort the ‘answer’.

10) Finally, return the ‘answer’.


TC : O(N), where N = total number of nodes in the given binary tree.
SC : O(N)

Approach (Using BFS) : 

1) Define a class with the following data members
a. ‘X_COORDINATE’ denoting the x-coordinate
b. ‘Y_COORDINNATE’ denoting the y-coordinate
c. ‘STEP_COUNT’ denoting the number of steps.

2) Take two arrays ‘DIRECTION_X’ and ‘DIRECTION_Y’ storing the direction in which the knight can move.

3) Create a queue to store the class objects.

4) Take a visited array to mark the cells already visited and initialize it to false.

5) Push the initial position of the knight to the queue and mark it as visited.

6) Loop till the queue is not empty.

7) Pop the front element.
a. If the current cell is equal to the target cell, return the 'STEP_COUNT’ which is the minimum step a Knight will take to reach the target position.
b. Else, loop for all the reachable coordinates. If the coordinate is not yet visited and is reachable, push it to the queue along with the incremented value of ‘STEP_COUNT’.


TC : O(N^2), where N = number of rows/columns.
SC : O(N^2)

The problem statement was quite straight forward but I was asked to code the Space Optimised Approach. I had
previously solved this question using a stack but without using any extra space required a liitle bit of observation that
the input vector given can also be used as a stack .

Approach 1 (Using Stack ) :
1) If the current token is a operand (number), push it into the stack
2) If the token is a operator, pop the top two operands from the stack. Find the result of the operation using the
operator and two operands and push the result back into stack
3) Finally, the stack will contain the result of evaluated reverse polish expression.


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


Approach 2 (Without using stack ) :
If we are allowed to modify the input vector, we can optimize the space usage by using the input vector itself as a
stack rather than an explicit stack.

1) Here, we will maintain a pointer top which will point to the top index of tokens (our implicit stack).
2) Everytime we receive a integer token, we will push it at the index pointed by top.
3) Similarly, when we receive an operator, we can pop the top two operands and after computing the result on them,
push it back into tokens.

The only important thing here is properly maintaining the top pointer, so that we correctly access the elements the
operands.


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

Approach : 

1) Create a recursive function that takes a node and the two values n1 and n2.
2) If the value of the current node is less than both n1 and n2, then LCA lies in the right subtree. Call the recursive
function for the right subtree.
3) If the value of the current node is greater than both n1 and n2, then LCA lies in the left subtree. Call the recursive
function for the left subtree.
4) If both the above cases are false then return the current node as LCA.

TC : O(h), where h=Height of the BST
SC : O(h)

The Diamond Problem : The Diamond Problem occurs when a child class inherits from two parent classes who both
share a common grandparent class i.e., when two superclasses of a class have a common base class.

Solving the Diamond Problem in C++ : The solution to the diamond problem is to use the virtual keyword. We make
the two parent classes (who inherit from the same grandparent class) into virtual classes in order to avoid two copies
of the grandparent class in the child class.

Object-oriented programming revolves around entities like objects. Each object consumes memory and there can be multiple objects of a class. So if these objects and their memories are not handled properly, then it might lead to certain memory-related errors and the system might fail.

Garbage collection refers to this mechanism of handling the memory in the program. Through garbage collection, the unwanted memory is freed up by removing the objects that are no longer needed.

Approach : 

Phone Directory can be efficiently implemented using Trie Data Structure.

1) We insert all the contacts into Trie.

2) Generally search query on a Trie is to determine whether the string is present or not in the trie, but in this case we
are asked to find all the strings with each prefix of ‘str’. This is equivalent to doing a DFS traversal on a graph.

3) From a Trie node, visit adjacent Trie nodes and do this recursively until there are no more adjacent. This recursive
function will take 2 arguments one as Trie Node which points to the current Trie Node being visited and other as the
string which stores the string found so far with prefix as ‘str’.

4) Each Trie Node stores a boolean variable ‘isLast’ which is true if the node represents end of a contact(word).

5) User will enter the string character by character and we need to display suggestions with the prefix formed after
every entered character.

6) Find the prefix starting with the string formed is to check if the prefix exists in the Trie, if yes then call the
displayContacts() function. In this approach after every entered character we check if the string exists in the Trie.

7) Instead of checking again and again, we can maintain a pointer prevNode‘ that points to the TrieNode which
corresponds to the last entered character by the user, now we need to check the child node for the ‘prevNode’ when
user enters another character to check if it exists in the Trie.

8) If the new prefix is not in the Trie, then all the string which are formed by entering characters after ‘prefix’ can’t be
found in Trie too.

9) So we break the loop that is being used to generate prefixes one by one and print “No Result Found” for all
remaining characters.

Approach : 

1) Take an ordered map and a queue. The ordered map will help to store the nodes in the left to right order.

2) Push the root and the horizontal distance(which is 0 for the root) using the pair data structure, in the queue.

3) While the queue is not empty, perform the below steps :
a. Store the front element of the queue, which will be a node and the horizontal distance of that node in a variable ‘TEMP’.
b. Pop the front element.
c. Put the dequeued tree node in the map having the corresponding horizontal distance as the key. If the key is already present in the map, update its value with the current dequeued tree node.
d. If the dequeued node has a left child, push it to the queue along with the horizontal distance of the dequeued node - 1.
e. If the dequeued node has a right child, push it to the queue along with the horizontal distance of the dequeued node + 1.

4) Traverse the map and keep storing the values of each key in a vector.

5) Finally, return the vector which will be our required nodes in the bottom view of the binary tree.


TC : O(N*log(N)), where N = number of nodes in the binary tree.
SC : O(N)