Software Developer

This question can be solved using hashing. Store the frequencies of the elements present in the array A1[ ] in a hash table and then traverse the array A2[ ] from its beginning and check the frequency of that element in the hash table we built.
Algorithm:
• Store all the elements of first array in map.
• Traverse over the second array and store all those elements which are present in map.
• Iterate over the map and store the rest elements present in map.

The brute force solution is to traverse the entire array and find the minimum. Time Complexity : O(N)
The efficient approach is to use Binary Search. The following pattern can be observed : 
1. The minimum element is the only element whose previous is greater than it. If there is no previous element, then there is no rotation (the first element is minimum). We check this condition for the middle element by comparing it with (mid-1)’th and (mid+1)’th elements.
2. If the minimum element is not at the middle (neither mid nor mid + 1), then the minimum element lies in either the left half or right half. 
1. If the middle element is smaller than the last element, then the minimum element lies in the left half
2. Else minimum element lies in the right half.

Pseudocode:

low = 0
high = n-1
findMin(arr[],low, high)
{
while(low < high)
{
mid = low + (high - low)/2
if (arr[mid] == arr[high])
high--
else if(arr[mid] > arr[high])
low = mid + 1
else
high = mid
}
return arr[high]
}

The direct approach to solve this problem is to run two for loops and for every subarray check if it is the maximum sum possible. 
Time complexity: O(N^2), Where N is the size of the array.
Space complexity: O(1)
The efficient approach is to use Kadane's algorithm. It calculates the maximum sum subarray ending at a particular index by using the maximum sum subarray ending at the previous position. 
Steps : 
Declare two variables : currSum which stores maximum sum ending here and maxSum which stores maximum sum so far.
Initialize currSum = 0 and maxSum = INT_MIN.
Now, traverse the array and add the value of the current element to currSum and check : 
1. If currSum > maxSum, update maxSum equals to currSum.
2. If currSum < 0, make currSum equal to zero.
Finally, print the value of maxSum.

A greedy approach can be built for this question. 
Call a plot ready if the very first flower is allowed to be planted there.
Consider the left-most ready plot x (if it exists). If x+1 is not ready, then we increase our answer strictly by planting at x, since x does not disturb any ready plots. If x+1 is ready, then planting at x instead of x+1 is at least as good, since x disturbs only {x, x+1}, whereas x+1 disturbs {x, x+1, x+2}.

Now our implementation is trivial. For each plot from left to right, if we can plant a flower there, then do so. We can plant a flower if the left neighbor is 0 (or we are on the left edge), AND the right neighbor is 0 (or we are on the right edge).

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.