[Java] Implement a LRU cache

Here is an interesting and quite simple exercise: implement a LRU cache in Java.

When thinking about the problem, it appears immediately that we cannot do away with a single "basic" data structure, so we must combine at least two of them in a custom class. We use a HashMap for fast object retrieval and a custom doubly linked list to keep track of the objects access order, from MRU to LRU.

In this solution we have the put and get operations working in O(1) and we use additional O(N) space where N is the max cache size.

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

Convert Ghostscript to PDF

To convert a Ghostscript file to PDF it's quite useful to have the utility ps2pdf installed on your system; it will come as part of the Ghostscript installation.

Then, make sure you have the gs command on the path and run either of these scripts depending on the PDF version you want to generate (note that the official documentation will be constantly updated, this page not!) :

• ps2pdf12 produces PDF 1.2 output (Acrobat 3-and-later compatible).
• ps2pdf13 produces PDF 1.3 output (Acrobat 4-and-later compatible).
• ps2pdf14 produces PDF 1.4 output (Acrobat 5-and-later compatible).
• ps2pdf per se currently produces PDF 1.4 output. However, this may change in the future. If you care about compatibility with a specific output level,use the -dCompatibilityLevel=1.x switch in the command line, or one of the specific version aliases ps2pdf12, ps2pdf13, or ps2pdf14.

Another thing to be aware of is that you might receive some errors while generating the PDF such as /invalidfileaccess in /findfont 

This might mean that you are missing a specific font installed on your system, but if that is not the case, maybe the font or some other file is not accessible due to permissions restrictions. You can try by running the utility again and adding -dnosafer as option.

[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;  
   }