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 status 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, new status[rows, cols], rows, cols, 0, 0)

int (m, ti, tj, status, 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 status[i,j] == visited:
        return m[i,j]
    status[i,j] = visited
    // 2 directions - right, bottom
    m[i,j] = 
        (m, ti, tj, flags, rows, cols, i+1, j) +
        (m, ti, tj, flags, rows, cols, i, j+1)
    return m[i,j]

status:
    unvisited = 0,
    visited = 1
[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

find longest words in words formed by chars

words = [ "abc" , "baa" , "caan" , "an" , "banc" ]
chars = [ "a" , "a" , "n" , "c" , "b"]

output = ["caan", "banc"]

Two optimizations:
1. canFormWord() returns false when word's length is lesser than chars's length
2. canFormWord() is called only if word's length() is >= maxlen
(words, chars):
    // nulls checks omitted
    list longest = new
    charsmap = tocharmap(chars)
    maxlen = 0
    for word in words:
        if word.length() >= maxlen && canFormWord(charsmap, word, chars):
            if word.length() > maxlen:
                longest.clear()
                maxlen = word.length()
            if word.length() == maxlen:
                longest.add(word)
    return longest

tocharmap(chars):
    charsmap = new
    for c in chars:
        count = 0
        charsmap.tryget(c, out count)            
        charsmap[c] = count+1
    return charsmap

// return false early if word's char is not present in charsmap or
// if char's count is less in charsmap
canFormWord(charsmap, word, chars):
    if chars.length() < word.length():
        return false
    result = true
    wordmap = new
    for c in word:
        if !charsmap.haskey(c):
            result = false
            break
        count = 0
        wordmap.trygetvalue(c, out count)
        count++
        wordmap[c] = count
        if charsmap[c] < count:
            result = false
            break
    return result
[Hat tip to SM]

Saturday, July 30, 2016

if array is in heap property

//dfs
isminheap(a):
    if a == null:
        throw
    return isminheap(a, 0)
isminheap(a, i):
    if i >= a.length():
        return true
    left = i * 2 +1
    right = left +1
    if (left < a.length() && a[i] > a[left])
        || (right < a.length() && a[i] > a[right]):
        return false
    if !isminheap(a, left):
        return false
    if !isminheap(a, right):
        return false
    return true
//bfs
isminheap(a):
    if a == null:
        throw
    result = true
    q = new
    q.enqueue(0)
    while !q.isempty():
        i = q.dequeue()
        left = i * 2 +1
        right = left +1
        if left < a.length():
            if a[i] > a[left]:
                result = false
                break
            else:
                q.enqueue(left)
        if right < a.length():
            if a[i] > a[right]:
                result = false
                break
            else:
                q.enqueue(right)
    return result