Google Interview Question Software Engineer / Developers
Country: India
If the input array contains duplicate values, "augmented", order statistics (BST/Red-Black) tree is better choice than merge sort, as it's not stable.
This problem is called "Counting number of inversions" and one of possible solutions is modified "merge" operation of mergesort. Google it :)
#include <iostream>
#include <cstring>
using namespace std;
void merge(int *array, int *pos, int *result, int start, int mid, int end)
{
int temp[1000];
for (int i = start; i <= end; ++i)
{
temp[i] = pos[i];
}
int cur = start;
int leftcur = start;
int rightcur = mid + 1;
while (leftcur <= mid && rightcur <= end)
{
if (array[temp[leftcur]] <= array[temp[rightcur]])
{
pos[cur] = temp[leftcur];
result[pos[cur]] += rightcur - mid - 1;
++leftcur;
++cur;
}
else
{
pos[cur] = temp[rightcur];
++cur;
++rightcur;
}
}
while (leftcur <= mid)
{
pos[cur] = temp[leftcur];
result[pos[cur]] += end - mid;
++cur;
++leftcur;
}
while (rightcur <= end)
{
pos[cur] = temp[rightcur];
++cur;
++rightcur;
}
}
void mergesort(int *array, int *pos, int *result, int start, int end)
{
if (start >= end)
{
return;
}
int mid = start + (end - start) / 2;
mergesort(array, pos, result, start, mid);
mergesort(array, pos, result, mid + 1, end);
merge(array, pos, result, start, mid, end);
}
int main()
{
int array[1000];
int pos[1000];
int result[1000];
memset(result, 0, sizeof(int) * 1000);
int n;
cin >> n;
for (int i = 0; i < n; ++i)
{
cin >> array[i];
pos[i] = i;
}
mergesort(array, pos, result, 0, n - 1);
/*for (int i = 0; i < n; ++i)
{
cout << array[pos[i]] << " ";
}
cout << endl;*/
for (int i = 0; i < n; ++i)
{
cout << result[i] << " ";
}
cout << endl;
return 0;
}
why you doing merge sort for this, This is not sorting question I guess. I think question needs more clarity.
I really can't understand how BST or merge sort will solve this problem in O(nlogn) in worst case. Please explain. I have a google interview this month :)
Most straightforward method is based on BST insert. with two extra values to record value and left child count.
Class Node{
public:
node *left, *right, *parent;
int leftc;
int key;
int val;
node(int _key=0):key(_key){
left=NULL; right = NULL; parent=NULL;
val=0; leftc=0;}
}
by calling the following function from the last element to the first one, you can get the result in ave O(nlogn), worst O(n^2);
int revised_insert(node*& root, node* new){
node* curr=root;
node*tmp=NULL;
while(curr!=NULL){
tmp=curr;
if(new->key>curr->key){
curr->leftc++;
curr=curr->left;}
else{
new->value+=curr->leftc+1;
curr=curr->right;}
}
//update links
new->parent=tmp;
if (tmp==NULL)
root=new;
else if(new->key<tmp->key)
tmp->left=new;
else tmp->right=new;
//return result
return new->value;
}
Simple algorithm, please confirm:
1. Start inserting elements from the end of the array into a BST.
2. As you're inserting current element, increment a counter when you go right, this will imply that current element is greater than parent.
3. Note that elements of left subtree of parent are less than parent and thus less than current element, so in addition to incrementing counter when going right, add all elements in the left subtree of that level.
4. If going left, increment a left_subtree_counter and keep that value in the parent so it can be easily tracked.
5. Do this until you get to the level for the current element.
This is simply building a BST, which takes O(nlogn).
Space O(n).
If you get as input and array [5,4,3,2,1] (or any sorted array) it won't be O(nlogn) but O(n^2). On the other hand a self balancing tree (RB, AVL, Splay etc) will mess up our "child count". So we have worst case O(n^2) (average probably O(nlogn)) with O(n) space vs O(n^2) worst O(1) space brute force.
You can use a binary tree insertion algorithm....Start inserting the elements into the tree from the end of the array .So for eg in the given array the tree's root will be 2.Then when inserting an element if we go towards the right child of the parent increment the counter if we go towards the left child do not increment the counter....reset the counter to zero for each insertion...So nlog n should be run time of the alg...
This solution is partially correct. If we do nothing when go left then we're just ignoring them and they'll not appear in later calculations. This will result to wrong numbers, e.g. for the array in example [4, 12, 5, 6, 1, 34, 3, 2] we will get the result [2, 3, 2, 2, 0, 1, 0].
For the correct solution we need to keep the number of left subtree children also for each node (let's define it as num_of_lefts). So when for a given element we should go to left we should increment num_of_lefts for the parent node. Else if we should go to right we should both increment the counter and add the num_of_lefts (as we know for sure they'll also be less than the current element and their indexes are greater in the original array).
You can find my implementation in C++ in the page comments.
For each element in the array, count the number of elements to the right-side of it, that are smaller than it. For eg, considering the element 12, there are 5 elements (5,6,1,3,2) that are smaller than it, and positioned to the right-hand side of it. 4 is not counted because it is to the left of 12.
This sort of comment is very unhelpful. You might have understood the question immediately, but it could be that it is not instantly clear to somebody else. After all we are all here to take knowledge, and spread it around as well. If you don't want to help, its fine; but when somebody is asking for help and you do reply, it would be great if you could add a comment that is actually a value-add rather than something completely unhelpful. Just saying. Thanks for understanding.
Well..it,a clever application of segment tree/binary indexed tree.
my code using BIT
#include"stdio.h"
int ct[2000003];
int read()
{
int sum=0;
char c;
while(1)
{
c=getchar_unlocked();
if(c != 32 && c!= EOF) sum=sum*10+c-'0';
else break;
//return sum;
}
return sum;
}
void put(int pos)
{
while(pos<2000003)
ct[pos] ++,
pos += (pos & -pos);
}
unsigned int get(int pos)
{
unsigned int ans=0;
while (pos > 0)
ans += ct[pos],
pos -= (pos & -pos);
return ans;
}
int res[5000000],c=0;
void m()
{
int n;
n=read();if(n==0) return;
n+=1000002;
m();
res[c++]=get(n-1);
put(n);
}
int main()
{
m();
//for(int i=0;i<=100;i++) printf("rec[%d]=%d ",i,res[i]);
while(c--)
printf("%d ",res[c]);
}
Well..it,a clever application of segment tree/binary indexed tree.
my code using BIT
#include"stdio.h"
int ct[2000003];
int read()
{
int sum=0;
char c;
while(1)
{
c=getchar_unlocked();
if(c != 32 && c!= EOF) sum=sum*10+c-'0';
else break;
//return sum;
}
return sum;
}
void put(int pos)
{
while(pos<2000003)
ct[pos] ++,
pos += (pos & -pos);
}
unsigned int get(int pos)
{
unsigned int ans=0;
while (pos > 0)
ans += ct[pos],
pos -= (pos & -pos);
return ans;
}
int res[5000000],c=0;
void m()
{
int n;
n=read();if(n==0) return;
n+=1000002;
m();
res[c++]=get(n-1);
put(n);
}
int main()
{
m();
//for(int i=0;i<=100;i++) printf("rec[%d]=%d ",i,res[i]);
while(c--)
printf("%d ",res[c]);
}
Well..it,a clever application of segment tree/binary indexed tree.
my code using BIT
#include"stdio.h"
int ct[2000003];
int read()
{
int sum=0;
char c;
while(1)
{
c=getchar_unlocked();
if(c != 32 && c!= EOF) sum=sum*10+c-'0';
else break;
//return sum;
}
return sum;
}
void put(int pos)
{
while(pos<2000003)
ct[pos] ++,
pos += (pos & -pos);
}
unsigned int get(int pos)
{
unsigned int ans=0;
while (pos > 0)
ans += ct[pos],
pos -= (pos & -pos);
return ans;
}
int res[5000000],c=0;
void m()
{
int n;
n=read();if(n==0) return;
n+=1000002;
m();
res[c++]=get(n-1);
put(n);
}
int main()
{
m();
//for(int i=0;i<=100;i++) printf("rec[%d]=%d ",i,res[i]);
while(c--)
printf("%d ",res[c]);
}
// start looking for smaller numbers from the right end
int[] findSmaller(int[] a) {
int[] results = new int[a.length];
results[n-1] = 0;
for (int i = n-2; i>=0; i--) {
for (int j = i+1; j<n; j++) {
if (a[i] > a[j])
results[i] = results[j] + 1;
}
// if can't find any smaller numbers, then don't need to do anything since default value is 0.
}
return results;
}
// start looking for smaller numbers from the right end
int[] findSmaller(int[] a) {
int[] results = new int[a.length];
results[n-1] = 0;
for (int i = n-2; i>=0; i--) {
for (int j = i+1; j<n; j++) {
if (a[i] > a[j])
results[i] = results[j] + 1;
}
// if can't find any smaller numbers, then don't need to do anything since default value is 0.
}
return results;
}
I think a BST would do the job. On average it should take O(n*log(n)). Worst case is O(n^2).
Every node in the BST is a pair of (value in the array, number of elements in the left subtree).
Node {
int d;
int leftsize = 0;
Node left;
Node right;
Node(int d) {
this.d = d;
}
}
Node root = new Node(a[a.length - 1]);
Node parent;
int[] r = new int[a.length];
r[a.length-1] = 0;
for (int i = a.length - 2; i--; i >=0) {
int c = 0;
while (root != null) {
parent = root;
if (root.d < a[i]) {
c += root.leftsize + 1;
root = root.right;
}
else {
root.leftsize++;
root = root.left;
}
}
if (parent.d < d) {
parent.right = new Node(d);
}
else {
parent.left = new Node(d);
}
r[i] = c;
}
public class SmallerElesOnRight {
private static class Pair {
int val, index;
Pair(int val, int index) {
this.val = val;
this.index = index;
}
static Pair[] construct(Pair a[], int i, int j) {
Pair b[] = new Pair[j - i + 1];
for (int k = i; k <= j; ++k) {
b[k - i] = new Pair(a[k].val, a[k].index);
}
return b;
}
}
private static void mergeSort(Pair a[], int ans[]) {
if (a.length <= 1) {
return;
}
Pair l[] = Pair.construct(a, 0, (a.length >> 1) - 1);
mergeSort(l, ans);
Pair r[] = Pair.construct(a, a.length >> 1, a.length - 1);
mergeSort(r, ans);
int i = 0, j = 0;
while (i < l.length && j < r.length) {
if (l[i].val >= r[j].val) {
ans[l[i].index] += r.length - j;
a[i + j].val = l[i].val;
a[i + j].index = l[i].index;
++i;
} else {
a[i + j].val = r[j].val;
a[i + j].index = r[j].index;
++j;
}
}
while (i < l.length) {
a[i + j].val = l[i].val;
a[i + j].index = l[i].index;
++i;
}
while (j < r.length) {
a[i + j].val = r[j].val;
a[i + j].index = r[j].index;
++j;
}
}
public static void getSmallerElesOnRight(int a[]) {
Pair b[] = new Pair[a.length];
for (int i = 0; i < a.length; ++i) {
b[i] = new Pair(a[i], i);
}
int ans[] = new int[a.length];
mergeSort(b, ans);
for (int i = 0; i < ans.length; ++i) {
System.out.print(ans[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
int a[] = {4, 12, 5, 6, 1, 34, 3, 2};
getSmallerElesOnRight(a);
}
}
public class SmallerElesOnRight {
private static class Pair {
int val, index;
Pair(int val, int index) {
this.val = val;
this.index = index;
}
static Pair[] construct(Pair a[], int i, int j) {
Pair b[] = new Pair[j - i + 1];
for (int k = i; k <= j; ++k) {
b[k - i] = new Pair(a[k].val, a[k].index);
}
return b;
}
}
private static void mergeSort(Pair a[], int ans[]) {
if (a.length <= 1) {
return;
}
Pair l[] = Pair.construct(a, 0, (a.length >> 1) - 1);
mergeSort(l, ans);
Pair r[] = Pair.construct(a, a.length >> 1, a.length - 1);
mergeSort(r, ans);
int i = 0, j = 0;
while (i < l.length && j < r.length) {
if (l[i].val >= r[j].val) {
ans[l[i].index] += r.length - j;
a[i + j].val = l[i].val;
a[i + j].index = l[i].index;
++i;
} else {
a[i + j].val = r[j].val;
a[i + j].index = r[j].index;
++j;
}
}
while (i < l.length) {
a[i + j].val = l[i].val;
a[i + j].index = l[i].index;
++i;
}
while (j < r.length) {
a[i + j].val = r[j].val;
a[i + j].index = r[j].index;
++j;
}
}
public static void getSmallerElesOnRight(int a[]) {
Pair b[] = new Pair[a.length];
for (int i = 0; i < a.length; ++i) {
b[i] = new Pair(a[i], i);
}
int ans[] = new int[a.length];
mergeSort(b, ans);
for (int i = 0; i < ans.length; ++i) {
System.out.print(ans[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
int a[] = {4, 12, 5, 6, 1, 34, 3, 2};
getSmallerElesOnRight(a);
}
}
Working example using BST and modified insertion algorithm.
//
// main.cpp
// SmallerElementsOnRightSide
//
// Created by Artak Begnazaryan on 3/2/12.
//
#include <iostream>
struct Node {
int value;
Node* left;
Node* right;
size_t num_of_lefts;
Node(int val)
: value(val)
, left(0)
, right(0)
, num_of_lefts(0)
{
}
};
struct BST {
Node* root;
BST()
: root(0)
{
}
size_t insert_element(int value)
{
if (0 == root) {
root = new Node(value);
return 0;
}
size_t result = 0;
Node* runner = root;
while (0 != runner) {
if (runner->value < value) {
++result;
result += runner->num_of_lefts;
if (0 == runner->right) {
runner->right = new Node(value);
return result;
} else {
runner = runner->right;
}
} else {
++runner->num_of_lefts;
if (0 == runner->left) {
runner->left = new Node(value);
return result;
} else {
runner = runner->left;
}
}
}
return 0;
}
};
void smaller_elements_on_right_side(int array[], size_t size, size_t result[])
{
BST tree;
for (int i = (int)(size - 1); i >= 0; --i) {
result[i] = tree.insert_element(array[i]);
}
}
template <typename T>
void print_array(T array[], size_t size)
{
for (size_t i = 0; i < size; ++i) {
std::cout << array[i] << ' ';
}
std::cout << std::endl;
}
int main (int argc, const char * argv[])
{
const size_t size = 8;
int array[size] = {4, 12, 5, 6, 1, 34, 3, 2};
size_t result[size] = {0};
smaller_elements_on_right_side(array, size, result);
print_array(array, size);
print_array(result, size);
return 0;
}
package com.keane.driver;
public class SmallFromRight {
public static void main(String[] args) {
int[] numbers = {4,12,5,6,1,34,3,2};
int[] outNum = new int[8];
int pos=0;
int numCount=0;
for(int i=0;i<numbers.length;i++)
{
numCount=0;
for(int j=i;j<numbers.length;j++)
{
if(numbers[i]>numbers[j])
{
numCount++;
}
}
outNum[pos++]=numCount;
}
for(int i=0;i<outNum.length;i++)
{
System.out.print(outNum[i]+",");
}}}
#include <iostream>
using namespace std;
int l[100];
int insert(int* A, int *B, int x)
{
int k = 0;
int i = 0;
while (A[k])
{
if (x < A[k])
{
l[k]++;
k = k*2+1;
}
else
{
i = i+1+l[k];
k = k*2+2;
}
}
A[k] = x;
B[k] = i;
return k;
}
int main()
{
int N;
int A[200];
int B[200];
int C[200];
int D[200];
int x;
cin >> N;
for (int i = N-1; i >= 0; --i)
cin >> D[i];
for (int i = 0; i < N; i++)
C[D[i]] = insert(A, B, D[i]);
for (int i = 0; i < N; i++)
cout << D[i] << ":" << B[C[D[i]]]<<endl;
}
import java.util.Arrays;
class TreeNode
{
public int value;
public int count;
public TreeNode left,right;
public TreeNode(int v)
{
value = v;
count = 0;
}
}
class BST
{
TreeNode root = null;
private int findAndInsert(int value,int all)
{
if( root == null)
{
root = new TreeNode(value);
return 0;
}
if( root.value < value)
{
TreeNode node = new TreeNode(value);
node.left = root;
node.count = all - 1;
root = node;
return all - 1;
}
TreeNode current = root;
TreeNode parent = root;
while(current != null)
{
if( current.value > value )
{
current.count++;
parent = current;
current = current.left;
}else
{
break;
}
}
TreeNode node = new TreeNode(value);
node.count = parent.count -1;
node.left = parent.left;
parent.left = node;
return node.count;
}
public int[] find(int[] a)
{
BST tree = new BST();
for(int i=a.length - 1; i> -1; i--)
{
a[i] = tree.findAndInsert(a[i], a.length - i);
}
return a;
}
}
This is a solution that works in (nlog n) in average. I use a binary search tree in which each node has an extra field (count). Here is the procedure:
- Scan the list from beginning to end and for each item:
- Add it to tree . While adding to tree increase the count number of each node if we are going to the left of that node.
- Scan the list again. For each element result=0. Find the item in the tree. In the process of searching for that element, if you are going right of a node add count of that node to result otherwise decrease the count of that node.
Example:
4,12,5,6,1,34,3,2
After the first phase the tree is look like this
4(3)
/ \
1 12(2)
\ / \
3(1) 5 34
/ \
2 6
The most straight forward way:
public int[] GetSmallerCounts(int[] input)
{
if (input == null || input.Length == 0)
{
throw new ArgumentException();
}
int[] result = new int[input.Length];
for (int i = 0; i < result.Length; i++)
{
int count = 0;
for (int j = i+1; j < result.Length; j++)
{
if (input[j] < input[i])
{
count++;
}
}
result[i] = count;
}
return result;
}
My solution based on merge sort
running time O(nlogn)
space complexity S(n)
#include <map>
#include <iostream>
std::map<int,int> counters;
void merge(int* arr, size_t left,size_t mid,size_t right,int* tempArr)
{
int size = 0;
size_t leftIdx = left,rightIdx = mid+1;
int c = 0;
while (leftIdx <= mid && rightIdx <= right)
{
if (arr[leftIdx] <= arr[rightIdx])
{
int n = arr[leftIdx++];
tempArr[size++] = n;
counters[n]+=c;
}
else
{
c++;
tempArr[size++] = arr[rightIdx++];
}
}
while (leftIdx <= mid)
{
int n = arr[leftIdx++];
tempArr[size++] = n;
counters[n]+=c;
}
while (rightIdx <= right)
{
tempArr[size++] = arr[rightIdx++];
}
for(int i = 0; i < size ; ++i)
{
arr[left+i] = tempArr[i];
}
}
void mergeSortHelper(int* arr,int left,int right,int* temp)
{
if (left==right) return;
int mid = (left+right)/2;
mergeSortHelper(arr,left,mid,temp);
mergeSortHelper(arr,mid+1,right,temp);
merge(arr,left,mid,right,temp);
}
void mergeSort(int* arr,int size)
{
int* temp = new int[size];
mergeSortHelper(arr,0,size-1,temp);
delete temp;
}
int main(int argv, char** args)
{
int arr[] = {4,12,5,6,1,34,3,2};
int arr2[] = {4,12,5,6,1,34,3,2};
int temp[] = {4,12,5,6,1,34,3,2};
for(int i = 0; i < 8 ; ++i)
{
counters[arr[i]] = 0;
}
mergeSort(arr,8);
for(int i = 0; i < 8 ; ++i)
{
std::cout << counters[arr2[i]] << ",";
}
return 0;
}
Solution based on BST:
class Node:
def __init__(self, val):
self.val = val
self.right = None
self.left = None
self.nodes_on_left = 0
self.nodes_on_right = 0
class BST(Node):
def __init__(self):
self.root = None
def insert_counting_lower(self, val):
lower_count = 0
if not self.root: self.root = Node(val)
else:
iterator = self.root
while True:
if val < iterator.val:
iterator.nodes_on_left += 1
if not iterator.left:
iterator.left = Node(val)
break
else:
iterator = iterator.left
elif val >= iterator.val:
iterator.nodes_on_right += 1
lower_count += iterator.nodes_on_left + 1
if not iterator.right:
iterator.right = Node(val)
break
else:
iterator = iterator.right
return lower_count
def smaller_on_right(array):
tree = BST()
lower_count = []
for e in reversed(array):
lower_count.append(tree.insert_counting_lower(e))
return lower_count[::-1]
Modify merge-sort
- Rayden February 28, 2012