[Java] Xchange me, sir - Sample REST project to get xrates to EUR

A while ago, while I was going through some interview rounds, a company that will be left unnamed, reluctantly assigned me a sample project to deliver as part of the interview process.
Very annoying though, was the fact that they had me book after some organisational pain, an hour of my time just to call and tell me in five minutes that it was highly unlikely I could deliver since I hadn't worked in Java recently.
Regardless of that quite bold and rude statement, I still asked to have the project just for practice anyway and they agreed, saying if I really wanted I could try and come back to them when I was done .
I of course did not plan to, but turning down some free exercise is never a smart choice, so I rolled with it.
Obviously they had never heard of Google as well, given that the whole project can easily be assembled just by searching code snippets and gluing them with minimal brainpower anyway if you are on a lazy mode day.
So long story short, here we are with the Xchange me, sir project.


[Java] Reverse doubly linked list

Here is a O(N) time and O(1) space method to reverse a doubly linked list:

 //reverse doubly linked list  
   public static DoubleLinkedListNode reverseList(DoubleLinkedListNode head){  
     if(head == null) return head;  
     DoubleLinkedListNode prev = null;  
     while(head != null){  
       DoubleLinkedListNode next = head.next;  
       head.next = prev;  
       prev = head;  
       head = next;  
     return prev;  

You can check the implementation on my Gist along with the definition of the DoubleLinkedList class and some test cases.


[Java] Find if binary tree is complete

A binary tree is complete if for each level, there are no holes between two children. For example:

complete =
      B  C
there are no holes between B and C

complete =
there are no holes after B

non complete =
there is a hole before C

You can the code on my Gist (isTreeComplete) along with some test cases:

   is tree complete  
   A tree is complete if for each level, there are no holes between children:  
   complete =  
    B C  
    no holes between B and C  
    complete =  
    no holes after B  
    non complete =  
    hole before C  
   public static boolean isTreeComplete(BST root){  
     //null root is always complete  
     if(root == null) return true;  
     otherwise, we must NOT have null nodes between two nodes at each level  
     so do a BFS BUT CAUTION: track also NULL children, then check we do not have a non null node after we encountered a null one  
     Queue<BST> levels = new LinkedList<>();  
     boolean has_null = false;  
       BST t = levels.remove();  
       //if current node is not null  
       if(t != null) {  
         //if we had a null, fail  
         if(has_null) return false;  
         //otherwise add its children  
       //track if the node we just saw was null. CAUTION: do not overwrite it!  
       has_null = has_null || t == null;  
     //if we navigated the whole tree without problem, it is complete  
     return true;  

[Java] Find if a binary tree is balanced

A binary tree is balanced if the left and right branches do not differ in depth for more than one level.

Here is some code to test this (isTreeBalanced) you can check on my Gist for some test cases as well:

   is tree balanced  
   A tree is balanced if the left and right branches do not differ for more than 1 level in length  
   private static Entry isTreeBalancedAux(BST root){  
     //null root is always balanced  
     if(root == null) return new Entry(true, -1);  
     Entry left, right;  
     //check subtrees  
     left = isTreeBalancedAux(root.left);  
     right = isTreeBalancedAux(root.right);  
     //if they are not balanced, we have our answer  
     if(!left.isBalanced || !right.isBalanced) return new Entry(false, 0);  
     //otherwise if they are balanced, but they differ for more than 1 level in depth, this node is not balanced  
     if(Math.abs(left.height - right.height) > 1) return new Entry(false, 0);  
     //finally, if all is good, return the max depth from this node incuding itself and mark it as balanced  
     return new Entry(true, Math.max(left.height, right.height) + 1);  
   public static boolean isTreeBalanced(BST root){  
     return isTreeBalancedAux(root).isBalanced;  

I use an additional data structure (Entry) to pass around two pieces of information:

- is the tree balanced so far
- what is the current depth of the path being analyzed

[Java] Find depth of binary tree

Here is a simple method to find the depth of a given binary tree, no matter if it's balanced or not.

The null tree has depth -1, the root has depth 0 and so on. By looking at the depth it is immediately possible to get the max number of elements at that depth: 2^depth.

You can check the code on my Gist (getTreeDepth) along with some test cases:

 //find depth of the tree  
   public static int getTreeDepth(BST root){  
     if(root == null) return -1;  
     return Math.max(getTreeDepth(root.left), getTreeDepth(root.right)) + 1;  

[Java] LinkedList sum

Here's a simple exercise: given two positive numbers represented as linked lists, return their sum as a new linked list.

This is quite easy if we represent the two integers with lists that have the least significant digit at the head, eg:

A = 123 -> 3,2,1
B = 45 -> 5,4
result = 168 -> 8,6,1

You can check the code and some tests on my Gist (LinkedListSumJTests):

   Given two lists representing integer numbers  
   with the least significant digit in the head position  
   return a new list containing the sum  
   public static SingleLinkedListNode sumListsFromLSD(SingleLinkedListNode x, SingleLinkedListNode y){  
     if(x == null && y == null) return null;  
     int carry = 0, curr = 0, val = 0;  
     SingleLinkedListNode result = null, n = null;  
     //keep going until we have data in either list and do not forget the last carry!  
     while(x != null || y != null || carry != 0){  
       curr = ((x == null || x.id == null) ? 0 : x.id) + ((y == null || y.id == null) ? 0 : y.id) + carry; //x + y + carry  
       val = curr % 10; //take only LSD  
       //track if we have a carry  
       carry = (curr >= 10) ? 1 : 0;  
       if(n == null){  
         n = new SingleLinkedListNode(val);  
         result = n;  
         n.next = new SingleLinkedListNode(val);  
         n = n.next;  
       //move to next digit  
       if(x != null) x = x.next;  
       if(y != null) y = y.next;  
     return result;  


[Java] Rolling average for both sorted and unsorted streams

The rolling, moving, running, whatever movement verb you like median or average is a problem regarding the online calculation of the average element in a streaming dataset.

The pro version requires you to sort the data on the fly in order to produce the median result:

input = 9, 4, 10, 3, 3
output = 4 because sorted input is: 3, 3, 4, 9, 10

The base version just wants the actual median element of the stream:

input = 9, 4, 10, 3, 3
output = 10

If the stream length is odd, the median is the actual median element, otherwise it's the average of the two elements near the middle of the stream.

The solution to both returns the median in constant O(1) time and keeps it updated in O(N) time. Also they both use additional O(N) space.