## Amazon Interview Question for Production Engineers

• 0

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

1) first sort the array --> O(nlog n)
2) Take two pointers first and last
while(first<=last)
{
if(arr[first]*arr[last]==given_input)
print " both nos";
if(arr[first]*arr[last]>given_input)
last--;
if(arr[first]*arr[last]<given_input)
first++;
}

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

not sure what you need an array of 100, you can just use two counters, one going up from 1, the other going down from N (where N is the number), the termining condition being (lower counter< upper counter)

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

``````it can be done with O(n) space and O(n) Runtime with Hash.

Step#1 Iterate over Array.
Step#2 Key=30/Array[i].
a)Check if the key exists in Hashmap. If yes, print key and Array[i]
b)if not [Insert key into Hashmap ]``````

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

``````A small correction.

it can be done with O(n) space and O(n) Runtime with Hash.

Step#1 Iterate over Array.
Step#2 Key=30/Array[i].
a)Check if the array[i] exists in Hashmap. If yes, print key and Array[i]
b)if not [Insert key into Hashmap ]``````

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

perfect !

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

void main()
{
A[100];
k;
B[k/2];
PRINT(1,k);
for(i=2;i<100;i++)
{
If(k%A[i]==0)
{
m= k/A[i];
if(i<=m&&B[i]==0)
{
B[i]=1;
PRINT(i,m);
}
if(m]<i&&B[m]==0)
{
B[m]=1;
PRINT(m,i);

}
}
}
}

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

amit's solution is correct approach.

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

``````This can be done using a hashtable. For each number, check if (Given_value / array[i]) exists in the hash, if not then add array[i] in the hashtable. Keep going through the array, until you find the pair which multiplication is the value given.
This can be done in O(n) with extra storage.``````

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

This can be done using a hashtable. For each number, check if (Given_value / array[i]) exists in the hash, if not then add array[i] in the hashtable. Keep going through the array, until you find the pair which multiplication is the value given.
This can be done in O(n) with extra storage.

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

``suppose array has only six elements {1,2,3,4,5,6} number is 30,  key=30/arr[i]  .. ..30,15,10,7,6,5  can you explain how to get 6 and 5 is answer in this scenario.``

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

i got it thanks

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

good solution given by amit

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

vector< pair <int, int> > getFactorInArrayOfInt( int numbers[100], int n )
{
map<int, bool> foundNums;
vector< pair <int, int> > ret;
for ( int i = 0; i < 100; i++ )
{
if ( n % numbers[i] == 0 )
{
int otherFactor = n / numbers[i];
if ( foundNums[ otherFactor ] )
{
pair <int, int> p( otherFactor, numbers[i] );
ret.push_back(p);
}
foundNums[ numbers[i] ] = true;
}
}
return ret;
}

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

When the array is pre-sorted it takes only o(n) time(single pass) and o(1) space, for idea's solution.

HashTable Solution doesnt depend on whether array is sorted or not. It always takes o(2n)(two passes) time and o(n) space.

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

``````int cmp(const void* a, const void* b) {
return (*(int*) a) - (*(int*) b);
}

void factorsWithSort(int a[], int x) {
int y = sqrt(x), z = 0;

qsort(a, N, sizeof (int), cmp);

for (int i = 0; a[i] <= y && i < N; ++i) {
z = x / a[i];
if (x % a[i] == 0 && binary_search(a, a + N, z)) cout << a[i] << '\t' << z << endl;
}
}

// int hash[N] = {0}; Won't suffice if any value is >= 100
void factorsWithHash(int a[], int x) {
map<int, int> map;
int k = 0, v = 0;

for (int i = 0; i < N; ++i) {
if (x % a[i] == 0) {
k = x / a[i];
if (v = map[k]) cout << k << '\t' << v << endl;
else map[a[i]] = k;
}
}
}``````

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

Enhancement:

void factorsWithHash(int a[], int x) {
map<int, int> map;
int k = 0, v = 0;

for (int i = 0; a[i] <= x && i < N; ++i) {
if (x % a[i] == 0) {
k = x / a[i];
if (v = map[k]) cout << k << '\t' << v << endl;
else map[a[i]] = k;
}
}
}

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

Enhancement:

``````void factorsWithHash(int a[], int x) {
map<int, int> map;
int k = 0, v = 0;

for (int i = 0; a[i] <= x && i < N; ++i) {
if (x % a[i] == 0) {
k = x / a[i];
if (v = map[k]) cout << k << '\t' << v << endl;
else map[a[i]] = k;
}
}
}``````

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

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

what if we have to do without extra space,,i.e. inplace (and unsorted list) ?

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

void getProductPairs(std::vector<unsigned int> numberArray, unsigned int product, std::vector< std::pair<unsigned int, unsigned int> > &allPairs) {
std::map<unsigned int, unsigned int> occurenceMap;
for (std::vector<unsigned int>::iterator iter = numberArray.begin(); iter != numberArray.end(); iter++) {
if ((product % *iter) == 0) {
int numPairs;
if ( (numPairs = occurenceMap.count((product / *iter))) > 0) {
allPairs.insert(allPairs.begin(), occurenceMap[(product / *iter)] , std::make_pair(*iter, product/(*iter)));
}
}
occurenceMap[*iter]++;
}
}

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

Amit's solution though O(n) on the look of it is not all that elegant!

First, insertion or search in Hash would consume O(log(n)).
Second, even by using extra space the algorithm is not getting efficient on reruns!
His solution would eventually turn out to be O(nlog(n))!

In my opinion, time complexity is not an issue here because it's given that the Array is of size 100... even nlogn =~ O(700) which is not huge at all!

So without using any more space the possible solution is:
1. Sort the array (100log100)
2. Init low=A[0], high = A[99]; Input M;
3. Iterate array starting at low ; compute val = int(M/A[low]);
4. Put high = tentative_Binary_search(val, low, high); // tentative binary search means if val doesn't exist return the lower key
5. If(A[high] == val) Print A[low] and A[high];
6. low = low + 1;
7. Go to 3 ; Till the point where (low == high)

In this scenario also most expensive step is sorting [which can be improved to O(n) depending on Array sets]
The other part is worst case O(100)

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

@Anshul

Dude..Don't say O(700) and O(100) to the interviewer.. O(any number) is considered as constant time.. You shouldn't substitute n with the size of the input.. because you are calculating the asymptotic growth. n is a variable.

You may say, for input size 100, the run times won't vary that much for a O(n) and O(nlogn) solution.

Insertion and Search is not O(logn) for hash table, insertion is O(n) and search is O(1)

you are doing a sort.. O(nlogn)
and for each n-> binary search which again is O(nlogn)

I am not sure, how your solution is better than Amit's, especially when you want the algorithm to be rerun.

Amit's solution is O(n) + O(n)and it is optimized for algorithm rerun, because all values are already hashed..

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

i dont understand the need for a hash table.

assuming the array is from 1-100 ( in any order), iterate from start to end and check for key % a[i]==0 . if this stmt is true, then factor1 = key/a[i] and factor2 = a[i]. to prevent repetition check if factor2 is greater than factor1 and if so then dont print it else print it

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

arr = 100

arr = [i for i in range(1, arr+1)] # ask if array to start from 0 or 1

target = 30

ret = []

for x in range(0, len(arr)-1):
for y in range(x+1, len(arr)):
if x*y == target:
ret.append([x,y])
print(x,'', y)
else:
print('not possible to multiply')

#option2
arr2= [(x, y) for x in range(0, len(arr)-1) for y in range(x+1, len(arr)) if x*y ==target]
print(arr2)

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

sachin sinh gaur : do you hate indents/tabs? please surround your code with

``and``

.

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

@Anshul: You are a big SUCKER !
care to suck ? ring 1-320-322-468

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.