Interview Question


Country: India




Comment hidden because of low score. Click to expand.
1
of 1 vote

Hint:
Try modifying merge sort's merge procedure, to keep track of the count.

- mrb March 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Use merge sort.. count inversions when you put element from right array to left ..

- yogeshhan March 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Wat u mean by inversion?

- Anonymous March 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I guess it means an anomaly in ordering.
e.g 2,7,5,6,9,8
For increasing order, there are two inversions <7,5> and <9,8>

- Learner March 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

<7 5> <9 8> and then <6 7>
I think the answeer should be 3.

- Anonymous May 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Following code wil give the number of inversions in a sequence of n mumbers

#include<iostream>
#include<iomanip>
using namespace std;
long long int mergeArrays(int arr[],int beg,int mid,int end)
{
	int i,j,*temp,k=0,p=0;
	long long int count=0;
	temp=new int[end-beg+1];
	i=beg;j=mid+1;
	while(i<=mid && j<=end){
		while(j<=end && arr[i] > arr[j]){temp[k++]=arr[j++];++p;}
		count+=p;
		temp[k++]=arr[i++];
	}
	while(j<=end){
		temp[k++]=arr[j++];
	}
	while(i<=mid){	temp[k++]=arr[i++]; count+=(end-mid);}
	for(i=0;i<k;i++)	arr[beg+i]=temp[i];
return count;
}

long long int countInversion(int arr[],int beg,int end){
	int mid;
	long long int noi=0;
	if(beg<end){
		mid=(beg+end)/2;
		noi=countInversion(arr,beg,mid);
		noi+=countInversion(arr,mid+1,end);
		noi+=mergeArrays(arr,beg,mid,end);
	}
	return noi;
}
int main()
{
	int i, a[100000];
	for(i=0;i<100000;i++)	cin>>a[i];
	cout<<countInversion(a,0,99999)<<endl;

return 0;
}

- gautam jha March 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This code gives a wrong answer!!

- Ashu March 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <iomanip>
#include <stdio.h>

using namespace std;

const int MAXN = 100000;
int numbers[MAXN];
long result;

//read the file to numbers
void num_read()
{
freopen("integerArray.txt","r",stdin);
for (int i=0;i<MAXN;i++)
cin >> numbers[i];
}

//merge fuction
void merge(int* input, int low, int high)
{
int mid = ((low + high) / 2);
int i = 0;
int left = low;
int right = mid + 1;

// Temp array
int t=high - low + 1;
int temp[t];


while(left <= mid && right <= high)
{
if(input[left] < input[right])
temp[i++] = input[left++];
else
{
temp[i++] = input[right++];
result += (mid - left + 1);
}
}

while(left <= mid)
temp[i++] = input[left++];

while(right <= high)
temp[i++] = input[right++];

for(i = low; i < high + 1; ++i)
input[i] = temp[i - low];

}


//merge sort function
void merge_sort(int* input, int low, int high)
{
if ( low < high )
{
int mid = ((low + high) / 2);
merge_sort(input, low, mid);
merge_sort(input, mid + 1, high);
merge(input, low, high);
}

}


int main()
{
num_read();
merge_sort(numbers, 0, MAXN-1);
cout<<result<<endl;

return 0;
}

- Anonymous April 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <iomanip>
#include <stdio.h>

using namespace std;

const int MAXN = 100000;
int numbers[MAXN];
long result;

//read the file to numbers
void num_read()
{
freopen("integerArray.txt","r",stdin);
for (int i=0;i<MAXN;i++)
cin >> numbers[i];
}

//merge fuction
void merge(int* input, int low, int high)
{
int mid = ((low + high) / 2);
int i = 0;
int left = low;
int right = mid + 1;

// Temp array
int t=high - low + 1;
int temp[t];


while(left <= mid && right <= high)
{
if(input[left] < input[right])
temp[i++] = input[left++];
else
{
temp[i++] = input[right++];
result += (mid - left + 1);
}
}

while(left <= mid)
temp[i++] = input[left++];

while(right <= high)
temp[i++] = input[right++];

for(i = low; i < high + 1; ++i)
input[i] = temp[i - low];

}


//merge sort function
void merge_sort(int* input, int low, int high)
{
if ( low < high )
{
int mid = ((low + high) / 2);
merge_sort(input, low, mid);
merge_sort(input, mid + 1, high);
merge(input, low, high);
}

}


int main()
{
num_read();
merge_sort(numbers, 0, MAXN-1);
cout<<result<<endl;

return 0;
}

- Kiran BIliyawala April 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

All the above codes are wrong.

- Anonymous February 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

3

- Anonymous October 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/* Include Header Files
*/
#include "stdio.h"
#include "stdlib.h"

/* Include Pre-processor directives
*/
#define N 100000

/* Function Proto-type
*/
void partition(long int *data, int first, int last);
void merge(long int *data, int first, int mid, int last);

/* Global Variable
*/
unsigned int counter = 0;

int main()
{
/* Declaring and initializing variables
*/
long int data[N] = {0};
int multiplying_factor = 10;
char c = '\0';
char d = 0;
long int sum = 0;
int indexcount = 0;

/* FILE READ OPERATION, USER CAN USE THEIR OWN FILE OPERATION
* IF NEEDED OR FOR SMALL ARRAY SIZE INITIALIZE THE VALUE
* OF ARRAY DURING DECLARATION
*/
/* Open file in directory
*/
FILE *fp = fopen("F:/IntegerArray.txt", "r");


/* Read till end of file
*/
while (c != EOF)
{
/* Reading file by character
*/
c = fgetc(fp);

if (c != '\n')
{
d = atoi(&c);

sum = (sum * multiplying_factor) + d;
}
else
{
/* Filling data in array
*/
data[indexcount] = sum;
indexcount = indexcount + 1;
sum = 0;
}
}

fclose(fp);

partition(data, 0, N - 1);

printf("\nCounter = %u \n", counter);

return 0;
}


void partition(long int *data, int left, int right)
{
int middle = (left + right) / 2;

if (left < right)
{
partition(data, left, middle);
partition(data, middle + 1, right);
merge(data, left, middle, right);
}

}

void merge(long int *data, int left, int middle, int right)
{
/* Declaring and initializing variables
*/
int Nleft = middle - left + 1;
int Nright = right - middle;
long int left_data[N] = {0};
long int right_data[N] = {0};
int index = 0;
int index_l = 0;
int index_r = 0;

/* Initialize left_data array
*/
for(index = 0; index < Nleft; index++)
{
left_data[index] = data[left + index];
}
/* Initialize right_data array
*/
for (index = 0; index < Nright; index++)
{
right_data[index] = data[middle + 1 + index];
}

index = left;

while (index_l < Nleft && index_r < Nright)
{
if (left_data[index_l] < right_data[index_r])
{
data[index] = left_data[index_l];
index_l++;

}
else
{
data[index] = right_data[index_r];
index_r++;

/* Updating counter
*/
counter = counter + (Nleft - index_l);
}

index++;
}

while(index_l < Nleft)
{
data[index] = left_data[index_l];
index++;
index_l++;
}

while(index_r < Nright)
{
data[index] = right_data[index_r];
index++;
index_r++;
}


}

- Azeemali Hashmani November 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Surely this can be done in O(n) time by looking at each line, and counting the number of cases where the line number != value on that line.
The number of inversions is half this number.

- Anonymous March 12, 2012 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More