Deshaw Inc Interview Question for Applications Developers


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[0]);
    cout << "Inversion Count : " << getInvCount(arr, n);
    return 0;
}

- sreejrocks December 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- zr.roman December 31, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

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

- zr.roman December 31, 2015 | Flag
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]);
							
						}
					}
				}
			}
		}

- Soraya December 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- tihor December 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- gen-x-s December 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Check out solution of Darkhan.Imangaliev.

- tihor December 31, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

outputArray[0] = inputArray[0];

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

- Anonymous December 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- tihor December 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

outputArray[0] = inputArray[0];

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

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

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

outputArray[0] = inputArray[0];

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

- Raj December 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

outputArray[0] = inputArray[0];

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

- Raj December 29, 2015 | Flag Reply
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]);
}
}
}
}
}

}

}

- pradeep kumar R S December 30, 2015 | Flag Reply
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[0].set(a[i], 1);
  bit[1].set(a[i], bit[0].sum(a[i] + 1, MAXN - 1);
  bit[2].set(a[i], bit[1].sum(a[i] + 1, MAXN - 1);
}

System.out.println(bit[2].sum(0, MAXN - 1));

- Darkhan.Imangaliev December 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Pc December 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you provide more explanation please? or an examle

- mehraz December 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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).
please, provide a runnable solution.

- zr.roman December 31, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- zr.roman December 31, 2015 | Flag
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) {
                    mediums.add(input[j]);
                }

            }
        }
    }

- gtitorobe December 31, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this is O(n^3).

- zr.roman December 31, 2015 | Flag
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[0])

	temp = nums[0]
	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)

- tan January 13, 2016 | 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