http://shirleyisnotageek.blogspot.com/2015/01/write-all-solutions-for-a3b3-c3-d3.html
This is a FB interview question. Here are some feasible approaches. I followed the priority queue method:
So when the range goes up to 10^5, it gives me OutOfMemoryError().
However, just for comparison, I also tried the HashMap method, the memory leak occurs even when range only goes to 10^4. This means the Map has a worse performance than the Priority Queue.
http://stackoverflow.com/questions/14454133/write-all-solutions-for-a3-b3-c3-d3
The HashMap method:
http://algobox.org/cube-sum/
This is a FB interview question. Here are some feasible approaches. I followed the priority queue method:
I certainly didn't fully understand how he maintained O(n) storage in the Queue. When I increment the second value, I still have to store the pairs that has a cube sum that is not equal to the smallest element in the queue. The total space for the queue is still O(n^2), or more accurately O(n^2 / 2).Using a priority queue is almost certainly the simplest solution, and also the most practical one, since it's O(n) storage (with a log factor if you require bignums). Any solution which involves computing all possible sums and putting them in a map will require O(n^2) storage, which soon becomes impractical.My naive, non-optimized implementation using a priority queue is O(n^2 log(n)) time. Even so, it took less than five seconds for n = 10000 and about 750 seconds for n = 100000, using a couple of megabytes of storage. It certainly could be improved.The basic idea, as per your comment, is to initialize a priority queue with pairs (a, a+1) for a in the range [1, N), and then repeatedly increment the second value of the smallest (by sum of cubes) tuple until it reaches N. If at any time the smallest two elements in the queue are equal, you have a solution. (I could paste the code, but you only asked for a hint.)
So when the range goes up to 10^5, it gives me OutOfMemoryError().
However, just for comparison, I also tried the HashMap method, the memory leak occurs even when range only goes to 10^4. This means the Map has a worse performance than the Priority Queue.
public class CubePair implements Comparable<cubepair> { //num1 will always be smaller than num2 private int num1; private int num2; private int cubeSum; public CubePair(int a, int b) { if (a > b) { int tmp = a; a = b; b = tmp; } num1 = a; num2 = b; cubeSum = (int)(Math.pow(num1, 3) + Math.pow(num2, 3)); } public boolean hasEqualSum(CubePair cp) { return cp.cubeSum == cubeSum; } public boolean equals(CubePair cp) { return num1 == cp.num1 && num2 == cp.num2; } public int getFirst() { return num1; } public int getSecond() { return num2; } public String toString() { return String.valueOf(num1) + ", " + String.valueOf(num2) + ";"; } @Override public int compareTo(CubePair cp) { return cubeSum - cp.cubeSum; }}import java.util.*;public class FindCube { public List<list tring="">> sameCubeSums(int range) { if (range <= 0) throw new IllegalArgumentException("range must be positive"); List<list tring="">> rst = new ArrayList<list tring="">> (); PriorityQueue<cubepair> pq = new PriorityQueue<cubepair> (); for (int i = 1; i < range; i++) { pq.add(new CubePair(i, i + 1)); } int prev = 0; int maxSize = 0; while (!pq.isEmpty()) { maxSize = Math.max(maxSize, pq.size()); CubePair curr = pq.poll(); if (pq.isEmpty()) break; if (curr.hasEqualSum(pq.peek())) { addList(rst, curr, pq.peek()); if (curr.getFirst() < pq.peek().getFirst()) curr = pq.poll(); else pq.poll(); } if (curr.getFirst() <= prev) continue; for (int i = curr.getSecond() + 1; i <= range; i++) { CubePair tmp = new CubePair(curr.getFirst(), i); if (tmp.hasEqualSum(pq.peek())) { addList(rst, tmp, pq.peek()); } else { pq.add(tmp); } } prev = curr.getFirst(); } System.out.println("max queue size: " + maxSize); return rst; } private void addList(List<list tring="">> rst, CubePair pair1, CubePair pair2) { List<string> pair = new ArrayList<string> (); pair.add(pair1.toString()); pair.add(pair2.toString()); rst.add(new ArrayList<string> (pair)); }}The HashMap method:
public List<list tring="">> sameCubeSums2(int range) { if (range <= 0) throw new IllegalArgumentException("range must be positive"); Map<integer list="" tring="">> map = new HashMap<integer list="" tring="">>(); List<list tring="">> rst = new ArrayList<list tring="">> (); for (int i = 1; i < range; i++) { for (int j = i + 1; j <= range; j++) { int cubeSum = (int)(Math.pow(i, 3) + Math.pow(j, 3)); if (!map.containsKey(cubeSum)) { map.put(cubeSum, new ArrayList<string> ()); map.get(cubeSum).add(String.valueOf(i) + "; " + String.valueOf(j)); } else map.get(cubeSum).add(String.valueOf(i) + "; " + String.valueOf(j)); } } for (List<string> pairs : map.values()) { if (pairs.size() > 1) rst.add(pairs); } return rst; }