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]

Wednesday, September 14, 2016

serialize deserialize binary tree

//examples
   4
 2   6
1 3 5 7

4 2 1 - - 3 - - 6 5 - - 7 - -

 1
2 3
 - 4
  - 5

1 2 - - 3 - 4 - 5 - - 
Serialize using pre-order traversal and recording nulls.
serialize(n):
    buffer = new buffer()
    (n, buffer)
    return buffer
(n, buffer):
    buffer.append(n == null ? "-" : n.value)
    if n == null:
        return
    (n.left, buffer)
    (n.right, buffer)
deserialize(a):
    return (a, {value = 0})
(a, i):
    if i.value >= a.length():
        return null
    x = a[i.value]
    i.value++
    if x == -1: //or null
        return null
    n = new node(x)
    n.left  = (a, i)
    n.right = (a, i)
    return n
[Hat tip to MP]

Friday, August 19, 2016

jobs with priority and sla

Each job has a priority and each priority has an sla. Return finish time if job can be honored or return false.
priority    sla (mins)
1           3
2           5
3           7
Use queue for each priority. Calculate cumulative count of jobs for a priority and its higher priority(s) and compare with slas.
//examples
Assume each job takes 1 min to finish i.e. job.time = 1.

q(sla) times
q1(3)  2: 1-1
q2(5)  2: 
q3(7)  2:
output: job(1,2,3) is accepted

q(sla) times
q1(3)  0: 
q2(5)  4: 2-2-2-2
q3(7)  4:
output: job(1,2,3) is accepted

q(sla) times
q1(3)  0: 
q2(5)  0: 
q3(7)  6: 3-3-3-3-3-3
output: job(1,2,3) is accepted

--

q(sla) times
q1(3)  0: 
q2(5)  0: 
q3(7)  7: 3-3-3-3-3-3-3
output: none is accepted

--

q(sla) times
q1(3)  0: 
q2(5)  5: 2-2-2-2-2
q3(7)  5:
output: job(3) is accepted

q(sla) times
q1(3)  3: 1-1-1
q2(5)  5: 2-2
q3(7)  7: 3-3
output: none is accepted

--

q(sla) times
q1(3)  2: 1-1
q2(5)  4: 2-2
q3(7)  6: 3-3
output: job(1,2,3) is accepted

q(sla) times
q1(3)  3: 1-1-1
q2(5)  4: 2
q3(7)  6: 3-3
output: job(2,3) is accepted

q(sla) times
q1(3)  3: 1-1-1
q2(5)  5: 2-2
q3(7)  6: 3
output: job(3) is accepted
jobQueue:
    // queues for jobs with priority 1, 2, 3
    q1, q2, q3
    // slas for jobs with priority 1, 2, 3
    sla1, sla2, sla3
    
    // O(nm) for n items and m priorities
    insert(job):
        time1 = q1.time()
        time12 = time1 + q2.time()
        time123 = time12 + q3.time()
        if job.priority == 1:
            if time1 +job.time <= sla1
                && time12 +job.time <= sla2
                && time123 +job.time <= sla3:
                q1.enqueue(job)
                return (true, time1 +job.time)
        else if job.priority == 2:
            if time12 +job.time <= sla2
                && time123 +job.time <= sla3:
                q2.enqueue(job)
                return (true, time12 +job.time)
        else if job.priority == 3:
            if time123 +job.time <= sla3:
                q3.enqueue(job)
                return (true, time123 +job.time)
        return (false, null)
    
    // O(m) for m queues
    job next():
        if !q1.empty():
            return q1.dequeue()
        else if !q2.empty():
            return q2.dequeue()
        else if !q3.empty():
            return q3.dequeue()
        return null

queue:
    q
    time
    enqueue():
        q.enqueue(job)
        time += job.time
    job dequeue():
        if !q.empty():
            job = q.dequeue()
            time -= job.time
            return job
        throw
    time():
        return time
[Hat tip to M]

Thursday, August 18, 2016

get string for binary expression tree

   +
 *   7
2 3
= "2*3+7"

   *
 +   7
2 3
= "(2+3)*7"

   /
 *   /
2 3 6 2
= "2*3/6/2"
inode:
    text(putbrackets)
valueNode: inode
    value
    text(putbrackets = true):
        return value.tostring()
operandHighPrecedenceNode: inode
    inode left
    inode right
    operand
    text(putbrackets = true):
        if left == null || right == null || operand == null:
            throw
        return left.text() + operand + right.text()
operandLowPrecedenceNode: operandHighPrecedenceNode
    text(putbrackets = true):
        return putbrackets ? "(" + base.text() + ")" : base.text()

(root):
    if root == null:
        throw
    return root.text(false)
[Hat tip to LW]

Sunday, August 14, 2016

ways from top-left to bottom-right with obstacles

// examples - x are obstacles

m:
631
321
11_
ways: 6

m:
211
1x1
11_
ways: 2

m: 
552x
x321
x11_
ways: 5

m:
1
ways: 1

m:
x
ways: 0

m: 
10xx
1000
1xxx
111_
ways: 5
Using visited is cleaner instead of using 2 negative values for obstacles and unvisited (0 can't be used for unvisited).
int (m):
    if m == null || m.length() == 0 || m[0].length() == 0:
        throw
    rows = m.length()
    cols = m[0].length()
    ti = rows-1, tj = cols-1
    // [ti,tj] could be blocked
    if m[ti,tj] < 0:
        return 0
    return (m, ti, tj, visited = new bool[rows, cols], rows, cols, 0, 0)

int (m, ti, tj, visited, rows, cols, i, j):
    if !(0 <= i < rows) || !(0 <= j < cols):
        return 0
    // obstacle
    if m[i,j] < 0:
        return 0
    if i == ti && j == tj:
        return 1
    // cached value
    if visited[i,j]:
        return m[i,j]
    visited[i,j] = true
    // 2 directions - right, bottom
    m[i,j] = 
        (m, ti, tj, visited, rows, cols, i+1, j) +
        (m, ti, tj, visited, rows, cols, i, j+1)
    return m[i,j]
[Hat tip to MA]

Thursday, August 11, 2016

print matrix in spiral manner

m:
 12345
layers = 1

m:
 12345
 67890
layers = 1

m:
 1234
 5678
 9012
layers = 2

m:
 1234
 5678
 9012
 3456
layers = 2

min(rows/cols) layers
            1      1 
            2      1
            3      2
            4      2

i.e. layers = (min(rows, cols) +1) /2
For each layer in layers, four while loops starting from location [layer, layer] print out each side of spiral (right, down, left, up). Break out if a while loop body is not executed.
(m):
    rows = m.length()
    cols = m[0].length()
    layers = (min(rows, cols) +1) /2
    while layer < layers:
        i = j = layer
        if !(i < rows -layer):
            break
        while i < rows -layer:
            print(i,j)
            i++
        i-- j++
        if !(j < cols -layer):
            break
        while j < cols -layer:
            print(i,j)
            j++
        j-- i--
        if !(i >= layer):
            break
        while i >= layer:
            print(i,j)
            i--
        i++ j--
        if !(j >= layer):
            break
        while j >= layer:
            if i == j == layer:
                break
            print(i,j)
            j--
        layer++
[Hat tip to MA]

Monday, August 08, 2016

split linked list into halves

Split such that count(first) >= count(second)
    s
1-2-3-4-5
        f

  s
1-2-3-4 
    f

s
1-2
f

s
1
f

s
-
f
(n):
    if n == null:
        return {null, null}
    first = n
    slow = fast = n
    while fast != null 
        && fast.next != null 
        && fast.next.next != null:
        slow = slow.next
        fast = fast.next.next
    second = slow.next
    slow.next = null
    return {first, second}