Software Developer

Approach :
1) First make a recursive function, say ‘solve’ taking the number of opening brackets ‘opening’, number of closing
brackets ‘closing’ output string ‘output’, and an array of strings ‘ans’ as arguments.

2) Make the base condition as if ‘opening’ = 0 and ‘closing’ = 0 then push the output string in the ‘ans’ and return.

3) If ‘opening’ is not equal to zero then call the ‘solve’ function recursively by decrementing ‘opening’ by 1 and
inserting ‘(‘ into the ‘output’.

4) If ‘closing’ > ‘opening’ then call the ‘solve’ function recursively by decrementing ‘closing’ by 1 and inserting ‘)’ into
the ‘output’.


TC : O(2 ^ N), where N is the given integer.
SC : O(N)

Approach 1 (Brute Force) :

1) Iterate over every elevation or element and find the maximum elevation on to the left and right of it. Say, the
maximum elevation on to the left of the current elevation or element that we are looking at is ‘maxLeftHeight’ and the
maximum elevation on to the right of it is ‘maxRightHeight’.

2) Take the minimum of ‘maxLeftHeight’ and ‘maxRightHeight’ and subtract it from the current elevation or element.
This will be the units of water that can be stored at this elevation.

3) Compute units of water that every elevation can store and sum them up to return the total units of water that can
be stored.


TC : O(N^2), where ‘N’ is the total number of elevations in the map.
SC : O(1)


Approach 2 (Efficient Approach) :

1) Create two lists or arrays, say, ‘leftMax’ and ‘rightMax’.

2) At every index in the ‘leftMax’ array store the information of the ‘leftMaxHeight’ for every elevation in the map.

3) Similarly, at every index in the ‘rightMax’ array store the information of the ‘rightMaxHeight' for every elevation in
the map.

4) Iterate over the elevation map and find the units of water that can be stored at this location by getting the left max
height and right max height from the initial arrays that we created.


TC : O(N), where ‘N’ is the total number of elevations in the map.
SC : O(N)

Approach : I solved this problem using Multisource-BFS as I had solved questions similar to this while preparing for
my interviews.

Steps :

1) Initialize ‘TIME’ to 0.

2) Declare a Queue data structure and a 2D boolean array ‘VISITED’.

3) Push all cells with rotten orange to the queue.

4) Loop till queue is not empty
4.1) Get the size of the current level/queue.
4.2) Loop till the 'LEVEL_SIZE' is zero:
i) Get the front cell of the queue.
ii) Push all adjacent cells with fresh oranges to the queue.
iii) Mark the cells visited which are pushed into the queue.
4.3) Increment ‘TIME’ by 1.

5) Iterate the grid again. If a fresh orange is still present, return -1.

6) Return maximum of ‘TIME’ - 1 and 0.


TC : O(N * M), where N and M are the numbers of rows and columns of the grid respectively.
SC : O(N*M)

A queue can be implemented using two stacks. Let queue to be implemented be q and stacks used to implement q be stack1 and stack2. q can be implemented in two ways: 

Approach 1 (By making enQueue operation costly) : This method makes sure that oldest entered element is always at the top of stack 1, so that deQueue operation just pops from stack1. To put the element at top of stack1, stack2 is used. 

enQueue(q, x): 
1) While stack1 is not empty, push everything from stack1 to stack2.
2) Push x to stack1 (assuming size of stacks is unlimited).
3) Push everything back to stack1.


deQueue(q): 
1) If stack1 is empty then error
2) Pop an item from stack1 and return it


TC : 
Push operation: O(N). 
In the worst case we have empty whole of stack 1 into stack 2.

Pop operation: O(1). 
Same as pop operation in stack.

SC : O(N)



Approach 2 (By making deQueue operation costly) : n this method, in en-queue operation, the new element is entered at the top of stack1. In de-queue operation, if stack2 is empty then all the elements are moved to stack2 and finally top of stack2 is returned. 

enQueue(q, x) : 
1) Push x to stack1 (assuming size of stacks is unlimited).


deQueue(q) : 
1) If both stacks are empty then error.
2) If stack2 is empty
While stack1 is not empty, push everything from stack1 to stack2.
3) Pop the element from stack2 and return it.


TC : 
Push operation: O(1). 
Same as pop operation in stack.

Pop operation: O(N). 
In the worst case we have empty whole of stack 1 into stack 2

SC : O(N)

Approach :

1) We will first sort the intervals by non-decreasing order of their start time.

2) Then we will add the first interval to our resultant list.

3) Now, for each of the next intervals, we will check whether the current interval is overlapping with the last interval in
our resultant list.

4) If it is overlapping then we will update the finish time of the last interval in the list by the maximum of the finish time
of both overlapping intervals.

5) Otherwise, we will add the current interval to the list.


TC : O(N * log(N)), where N = number of intervals
SC : O(1)

Approach : 

1) Fill the 5 liter jug from the tap.
2) Empty the 5 liter jug into the 3 liter jug - leaving 2 liters in the 5 liter jug.
3) Pour away the contents of the 3 liter jug.
4) Fill the 3 liter jug with the 2 liters from the 5 liter jug - leaving 2 liters in the 3 liter jug.
5) Fill the 5 liter jug from the tap.
6) Fill the remaining 1 liter space in the 3 liter jug from the 5 liter jug.
7) Leaving 4 liters in the 5 liter jug.

Approach 1 :

Steps :

1) If the ‘root’ node is NULL, return 0. The diameter of an empty tree is 0.
2) Recur for the left subtree and store the diameter of the left subtree in a variable ‘leftDiameter’, i.e.
‘leftDiameter’ = getDiameter(left child of the root node)
3) Similarly, recur for the right subtree and store the diameter of the right subtree in a variable
‘rightDiameter’ i.e. ‘rightDiameter’ = getDiameter(right child of the root node)
4) Now, get the height of the left subtree and right subtree and store it in a variable.
4.1) ‘leftHeight’ = getHeight(left child of the root node)
4.2) ‘rightHeight’ = getHeight(right child of the root node)
5) The diameter of the given tree will be the maximum of the following terms:
i) ‘leftDiameter’
ii) ‘rightDiameter’
iii) 1 + ‘leftHeight’ + ‘rightHeight’
6) Return the maximum of above terms i.e.max(leftDiameter, rightDiameter, 1 + leftHeight + rightHeight).

TC : O(N^2), where ‘N’ is the number of nodes in the given binary tree.
SC : O(N)


Approach 2 :

Steps :

1) If the root node is NULL, assign “height” = 0 and return 0 because the height and diameter of an empty
tree will be 0.
2) Initialize two variables, “leftHeight” and “rightHeight” to 0, which denotes the height of the left subtree
and right subtree, respectively.
3) Recur for the left subtree and store the diameter of the left subtree in a variable i.e. leftDiameter =
getDiameter(root->left, leftHeight)
4) Similarly, recur for the right subtree and store the diameter of the right subtree in a variable i.e.
rightDiamater = getDiamter(root->right, rightHeight)
5) Update the height of the tree i.e. height = max(leftHeight, rightHeight) + 1
6) The diameter of the given tree will be the maximum of the following terms:
i) “leftDiameter”
ii) “rightDiameter”
iii) “leftHeight” + “rightHeight”
7) Return the maximum of above terms i.e. max(leftDiameter, rightDiameter, leftHeight + rightHeight).

TC : O(N), where 'N' is the number of nodes in the binary tree.
SC : O(N)

Approach : If a number N is power of 2 then bitwise & of N and N-1 will be zero. We can say N is a power of 2 or not
based on the value of N&(N-1). The expression N&(N-1) will not work when N is 0.
So,handle that case separately.

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

1) OOPs is very helpful in solving very complex level of problems.
2) Highly complex programs can be created, handled, and maintained easily using object-oriented programming.
3) OOPs, promote code reuse, thereby reducing redundancy.
4) OOPs also helps to hide the unnecessary details with the help of Data Abstraction.
5) OOPs, are based on a bottom-up approach, unlike the Structural programming paradigm, which uses a top-down
approach.
6) Polymorphism offers a lot of flexibility in OOPs.

Access specifiers, as the name suggests, are a special type of keywords, which are used to control or specify the
accessibility of entities like classes, methods, etc. Some of the access specifiers or access modifiers include “private”,
“public”, etc. These access specifiers also play a very vital role in achieving Encapsulation - one of the major features
of OOPs.

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.