Member of Technical Staff

Approach : 

Let ‘allAllPaths(n, m, edges, src, des)’ be the function that returns a 2D array that contains all the possible paths.

1) Take the following variables: 2D array ‘Graph’, to store graphs and ‘Visited’ array to mark each node whether it is visited or not.

2) Clear graph, initialize the visited array to false.

3) Run a loop from 0 to 'm' :
Add the undirected edge between edges[i] [0] and edges[i][1].

4) Take an 2D array 'allPaths' to store the answer.

5) Take an array 'currPath' to store the current path.

6) Push ‘src’ in ‘currPath’ and mark visited[src] equal to true.

7) Make a dfs(n, allPaths, currPath, src, des, graph, visited) and call the dfs function.

8) Return ‘allPaths’. 


TC : O(N ^ N), where N = number of vertices
SC : O(N ^ N)

Approach : 

1) Run loop until all the squares of loops are printed.

2) In each outer loop traversal push the elements of a square in a clockwise manner.

3) Push the top row, i.e. Push the elements of a kth row and increase k..

4) Push the right column, i.e. Push the last column and decrease the count of columns.

5) Push the bottom row, and decrease the count of rows.

6) Push the left column, and increase the count of the starting column index.


TC : O(N*M), where N = number of rows and M = number of columns
SC : O(1)

Approach : 

1) We initialize two 2-D matrices, buy[K+1][N+1] and sell[K+1][N+1]. 

2) Here, buy[i][j] will denote the maximum profit we can get in at most ‘i’ transactions from the array starting from index 0 and ending at index j -1 and the final state is buying the stock. 

3) sell[i][j] will denote the maximum profit we can get in at most ‘i’ transactions from the array starting from index 0 and ending at index j -1 and the final state is not holding the stock i.e. selling the stock.

4) We iterate the matrix buy and sell column-wise and update the values.

4.1) buy[j][i] = max(buy[j][i-1], sell[j-1][i-1] - PRICES[i-1]). Here buy[j][j-1] denotes holding the stock and sell[j -1][i - 1] - PRICES[i -1] denotes buying the stock on i-th day.

4.2) sell[j][i] = max(sell[j][i-1], buy[j][i-1]+PRICES[i-1]). Here sell[j][i-1] denotes not holding the stock and buy[i][j - 1] + PRICES[i -1] denotes selling the stock on i-th day.

5) Finally return sell[K][N].


TC : O(N*K), where N = size of the array and K = max number of transactions allowed
SC : O(N*K)

Approach : 

1) Assign the diagonal number of the root as 0.

2) Do a preorder traversal of the binary tree and for each node keep track of the diagonal number.
2.1) Insert the value of the current node in the Map with the key as the diagonal number of the current node.
2.2) Now increase the diagonal number by 1 for the left child of the node and recursively traverse the left subtree.
2.3) Recursively traverse the right subtree and keep the diagonal number the same as the current node.

3) Initialize an empty array to store the diagonal traversal, let’s say 'traversal'

4) Iterate through the Map and add all the values of the Map to 'traversal'.

5) Finally, Return 'traversal'.


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

Approach :

1) The idea is to create a 2D table of size N*N.

2) Each entry in the table stores the solution to a subproblem i.e. ‘TABLE’['I']['J'] represents the maximum amount you
can win for the subarray ‘COINS’['I', 'J'] given that you start first.

3) The algorithm for filling the table is as follows :
Loop 1: For ‘LEN’ = 1 to ‘N’:
Loop 2: For ‘I’ = 0 to ('N' - ‘LEN’):
→Let 'J' = 'I' + ‘LEN’ - 1
→If ('I'+1) < N && ('J'-1) >= 0 then, A = ‘DP’['I'+1]['J'-1], otherwise A = 0.
→If (i+2) < N then, B = ‘DP’['I'+2]['J'], otherwise B = 0.
→ If ('J'-2) >= 0 then, C = ‘DP’['I']['J'-2], otherwise C = 0.
→ Update ‘DP’['I']['J'] = max(‘COINS’['I'] + min(A, B), coins['J'] + min(A, C)).
End Loop 2.
End Loop 1.

4) ‘DP’[0]['N'-1] stores the final answer.


TC : O(N^2) , where N = number of coins
SC : O(N^2)

Approach (Using DP) :

1) We reach “currStep” step in taking one step or two steps:
1.1) We can take the one-step from (currStep-1)th step or,
1.2) We can take the two steps from (currStep-2)th step.

2) So the total number of ways to reach “currStep” will be the sum of the total number of ways to reach at (currStep-
1)th and the total number of ways to reach (currStep-2)th step.

3) Let dp[currStep] define the total number of ways to reach “currStep” from the 0th. So,
dp[ currStep ] = dp[ currStep-1 ] + dp[ currStep-2 ]

4) The base case will be, If we have 0 stairs to climb then the number of distinct ways to climb will be one
(we are already at Nth stair that’s the way) and if we have only one stair to climb then the number of
distinct ways to climb will be one, i.e. one step from the beginning.


TC : O(N), Where ‘N’ is the number of stairs.
SC : O(N)

There are two main types of semaphores i.e. counting semaphores and binary semaphores.

1) Counting Semaphores :
These are integer value semaphores and have an unrestricted value domain. These semaphores are used to
coordinate the resource access, where the semaphore count is the number of available resources. If the resources
are added, semaphore count automatically incremented and if the resources are removed, the count is decremented.


2) Binary Semaphores :
The binary semaphores are like counting semaphores but their value is restricted to 0 and 1. The wait operation only
works when the semaphore is 1 and the signal operation succeeds when semaphore is 0. It is sometimes easier to
implement binary semaphores than counting semaphores.

Deadlock is generally a situation where a set of processes are blocked as each process is holding resources and
waits to acquire resources held by another process. In this situation, two or more processes simply try to execute
simultaneously and wait for each to finish their execution because they are dependent on each other. We can see a
hand problem in our system whenever a deadlock occurs in a program. It is one of the common problems you can
see in multiprocessing.

Necessary Conditions for Deadlock

There are basically four necessary conditions for deadlock as given below:

1) Mutual Exclusion
2) Hold and Wait
3) No Pre-emption
4) Circular Wait or Resource Wait

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.

Abillity 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