Distorting a Binary Tree

We know that there are 3 different ways to traverse a Binary Tree i.e. InOrder, PreOrder, and PostOrder. Let us try to ignore other traversals like LevelOrder etc for now. Each traversal has its own significance and you can never think of one traversal technique as a replacement for the other. I am going to talk here about which traversal suits better when the tree is getting distorted. I will be taking 2 examples here and proceed.

The links to left and right subtrees are as important to a tree as the next pointer for a linked list. These are all the pointers/references that keep the structure intact. Once they are lost, there is no way to recover them once again. So when it comes to distorting a tree, I would always prefer PostOrder traversal where you don't touch the current node till you are done with the sub-trees.

Deleting a Binary tree
Consider for example the problem of how to deallocating an entire Binary tree? You cant start with the root node of the tree, as if you do so, you have no way to go to the left and right subtrees. So if you deallocate the root first, you cant proceed anymore. Similarly in case of InOrder traversal, you cant deallocate the right subtree. So the most suitable procedure involves deallocating the left and right subtrees first and coming to the root at last.

Binary tree to Doubly Linked List
Now consider the problem of converting a Binary Tree into a doubly linked list where the left pointer of the tree should be made to point the InOrder predecessor node and right pointer should be altered to point the InOrder successor node.
Though the problem talks about InOrder arrangement, you should not start tackling the problem with InOrder traversal. Because as we discussed in case of delete operation, any operation that distorts the tree is best done by the PostOrder traversal.
So, you need to write a recursive procedure to convert a tree to a Doubly Linked List. You can recursively apply the procedure to the left sub-tree and get a leftDll and separately to the right sub-tree to get a rightDll.
Now, you need to form a single DLL from the leftDll, the current root node, and the rightDll. So you need to attach the last node of the leftDll to the root, and then attach the root to the rightDll's head. However, finding the last node of leftDll is O(n) operation. In order to minimize that, instead of returning a Dll, always return a circular DLL so that once you have access to its head, it is just a O(1) operation to get its tail.
Now, we have discussed that circular DLL is the best data-structure to be returned. But what exact node would you return? Remember that you expect the left subtree to return a circular DLL which is arranged InOrder. Now to preserve the InOrder property, you would want to attach the current root to the end of the Circular DLL. Similarly you would link the circular DLL that you have obtained from the right subtree and form a single circular DLL. Now you should return the head node in other words, the node returned by the left subtree's iteration if present or else the current node to maintain the invariant.

Algorithms based on majority element

What is majority element in an array?
In an array of size n, if a specific element repeats itself more than half the times (> n/2 times), then it is called the majority element. If no such element exists, then the array is said to have no majority element in it.
Examples:
[3,2,2,3,3] -> 3 is the majority element
[4,4,5,7,3,3,3,4,4] -> 4 is the majority element
[1,2,3,4,5] -> no majority element at all.
[1,1,1,2,2,2] -> no majority element as the majority element has to repeat more than half the times (i.e. 4 times at least in this array)

How to check whether a number is majority element or not?
It is very simple and obvious. Given a number X and an array A, run through the array and make the count of X's in the array. If the count is more than A.size()/2, then X is the majority element.

Logic to find majority element?
Suppose X is the majority element of an array. If you find an element Y in the same array which is not equal to X, you can cancel one occurrence of Y and one occurrence of X from the array and still the resultant array will have X as the majority element. This cancellation will reduce the size of both the parts of the array, i.e. the part (may not be contiguous) having majority element, and the one having rest of the elements.
Example: [3,1,2,3,3] -> In this array, 3 is the majority element. If you are able to find one non-majority element (say 1), you can cancel one occurrence of both 1 and 3 and still 3 will be the majority element. i.e. [2,3,3] obtained after cancelling one 3 and one 1 also has 3 as the majority element.

Similarly, take 2 elements which are not majority elements, say Y and Z. If you cancel both of them, the majority element will still be the same. i.e. in the above example, if you cancel two non majority elements 1 and 2, the resultant array will have [3,3,3] in which 3 is majority element once again.

In other words, you can pick any 2 elements from the array, and you can discard them if both of them are not the majority elements.


Solution:
Given an array A[0..n-1], your assignment is to find the majority element in it.
Let counter be the variable which records the number of occurrences of the majority element. Initially it will be 0.
Whenever the counter is less than or equal to zero, take the next element in A as majority element. Increment the counter when you see the same element and decrement it when you see a different element. Do it again if the counter becomes zero once again.

counter = 0
majority_index = -1
// Find majority element
for i in 0..Arr.size()-1
  if counter == 0
    majority_index = i
  end
  counter += Arr[i] == Arr[majority_index]
end


// Check the correctness
majority_count = 0
for j in 0..Arr.size()-1
  if Arr[j] == Arr[majority_index]
    majority_count ++
  end
end
if (majority_count > Arr.size()/2)
  return Arr[majority_index]
else
  throw "No majority element found"
end

E.g. 1,2,4,2,5,6,3,4,4,2,4,4,4,4,4
counter = 0
Start with 1 as majority element.
Next element is 2 which is not 1. So discard both.
Now 4 becomes the majority element and counter will be 1
when 2 comes again, counter will become 0, and so till now no majority element exists.
Next 5 and 6 gets discarded similarly as both are different.
Similarly, 3 and 4 will get discarded, and again 2 and 4 will get discarded.
Now the only array having majority element is [4,4,4,4,4] and the counter keeps incrementing to 5.
Now check whether 4 is the real majority element in the array. If so, you can return 4.

Problem 2 "Find element which occurs at least half the times"
Good that you now know how to find the majority element. Now, given that you need to find the element which occurs at least half the times in the array, how will you proceed? Remember, this is a different problem. As per the majority element, it should occur more than half the times, but now the problem has been modified to find that element which repeats at least half the times.
Solution:
We can use the majority algorithm that we discussed above in all the cases except when the element that needs to be found occurs exactly half the times in the array. We can change the solution a bit to catch that case also. In the array, check whether the first element is the majority element; if so, return it. Else, discard the first element in the array. Now after discarding, we can apply the above described normal majority element algorithm itself as now the majority element is guaranteed to be more than half the number of times in the array.

Minima in a sliding window

This is the second time I am hearing about this interview question, and so I should not ignore this anymore. I personally had this question in one of my interviews where I couldn't find the most optimal solution. My friend got this question in Google interview very recently and he too failed to give the best answer. So, I took my time to surf the Internet to find out the best answer.

Question:
You are given an array of size n (may be a stream also). You have a sliding window of size k. The window first boxes the first k elements of the array and slides slowly over the array by shifting its position 1 element each time. At each position of the array, you need to find the minimum element in the sliding window. i.e. you need to give the minimum of 0 to k-1 elements, then 1 to k elements, 2 to k+1 elements etc. So if your array's size is n, you have to give me n-k+1 minimum values.
E.g. Assume that the array is 5,1,3,2,6,8,4,6, and the window size is 3
You should give me 1,1,2,2,4,4. How will you give it?

Solution #1:
As you  need to find out the minimum, my solution was to use a min-heap of size k and gave a solution with time complexity O(nlog(k)). My friend too thought in the same lines. First form a min heap with the first k elements (initial position of the window). Now as and when the window slides, you need to form a new min-heap by adding the next element and discard the first element. Addition of a new element is simple and will take O(log(k)) time. But for deleting an element, you need O(k) time which pushes the time higher. So instead of seeing the problem as a two step process, see it as changing the value of an element in the heap, i.e. you need to change the value of the element you want to discard to the new element that you want the heap to have. If the element that gets into the window knows which element to remove from heap (by maintaining a pointer), the problem can easily be solved in O(nlog(k)) time by simply calling min-heapify n times.

Solution #2:
However, there is a better solution for this problem in O(n) time. At any time, you will add exactly 1 new element from the stream to the window, and discard 1 element.

Step 1: Finding ascending minima:

Assume that the current window is 5,1,3,2. You need to form a list with the following algorithm -
1. Find the minimum element in the whole list (1 in our example). Let the index of that element in the window be i (this too is 1 if the index is zero based). Insert that element in the list.
2. Now forget about the first i elements (where W[i] = min element in the whole window).
3. From  i+1 to k elements, find the minimum value and add it to the list.
4. Repeat it till you add the last element of the window as an entry in the list.
In our example, among all the elements 1 is the least element. So, the result list should be 1.
Now discard the first two elements (ignore the prefix of the array such that the end element is the minimum element you have found. i.e. ignore 5 and 1). Now in the resultant array, find the minimum. i.e. 2. Add this element to the list. So the list will be 1,2.
Do the same step recursively (here only 2 elements are there, but if 2 is not the last element, you should have continued doing the same till you insert the last element in the list).
The new list that you have formed is called ascending minima.
Example:

Assume that the window is [6,2,1,5,3,4,8].

1. Start with an empty ascending minima array, call it ama = {}

2. In the window, find the minimum element in the window (1 at the 3rd position). Add that minimum element to the ama list, and ignore all elements till 1 in the window,

So ama = {1} and sub-window to be processed = {5,3,4,8}.

3. Find the smallest element in the sub-window to be processed (3 at the 2nd position in the sub-window). Add 3 to the ama list and discard all elements till 3 in the sub-window.

So, ama = {1,3} and sub-window to be processed = {4,8}.

4. Find the smallest element again in the sub-window (4 at the 1st position), and add it to the ama list. Ignore elements till 4.

So, ama = {1,3,4} and sub-window to be processed = {8}.

5. Find the smallest element in the window again. i.e. (8 at the 1st position). Add it to the ama list. Now discard all elements till 8 which results the sub-window as an empty array.

ama={1,3,4,8} and sub-window to be processed = {}

6. End the process as sub-window to be processed is empty.

Other examples:

[8,9,5,3,6,5,1,1,0] - ascending minima = [0]

[7,4,8,6,3,4,2,1,2] - ascending minima = [1,2]

[1,2,3,4,5,6,7,8,9] - ascending minima = [1,2,3,4,5,6,7,8,9]

[9,8,7,6,5,4,3,2,1] - ascending minima = [1]

[9,1,1,3,4,2,6,8,9] - ascending minima = [1,2,6,8,9] (In case duplicates are there, take the last one).

Algorithm:

def ascending_minima(arr, minima = [])
  return minima if arr.empty?
  return minima << arr[0] if arr.size == 1
  
  min_index = 0
  1..(arr.size-1).each { |i| min_index = i if arr[i] < arr[min_index]}
  minima << arr[min_index]
  minima = ascending_minima(arr[min_index+1..arr.size-1], minima)
  return minima
end

Note: The minimum element of the window is always present as the first element of the ascending minima list.

Step 2: Adjusting ascending minima for window shift

What happens when a window shifts by an element? The first element in the previous window gets discarded and a new element gets added at the end of the window. As, from ascending minima, you can easily find the smallest element of a window (by peeking into the first element of the ascending minima). Let us try how to get the ascending minima without reconstructing it from scratch by using the previous ascending minima itself.

1. If the element that you discard is the first element in the ascending minima, you need to get rid of that element from the ascending minima.
2. As in all the cases, we took the suffix array to find the minimum element. Now there should have been cases that the newly added element is the minimum element. Search from the end of the ascending minima start discarding all elements that are > X .
3. Insert X at the end.
Now, for 1 shift of the window, you have adjusted the minima array from which you can find the minimum element of the window in O(1) time by looking at the first element.
Example:
The ascending minima of [6,2,1,5,3,4,8] is [1,3,4,8].
If the window slides and takes in the next element say 7 and discards the first element 6. How should we reconstruct the ascending minima?
1. As 6 is getting discarded right now, in case the lowest element in window was 6, it would have been the first element in the minima list, in which case should discard the first element in the minima list. Here this is not the case.
2. After shifting, the window has the following elements [2,1,5,3,4,8,7]. Our previous minima list was [1,3,4,8]. We add an element to the minima list only when that is the SMALLEST element in the sub-window. So any number > 7 say K would have entered the minima only because at that time, the sub-window had all numbers >= K. Now that 7 has come that too as the LAST element of the window, no element > 7 should be present in the minima list as the adjusted new sub-window will have 7 also from now on, and 7 is lesser than any other element in the sub-window. i.e. When we chose 8 for the minima list, the sub-window we had was only [8]. Now, as window has shifted and 7 has entered, the sub-window will be [8,7]. So, clearly 8 can't be present in the minima list. It should be 7.
3. So adjusting for a shift is the minima list becomes [1,3,4,7].
Other examples:
[1,3,3,2,5,8,7,8,9] - minima is [1,2,5,7,8,9]
Case #1: If window moves and adds 6 at the right, then:
1. 1 gets discarded from the minima list. leaving the minima as [2,5,7,8,9]
2. As 6 has entered, remove all elements from the right that are > 6 and add 6 at the end. So minima will become [2,5,6].
Case #2: If the given window moves and adds 10 instead of 6,
1. 1 gets discarded leaving the minima as [2,5,7,8,9]
2. Pop out all elements that are > 10 at the end and insert 10 at the end. So the minima will become [2,5,7,8,9,10].
Case #3: If the given window moves and adds 0
1. 1 gets discarded leaving the minima as [2,5,7,8,9]
2. Pop out all elements that are >= 0 and insert a 0 at the end. So the new minima will become [0]


Algorithm

def get_minima_adjusted_to_shift(previous_window, new_element, previous_minima)
  previous_minima.delete(0) if previous_window[0] == previous_minima[0]
  while (previous_minima.last > new_element)
    previous_minima.delete(previous_minima.size-1)
  end
  previous_minima << new_element
  return previous_minima
end

Coming to the time complexity of the algorithm, in the worst case, all the elements might enter the minima array and all of them might get discarded from the array both of which are O(n). So the whole algorithm works in O(n) time.

Random linked list

One of my friends attended Google interview few days back, and he got this question as one of the questions. I have chosen to discuss the solution for that question in this post. I have written a dedicated post only because if you know a better solution, you can discuss it here so that many others (including myself) can learn.

Question:
There is a lined list whose node has 3 components. The trivial ones are the data and the next pointer. Apart from these two fields, the 3rd field is interesting. It is another pointer called rand which points to a random node in the list. The random node can come before/after the current node in the list, or can also be NULL. Given such a list, how will you make a copy of it? (Before jumping to see my solution, please take a couple of minutes and come up with your own solution first.)

struct node {
  int data;
  struct node *next;
  struct node *rand;
}

My Answer:
If it is just a matter of data and next fields, the solution becomes very trivial. The only challenge is the rand pointer. One crude way of doing this is to ignore the rand pointer initially and create the copy of the list. To fix the rand pointer, for each node in the given list, find out the order of the node (nth node) to which rand pointer points to. Once the n value is known, use it in the fresh list that you have created. This will take O(n^2) time and is more of a brute force type.

Here is a better solution. Assume that the list given to you is A1->A2->A3->A4 (ignoring the rand pointer).
Create a copy of the same list B1->B2->B3->B4 (Note that A1=B1, A2=B2, A3=B3, A4=B4).
Now, form a list like this A1->B1->A2->B2->A3->B3->A4->B4 (You could have created this as the first step itself, instead of creating a list with only B's).
Now assume that the rand pointers of B's are copied from A's directly. Then, if A1.rand=A3, then B1.rand=A3. Now, if you go to each odd node (i.e. nodes that are newly created), and move the rand pointer just 1 step forward, all your rand pointers will get fixed correctly.
Now the only remaining task is to break down the list once again to two lists which should be very trivial.

Any other answer?
Guys, I have shared one solution that I know of. Is there any better way of doing this?