[misc2] #algo

cloneLinkedListWithRandomPointer.java

/*
Given a linked list where each node has two pointers, one to the next node and one to a random node in the list, clone the linked list.
1 -> 2 -> 3 -> 4 -> null
|    |    |    |
v    v    v    v
3    1    3    2
*/

// Private node class
private static class Node {
    int value;
    Node next;
    Node random;
}
    
// Copy list using extra space. Store mapping of old nodes to new nodes
public static Node cloneExtraSpace(Node n) {
    if (n == null) return n;
        
    // Map nodes in old list to equivalent nodes in new list
    HashMap<Node, Node> mapping = new HashMap<Node, Node>();
        
    // Create new linked list, minus the random node pointers. Save mapping
    // of equivalent old node to new node
    Node copy = new Node();
    Node nCurr = n, copyCurr = copy;
    mapping.put(nCurr, copyCurr);
        
    while (nCurr.next != null) {
        copyCurr.next = new Node();
        nCurr = nCurr.next;
        copyCurr = copyCurr.next;
        mapping.put(nCurr, copyCurr);
    }
        
    // Copy the random pointers. Find the random pointer in the original 
    // list and look up the equivalent using the map
    nCurr = n;
    copyCurr = copy;
    while (nCurr != null) {
        copyCurr.random = mapping.get(nCurr.random);
        nCurr = nCurr.next;
        copyCurr = copyCurr.next;
    }
        
    return copy;
}
    
// Copy list without using extra space. Interleave the nodes from the new 
// with the nodes from the original list. Then separate the new list from 
// the old
public static Node cloneNoExtraSpace(Node n) {
    if (n == null) return n;
        
    // Create new nodes in between the original nodes
    Node nCurr = n;
    while (nCurr != null) {
        Node temp = new Node();
        temp.value = nCurr.value;
        temp.next = nCurr.next;
        nCurr.next = temp;
        nCurr = nCurr.next.next;
    }
        
    // Copy random pointers
    nCurr = n;
    while (nCurr != null) {
        nCurr.next.random = nCurr.random.next;
        nCurr = nCurr.next.next;
    }
        
    // Separate new nodes from old nodes
    Node copy = n.next; 
    nCurr = n;
    while (nCurr.next != null) {
        Node tmp = nCurr.next;
        nCurr.next = nCurr.next.next;
        nCurr = tmp;
    }
        
    return copy;
}

largeModulus.java

/*
Given a list of bytes a, each representing one byte of a larger integer (ie. {0x12, 0x34, 0x56, 0x78} 
represents the integer 0x12345678), and an integer b, find a % b.
*/

// Compute the mod. We use a char array as it is equivalent to an array of 
// unsigned bytes
public static int mod(char[] a, int b) {
    // If input is null, let's just return 0
    if (a == null) return 0;
    int m = 0;
    // Start with modding the most significant byte, then repeatedly shift
    // left. This way our value never gets larger than an int
    for (int i = 0; i < a.length; i++) {
        m <<= 8;
        m += (a[i] & 0xFF);
        m %= b;
    }
    return m;
}

sumWithoutArithmeticOperator.java

/*
Given two integers, write a function to sum the numbers without using any arithmetic operators.
*/
public int sum(int a, int b) {
    if (b == 0) return a;
    int partialSum = a ^ b;
    int carry = (a & b) << 1;
    return sum(partialSum, carry);
}