## Deshaw Inc Interview Question for Applications Developers

• 2

Country: India

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

Find all the numbers greater than a[i] whose index is less than i, find all the numbers which are smaller than a[i] and index is more than i. We multiply the number of elements greater than a[i] to the number of elements smaller than a[i] and add it to the result.
Complexity: O(n^2)

``````#include<bits/stdc++.h>
using namespace std;

// Returns count of inversions of size 3
int getInvCount(int arr[], int n)
{
int invcount = 0;  // Initialize result

for (int i=1; i<n-1; i++)
{
// Count all smaller elements on right of arr[i]
int small = 0;
for (int j=i+1; j<n; j++)
if (arr[i] > arr[j])
small++;

// Count all greater elements on left of arr[i]
int great = 0;
for (int j=i-1; j>=0; j--)
if (arr[i] < arr[j])
great++;

// Update inversion count by adding all inversions
// that have arr[i] as middle of three elements
invcount += great*small;
}

return invcount;
}

// Driver program to test above function
int main()
{
int arr[] = {8, 4, 2, 1};
int n = sizeof(arr)/sizeof(arr);
cout << "Inversion Count : " << getInvCount(arr, n);
return 0;
}``````

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

O(n^2) is optimal for such task.

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

actually, O(nlogn) is possible.
Here (/question?id=5631660689195008) is a O(nlogn) solution for creating a new array as follows: how many elements are greater than that element remaining in the array.
So, we can apply this approach twice:
1) get first array containing values: how many previous elements are greater than each element in the initial array.
2) get second array containing values: how many remaining elements are smaller than each element in the initial array.

Then do 1 pass through the 2 new arrays simultaneously, multiplying the values to calculate count of inversions.

The complexity will be O(n logn).

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

``````int []arr={23,10,24,7,12,19};
int count=0;

for(int i=0; i<arr.length;i++){
for(int j=i+1; j<arr.length;j++){
if(arr[j] < arr[i]){
for(int k=j+1; k<arr.length;k++){
if(arr[k]<arr[j]){
count++;
sb.append(arr[i]);
sb.append(arr[j]);
sb.append(arr[k]);

}
}
}
}
}``````

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

This is O(n^3). Can we do it in better than O(n^2)?

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

tihor (?) the number of inversions is O(n^3) so that is the best answer . For example, in a descending sequence every set of 3 elements are an inversion, and there are C(3, n) sets which is O(n^3).

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

Check out solution of Darkhan.Imangaliev.

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

public static int[] InversionsArray(int[] inputArray)
{
int[] outputArray = new int;

outputArray = inputArray;

int outputArrayPtr = 0;

for (int i = 1; i < inputArray.Length; i++)
{
if (outputArray[outputArrayPtr] > inputArray[i])
outputArray[++outputArrayPtr] = inputArray[i];

if (outputArrayPtr >= 2)
break;
}

return outputArray;
}

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

It will fail in this condition: 30 1 12 19 5

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

public static int[] InversionsArray(int[] inputArray)
{
int[] outputArray = new int;

outputArray = inputArray;

int outputArrayPtr = 0;

for (int i = 1; i < inputArray.Length; i++)
{
if (outputArray[outputArrayPtr] > inputArray[i])
outputArray[++outputArrayPtr] = inputArray[i];

if (outputArrayPtr >= 2)
break;
}

return outputArray;
}

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

public static int[] InversionsArray(int[] inputArray)
{
int[] outputArray = new int;

outputArray = inputArray;

int outputArrayPtr = 0;

for (int i = 1; i < inputArray.Length; i++)
{
if (outputArray[outputArrayPtr] > inputArray[i])
outputArray[++outputArrayPtr] = inputArray[i];

if (outputArrayPtr >= 2)
break;
}

return outputArray;
}

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

public static int[] InversionsArray(int[] inputArray)
{
int[] outputArray = new int;

outputArray = inputArray;

int outputArrayPtr = 0;

for (int i = 1; i < inputArray.Length; i++)
{
if (outputArray[outputArrayPtr] > inputArray[i])
outputArray[++outputArrayPtr] = inputArray[i];

if (outputArrayPtr >= 2)
break;
}

return outputArray;
}

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

import java.util.Scanner;

public class inversionOfSize3 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int max = sc.nextInt();
int[] array = new int[max];
for (int i = 0; i < max; i++) {
array[i] = sc.nextInt();
}
for (int i = 0; i < max - 2; i++) {
for (int j = i + 1; j < max - 1; j++) {
if (array[i] > array[j]) {
for (int k = j + 1; k < max; k++) {
if (array[j] > array[k]) {
System.out.println(array[i]+" "+array[j]+" "+array[k]);
}
}
}
}
}

}

}

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

This can be solved with Binary Indexed Tree in O(nlogn) complexity with O(n) memory. We also have to compress elements in array

``````for(int i = 0; i < n; ++i){
bit.set(a[i], 1);
bit.set(a[i], bit.sum(a[i] + 1, MAXN - 1);
bit.set(a[i], bit.sum(a[i] + 1, MAXN - 1);
}

System.out.println(bit.sum(0, MAXN - 1));``````

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

Why not just use binary tree as an array and traverse the right children. (n) for building, (2n) of extra memory and (log n) for getting all inversions.

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

can you provide more explanation please? or an examle

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

this is not a solution, this is a buggy sketch.
What is "bit" here, what is MAXN? (I don't mention 2 missing parentheses, ok).

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

looks like, it is O(n^2) solution, because each time we insert element in the bit structure, we have to recalculate at most n-2 existing elements in worst case (quite rare case, but still). In best case we have to recalculate 0 elements. So, average running time is (n-2)/2 per each iteration. For the whole solution average running time is n*(n-2)/2.
Asymptotic complexity is O(n^2).
This is not just a running total, as it is described on wikipedia.
The task is of much more complicated (combinatorial) logic.

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

I think this is O(n2)

``````public static void main(String[] args) {

int[] input = new int[]{23, 10, 24, 7, 12, 1, 19};

List<Integer> mediums;

for (int i = 0; i < input.length - 2; i++) {
mediums = new ArrayList<>();
int base = input[i];
for (int j = i + 1; j < input.length; j++) {
if (!mediums.isEmpty()) {
for (Integer medium : mediums) {
if (input[j] < medium) {
System.out.println(base+ " " +medium + " "+input[j] );
}
}
}

if (input[j] < base) {
}

}
}
}``````

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

this is O(n^3).

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

``````def testing(nums):
length = len(nums)
new_nums = []

new_nums.append(nums)

temp = nums
for x in range(1, length-1):
if(x+1) <= length-1:
if(nums[x] < temp):
temp = nums[x]
new_nums.append(nums[x])
x+=1
else:
x+=1
print new_nums

nums = [9,10,24,7,12,19]
testing(nums)``````

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.