Monday, November 13, 2017

ordered hashset

OrderedHashSet:
    map     // {T, {node{T}}
    dq      // {T}
    add(x):
        if hasKey(x):
            dq.moveToEnd(map[x])
            return
        map[x] = dq.enqueue(x)
    bool hasKey(x):
        return map.hasKey(x)
    bool removeKey(x):
        if !hasKey(x):
            return false
        dq.removeNode(map[x])
        map.removeKey(x)
        return true
    [] foreach():
        for x in dq:
            yield x

// deque interface
dq:
    node enqueue(x):
    bool removeNode(node):
    moveToEnd(node):

Sunday, November 12, 2017

find shortest path for steps with obstacles

[0] is for step 1 and [n-1] for step n.
    i: 01   n = 2, length = 2
 step: 12   
value:      x don't care
steps findBestPath(obstacles, steps):
    if obstacles == null || obstacles.length() == 0:
        throw
    if steps.any(step <= 0):
        throw
    sortDesc(steps)
    best = new
    findBestPath(obstacles, steps, best)
    return best

findBestPath(obstacles, steps, best, i = a.length()):
    if i == 0:
        return true
    if hasObstacle(obstacles, i):
        return false
    for step in steps:
        best.add(step)
        if findBestPath(obstacles, steps, best, i -step):
            return true
        best.removeLast(step)
    return false

bool hasObstacle(obstacles, i):
    if !(1 <= i <= a.length()):
        return false
    return obstacles[i-1]

Tuesday, November 07, 2017

first unique char in string

char? (s):
    if s == null:
        throw
    dq = new           //{char}
    chToNodeMap = new  //{char, node{char}}
    for i = 0, i < s.length(), i++:
        ch = s[i]
        if !chToNodeMap.hasKey(ch):
            chToNodeMap[ch] = dq.enqueue(ch)
        else:
            chNode = chToNodeMap[ch]
            if chNode != null:
                dq.removeNode(chNode)
                chToNodeMap[ch] = null
    if dq.isEmpty():
        return null
    return dq.peek()

deque:
    node enqueue(T)
    bool removeNode(node)
    T peek()
    bool isEmpty()
[Hat tip to MC]

Friday, November 03, 2017

swap matrix along diagonal

00 01 02 03 04
10 11 12 13 14
20 21 22 23 24
30 31 32 33 34
40 41 42 43 44
swapRightDiagonal(m):
    // no throw for n = 0
    if m == null ||
        (m.length() > 0 && m.length() != m[0].length()):
        throw
    n = m.length()
    ni = n -1
    for layer = 0, layer < n/2, layer++:
        swap(m, layer, layer, ni -layer, ni -layer)
        for i = layer +1, i < ni -layer, i++:
            swap(m, layer, i, ni -i, ni -layer)
            swap(m, i, layer, ni -layer, ni -i)

swapLeftDiagonal(m):
    // no throw for n = 0
    if m == null ||
        (m.length() > 0 && m.length() != m[0].length()):
        throw
    n = m.length()
    ni = n -1
    for layer = 0, layer < n/2, layer++:
        swap(m, ni -layer, layer, layer, ni -layer)
        for i = layer +1, i < ni -layer, i++:
            swap(m, i, layer, layer, i)
            swap(m, ni -layer, i, i, ni -layer)

swap(m, ai, aj, bi, bj):
    temp = m[ai][aj]
    m[ai][aj] = m[bi][bj]
    m[bi][bj] = temp

rotate matrix

clockwise 90 degrees.
m
00 01 02 03
10 11 12 13
20 21 22 23
30 31 32 33

// right = top
00 01 02 03
         13
         23
rotate90C(m):
    // no throw for n = 0
    if m == null || 
        (m.length() > 0 && m.length() != m[0].length()):
        throw
    n = m.length()
    for layer = 0, layer < n/2, layer++:
        for i = layer, i < n-1 -layer, i++:
            // temp = top
            temp = m[layer][i]
            // top = left
            m[layer][i] = m[n-1-i][layer]
            // left = bottom
            m[n-1-i][layer] = m[n-1-layer][n-1-i]
            // bottom = right
            m[n-1-layer][n-1-i] = m[i][n-1-layer]
            // right = temp
            m[i][n-1-layer] = temp
[Hat tip to ctci]

180 degrees.
rotate180(m):
    // no throw for n = 0
    if m == null || 
        (m.length() > 0 && m.length() != m[0].length()):
        throw
    for layer = 0, layer < n/2, layer++:
        for i = layer, i < ni -layer, i++:
            // top - bottom
            swap(m, layer, i, ni -layer, ni -i)
            // left - right
            swap(m, i, ni -layer, ni -i, layer)

Wednesday, November 01, 2017

implement hashmap

k cannot be null as cannot calculate hash of k.
hashmap:
    store = new // deque{{k, v}}[]
    
    add(k, v):
        i = index(k)
        dq = store[i]
        if dq == null:
            dq = new dq()
            store[i] = dq
        for kv in dq:
            if kv.key == k:
                kv.value = v
                return
        dq.enqueue(new {k, v})
    
    bool hasKey(k):
        dq = store[index(k)]
        if dq == null:
            return false
        for kv in dq:
            if kv.key == k:
                return true
        return false
    
    bool removeKey(k):
        i = index(k)
        dq = store[i]
        if dq == null:
            return false
        for node in dq.nodes():
            if node.kv.key == k:
                dq.removeNode(node)
                if dq.isEmpty():
                    store[i] = null
                return true
        return false
    
    // O(n)
    bool remove(v):
        for i = 0, i < store.length(), i++:
            dq = store[i]
            for node in dq.nodes():
                if node.kv.value == v:
                    dq.removeNode(node)
                    if dq.isEmpty():
                        store[i] = null
                    return true
        return false
    
    // helpers
    int index(k):
        return hash(k) %store.length()
    int hash(k):
        if k == null:
            throw
        // ...

top k facebook friends of a user

dfs using a minheap.
// dfs, time: O(nlogk), space: O(k + logn + n)
[] top(user, k):
    if user == null || k < 0:
        throw
    if k == 0:
        return []
    best = new minheap(capacity: k)
    set visited = new
    visited.add(user)
    for friend in user.friends():
        top(friend, k, best, visited)
    return best

top(user, k, best, visited):
    if visited.has(user):
        return
    visited.add(user)
    if best.count() == k:
        if user.rating() > best.top().rating():
            best.displace(user)
    else:
        best.insert(user)
    for friend in user.friends():
        top(friend, k, best, visited)

minheap:
    insert(x):
    // return current top, replace it with x and heapify
    x displace(x):
    x top(): // or peek()
bfs.
// bfs, time: O(nlogk), space: O(k + n)
[] top(user, k):
    if user == null || k < 0:
        throw
    if k == 0:
        return []
    best = new minheap(capacity: k)
    set visited = new
    visited.add(user)
    q = new
    for friend in user.friends():
        q.enqueue(friend)
    top(k, best, q, visited)
    return best

top(k, best, q, visited):
    while !q.isEmpty():
        user = q.dequeue()
        if visited.has(user):
            continue
        visited.add(user)
        if best.count() == k:
            if user.rating() > best.top().rating():
                best.displace(user)
        else:
            best.insert(user)
        for friend in user.friends():
            q.enqueue(friend)

Thursday, October 26, 2017

combinations with duplicates

For aaaa,
a
aa
aaa
aaaa

a               a
    a           aa
        a       aaa
            a   aaaa
        a X
    a X
    a X
a X
a X
a X

For aaab,
a
aa
aaa
ab
aab
aaab
b

a               a
    a           aa
        a       aaa
            b   aaab
        b       aab
    a X         aa      X
        b       aab     X
    b           ab
a X             a       X
    a           aa      X
        b       aab     X
    b           ab      X
a X             a       X
    b           ab      X
b               b
Sort the characters in s so dupes are adjacent to each. The 1st iteration needs to go through and skip the 2nd iteration onward for dupes.
combineWithDupes(in, start = 0, buffer, items)
    if start > 0:
        items.add(buffer.toString())
    for i = start, i < in.length(), i++:
        if i > start && a[i-1] == a[i]:
            continue
        buffer.append(in[i])
        combine(in, i +1, buffer, items)`
        buffer.removeLast()
Bottom-up:
[] combineWithDupes(in, i = 0)
    if i == in.length():
        return []
    ch = in[i]
    items = new
    items.add(ch)
    childItems = combineWithDupes(in, i +1)
    for item in childItems:
        items.add(ch + item)
    if childItems.firstOrDefault() != ch:
        for item in childItems:
            items.add(item)
    return items

Sunday, October 22, 2017

if string is a subsequence of another

bool (sub, s):
    if s == null || sub == null:
        throw
    if sub.length() > s.length():
        return false
    for i = 0, j = 0; i < s.length() && j < sub.length(); i++:
        if s[i] == sub[j]:
            j++
    return j == sub.length()
Follow-up: There are multiple strings to check.

Keep a ch->indexes map for s. For each ch of sub, get the first index as i which is greater than previ (i of previous ch).
(subs, s):
    subCount = 0
    cindexMap = createIndexMap(s)
    for sub in subs:
        if isSubsequence(sub, cindexMap);   
            subCount++
    
bool isSubsequence(sub, cindexMap):
    previ = -1
    for c in sub:
        if !cindexMap.hasKey(c):
            return false
        indexs = cindexMap[c]
        i = -1
        // could use binary search
        for index in indexs:
            if index > previ:
                i = index
                break
        if i == -1:
            return false
        previ = i
    return true
    
map createIndexMap(s):
    // c->indexs map, indexs is list
    cindexMap = new
    for i = 0, i < t.length(), i++:
        c = t[i]
        if !cindexMap.hasKey(c):
            indexs = new list()
            cindexMap[c] = indexs
        else:
            indexs = cindexMap[c]
        indexs.add(i)
    return cindexMap
It's easier to check by generating all sub-sequences using combinations (uses O(2^n) space).
(subs, s):
    subCount = 0
    combinations = combine(s)
    for sub in combinations:
        subSet.add(sub)
    for sub in subs:
        if subSet.has(sub):
            subCount++

// for abc, gives
// a
// ab
// abc
// ac
// b
// bc
// c
[] combine(s):
[Hat tip to LeCo]

Thursday, October 19, 2017

if binary tree is full, perfect, complete

full: each node has 0 or 2 child nodes.
// full
    x
 x     x
      x x

// not full
    x
 x     x
x     x x

bool isfull(n):
    if n == null:
        return true
    if n.left == null && n.right != null:
        return false
    if n.left != null && n.right == null:
        return false
    return (n.left) && (n.right)
perfect: tree has 2^depth -1 nodes (i.e. each level is full).
tip: The depths of left and right subtrees are equal at all levels.
// perfect
    x
 x     x
x x   x x

bool isPerfect(n):
    return depthPerfect(n) != null

int? depthPerfect(n):
    if n == null:
        return 0
    ldepth = (n.left)
    if rdepth == null:
        return null
    rdepth = (n.right)
    if rdepth == null:
        return null
    if ldepth != rdepth:
        return null
    return ldepth +1 // or rdepth +1
complete: nodes at last level are filled from left.
tip: After encountering a null child, no nodes in queue should have any children.
// complete
    x
 x     x
x x   x

// not complete
    x
 x     6
x x     7

    4
 2     6
1     5

// bfs
bool isComplete(node):
    if node == null:
        return true
    q = new
    q.enqueue(node)
    ended = false
    while !q.isEmpty():
        n = q.dequeue()
        if ended && n.left != null:
            return false
        if n.left != null:
            q.enqueue(n.left)
        else:
            ended = true
        if ended && n.right != null:
            return false
        if n.right != null:
            q.enqueue(n.right)
        else:
            ended = true
    return true

// bfs
bool isComplete(node):
    if node == null:
        return true
    q = new
    q.enqueue(node)
    ended = false
    while !q.isEmpty():
        n = q.dequeue()
        if ended && (n.left != null || n.right != null):
            return false        
        if n.left == null && n.right != null:
            return false
        ended = n.left == null || n.right == null
        if n.left != null:
            q.enqueue(n.left)
        if n.right != null:
            q.enqueue(n.right)
    return true

// dfs
bool isComplete(n):
    return (n, count(n) -1)

bool isComplete(n, ncount, i = 0):
    if n == null:
        return true
    if i > ncount:
        return false
    // faster to check right subtree first as
    // right subtree returns false if not complete
    return isComplete(n.right, ncount, i*2 +2)
        && isComplete(n.left, ncount, i*2 +1)

int count(n):
    if n == null:
        return 0
    return 1 + count(n.left) + count(n.right)
[Hat tip to ctci]