# SE103, Week 1 HackerRank Solutions

### Multiple Choice Question 1: Minimum Bytes Per Node
Question: On a 64-bit machine, what is the minimum number of bytes per node needed to implement a Singly Linked List, assuming that each node stores a reference to its value?

**Answer**: 16

### Multiple Choice Question 2: List Operations
Question: Given the list `1->2`, what would the result look like after the following operations are applied sequentially?

Insert(3)
Insert(4)
Delete(1)

What about after setting `head.next.next.val = 5`?

**Answer**: 4->3->2 4->3->5

### Multiple Choice Question 3: Time and Space Complexity
What is the space and time complexity of the following algorithm for reversing a linked list?

def get_last(head):
    if not head or not head.next:
        return head
    return get_last(head.next)

def reverse(head):
    if not head or not head.next:
        return head
    r = reverse(head.next)
    l = get_last(r)
    head.next = None
    l.next = head
    return r

**Answer**: Time Complexity: O(n^2) Space Complexity: O(n^2)

### Multiple Choice Question 4: Execution by Hand
What is the output of running the following code with the input `head = 1 → 2 → 3 → 4 → 5, k = 3`?

def do_what(head, k):
    if not head:
        return head

    e = head
    ne = head
    i = 0
    while i < k:
        e = e.next
        if not e:
            return head
        i += 1

    while e.next:
        ne = ne.next
        e = e.next

    d = Node("d")
    d.next = ne.next
    ne.next = None
    e.next = head
    return d.next

**Answer**: 3->4->5->1->2

### Multiple Choice Question 5: Algorithm Space Complexity
What is the space complexity of the following algorithm for splitting a linked list into parts?

def splitListToParts(root, k):
    if k < 2:
        return [root]

    len_l = 0
    c = root
    while c:
        len_l += 1
        c = c.next
    binlen = int(len_l / k)
    olen = len_l - binlen * k
    blens = [binlen for i in range(k)]
    for i in range(olen):
        blens[i] += 1

    ds = [ListNode("dummy") for _ in range(k)]
    c = root
    t = 0
    b = 0
    cd = ds[0]
    while c:
        if t == blens[b]:
            b += 1
            t = 0
            cd = ds[b]
        cd.next = c
        c = c.next
        cd = cd.next
        cd.next = None
        t += 1
    return [d.next for d in ds]

**Answer**: O(k)

### Coding Question 1: Compute Length
Compute the length of the list A.

static int getLength(SinglyLinkedListNode A) {
    int length = 0;
    while (A != null) {
        A = A.next;
        length += 1;
    }
    return length;
}

# Iterate over the list until there are no more elements, incrementing a
# counter at each iteration.
def getLength(A):
    length = 0
    while A:
        A = A.next
        length += 1
    return length

### Coding Question 2: Palindrome Linked List
Given a singly linked list, determine if it is a palindrome.

class Solution {
    static SinglyLinkedListNode reverseList(SinglyLinkedListNode head) {
        if (head == null || head.next == null)
            return head;
        SinglyLinkedListNode cur = head;
        SinglyLinkedListNode next = head.next;
        cur.next = null;
        while (next != null) {
            SinglyLinkedListNode temp = next.next;
            next.next = cur;
            cur = next;
            next = temp;
        }
        return cur;
    }
    static int len(SinglyLinkedListNode A) {
        int length = 0;
        while (A != null) {
            A = A.next;
            length++;
        }
        return length;
    }
    static boolean isPalindrome(SinglyLinkedListNode A) {
        int length = len(A);
        if (length == 0 || length == 1) return true;
        int half = (length + 1) / 2;
        SinglyLinkedListNode cur = A;
        for (int i = 0; i < half; i++)
            cur = cur.next;
        SinglyLinkedListNode secondHalfReversed = reverseList(cur);
        cur = secondHalfReversed;
        while (cur != null && A != null) {
            if (cur.data != A.data)
                return false;
            cur = cur.next;
            A = A.next;
        }
        return true;
    }
};

# The key insight is that we want to iterate from both ends of the list
# simultaneously to see whether they match, but a singly linked list only
# supports fast iteration in one direction. Therefore, we need to reverse the
# right half of the list.
# Thus, the algorithm first cuts the list in half and reverses the second half.
# Then, iterate over the two halves together, and return False if one of their
# values does not match. If all values match, then the original list was a
# palindrome. Finding the halfway point of the list, reversing the list, and
# iterating over the two halves each take linear time, so the algorithm takes
# linear time overall.
def isPalindrome(A):
    def getLength(A):
        length = 0
        while A:
            A = A.next
            length += 1
        return length

    def reverseList(head):
        previous = None
        while head:
            next_head = head.next
            head.next = previous
            previous = head
            head = next_head
        return previous

    length = getLength(A)
    if length == 0 or length == 1:
        return True
    half = (length + 1) / 2
    cur = A
    for i in xrange(half):
        cur = cur.next
    secondHalfReversed = reverseList(cur)
    cur = secondHalfReversed
    while cur and A:
        if cur.data != A.data:
            return False
        cur = cur.next
        A = A.next
    return True

### Coding Question 3: Plus One Linked List
Given a non-negative integer represented as a non-empty singly linked list of digits, add one to the integer.

You may assume the integer do not contain any leading zero, except the number 0 itself.

The digits are stored such that the most significant digit is at the head of the list.

class Solution {
    static SinglyLinkedListNode reverseList(SinglyLinkedListNode head) {
        if (head == null || head.next == null)
            return head;
        SinglyLinkedListNode cur = head;
        SinglyLinkedListNode next = head.next;
        cur.next = null;
        while (next != null) {
            SinglyLinkedListNode temp = next.next;
            next.next = cur;
            cur = next;
            next = temp;
        }
        return cur;
    }
    static SinglyLinkedListNode addOne(SinglyLinkedListNode A) {
        A = reverseList(A);
        SinglyLinkedListNode cur = A;
        cur.data++;
        while (cur.data == 10) {
            cur.data = 0;
            if (cur.next != null) {
                cur = cur.next;
                cur.data++;
            } else {
                cur.next = new SinglyLinkedListNode(1);
                break;
            }
        }
        return reverseList(A);
    }
}

# The key insight is that adding one to a number represented as a linked list
# may result in the need to propagate an increment from the least sigificant
# digit upwards to the most significant digit. Since it is expensive to iterate
# a linked list backwards, the algorithm below first reverses the linked list.
# It then increments the least sigificant digit and performs any carrying
# operation that is needed, and returns the revese of the resulting list. The
# two linked list reversals and the propagation each take linear time, so the
# overall running time is O(n).
def addOne(A):
    def reverseList(head):
        previous = None
        while head:
            next_head = head.next
            head.next = previous
            previous = head
            head = next_head
        return previous

    A = reverseList(A)
    cur = A
    cur.data += 1
    while cur.data == 10:
        cur.data = 0
        if cur.next:
            cur = cur.next
            cur.data += 1
        else:
            cur.next = SinglyLinkedListNode(1)
            break
    return reverseList(A)

### Coding Question 4: LRU Cache
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(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.

An optimal can do both operations in O(1) time complexity.

Feel free to implement or use any data structures available in the standard library, unless you find a pre-built LRU Cache in the standard library.

Here is an example usage.

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

**Java**

import java.util.*;

static class LRUCache {
    class Node{
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }

        public int key;
        public int value;
        public Node prev;
        public Node next;
    }

    int capacity;
    Node evictionQueueHead;
    Node evictionQueueTail;
    Map<Integer, Node> nodes;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        nodes = new HashMap<Integer, Node>();
    }

    private void evict(Node node) {
        if (node.prev != null) {
            node.prev.next = node.next;
        }
        if (node.next != null) {
            node.next.prev = node.prev;
        }
        if (node == evictionQueueTail) {
            evictionQueueTail = evictionQueueTail.prev;
        }
        if (node == evictionQueueHead) {
            evictionQueueHead = evictionQueueHead.next;
        }
    }

    private void addToEvictionQueue(Node node) {
        if (evictionQueueTail == null) {
            evictionQueueTail = evictionQueueHead = node;
            return;
        }
        evictionQueueTail.next = node;
        node.prev = evictionQueueTail;
        node.next = null;
        evictionQueueTail = evictionQueueTail.next;
    }

    public int get(int key) {
        if (!nodes.containsKey(key)) {
            return -1; 
        }
        Node node = nodes.get(key);
        evict(node);
        addToEvictionQueue(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (!nodes.containsKey(key) && nodes.size() >= capacity) {
            // Need to evict head of queue first.
            nodes.remove(evictionQueueHead.key);
            evict(evictionQueueHead);
        }

        Node node = null;
        if (nodes.containsKey(key)) {
            evict(nodes.get(key));
            node = nodes.get(key);
            node.value = value;
        } else {
            node = new Node(key, value);
            nodes.put(key, node);
        }
        addToEvictionQueue(node);
    }
}

**Python**

# The LRU cache implementation below represents the user's data as a doubly
# linked list and a map from keys to nodes in the list.  Each node contains a
# key-value pair, and nodes are stored from least recently used to most
# recently used. Lookups for both get() and put() use the map to find the
# target node, and lookups cause the node that was accessed to move to the end
# of the linked list. If a put() occurs on a new key and the queue is full, the
# node at the beginning of the list is evicted by removing its key from the map
# and removing it from the list.
# Removing an element from a doubly linked list is O(1).
# Adding an element to the end of a doubly linked list when one maintains a
# tail pointer is O(1).
# Looking up a key in a map is O(1).
# These are the only operations used by this implementation, so it supports
# both get and put in O(1) time,
class LRUCache(object):
    # This class represents a node in a doubly linked list which is used as an
    # eviction queue for the LRU Cache.
    class Node:
        def __init__(self, key, value):
            self.key = key
            self.value = value
            self.prev = None
            self.next = None

    def __init__(self, capacity):
        # Store the capacity so that we will know when we must evict.
        self.capacity = capacity

        self.evictionQueueHead = None
        self.evictionQueueTail = None

        # Map keys to nodes in the doubly linked list. The nodes store the
        # actual values.
        self.nodes = {}

    # Remove an element from the eviction queue.
    def evict(self, node):
        if node.prev:
            node.prev.next = node.next
        if node.next:
            node.next.prev = node.prev
        if node == self.evictionQueueTail:
            self.evictionQueueTail = self.evictionQueueTail.prev
        if node == self.evictionQueueHead:
            self.evictionQueueHead = self.evictionQueueHead.next

    # Add an element to the end of the eviction queue. This method assumes that
    # the node being added is not already in the eviction queue
    def addToEvictionQueue(self, node):
        if self.evictionQueueTail == None:
            self.evictionQueueTail = self.evictionQueueHead = node
            return
        self.evictionQueueTail.next = node
        node.prev = self.evictionQueueTail
        # This node may have been attached elsewhere before.
        node.next = None
        self.evictionQueueTail = self.evictionQueueTail.next

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key not in self.nodes:
            return -1

        node = self.nodes[key]
        self.evict(node)
        self.addToEvictionQueue(node)
        return node.value

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: void
        """
        if key not in self.nodes and len(self.nodes) >= self.capacity:
            # Need to evict head of queue first.
            del self.nodes[self.evictionQueueHead.key]
            self.evict(self.evictionQueueHead)

        node = None
        if key in self.nodes:
            self.evict(self.nodes[key])
            node = self.nodes[key]
            node.value = value
        else:
            node = self.Node(key, value)
            self.nodes[key] = node
        self.addToEvictionQueue(node)