calc grid min given directions

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)

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

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

- 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

dial

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

// 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

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

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

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

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]

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]

first unique char in string

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

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)

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)

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.

// 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

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

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

// 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)

OR

// 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

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]