SDE - Intern

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)

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.

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)

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.

spiralPrint(matrix[][], R, C, rows, cols):

1) Check for base cases, i.e. if outside the boundary of the matrix then return.
2) Print the first row from left to right of the matrix i.e from column ‘C’ to ‘cols’, print the elements of the Rth row.
3) Print the last column from top to bottom of the matrix i.e from row ‘R’ to ‘rows’, print the elements of the (cols)th column.
4) Print the last row from right to left of the matrix i.e from column ‘cols’ to ‘C’, print the elements of the (rows)th row.
5) Print the first column from bottom to top of the matrix i.e from row ‘rows’ to ‘R’, print the elements of the Cth column.
6) Call the function recursively with the updated values of boundaries, spiralPrint(matrix, R + 1, C + 1, rows - 1, cols - 1).

TC : O(N*M) , where N = number of rows and M = number of columns of the matrix.
SC : O(max(N,M))