Amazon Interview Question Senior Software Development Engineers
Country: United States
how what merge sort concept-
let 3 arrays are - A,B,C
take x from A[i] then look for y in B[j] such that y >x then for all j <len(B) B[j] >x
then look for z in C ,such that C[k] >y then for all k < len(C) C[k] >y
required pair{ x,B[j],C[k] to C[end]}
Optimal time for finding y in B - is binary search -> log (len(B)).
similary for k in C using binary search-->>>>>>>> log(len(C)).
time complexity (len(A) * log(lenB) * log(lenC))
how what merge sort concept-
let 3 arrays are - A,B,C
take x from A[i] then look for y in B[j] such that y >x then for all j <len(B) B[j] >x
then look for z in C ,such that C[k] >y then for all k < len(C) C[k] >y
required pair{ x,B[j],C[k] to C[end]}
Optimal time for finding y in B - is binary search -> log (len(B)).
similary for k in C using binary search-->>>>>>>> log(len(C)).
time complexity (len(A) * log(lenB) * log(lenC))
how what merge sort concept-
let 3 arrays are - A,B,C
take x from A[i] then look for y in B[j] such that y >x then for all j <len(B) B[j] >x
then look for z in C ,such that C[k] >y then for all k < len(C) C[k] >y
required pair{ x,B[j],C[k] to C[end]}
Optimal time for finding y in B - is binary search -> log (len(B)).
similary for k in C using binary search-->>>>>>>> log(len(C)).
time complexity (len(A) * log(lenB) * log(lenC))
package whatever;
import java.io.*;
import java.util.Arrays;
class amazonSort {
public static void main (String[] args)
throws java.lang.Exception {
int[] arr1 = {5, 3, 15, 19, 6};
int[] arr2 = {24, 34, 11, 13, 16};
int[] arr3 = {91, 45, 57, 72, 100};
Arrays.sort(arr1);
Arrays.sort(arr2);
Arrays.sort(arr3);
int x = findPossibilityCount (arr1, arr2, arr3);
System.out.println("Number of possibilities of sequence [x < y < z] is " + x);
}
private static int smallestNumber (int[] anInput) {
int smallest = anInput[0];
for (int i=1; i<anInput.length; i++) {
if (smallest > anInput[i])
smallest = anInput[i];
}
return smallest;
}
private static int findPossibilityCount (int[] arr1, int[] arr2, int[] arr3) {
int smallestArr2 = smallestNumber(arr2);
int smallestArr3 = smallestNumber(arr3);
int counter1 = 0, counter2 = 0;
for (int i=0; i<arr1.length; i++) {
if (arr1[i] < smallestArr2)
counter1++;
else
break;
}
for (int i=0; i<arr2.length; i++) {
if (arr2[i] < smallestArr3)
counter2++;
else
break;
}
// System.out.println ("Counter 1 = " + counter1
// + " Counter 2 = " + counter2
// + " Size 3 = " + arr3.length);
return counter1 * counter2 * arr3.length;
}
}
I was thinking in terms of finding all solutions
After initially 'trimming' A, B & C:
for (int i = 0; i < rightIndexA; i++) {
for (int j = leftIndexB; j <= rightIndexB; j++) {
if (A[i] < B[j]) {
for (int k = leftIndexC; k < C.length; k++) {
if (B[j] < C[k]) {
System.out.println("solution: " + A[i] + " < " + B[j] + " < " + C[k]);
} else {
leftIndexC = k;
}
}
} else {
leftIndexB = j; // move left index to the right
}
}
}
/* package whatever; // don't place package name! */
import java.io.*;
import java.util.Arrays;
class amazonSort {
public static void main (String[] args)
throws java.lang.Exception {
// Prepare data set
int[] arr1 = {5, 3, 15, 19, 6};
int[] arr2 = {24, 34, 11, 13, 16};
int[] arr3 = {91, 45, 57, 72, 100};
Arrays.sort(arr1);
Arrays.sort(arr2);
Arrays.sort(arr3);
int x = findPossibilityCount (arr1, arr2, arr3);
System.out.println("Number of possibilities of sequence [x < y < z] is " + x);
}
private static int smallestNumber (int[] anInput) {
int smallest = anInput[0];
for (int i=1; i<anInput.length; i++) {
if (smallest > anInput[i])
smallest = anInput[i];
}
return smallest;
}
private static int findPossibilityCount (int[] arr1, int[] arr2, int[] arr3) {
int smallestArr2 = smallestNumber(arr2);
int smallestArr3 = smallestNumber(arr3);
int counter1 = 0, counter2 = 0;
for (int i=0; i<arr1.length; i++) {
if (arr1[i] < smallestArr2)
counter1++;
else
break;
}
for (int i=0; i<arr2.length; i++) {
if (arr2[i] < smallestArr3)
counter2++;
else
break;
}
// System.out.println ("Counter 1 = " + counter1
// + " Counter 2 = " + counter2
// + " Size 3 = " + arr3.length);
return counter1 * counter2 * arr3.length;
}
}
1. Start x from min in Arr1
2. Start z from max in Arr3
3. Find y values in Arr2 between x and z
To improve perf exclude values in Arr3 which are < x or > z from subsequent iterations
//C#
public static int ThreeArrayPatterns(int[] ar1, int[] ar2, int[] ar3)
{
int ar3LeftLimit = 0;
int ar2LeftLimit = 0;
int ar2RightLimit = ar2.Length - 1;
int count = 0;
for (int i = 0; i < ar1.Length; i++) //go from smallest to largest in ar1
{
for (int j = ar3.Length - 1; j >= ar3LeftLimit; j--) //go from largest to smallest in ar3
{
if (ar1[i] + 1 < ar3[j]) // there is room for x<y<z
{
//1. Find ar2[k] such that x<y
for (int k = ar2LeftLimit; k < ar2RightLimit; k++)
{
if (ar2[k] > ar1[i]) //x<y
{
if (ar2[k] < ar3[j])
{//x<y<z found
count++;
Console.WriteLine("{0},{1},{2}", ar1[i], ar2[k], ar3[j]);
}
else
{
ar2RightLimit = k;
break; //No matches further right
}
}
else
{ //x>=y
ar2LeftLimit = k;
}
}
}
if (ar2LeftLimit >= ar2RightLimit)
{
break;
}
}
if (ar2LeftLimit >= ar2RightLimit)
{
break;
}
}
return count;
}
public static void Test()
{
int[] arr1 = { 5, 3, 15, 19, 6 };
int[] arr2 = { 24, 34, 11, 13, 16 };
int[] arr3 = { 91, 45, 57, 72, 100 };
Array.Sort(arr1);
Array.Sort(arr2);
Array.Sort(arr3);
int count = ThreeArrayPatterns(arr1, arr2, arr3);
Console.WriteLine("Match Count = {0}", count.ToString());
}
I ended up with this:
int findLeft(int A[], int value, int lower, int upper);
'return the index i where value <= A[i], lower <= i <= upper'
A[], B[] and C[] are trimmed by using findLeft() & findRight() to obtain leftIndex & rightIndex prior to entering this block of code:
// arrays bounds ensure that A[i] < B[i] < C[i] so no additional compares are needed
int count = 0;
for (int i = leftIndexA; i <= rightIndexA; i++) {
leftIndexB = findLeft(B, A[i], leftIndexB, rightIndexB);
for (int j = leftIndexB; j <= rightIndexB; j++) {
leftIndexC = findLeft(C, B[j], leftIndexC, rightIndexC);
count += (rightIndexC - leftIndexC + 1);
}
}
// sort arr1, arr2 and arr3
// arrays bounds ensure that A[i] < B[i] < C[i]
int[] arr1 = {3};
int[] arr2 = {11, 13, 16};
int[] arr3 = {45};
int count = 0,a=0, b=0;
while(a < 5){
for (int i = a; i <5 ; i++ ) {
while(b < 5){
for (int j = b; j < 5; j++) {
if( arr1[i]<arr2[j]){
for (int k= 0; k < 5; k++) {
if( arr2[j]<arr3[k]){
count ++;
}
}
}
}
b++;
}
}
a++;
}
cout<<"count value :"<<count;
//sort the arr1, arr2 , arr3
// arrays bounds ensure that A[i] < B[i] < C[i]
int[] arr1 = {3};
int[] arr2 = {11, 13, 16};
int[] arr3 = {45};
int count = 0,a=0, b=0;
while(a < 5){
for (int i = a; i <5 ; i++ ) {
while(b < 5){
for (int j = b; j < 5; j++) {
if( arr1[i]<arr2[j]){
for (int k= 0; k < 5; k++) {
if( arr2[j]<arr3[k]){
count ++;
}
}
}
}
b++;
}
}
a++;
}
cout<<"count value :"<<count;
What if we use a balanced binary tree with Left<Root<Right and start comparing in groups, i.e. first tree's left most child to 2nd tree's left most child, + first tree's right most child to second tree's right most child, and continuing further.
The idea is to combine the elements, so that we dont perform check on every element but on a set of elements created using binary tree.
When this condition is not met, we could use back tracking to find out what will be the next set of elements
let me know your thoughts
iterate each elements from Array2 and find out last index of Array1 which smaller than y (found x) and find out First index of Array3 which is greater than y (found z).. Also increment index of Array2 upto z .. We get count1*count2*count3 .. do same for next element of Array2 ..
Complexity - log(n2)*log(n1)*log(n3)..
There's a simpler way. In its simplest form (where the arrays don't have any overlaps), total possibilitites = # subsets from 1 * # subsets from 2 * # subsets from 3
If there are no overlaps between the sorted arrays, the solution is O(1).
When I say # of subsets, it excludes the empty set. It now becomes a problem of figuring out various possibilities of start and end in each array based on how interleaved the arrays are.
/*
logic
1. Identify the first, second and third array of the input from the current pointer of each
2. All current elements make one combination
3. if the next in first is smaller the current second, call method with next pointer in first
double count the output of the method call. One with current element and one skipping it
4. Repeat 3 for second against third
5. Increment the current pointers of all and call the method again
6. Return the sum of all outputs
*/
private static int sequences(int[] a, int[] b, int[] c, int i, int j, int k){
if(i >= a.length || j >= b.length || k >= c.length) return 0;
//there can be a better way to find the first, second and third array in current selection
int[] first, second, third;
int f,s,t;
if(a[i] < b[j] && a[i] < c[k]){
first = a; f = i;
second = b[j] < c[k] ? b : c; s = b[j] < c[k] ? j : k;
third = b[j] < c[k] ? c : b; t = b[j] < c[k] ? k: j;
} else if(a[i] > b[j] && a[i] > c[k]){
third = a; t = i;
first = b[j] < c[k] ? b : c; f = b[j] < c[k] ? j : k;
second = b[j] < c[k] ? c : b; s = b[j] < c[k] ? k : j;
} else {
second = a; s = i;
first = b[j] < c[k] ? b : c; f = b[j] < c[k] ? j : k;
third = b[j] < c[k] ? c : b; t = b[j] < c[k] ? k : j;
}
int count = 1;// current elements combination
System.out.println(first[f]+" "+second[s]+" "+third[t]);
if (f < first.length-1 && first[f+1] < second[s]){
// count two times. 1 including the current element and one skipping it
count += 2*sequences(first, second, third, f+1, s, t);
}
if (s < second.length-1 && second[s+1] < third[t]){
count+= 2*sequences(first, second, third, f, s+1, t);
}
return count + sequences(first, second, third, f+1, s+1, t+1);
}
public static void main(String[] args){
int val = sequences(new int[] {3},
new int[] {11, 13, 16},
new int[] {45},
0, 0, 0);
System.out.println(val);
}
public class ThreeArray {
public void run(int[][] arrays) {
for (int i = 0; i < arrays.length; i++) {
Arrays.sort(arrays[i]);
}
print(arrays, 0, 0, new LinkedList<>());
}
public void print(int[][] arrays, int indexArray, int index, LinkedList<Integer> list) {
int[] array = arrays[indexArray];
if (index >= array.length) {
return;
}
for (int i = index; i < array.length; i++) {
int value = array[i];
if (list.isEmpty() || value > list.getLast()) {
list.add(value);
if (indexArray >= arrays.length - 1) {
printArray(list);
} else {
print(arrays, indexArray + 1, 0, list);
}
print(arrays, indexArray, index + 1, list);
list.removeLast();
}
}
}
private void printArray(List<Integer> list) {
int size = list.size();
System.out.print("(");
for (int i = 0; i < size; i++) {
System.out.print(list.get(i));
if (i + 1 < size) {
System.out.print(",");
}
}
System.out.println(")");
}
}
public class ThreeArrayTest {
private ThreeArray threeArray = new ThreeArray();
@Before
public void setup() {
threeArray = new ThreeArray();
}
@Test
public void test() {
threeArray.run(new int[][]{{3}, {11, 13, 16}, {45}});
}}
A Java solution I thought of...
package com.careercup.amazonchallenge;
import java.io.*;
import java.util.Arrays;
class amazonSort {
public static void main (String[] args)
throws java.lang.Exception {
// Form input data set, can be replaced by JUnit
int[] arr1 = {5, 3, 15, 19, 6};
int[] arr2 = {24, 34, 11, 13, 16};
int[] arr3 = {91, 45, 57, 72, 100};
Arrays.sort(arr1);
Arrays.sort(arr2);
Arrays.sort(arr3);
int x = findPossibilityCount (arr1, arr2, arr3);
System.out.println("Number of possibilities of sequence [x < y < z] is " + x);
}
private static int smallestNumber (int[] anInput) {
int smallest = anInput[0];
for (int i=1; i<anInput.length; i++) {
if (smallest > anInput[i])
smallest = anInput[i];
}
return smallest;
}
private static int findPossibilityCount (int[] arr1, int[] arr2, int[] arr3) {
int smallestArr2 = smallestNumber(arr2);
int smallestArr3 = smallestNumber(arr3);
int counter1 = 0, counter2 = 0;
for (int i=0; i<arr1.length; i++) {
if (arr1[i] < smallestArr2)
counter1++;
else
break;
}
for (int i=0; i<arr2.length; i++) {
if (arr2[i] < smallestArr3)
counter2++;
else
break;
}
// System.out.println ("Counter 1 = " + counter1
// + " Counter 2 = " + counter2
// + " Size 3 = " + arr3.length);
return counter1 * counter2 * arr3.length;
}
}
At the least, one could 'trim' the arrays based on min/max of the other arrays, meaning putting better bounds on the n^3 loops (instead of 0 to A.length-1).
- DaveO February 26, 2017