Saturday, December 27, 2014

equals

Shortest way.
public override bool equals(obj): 
    T that
    return obj != null
        && (that = obj as T) != null
        && this.x == that.x

Thursday, December 25, 2014

recursion and yield return

Get a list of nodes given a tree structure of nodes.
A
|
+--B
|
+--C
|  |
|  +--D
|
+--E
Result:
{ A, B, C, D, E }

Data structure:
node:
    string name
    list<node> children

Using recursion:
traverse(root):
    list = new
    Get(root, list)
    return list

// with list
Get(node, list):
    list.add(node)
    if node.children == null:
        return
    foreach child in node.children:
        Get(child, list)

Using recursion and yield return:
traverse(root):
    return Get(root)
    
// with yield return
Get(node):
    yield return node
    if node.children == null:
        yield break
    foreach child in node.children:
        foreach n in Get(child):
            yield return n

But it is inefficient when the tree is deep as every method call creates an iterator (see this). So the work-around is to not use recursion and save nodes in a stack with O(n) space.
traverse(root):
    return Get(root)
    
// without recursion, with yield return
Get(node):
    stack = new
    stack.push(node)
    while !stack.empty():
        var n = stack.pop()
        yield return n
        if n.children == null:
            continue
        // reverse to preserve children order
        foreach child in n.children.reverse():
            stack.push(child)


[Hat tip to RT, JS, EL]

Friday, July 25, 2014

add two string ints

"123", "4" => "127"
"99", "999" => "1098"
"9", "9" => "18"

string add(string s1, string s2):
    i = s1.length-1, j = s2.length-1
    carry = 0
    buffer = new
    while i >= 0 || j >= 0 || carry > 0:
        a = 0
        if i >= 0:
            a = s1[i] -'0'
            i--
        b = 0
        if j >= 0:
            b = s2[j] -'0'
            j--
        digit = a+b +carry
        carry = 0
        if digit >= 10:
            carry = 1
            digit -= 10
        buffer.append(digit)
    return buffer.reverse()


[Hat tip to SM]

Wednesday, April 09, 2014

merge ranges

Merges list of ranges.

(1,3), (4,6) => (1,6)
(1,3), (2,6) => (1,6)
(1,6), (2,3) => (1,6)
(1,3), (8,9) => (1,3), (8,9)
(1,3), (4,6), (8,9) => (1,6), (8,9)
(4,6), (1,2) => throw

range
    int start
    int end

range[] mergeRanges(range[] ranges):
    for i = 1..<ranges.length:
        if ranges[i-1].start > ranges[i].start:
            throw "ranges are NOT sorted by start value ascendingly"
    range[] merged = new
    start = ranges[0].start
    end = ranges[0].end
    for i = 1..<ranges.length:
        startcurr = ranges[i].start
        endcurr = range[i].end
        if end+1 >= startcurr:
            endcurr = max(end, endcurr)
        else:
            merged.add(new range(start, end))
            start = startcurr
            end = endcurr
    merged.add(new range(start, end))
    return merged


[Hat tip to SD]

Friday, February 28, 2014

cache read pattern

The basic cache read/get pattern.

// no lock on cache read, lock on cache write
get(key):
    t = null
    // get from cache
    t = cache.get(key)
    if t == null:
        lock(_lock):
            // check cache again after locking
            t = cache.get(key)
            if t == null:
                t = getTimeConsuming(key)
                // insert into cache only if not null
                if t != null:
                    cache.insert(key, t)
    return t

if graph is cyclic

For every node in graph, if a cycle exists (starting from node) then break out and return true else return false.
With only one map 'visited', it does not work. Ex: 1<-2<-3
With only one map 'path', nodes are visited multiple times for an acyclic path. Ex: 1->2->3
Two maps work. A map 'path' is used to save the path from current node. Another map 'acyclicNodes' is used to denote acyclic nodes.

Used for deadlock detection. Each process specifies order of locks required - forming a graph (directed).

graph
    list<node> nodes

node
    id
    list<node> neighbors

bool isCyclic(graph):
    map acyclicNodes = new
    foreach node in graph.nodes:
        map path = new
        if isCyclic(node, path, acyclicNodes):
            return true
    return false

bool isCyclic(node, path, acyclicNodes):
    if acyclicNodes(node.id):
        return false
    // node present in path so cyclic
    if path(node.id):
        return true
    path.add(node.id)
    foreach neighbor in node.neighbors:
        if isCyclic(neighbor, path, acyclicNodes):
            return true
    path.remove(node.id)
    // node is acyclic
    acyclicNodes.add(node.id)
    return false

Time: O(nodes + edges)
Space: O(nodes)

Friday, February 14, 2014

stack with array


stack
    a = new T[SIZE]
    i = 0
    
    push(T x):
        if i == a.length():
            resize()
        a[i++] = x
        
    T pop():
        if i == 0:
            throw "empty"
        return a[--i]
        
    resize():
        anew = new[a.length() * 2] //overflow possible
        for j=0 to <a.length():
            anew[j] = a[j]
        a = anew

Monday, February 10, 2014

queue with 2 stacks, stack with 2 queues

queue with 2 stacks. for enqueue, s2->s1 and push into s1. for dequeue, s1->s2 and pop from s2.

enqueue(T x):
    while !s2.isEmpty():
        s1.push(s2.pop())
    s1.push(x)
    
T dequeue():
    while !s1.isEmpty():
        s2.push(s1.pop())
    return s2.pop()

stack with 2 queues. for push, enqueue into non-empty queue (or q2). for pop, dequeue all from non-empty queue, enqueue into other and return last.

push(T x):
    if !q1.isEmpty():
        q = q1
    else
        q = q2
    q.enqueue(x)

T pop():
    if !q1.isEmpty():
        q = q1
        other = q2
    else
        q = q2
        other = q1
    if q.isEmpty():
        throw "empty"
    n = null
    while !q.isEmpty():
        n = q.dequeue()
        if q.isEmpty():
            break;
        other.enqueue(n)
    return n

Saturday, February 08, 2014

queue with O(1) find() and delete()

Use deque and map.

queue_mod<T>
    hashmap<T, Node> map // OR hashmap<T, queue<Node>> map for duplicates
    deque<T> dq
    
    enqueue(T x):
        n = dq.enqueue(x)
        map[x] = n
    
    T dequeue():
        x = dq.dequeue()
        map.remove(x)
        return x
    
    bool find(T x):
        return map[x] != null
    
    delete(T x):
        n = map[x]
        map.remove[x]
        dq.delete(n)

Node<T>
    T value
    Node next
    Node prev

deque<T>
    Node head, tail
    
    Node enqueue(T x):
        n = new Node(x)
        if head == tail == null:
            head = tail = n
        else
            tail.next = n
            n.prev = tail
            tail = n
        return n
    
    T dequeue():
        if head == tail == null:
            throw "empty"
        else if head == tail:
            n = head
            head = tail = null
        else
            n = head
            head = head.next
            n.next = head.prev = null
        return n.value
    
    delete(Node n):
        if n == null:
            throw "null"
        // adjust head / tail
        if head == tail == n:
            head = tail = null
        else if head == n:
            head = head.next
        else if tail == n:
            tail = tail.prev
        // handle next / prev
        prev = n.prev
        next = n.next
        if prev != null:
            prev.next = null
        if next != null:
            next.prev = null
        n.next = n.prev = null
    

[Hat tip to MB]

Tuesday, January 21, 2014

fix cyclic linked list

Last node always forms the cycle in linked list. Get the meet node first (where slow and fast pointers meet), then the last node, and null its next.

node getCyclicLinkedListMeetNode(root):
    slow = root
    fast = root
    while fast != null && fast.next != null:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    meet = null
    if slow == fast
        meet = slow
    return meet

void fixCyclicLinkedList(root):
    meet = getCyclicLinkedListMeetNode(root)
    // not cyclic
    if meet == null:
        return
    // if last node connects to root, then meet is root
    if meet == root:
        // go to last node
        last = root
        while last.next != root:
            last = last.next
    // else go to the last node from meet
    else:
        last = meet
        n = root
        while n.next != last.next:
            n = n.next
            last = last.next
    // fix
    last.next = null

cases:

// last connects to other than root

            meet
    1-->2-->3
        |   |
        -----

           meet
    1-->2-->3-->4
            |   |
            -----

// last connects to root

 meet
    1-->2-->3
    |       |
    ---------

 meet
    1-->2
    |   |
    -----

 meet
    1--
    | |
    ---