Deshaw Inc Interview Question
Applications DevelopersCountry: India
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).
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]);
}
}
}
}
}
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).
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;
}
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;
}
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;
}
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;
}
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]);
}
}
}
}
}
}
}
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));
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.
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.
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.
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]);
}
}
}
}
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)
- sreejrocks December 30, 2015