Software Engineer

The question boils down to finding the number of connected components in an undirected graph. Now comparing the connected components of an undirected graph with this problem, the node of the graph will be the “1’s” (land) in the matrix. 
BFS or DFS can be used to solve this problem. In each BFS call, a component or a sub-graph is visited. We will call BFS on the next un-visited component. The number of calls to BFS function gives the number of connected components. A cell in 2D matrix has 8 neighbors. So for each cell, we process all its 8 neighbors. We keep track of the visited 1s so that they are not visited again using a visited matrix.

Time Complexity : O(m*n) where m*n is the size of the given matrix
Space Complexity : O(min(m,n))

For every additional digit of the string, multiply the value of the digit by 26^n where n is the number of digits it is away from the one's place. 
This is similar to how the number 254 could be broken down as this: (2 x 10 x 10) + (5 x 10) + (4). For this question, 26 will be used as a base instead of 10. 
For s = "BCM" the final solution would be (2 x 26 x 26) + (3 x 26) + (13)
This process can be carried out iteratively. Start at looking at the first character of the string. Add the integer equivalent of that character to the running sum and continue. For every new character, multiply the running sum by 26 before adding the new digit to signify we are changing places.

XOR approach can be used to solve this question in an efficient manner. The following property of XOR can be used :
If x1^x2^…xn = a and x1^x2^..xn-1 = b , then a^b = xn

Steps:
1. Declare two variables a= 0 and b = 0

2. Calculate the xor of numbers from 1 to n and store them in a i.e. 1^2^…n = a. 

3. Now traverse the array from start to end.

4. For every index i update b as b = b ^ arr[i]

5. Return the missing number as a ^ b. 

Time Complexity : O(N)
Space complexity : O(1)

One approach would be to traverse the tree and for every traversed node X :
1) Find maximum sum from leaf to root in left subtree of X 
2) Find maximum sum from leaf to root in right subtree of X. 
3) Add the above two calculated values and X->data and compare the sum with the maximum value obtained so far and update the maximum value. 
4) Return the maximum value.

The time complexity of above solution is O(n2)

This question can also be solved in a single traversal of binary tree. The idea is to maintain two values in recursive calls : 
1) Maximum root to leaf path sum for the subtree rooted under current node. 
2) The maximum path sum between leaves (desired output).

For every visited node X, we find the maximum root to leaf sum in left and right subtrees of X. We add the two values with X->data, and compare the sum with maximum path sum found so far.

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.