Amazon interview question




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

Get all sub-sets of the questions set [which can be can have as many as (2^sizeOfSet)-1 elements].

int maxNumOfSubsets = (2^set.size())-1
Getting all sub-sets can be done by using the binary representation of all integers between 1 and maxNumOfSubsets.

The simply sum each sub-set, if the sum is zero then you have an answer.

private static String binary(int numOfBits, int value) {
		StringBuilder builder = new StringBuilder();
		while (numOfBits>0) {
			int a = value % 2;
			if (a>0) builder.append("1");
			else builder.append("0");
			value /= 2;
			numOfBits--;
		}
		return builder.toString();
	}

	private static List<Set<Integer>> subsets(int[] array) {
		List<Set<Integer>> result = new LinkedList<Set<Integer>>();
		int size = array.length;
		int max = (int) ((Math.pow(2, size)) - 1);
		List<String> binaryValues = new LinkedList<String>();
		for (int i = 1; i<=max; i++) {
			String binary = binary(size, i);
			binaryValues.add(binary);
		}
		for (String s : binaryValues) {
			Set<Integer> set = new HashSet<Integer>();
			for (int i=0; i<s.length(); i++) {
				if (s.charAt(i)=='1')
					set.add(array[i]);
			}
			result.add(set);
		}
		return result;
	}

	private static int sum(Set<Integer> set) {
		int result = 0;
		for (int i : set) {
			result += i;
		}
		return result;
	}

	private static List<Set<Integer>> solve(int[] array) {
		List<Set<Integer>> subsets = subsets(array);
		List<Set<Integer>> list = new LinkedList<Set<Integer>>();
		for (Set<Integer> s : subsets) {
			int sum = sum(s);
			if (sum==0)
				list.add(s);
		}
		return list;
	}

- Justin February 15, 2015 | 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