Amazon Interview Questions.

[Seabook]

1) LRU Cache Implementation.
If the cache is full then find the least recent used item in the cache, evict this item and replace it with new cached item.

2) Tree Question.
Random Binary Tree.
Node {
    Node left;
    Node right;
    Node next;
}

Write a function called populateNextNode(Node) {} to traverse the tree and set all the relevant next node in each node.
                  （1）
                /        \
             (2)  --->  (3)    Node2.next is Node3
           /           /     \
         (4)  --->(5) -->（6） Node4.next is Node5, Node5.next is Node6
            \                   \
           (7)    ------->    (8)  Node7.next is Node8


Happy Coding,
Seabook

[Huanwen Qu]

import java.util.ArrayList;
import java.util.List;

public class ClueTree {

/**
* @param args
*/
public static void main(String[] args) {
Node root = new Node(0);
Node left1 = new Node(1);
Node right2 = new Node(2);
Node left21 = new Node(21);
Node left22 = new Node(22);
Node right24 = new Node(24);
root.left = left1;
root.right = right2;
left1.left = left21;
left1.right = left22;
right2.right = right24;
buildClue(root);
System.out.println(root);
}

static class Node {

Node left;
Node right;
Node next;

int i;

Node(int i) {
this.i = i;
}
}

public static void buildClue(Node root) {
List<Node> rootLevel = new ArrayList<ClueTree.Node>();
rootLevel.add(root);
buildClue(rootLevel);
}

private static void buildClue(List<Node> level) {
if (level.size() == 0)
return;
List<Node> nextLevel = new ArrayList<ClueTree.Node>();
for (int i = 0; i < level.size(); i++) {
Node node = level.get(i);
if (i + 1 < level.size())
node.next = level.get(i + 1);
if (node.left != null)
nextLevel.add(node.left);
if (node.right != null)
nextLevel.add(node.right);
}
buildClue(nextLevel);

}

}


On 10月19日, 上午8时27分, Seabook <seabook1...@gmail.com> wrote:
> 1) LRU Cache Implementation.
> If the cache is full then find the least recent used item in the cache,
> evict this item and replace it with new cached item.
>
> 2) Tree Question.
> Random Binary Tree.
> Node {
>     Node left;
>     Node right;
>     Node next;
>
> }
>
> Write a function called populateNextNode(Node) {} to traverse the tree and
> set all the relevant next node in each node.
>                   （1）
>                 /        \

>              (2)  *---> * (3)    Node2.next is Node3
>            /           /     \
>          (4)  *--->*(5)* -->*（6） Node4.next is Node5, Node5.next is Node6
>             \                   \
>            (7)   * -------> *   (8)  Node7.next is Node8
>
> Happy Coding,
> Seabook

[Huanwen Qu]

import java.util.HashMap;

public class LRUCache {

/**
* @param args
*/
public static void main(String[] args) {

LRUCache cache = new LRUCache(4);
cache.put("1", "obj1");
cache.put("2", "obj2");
cache.put("3", "obj3");
cache.put("1", "obj1");
cache.put("3", "obj3");
cache.put("4", "obj4");
cache.printCache();
System.out.println(cache.get("10"));
cache.put("5", "obj5");
cache.put("6", "obj6");
cache.put("7", "obj7");
cache.printCache();
System.out.println(cache.get("4"));
System.out.println(cache.get("2"));
cache.printCache();
}

class Node {
Node prev, next;
Object key, obj;
}

private int size = 100;
private Node first = null, last = null;
private HashMap<Object, Node> map = null;

public LRUCache() {
map = new HashMap<Object, Node>(size);
}

public LRUCache(int size) {
this.size = size;
map = new HashMap<Object, Node>(size);
}

public void put(Object key, Object obj) {
Node node = map.get(key);
if (node == null) {
if (map.size() >= size) {
map.remove(last.key);
removeNode(last);
}
node = new Node();
node.obj = obj;
node.key = key;
} else {
removeNode(node);
}
addFirst(node);
map.put(key, node);
}

public Object get(Object key) {
Node node = map.get(key);
if (node != null) {
removeNode(node);
addFirst(node);
return node.obj;
} else {
return null;
}
}

private void removeNode(Node node) {
Node prev = node.prev;
Node next = node.next;
if (prev == null && next == null) {
// the only one
first = null;
last = null;
} else if (prev == null) {
// the first
first = next;
next.prev = null;
} else if (next == null) {
// the last
last = prev;
prev.next = next;
} else {
prev.next = next;
next.prev = prev;
}
}

private void addFirst(Node node) {
if (first == null || last == null) {
first = node;
last = node;
node.next = null;
node.prev = null;
} else {
node.next = first;
node.prev = null;
first.prev = node;
first = node;
}
}

public void printCache(){
if(first == null){
System.out.println("Emtpy cache.");
} else {
Node n = first;
while(n != null){
System.out.print(n.key);
System.out.print(" ");
n = n.next;
}
System.out.println();

}
}
}


On 10月19日, 上午8时27分, Seabook <seabook1...@gmail.com> wrote:

> 1) LRU Cache Implementation.
> If the cache is full then find the least recent used item in the cache,
> evict this item and replace it with new cached item.
>
> 2) Tree Question.
> Random Binary Tree.
> Node {
>     Node left;
>     Node right;
>     Node next;
>
> }
>
> Write a function called populateNextNode(Node) {} to traverse the tree and
> set all the relevant next node in each node.
>                   （1）
>                 /        \

>              (2)  *---> * (3)    Node2.next is Node3
>            /           /     \
>          (4)  *--->*(5)* -->*（6） Node4.next is Node5, Node5.next is Node6
>             \                   \
>            (7)   * -------> *   (8)  Node7.next is Node8
>
> Happy Coding,
> Seabook

[Seabook]

Thanks for the solution. It's good to have you in the group.

Here is my solution:

package com.seabook.google.algorithm;

import java.util.ArrayList;
import java.util.List;

public class TreeMutation {

    public static void main(String[] args) {

        TreeMutation treeMutation = new TreeMutation();
        TNode tree = treeMutation.createSampleTree();
        List<TNode> nodes = new ArrayList<TNode>();
        treeMutation.populateTree(tree, 0, nodes);
       
        printTree(tree);
    }

    public TNode createSampleTree() {
        TNode node1 = new TNode("1");
        TNode node2 = new TNode("2");
        TNode node3 = new TNode("3");
        TNode node4 = new TNode("4");
        TNode node5 = new TNode("5");
        TNode node6 = new TNode("6");
        TNode node7 = new TNode("7");

        node1.left = node2;
        //node1.right = node5;
        node1.right = node3;

        node2.left = node4;
        node3.right = node5;

        node5.left = node6;

        node5.right = node7;

        return node1;
    }

    public void populateTree(TNode tNode, int i, List<TNode> nodes) {
        if (nodes.size() != 0 && i < nodes.size()) {
            nodes.get(i).next = tNode;
            nodes.set(i, tNode);
        } else
            nodes.add(tNode);
        i++;
       
        if (tNode.left != null) {
            populateTree(tNode.left, i, nodes);
        }
       

        if (tNode.right != null) {
            populateTree(tNode.right, i, nodes);
        }
       
    }

    public static void printTree(TNode tree) {
        String left = tree.left == null ? "null" : tree.left.label;
        String right = tree.right == null ? "null" : tree.right.label;
        String next = tree.next == null ? "null" : tree.next.label;
        System.out.println(tree.label + " - [L:" + left + " R:"
                + right + " N:" + next + "]");

        if (tree.left != null) {
            printTree(tree.left);
        }

        if (tree.right != null) {
            printTree(tree.right);
        }
    }

    private class TNode {
        TNode left;
        TNode right;
        TNode next;

        String label;

        public TNode(String label) {
            this.label = label;
        }
    }
}

[Seabook]

LRU Cache, support Java Generics

public class LRUCache<K, V> {
    private Map<K, LRUCacheObject<V>> cache = new HashMap<K, LRUCacheObject<V>>();
    private static final int MAX_SIZE = 10;
   
    public void put(K key, V v) {
        // Wrapper
        LRUCacheObject<V> wrapperObj = new LRUCacheObject<V>(v);
        // cache is full, find the LRU object and replace it
        if (cache.size() == MAX_SIZE) {
            K foundKey = findLRUCacheObjKey();
            cache.remove(foundKey);
            cache.put(key, wrapperObj);
        } else {
        // otherwise, put it in
            cache.put(key, wrapperObj);
        }
           
    }
   
    private K findLRUCacheObjKey() {
        Set<Entry<K,LRUCacheObject<V>>> entries = cache.entrySet();
        Date earliest = new Date();
        K key = null;
        for (Iterator<Entry<K,LRUCacheObject<V>>> iterator = entries.iterator(); iterator.hasNext();) {
            Entry<K, LRUCacheObject<V>> entry = (Entry<K, LRUCacheObject<V>>) iterator.next();
            K tKey = entry.getKey();
            LRUCacheObject<V> temp = entry.getValue();
            if (temp.modTime.before(earliest)) {
                earliest = temp.modTime;
                key = tKey;
            }
        }
        return key;
    }

    public V get(K key) {
        //if exists, return V from the cache, modify the time
        LRUCacheObject<V> wrapperObj = cache.get(key);
       
        if (wrapperObj != null) {
            wrapperObj.resetTime();
            return wrapperObj.cacheObj;
        }
       
        // else if return null;
        return null;
    }
   
    private class LRUCacheObject<V> {
        Date modTime;
        V cacheObj;
       
        public LRUCacheObject(V obj) {
            this.cacheObj = obj;
            this.modTime = new Date();
        }
       
        public void resetTime() {
            this.modTime = new Date();
        }
       
    }
}

[Jason]

It is a bit shame that I have not contributor anything since I joined this group. I picked this one up as my start point. For question 1, I am not sure why we could not just implement by LinkedHashMap. The solution of question 2 looks pretty much the same as you guys. Anyway, I just paste my solution below:

public class LRUCache<K, V> {

  private Map<K, V> cache;

  private LinkedList<K> keyList;

  private int capacity;

  public LRUCache(int capacity) {

    this.capacity = capacity;

    this.cache = new HashMap<K, V>(capacity);

    this.keyList = new LinkedList<K>();

  }

  public synchronized void put(K key, V value) {

    int index = keyList.indexOf(key);

    if (index == -1) {

      if (capacity == keyList.size()) {

        cache.remove(keyList.poll());

      }

      cache.put(key, value);

      keyList.add(key);

    } else {

      if (index != keyList.size()) {

        keyList.remove(key);

        keyList.add(key);

      }

    }

  }

  public V get(K key) {

    return cache.get(key);

  }

  public boolean containsKey(K key) {

    return cache.containsKey(key);

  }

}

public class RandomBinaryTree {

  public static Node populateNextNode(Node root) {

    List<Node> nextNodeList = new ArrayList<Node>();

    traverseAndSetNextNode(root, 0, nextNodeList);

    return root;

  }

  private static void traverseAndSetNextNode(Node node, int level, List<Node> nextNodeList) {

    if (node == null) {

      return;

    }

    if (nextNodeList.size() <= level) {

      nextNodeList.add(level, node);

    } else {

      nextNodeList.get(level).next = node;

      nextNodeList.set(level, node);

    }

    level++;

    traverseAndSetNextNode(node.left, level, nextNodeList);

    traverseAndSetNextNode(node.right, level, nextNodeList);

  }

}

public class Node {

  Node left;

  Node right;

  Node next;

  String label;

  public Node(String label) {

    this.label = label;

  }

}

public class LRUCacheTest {

  public LRUCache<String, String> cache = new LRUCache<String, String>(3);

  @Test

  public void testLRUCache() {

    cache.put("1", "element 1");

    cache.put("2", "element 2");

    cache.put("1", "element 1");

    cache.put("4", "element 4");

    cache.put("5", "element 5");

    assertFalse("The cache should not contain element 2", cache.containsKey("2"));

    assertTrue("The cache should contain element 5", cache.containsKey("5"));

  }

}

public class RandomBinaryTreeTest {

  private Node root;

  @Before

  public void setUp() {

    root = new Node("1");

    Node node2 = new Node("2");

    Node node3 = new Node("3");

    Node node4 = new Node("4");

    Node node5 = new Node("5");

    Node node6 = new Node("6");

    Node node7 = new Node("7");

    Node node8 = new Node("8");

    root.left = node2;

    root.right = node3;

    node2.left = node4;

    node4.right = node7;

    node3.left = node5;

    node3.right = node6;

    node6.right = node8;

  }

  @Test

  public void testPopulateNextNode() {

    Node result = RandomBinaryTree.populateNextNode(root);

    Node node2 = result.left;

    Node node4 = node2.left;

    Node node5 = result.right.left;

    Node node7 = node4.right;

    assertEquals("The next of node 2 should be node 3", "3", node2.next.label);

    assertEquals("The next of node 4 should be node 5", "5", node4.next.label);

    assertEquals("The next of node 5 should be node 6", "6", node5.next.label);

    assertEquals("The next of node 7 should be node 8", "8", node7.next.label);

  }

}

[Jason]

Ignore my solution of 2nd question, I just found a bug. This is updated one.

public class LRUCacheTest {

  public LRUCache<String, String> cache = new LRUCache<String, String>(3);

  @Test

  public void testLRUCache() {

    cache.put("1", "element 1");

    cache.put("2", "element 2");

    cache.put("1", "element 1");

    cache.put("4", "element 4");

    cache.get("2");

    cache.put("5", "element 5");

    assertFalse("The cache should not contain element 1", cache.containsKey("1"));

    assertTrue("The cache should contain element 5", cache.containsKey("5"));

  }

}

public class LRUCache<K, V> {

  private Map<K, V> cache;

  private LinkedList<K> keyList;

  private int capacity;

  public LRUCache(int capacity) {

    this.capacity = capacity;

    this.cache = new HashMap<K, V>(capacity);

    this.keyList = new LinkedList<K>();

  }

  public synchronized void put(K key, V value) {

    if (!keyList.contains(key)) {

      if (capacity == keyList.size()) {

        cache.remove(keyList.poll());

      }

      cache.put(key, value);

      keyList.add(key);

    } else {

      hitCache(key);

    }

  }

  public synchronized V get(K key) {

    hitCache(key);

    return cache.get(key);

  }

  public boolean containsKey(K key) {

    return keyList.contains(key);

  }

  private void hitCache(K key) {

    if (keyList.contains(key) && keyList.getLast() != key) {

      keyList.remove(key);

      keyList.add(key);

    }

  }

}

[Seabook]

Nice solution. Use Linkedlist makes life a lot easier.

[Huanwen Qu]

Since you are implementing a cache, performance is the most important
thing.

The contains and remove operations on a LinkedList need O(n) time.
Therefore, your put and get operations needs at least O(n) time.

This is not acceptable for a cache. Put and get should take O(1) time
for a cache.

[Jason]

Thanks for your comments. I think you are right. The containsKey method could be changed to check cache map instead, but I am not exactly sure if the remove operation of LinkedList is expensive or not.

[Huanwen Qu]

I are not sure either.

[Jason]

It is nice to call it out. I think I was just lazy to implement it by myself. :)

Nice article about performance improvements in JAVA collection.

http://www.precisejava.com/javaperf/j2se/Collections.htm 

[Huanwen Qu]

Good. It shows that both contains and remove have the worst
performance.

This is the reason we have to implement our own doubly-linked list.