Google Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
Code...
class CountInversions{
public:
long* nums;
long count(long nums[], int begin, int end){
this->nums = nums;
return count(begin,end);
}
long count(int begin, int end){
if(begin >= end) return 0;
long c1 = count(begin, (begin+end)/2);
long c2 = count((begin+end)/2 + 1, end);
long c3 = mergeCount(begin, (begin+end)/2, (begin+end)/2+1, end);
return c1 + c2 + c3;
}
long mergeCount(int b1, int e1,int b2, int e2){
int p1 = b1;
int p2 = b2;
int len = e1-b1+1 + e2-b2+1;
long temp[len];
memset(temp,0,sizeof(temp));
long count = 0;
for(int i = 0; i < len; i ++){
if(p1 > e1){
temp[i] = nums[p2];
p2++;
}else if(p2 > e2){
temp[i] = nums[p1];
p1++;
}else{
if(nums[p1] <= nums[p2]){
temp[i] = nums[p1];
p1++;
}else{
temp[i] = nums[p2];
p2++;
count += e1-p1+1;
}
}
}
memcpy(nums+b1, temp, sizeof(temp));
return count;
}
};
Analysis:
1) We can observe that in a perfectly sorted list, the number of unordered pairs is 0. E.g.
[1 2 3 4 5]
2) If we swapped only one of them, the number of unordered pairs is the number of elements to the left of it. E.g.
[2 3 4 1 5]
In this case, the number of unordered pairs is 3:
[2 1], [3 1], [4 1]
3) Now, we observe the positional difference of the swapped elemented, in the sorted list, it's 0, in the scrambled list, it's 3. The difference seems to be our answer.
4) Let's take a look at a bit more complex example:
[2 5 4 1 3]
The number of unordered pairs is 6. How do we get that number?
Algorithm:
1) Sort the list into a copy of another list used for comparison. (Commonly O(N*log N))
2) Starting from the smallest element in the sorted list and add its positional difference to the final result.
3) Remove this element from both list. (There may be other positional math that doesn't require removing the element, but I'm too lazy to try to figure that out. This I find is very straight-forward to explain the algorithm)
4) Do (2) and (3) for all elements in the list. (O(N))
Time complexity: O(N * log N) + O(N) = O(N * log N)
E.g.
[2 5 4 1 3]
// Sort.
[1 2 3 4 5]
// Iteration 0.
[2 5 4 1 3]
[1 2 3 4 5]
numOfUnorderedPairs = 0;
// Iteration 1.
[2 5 4 3]
[2 3 4 5]
numOfUnorderedPairs = 3;
// Iteration 2.
[5 4 3]
[3 4 5]
numOfUnorderedPairs = 3; // no positional difference.
// Iteration 3.
[5 4]
[4 5]
numOfUnorderedPairs = 5;
// Iteration 4.
[5]
[5]
numOfUnorderedPairs = 6;
// Iteration 5.
[]
[]
numOfUnorderedPairs = 6; // Done.
I'm running short on time when writing this up, so I'll come up with code in a later post.
I think it's essential to show how to do (2) & (3) in O(n) instead of O(n^2), which I don't think is possible if you were to actually remove each element.
Otherwise the whole algorithm is O(n^2) and you might as well just do a double loop directly.
This is similar to the enhanced merge sort, but is more concise or maybe not. Iterate over the array and insert each number into a binary search tree. At each node maintain the number of nodes in the branch of the tree. When inserting a node into the tree count the number of nodes with values that are greater than the value of the inserted node. There are n inserts into the binary tree each costing log(n) so the total time complexity is n*log(n). Space complexity is O(n).
int numberOfInversions(int a[]) {
int inversionCount = 0;
Node root = new Node();
root.v = a[0];
root.count = 1;
for (int i = 1; i < a.length; ++i) {
Node node = root;
while (true) {
node.count++;
if (a[i] < node.v) {
inversionCount += (node.right != null ? node.right.count : 0) + 1;
if (node.left == null) {
node.left = new Node();
node.left.v = a[i];
node.left.count = 1;
break;
}
else {
node = node.left;
}
}
else {
if (node.right == null) {
node.right = new Node();
node.right.v = a[i];
node.right.count = 1;
break;
}
else {
node = node.right;
}
}
}
}
return inversionCount;
}
static class Node {
public int v;
public Node left;
public Node right;
public int count;
}
This problem is called "Number of inversions". It can be solved in O(NlogN) time by a mergesort or by any data structure that can find the sum on the any range [0; x] of the tree and modify a single element in O(logN) time. For example Binary Indexed Tree, or Segment Tree.
Now why do we need to find a sum on the range in this problem? If we have our input array, we can iterate starting from the last element to first, and for each element we need to know how many numbers lesser than the current element appeared in the array before. We can count this as sum on the range from 0 to element - 1. And after that we need to tell that this element has appeared by adding 1 to the tree in a single position - tree[element]. At the start out tree contains all zeros - we have not seen any number. Update and sum should work in O(NlogN) time.
Solution using Binary Indexed Tree:
const int N = 10000;
int tree[N + 1];
void update(int idx, int val) {
for (int i = idx; i <= N; i += i & -i) {
tree[i] += val;
}
}
int get(int idx) {
int res = 0;
for (int i = idx; i > 0; i -= i & -i) {
res += tree[i];
}
return res;
}
int array[N], n, result;
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> array[i];
}
for (int i = n - 1; i > -1; i--) {
update(array[i], 1);
result += get(array[i] - 1);
}
cout << result << "\n";
return 0;
}
{{ //DP Version can be modeled as longest decreasing subsequence with a twist
DP[0] = 0;
DP[j] = MAX { DP[i] for i<j for which A[j] < A[i] } + 1
// Once we have the DP Table, scan through the DP table add the entries to get the total number of pairs
//DP entry gives the number of entries since we are interested in pairs, we subtract 1 from the entries.
int totalPairs = 0;
for (int i in 1..DP.length())
totalPairs +=(DP[i]-1);
//You back track for each entry to arrive at the actual pairs
//your example (3, 2, 1}
//DP Entries 0 1 2 3. Total Pairs 1+2 = 3
//Another example (6 5 0 2 1)
// //DP Entries 0 1 2 3 3 4. Total Pairs = 1 + 2 + 2+3 = 8
//Running time with for this O(n2)
//But if we model it a dijkstra shortest path, with numbers as nodes and path exists if there
//i < j such that A[i] > A[j] Running time becomes O(nlogn)
}}
//DP Version can be modeled as longest decreasing subsequence with a twist
DP[0] = 0;
DP[j] = MAX { DP[i] for i<j for which A[j] < A[i] } + 1
// Once we have the DP Table, scan through the DP table add the entries to get the total number of pairs
//DP entry gives the number of entries since we are interested in pairs, we subtract 1 from the entries.
int totalPairs = 0;
for (int i in 1..DP.length())
totalPairs +=(DP[i]-1);
//You back track for each entry to arrive at the actual pairs
//your example (3, 2, 1}
//DP Entries 0 1 2 3. Total Pairs 1+2 = 3
//Another example (6 5 0 2 1)
// //DP Entries 0 1 2 3 3 4. Total Pairs = 1 + 2 + 2+3 = 8
//Running time with for this O(n2)
//But if we model it a dijkstra shortest path, with numbers as nodes and path exists if there
//i < j such that A[i] > A[j] Running time becomes O(nlogn)
Based on Anonymous answer above. During Inversion you also need to multiply with how many elements are greater than the right. and thats given by count += (middle-i)
public class MergeSort {
private int[] array;
private int[] tempMergArr;
private int length;
int count = 0;
public static void main(String a[]){
int[] inputArr = {1,3,2};
MergeSort mms = new MergeSort();
mms.sort(inputArr);
for(int i:inputArr){
System.out.print(i);
System.out.print(" ");
}
System.out.println("Count:"+mms.count);
}
public void sort(int inputArr[]) {
this.array = inputArr;
this.length = inputArr.length;
this.tempMergArr = new int[length];
doMergeSort(0, length - 1);
}
private void doMergeSort(int lowerIndex, int higherIndex) {
if (lowerIndex < higherIndex) {
int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
// Below step sorts the left side of the array
System.out.println("doMergeSort("+lowerIndex+","+middle+")");
doMergeSort(lowerIndex, middle);
// Below step sorts the right side of the array
System.out.println("doMergeSort("+(middle+1)+","+higherIndex+")");
doMergeSort(middle + 1, higherIndex);
// Now merge both sides
System.out.println("mergeParts("+(lowerIndex)+","+middle+","+higherIndex+")");
mergeParts(lowerIndex, middle, higherIndex);
}
}
private void mergeParts(int lowerIndex, int middle, int higherIndex) {
for (int i = lowerIndex; i <= higherIndex; i++) {
tempMergArr[i] = array[i];
}
int i = lowerIndex;
int j = middle + 1;
int k = lowerIndex;
while (i <= middle && j <= higherIndex) {
if (tempMergArr[i] <= tempMergArr[j]) {
array[k] = tempMergArr[i];
i++;
} else {
array[k] = tempMergArr[j];
j++;
count = count + (middle-i+1);
}
k++;
}
while (i <= middle) {
array[k] = tempMergArr[i];
k++;
i++;
}
}
}
This solution seems easiest to me since it is iterative instead of recursive and it is still o(nlogn):
Create new empty list sortedItems. Iterate from the back of the original list to the front. Insert the array item into the sortedItems list in SORTED ORDER. Then, the number of unordered pairs for that item will be (sortedItems.Length - 1) - P, where P is the position in the List where the sorted item was inserted. Add this to the total sum of unordered pairs. There are N items in the original list and each insertion costs log(n) so the total cost is Nlog(N)
Another idea is to first sort the array and its position, then compare the relative position change in the sorted array and position data from small to big value
struct Point{
int val,pos;
}point[N];
for(i=0;i<n;i++){
point[i].val = array[i];
point[i].pos = i;
}
sort(point,point+n,cmp);
int ans = 0;
int pos[N];
for(i=0;i<n;i++){
x = point[i].pos
while(x < i){point[i].pos = pos[x];x=pos[x];}
ans += point[i].pos-i;
pos[i] = point[i].pos
}
Illustration:
[3,2,4,1]
=> [(3,0),(2,1),(4,2),(1,3)]
sort: [(1,3),(2,1),(3,0),(4,2)]
Check (1,3), as it is smallest, when it move from previous position to current, the unordered pair has reduced pre.pos-cur.pos, that is 3-0=3
After doing this, we update the left as
[(1,3)(2,1),(3,0),(4,2)]
Since unordered pairs has been calculated for (1,3), we would not include this in the following calculation, so we have to update the one whose position is 0 to element 0 's original position. So (3,0) should be updated to (3,3) since element 0's original position is 3
The new array would be sorted from pos 1 and the postion value would also be ranged from 1 to n-1
So we do similar actions as before
[(1,3)(2,1),(3,3),(4,2)]
divide array into two.
lets say k is end of first half and k+1 is begining of second
find kth largest element and k+1th largest element via quickselect - O(n)
count number of elements bigger than kth in first half and smaller than k+1th in the second - O(n)
multiply them.
Do same thing for each half recursively and add up those products along the way.
Total complexit O(n log n )
To expand on Anonymous on November 02, 2014's idea:
def unordered_pairs(L):
if len(L) == 1:
return L, []
left_sorted, left_pairs = unordered_pairs(L[:len(L)/2])
right_sorted, right_pairs = unordered_pairs(L[len(L)/2:])
pairs = left_pairs + right_pairs
result = []
while left_sorted and right_sorted:
if left_sorted[0] > right_sorted[0]:
item = right_sorted.pop(0)
for j in left_sorted:
pairs.append((j,item))
result.append(item)
else:
result.append(left_sorted.pop(0))
result += left_sorted + right_sorted
return result, pairs
L = [3, 2, 1]
L_sorted, pairs = unordered_pairs(L)
print L, "has", len(pairs), "pairs:", pairs
//Number of inversions problem implementation 0(NlogN)
//Modified mergesort.
//Preallocating temp buffer same size as data.
int InvNum(int *pdata, int *ptemp, int s, int e)
{
if (s == e)
return 0;
int mid = (s + e) / 2;
int inv = InvNum(pdata, ptemp, s, mid);
inv += InvNum(pdata, ptemp, mid+1, e);
int ileft = s, iright = mid+1, itemp = 0, inv_merge = 0;
while (ileft <= mid && iright <= e)
{
if (pdata[ileft] <= pdata[iright])
{
ptemp[itemp++]=pdata[ileft++];
inv+=inv_merge;
}
else
{
ptemp[itemp++]=pdata[iright++];
inv_merge++;
}
}
while (iright <= e)
{
ptemp[itemp++]=pdata[iright++];
inv_merge++;
}
while (ileft <= mid)
{
ptemp[itemp++]=pdata[ileft++];
inv+=inv_merge;
}
copy(ptemp, ptemp+itemp, pdata+s);
return inv;
}
Java Implementation.
import java.util.*;
public class NumberOfUnsortedPairs{
public int getNumberOfUnsortedPairs(int[] array) {
int res = 0;
if (array == null || array.length == 0) {
return res;
}
MyClass[] myClassArray = new MyClass[array.length];
for (int i = 0; i < array.length; i++) {
myClassArray[i] = new MyClass(array[i]);
}
mergeSort(myClassArray, 0, array.length - 1);
for (MyClass myClass : myClassArray) {
res += myClass.numOfElementSmallerBehindMe;
}
return res;
}
private void mergeSort(MyClass[] myClassArray, int start, int end) {
if (start == end) {
return;
}
int mid = start + (end - start)/2;
mergeSort(myClassArray, start, mid);
mergeSort(myClassArray, mid + 1, end);
merge(myClassArray, start, mid, end);
}
private void merge(MyClass[] myClassArray, int start, int mid, int end) {
MyClass[] left = new MyClass[mid - start + 2];
MyClass[] right = new MyClass[end - mid + 1];
for (int i = 0; i < left.length - 1; i++) {
left[i] = myClassArray[start + i];
}
for (int i = 0; i < right.length - 1; i++) {
right[i] = myClassArray[mid + 1 + i];
}
left[left.length - 1] = new MyClass(Integer.MAX_VALUE);
right[right.length - 1] = new MyClass(Integer.MAX_VALUE);
int leftIndex = 0;
int rightIndex = 0;
int i = start;
int bigerSum = 0;
for (i = start; i <= end; i++) {
if (left[leftIndex].val < right[rightIndex].val) {
myClassArray[i] = left[leftIndex];
myClassArray[i].numOfElementSmallerBehindMe += bigerSum;
leftIndex++;
} else {
bigerSum++;
myClassArray[i] = right[rightIndex];
rightIndex++;
}
}
}
public static void main(String[] args) {
NumberOfUnsortedPairs code = new NumberOfUnsortedPairs();
int[] array = {2, 1, 3};
System.out.println(code.getNumberOfUnsortedPairs(array));
int[] array1 = {3, 2, 1};
System.out.println(code.getNumberOfUnsortedPairs(array1));
}
}
class MyClass{
int val;
int numOfElementSmallerBehindMe = 0;
public MyClass(int val) {
this.val = val;
}
}
You can do this with a modified merge sort.
- Anonymous November 02, 2014Say you have [3,2,4,1]
You compare [3] vs. [2] and [4] vs. [1]
then you order to get
x = [2,3] vs. y= [1,4]
Now you know when u merge one integer at a time (in this case you add from y first), the fact that you added it to the merged array means that every integer in the other array that has not been visited must be bigger than it, but it comes before it so it is an unordered pair.
So when you add 1 to the merged array, you can see that 2 and 3 in the x array will be bigger but comes before it so they are unordered pairs.
This is the basic idea