Software Developer

The idea is to traverse the given list of prices and find a local minimum of every increasing sequence. We can gain maximum profit if we buy the shares at the starting of every increasing sequence (local minimum) and sell them at the end of the increasing sequence (local maximum). 

Steps :
1. Find the local minima and store it as starting index. If not exists, return.

2. Find the local maxima. and store it as an ending index. If we reach the end, set the end as the ending index.

3. Update the solution and Increment count of buy-sell pairs. 

4. Repeat the above steps till the end is not reached.

A stack can be used to solve this question. 
We traverse the given string s and if we :
1. See open bracket we put it to stack.
2. See closed bracket, then it must be equal to bracket in the top of our stack, so we check it and if it is true, we remove this pair of brackets.
3. In the end, if and only if we have empty stack, we have valid string.

Complexity: Time complexity is O(n) : we put and pop each element of string from our stack only once. Space complexity is O(n).

Approach 1 : Naive Recursive Approach

A naive approach is to start from the first element and recursively call for all the elements reachable from first element. The minimum number of jumps to reach end from first can be calculated using minimum number of jumps needed to reach end from the elements reachable from first.

minJumps(start, end) = Min ( minJumps(k, end) ) for all k reachable from start

TC : O(n^n)
SC:O(n)

Approach 2 : Dynamic Programming - Tabulation

We can solve this iteratively as well. For this, we start from the last index. We need 0 jumps from nums[n-1] to reach the end. We store this as dp[n - 1] = 0 and then iteratively solve this for each previous index till the 0th index. Here dp[i] denotes minimum jumps required from current index to reach till the end.

1) For each index, we explore all the possible jump sizes available with us.
2) The minimum jumps required to reach the end from the current index would be - min(dp[jumpLen]), where 1 <= jumpLen <= nums[currentPostion]

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

Approach 3 : Most optimal - Greedy-BFS

We can iterate over all indices maintaining the furthest reachable position from current index - maxReachable and currently furthest reached position - lastJumpedPos. Everytime we will try to update lastJumpedPos to furthest possible reachable index - maxReachable.

Updating the lastJumpedPos separately from maxReachable allows us to maintain track of minimum jumps required. Each time lastJumpedPos is updated, jumps will also be updated and store the minimum jumps required to reach lastJumpedPos (On the contrary, updating jumps with maxReachable won't give the optimal (minimum possible) value of jumps required).

We will just return it as soon as lastJumpedPos reaches(or exceeds) last index.

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

The basic idea of this approach is to store the elements of the matrix in an array/list and then sort the elements. Steps are as follows:

1. Create an auxiliary array/list of N*M length.

2. Traverse the matrix and insert all the elements in that array/list.

3. Sort that list/array in non-decreasing order.

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.