Thursday, October 19, 2017

is binary tree 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 true
    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).
// 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.
// complete
    x
 x     x
x x   x

// not complete
    x
 x     x
x x     x

bool isComplete(n):
    return isComplete(n) != null

int? isComplete(n):
    if n == null:
        return 0
    if n.left == null && n.right != null:
        return null
    ldepth = depth(n.left)
    if ldepth == null:
        return null
    rdepth = depth(n.right)
    if rdepth == null:
        return null
    if abs(ldepth - rdepth) > 1:
        return null
    return max(ldepth, rdepth) +1

// returns null if abs(ldepth - rdepth) > 1, else max(ldepth, rdepth) +1.
int? depth(n):
[Hat tip to ctci]

Friday, October 13, 2017

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]

Thursday, October 12, 2017

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]

Friday, October 06, 2017

flatten binary tree to right

Flatten to node's right pointers only.
    1
   / \
  2   5
 / \   \
3   4   6


 1
  \
   2
    \
     3
      \
       4
        \
         5
          \
           6
(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)
[Hat tip to LeCo]

lfu cache of n items

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
        if count() == n:
            item = {value, frequency: 1} // deleted item have 0 frequency
            map[key] = item
            lfuitem = minheap.displace(item)
            return            
        item = {key, value, frequency: 0}
        map[key] = item
        minheap.push(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 = 0 // new items have 1 frequency
        minheap.heapify()
        minheap.pop()
        return true
    
    bool has(key):
        if key == null: throw
        return map.haskey(key)
    
    int count():
        return minheap.count()

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

Wednesday, October 04, 2017

anagram substring search

int[] anagrams(text, pattern):
    if text == null || pattern == null:
        throw
    if text.length() < pattern.length():
        throw
    anagrams = new
    map = createMap(pattern)
    wmap = new //window map
    i = 0
    while i < text.length():
        c = text[i]
        wmap[c]++
        i++
        dropi = i - pattern.length()
        if dropi >= 0:
            if iscountequal(map, wmap):
                anagrams.add(dropi)
            dropc = text[dropi]
            wmap[dropc]--
    return anagrams
012345
abcdeabdca
|--i
[Hat tip to GfG, AP]

Saturday, October 29, 2016

matrix flip

Flip row or column of an nxn matrix to get max sum in the upper left quadrant. n is even.

For nxn matrix,
[0,0] can be swapped with [0,n-1], [n-1,0], [n-1,n-1],
[0,1] can be swapped with [0,n-1 -1], [n-1, 1], [n-1,n-1 -1],
and so on.

It is possible to swap any item without changing the other elements in upper left quadrant.

So, maxij = max(a[i,j], a[i,n-1-j], a[n-1-i,j], a[n-1-i,n-1-j])
(m):
    if m == null || m.length() == 0 || m[0].length() == 0:
        throw
    if m.length() &1 != 0 || m[0].length() &1 != 0:
        throw "matrix size is not even"
    if m.length() != m[0].length():
        throw "matrix size is not equal"
    n = m.length()
    maxsum = 0
    for i = 0, i < n/2, i++:
        for i = 0, i < n/2, i++:
            maxij = max(a[i,j], a[i,n-1-j], a[n-1-i,j], a[n-1-i,n-1-j])
            maxsum += maxij
    return maxsum
[Hat tip to HR,JK]

Monday, October 03, 2016

find intersection of linked lists

O(m+n) time, O(1) space. No changes to linked lists.
(head1, head2):
    if head1 == null || head2 == null:
        return null
    count1 = getcount(head1)
    count2 = getcount(head2)
    delta = count1 - count2
    n1 = head1, n2 = head2
    if delta > 0:
        for i = 0, i < delta, i++:
            n1 = n1.next
    else if delta < 0:
        for i = 0, i < abs(delta), i++:
            n2 = n2.next
    intersection = null
    while n1 != null: // or n1 != null
        if n1 == n2:
            intersection = n1
            break
        n1 = n1.next
        n2 = n2.next
    return intersection
[Hat tip to AJ]

reentrant lock, unlock

Given two primitive locking constructs, write reentrant acquire() and release().
// blocks others
acquire(obj):
// unblocks others, throws ex if called without lock(obj) first
release(obj):
acquire(obj) should be called as early as possible. release(obj) should be called as late as possible.

acquire(obj) cannot be the 1st statement for lock(obj) to be reentrant. It is ok if 1+ threads pass the if as acquire(obj) will allow only 1st thread and block others.

Calling release(obj) without acquire(obj) will throw.
locker:
    obj
    count = 0
    thread = null
    //ctor
    locker(obj):
        obj = obj

    lock(tid):
        // any other thread gets blocked (reentrant)
        if thread != tid:
            acquire(obj)
            thread = tid
        count++
    unlock(tid):
        if thread != tid:
            throw //as release called without lock
        count--
        if count == 0:
            thread = null
            // unblocks blocked threads
            release(obj)
Used as:
lockobj1 = new locker(obj1)
lockobj1.lock() //1st
// critical section
// ok to call lock() again
lockobj1.lock() //2nd
...
lockobj1.unlock() //2nd
lockobj1.unlock() //1st
[Hat tip to PK]

Thursday, September 15, 2016

remove, remove-all in linked list

remove(v):
    if head == null:
        throw
    if head.value == v:
        head = head.next
        return true
    n = head
    while n.next != null:
        if n.next.value == v:
            n.next = n.next.next
            result = true
            break
        n = n.next
    return result

removeall(v):
    if head == null:
        throw
    count = 0
    while head != null && head.value == v:
        head = head.next
        count++
    if head != null:
        n = head
        while n.next != null:
            if n.next.value == v:
                n.next = n.next.next
                count++
            else:
                n = n.next
    return count
[Hat tip to MK]