Amazon Interview Question for SDETs

• 3

Country: India

Comment hidden because of low score. Click to expand.
4
of 14 vote

``````for(int i=0;i<a.length;i++)
{
for(int j=i+1;j<b.length;j++)
{if(a[i]>b[j])
System.out.println(i +"," +j);
}
}``````

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

it's correct, but requires O(n^2) time.. they might be expecting O(n)

Comment hidden because of low score. Click to expand.
-1
of 1 vote

This is obvious. Something better ?

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

I don't think you can get better than O(n^2) since there are O(n^2) pairs, and if you wan't to process them all in some way (print, append to vector etc) you're going to have to do O(n^2) prints, appends, whatever.

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

Not sure why this got downvoted. As anon above me said, you have O(n^2) solution, so how can you find a O(n) solution?...

A more interesting problem might be return the number of pairs given these contraints

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

yes, it requires O(n^2) time..

int a[] = {5, 4, 3, 2, 1};

in this case need to print all possible 10 pairs, so O(n^2)..

in O(n) time can find a pair a[i] > a[j] and j-i is max

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

> Not sure why this got downvoted
Upvote it :) After all, this asymptotically optimal solution written in a simple form.

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

A = 20, 19, 18, 17 ,16
B= 1 , 2 , 3 , 4 ,5

for each i < j, there is a pair
so, there will be O(N^2) possible pair and so complexity.

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

While it's true that this is asymptotically optimal if the number of pairs returned is as large as it can be, a more interesting way to solve the problem might be to give an algorithm that runs in, say, O(n log n + r), where r is the number of results.

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

How would it be more interesting to solve the problem in O(nlogn + r)? r = n^2 so you are pretty much asking to solve this in nlogn + n^2 as opposed to n^2, both of which is O(n^2) except what you suggest is slightly worse than the solution we are commenting on.

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

> How would it be more interesting to solve the problem in O(nlogn + r)?
This makes perfect sense. There's a special term in CS for this, google for "Output-sensitive algorithm".

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

Oh I get it what he meant. Thanks

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

I think a suitable approach could be using a Binary Search Tree for the elements of B that have an index j>i.
We iterate from i=A.length-1 to 0 and keep updating the BST at each iteration by adding 1 element B[j] with j=i+1 (add an element to a BST costs O(logn)). Complexity O(nlogn)
If you have the pairs:
(1,2)(1,3)(1,4)(1,7)
you can retrieve them as:
(1,(2,3,4,7))
and you won't loss any information;
with my algorithm for each i you should go down the BST built with the elements of B[] with index j > i, and associate that i with the sublist of the elements already present in the BST that are smaller of A[i].
so:

``````Build a Binary Search Tree of the elements of the array B with index j>A.length.
for each i from A.length-1 to 0; O(n)
- add the element B[i+1] (if exists) to the BST; O(logn)
- go down the BST (that holds the elements of B[] with index j>i) and find which should be the position of A[i] in the BST O(logn)
- associate i with the sublist of smaller elements in the BST.``````

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

Usage of BSTs is possible, but it won't yield solution better than O(N^2)

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Adding an element to a BST is O(n) complexity and not O(log n).

Consider a binary tree with 3 elements {6,7,9). Now imagine you add 10 to it, starting from the root you will need to iterate through all the elements, in other words the height of the tree would also happen to be 'n' in case you have sorted elements in your array.

So, even for the BST solution you proposed the complexity would be O(n^2)

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

I'm pretty sure that adding an element to a BST is O(logn), such as searching for an element or deleting it. The cost of those operations on a BST is proportional to the height of the BST. The height of a BST is log(n). The worst case is present only if the height of the BST is n, that is a completely unbalanced tree. But in this case the tree behave like a linked list, and is called a degenerate tree.

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

How do you figure that the tree behaves like a linked list and is infact a degenerate tree?
Consider a scenario where Array B is a sorted array in the increasing order. This would lead us to a completely unbalanced BST.
In such a situation the height of the tree = the number of nodes and add and search operations would both be O(n).
Your solution would no doubt be a good one to discuss with the interviewer, but the worst case time complexity would still be O(n^2)

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

Therefore you recognize that this has O(nlogn) complexity and a worst case of O(n^2), that is definitely better than an algorithm that has a complexity of O(n^2) in the average and worst case. Example given: the quick sort algorithm has an average compexity of O(nlogn) and a worst case of O(n^2), and is definitely better than bubble sort that is O(n^2) in both average and worst case...

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

Saying O(something) itself means worst case complexity.

You can argue that your approach has a better average complexity than O(n^2), but average complexity is not denoted by 'O'.

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

Sorry, I still do not agree...to describe the complexity of an algorithm you can use both average and worst case complexity, both described by the Big O notation. Again take into account QuickSort that is a well known algorithm, and has an average case performance of O(nlogn) and a worst case performance of O(n^2). And it is always presented as one of the best perfoming sorting algorithms, often with better performance than MergeSort that has a complexity of O(nlogn) in both average and worst case.

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

In practice QuickSort is usually implemented with random median selection and with optimizations like dutch-flag partitioning. That makes algorithm *expected* time complexity O(NLogN) regardless of the input!
You won't be able to construct anything like this for the problem we are discussing.

Even unmodified quicksort works well with random input. It has average complexity O(NlogN). For the problem we are discussing - no algorithm will work great with random input since in our case expected number of pairs in a random input will be O(N^2).

So this is fundamentally O(N^2) problem. The only thing you can do you is to optimize special cases where expected number of pairs is asymptotically lower than O(N^2).

Alternatively, you can cross the line and apply various form of cheating - see the idea of O(1) "algorithm" described in comments.

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

If you have the pairs:
(1,2)(1,3)(1,4)(1,7)
you can retrieve them as:
(1,(2,3,4,7))
and you won't loss any information;
with my algorithm for each i you should go down the BST built with the elements of B[] with index j > i, and associate that i with the sublist of the elements already present in the BST that are smaller of A[i].
so:

``````for each i from A.length-1 to 0; O(n)
- add the element B[i+1] (if exists) to the BST; O(logn)
- go down the BST (that holds the elements of B[] with index j>i) and find which should be the position of A[i] in the BST O(logn)
- associate i with the sublist of smaller elements.``````

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

Think dynamically ...supose we have a array a1,a2,a3,a4...an.Now divide this into two parts(a1 to an-1) and an.Now comparing the max of second part with min of first part of b that is (b1,b2,tobn-1) will give us valid result (adjust invarient case when n>m).Now recurse using n iteration. Now sub problem is finding the max of subpart of a and min of sub part of b. efficiently. I think you know the answer use priority queue.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

some idiot down voted my generous and very correct explanation :(

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

There *is* a way we can talk about a worst-case bound here while making apparent the O(NlogN) nature of this solution. We can say it is O(NlogN + R), where R is the size of the result set. That is a worst-case bound if we use a self-balancing BST, which guarantees O(logN) per lookup in the worst case.

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

@teli: standard BST implementations actually do have a worst-case of O(logN), so while many of your points were good, I can see why someone would downvote that particular comment (though it wasn't me). These BST implementations use tree rebalancing techniques to provide these worst-case guarantees.

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

Let's try not to use the word "idiot" around here because there may be aspects you're not considering, or even when someone's wrong they may just be confused or uninformed :)

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Relax dude.. I wasn't saying it was you. But a possible BST in this scenario has worst case O(n) is correct and is what I stand by.
If you have your implementation to include rebalancing then you are right in you own way :)

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

The problem is basically counting number of inversions in an array.
Use modified merge sort.
1.combine A and B arrays into C.
2.label each element in C with either A or B.
3.Count number of inversion pairs using merge sort.
4. For each inversion pair , reject if label(i) == label(j)

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

I voted you up, then I voted you down.

Your solution may be correct but it's not more efficient than the naive approach.
Assuming A[i] > B[j] for all i,j (or even only i < j) then there are O(len(A)*len(B)) pairs and simply printing them to output would take O(len(A)*len(B)), same as the naive approach.

If you only meant to return the number of pairs your solution might have been faster - if there wasn't the need to check every pair's labels, hence making it O(#pairs) = O(len(A)*len(B)) again and not any better than the naive solution.

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

Since algorithm has to produce ALL pairs, it is easy to show that bunch of worse cases exist where algorithm have to produce O(N^2) pairs. Thus, you won't be able to construct anything asymptotically better than O(N^2).

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

This is the correct answer. If you don't have to specifically report all the pairs in (int1, int2) format, you might be able to make an algorithm with a better time complexity (something like gigi84's algorithm), for example if all the O(n^2) pairs can be easily extracted from the data structure but creating the data structure is less than O(n^2). But in that case where do you draw the line, as you could just give the original arrays and a naive pair-extraction algorithm and claim O(1) time complexity.

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

Maybe a custom type of quad-nary tree of either A or B maybe such that each node has four leaves instead of two:

``````X > A[i], y > i --   node A[i], i  -- X < A[i] , y > i
X > A[i],  i < y /              \ X < A[i], i < y``````

And so on, but we would also need some internal balancing scheme similar to red black tree to fully ensure logarithmic run time, which would probably be non-trivial to implement.

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

The problem is basically counting number of inversions in an array.
Use modified merge sort.

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

Another approach could be Java TreeMap. Store all the element of second array in Treemap. Format of Treemap would be array-values as key and array-index as value.
Now for each element X of first array,do a headMap() on hashmap. It will give all the values which are less than X. Now choose the appropriate index from sub map.

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

#include <bits/stdc++.h>
using namespace std;
long long tree[200005];
int A[200005];
int B[200005];
long long query(int idx)
{
long long res = 0;
while ( idx > 0 ) {
res += tree[idx];
idx -= (idx & (-idx));
}
return res;
}
void update(int idx)
{
while ( idx <= 100001 ) {
tree[idx] += 1;
idx += (idx &(-idx));
}
return;
}
int main()
{
int t=1,n;
while ( t-- ){
cin >> n;
for ( int i = 0; i < n; i++ ) cin >> A[i];
for ( int i = 0; i < n; i++ ) cin >> B[i];
memset(tree, 0, sizeof(tree));
long long ans = 0;
for ( int i = n-1; i >= 0; i-- ) {
ans += query(A[i]-1);
update(B[i]);
}
cout << ans << endl;
}

return 0;
}

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

``````def find_all_pairs(a, b):
pairs = []

for i in range(len(a)):
for j in range(i + 1, len(b)):
if a[i] > b[j]:
pairs.append((i, j))
return pairs

print find_all_pairs([2,3,4,8],[10,11,2,1])``````

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

OK, as many of us concluded it's impossible to construct algorithm for this problem with time complexity better than O(N^2) [in worst case]. What to do when interviewer still expects O(N) solution for worst case [where O(N^2) pairs has to be reported]?

1) Provide a formal proof that this is impossible in a classic computation model (turing machine) [providing an argument about # of pairs is enough].

2) Tell the interviewer that we're engineers and we are going to solve this no matter what. Show what constraints we can change to provide O(N) time complexity or better.
For instance we can escape from classical sequential model and design a system (either design a new hardware system or build a distributed systems with many processors/computers) - where we can leverage O(N) processors with very efficient communication between each pair of processors. In this case O(N) solution is possible. We can find O(N^2) pairs and report them in O(N) time into a distributed storage across our O(N) nodes.

If I was an interviewer at Amazon I'd be happy to hear such answer.

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

Maybe I'm missing something but this seems really trivial:

have two opposing indices and increment/decrement comparing every time they move.

Javaish:

``````int i = 0;
int j = B.size() - 1;
boolean increment = true;

while(i < j) {
if(A[i]>B[j]) {
}
if(increment) {
i++;
} else {
j--;
}
increment = !increment;
}
// return pairs``````

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

``````import java.util.HashMap;
public class Inversion{

int sum =0;
public int [] merge(int a[], int s, int m, int e, HashMap<Integer, Integer> index){
int l1 = m-1;
int [] helper = clone(a);
int r = s;
int inv = 0;
int sum=0;
while(s <= l1 && m <= e){
if(index.get(a[s]) <= index.get(a[m])){
sum += inv;
helper[r++] = a[s++];
}
else{

if(sum == 0)
sum = inv;
inv++;
sum += 1;

helper[r++] = a[m++];
}
}
while(r < e+1){
if(s > l1){
helper[r++] = a[m++];
}
else{
if(sum == 0)
sum += inv;
helper[r++]  = a[s++];
}
}
this.sum += sum;
return helper;
}
public int [] countInversions(int a[], int s, int e, HashMap<Integer, Integer> index){

if(s > e || s > a.length-1 || e < 0){
return null;
}
if(s == e){
return a;
}
else{
int m = (s+e)/2;
a = countInversions(a, s, m, index);
a = countInversions(a, m+1, e,  index);
a = merge(a, s, m+1, e, index);
return a;
}
}
public int countInversions(int a [], HashMap<Integer, Integer> index){
a = countInversions(a, 0, a.length-1,  index);
for(int i:a){
System.out.print(i+" ");
}
System.out.println();
return this.sum;
}
private int [] clone(int a[]){
int helper [] = new int[a.length];
for(int i=0; i<a.length; i++){
helper[i] = a[i];
}
return helper;
}
private static HashMap<Integer, Integer> reverseIndex(int a[]){
HashMap<Integer, Integer> index = new HashMap<Integer, Integer> ();
for(int i =0; i<a.length; i++){
index.put(a[i],i);
}
return index;
}
public static void main(String [] args){
int a[] = {5,4,3,2,1};
int b[] = {1,2,3,4,5};
HashMap<Integer, Integer> index = reverseIndex(b);

Inversion inv = new Inversion();
System.out.println(inv.countInversions(a,index));
}
}``````

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

Sort the two arrays and start an imaginary merge process by keeping the index i and j at a and b respectively.Whenever we find a[i]>b[j] and i<j, find the ceil(a[i]) in b[j+1....b.size], that will give us the count of pairs corresponding to each a[i] found.Continuing in this manner, all pairs corresponding to each a[i] can be found in O((M+N)Log(M+N)).

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

#Perl code
#!D:\\bin\\perl
use strict;
use warnings;

my @A = qw(10 15 16 18 110 115);
my @B = qw(5 9 6 10);
my \$j =0;
for(my \$i=0; \$i <= scalar @B - 1 && \$i < scalar @A ;\$i++)
{

for(\$j=\$i+1; \$j < scalar @B ;\$j++)
{

if( \$A[\$i] > \$B[\$j])
{
print "\$i\t\$j\n";
}
}
}

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

Perl code

``````#!D:\\bin\\perl
use strict;
use warnings;

my @A = qw(10 15 16 18 110 115);
my @B = qw(5 9 6 10);
my \$j =0;
for(my \$i=0; \$i <= scalar @B - 1 && \$i < scalar @A ;\$i++)
{

for(\$j=\$i+1; \$j < scalar @B ;\$j++)
{

if( \$A[\$i] > \$B[\$j])
{
print "\$i\t\$j\n";
}
}
}``````

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

Perl code

``````#!D:\\bin\\perl
use strict;
use warnings;

my @A = qw(10 15 16 18 110 115);
my @B = qw(5 9 6 10);
my \$j =0;
for(my \$i=0; \$i <= scalar @B - 1 && \$i < scalar @A ;\$i++)
{

for(\$j=\$i+1; \$j < scalar @B ;\$j++)
{

if( \$A[\$i] > \$B[\$j])
{
print "\$i\t\$j\n";
}
}
}``````

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

``````def big_small_pair(a,b)
j = b.length - 1
i = 0
result = [ ]
while ( 0 < j)
if a[i] > b[j]
result << [ a[i], b[j] ]
end
i = i + 1
if i == a.length
j = j - 1
i = 0
end

end
puts result.inspect
end

a= [2,3,4,9,6]
b= [1,9,7,5,1,4,3,1]
puts big_small_pair(a,b)``````

Comment hidden because of low score. Click to expand.
-1
of 3 vote

``````/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void printPair(int[]a ,int[] b)
{
for(int i=0;i<a.length-1;i++)
{
for(int j= i+1;j<b.length;j++)
{
if(a[i] > b[j])
{
System.out.println("("+a[i]+","+b[j]+")");
}
}

}
}

public static void main (String[] args) throws java.lang.Exception
{
int a[] ={2,7,3,4,9,10};
int b[] ={8,4,9,3,2};

printPair(a,b);
}
}``````

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

According to me the complexity of for loop solution is n log m and not n^2 because execution of inner loop is decreasing as value of i is increasing.

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

Coder: O(N-1 + N-2 + N-3 ... + 2 + 1 ) = O(N(N-1)/2) = O(N^2)
I recommend reading something like Skiena "The Algorithm Design Manual", to learn about asymptotic complexities and RAM model.

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

``````#include<stdio.h>
#include<stdlib.h>

int main(int argc,char *argv[])
{
int A[] = {1,3,4,8,2,5,6};
int B[] = {8,2,7,9,4,1};
int i,j;
int len1 =0;
int len2 =0;
i = 0;
while(A[i])
{
len1++;
i++;
}
j =0;
while(B[j])
{
len2++;
j++;
}
printf(" length of A %d",len1);
printf("length of B %d\n",len2);

for(i=0;i<len1;i++)
{
for(j=i+1;j<len2;j++)
{
if(A[i]>B[j])
{
printf("pairs are %d%c%d\n", i+1,',',j+1);
}
}
}
}
~
~
~
~``````

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

My approach:
1. Create a binary search tree for the array with longer length where each node in the BST will have value and the index
2. For each element in the other array, search for the appropriate nodes based on greater or lesser needed, print all the nodes from the subtree.
Complexity: it is still quadratic. But it has potential of elements parsing to half for the larger array.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Complexity: O(N^2)

Comment hidden because of low score. Click to expand.
-1
of 1 vote

@0xF4, if the tree is self balancing, then the complexity will be what I have mentioned.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Victor: even if tree is self-balancing the complexity is still O(N^2).
Note, that you have to find ALL the pairs. In worst case (or on a random input) there will be O(N^2) pairs to report, so overall complexity is O(N^2). The fact that you propose to use self-balancing tree doesn't help here.

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

@0xF4: After further scruitiny, I know why are you saying so. I agree, the solution is quadratic. The only optimization is that, for some, it is possible to not parse half of them.

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

You inrecment both i and j. But what if you can increment only the i and next maximum will be bigger then B1[j]?

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

This is incorrect. You have to find ALL pairs

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

It doesn't matter whether you sort it or not, asymptotically it will be O(N^2) since in worst case you have to report O(N^2) pairs.

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

This is O(N^2)

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.