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

REST idempotency for long running jobs

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

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]