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'
        b = 0
        if j >= 0:
            b = s2[j] -'0'
        digit = a+b +carry
        carry = 0
        if digit >= 10:
            carry = 1
            digit -= 10
        buffer.append(digit)
        i--
        j--
    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--
    | |
    ---

Sunday, January 19, 2014

if two numbers overlap a 5x number

Needed this for battery-shallow-discharge project.

bool isOverlap5x(current, last):
    if current < last:
        return isOverlap5x(last, current)
    else if current == last:
        return current %5 == 0
    return current/5 > last/5

Monday, January 13, 2014

quicksort

For inplace, the pivot is first moved to the end, the rest of the array is partitioned, and the pivot is moved to the correct index. The original order of duplicates is NOT maintained.

// space: O(1), inplace
void quicksort(int[] array, int start, int end):
    if start >= end :
        return
    pivot = start // or random
    pivotvalue = array[pivot]
    // move pivot to end
    swap(array, pivot, end)
    // partition array
    lo = start
    hi = end - 1
    pivotindex = lo
    while lo <= hi :
        if array[lo] < pivotvalue :
            lo++
            pivotindex++
        else:
            swap(array, hi, lo)
            hi--
    // at this point: lo = hi + 1, lo = pivotindex
    // move pivot to correct index
    swap(array, pivotindex, end)
    // sort partitions
    quicksort(array, start, pivotindex - 1)
    quicksort(array, pivotindex + 1, end)


// space: O(n), not inplace
void quicksort_notinplace(int[] array, int start, int end)
    if start >= end : 
        return
    pivot = start // or random
    pivotvalue = array[pivot]
    copy = new int[end - start + 1]
    lo = 0
    hi = copy.Length - 1
    pivotindex = lo
    for (int i = start; i <= end; i++) :
        if i == pivot :
            continue
        if array[i] < pivotvalue : 
            copy[lo] = array[i]
            lo++
            pivotindex++
        else : 
            copy[hi] = array[i]
            hi--
    // at this point: lo = hi, lo = pivotindex
    copy[pivotindex] = pivotvalue
    Array.Copy(copy, 0, array, start, copy.Length)
    // sort partitions
    quicksort(array, start, start + lo - 1)
    quicksort(array, start + lo + 1, end)

Time: O(n2) worst case, O(nlogn) on average. Random pivot is better than picking start or end as pivot to sorted asc/desc values. Array with same values incurs worst case.