The Great Tree-List Recursion Problem, LRU Cache, Search Insert Position, Longest Common Prefix, Linked List Cycle, Linked List Cycle II

First Problem ఠ_ఠ

Convert a given Binary Tree to Doubly Linked List

Solution

Inorder traversal, then link each value…

static DListNode pre = new DListNode();
public static DListNode dummy = pre;

public static void btreetolist(TreeNode r){
    if(r==null) return;
    btreetolist(r.left);
    DListNode cur = new DListNode(r);
    cur.prev = pre;
    pre.next = cur;
    pre = cur;
    btreetolist(r.right);
    }

public static void main(String[] args) {
    TreeNode root = new TreeNode(2);
    TreeNode l = new TreeNode(1);
    TreeNode r = new TreeNode(3);
    root.left = l; root.right=r;
    btreetolist(root);
    System.out.println(dummy.next.val.val);
    System.out.println(dummy.next.next.val.val);
    System.out.println(dummy.next.next.next.val.val);
}

---

The Great Tree-List Recursion Problem

Here’s the formal problem statement: Write a recursive function treeToList(Node root) that takes an ordered binary tree and rearranges the internal pointers to make a circular doubly linked list out of the tree nodes. The “previous” pointers should be stored in the “small” field and the “next” pointers should be stored in the “large” field. The list should be arranged so that the nodes are in increasing order. Return the head pointer to the new list. The operation can be done in O(n) time — essentially operating on each node once. Basically take figure-1 as input and rearrange the pointers to make figure-2.

Solution

/*
This is the simple Node class from which the tree and list
are built. This does not have any methods -- it's just used
as dumb storage by TreeList.
The code below tries to be clear where it treats a Node pointer
as a tree vs. where it is treated as a list.
 */
class Node {
    int data;
    Node small;
    Node large;

    public Node(int data) {
        this.data = data;
        small = null;
        large = null;
    }
}


/*
TreeList main methods:
-join() -- utility to connect two list nodes
-append() -- utility to append two lists
-treeToList() -- the core recursive function
-treeInsert() -- used to build the tree
 */
class TreeList {
    /*
  helper function -- given two list nodes, join them
  together so the second immediately follow the first.
  Sets the .next of the first and the .previous of the second.
     */
    public static void join(Node a, Node b) {
        a.large = b;
        b.small = a;
    }


    /*
  helper function -- given two circular doubly linked
  lists, append them and return the new list.
     */
    public static Node append(Node a, Node b) {
        // if either is null, return the other
        if (a==null) return(b);
        if (b==null) return(a);

        // find the last node in each using the .previous pointer
        Node aLast = a.small;
        Node bLast = b.small;

        // join the two together to make it connected and circular
        join(aLast, b);
        join(bLast, a);

        return(a);
    }


    /*
  --Recursion--
  Given an ordered binary tree, recursively change it into
  a circular doubly linked list which is returned.
     */
    public static Node treeToList(Node root) {
        // base case: empty tree -> empty list
        if (root==null) return(null);

        // Recursively do the subtrees (leap of faith!)
        Node aList = treeToList(root.small);
        Node bList = treeToList(root.large);

        // Make the single root node into a list length-1
        // in preparation for the appending
        root.small = root;
        root.large = root;

        // At this point we have three lists, and it's
        // just a matter of appending them together
        // in the right order (aList, root, bList)
        aList = append(aList, root);
        aList = append(aList, bList);

        return(aList);
    }


    /*
  Given a non-empty tree, insert a new node in the proper
  place. The tree must be non-empty because Java's lack
  of reference variables makes that case and this
  method messier than they should be.
     */
    public static void treeInsert(Node root, int newData) {
        if (newData<=root.data) {
            if (root.small!=null) treeInsert(root.small, newData);
            else root.small = new Node(newData);
        }
        else {
            if (root.large!=null) treeInsert(root.large, newData);
            else root.large = new Node(newData);
        }
    }


    // Do an inorder traversal to print a tree
    // Does not print the ending "\n"
    public static void printTree(Node root) {
        if (root==null) return;
        printTree(root.small);
        System.out.print(Integer.toString(root.data) + " ");
        printTree(root.large);
    }


    // Do a traversal of the list and print it out
    public static void printList(Node head) {
        Node current = head;

        while (current != null) {
            System.out.print(Integer.toString(current.data) + " ");
            current = current.large;
            if (current == head) break;
        }

        System.out.println();
    }


    // Demonstrate tree->list with the list 1..5
    public static void main(String[] args) {

        // first build the tree shown in the problem document
        // http://cslibrary.stanford.edu/109/
        Node root = new Node(4);
        treeInsert(root, 2);
        treeInsert(root, 1);
        treeInsert(root, 3);
        treeInsert(root, 5);

        System.out.println("tree:");
        printTree(root);   // 1 2 3 4 5
        System.out.println();

        System.out.println("list:");
        Node head = treeToList(root);
        printList(head);   // 1 2 3 4 5   yay!
    }
}

---

LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

LinkedHashMap Solution

private java.util.LinkedHashMap<Integer,Integer> self = new java.util.LinkedHashMap<Integer,Integer>();
private int capacity;
public LRUCache(int capacity) {
    this.capacity = capacity;
}
public int get(int key) {
    Integer val = self.get(key);
    if(val==null) return -1;
    self.remove(key);
    self.put(key,val);
    return val;
}
public void set(int key, int value) {
    Integer val = self.get(key);
    if(val==null && self.size() == capacity){
        self.remove(self.keySet().iterator().next());
    }
    else if(val!=null) self.remove(key);
    self.put(key,value);
}

Map + List Solution

private HashMap<Integer,Integer> map;
private ArrayList<Integer> list;
private final int cap;
public LRUCache(int cap){
    map = new HashMap<Integer, Integer>();
    list = new ArrayList<Integer>();
    this.cap = cap; 
}

public int get(int key){
    if(!map.containsKey(key)) return -1;
    int var = map.get(key);
    list.remove(list.indexOf(key));
    list.add(key);
    return var;
}
public void set(int key, int value){
    int val = get(key);
    map.put(key, value);
    if(val == -1){
        list.add(key);
        if(map.size()> cap){
            map.remove(list.get(0));
            list.remove(0);
        }
    }
}

---

Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

Binary Search Solution

• Aside form the obvious scan solution..

public int searchInsert(int[] A, int target) {
    int index = bsearch(A, target, 0, A.length-1);
    return index;
}
private int bsearch(int[] A, int target, int l, int r){
    int mid = (l+r) / 2;
    if(l>=r) 
    {if(A[l]<target) return l+1;
     if(A[l]>target) return l;}
    if(target == A[mid]) return mid;
    if(target > A[mid]) return bsearch(A,target,mid+1,r);
    else return bsearch(A,target,l,mid-1);
}

---

Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

Solution

public String longestCommonPrefix(String[] strs) {
    int n = strs.length;
    if(n==0) return "";
    StringBuilder sb = new StringBuilder(); 
    for(int i=0; i<strs[0].length();i++){
        char tmp = strs[0].charAt(i);
        for(String s: strs){
            if(i+1>s.length() || s.charAt(i)!=tmp) return sb.toString();
        }
        sb.append(tmp);
    }
    return sb.toString();
}

---

Linked List Cycle

Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?

Fast Slow Pointer Solution

• Edge case one: input <=1 element
• Edge case two: fast==null || fast.next==null

public boolean hasCycle(ListNode head) {
    if(head==null || head.next==null) return false;
    ListNode a = head;
    ListNode b = head;
    while(b!=null && b.next!=null){
        a = a.next;
        b = b.next.next;
        if(a==b) return true;
    }
    return false;
}

---

Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Follow up:
Can you solve it without using extra space?

Solution

• fast dis = a+b+c+b = 2 X slow dis = 2 * (a+b) -> a=c

public ListNode detectCycle(ListNode head) {
    ListNode a = head;
    ListNode b = head;
    while(b!=null && b.next!=null){
        a = a.next;
        b = b.next.next;
        if(a==b){
            a=head;
            while(a!=b){
                a=a.next;
                b=b.next;
            }
            return a;
        }
    }
    return null;
}