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.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)
  p s
1-2-3-4-5
        f

  p s
1-2-3-4 
        f

p s
  1
  f

p s
1-2
    f
(n):
    first = n
    slow = fast = n
    prev = null
    while fast != null && fast.next != null:
        prev = slow
        slow = slow.next
        fast = fast.next.next
    if fast != null:
        prev = slow
        slow = slow.next
    if prev != null:
        prev.next = null
    second = slow
    return first, second

split linked list by even and odd nodes

(head):
    n = head
    evenhead = n
    if n != null:
        oddhead = n.next
    even = odd = null
    i = 0
    while n != null:
        if i == 0:
            if even == null:
                even.next = n
            even = n
        else:
            if odd == null:
                odd.next = n
            odd = n
        n = n.next
        i = (i+1) &1
    if even != null:
        even.next = null
    if odd != null:
        odd.next = null
    return evenhead, oddhead
[Hat tip to MA]

Sunday, August 07, 2016

construct bst from sorted array

If array has dupes then mid has to adjusted to rightmost dupe as left subtree <= node < right subtree for bst.
0123456
s  m  e
sme

01234
s m e
se
m

111
s e
 -m

11
se
-m
atobst(a):
    if a == null:
        throw
    return atobst(a, 0, a.length()-1)

// a is asc
atobst(a, start, end):
    if start > end:
        return null
    mid = start + (end-start)/2
    while mid < end && a[mid] == a[mid+1]
        mid++
    n = new node(a[mid])
    n.left = atobst(a, start, mid-1)
    n.right = atobst(a, mid+1, end)
    return n

// a is desc
atobst(a, start, end):
    if start > end:
        return null
    mid = start + (end-start)/2
    while mid > start && a[mid] == a[mid-1]
        mid--
    n = new node(a[mid])
    n.left = atobst(a, mid+1, end)
    n.right = atobst(a, start, mid-1)
    return n
[Hat tip to MA]

Thursday, August 04, 2016

find all repeating in array O(1) space

Find all repeating numbers in array of size n with range 0..n-1. Numbers could repeat any number of times. In O(1) space and O(n) time. (related to this)

The range is 0 .. n-1 and array is of size n. The array itself is used as flags by mutating it. The range is not -ve so a -ve value is used as flag. For x, a[x] is set to -ve on 1st visit if +ve, and added to dupes if -ve (after 1st visit). Note that the logic deals with item x and value a[x] where x = abs(x). As a[x] can be -ve, abs is needed.
i:   i  ..   x 
a: a[i] .. a[x] //x = abs(a[i])

For x =  2, a[2] is set to -2 from 2.
For x = -2, a[2] is -ve so added to dupes.
i: 0  1  2
a: .  2 -2
         -
//example
     - -
a: 1 2 1
i: 0 1 2
dupes: 1
// does not work if a[i] = 0
(a):
    if a == null:
        throw
    set dupes = new
    for x in a:
        x = abs(x)
        if a[x] < 0:
            dupes.add(x)
        else: // a[x] >= 0
            a[x] = -a[x]
    return dupes
When a[x] is 0, set it to -n to be used as a flag (0 cannot be used as flag). Which means a[i] of -n denotes 0 so %n to handle it.
//example
  -n
a: 0 0 0
i: 0 1 2
dupes: 0

   --n
a: 1 0 0 1
i: 0 1 2 3
dupes: 0 1
// O(n) time, O(1) space
(a):
    if a == null:
        throw
    set dupes = new
    n = a.length()
    for x in a:
        x = abs(x) %n     // to handle 0 values
        if a[x] < 0:
            dupes.add(x)
        else if a[x] > 0:
            a[x] = -a[x]
        else: //a[x] == 0 // to handle 0 values
            a[x] = -n
    return dupes