## Monday, February 22, 2016

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

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:
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<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));`
` ``}`
`}`
http://stackoverflow.com/questions/14454133/write-all-solutions-for-a3-b3-c3-d3
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;`
` ``}`
http://algobox.org/cube-sum/