SDE - 1

This can be done by iterative swapping using two pointers. The first pointer points to the beginning of the string, whereas the second pointer points to the end. Both pointers keep swapping their elements and go towards each other. Essentially, the algorithm simulates the rotation of a string with respect to its midpoint.
Time Complexity : O(n)

The brute force solution is to consider all subarrays and find a subarray with maximum value of (count of 1s) – (count of 0s). Let this value be max_diff. Finally, return count of zeros in original array plus max_diff.

The problem can also be solved efficiently in O(n) time complexity. This problem can be reduced to largest subarray sum problem. The idea is to consider every 0 as -1 and every 1 as 1, find the sum of largest subarray sum in this modified array. This sum is our required max_diff ( count of 0s – count of 1s in any subarray). Finally we return the max_diff plus count of zeros in original array.

Pseudocode :
findMaxZeroCount(bool array, n)
{
// Initialize count of zeros and maximum difference between count of 1s and 0s in a subarray
orig_zero_count = 0;

// Initiale overall max diff for any subarray
max_diff = 0;

// Initialize current diff
curr_max = 0;

for (int i=0; i {
// Count of zeros in original array 
if (arr[i] == 0)
orig_zero_count++;

// Value to be considered for finding maximum sum
val = (arr[i] == 1)? 1 : -1;

// Update current max and max_diff
curr_max = max(val, curr_max + val);
max_diff = max(max_diff, curr_max);
}
max_diff = max(0, max_diff);

return orig_zero_count + max_diff;
}

This problem is similar to Next Greater Element. A stack can be used to find the next greater element and after finding next greater, if we find a smaller element, then return false.
Steps : 
1) Create an empty stack.
2) Initialize root as INT_MIN.
3) Do following for every element pre[i]
a) If pre[i] is smaller than current root, return false.
b) Keep removing elements from stack while pre[i] is greater then stack top. Make the last removed item as new root (to be compared next). At this point, pre[i] is greater than the removed root. (That is why if we see a smaller element in step a), we return false)
c) push pre[i] to stack (All elements in stack are in decreasing order) 
Time Complexity : O(N)

The Naive approach is to remove every second element from the array until the size of the array becomes equals to ‘1’. 
The time complexity of this approach is O(n2).

The Efficient approach is to use recursion. Let’s consider n to be even. In one traversal, numbers 2, 4, 6 … N will be removed and we start again from 1. Thus, exactly n/2 numbers are removed, and we start as if from 1 in an array of N/2 containing only odd digits 1, 3, 5, … n/2. 
Thus the recursive formula can be written as : 

If n is even:
solve(n) = 2 * solve(n/2) - 1
else
solve(n) = 2 * solve((n-1) / 2) + 1

Base condition would occur when n = 1, then answer would be 1.

Union :
1) Initialize an empty hash set or hash map mp;
2) Iterate through the first array and put every element of the first array in the set mp.
3) Repeat the process for the second array.
4) Print the set mp.

Time complexity : O(m+n) under the assumption that hash table search and insert operations take O(1) time.
Space complexity : O(m+n) in case of Union and O(min(m,n)) in case of Intersection

The brute force approach is to use nested loops. Outer loop is used to pick the elements one by one and the inner loop compares the picked element with the rest of the elements. 
An efficient approach would be to use hashing. Traverse the link list from head to end. For every newly encountered element, check whether it is in the hash table: if yes, we remove it; otherwise put it in the hash table.
Time Complexity : O(N)

1. Swapping is procedure of copying out the entire process.Paging is a technique of memory allocation.
2. Swapping occurs when whole process is transferred to disk. Paging occurs when some part of process is transfers to disk.
3. In swapping, process is swapped temporarily from main memory to secondary memory. In paging, the contiguous block of memory is made non-contiguous but of fixed size called frame or pages.
4. Swapping can be performed without any memory management. There is Non-contiguous Memory Management in paging. 
5. Swapping is done by inactive processes. Only active process can perform paging.

A real-world example would be traffic, which is going only in one direction.
Here, a bridge is considered a resource. So, when Deadlock happens, it can be easily resolved if one car backs up (Preempt resources and rollback). Several cars may have to be backed up if a deadlock situation occurs.
So starvation is possible.

Algorithm : 
1) Initialize two index variables left and right: 
left = 0, right = size -1 
2) Keep incrementing left index until we see an even number.
3) Keep decrementing right index until we see an odd number.
4) If left < right then swap arr[left] and arr[right]

Recursion can be applied here. 
Steps: 
• Get the middle of the array and make it as root.
• Take the left half of the array, call recursively and add it to root.left.
• Take the right half of the array, call recursively and add it to root.right.
• Return root.

Select from the given coins two groups of three coins each and put them on the opposite cups of the scale. If they weigh the same, the fake is among the remaining two coins, and weighing these two coins will identify the lighter fake. If the first weighing does not yield a balance, the lighter fake is among the three lighter coins. Take any two of them and put them on the opposite cups of the scale. If they weigh the same, it is the third coin in the lighter group that is fake; if they do not weigh the same, the lighter one is the fake.

1. MVC has controller that drives both Model and View. MVT has Views for receiving HTTP request and returning HTTP response.
2. View tells how the user data will be presented in MVC. Templates are used in MVT for that purpose.
3. In MVC, we have to write all the control specific code. Controller part is managed by the framework itself in MVT.
4. MVC is Highly coupled. MVT is Loosely coupled. 
5. Modifications are difficult in MVC. Modifications are easy in MVT. 
6. MVC is suitable for development of large applications but not for small applications. MVT is suitable for both small and large applications.

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.