## Amazon Interview Question

Country: United States

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

``````#include <set>
#include <utility>
#include <iostream>

typedef std::set<std::pair<int, int>> PairOfNums;

void findNotMachingPairs(int n, PairOfNums& s)
{
// at least 2 numbers needed
if (n >= 2) {
for (int a = 1; a <= n - 1; ++a) {
for (int b = 2; b <= n; ++b) {
if (a > 10 * b || b > 10 * a) s.insert(std::make_pair(a, b));
}
}
}
}

int main()
{
int n = 40;

PairOfNums s;
findNotMachingPairs(n, s);

for (PairOfNums::const_iterator it = s.begin(); it != s.end(); ++it)
{
std::cout << (*it).first << " " << (*it).second << "\n";
}

return 0;
}``````

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

If i understand problem correctly and we need to form a set of violating pairs, we just need to loop over range 1..n and for each number 'a' add to set pairs of form {a, b}, where b is in range 1..n excluding ceil(a/10.0) .. a*10.

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

I think we should sort the numbers, then for each i we can do a binary search for array[i]×10.. if we found a match then we have a pair a,b.. if no match was found our modified binary search should return the largest number smaller than array[i]×10.. if that number is not the array[i] then a match is found.. else do the same for the next array elements

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

R we just looking for pairs which have different digits?

like 10,3;10,110
we can reduce the search space by this.

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

int set=a;
int count=0;

for(int i=0;i<n;i++)
{
if(a[i]>10*set[count])
{
count++;
set[count]=a[i]
}

i++;
}

//assuming that we have to find the largest set which fulfills all the conditions.

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

On first thought, it would seem THE PROBLEM itself has an OMEGA(N^2) runtime (lower bound N^2).

The number of pairs that meet the conditions of the question seems to be ( as N-> inf ) quadratic in N. So you have to access all results.

Or am I missing anything?

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

s = [(a,b) for a in range(n) for b in range(n) if a>10*b or b>10*a]

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

don't we have all no.s from 1 to n or just some of the numbers ????

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.