Wednesday, March 04, 2015

federal tax

bracket:
    limit
    percentage

ex: 
brackets = {
    { limit:  50k, percentage: 10% },
    { limit: 100k, percentage: 15% },
    { limit: 150k, percentage: 20% },
    { limit: 200k, percentage: 25% },
    { limit: 250k, percentage: 30% },
    { limit: 300k, percentage: 35% },
    { limit:    ∞, percentage: 40% },
}

federalTax(taxable, brackets):
    tax = 0
    prevBracketLimit = 0
    foreach bracket in brackets:
        if taxable <= prevBracketLimit:
            break
        delta = bracket.limit - prevBracketLimit
        if taxable < bracket.limit:
            delta = taxable - prevBracketLimit
        tax = tax + delta * bracket.percentage
        prevBracketLimit = bracket.limit
    return tax


[Hat tip to tax season]

Wednesday, February 18, 2015

if two strings are anagrams

isAnagram(s1, s2):
    if s1 == null || s2 == null
        return false
    if s1.length != s2.length
        return false
    result = true
    map1 = map(s1)
    map2 = map(s2)
    foreach c in map1.keys:
        count1 = map1[c]
        count2
        map2.tryGetValue(c, out count2)
        if count1 != count2:
            flag = false
            break
    return result

map(s):
    map = new
    foreach c in s:
        count
        if !map.tryGetValue(c, out count):
            map[c] = 0
        map[c]++
    return map


[Hat tip to JS]

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

ranges merge(ranges):
    merged = new
    start, end = 0
    any = false
    foreach range in ranges:
        if !any:
            any = true
            start = range.start
            end = range.end
            continue
        if start > range.start:
            throw new ex("ranges not sorted asc by start value.")
        if end >= range.start:
            end = max(end, range.end)
        else
            merged.add(new range(start, end))
            start = range.start
            end = range.end
    if any: 
        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() && q2.isEmpty():
        throw "empty"
    if !q1.isEmpty():
        q = q1
        other = q2
    else
        q = q2
        other = q1
    n = null
    while !q.isEmpty():
        n = q.dequeue()
        if q.isEmpty():
            break;
        other.enqueue(n)
    return n