Google Interview Question
Country: United States
Interview Type: Phone Interview
Please note that my code is basically a MERGE SORT and I just added ONE line of code:
input->at(i).value += ( end - j + 1 );
The only thing i dont like about your solution is that your result array doesn't come in the same order as your input array.
You may easily restore initial order in O(n) by adding field int originalPosition to your structure.
My solution is based on building BST from right to left. The idea is as following:
In My BST every node knows the size of its right subtree (including himself). So for every new node while inserting do the following
0) have counter how many nodes there are in the subtrees which were on right side while inserting.
1) if root>new node, go left and add counter the size of root, root= leftnode
2) if root<new node, go right, increasing root's counter of right tree size by one; root=rightnode
3) repeat till leaf
1. Start traversing from the end of the array. This is O(n).
2. Create a sorted list as you go from the end of the array.
3. Apply a binary search on the sorted list to find the rank of the new number and insert that number in the list. This is O(log(n)).
Overall O(n*log(n)) complexity and you save all the effort of creating BinaryTrees or writing Merge Sort which is undoubtedly a smart solution but might not click at the time of the interview. However if the interviewer asks to not use auxiliary memory, then it is the solution to go. :)
One way to solve this with time complexity less than O(n^2) is to use a self balancing BST. AVL, Redblack etc.., can be used to get the solution in O(n Log n) time complexity
Initially we traverse the given array from right to left and insert all elements one by one in an AVL tree. While inserting a new key in an AVL tree, we first compare the key with root. We add it to the left / right accordingly and count the number of elements that are greater. We recursively follow the same approach for all nodes down the root.
#include <stdio.h>
#include <stdlib.h>
struct node {
int key;
struct node *left;
struct node *right;
int height;
int size;
};
int min(int a, int b);
int height(struct node *N) {
if (N == NULL)
return 0;
return N->height;
}
int size(struct node *N) {
if (N == NULL)
return 0;
return N->size;
}
int min(int a, int b) {
return (a < b)? a : b;
}
struct node* newNode(int key) {
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1;
node->size = 1;
return(node);
}
struct node *rightRotate(struct node *y) {
struct node *x = y->left;
struct node *T2 = x->right;
x->right = y;
y->left = T2;
y->height = min(height(y->left), height(y->right))+1;
x->height = min(height(x->left), height(x->right))+1;
y->size = size(y->left) + size(y->right) + 1;
x->size = size(x->left) + size(x->right) + 1;
return x;
}
struct node *leftRotate(struct node *x) {
struct node *y = x->right;
struct node *T2 = y->left;
y->left = x;
x->right = T2;
x->height = min(height(x->left), height(x->right))+1;
y->height = min(height(y->left), height(y->right))+1;
x->size = size(x->left) + size(x->right) + 1;
y->size = size(y->left) + size(y->right) + 1;
return y;
}
int getBalance(struct node *N) {
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}
struct node* insert(struct node* node, int key, int *count) {
if (node == NULL)
return(newNode(key));
if (key > node->key)
node->left = insert(node->left, key, count);
else
{
node->right = insert(node->right, key, count);
*count = *count + size(node->left) + 1;
}
node->height = min(height(node->left), height(node->right)) + 1;
node->size = size(node->left) + size(node->right) + 1;
int balance = getBalance(node);
if (balance > 1 && key > node->left->key)
return rightRotate(node);
if (balance < -1 && key < node->right->key)
return leftRotate(node);
if (balance > 1 && key < node->left->key)
{
node->left = leftRotate(node->left);
return rightRotate(node);
}
if (balance < -1 && key > node->right->key)
{
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
void constructHigherArray (int arr[], int countHigherElements[], int n) {
int i, j;
struct node *root = NULL;
for (i = 0; i < n; i++)
countHigherElements[i] = 0;
for (i = n-1; i >= 0; i--)
{
root = insert(root, arr[i], &countHigherElements[i]);
}
}
void printArray(int arr[], int size) {
int i;
printf("\n");
for (i=0; i < size; i++)
printf("%d ", arr[i]);
}
int main() {
// int arr[] = {3,4,5,9,2,1,3};
int arr[] = {10, 6, 15, 20, 30, 5, 7, 3, 4, 5, 9, 2, 1, 3};
int n = sizeof(arr)/sizeof(arr[0]);
int *low = (int *)malloc(sizeof(int)*n);
constructHigherArray(arr, low, n);
printf("Following is the constructed larger count array");
printArray(low, n);
return 0;
}
Rather than using Self Balancing Binary Tree, why not simply create a sorted list as you go from the end of the array and apply a binary search on it to find the rank of the new number from that sorted list. That would still be O(n*log(n)) complexity and you save all the effort of creating Self Balanced Trees. :)
inline void update(int u)
{
while(u<=n)
{
val[u]++;
u+=(u&-u);
}
}
inline int sum(int u)
{
int ret = 0;
while(u>0) {
ret += val[u]; u-=(u&-u);
}
return ret;
}
first step is using map change (a[1],a[2],.....,a[n]) to any permutation of (1,2,....n).
second step. According to below source code.
for(int i=n; i>0; i--) {
/* Binary Indexed Tree */
update(a[i]);
int cnt = sum(a[i]); // cnt is number of less than a[i].
answer is print("%d ",n-i+1-cnt);
}
Time limit is n * (log(n) + log(n));
It's like first we have arr[] = {4,5,7,1,2} and we sort them we get another arr sortArr[] = { 1,2,4,5,7}. We use another array cnt[] to count the number which is larger than them in their suffix array of sortArr[], so cnt[] = {4,3,2,1,0} initially.
and we start from the first left element 4 in arr[], which is in the pos 2(0-based index) of sortArr, return the value 2, and all of the index before pos should be decreased by 1, thus cnt becomes {3,2,2or1(depending you decrease itself or not), 1,0}. Then we try another element 5, which is in pos 3, so return 1 and go on, finally the result is {2,1,0,1,0}. The complexity is O(nlgn) because we will traverse each element in arr once,which is O(n) and each time we have to access the value in O(1) and decrease the index before that position by 1, this can be done in O(lgn) using segment tree or Binary tree array.
Hello. Did you try to iterate from the last element to the first and keep track elements in stack?
input: int[] arr;
1. int[] sorted=Sort(arr) -> o(n log (n))
2. Foreach i -> o(n)
out[i]=arr.length-1-findIndex(sorted, arr[i]) -> o(log (n))
3. return out;
The findIndex method must return the biggest index in the array that has the value.
c++, implementation, O(n^2)
Loop: O(n), distance: O(n). This is not fast solution.
vector<int> remainGreaterCount(vector<int>& arr) {
multiset<int> s;
multiset<int>::iterator it;
vector<int> result;
int i, j;
result.assign(arr.size(), 0);
for (i = arr.size() - 1; i >= 0; i--) {
s.insert(arr[i]);
it = s.upper_bound(arr[i]);
result[i] = distance(it, s.end());
}
return result;
}
public class Node
{
int value;
int count;
Node left;
Node right;
Node(int v,int c)
{
value=v;
count=c;
}
}
public Node insert(int v,Node n)
{
if(n==null)
{
n=new Node(v,1);
return n;
}
Node rt=n;
Node p=rt;
while(n!=null)
{
if(v<=n.value)
{
p=n;
n=n.left;
}
else
{
n.count++;
p=n;
n=n.right;
}
}
if(v>p.value)
{
p.right=new Node(v,1);
}else
{
p.left=new Node(v,1);
}
return rt;
}
public int getCount(Node n, int v)
{
while(n!=null && n.value<=v)
{
n=n.right;
}
if(n==null)
{
return 0;
}
if(n.value>v)
{
return n.count;
}
}
public int[] getCounts(int[] a)throws NullPointerException
{
if(a==null)
{
throw new NullPointerException();
}
Node rt=null;
for(int i=a.length-1;i>=0;i--)
{
int count=getCount(rt,a[i]);
rt=insert(a[i],rt);
a[i]=count;
}
return a;
}
//Uses a BST. O(n log n) running time with O(n) space.
My O(nlogn) solution using TreeSet and custom comparator
import java.util.Arrays;
import java.util.Comparator;
import java.util.TreeSet;
/**
* Created by rshrivastava on 10/27/15.
*/
public class CountLargerElements {
private static class Node {
int val;
int count;
int index;
public Node(int v, int i) {
val = v;
index = i;
}
@Override
public boolean equals(Object obj) {
Node other = (Node) obj;
return other.val == val && other.index == index;
}
@Override
public int hashCode() {
return val + index;
}
}
public static int[] countGreater(int[] input) {
Comparator<Node> treeComparator = (first, second) -> {
if (first.equals(second)) return 0;
if (first.val < second.val) {
first.count = second.count + 1;
return -1;
} else {
return 1;
}
};
TreeSet<Node> treeSet = new TreeSet<>(treeComparator);
for (int i = input.length - 1; i >= 0; --i) {
Node node = new Node(input[i], i);
treeSet.add(node);
}
int[] result = new int[input.length];
treeSet.stream().forEach(node -> result[node.index] = node.count);
return result;
}
public static void main(String[] args) {
int[] input = new int[]{3, 4, 5, 9, 2, 1, 3};
System.out.println(Arrays.toString(countGreater(input)));
}
}
O(n log n) Java solution with TreeSet.tailSet():
public static List<Integer> solution(int[] nums) {
LinkedList<Integer> result = new LinkedList<Integer>();
TreeSet<Integer> set = new TreeSet<Integer>();
for(int i=nums.length-1; i >= 0; i--) {
Set<Integer> larger = set.tailSet(nums[i], false);
result.addFirst(larger.size());
set.add(nums[i]);
}
return result;
}
1. In naive way, it would take O(n^2) and additional array of size n.
alternate means is
--------------------------
steps:-
1. iterate each element and create binary tree, (right greater than root and left smaller than root).
2. Upon encountering duplicate , skip that node and proceed to insert as thou duplicate element is lesser than element already present.
3. traverse the constructed binary tree, for each element find number of nodes till leaf . That would provide the count of number of larger numbers for that elements.
4. repeat for remaining elements.
1. In naive way, it would take O(n^2) and additional array of size n.
alternate means is
--------------------------
steps:-
1. iterate each element and create binary tree, (right greater than root and left smaller than root).
2. Upon encountering duplicate , skip that node and proceed to insert as thou duplicate element is lesser than element already present.
3. traverse the constructed binary tree, for each element find number of nodes till leaf . That would provide the count of number of larger numbers for that elements.
4. repeat for remaining elements.
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void numGreater(int a[], int b[], int n)
{
if (n <= 1)
{
return;
}
b[n-1] = 0;
for(int i = n - 2; i >= 0; i--)
{
b[i] = (n - 1) - i;
for (int j = 0; j < n - 1 - i; j++)
{
if (a[i+j] >= a[i+1+j])
{
swap(&a[i+j], &a[i+1+j]);
b[i] --;
}
else
{
break;
}
}
}
}
int main(int argc, char* argv[])
{
int a[] = {3, 4, 5, 9, 2, 1, 3};
int b[] = {0, 0, 0, 0, 0, 0, 0};
numGreater(a, b, 7);
return 0;
}
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void numGreater(int a[], int b[], int n)
{
if (n <= 1)
{
return;
}
b[n-1] = 0;
for(int i = n - 2; i >= 0; i--)
{
b[i] = (n - 1) - i;
for (int j = 0; j < n - 1 - i; j++)
{
if (a[i+j] >= a[i+1+j])
{
swap(&a[i+j], &a[i+1+j]);
b[i] --;
}
else
{
break;
}
}
}
}
int main(int argc, char* argv[])
{
int a[] = {3, 4, 5, 9, 2, 1, 3};
int b[] = {0, 0, 0, 0, 0, 0, 0};
numGreater(a, b, 7);
return 0;
}
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void numGreater(int a[], int b[], int n)
{
if (n <= 1)
{
return;
}
b[n-1] = 0;
for(int i = n - 2; i >= 0; i--)
{
b[i] = (n - 1) - i;
for (int j = 0; j < n - 1 - i; j++)
{
if (a[i+j] >= a[i+1+j])
{
swap(&a[i+j], &a[i+1+j]);
b[i] --;
}
else
{
break;
}
}
}
}
int main(int argc, char* argv[])
{
int a[] = {3, 4, 5, 9, 2, 1, 3};
int b[] = {0, 0, 0, 0, 0, 0, 0};
numGreater(a, b, 7);
return 0;
}
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void numGreater(int a[], int b[], int n)
{
if (n <= 1)
{
return;
}
b[n-1] = 0;
for(int i = n - 2; i >= 0; i--)
{
b[i] = (n - 1) - i;
for (int j = 0; j < n - 1 - i; j++)
{
if (a[i+j] >= a[i+1+j])
{
swap(&a[i+j], &a[i+1+j]);
b[i] --;
}
else
{
break;
}
}
}
}
int main(int argc, char* argv[])
{
int a[] = {3, 4, 5, 9, 2, 1, 3};
int b[] = {0, 0, 0, 0, 0, 0, 0};
numGreater(a, b, 7);
return 0;
}
Here is C++ solution running in O(N log N) using merge sort.
#include <vector>
#include <iostream>
using namespace std;
struct node {
int value;
int count;
int pos;
node(int v, int p):value(v), count(0), pos(p){}
};
vector<node*> merge_sort(vector<node *>& input, int s, int e)
{
vector<node*> temp;
if (s == e)
{
temp.push_back(input[s]);
return temp;
}
int half = s+ (e-s)/2;
vector<node*> left = merge_sort(input, s, half);
vector<node*> right = merge_sort(input, half+1, e);
int lpos = 0, rpos = 0;
while (lpos < left.size() && rpos<right.size())
{
if (left[lpos]->value < right[rpos]->value)
{
left[lpos]->count += (right[rpos]->count + 1);
temp.push_back(left[lpos++]);
} else {
temp.push_back(right[rpos++]);
}
}
if (lpos < left.size())
temp.insert(temp.end(), left.begin()+lpos, left.end());
else if (rpos < right.size())
temp.insert(temp.end(), right.begin()+rpos, right.end());
return temp;
}
void count_larger_numbers_in_rest(int* input, int len)
{
vector<node*>list;
for (int i = 0; i < len; i++)
{
list.push_back(new node(input[i], i));
}
vector<node*> result = merge_sort(list, 0, len-1);
int* counts = new int[len];
for (int i = 0; i < len; i++)
counts[result[i]->pos]= result[i]->count;
for (int i = 0; i < len; i++)
cout<<counts[i]<<", ";
}
int main()
{
int input[7] = {3,4,5,9,2,1,3};
count_larger_numbers_in_rest(input, 7);
return 1;
}
Here is C++ version of the solution running in O (n log n) using merge sort.
#include <vector>
#include <iostream>
using namespace std;
struct node {
int value;
int count;
int pos;
node(int v, int p):value(v), count(0), pos(p){}
};
vector<node*> merge_sort(vector<node *>& input, int s, int e)
{
vector<node*> temp;
if (s == e)
{
temp.push_back(input[s]);
return temp;
}
int half = s+ (e-s)/2;
vector<node*> left = merge_sort(input, s, half);
vector<node*> right = merge_sort(input, half+1, e);
int lpos = 0, rpos = 0;
while (lpos < left.size() && rpos<right.size())
{
if (left[lpos]->value < right[rpos]->value)
{
left[lpos]->count += (right[rpos]->count + 1);
temp.push_back(left[lpos++]);
} else {
temp.push_back(right[rpos++]);
}
}
if (lpos < left.size())
temp.insert(temp.end(), left.begin()+lpos, left.end());
else if (rpos < right.size())
temp.insert(temp.end(), right.begin()+rpos, right.end());
return temp;
}
void count_larger_numbers_in_rest(int* input, int len)
{
vector<node*>list;
for (int i = 0; i < len; i++)
{
list.push_back(new node(input[i], i));
}
vector<node*> result = merge_sort(list, 0, len-1);
int* counts = new int[len];
for (int i = 0; i < len; i++)
counts[result[i]->pos]= result[i]->count;
for (int i = 0; i < len; i++)
cout<<counts[i]<<", ";
}
int main()
{
int input[7] = {3,4,5,9,2,1,3};
count_larger_numbers_in_rest(input, 7);
return 1;
}
To solve this problem a merge sort approach must be used, if we use recursion by far the implementation is clean, The idea is to split the list and in the merge process in the second list locate the first occurrence of a greater value and use its current count, a helper array is used to store the counts.
The tricky part is that the original list must be split in a pow of two in order to get a correct result.
public int[] FindValues(int[] values)
{
if (values == null || values.Length == 0)
return new int[0];
int[] result = new int[values.Length];
int n = 1;
while (n < values.Length)
n *= 2;
MergeSort(values, result, 0, n);
return result;
}
private void MergeSort(int[] values, int[] result, int startIndex, int n)
{
if (n == 1)
return;
int middle = n / 2;
MergeSort(values, result, startIndex, middle);
MergeSort(values, result, startIndex + middle, middle);
MergeLists(values, result, startIndex, startIndex + middle);
}
private void MergeLists(int[] values, int[] result, int index1, int index2)
{
int n = index2 - index1;
Debug.Assert(n > 0);
if (index2 + n >= values.Length)
n = values.Length - index2;
while (index1 < index2)
{
for (int i = 0; i < n; i++)
if (values[index1] < values[index2 + i])
{
result[index1] += (result[index2 + i] + 1);
break;
}
index1++;
}
}
Can be done in O(nlogn) using the below algo
> Prepare binary search tree from the area (takes O(nlogn)
>> While preparing, maintain its original index and value that represents how many values going towards its right (greater values)
> Once binary search tree is done, traverse the tree and prepare output array using the original index saved and the value which represent number of greater values. (any traversal takes O(n) )
Overall algo should be O(nlogn).
This is not correct. What if all the inputs are the same? i.e: 3 3 3 3 3 3. You would build a binary tree where each element is to the right and print something like 5 4 3 2 1 0 when clearly the answer should be 0 0 0 0 0 0 0. If you say, ok, just find the next biggest one, basically keep going if they are equal, then on the set I have presented your algo would run in O(n^2) time. So this is not an O(nlogn) solution.
This is not correct. Your algo runs in O(n^2) worst case. Consider the following set:
[3 3 3 3]
your binary tree would just be a list basically, with all nodes going to the right. Then you would print
[3 2 1 0]
which clearly is not correct since the answer should be
[0 0 0 0]
. If you say, ok ignore the equals and just keep going until you find one on the right side which is bigger, then your algorithm will take O(n^2) time.
I don't think a BST is the right way to go. I think this problem can be solved in O(n) time by traversing the array from the back and keeping track of an absolute maximum and a local maximum.
The idea is to start from the right hand side of array to the left hand side and use insertion sort.
- Initialize a sorted data like std::set as sortedArray
- Initialize a linked list to take the result, result
- Take the element, x, from the array in the reverse order
- Find the number of larger value in sortedArray than x, as n
- Push n into the front of result
- Insert x into sortedArray
- Loop the above 4 steps until exhaust the whole array
- Return result
Implementation: cpluspluslearning-petert.blogspot.co.uk/2015/11/insertion-sort-find-number-of-larger.html
Test
void TestFindTheNumberOfLargerValuesInTheRemainingArray()
{
{
std::vector<int> input;
std::vector<int> output = FindTheNumberOfLargerValuesInTheRemainingArray(input);
assert(output.empty() == true);
input.push_back(0);
output = FindTheNumberOfLargerValuesInTheRemainingArray(input);
assert(output.size() == 1);
assert(output[0] == 0);
}
{
std::vector<int> input = { 3, 4, 5, 9, 2, 1, 3 };
const std::vector<int> result = { 3, 2, 1, 0, 1, 1, 0 };
std::vector<int> output = FindTheNumberOfLargerValuesInTheRemainingArray(input);
assert(result == output);
}
{
std::vector<int> input = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
const std::vector<int> result = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
std::vector<int> output = FindTheNumberOfLargerValuesInTheRemainingArray(input);
assert(result == output);
}
{
std::vector<int> input = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
const std::vector<int> result = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
std::vector<int> output = FindTheNumberOfLargerValuesInTheRemainingArray(input);
assert(result == output);
}
}
Let's think about sorting in descending order for just a second. Intuitively, exchanging elements while sorting contains the required information already. If we move some element forward, we incrementing the counter for all elements, that we have "outruned" in the array.
So, we need only to modify some existing sorting algorithm witn O(nlogn) complexity in order to store the required information. Let's take Merge sort and make two modifications.
1. Let's preserve the source array by introducing the array of indices ( int[] arrindices ), where arrindices[i] shows which element of the source array stays at position i at the moment.
2. we introduce int[] resarray to store the number of elements, greater than that element remaining in the array.
Let's consider the DoMerge part of the algorithms, where we are merging two sorted subarrays. If we take the element from the second array (else clause), it is by default greater then all remaining elements from the first array. So, we have to increment the resulting array for all such elements by one. To avoid introducing another loops in code, we'll introduce the counter of the elements, that had been moved from the second array, and will add this counter to resarray for each element of the first array, when it is taken to the resulting array.
Complete code here:
public class MergeSortModified
{
public void DoMerge(int[] arr, int[] arrindices, int[] resarray, int start, int middle, int end)
{
// create temp array to store sorted subarray
int[] temp = new int[end - start + 1];
int l = start;
int m = middle + 1;
int k = 0;
// store the amount
int gr = 0;
// run a marker until at least one source subarrays is not empty
while (l <= middle && m <= end)
{
if (arr[arrindices[l]] >= arr[arrindices[m]])
{
temp[k] = arrindices[l];
// increment the result array by the number of already found greater elements
resarray[arrindices[l]] += gr;
l++;
k++;
}
else
{
// increment the amount of "greater" elements
gr++;
temp[k] = arrindices[m];
m++;
k++;
}
}
// take the remaining elements from the first subarray is any
while (l <= middle)
{
temp[k] = arrindices[l];
// increment the result array by the number of already found greater elements
resarray[arrindices[l]] += gr;
k++;
l++;
}
// take the remaining elements from the second subarray is any
while (m <= end)
{
temp[k++] = arrindices[m++];
}
// copy sorted subarray of indices back to the indices array
for (int pos = 0; pos < end - start + 1; pos++)
arrindices[start + pos] = temp[pos];
}
public void Merge(int[] arr, int[] arrindices, int[] resarray, int start, int end)
{
// if array is long enough
if (start < end)
{
// divide array into two parts
int m = (start + end) / 2;
// sort the first half
Merge(arr, arrindices, resarray, start, m);
// sort the second half
Merge(arr, arrindices, resarray, m + 1, end);
// Merge sorted subarrays
DoMerge(arr, arrindices, resarray, start, m, end);
}
}
}
Merge sort with tweak will do it;
Assume we have the following numbers, for each number we also define a "value" which is the number of items greater than me with a bigger index, this value is initialized to zero
16, 17, 9, 0, 19, 24, 3, 8,
Now I explain the last step of the merge sort, here's what I have
{number=0 value=0 },{number=9 value=0 },{number=16 value=1 },{number=17 value=0 }
{number=3 value=1 },{number=8 value=0 },{number=19 value=1 },{number=24 value=0 }
- Pick "0": 0 is less than 3, so it's less than 4 elements in the second half, so it's value is insreased by 4
- Pick "3": it's from the second half, do nothing
- Pick "8": it's from the second half, do nothing
- Pick "9": 9 is smallet than 2 elements in the second half, so it's value is insreased by 2
- Pick "16": 16 is smallet than 2 elements in the second half, so it's value is insreased by 2
- Pick "17": 17 is smallet than 2 elements in the second half, so it's value is insreased by 2
- Pick "19": it's from the second half, do nothing
- Pick "24": it's from the second half, do nothing
Here is the final result
(0 , 4)
(3 , 1)
(8 , 0)
(9 , 2)
(16 , 3)
(17 , 2)
(19 , 1)
(24 , 0)
Here's the code
- koosha.nejad October 27, 2015