Amazon Interview Question

• 0

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

Is it not the simple knapsack problem; where the size of the weight are i*i and value of the each weight is -1; now maximize the value of the knapsack size N;

getMin(int N)
{
int m[]=new int[N];
m=1;
for(int i=1;i<N;i++)
{
for(int j=1;j<Sqrt(N)+1;j++)
m[i]=Min(m[i],1+m[i-w[j*j]);// add a special condition that m[i] cannot be 1;
}
return m[N];// If we want to print the values ; we need to store the vales which
//we choose then back trace.
}

please comment if i am wrong

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

Hey Luffy
Your solution seems to be correct to me . Its almost like coin change problem where we have denominations from 1 to sqrt(n) , each denomination are infinite . Its similar to knap sack problem where we associate -1 value for each addition of a coin . so we get the solution with minimum complexity . Time complexity is 0(n*sqrt(n)) .space complexity is same . DP its better we use bottom up approach

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

If you assume hash is O(1) operation, then the lowest possible complexity seems to be O(n) as I explained in my post. 4-Sum problem would be O(m^2) [in my above post] if done with hashtable.

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

1) Get the largest a > 0, such that a^2 <= N. If N is a perfect square, return.
2) Now take the set of numbers 0, 1, 4, 9 .. a^2 and use dynamic programming to get the optimal combination to reach N. This is the exact same problem as the Coins combination problem.
The basic idea is
MinNoOfSquares(N) = Minimum of (MinNoOfSquares(N - 1), MinNoOfSquares(N - 4), (MinNoOfSquares(N - 9) ...) + 1;

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

My first idea - kind of brute: consider the squared numbers 1,4,9,...,[sqrt(N)]^2 as nodes in a weighted graph where w(i,j) = i+j (i and j are two nodes) - the graph will be complete.
For each node (or only a half is enough?), do a DFS/BFS while computing the path length.
If a partial solution has 2 nodes, return it.
If path length < N, continue with next node.
If path length == N, store the partial solution in a set of partial solutions.
If path length > N, remove the current node and continue.
When all nodes are complete, get the minimum solution (i.e. the smallest number of nodes) from partial solutions set.
I thinks the complexity is O(m^2) in time and space, where m is the number of nodes in graph.

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

I really doubt if u r convinced urself that ur method works. When you say, w(i,j) = i+j, can't you realize that you are taking same value twice, if you chose two edges like w(i,j) and then w(j,k). Hence, this graph theoretic method is wrong at it's core conception!

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

outright rubbish solution !

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

One can make sure that the values are taken only once. But the graph idea works. Maybe not as a weighted graph... but one can design a graph where the values are on the nodes. Hence, adding the same value twice is not possible (by design).

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

We can solve this problem using recursive function.
1. Create a function which returns nearest largest square root of the number.
2. Call the above function recursively till the number is reduced to 0.

Ex: n = 21
1. nearest sqrt: 4, call function(21-(4^2)) i.e., function(5)
2. nearest sqrt: 2, call function(5-(2^2)) i.e., function(1)
3. nearest sqrt: 1, call function(1-(1^2)) i.e., function(0) //stop recursion

Solution: 4, 2, 1

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

What u try to do is called greedy. It fails. For N = 106, you'd pick 100, then 4, then 1, then 1. Hence, length = 4. But, optimum is 9^2+5^2 = 106.

Why don't work with few inputs before giving so simple? That way you'd learn something!

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

Agree. Thanks.

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

In that case I think backtracking could help.

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

This question needs some clarification. Is it possible to take a number multiple times? For example, if N = 3, there is only 1 way: 1^2 + 1^2 + 1^2 = 3. Otherwise, there is no solution for most of the input cases, and that makes the problem a lot simpler!

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

You have a sorted array of squares: 1^2, 2^2, ..., [sqrt(N)]^2.

Determine if that array has two elements, a,b which sum to N.
Determine if that array has three elements a,b,c, which sum to N.

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

This approach works. But we need to have N/(n^2) copies of each (n^2).

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

@Guest123: Why?

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

Remember Waring's theorem... Every integer can be written as sum of four squares.

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

Or rather, lagrange's four square theorem.

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

if N=3,
we need to have 3 1^2's right.

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

3 is the limit.

So to clarify.

Let P^2 be the largest perfect square <= N.

Have three arrays:

1^2, 2^2, ..., P^2
2* 1^2, 2* 2^2, ..., 2*P^2
3* 1^2, 3* 2^2, ..., 3* P^2

Check if N appears in last two. etc etc.

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

works!

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

But why have same elements repeated 6 times in 3 different arrays? can't they be repeated 4 times in same array including 4* 0^2?

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

It was mentioned only to dispel doubts of this working. Optimization left to the reader.

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

I think there are 3 cases:

- find a, b such that a^2 + b^2 = n => takes O(m) where m is number of elements from which to select a and b.

- find a, b, c such that a^2 + b^2 + c^2 = n => takes O(m^2)

- find a, b, c, d such that a^2 + b^2 + c^2 + d^2 = n => takes O(m^2 logm)

As m = sqrt(n), it seems total time complexity would be O(n logn).

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

I think this is a problem which involves combination.

Have squares in an array and find the smallest combination which adds upto the number.

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

1. Find the number which is a perfect square closest to the given number.
2. Get the remainder (number-perfect square) and then perform step 1.
3. By Lagrange's four square theorem we know that the maximum we can go is 4.

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

your algo doesn't work... pls read the above discussion, your algo is the brute force approach not the optimal one.

Eg: 106
-according to you algo its 10^2 + 2^2 + 1^2 + 1^2
- but its also 9^2 + 5^2 which is optimal

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

Hey genius! wht's ur problem? Guest123 had already talked abt this greedy approach... Someone posted this to his reply :

What u try to do is called greedy. It fails. For N = 106, you'd pick 100, then 4, then 1, then 1. Hence, length = 4. But, optimum is 9^2+5^2 = 106.

Why don't work with few inputs before giving so simple? That way you'd learn something!

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

correct me if m wrong..we can calcuate all possible sums?? for all the perfect squares that are posted in the the solution...is it related to dynamic programming?

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

Yes, I thought about the dynamic programming approach.It works, but there could be a better solution with some mathematical caveat.

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

O(2^n) without memoization. O(kn) if memoization used..

c = 0
MKS(k, i)
if(i < 0)
return
if(k == 0)
if(c < min)
min = c
return
else
MKS(k - a[i], i-1, c+1)
MKS(k, i-1, c)

n = 0
CA(k)
while(1)
if(n*n <= k)
a[n] = n*n
else
return

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

Improved one

MKS(k, i)
if(i > n)
print "No solution possible"
if(k == 0)
return 0
if(a[i] > k)
return 0
return min(MKS(k-a[i], i+1) + 1, MKS(k, i+1))

n = 0
CA()
while(n*n < k)
a[n] = n*n
n++
main()
CA()
print MKS(k, 0)

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

Improved one

MKS(k, i)
if(i > n)
print "No solution possible"
if(k == 0)
return 0
if(a[i] > k)
return 0
return min(MKS(k-a[i], i+1) + 1, MKS(k, i+1))

n = 0
CA()
while(n*n < k)
a[n] = n*n
n++
main()
CA()
print MKS(k, 0)

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

int minsquares(int sum, int i, int n)
{
if( i >= n)
return INT_MIN;

if(sum == 0)
return 0;

if(sum < 0)
return INT_MIN;

return max(1 + minsquares(sum - i * i, i + 1, n), minsquares(sum, i + 1, n));
}

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.