Interview questions asked in Google

I will try to post my solutions to Google Interview Questions as & when I get those & if I can solve those. Request you also to keep posting the questions & suggestions here so that all can benefit.

Question 1:
Given an array of integers, return a new array where each element in the new array is the number of smaller elements to the right of that element in the original input array.
For example, given the array [3, 4, 9, 6, 1], return [1, 1, 2, 1, 0], since:

• There is 1 smaller element to the right of 3
• There is 1 smaller element to the right of 4
• There are 2 smaller elements to the right of 9
• There is 1 smaller element to the right of 6
• There are no smaller elements to the right of 1

 Solution which I can think is as below using Binary Tree & I feel that it can further be
​ improved such that count is found during Tree creation itself.

 I think above buildTree() can be modified like shown below to reduce the traversing-
 Please provide your comments if we can solve it in better way & please keep posting the questions you get.

 I got the concern about the performance of the above solution, so just did a little tweak to improve its performance as shown below -

 Well above can be one one way but better will be to have 2 other arrays-
 one array keeps the count of smaller elements in the right to the current index.
 second array keeps the index of next smaller element in the right to current index.
​ So this way also we can hop to have log n comparison like we have above.