Monday, April 16, 2018

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]

Monday, March 26, 2018

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, visited = new bool[rows][cols]):
    if !(0 <= r < rows) || !(0 <= c < cols):
        return false
    if hasObstacle(m, r, c):
        return false
    if visited[r][c]:
        return false
    visited[r][c] = true
    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()
    return false

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

Saturday, March 24, 2018

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 = stack.pop()
            if n.left != null && !isVisited(n.left, prevn):
                stack.push(n)
                stack.push(n.left)
                continue
            if n.right != null:
                stack.push(n.right)
            prevn = n
            return n.value
        throw "invalid op"
    
    // 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]

Monday, March 05, 2018

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]

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