SDE - Intern

Start traversing through the given ‘A’ 2D matrix row-wise and fill in the values.
For the first row and the first column, set the value to 1 if an obstacle is not found.
If an obstacle is found for the first row and first column, then start filling 0 till the last index in that particular row or column.
Now start traversing from the second row and column (e.g., A[ 1 ][ 1 ]).
If an obstacle is found, set 0 at a particular Grid (e.g., A[ i ][ j ] ); otherwise, set sum of upper and left values at A[ i ][ j ].
Return the last value of the 2D matrix.

This is the same as the above method, but the elements are pushed and popped only once into the stack. The array is changed in place. The array elements are pushed into the stack until it finds the most significant element on the right of the array. In other words, the elements are popped from the stack when the top of the stack value is smaller in the current array element.
The stack is not empty once all the elements are processed in the array. The left-out elements in the stack don’t encounter any most significant element. So, pop the element from the stack and change its index value to -1 in the array.

1) Create an array longest of length n (size of the input
string) initialized to zero.
The array will store the length of the longest valid 
substring ending at that index.
2) Initialize the result as 0.
3) Iterate through the string from the second character
a) If the character is '(' set longest[i]=0 as no 
valid sub-string will end with '('.
b) Else
i) if s[i-1] = '('
set longest[i] = longest[i-2] + 2
ii) else
set longest[i] = longest[i-1] + 2 + 
longest[i-longest[i-1]-2]
4) In each iteration, update the result as the maximum of 
result and longest[i]
5) Return result.

Create a stack and push all the IDs in the stack.
Run a loop while there are more than one element in the stack.
Pop the top two elements from the stack (represent them as A and B).
If A knows B, A can’t be a celebrity and push B into the stack. Otherwise, B can’t be a celebrity push A in the stack if A doesn't know B.
Could you assign the remaining element in the stack as the celebrity?
Run a loop from 0 to n-1 and find the count of persons who know the celebrity and the number of people whom the celebrity knows.
If the count of persons who know the celebrity is n-1 and the count of people whom the celebrity knows is 0, then return the ID of the celebrity else, return -1.