CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

Amazon Interview Question for SDE-2s


Country: United States
Interview Type: In-Person



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

It seems to me like a knapsack problem...

There are several approaches that can be used to solve it. Dynamic programming, branch and bound, etc...

- srdjan August 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Yes but we need to apply all combinations of all tiles to get them fit exactly without leaving any gap. NP problem are those problem which needs infinite time to get resolved.

- Akash Deep August 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Question can be more clear. This is how I interpret it

- You are given choices of different tiles to use of different dimensions and prices.

- The available quantities of each tile are unlimited.

- You are not limited to using the same tile in a configuration. You can use a mix of tile sizes.

-The goal is to tile the entire floor at the minimum cost, without gaps at the walls. The tiles have to fit exactly since you can't cut them.

- wgestrich August 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

can not understand question itself...

- Anonymous August 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Looks like a Tank jar problem where a tank has to be filled with water cans of different capacities in min attempts . Dynamic programming can be used to solve the problem. Sort the tiles by cost per unit area. Start with tile with minimum cost per unit area and then go to the next tile.

- Raj August 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a NP complete problem...so there is no solution faster than O(2^n) solution...

- Praveen August 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Prove that it is NP-Complete.

- Anonymous August 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is NP complete if tiles are limited in number, if unlimited then DP can be used.

- tryingtosolvemystery August 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think it is also NP-complete when unbounded, because it seems like a generalization of unbounded knapsack problem

- Isai August 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Yes it's NP problem, it takes enough time to get solved. As we have a given area and we need to fit tiles in it.

Proved it's NP problem.

- Akash Deep August 14, 2013 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More