[FWD] 3x3 Online Solution

Link: https://www.youcandothecube.com/solve-it/3-x-3-solution

[Java] Doubly Linked List

Reference: https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html

The time complexity of remove() method of java.util.LinkedList is O(n) because Java standard LinkedList class does not expose the internal Node details for clients.

Therefore, we implement a custom DoublyLinkedList class for competitive programming. In this implementation, both time complexity of add() and of remove() are O(1).

    
    public class DoublyLinkedList<V> {
        private int size;
        private Node<V> head;
        private Node<V> tail;

        public DoublyLinkedList() {
            this.size = 0;
            this.head = new Node<V>();
            this.tail = new Node<V>();
            this.head.next = this.tail;
            this.tail.prev = this.head;
        }
        
        public void addFirst(Node<V> node) {
            this.size++;
            node.next = this.head.next;
            node.next.prev = node;
            node.prev = this.head;
            node.prev.next = node;
        }
        
        public void addLast(Node<V> node) {
            this.size++;
            node.prev = this.tail.prev;
            node.prev.next = node;
            node.next = this.tail;
            node.next.prev = node;
        }
        
        public void remove(Node<V> node) {
            if (node.prev != null && node.next != null) {
                this.size--;
                node.next.prev = node.prev;
                node.prev.next = node.next;
                node.prev = node.next = null;
            }
        }
        
        public Node<V> getFirst() {
            return isEmpty() ? null : this.head.next;
        }

        public Node<V> getLast() {
            return isEmpty() ? null : this.tail.prev;
        }
        
        public int size() {
            return this.size;    
        }
        
        public boolean isEmpty() {
            return this.size == 0;
        }
        
        @Override
        public String toString() {
            StringBuilder builder = new StringBuilder();
            Node<V> curr = this.head.next;
            while (curr != this.tail) {
                builder.append(curr.getValue());
                builder.append(" -> ");
                curr = curr.next;
            }
            builder.append("END \n");
            return builder.toString();
        }
    }

    public class Node<V> {
        private V value;
        private Node prev;
        private Node next;

        public Node(V value) {
            this.value = value;
        }

        public Node() {
            this.value = null;
        }
        
        public V getValue() {
            return this.value;
        }
        
        @Override
        public String toString() {
            return this.value == null ? null : this.value.toString();
        }
    }

[Java] Map Implementations

Documents: https://docs.oracle.com/javase/tutorial/collections/implementations/map.html


General-Purpose Map Implementations:

• HashMap
• TreeMap
• LinkedHashMap

Special-Purpose Map Implementations:

• EnumMap
• WeakHashMap
• IdentityHashMap

Concurrent Map Implementations:

• The java.util.concurrent package contains the ConcurrentMap interface, which extends Map with atomic putIfAbsent, remove, and replace methods, and the ConcurrentHashMap implementation of that interface.

---

Example: [LeetCode] 146. LRU Cache

• Link: https://leetcode.com/problems/lru-cache/description/
• HashMap + Doubly Linked List
• Illustration is here: http://androidsrc.net/lru-cache-java-implementation/

public class LRUCache {
    private int capacity;
    private Map<Integer, Node> cache;
    private DoublyLinkedList doublyLinkedList;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.doublyLinkedList = new DoublyLinkedList();
    }

    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        Node node = cache.get(key);
        doublyLinkedList.moveToTail(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            doublyLinkedList.moveToTail(node);
            node.value = value;
            return;
        }

        if (cache.size() == capacity) {
            cache.remove(doublyLinkedList.first().key);
            doublyLinkedList.remove(doublyLinkedList.first());
        }

        Node insert = new Node(key, value);
        cache.put(key, insert);
        doublyLinkedList.addToTail(insert);
    }
    
    public static class DoublyLinkedList {
        private Node head;
        private Node tail;

        public DoublyLinkedList() {
            this.head = new Node();
            this.tail = new Node();
            this.head.next = this.tail;
            this.tail.prev = this.head;
        }
        
        public Node first() {
            return head.next;
        }
        
        public void remove(Node node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }

        public void addToTail(Node node) {
            node.prev = tail.prev;
            tail.prev = node;
            node.prev.next = node;
            node.next = tail;
        }
        
        public void moveToTail(Node node) {
            remove(node);
            addToTail(node);
        }
    }
    
    public static class Node {
        public int key;
        public int value;
        public Node prev;
        public Node next;
        
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
        
        public Node() {
            this.key = -1;
            this.value = -1;
        }
    }
}

---

Example: [LeetCode] 460. LFU Cache

• Link: https://leetcode.com/problems/lfu-cache/description/
• Reference: http://dhruvbird.com/lfu.pdf

class LFUCache {
    private int capacity;
    private HashMap<Integer, Integer> valueHash;
    private Node head;
    private HashMap<Integer, Node> nodeHash;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.valueHash = new HashMap<>();
        this.nodeHash = new HashMap<>();
    }
    
    public int get(int key) {
        if (valueHash.containsKey(key)) {
            increaseFrequency(key);
            return valueHash.get(key);
        } else {
            return -1;
        }
    }
    
    public void put(int key, int value) {
        if (capacity == 0) {
            return;
        }
        if (!valueHash.containsKey(key)) {
            if (valueHash.size() == capacity) {
                removeOldestKey();
            }
            addToHead(key);
        }
        valueHash.put(key, value);    
        increaseFrequency(key);
    }
    
    private void addToHead(int key) {
        if (head == null) {
            head = new Node(0);
        } else if (head.frequency > 0) {
            Node node = new Node(0);
            node.next = head;
            head.prev = node;
            head = node;
        }
        head.bucket.add(key);
        nodeHash.put(key, head);      
    }
    
    private void increaseFrequency(int key) {
        Node node = nodeHash.get(key);
        node.bucket.remove(key);
        
        if (node.next == null) {
            node.next = new Node(node.frequency + 1);
            node.next.prev = node;
        } else if (node.next.frequency > node.frequency + 1) {
            Node middle = new Node(node.frequency + 1);
            middle.prev = node;
            middle.next = node.next;
            node.next.prev = middle;
            node.next = middle;
        }
        node.next.bucket.add(key);
        nodeHash.put(key, node.next);
        if (node.bucket.isEmpty()) {
            removeNode(node);
        }
    }
    
    private void removeOldestKey() {
        if (head == null) { 
            return;
        }
        int oldestKey = getOldestKey();
        head.bucket.remove(oldestKey);
        if (head.bucket.isEmpty()) {
            removeNode(head);   
        }
        nodeHash.remove(oldestKey);
        valueHash.remove(oldestKey);
    }
    
    private int getOldestKey() {
        for (int n : head.bucket) {
            return n;
        }
        return 0;
    }
    
    private void removeNode(Node node) {
        if (node.prev == null) {
            head = node.next;
        } else {
            node.prev.next = node.next;
        } 
        if (node.next != null) {
            node.next.prev = node.prev;
        }        
    }
    
    public static class Node {
        public int frequency;
        public LinkedHashSet<Integer> bucket;
        public Node prev;
        public Node next;
        
        public Node(int frequency) {
            this.frequency = frequency;
            this.bucket = new LinkedHashSet<>();
        }
    }
}

[Java] Set Implementations

Documents: https://docs.oracle.com/javase/tutorial/collections/implementations/set.html


There are three general-purpose Set implementations:

• HashSet
• No ordering guarantees.
• TreeSet
• Implements SortedSet interface
• LinkedHashSet
• Differs from HashSet in that it maintains a doubly-linked list running through all of its entries. 
• This linked list defines the iteration ordering, which is the order in which elements were inserted into the set (insertion-order).

There are two special-purpose Set implementations:

• EnumSet
• CopyOnWriteArraySet

[FWD] Solving the 2x2x2 Rubik's Cube

Document: http://lghttp.38568.nexcesscdn.net/8013252/pdf/uploads/general_content/Rubiks_Cube_2x2x2_solving_guide.pdf


Comments:

• Step 1: Solving the first layer (white) as 3x3x3.
• Step 2: Orienting the yellow face.
• There are only seven possible cases.
• Left Soon algorithm: L' U' L U' L' U2 L
• Right Soon algorithm: R U R' U R U2 R'
• Step 3: Permuting the second layer.
• x R' U R' D2 R U' R' D2 R2 x'

[HackerRank] Practice Interview Preparation Kit: Dynamic Programming

Link: https://www.hackerrank.com/interview/interview-preparation-kit/dynamic-programming/challenges

---

1. Max Array Sum: https://www.hackerrank.com/challenges/max-array-sum/problem

Solution: Naive dynamic programming. Time = O(n), Space = O(1).

• Define 
• f(i): max subarray sum from 1 to i which contains the last element.
• g(i): max subarray sum from 1 to i which does not contain the last element.
• Answer = max(f(n), g(n)).
• Recursive formula:
• f(i) = g(i - 1) + a[i]
• g(i) = max(f(i - 1), g(i - 1)).

#!/bin/python3

import math
import os
import sys

# Complete the maxSubsetSum function below.
def maxSubsetSum(arr):
    best_w_last, best_wo_last = 0, 0
    for a in arr:
        best_w_last, best_wo_last = best_wo_last + a, max(best_w_last, best_wo_last)
    return max(best_w_last, best_wo_last)
        
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    n = int(input())
    arr = list(map(int, input().rstrip().split()))
    res = maxSubsetSum(arr)
    fptr.write(str(res) + '\n')
    fptr.close()

---

2. Candies: https://www.hackerrank.com/challenges/candies/problem

Solution: Two pass greedy algorithm. Time = O(n), Space = O(n).

#!/bin/python3

import math
import os
import sys

# Complete the candies function below.
def candies(n, r):
    c = [1 for i in range(n)]
    for i in range(1, n):
        if r[i] > r[i - 1]:
            c[i] += c[i - 1];
    for i in range(n - 2, -1, -1):
        if r[i] > r[i + 1]:
            c[i] = max(c[i + 1] + 1, c[i])
    return sum(c)    

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    n = int(input())
    arr = []
    for _ in range(n):
        arr_item = int(input())
        arr.append(arr_item)
    result = candies(n, arr)
    fptr.write(str(result) + '\n')
    fptr.close()

---

3. Abbreviation: https://www.hackerrank.com/challenges/abbr/problem

---

4. Decibinary Numbers: https://www.hackerrank.com/challenges/decibinary-numbers/problem

[ProjectEuler][Problem 215] Crack-free Walls

Problem statement:

• Origin: https://projecteuler.net/problem=215
• HackerRank: https://www.hackerrank.com/contests/projecteuler/challenges/euler215
• Solution: DP: https://github.com/Meng-Gen/ProjectEuler/blob/master/215.cc

Similar Problem (but not the same):

• Statement: https://www.hackerrank.com/challenges/lego-blocks/problem
• Solution: https://yuting-zhang.github.io/hackerrank/2017/10/18/Hackerrank-lego-blocks.html