3 days ago

admin 1.6k

Hyderabad

Question - 1

Given two Binary Search Trees, find common nodes in them. In other words, find intersection of two BSTs.

Question - 2

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

 Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
 Output: 6
 Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water 
 (blue section) are being trapped.

Question - 3

An array contains both positive and negative numbers in random order. Rearrange the array elements so that positive and negative numbers are placed alternatively. A number of positive and negative numbers need not be equal. If there are more positive numbers they appear at the end of the array. If there are more negative numbers, they too appear at the end of the array.

input array is [-1, 2, -3, 4, 5, 6, -7, 8, 9]
output should be [9, -7, 8, -3, 5, -1, 2, 4, 6]

3 days ago

admin 1.6k

Hyderabad

Problem 1

• Fact - Inorder Traversal of Binary Search Tree results in an array that is sorted in ascending order.
• So if we apply Inorder Traversal to both Binary Search Tree, it will result in two arrays which are sorted in ascending order. Now the problem reduces to "Finding intersection of two sorted arrays".
• Above reduced problem, now can be solved in O(N) time and space using simple two pointer approach.

Note - A minor optimization in space complexity can be achieved, by using implementing inorder traversal of Binary Search Tree iteratively and using stack to store each branch of a Tree. However, since worst case complexity still remains same, this isn't really required.

Problem 2

• ith bar can trap the water if and only if there exists a higher bar to the left and a higher bar to the right of ith bar.
• To calculate how much amount of water the ith bar can trap, we need to look at the maximum height of the left bar and the maximum height of the right bar, then
  • The water level can be formed at ith bar is: waterLevel = min(maxLeft[i], maxRight[i])
  • If waterLevel >= height[i] then ith bar can trap waterLevel - height[i] amount of water.
• To achieve in O(1) when looking at the maximum height of the bar on the left side and on the right side of ith bar, we pre-compute it:
  • Let maxLeft[i] is the maximum height of the bar on the left side of ith bar.
  • Let maxRight[i] is the maximum height of the bar on the right side of ith bar.

Implementation of above idea in C++.

• Time Complexity : O(N)
• Space Complexity : O(N)
• Note: We can optimize space and rewrite same idea with constant space complexity.

Problem 3

A straightforward solution is to simply store all positives in one array, all negatives in another array and eventually combine them one by one into final array. However, this results in O(N) time which is optimal, but O(N) space which is good, but not optimal.

So how can we achieve optimal space and time complexity solutions?

Turns out there are multiple equally interesting solutions!

Solution 1 - Using Dutch Flag Algorithm

1. Using Dutch Flag Algorithm, we move all negative numbers to left and all positives to right. This step is done in O(N) time and O(1) space.
2. find the the index of first positive number. Let it be posIndex.
3. Initialize negIndex with index of second negative number that is 1.
4. Swap alternate negative numbers with positive numbers. Swap inputArray[negArray] and inputArray[posArray].
5. Increment posIndex (posIndex++) and set negIndex to alternate negative number(negIndex += 2;).

Solution 2 - Using Pivot idea from Quicksort The idea is to use 0 as a pivot element and make one pass of the partition process. The resultant array will contain all positive integers at the end of the array and all negative integers at the beginning. Then swap alternate negative elements from the next available positive element until the end of the array is reached, or all negative or positive integers are exhausted just like solution above.

Sample Illustration