Pocket Gems Interview Question: Given an infinite number of b... | Glassdoor

Interview Question

Software Engineer Interview(Student Candidate)

Given an infinite number of bricks of given weights w (say

  w = [1, 2]) and a truck of capacity c (say, c = 3), how would you find all possible combinations of bricks that match the capacity exactly? Duplicates such as [1,2] and [2,1] are NOT allowed.

Interview Answer

4 Answers


This is a typical coin change problem.

Khaleeque Ansari on Nov 10, 2013

This is not a coin change problem. This is a K-Sum problem, In which you need to find all possible combinations that sum up to a value, in this case C= 3.
Check out the solution here.http://stackoverflow.com/questions/4632322/finding-all-possible-combinations-of-numbers-to-reach-a-given-sum

Akash Mankar on Mar 16, 2014

In the case of w = [1,2], this problem can be simplified as how many (int)(c/2)+1.

Cong Ku on Mar 2, 2015

Do you have a question about Pocket Gems? Don't ask just anyone for information, ask an employee from Pocket Gems. They're all waiting at Rooftop Slushie.


Anonymous on Jul 15, 2019

Add Answers or Comments

To comment on this, Sign In or Sign Up.