Thursday, March 26, 2015

circular stack

circular-stack:
    a = new
    count = 0
    i = 0
    
    push(x):
        a[i] = x
        i++
        if i == a.length:
            i = 0
        if count < a.length:
            count++
    
    pop():
        if count == 0:
            return null
        if i == 0:
            i = a.length
        i--
        count--
        return a[i]

[Hat tip to 2048]

Tuesday, March 24, 2015

if binary tree is binary search tree

It is bit tricky to get it working for duplicates, int.min and int.max values.
// works for duplicates but does not work for int.min values
is-bst(node, min = int.min, max = int.max): //checkBST(node)
    if node == null:
        return true
    if node.value <= min || max < node.value:
        return false
    return is-bst(node.left, min, node.value)
        && is-bst(node.right, node.value, max)
// works for duplicates and int.min values too
is-bst(node, min = null, max = null): //checkBST(node)
    if node == null:
        return true
    if min != null && node.value <= min
        return false
    if max != null && max < node.value:
        return false
    return is-bst(node.left, min, node.value)
        && is-bst(node.right, node.value, max))

Examples:
//1
      20
   10
10    10 --incorrect node

//2
      20
   10
10    11
    10 --incorrect

//3
      int.min --correct node

Another logic that works for duplicates. The null checks are required for int.max and int.min values.
max(left subtree) <= node.value < min(right subtree)
// inefficient
is-bst(node): //checkBST(node)
    if node == null:
        return true
    if node.left != null && right != null:
        if !(max(node.left) <= node.value < min(node.right)):
            return false
    else if node.left != null:
        if !(max(node.left) <= node.value):
            return false
    else if node.right != null:
        if !(node.value < min(node.right)):
            return false
    return is-bst(node.left) && is-bst(node.right)

max(node):
    if node == null:
        return int.min
    return math.max(node.value, max(node.left), max(node.right))

min(node):
    if node == null:
        return int.max
    return math.min(node.value, min(node.left), min(node.right))

Better way is to "bubble up" during dfs. For a node, return min and max if node's subtree is bst else null. If node's left or right subtree returns null then bubble it up.
// efficient
is-bst(node): //checkBST(node)
    if node == null:
        return true
    return get-min-max(node) != null

get-min-max(node):
    if node == null:
        throw

    // bubble up
    left, right = null
    if node.left != null:
        left = get-min-max(node.left)
        if left == null:
            return null
    if node.right != null:
        right = get-min-max(node.right)
        if right == null:
            return null

    // left.max <= node.value < right.min
    if left != null && right != null:
        if !(left.max <= node.value < right.min)):
            return null
    else if left != null:
        if !(left.max <= node.value)):
            return null
    else if right != null:
        if !(node.value < right.min)):
            return null

    // return min, max
    min, max = node.value
    if left != null:
        min = left.min
    if right != null:
        max = right.max
    return { min, max }

[Hat tip to ctci]

Friday, March 20, 2015

if binary tree is balanced

BT is balanced when difference between depths (heights) of left and right subtree is <= 1.

// inefficient
depth(node):
    if node == null:
        return 0
    return 1 + max(depth(node.left), depth(node.right))

is-balanced-bt(node):
    if node == null:
        return true
    depthleft = depth(node.left)
    depthright = depth(node.right)
    if abs(depthleft - depthright) > 1:
        return false
    return is-balanced-bt(node.left) && is-balanced-bt(node.right)

A better way is to "bubble up" the depth. For a node, if the difference in depth for left and right is 1+ then return -1 instead. If depth for either left or right is -1 then bubble -1 up.
// efficient
depth(node):
    if node == null:
        return 0
    depthleft = depth(node.left)
    if depthleft == -1
        return -1
    depthright = depth(node.right)
    if depthright == -1
        return -1
    if abs(depthleft - depthright) > 1
        return -1
    return 1 + max(depthleft, depthright)

is-balanced-bt(node):
    return depth(node) != -1

Tuesday, March 10, 2015

filter tree

Filter tree so that a node is skipped based on some condition and node's descendants become nearest ancestor's children.
input:
1
    2
    x
        x
            3a
                4
            3b

output:
1
    2
    3a
        4
    3b
to-include(node):
    // returns true or false on some condition
    returns true

node structure
node:
    string name
    node[] children

Keep a nearest ancestor pointer (initially null) and add current node to its children.
filteredTree = filter-tree(tree, null)

filter-tree(node, ancestor):
    if to-include(node):
        nodeCopy = new node(node.name)
        if ancestor != null:
            ancestor.children.add(nodeCopy)
        ancestor = nodeCopy
    foreach child in node.children:
        childAncestor = filter-tree(child, ancestor)
        if ancestor == null:
            ancestor = childAncestor
    return ancestor

The root node itself could be skipped, so the very first filtered node becomes root of filtered tree. There are cases where the hierarchy is not maintained.
input:
x
    x
        3a
            4
        3b

output:
3a
    4
    3b
input:
x
    x
        1
    x
        2

output:
1
    2

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:
            result = 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]