Write all solutions for a^3+b^3 = c^3 + d^3, where a, b, c, d lie between [0, 10^5]

This is a FB interview question. Here are some feasible approaches. I followed the priority queue method:

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.)

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).
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 {
 //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> sameCubeSums(int range) {
  if (range <= 0)
   throw new IllegalArgumentException("range must be positive");
  List> rst = new ArrayList> ();
  PriorityQueue pq = new PriorityQueue ();
  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> rst, CubePair pair1, CubePair pair2) {
  List pair = new ArrayList ();
  pair.add(pair1.toString());
  pair.add(pair2.toString());
  rst.add(new ArrayList (pair));
 }
}

Teaser: the HashMap method:

public List> sameCubeSums2(int range) {
  if (range <= 0)
   throw new IllegalArgumentException("range must be positive");
  Map> map = new HashMap>();
  List> rst = new ArrayList> ();
  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 ());
     map.get(cubeSum).add(String.valueOf(i) + "; " + String.valueOf(j));
    }
    else 
     map.get(cubeSum).add(String.valueOf(i) + "; " + String.valueOf(j));
   }
  }
  for (List pairs : map.values()) {
   if (pairs.size() > 1) 
    rst.add(pairs);
  }
  return rst;
 }