Friday, April 24, 2015

shuffle

Fisher-Yates shuffle, revised by Knuth edition. O(n) time.
shuffle(a):
    return shuffle(a.copy(), new rng())

// ok to modify buffer array
shuffle(buffer, rng):
    for i = buffer.length -1, i >= 0, i--:
        // rng.next(i) returns 0 to i-1, rng.next(0) is invalid
        swapindex = rng.next(i +1)
        yield return buffer[swapindex]
        // no need to swap fully as buffer[i] is not used after this iteration
        buffer[swapindex] = buffer[i]

Monday, April 20, 2015

convert spaces to %20

Convert spaces to %20 in buffer with spaces at end.
"this.is.a.test......"
"this%20is%20a%20test"
Test cases:
".test.."
"%20test"

"test..."
"test%20"

"..."
"%20"

"........."
"%20%20%20"

throw exception for:
"...test"
"..test."
3 passes: count spaces, verify actual spaces, convert spaces.

Throw if
- spaces %3 is not 0
- the spaces aren't within actual length.
convert-spaces(s):
    // count spaces
    spaces = 0
    foreach c in s:
        if c == ' ':
            spaces++
    if spaces %3 != 0:
        throw
    spaces = spaces /3
    // calculate actual length
    actual_length = s.length - 2*spaces // 2 extra characters per space
    // verify spaces within actual length
    actual_spaces = 0
    i = actual_length -1
    while i >= 0:
        if s[i] == ' ':
            actual_spaces++
        i--
    if spaces != actual_spaces:
        throw
    // convert spaces
    i = actual_length -1
    target = s.length -1
    while i >= 0:
        if s[i] == ' ':
            target -= 2
            s[target +0] = '%'
            s[target +1] = '2'
            s[target +2] = '0'
        else:
            s[target] == s[i]
        i--
        target--

Sunday, April 19, 2015

radix sort

Simple implementation of radix sort (LSB) with queues. Works for -ve numbers too as -12 %10 is -2. So 19 queues, for -9 to 9.
radix-sort(a):
    radix-sort(a, new queue[19]) // 19 for -9 to 9

radix-sort(a, queues):
    passes = get-passes(max(a))
    for pass = 0, < passes:
        radix-sort-pass(a, queues, pass)
        copy-to-a(queues, a)

radix-sort-pass(a, queues, pass):
    foreach n in a:
        radix = get-radix(n, pass)
        queues[radix + 9].enqueue(n)

// works for -ve n, -9 %10 = -9
get-radix(n, pass):
    while pass > 0 && n != 0:
        n = n /10
        pass--
    return n %10

copy-to-a(queues, a):
    i = 0
    foreach q in queues:
        while !q.empty():
            a[i++] = q.dequeue()

get-passes(n):
    passes = 0
    while n != 0:
        n = n /10
        passes++
    return passes

Time: O(nm) for m passes

Friday, April 17, 2015

if binary tree is a subtree of other

is-subtree(node1, node2):
    if node1 == null:
        throw
    if node2 == null:
        return true
    return is-subtree-recursive(node1, node2)

is-subtree-recursive(node1, node2):
    if node1 == null:
        return false
    if is-equal(node1, node2):
        return true
    return is-subtree-recursive(node1.left, node2)
        || is-subtree-recursive(node1.right, node2)

is-equal(node1, node2):
    if node1 == null && node2 == null:
        return true
    if node1 == null || node2 == null:
        return false
    return node1.value == node2.value
        && is-equal(node1.left, node2.left)
        && is-equal(node1.right, node2.right)

[Hat tip to ctci]

Monday, April 13, 2015

trie

Methods:

add-word(word)
is-word(word)
get-all-words()
get-words-by(prefix)
get-longest-words()
remove-word(word)

trienode:
    // members
    char c
    map<char, trienode> children
    int wordcount
    trienode parent
    
    // ctors
    trienode(c, parent):
        c = c
        children = new
        wordcount = 0
        parent = parent
    
    // methods
    is-word():
        return wordcount > 0

trie:
    // members
    root = new trienode(' ', parent: null)
    
    // methods
    add-word(word):
        node = root
        foreach c in word:
            child = node.children[c]
            if child == null:
                child = new trienode(c: c, parent: node)
                node.children[c] = child
            node = child
        node.wordcount++
    
    is-word(word):
        node = get-trienode-by(word)
        return node != null && node.is-word()
    
    get-all-words():
        return get-words-wrapper(root, prefix: "")
    get-words-by(prefix):
        node = get-trienode-by(prefix)
        if node != null:
            words = get-words-wrapper(node, prefix)
        else:
            words = new // empty if prefix does not exists
        return words
    get-words-wrapper(node, prefix):
        words = new
        get-words-recursive(words, node, new buffer(prefix))
        return words
    get-words-recursive(words, node, buffer):
        if node.is-word():
            words.add(buffer.tostring())
        foreach child in node.children:
            buffer.append(child.c)
            get-words-recursive(words, child, buffer):
            buffer.length--
    get-trienode-by(s):
        node = root
        foreach c in s:
            node = node.children[c]
            if node == null:
                break
        return node
    
    get-longest-words():
        words = new
        length = 0
        get-longest-words-recursive(words, root, new buffer(), ref length):
        return words
    get-longest-words-recursive(words, node, buffer, ref length):
        if node.is-word():
            if buffer.length > length:
                words.clear()
                length = buffer.length
            if buffer.length == length:
                words.add(buffer.tostring())
        foreach child in node.children:
            buffer.append(child.c)
            get-longest-words-recursive(words, child, buffer, ref length):
            buffer.length--
    
    remove-word(word):
        node = get-trienode-by(word)
        if node == null || !node.is-word():
            throw
        node.wordcount = 0
        while node.children.count == 0 && !node.is-word() && node != root:
            parent = node.parent
            parent.children.remove(node.c)
            node.parent = null
            node = parent

Sunday, April 12, 2015

queens

Arrange 8 queens on 8x8 chessboard with no intersecting row, column, or diagonal. There seems to be 92 ways.

Determine if the square can be added using already added squares. The square is in
- same row or column if it has same row or column of an already added square.
- same diagonal if the abs of difference in row and col of an already added square is same.

queens8():
    // way is one way of arranging queens
    way = new
    // ways is list of way
    ways = new
    queens8(0, way, ways)
    return ways

queens8(row, way, ways):
    if row == 8:
        // need to make copy
        ways.add(copy(way))
        return
    for col = 0, col < 8, col++:
        if !is-square-ok(row, col, way):
            continue
        way.add({row, col})
        queens8(row +1, way, ways)
        //remove last added square
        way.remove-last()

// way has the already added squares
is-square-ok(row, col, way):
    foreach square in way:
        if
            // same row (this is not needed)
            row == square.row
            // same col
            || col == square.col
            // same diagonal
            || abs(row - square.row) == abs(col - square.col):
            return false
    return true
Time: O(nn)

[Hat tip to ctci]

Thursday, April 09, 2015

ways, coins used for n cents

Count number of ways and coins used for n cents given set of coins.

coins = { 5, 10, 25 }
count-ways(n, coins):
    if n == 0:
        return 1
    if n < 0:
        return 0
    ways = 0
    foreach coin in cents:
        ways += count-ways(n-coin, coins)
    return ways
count-ways(10) =2
    (5)
        (0) =1
    (0) =1

count-ways(7) =0
    (2) =0
        (-3) =0

Bubble -1 up if count is 0 for n.
// cache[i] = int.min initially, cache[0] is for 1
count-coins(n, coins, cache):
    if n == 0:
        return 0
    if n < 0:
        return -1
    if cache[n-1] >= -1:
        return cache[n-1]
    count = 0
    foreach coin in coins:
        x = count-coins(n-coin, coins, cache)
        if x != -1:
            count += 1 + x
    // bubble -1 up
    if count == 0:
        count = -1
    cache[n-1] = count
    return count
count-coins(10) =3
    (5) =1
        (0) =0
    (0) =0

count-coins(7) =-1
    (2) =-1
        (-3)=-1

[Hat tip to ctci]

Sunday, April 05, 2015

valid n-pairs of brackets

// n=1
()

// n=2
(())
()()

// n=3
((()))
(()())
(())()
()(())
()()()
This needs a set to avoid duplicates. Space: O(pairs)
npairs(n):
    npairs(n, new buffer(), new set())

npairs(n, out, set):
    if n == 0:
        if !set.contains(out):
            set.add(out)
            print(out)
        return
    for i=0, <= out.length:
        out.append("()")
        npairs(n-1, out, set)
        out.remove(i, 2)
This does not.
npairs(n):
    npairs(n, 0, 0, new buffer())

npairs(n, left, right, out):
    if left < right:
        return
    if left+right == n+n:
        print(out)
        return
    if left < n:
        out.append("(")
        npairs(n, left+1, right, out)
        out.length--
    if right < n:
        out.append(")")
        npairs(n, left, right+1, out)
        out.length--

[Hat tip to ctci]

Friday, April 03, 2015

search magic index in sorted array

If i = a[i], then i is magic index.

Divide into two parts and search left or right. For duplicates, search both.
// search left
index: 012-3-45
array: 023-5-67

// search right
index: 012-3-45
array: ..0-1-35
search(a):
    return search(a, 0, a.length-1)

// assume no duplicates
search(a, start, end):
    if start > end:
        return -1
    mid = (start+end) /2
    if mid < a[mid]:
        // search left
        return search(a, start, mid-1)
    if mid > a[mid]:
        // search right
        return search(a, mid+1, end)
    return mid
// for duplicates, search both
index: 012-3-45
array: 000-2-55

index: 012-3-45
array: 000-4-55

// search left, and portion of right
index: 012-3-45
array: ...-5-55

// search right, and portion of left
index: 012-3-45
array: 111-1-..
// with duplicates
search(a, start, end):
    if start > end:
        return -1
    mid = (start+end) /2
    if mid < a[mid]:
        // search left first
        index = search(a, start, mid-1)
        if index != -1:
            return index
        // search portion of right
        return search(a, a[mid], end)
    if mid > a[mid]:
        // search right first
        index = search(a, mid+1, end)
        if index != -1:
            return index
        // search portion of left
        return search(a, start, a[mid])
    return mid
// worst cases
index: 012-3-45
array: 123-4-56
array: ..1-2-34

[Hat tip to ctci]

search x in sorted but rotated array

Divide into two parts. Either left or right part would be ascending. If x lies in the ascending part, search in it else search the other part. For duplicates, search both parts.
// search right for 2
// search left for 5
index: 012-3-45
array: 456-1-23

// search both for 1
index: 012-3-45
array: 222-2-12
array: 221-2-22
// a is sorted asc but rotated
search(a, x):
    return search(a, x, 0, a.length-1)

search(a, x, start, end):
    if start > end:
        return -1
    mid = (start+end) /2
    if a[mid] == x:
        return mid
    if a[start] < a[mid]:
        if a[start] <= x < a[mid]:
            return search(a, x, start, mid-1)
        else:
            return search(a, x, mid+1, end)
    else if a[mid] < a[end]:
        if a[mid] < x <= a[end]:
            return search(a, x, mid+1, end)
        else:
            return search(a, x, start, mid-1)
    // search both as a[start] == a[mid] == a[end]
    index = search(a, x, start, mid-1)
    if index != -1:
        return index
    index = search(a, x, mid+1, end)
    if index != -1:
        return index
    return -1

[Hat tip to ctci]