Sunday, June 21, 2015

sort stack using a stack and temp variable

sort(stack):
    sorted = new stack()
    while !stack.empty():
        temp = stack.pop()
        while !sorted.empty() && sorted.peek() > temp:
            stack.push(sorted.pop())
        sorted.push(temp)
    while !sorted.empty():
        stack.push(sorted.pop())

[Hat tip to ctci]

implement 3 stacks in an array

- Each stack has a neighbor stack on its right.
- push(): push into current stack. If current stack is full, borrow from neighbor (which, if full, borrows from its neighbor and so on recursively) and push. If all stacks are full, throw.
- canLend(): If the stack has space, shift its elements to right and lend. If not, check its neighbor. When all stacks are full, the calls will loop around to same stack. So note the first stack that calls canLend(). Adjust start and capacity here.
- shift: shift elements to right and wrap around.
- pop(): Typical. No adjusting here.

stack:
    a
    id
    start
    capacity
    count
    stack neighbor
    
    stack(a, id, start, capacity):
        a = a
        id = id
        start = start
        capacity = capacity
        count = 0
    
    // push into current or borrow from neighbor and push
    push(T x):
        if count < capacity:
            push_(x)
        else if neighbor.canLend(id):
            capacity++
            push_(x)
        else:
            throw "stacks full"
    push_(T x):
        // last stack overflows into first
        top = (start + count) % a.length
        a[top] = x
        count++
    
    // check current stack and then neighbor
    bool canLend(id):
        // all stacks are full and back to same stack
        if id == this.id:
            return false
        if count < capacity:
            shift()
            capacity--
            start = (start +1) % a.length
            return true
        if neighbor.canLend(id):
            shift()
            start = (start +1) % a.length
            return true
        return false
    
    // move elements to right
    shift():
        if count == 0:
            return
        i = (start + count) % a.length
        for j = 0, j < count, j++:
            // wrap around, so a[i] = a[i-1] except a[0] = a[last]
            a[i] = a[(i != 0 ? i : (i = a.length)) - 1] // this works :)
            i--
        // clear for clarity
        a[i] = null
    
    T pop():
        if count == 0:
            throw "stack empty"
        count--
        top = (start + count) % a.length
        t = a[top]
        // clear for clarity
        a[top] = null
        return t
    
// n stacks with capacity capacity
stack-combined:
    stack-combined(n, capacity):
        // assume equal capacity for all
        a = new [size *n]
        stacks = new stack[n]
        for i = 0, i < n, i++:
            stacks[i] = new stack(a: a, id: i, start: n*i, capacity: n)
        // 0's neighbor is 1, (n-1)'s is 0
        for i = 0, i < n, i++:
            stacks[i].neighbor = stack[(i+1) %n]
    
    push(id, x):
        if !(0 <= id < n):
            throw
        stacks[id].push(x)
    pop(id):
        if !(0 <= id < n):
            throw
        stacks[id].pop()

[Hat tip to ctci]

Thursday, June 18, 2015

devious binary tree

This compiles.
node:
    node left
    node right
    node():
        left = right = this

Thursday, June 11, 2015

selection rank

kth smallest element (element with rank k) in an array.
// time: O(n)
selection-rank(a, rank, left = 0, right = a.length-1):
    if left > right:
        throw
    first = left
    last = right
    pivotindex = random(left, right) //left, right inclusive
    pivot = a[pivotindex]
    swap(a, pivotindex, last)
    right--
    while left <= right:
        if a[left] <= pivot:
            left++
        else:
            swap(a, left, right)
            right--
    pivotindex = left // right + 1 = left = pivotindex
    swap(a, pivotindex, last)
    if rank < pivotindex:
        return selection-rank(a, rank, first, pivotindex-1)
    else if rank > pivotindex:
        return selection-rank(a, rank, pivotindex+1, last)
    return max(a, first, pivotindex)

[Hat tip to ctci]

Sunday, June 07, 2015

get interval with max discount given discounts for intervals

There are discounts on particular time intervals. Find the interval where maximum discount is available. Time interval could be days or time.

Example:
Day 1 - 5 => 10%
Day 2 - 8 =>  5%
Day 4 - 6 => 20%

Interval with max discount:
Day 4 - 5 => 35%
interval:
    start, end
    discount

// time: O(nlogn)
getmaxdiscount(intervals):
    times = split(intervals) // O(nlogn)
    maxdiscount = getmaxdiscount(times) // O(n)
    return maxdiscount

time:
    value
    discount
    isstart
    
// split interval into time
// time: O(nlogn)
split(intervals):
    times = new
    foreach interval in intervals:
        times.add(new time(interval.start, interval.discount, true))
        times.add(new time(interval.end, interval.discount, false))
    // when value is same, the start time should come first
    return times.orderby(value, !isstart)

// time: O(nlogn)
getmaxdiscount(times):
    discount = 0
    start, end = null, maxdiscount = 0
    foreach time in times:
        if time.isstart: // time is start
            discount += time.discount
            if discount > maxdiscount:
                maxdiscount = discount
                start = time.value
                end = null
        else: // time is end
            if discount == maxdiscount:
                end = time.value
            discount -= time.discount
    return { start, end, maxdiscount }

--example:
Day 1 + 10%, 10%, {Days 1-?, 10%}
Day 2 +  5%, 15%, {Days 2-?, 15%}
Day 4 + 20%, 35%, {Days 4-?, 35%}
Day 5 - 10%, 25%, {Days 4-5, 35%} --max
Day 6 - 20%,  5%, 
Day 8 -  5%,  0%, 

There could multiple intervals with same max discount so capture the longer interval.
// time: O(nlogn)
getmaxdiscount(times):
    discount = 0
    start, end = null, maxdiscount = 0
    max = null
    foreach time in times:
        if time.isstart: // time is start
            discount += time.discount
            if discount >= maxdiscount: // = to capture longer interval
                maxdiscount = discount
                start = time.value
                end = null
        else: // time is end
            if discount == maxdiscount:
                end = time.value
                curr = new interval(start, end, maxdiscount)
                if max == null || curr > max: //operator > overloaded
                    max = curr
            discount -= time.discount
    return max

interval: icomparable
    // compare discount first, length of interval second
    compare(other):
        c = discount.compare(other.discount)
        if c == 0:
            c = (end - start).compare(other.end - other.start)
        return c

Saturday, June 06, 2015

sitemap

Create sitemap html from a tree of nodes.
- Exclude certain nodes
- No redundant tags
example:
a {parent} /a
ul
  li
    a {child} /a
  /li
/ul
// include the node in sitemap
bool isinclude(node):

Skip node and its subtree too.
sitemap(n):
    buffer = new
    if !isinclude(n):
        return buffer
    buffer.append("a" + node.value + "/a")
    childrenbuffer = new
    foreach child in n.children:
        childbuffer = sitemap(child)
        if childbuffer.length > 0:
            childrenbuffer.append("li" + childbuffer + "/li")
    if childrenbuffer.length > 0:
        buffer.append("ul" + childrenbuffer + "/ul")
    return buffer

// wrap in div
sitemap-main(n):
    return "div" + sitemap(n) + "/div"

Skip node only not its subtree. But redundant nested tags are created.
sitemap(n):
    buffer = new
    if isinclude(n):
        buffer.append("a " + node.value + "/a")
    childrenbuffer = new
    foreach child in n.children:
        childbuffer = sitemap(child)
        if childbuffer.length > 0:
            childrenbuffer.append("li" + childbuffer + "/li")
    if childrenbuffer.length > 0:
        buffer.append("ul" + childrenbuffer + "/ul")
    return buffer

Skip node only not its subtree. There are still few redundant tags.
// creates redundant tags for this example:
//  x
//      x
//          n
//
// as
//
//  ul
//    li
//      a {n} a
//    /li
//  /ul

// wrap in ul if needed
sitemap-main(n):
    tuple = sitemap(n)
    buffer = new
    if tuple.isinclude:
        // tuple.buffer is a, lis
        tuple.buffer
    else:
        // tuple.buffer is lis
        "ul" + tuple.buffer + "/ul"

sitemap(n):
    buffer = new
    if isinclude(n):
        buffer.append("a" + node.value + "/a")
    childrenbuffer = new
    foreach child in n.children:
        tuple = sitemap(child)
        childbuffer = tuple.buffer
        isinclude = tuple.isinclude
        if childbuffer.length > 0:
            if isinclude:
                // childbuffer is a, lis
                childrenbuffer.append("li" + childbuffer + "/li")
            else:
                // childbuffer is lis
                childrenbuffer.append(childbuffer)
    if childrenbuffer.length > 0:
        if isinclude(n):
            buffer.append("ul" + childrenbuffer + "/ul")
        else:
            buffer.append(childrenbuffer)
    return { buffer, isinclude(n) }

Skip node only not its subtree. No redundant tags.
// works for this example:
//  x
//      x
//          n
//
// as
//
//  a {n} /a

// wrap in ul if needed
sitemap-main(n):
    //same

sitemap(n):
    buffer = new
    if isinclude(n):
        buffer.append("a" + node.value + "/a")
    childcount = 0
    childrenbuffer = new
    foreach child in n.children:
        tuple = sitemap(child)
        childbuffer = tuple.buffer
        isinclude = tuple.isinclude
        if childbuffer.length > 0:
            // capture child
            childcount++
            singlechild = tuple
            if isinclude:
                // childbuffer is a, lis
                childrenbuffer.append("li" + childbuffer + "/li")
            else:
                // childbuffer is lis
                childrenbuffer.append(childbuffer)
    // if node is not included and only one child, bubble up child
    if !isinclude(n) && childcount == 1:
        return singlechild
    if childrenbuffer.length > 0:
        if isinclude(n):
            buffer.append("ul" + childrenbuffer + "/ul")
        else:
            buffer.append(childrenbuffer)
    return { buffer, isinclude(n) }

Saturday, May 30, 2015

heap / max heap / priority queue

Using list as a backing store. All heap-changing operations are O(logn) - occasionally O(n) when list resizes. When top has to be replaced, displace() avoids having to call delete() and insert().
// interface
heap:
    insert(T)     // uses siftup()
    T delete()    // uses siftdown()
    T displace(T) // replaces top with given value
    int size()
    T peek()
heap:
    list = new
    
    // add, siftup
    insert(x):
        list.add(x)
        if size() >= 2:
            siftup(list)
    
    // return 0th, swap(last, 0), siftdown
    delete():
        if size() == 0:
            throw
        x = list[0]
        if size() >= 2:
            swap(list, 0, size()-1)
        list.count--
        if size() >= 2:
            siftdown(list)
        return x
    
    // replace top, siftdown 
    displace(x):
        if size() == 0:
            throw
        t = list[0]
        list[0] = x
        if size() >= 2:
            siftdown(list)
        return t
    
    siftup(a):
        i = a.length-1
        while i > 0:
            parent = (i-1) /2
            if a[parent] >= a[i]:
                break
            swap(a, i, parent)
            i = parent
    
    siftdown(a):
        siftdown(a, 0)
    siftdown(a, i):
        while i < a.length:
            left = i*2 +1
            right = left+1
            max = i
            if left < a.length && a[left] > a[max]:
                max = left
            if right < a.length && a[right] > a[max]:
                max = right
            if max == i:
                break
            swap(a, i, max)
            i = max
    
    size():
        return list.count
    peek():
        if size() == 0:
            throw
        return list[0]

Saturday, May 16, 2015

make a love/ransom note from magazine(s)

// 1 magazine
(ransom, magazine):
    result = true
    map = new
    foreach r in ransom:
        while !map.has(r) || map[r] == 0:
            if !magazine.hasnext():
                result = false
                break
            m = magazine.next()
            if !map.has(m):
                map[m] = 1
            else:
                map[m]++
        map[r]--
    return result

// 1+ magazines
(ransom, magazines):
    result = true
    map = new
    magazine = magazines.next()
    foreach r in ransom:
        while !map.has(r) || map[r] == 0:
            while !magazine.hasnext(): //while to handle magazine with 0 words
                if !magazines.hasnext():
                    result = false
                    break
                magazine = magazines.next()
            if !magazine.hasnext():
                break
            m = magazine.next()
            if !map.has(m):
                map[m] = 1
            else:
                map[m]++
        map[r]--
    return result
Using word->count map for ransom.
// 1+ magazines
(ransom, magazines):
    rmap = ransom.groupby(x).tomap(x.key, x.count) //word->count map
    magazine = magazines.next()
    while rmap.keys.count > 0:
        while !magazine.hasnext(): // while to handle magazine with 0 words
            if !magazines.hasnext():
                break
            magazine = magazines.next()
        if !magazine.hasnext():
            break
        m = magazine.next()
        if rmap.has(m):
            rmap[m]--
            if rmap[m] == 0:
                rmap.remove(m)
    result = rmap.keys.count == 0:
    return result

[Hat tip to GL]

Wednesday, May 13, 2015

lru cache for n items

lru cache for n items with O(1) add, remove, has, get.

With queue, add() is not O(1), get() is difficult/hacky to implement. So deque.
// caches n recently used items
lru-cache:
    n // items
    ctor(n):
        n = n
    count = 0
    map
    q
    dq
    add(key, value):
        if map.has(key):
            // update value
            map[key] = value
            return
        if count == n:
            // remove lru item
            // handle delayed removal from queue
            lrukey = q.pop()
            while !map.has(lrukey):
                lrukey = q.pop()
            map.remove(lrukey)
            count--
        // add key
        count++
        q.push(key)
        map.add(key, value)
    add(key, value):
        if map.has(key):
            // update value only
            item = map[key]
            map[key] = {item.node, value}
            return
        if count == n:
            // remove lru item
            count--
            lrukey = dq.pop()
            map.remove(lrukey)
        // add key
        count++
        node = dq.push(key)
        map.add(key, {node, value})
    remove(key):
        if !map.has(key):
            return // or throw "error"
        count--
        // only remove from map, delay removal from queue during add
        map.remove(key)
    remove(key):
        if !map.has(key):
            return // or throw "error"
        count--
        item = map[key]
        dq.remove(item.node)
        map.remove(key)
    has(key):
        return map.has(key)
    has(key):
        return map.has(key)
    get(key):
        // difficult/hacky to implement
    get(key):
        if !map.has(key):
            return null
        // move node to end of dq
        item = map[key]
        dq.remove(item.node)
        dq.push(item.node)
        // map does not change
        return map[key].value
    count():
        return count
    foreach():
        foreach key in q:
            yield map[key]
    foreach():
        foreach key in dq:
            yield map[key].value
    
// deque interface
dq:
    // push(key) and remove(node) are used for removal in O(1) time
    node push(key):
    key pop():
    remove(node):
    push(node): //push node to end

Tuesday, May 12, 2015

kth in-order traversal node of binary tree

(node, k):
    wrapper = { count = 0 }
    return (node, k, wrapper)

(node, k, wrapper):
    if node == null: 
        return null
    x = (node.left, k, wrapper)
    if x != null:
        return x
    wrapper.count++
    if wrapper.count == k:
        return node
    return (node.right, k, wrapper)