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

Project description Xchange me, sir:

Implement a simple foreign exchange rate service that uses data provided by the European Central Bank. Provide a REST API to retrieve the exchange rate to EUR from any other currency provided by the ECB and allow querying current (https://www.ecb.europa.eu/stats/eurofxref/eurofxref-daily.xml) and past (https://www.ecb.europa.eu/stats/eurofxref/eurofxref-hist-90d.xml) data. Use an asynchronous job to retrieve and update the xrates storing them locally in memory and have the REST API use the data in memory to return this information.

[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 =
        A
      B  C
there are no holes between B and C

complete =
        A
       B
there are no holes after B

non complete =
       A
        C
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 =  
     A  
    B C  
    no holes between B and C  
   
    complete =  
     A  
     B  
    no holes after B  
   
    non complete =  
     A  
     C  
    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;  
   
     levels.add(root);  
   
     while(!levels.isEmpty()){  
       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  
         levels.add(t.left);  
         levels.add(t.right);  
       }  
   
       //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;  
       }  
       else{  
         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.