RM

calc grid min given directions

2020-07-03T12:00:00.000-07:00

Calculate min for a grid starting from top row and going down in 3 directions (down-left, down, down-right).

00 01 02 -> j
10 11 12
20 21 22

calcMin(grid):
    if grid == null
        || grid.length() == 0
        || grid[0].length() == 0:
        throw
    rows = grid.length()
    cols = grid[0].length()
    mins = new [rows, cols]
    calcMins(grid, rows, cols, mins)
    min = getMin(mins, cols)
    return min

calcMins(grid, rows, cols, mins):
    for i = 0, i < rows, i++:
        calcMin(grid, rows, cols, i, 0, mins)

calcMin(grid, rows, cols, i, j, mins):
    if !(0 <= i < rows):
        return null
    if !(0 <= j < cols):
        return null
    if mins[i][j] != null:
        return mins[i][j]
    min =
        checked(
            grid[i][j]
                + min(
                    calcMin(grid, rows, cols, i+1, j-1], mins),
                    calcMin(grid, rows, cols, i+1,   j], mins),
                    calcMin(grid, rows, cols, i+1, j+1], mins)
                    )
            )
    mins[i][j] = min
    return min

min(a, b, c):
    if a == null && b == null && c == null:
        return 0
    return
        math.min(
            a ?? int.max,
            b ?? int.max,
            c ?? int.max
            )

getMin(mins, cols):
    min = mins[0][0]
    for j = 1, j < cols, j++:
        min = math.min(min, mins[0][j])
    return min

[Hat tip to SM]

batching items with batch.tryAdd(item)

2020-01-15T02:00:00.000-08:00

Process items in batches with bool batch.tryAdd(item).

This is a bit clunky as it mixes the batch population and sending.

process(sender, items):
    batch = new
    for item in items:
        if !batch.tryAdd(item):
            if batch.any():
                sender.send(batch)
            batch = new
            if !batch.tryAdd(item):
                // poison message
                throw
    if batch.any():
        sender.send(batch)

Better as batch population is separated out.

process(sender, items):
    i = 0
    while i < items.count():
        batch = new
        while i < items.count() && batch.tryAdd(items[i]):
            i++
        if !batch.any():
            // poison message
            throw
        sender.send(batch)

find x in non-overlapping ranges

2019-12-14T01:00:00.000-08:00

range:
    min
    max

// pre-condition: ranges are sorted and are not overlapping
// O(logn)
range find(x, ranges):
    if ranges == null:
        throw
    if ranges.isEmpty():
        return nullRange
    return findInner(x, ranges)

// O(nlogn)
sort(ranges):
    ranges = ranges.sort(x => x.min)

// ranges need to be sorted
// O(n)
validate(ranges):
    if ranges.isEmpty():
        return
    prevRange = ranges[0]
    for i = 1, i < ranges.count(), i++:
        range = ranges[i]
        if !(prevRange.max < range.min):
            throw
        prevRange = range

// O(logn)
findInner(x, ranges):
    start = 0
    end = ranges.count() -1
    while start <= end:
        mid = start + (end-start)/2
        range = ranges[mid]
        if x < range.min:
            end = mid -1
        else if x > range.max:
            start = mid +1
        else:
            return range
    return nullRange

polly simple circuit breaker

2019-10-07T09:00:00.000-07:00

- Break (or open) circuit on consecutive 'n' handled exception or handled result for breakDuration interval. Throw brokenCircuitEx when circuit is open.
- When circuit is open and breakDuration has elapsed, the circuitBreaker goes into half-open state. Sample the next call:
- If it succeeds, close the circuit.
- If it fails (throws handled ex or handled result), break the circuit again.
- An unhandled ex does not alter the circuit state. An unhandled result closes the circuit.
- The ex or result that breaks the circuit is always thrown or returned. brokenCircuitEx is thrown on the next call.
- When throwing brokenCircuitEx, wrap the last exception or last result that broke the circuit.

// polly circuit breaker
brokenAt = null
count = 0

pollyCircuitBreaker_Execute(
        work, threshold, breakDuration,
        handlesException, handlesResult):
    lock(_lock):
        try:
            if isOpen():
                if lastHandledEx != null:
                    throw brokenCircuitEx(lastHandledEx)
                if lastHandledResult != null:
                    throw brokenCircuitEx(lastHandledResult)
                throw invalidStateEx()
            result = work()
            if handlesResult(result):
                if isHalfOpen():
                    breakCircuit()
                    lastHandledResult = result
                    return result
                if isClosed():
                    count++
                    if thresholdReached():
                        breakCircuit()
                        lastHandledResult = result
                    return result
                throw unsupportedEnumEx()
            // unhandled result
            closeCircuit()
            return result
        catch ex:
            if handlesException(ex):
                if isHalfOpen():
                    breakCircuit()
                    lastHandledEx = ex
                    throw
                if isClosed():
                    count++
                    if thresholdReached():
                        breakCircuit()
                        lastHandledEx = ex
                    throw
                throw unsupportedEnumEx()
            // unhandled ex
            throw

bool thresholdReached():
    return count == threshold
breakCircuit():
    brokenAt = now()
closeCircuit():
    brokenAt = null
    count = 0
    lastHandledEx = null
    lastHandledResult = null

bool isOpen():
    if isClosed():
        return false
    return brokenAt + breakDuration >= now()
bool isHalfOpen():
    if isClosed():
        return false
    return brokenAt + breakDuration < now()
bool isClosed():
    return brokenAt == null

REST idempotency for long running jobs

2019-09-28T11:00:00.000-07:00

scenarios:

- POST 202
  GET  404, 200

- POST 409

- POST 202
  GET  500
  retry POST

- POST 500
  retry POST

Due to two operations (cache, queue) there is a possibility of inconsistent state where the cache operation succeeds but the queue operation fails. One way to deal is to do a compensation operation (cache undo).

// post
response accept(request):
    item = cache.get(request.id)
    hash = hasher(request.id, request.body,
                  request.header1, request.header2, ...)
    if item == null:
        cache.insert({ id: request.id,
                       hash: hash })
        queue.send(request)
        return { statusCode: 202,
                 location: "{request.id}/status" }
    if hash != item.hash:
        return { statusCode: 409 }
    if item.statusCode == 5xx:
        updateItem(item)
        queue.send(request)
    return { statusCode: 202,
             location: "{request.id}/status" }

updateItem(item):
    item.statusCode = null
    cache.update(item)

// get
response status(id):
    item = store.get(id)
    return { statusCode: 200,
             code: item.statusCode,
             body: item.body }

// cache ttl exceeds possible retry window
cache:
    item get(id):
    insert(item):
    update(item):

store:
    item get(id):

hasher(request):
    // sha1 hash

This deals with the inconsistent state mentioned above but is unable to handle 409 conflicts in the backend. The chance of id collision is quite less. It is mainly an attack vector (attacker uses the same id but different bodies for requests in quick succession).

// post
response accept(request):
    item = cache.get(request.id)
    if item == null || item.statusCode == 5xx:
        queue.send(request)
        return { statusCode: 202,
                 location: "{request.id}/status" }
    hash = hasher(request.id, request.body,
                  request.header1, request.header2, ...)
    if hash != item.hash:
        return { statusCode: 409 }
    return { statusCode: 202,
             location: "{request.id}/status" }

// backend
process(request):
    item = cache.get(request.id)
    if item != null && item.processing:
        // drop message
        return
    if item == null:
        hash = hasher(request.id, request.body,
                      request.header1, request.header2, ...)
        cache.insert({ id: request.id,
                       hash: hash,
                       processing: true })
    // can't deal with 409 here
    if item.statusCode == 5xx:
        item.statusCode = null
        item.processing = true
        cache.updateItem(item)
    processInner(request)

// get
response status(id):
    item = store.get(id)
    return { statusCode: 200,
             code: item.statusCode,
             body: item.body }

// cache ttl exceeds possible retry window
cache:
    item get(id):
    insert(item):
    update(item):

store:
    item get(id):

hasher(request):
    // sha1 hash

dial

2019-09-19T21:00:00.000-07:00

rng = new

// dialValue: 0 - 100%
bool toDial(dialValue):
    if !(0 <= dialValue <= 100):
        throw
    r = rng.next(100) +1
    return r <= dialValue

// dialValue: 0.00 - 100.00%
bool toDial(dialValue):
    if !(0 <= dialValue <= 100):
        throw
    r = (rng.next(100_00) /100.0) +.01
    return r <= dialValue

polly retry

2019-08-06T01:00:00.002-07:00

// polly retry
pollyRetry_ExecuteAndCapture(
        work, retryCount, delayer,
        handlesException, handlesResult):
    pollyResult = new
    for i = 0, i <= retryCount, i++:
        // default if success or ends in exception
        pollyResult.finalHandledResult  = default
        pollyResult.finalException      = default
        pollyResult.faultType           = default
        pollyResult.exceptionType       = default
        if i > 0:
            delay(delayer(i))
        try:
            result = work()
            if handlesResult(result):
                pollyResult.outcome = outcome.failure
                pollyResult.faultType = faultType.handledResult
                pollyResult.finalHandledResult = result
                // retry
                continue
            else:
                pollyResult.outcome = outcome.successful
                pollyResult.result = result
                break
        catch ex:
            pollyResult.finalException = ex
            if handlesException(ex):
                pollyResult.outcome = outcome.failure
                pollyResult.faultType = faultType.handledException
                pollyResult.exceptionType = exceptionType.handled
                // swallow, retry
                continue
            else:
                // do not throw
                pollyResult.outcome = outcome.failure
                pollyResult.faultType = faultType.unhandledException
                pollyResult.exceptionType = exceptionType.unhandled
                break
    return pollyResult

// polly retry
pollyRetry_Execute(
        work, retryCount, delayer,
        handlesException, handlesResult):
    pollyResult = pollyRetry_ExecuteAndCapture(work, retryCount, delayer,
        handlesException, handlesResult)
    if pollyResult.finalException != null:
        throw pollyResult.finalException
    return pollyResult.result

find min in rotated array

2018-04-16T09:00:00.000-07:00

se
m
12
21

sme
123
231
312

int findMinRotated(a, start = 0, end = a.length() -1):
    if start > end:
        throw
    if start == end:
        return a[start]
    if start +1 == end:
        return min(a[start], a[end])
    mid = start + (end-start)/2
    if a[start] < a[mid] < a[end]:
        return a[start]
    if a[start] < a[mid]:
        return findMinRotated(a, mid, end)
    if a[mid] < a[end]:
        return findMinRotated(a, start, mid)
    throw

[Hat tip to JR]

find path out of a maze

2018-03-26T23:00:00.000-07:00

For left, right, up, down directions.

path maze(m, r = 0, c = 0):
    if m == null || m.length() == 0 || m[0].length() == 0:
        throw
    rows = m.length()
    cols = m[0].length()
    path = new
    mazeInner(m, r, c, rows, cols, path)
    return path

bool mazeInner(m, r = 0, c = 0, rows, cols,
    path, blocked = new bool[rows][cols]):
    if !(0 <= r < rows) || !(0 <= c < cols):
        return false
    if hasObstacle(m, r, c):
        return false
    if blocked[r][c]:
        return false
    if path.has(r, c):
        return false
    path.add((r, c))
    if isExit(m, r, c):
        return true
    if (m, r+1, c, rows, cols, path, visited):
        return true
    if (m, r-1, c, rows, cols, path, visited):
        return true
    if (m, r, c+1, rows, cols, path, visited):
        return true
    if (m, r, c-1, rows, cols, path, visited):
        return true
    path.removeLast()
    blocked[r][c] = true
    return false

bool isObstacle(m, r, c):
    return m[r][c] == -1
bool isExit(m, r, c):
    return m[r][c] == 1

binary tree iterators

2018-03-24T00:00:00.000-07:00

binarytreeIterator:
    stack, prevn
    ctor(tree):
        if tree == null:
            throw
        stack = new
        prevn = null
        if tree.root != null:
            stack.push(tree.root)
    
    bool hasnext():
        return stack.any()
    
    //O(n)
    bool isVisited(n, visited):
        return visited.has(n)
    
    //O(1), and O(logn) due to stack
    bool isVisited(n, prevn):
        return prevn == n
    
    // pre-order
    x current():
        if stack.isEmpty():
            throw "empty"
        n = stack.pop()
        if n.right != null:
            stack.push(n.right)
        if n.left != null:
            stack.push(n.left)
        return n.value
        
    // in-order
    x current():
        if stack.isempty():
            throw "empty"
        while stack.any():
            n, isVisited = stack.pop()
            if !isVisited && n.left != null:
                stack.push(n, isVisited: true)
                stack.push(n.left, isVisited: false)
                continue
            if n.right != null:
                stack.push(n.right, isVisited: false)
            return n
    
    // post-order
    x current():
        if stack.isEmpty():
            throw "empty"
        while stack.any():
            n = stack.pop()
            if n.left != null 
                && !isVisited(n.left, prevn) && !isVisited(n.right, prevn):
                stack.push(n)
                stack.push(n.left)
                continue
            if n.right != null && !isVisited(n.right, prevn):
                stack.push(n)
                stack.push(n.right)
                continue
            prevn = n
            return n.value
        throw "invalid op"

[Hat tip to J]

find x in sorted matrix

2018-03-05T00:00:00.000-08:00

Find x in sorted matrix (last element of row is less than first element of next row).

(row, col) find(matrix, x):
    if matrix == null
        || matrix.length() == 0
        || matrix[0].length() == 0:
        throw
    rows = matrix.length()
    cols = matrix[0].length()
    len = rows * cols
    start = 0, end = len -1
    while start <= end:
        mid = start + (end - start)/2
        i, j = toij(mid, cols)
        if x < matrix[i][j]:
            end = mid -1
        else if matrix[i][j] < x:
            start = mid +1
        else:
            return (i, j)
    return null

(i, j) toij(mid, cols):
    return (mid /cols, mid %cols)

[Hat tip to DJ]

ordered hashset

2017-11-13T10:00:00.000-08:00

OrderedHashSet:
    map     // {T, {node{T}}
    dq      // {T}
    add(x):
        if has(x):
            // don't change position in queue
            // as it's a subtle behavior, instead let
            // the caller explicity call remove(x) and add(x)
            return
        map[x] = dq.enqueue(x)
    bool has(x):
        return map.hasKey(x)
    bool remove(x):
        if !has(x):
            return false
        dq.removeNode(map[x])
        map.remove(x)
        return true
    [] foreach():
        for x in dq:
            yield x

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

find shortest path for steps with obstacles

2017-11-12T18:00:00.000-08:00

[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]

first unique char in string

2017-11-07T23:00:00.001-08:00

char? (s):
    if s == null:
        throw
    countMap = new
    for c in s:
        countMap.tryGetValue(c, out count)
        countMap[c] = count +1
    for c in s:
        if countMap[c] == 1:
            return c
    return null

char? (s):
    if s == null:
        throw
    unique = new
    repeating = new
    for c in s:
        if repeating.has(c):
            // do nothing
        else if unique.has(c):
            unique.remove(c)
            repeating.add(c)
        else:
            unique.add(c)
    for c in s:
        if unique.has(c):
            return c
    return null

char? (s):
    if s == null:
        throw
    dq = new            //{char}
    chToNodeMap = new   //{char, node{char}}
    repeating = new     //{char}
    for c in s:
        if repeating.has(c): // 3+ hit
            // do nothing
        else if chnodeMap.hasKey(c): // 2nd hit
            repeating.add(c)
            dq.deleteNode(chnodeMap[c])
            chnodeMap.removeKey(c)
        else: // 1st hit
            chnodeMap[c] = dq.enqueue(c)
    if dq.isEmpty():
        return null
    return dq.peek()

deque:
    node enqueue(T)
    bool deleteNode(node)
    T peek()
    bool isEmpty()

[Hat tip to MC]

// a        a
// abc      a
// aba      b
// abb      a
// abcbab   c
// aabb     null
char? (s):
    if s == null:
        throw
    consumed = new
    for i = s.length() -1, i >= 0, i--:
        c = s[i]
        if consumed.has(c):
            if firstUniqueChar == c:
                firstUniqueChar = null
        else:
            consumed.add(c)
            firstUniqueChar = c
    return firstUniqueChar

swap matrix along diagonal

2017-11-03T14:00:00.000-07:00

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

2017-11-03T03:00:00.000-07:00

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)

implement hashmap

2017-11-01T18:00:00.000-07:00

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
        // dq.nodes() is a copy
        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]
            if dq == null:
                continue
            // dq.nodes() is a copy
            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

2017-11-01T11:00:00.000-07:00

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)

combinations with duplicates

2017-10-26T23:00:00.000-07:00

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.

// in is sorted
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])
        combineWithDupes(in, i +1, buffer, items)`
        buffer.removeLast()

Bottom-up:

// in is sorted
[] combineWithDupes(in, i = 0)
    if i == in.length():
        yield break
    ch = in[i]
    childitems = combineWithDupes(in, i +1)
    yield ch                                    // a
    for child in childitems:                    // a, aa
        yield ch + child                        // aa, aaa
    if i +1 < in.length() && in[i] == in[i +1]:
        yield break
    for child in childitems:                    // a, aa
        yield child                             // a, aa

if string is a subsequence of another

2017-10-22T14:00:00.000-07:00

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]

if binary tree is full, perfect, complete

2017-10-19T01:00:00.000-07:00

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: // same as ^
        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, maxi, i = 0):
    if n == null:
        return true
    if i > maxi:
        return false
    // faster to check right subtree first as
    // right subtree returns false if not complete
    return isComplete(n.right, maxi, i*2 +2)
        && isComplete(n.left, maxi, i*2 +1)

int count(n):
    if n == null:
        return 0
    return 1 + count(n.left) + count(n.right)

// dfs
bool isComplete(n):
    isComplete(n, count: {value: 0}, maxi: {value: 0}, i: 0)
    return count.value < i.value +1

isComplete(n, count, maxi, i):
    if n == null:
        return
    count.value++
    maxi.value = max(maxi.value, i)
    (n.left, count, maxi, i*2 +1)
    (n.right, count, maxi, i*2 +2)

// bfs
bool isComplete(node):
    if node == null:
        return true
    q = new
    q.enqueue((node, iexp: 0))
    i = 0
    while !q.isEmpty():
        n, iexp = q.dequeue()
        if iexp > i:
            return false
        i++
        if n.left != null:
            q.enqueue((n.left, iexp*2 +1))
        if n.right != null:
            q.enqueue((n.right, iexp*2 +2))
    return true

[Hat tip to ctci]

reverse a stack with recursion

2017-10-13T12:00:00.000-07:00

// time: O(n^2), space: O(n)
(stack):
    for i = stack.size() -1, i > 0, i--:
        top = stack.pop()
        (stack, i, top)

// time: O(n), space: O(n)
(stack, i, top):
    if i == 0:
        stack.push(top)
        return
    // no need to check if stack empty
    temp = stack.pop()
    (stack, i -1, top)
    stack.push(temp)

// time: O(n^2), space: O(n)
(stack):
    if stack.isEmpty():
        return
    temp = stack.pop()
    (stack)
    insertAtBottom(stack, temp)

// time: O(n), space: O(n)
insertAtBottom(stack, x):
    if stack.isEmpty():
        stack.push(x)
        return
    temp = stack.pop()
    insertAtBottom(stack, x)
    stack.push(temp)

[Hat tip to GfG]

queue with 1 stack

2017-10-12T22:00:00.000-07:00

Using recursion and backtracking, i.e. using the method call stack as the "other" stack to hold on to the elements.

// O(n)
enqueue(x):
    if stack.isEmpty():
        stack.push(x)
        return
    temp = stack.pop()
    enqueue(x)
    stack.push(temp)

// O(1)
x dequeue():
    return stack.pop()

// O(1)
enqueue(x):
    stack.push(x)

// O(n)
x dequeue():
    temp = stack.pop()
    if stack.isEmpty():
        x = temp
    else:
        x = dequeue()
        stack.push(temp)
    return x

[Hat tip to SO]

flatten binary tree to right

2017-10-06T20:00:00.000-07:00

Flatten to node's right pointers only.

(n):
    if n == null:
        return
    if n.left != null:
        lsubtree = n.left
        rsubtree = n.right
        n.left = n.right = null
        n.right = lsubtree
        // rightmost of left subtree
        rmost = lsubtree
        while rmost.right != null:
            rmost = rmost.right
        rmost.right = rsubtree
    (n.right)

(n):
    while n != null:
        if n.left != null:
            lsubtree = n.left
            rsubtree = n.right
            n.left = n.right = null
            n.right = lsubtree
            rmost = lsubtree
            while rmost != null:
                rmost = rmost.right
            rmost.right = rsubtree
        n = n.right

[Hat tip to LeCo]

lfu cache of n items

2017-10-06T16:00:00.000-07:00

lfu cache with O(logn) get, add, delete.

lfuCache:
    map
    minheap
    n
    
    ctor(n):
        if n < 0:
            throw
        n = n
        map = new map(capacity: n)
        minheap = new minheap(n, item => item.frequency)
    
    value get(key):
        if key == null: throw
        // do not throw if key no exists
        if !has(key):
            return null // default(value)
        item = map[key]
        item.frequency++ // possible overflow
        minheap.heapify()
        return item.value
    
    add(key, value):
        if key == null: throw
        if has(key):
            item = map[key]
            item.value = value
            item.frequency = 0
            minheap.heapify()
            return
        item = {key, value, frequency: 0} // deleted item have -1 frequency
        if isfull():
            lfuitem = minheap.displace(item)
        else:
            minheap.push(item)
        map[key] = item
    
    bool delete(key):
        if key == null: throw
        // do not throw if key no exists
        if !has(key):
            return false
        item = map[key]
        item.frequency = -1 // new items have 0 frequency
        minheap.heapify()
        minheap.pop()
        map.removeKey(k)
        return true
    
    bool has(key):
        if key == null: throw
        return map.haskey(key)
    
    int count():
        return minheap.count()
    int isfull():
        return count() == n

// heapify x by keySelector
minheap:
    ctor(n, keySelector):
        n = n
        keySelector = keySelector
    push(x):
    x pop():
    // uses siftdown
    heapify():
    // returns top, replacing with x, heapify
    x displace(x):
    int count():

item:
    value
    frequency // unsigned to reduce overflow chance