## 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.

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 ..

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

Wat u mean by inversion?

Comment hidden because of low score. Click to expand.
0

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>

Comment hidden because of low score. Click to expand.
0

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

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;
}``````

Comment hidden because of low score. Click to expand.
0

This code gives a wrong answer!!

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;

{
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()
{
merge_sort(numbers, 0, MAXN-1);
cout<<result<<endl;

return 0;
}

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;

{
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()
{
merge_sort(numbers, 0, MAXN-1);
cout<<result<<endl;

return 0;
}

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

All the above codes are wrong.

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

3

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

*/
#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)
{
*/
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++;
}

}

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.

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.

### 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.