Java Data Structures Interview Question
LinkedHashMaps in Java, Lyft type interview questions
This is a modified version of what my Lyft interview question for the third round looked like. I also stripped back some of the requirements. Mostly because I couldn’t remember what they were, but also because this is what you really need to get familiar with if you work in Java often.
“Here at Lyft we love Java and we love using LinkedHashMaps in Java. LinkedHashMap is obviously just an extended type of the Map in Java. We love using maps for their constant time lookup and insertions. Can you explain the benefits and cons of using a LinkedHashMap over a regular HashMap in Java? And can you implement your own version of a LinkedHashMap with only the basic features of add, get, and return a list or set of values in insertion order? Don’t worry about hash collisions.”
My answer:
“LinkedHashMaps are great because they provide all the benefits of using a regular HashMaps but it keeps the insertion order of elements, so if one wanted to keep track of how elements are inserted, then one could just iterate over the Map. It does this by using each MapElement as a node in a linked list-like format by keeping its predecessor and successor. The cons of this are really only overhead as each Node inserted now has to keep a reference of 2 other nodes.”
My code:
//Main.java:import java.util.ArrayList;public class Main { public static void main(String[] args) { MyLinkedHashMap<String, Integer> myLinkedHashMap = new MyLinkedHashMap<>(100); myLinkedHashMap.add("Seun Suberu", 20); System.out.println(myLinkedHashMap.get("Seun Suberu")); System.out.println(myLinkedHashMap.get("SeunSuberu")); myLinkedHashMap.add("Jasmine Patrick", 30); ArrayList<MyLinkedHashMapNode<String, Integer>> iterativeList = myLinkedHashMap.getIterator(); for(MyLinkedHashMapNode<String, Integer> node : iterativeList) System.out.println(node.getValue()); }}//MyLinkedHashMap.java:import java.lang.IllegalArgumentException;import java.util.ArrayList;import java.util.Set;public class MyLinkedHashMap<K, V> { MyLinkedHashMapNode head; MyLinkedHashMapNode tail; MyLinkedHashMapNode[] nodes; int capacity; int size; MyLinkedHashMap(int capacity){ nodes = new MyLinkedHashMapNode[capacity]; this.capacity = capacity; size = 0; } public boolean add(K key, V value){ if(key instanceof Object){ int hash = Math.abs(key.hashCode()); int index = hash % capacity; if(nodes[index] != null) return false; MyLinkedHashMapNode<K, V> newNode = new MyLinkedHashMapNode(key, value); nodes[index] = newNode; if(head == null) { head = newNode; tail = newNode; } else{ tail.setNext(newNode); newNode.setPrevious(tail); tail = newNode; } } else{ throw new IllegalArgumentException(); } return true; } public Object get(K key){ int hash = key.hashCode(); int index = hash % capacity; if(nodes[index] != null) return nodes[index].getValue(); else return null; } public ArrayList<MyLinkedHashMapNode<K, V>> getIterator(){ ArrayList<MyLinkedHashMapNode<K, V>> returnedList = new ArrayList<>(); MyLinkedHashMapNode<K, V> curr = this.head; while(curr != null){ returnedList.add(curr); curr = curr.getNext(); } return returnedList; }}//MyLinkedHashMapNode.java:import java.util.Objects;public class MyLinkedHashMapNode<K, V> { private MyLinkedHashMapNode previous; private MyLinkedHashMapNode next; private V value; private K key; MyLinkedHashMapNode(K key, V value){ this.key = key; this.value = value; } public MyLinkedHashMapNode getNext() { return next; } public MyLinkedHashMapNode getPrevious() { return previous; } public void setValue(V value) { this.value = value; } public void setNext(MyLinkedHashMapNode next) { this.next = next; } public void setPrevious(MyLinkedHashMapNode previous) { this.previous = previous; } public V getValue() { return value; }}
Additional Resources:
