Monday, June 27, 2016

find missing integer(s) with limited memory

Find the missing integers in 32k integers with no duplicates (range 0..32k) and with 4KB available memory?

Without the limited memory constraint:
// using sum(0..n) = n*(n+1)/2, and overflow optimization
(a):
    sum = 0
    max = 0
    for x in a:
        if x < 0:
            throw "-ve"
        sum += x
        if x > max:
            max = x
    if max == 0:
        throw
    n = max
    missing = 0
    // to avoid overflow
    if n &1 == 0:
        // n even
        missing = (n/2)*(n+1) - sum
    else:
        // n+1 even
        missing = (n)*((n+1)/2) - sum
    return missing

32k integers = 2^(10+5) integers
bool[] size = 2^(10+5) x 1B = 32KB
bitset size = 2^(10+5) KB / 2^3 = 2^12 KB = 4KB
bitset:
    bool has(x):
    set(x):
    clearall():

// 1 pass
find(file, max = 2^(10+5)):
    list missing = new
    bitset = new bitset(max)
    using stream = create(file):
        while stream.hasnext():
            x = stream.next()
            bitset.set(x)
    for x = 0, x <= max, x++:
        if !bitset.has(x):
            missing.add(x)
    return missing

With 2KB available memory?
// 1+ passes
find(file, max = 2^(10+5), available = 2^(11)):
    list missing = new
    bitset = new bitset(max)
    chunksize = available << 3      // 2KB = 2K x 8 bits
    passes = (max / chunksize) +1   // +1 is needed
    for pass = 0, pass < passes, pass++:
        start = pass *chunksize
        end = start +chunksize
        using stream = create(file):
            while stream.hasnext():
                x = stream.next()
                if !(start <= x < end):
                    continue
                bitset.set(x -start)
        for x = 0, x < chunksize, x++:
            if !bitset.has(x):
                missing.add(x +start)
        bitset.clearall()           // cannot new as limited space
    return missing

XOR method: For only 1 integer missing in n-1 integers in range 1..n and no duplicates.
// xor method
find(file, max = 2^(10+5)):
    xor1 = 0
    using stream = create(file):
        while stream.hasnext():
            x = stream.next()
            xor1 ^= x
    xor2 = 0
    for i = 0, i <= max, i++:
        xor2 ^= i
    missing = xor1 ^ xor2
    return missing
[Hat tip to PC, GFG]

Saturday, June 25, 2016

next in-order successor of node in binary search tree

//example
   4
 2       6
1 3   5    7
     5 6
node:
    left, right
    parent
    
(root, n):
    if root == null:
        throw
    next == null
    if n == null:
        // return leftmost of root
        next = root
        while next.left != null:
            next = next.left
    else if n.right != null:
        // return leftmost of right child
        next = n.right
        while next.left != null:
            next = next.left
    else:
        // go up till next is parent's right child, return its parent
        next = n
        while next.parent != null && next.parent.right == next:
            next = next.parent
        next = next.parent        
    return next
[Hat tip to ctci]

get max profit given matrix of profit for days and pachinkos

//matrix
 --days-->
|
pachinkos
|

//example
   d1 d2 d3
p1 -1  2  1
p2  1 -1  2
p3 -2  1  3
constraints:
- only 1 pachinko per day
- from pachinko i, only pachinkos i-1 and i+1 can be visited
- from last pachinko, first pachinko can be visited and vice versa
- pachinko can be visited only once

note:
- the recursive function returns null instead of 0 as matrix has -ve profits.
(matrix):
    if matrix == null || matrix.length() == 0 || matrix[0].length() == 0:
        throw //or return null
    maxprofit = null
    days = matrix.length()
    pachinkos = matrix[0].length()
    bool[] visited = new
    for pachinko = 0, pachinko < pachinkos, pachinko++:
        profit = (matrix, day: 0, days, pachinko, pachinkos, visited)
        if maxprofit == null || profit > maxprofit:
            maxprofit = profit
    return maxprofit

int? (matrix, day, days, pachinko, pachinkos, visited):
    if day == days:
        return null
    if !(0 <= day < days):
        return null
    if pachinko == -1:
        pachinko = pachinkos-1
    if pachinko == pachinkos:
        pachinko = 0
    if !(0 <= pachinko < pachinkos):
        return null
    if visited[pachinko]:
        return null
    profit = matrix[day][pachinko]
    visited[pachinko] = true
    maxNextDayProfit = null
    nextdayProfit = (matrix, day+1, days, pachinko-1, pachinkos, visited)
    if maxNextDayProfit == null || nextdayProfit > maxNextDayProfit:
        maxNextDayProfit = nextdayProfit
    nextdayProfit = (matrix, day+1, days, pachinko+1, pachinkos, visited)
    if maxNextDayProfit == null || nextdayProfit > maxNextDayProfit:
        maxNextDayProfit = nextdayProfit
    if maxNextDayProfit != null:
        profit += maxNextDayProfit
    visited[pachinko] = false
    return profit
[Hat tip to SM]

Friday, June 24, 2016

swap nodes in linked list

Without swapping just the data/value.

- n1, n2 are apart (1+ nodes).
- n1, n2 are adjacent i.e. n1->n2 or n2->n1.
- n1, n2 could be head or tail.
- n1, n2 may not exist in linked list.
//case 1:
pn1-n1-an1
pn2-n2-an2

//case 2:
pn1-n1-n2-x
//case 3:
pn2-n2-n1-x

In each cash, n1 or n2 could be head or tail.
For singly linked list:
singly-linkedlist:
    node head, tail
    
    swap(n1, n2):
        if head == null || n1 == null || n2 == null:
            throw
        if n1 == n2:
            return
        pn1 = previous(n1)
        pn2 = previous(n2)
        if n1.next == n2:
            // n1->n2
            if pn1 != null:
                pn1.next = n2
            n1.next = n2.next
            n2.next = n1            
        else if n2.next == n1:
            // n2->n1
            if pn2 != null:
                pn2.next = n1
            n2.next = n1.next
            n1.next = n2
        else:
            an1 = n1.next
            an2 = n2.next
            if pn1 != null:
                pn1.next = n2
            n2.next = an1
            if pn2 != null:
                pn2.next = n1
            n1.next = an2
        // head
        if n1 == head:
            n2 = head
        else if n2 == head:
            n1 = head
        // tail
        if n1 == tail:
            n2 = tail
        else if n2 == tail:
            n1 = tail

    node previous(x):
        if head == null || x == null:
            throw
        if x == head:
            return null
        prev = null
        n = head
        while n != null:
            if n == x:
                break
            prev = n
            n = n.next
        if n == null:
            throw "x not present"
        return prev
For doubly linked list:
doubly-linkedlist:
    node head, tail
    
    swap(n1, n2):
        if head == null || n1 == null || n2 == null:
            throw
        if n1 == n2:
            return
        pn1 = previous(n1)
        pn2 = previous(n2)
        if n1.next == n2:
            // n1->n2
            x = n2.next
            if pn1 != null:
                pn1.next = n2
            n2.prev = pn1
            n1.next = x
            if x != null:
                x.prev = n1
            n2.next = n1
            n1.prev = n2
        else if n2.next == n1:
            // n2->n1
            x = n1.next
            if pn2 != null:
                pn2.next = n1
            n1.prev = pn2
            n2.next = x
            if x != null:
                x.prev = n2
            n1.next = n2
            n2.prev = n1        
        else:
            an1 = n1.next
            an2 = n2.next
            if pn1 != null:
                pn1.next = n2
            n2.prev = pn1
            n2.next = an1
            if an1 != null:
                an1.prev = n2
            if pn2 != null:
                pn2.next = n1
            n1.prev = pn2
            n1.next = an2
            if an2 != null:
                an2.prev = n1
        // head
        if n1 == head:
            n2 = head
        else if n2 == head:
            n1 = head
        // tail
        if n1 == tail:
            n2 = tail
        else if n2 == tail:
            n1 = tail
[Hat tip to PC]

Thursday, June 23, 2016

link node to its right / left neighbor for every node in binary tree

node:
    left, right
    next

(node):
    if node == null:
        throw
    q = new
    level = 0
    q.enqueue({node, level})
    while !q.empty():
        prevn = null
        while !q.isempty() && q.peek().level == level:
            n, nlevel = q.dequeue()
            // link to right
            if prevn != null:
                prevn.next = n
            prevn = n
            // link to left
            n.next = prevn
            prevn = n
            if n.left != null:
                q.enqueue({n.left, nlevel+1})
            if n.right != null:
                q.enqueue({n.right, nlevel+1})
        level++
[Hat tip to PC]

get depth of node in binary tree

nodedepth(n, x):
    if n == null || x == null:
        throw
    return nodedepth_(n, x)

nodedepth_(n, x):
    if n == null:
        return 0
    if n == x:
        return 1
    depthleft = (n.left, x)
    if depthleft != 0:
        return depthleft +1
    depthright = (n.right, x)
    if depthright != 0:
        return depthright +1
    return 0
[Hat tip to PC]

if binary tree is full

isfull(n):
    count = {value = 0}
    depth = (n, count)
    return count.value == power(2, depth) -1

(n, count):
    if n == null:
        return 0
    count.value++
    return 1 + max((n.left, count), (n.right, count))
[Hat tip to PC]

Wednesday, June 22, 2016

search word in matrix

Match word in matrix in any of 8 directions. From link.

[image from TH]
//matrix
 j---->n
i
|
|
m
- For every i,j square in matrix, try if the word matches.
- For any i,j square, the word[k] should match a[i,j] and any one of the neighboring 8 squares (excluding already matched squares) should match word[k+1].
indexs find(a, word):
    if a == null || a.length() == 0 || a[0].length() == 0:
        throw
    if word == null || word == "":
        throw
    m = a.length()
    n = a[0].length()
    for i = 0, i < m, i++:
        for j = 0, j < n, j++:
            if (a, i, j, m, n, word, squares, k: 0):
                return convert(squares, n)
    return convert(squares, n)

// return true if word is present starting with kth char in word till end
bool (a, i, j, m, n, word, squares, k):
    //this check needs to be before i, j check for a word ending in corner
    if k == word.length():
        return true
    if !((0 <= i < m) && (0 <= j < n)):
        return false
    if a[i][j] != word[k]:
        return false
    ijkey = flatten(i, j, n)
    if squares.has(ijkey):
        return false
    squares.add(ijkey)
    isnextmatch = 
           (a, i-1, j, m, n, word, squares, k+1)
        || (a, i+1, j, m, n, word, squares, k+1)
        || (a, i, j+1, m, n, word, squares, k+1)
        || (a, i, j-1, m, n, word, squares, k+1)
        || (a, i-1, j-1, m, n, word, squares, k+1)
        || (a, i-1, j+1, m, n, word, squares, k+1)
        || (a, i+1, j-1, m, n, word, squares, k+1)
        || (a, i+1, j+1, m, n, word, squares, k+1)
    if !isnextmatch:
        squares.removelast()
    return isnextmatch

// flattens i,j to an int
int flatten(i, j, n):
    return i*n + j

// unflattens int to i,j
int, int unflatten(x, n):
    return x/n, x%n

convert(squares, n):
    for x in squares:
        yield unflatten(x, n)
    
index:
    i, j
[Hat tip to SM, TH]

Sunday, June 19, 2016

longest substring with 2 unique chars

On 3rd char, reset back to 2nd char's index (first occurrence).

Same code works for 3+ unique chars too.
// example
xx xxxxx
abbcbcbdddde
|-|3 ..   ..
 |----|6  ..
   |--|4  ..
    |-|3  ..
     ||2  ..
      |---|5
       |---|5
(s, uniqueCharCount = 2):
    if s == null:
        throw
    maxstart = maxend = 0
    set unique = new
    resetindex = 0
    start = i = 0
    while i < s.length():
        c = s[i]
        if unique.has(c):
            i++
        else if unique.count() == uniqueCharCount:
            if i-start > maxend-maxstart:
                maxstart = start, maxend = i
            unique.clear()
            start = i = resetindex
        else:
            unique.add(c)
            // reset from 2nd char's index (first occurrence)
            if unique.count() == 2:
                resetindex = i
            i++
    if i-start > maxend-maxstart:
        maxstart = start, maxend = i
    return s.substring(maxstart, maxend-maxstart)
[Hat tip to SM]

Saturday, June 18, 2016

if two strings are isomorphic

// example
add
egg

adx    false
egg

paper
title

is
so

is
si
is-isomorphic(s1, s2):
    if s1 == null || s2 == null
        || s1.length() != s2.length():
        return false
    if s1 == s2:
        return true
    result = true
    map1to2, map2to1 = new
    for i = 0, i < s1.length(), i++:
        c1 = s1[i], c2 = s2[i]
        if map1to2.has(c1):
            if map1to2[c1] != c2:
                result = false
                break
        else:
            map1to2[c1] = c2
        if map2to1.has(c2):
            if map2to1[c2] != c1:
                result = false
                break
        else:
            map2to1[c2] = c1
    return result
[Hat tip to SM]