Saturday, August 01, 2015

water volume in histogram graph

//examples

       x
  x   ||
 ||   ||
 ||   ||
 ||   ||
x||  ||| x
|||  ||| | x
||||||||_|||


          x
  x      ||
 ||     |||
 ||     |||
 ||     |||
x||  |  ||| x
|||  |  ||| | x
|||||||||||_|||


      x
    x |
  x | |
x | | |
|_|_|_|


x      
|     x
|     |
|   | |
|_|_|_|


x      
| x    
| | x  
| | | x
|_|_|_|
The trick is to find the boundaries of troughs. Trough has a decreasing slope followed by an increasing slope.
// time: O(n), space: O(1)
(a):
    volume = 0
    i = 0
    while true:
        if i+1 == a.length:
            break
        // trough boundaries
        start = i
        // decreasing slope
        while i+1 < a.length && a[i] >= a[i+1]:
            i++
        end = i
        // increasing slope
        while i+1 < a.length && (a[i] <= a[i+1] || a[end] <= a[start]):
            i++
            if a[i] >= a[end]:
                end = i
        // trough volume
        level = min(a[start], a[end])
        for j = start, j <= end, j++:
            if a[j] < level:
                volume += level - a[j]
        i = end
    return volume
[Hat tip to N]

sanitize path

//example:
/a/b/..       -> /a/
/a/b/./       -> /a/b/
/a/b//        -> /a/b/
/a/b/../../   -> /
/////         -> /
/a/b/../../.. -> throw
string sanitize-path(path):
    if path == null || (path = path.trim()) == "":
        throw
    // assume split removes empty entries
    tokens = path.split("/")
    target = 0
    for i = 0, i < tokens.length, i++:
        if tokens[i] == ".":
            // do nothing
        else if tokens[i] == "..":
            target--
            if target < 0:
                throw "invalid input"
        else:
            tokens[target] == tokens[i]
            target++
    buffer = new
    buffer.append("/")
    for i = 0, i < target, i++:
        buffer.append(tokens[i])
        buffer.append("/")
    return buffer.tostring()
[Hat tip to LM]

string pattern matching

int pattern-matching(text, pattern):
    if text == null || pattern == null:
        throw
    // assume pattern of 0 length is ok
    index = -1
    for i = 0, i <= text.length - pattern.length, i++:
        for j = 0, j < pattern.length, j++:
            if text[i+j] != pattern[j]:
                break
        if j == pattern.length:
            index = i
            break
    return index

Update: pattern has char * which matches 0+ chars in text.
// example
text:    abcde
pattern: *b****
int pattern-matching(text, pattern):
    if text == null || pattern == null:
        throw
    index = -1
    for i = 0, i < text.length, i++:
        if text[i] == '*':
            throw "invalid char"
        k = i
        for j = 0, j < pattern.length, j++:
            if pattern[j] == '*':
                while j < pattern.length && pattern[j] == '*':
                    j++
                if j == pattern.length:
                    break
                while k < text.length && text[k] != pattern[j]:
                    k++
                if k == text.length:
                    break
            else if text[k] != pattern[j]:
                break
            k++
        if j == pattern.length:
            index = i
            break
    return index
[Hat tip to G]

is binary tree symmetric

bool is-symmetric(node):
    if node == null:
        throw
    return is-symmetric(node.left, node.right)

bool is-symmetric(n1, n2):
    if n1 == null && n2 == null:
        return true
    if n1 == null || n2 == null:
        return false
    return n1.value == n2.value
        && is-symmetric(n1.left, n2.right)
        && is-symmetric(n1.right, n2.left)

Sunday, July 26, 2015

sort items by priority in array inplace

enum priority:
    high = 1,
    medium = 2,
    low = 3

// sort by priority inplace
(a):
    highcount, mediumcount, lowcount = getprioritycounts(a)
    moveitems(a, highcount, mediumcount, lowcount)

getprioritycounts(a):
    for i = 0, i < a.length, i++:
        priority = a[i].priority()
        if priority == priority.high:
            highcount++
        else if priority == priority.medium:
            mediumcount++
        else if priority == priority.low:
            lowcount++
    return highcount, mediumcount, lowcount

moveitems(a, highcount, mediumcount, lowcount):
    highi = 0, mediumi = highcount, lowi = mediumi + mediumcount
    // move the high priority items
    for i = 0, i < highcount,:
        priority = a[i].priority()
        if priority == priority.high:
            i++
        else if priority == priority.medium:
            swap(a, i, mediumi)
            mediumi++
        else if priority == priority.low:
            swap(a, i, lowi)
            lowi++
    // move the medium priority items
    for i = mediumi, i < highcount + mediumcount,:
        priority = a[i].priority()
        if priority == priority.high:
            // this should not occur
            throw
        else if priority == priority.medium:
            i++
        else if priority == priority.low:
            swap(a, i, lowi)
            lowi++
[Hat tip to ts]

Friday, July 24, 2015

largest difference in array

(a):
    low = 0
    maxlow = 0, maxhigh = 0
    for i = 0, i < a.length, i++:
        if a[i] < a[low]:
            low = i
        if i > low && (a[i]-a[low]) > (a[maxhigh]-a[maxlow]):
            maxhigh = i
            maxlow = low
    return maxlow, maxhigh
[Hat tip to eopi]

Thursday, July 23, 2015

is any combination of string palindrome

(s):
    if s == null:
        throw
    if s == "":
        return false
    set oddchars = new
    for i = 0, i < s.length, i++:
        // break out if rest of string cannot get oddchars's count down to 1 
        if oddchars.count() - (s.length - i) >= 2:
            break
        c = a[i]
        if oddchars.has(c):
            oddchars.remove(c)
        else:
            oddchars.add(c)
    return oddchars.count() <= 1
[Hat tip to LV]

max contiguous subarray sum

Based on max contiguous sum in array.
// max sum
(a):
    sum = 0, maxsum = a[0] // 1st element for -ve values
    for i = 0, i < a.length, i++:
        sum += a[i]
        if sum > maxsum:
            maxsum = sum
        if sum < 0:
            sum = 0
    return maxsum
// contiguous subarray max sum
// handles all -ve values, excludes 0s, longer subarray does not matter
(a):
    if a == null || a.length == 0:
        throw
    sum = 0, maxsum = a[0] // 1st element for -ve values
    start = 0, maxstart = 0
    end = 0, maxend = 0
    for i = 0, i < a.length, i++:
        sum += a[i]
        // works for -ve values due to order of ifs and maxsum = a[0]
        if sum > maxsum:
            maxsum = sum
            end = i
            maxstart = start
            maxend = end
        if sum < 0:
            sum = 0
            start = i +1
    return maxstart, maxend
//examples
              |     |
a:   5  5 -20 5  5  5
sum: 5 10   0 5 10 15

     |  |
a:   5  5 -20 2 3  5
sum: 5 10   0 2 5 10

        |
a:   -3 0 -2
sum:  0 0  0

     |    |
a:   2 3  5 -20 5  5 0
sum: 2 5 10   0 5 10 0

      |
a:    2 -2 2
sum:  2  0 2

      |
a:    0 0 0
sum:  0 0 0

         |
a:   -3 -1 -2
sum:  0  0  0
// largest contiguous subarray max sum
// handles all -ve values, includes 0s, longer subarray
(a):
    if a == null || a.length == 0:
        throw
    sum = 0, maxsum = a[0]
    start = 0, maxstart = 0
    end = 0, maxend = 0
    for i = 0, i < a.length, i++:
        sum += a[i]
        // works for -ve values due to order of ifs and maxsum = a[0]
        if sum > maxsum:
            maxsum = sum
            end = i
            maxstart = start
            maxend = end
        // when sum and maxsum are equal, take longer subarray
        else if sum == maxsum:
            end = i
            if (end-start) > (maxend-maxstart):
                maxstart = start
                maxend = end
        if sum < 0:
            sum = 0
            start = i +1
    return maxstart, maxend
//examples
              |     |
a:   5  5 -20 5  5  5
sum: 5 10   0 5 10 15

              |    |
a:   5  5 -20 2 3  5
sum: 5 10   0 2 5 10

        |
a:   -3 0 -2
sum:  0 0  0

     |    |
a:   2 3  5 -20 5  5 0
sum: 2 5 10   0 5 10 0

      |    |
a:    2 -2 2
sum:  2  0 2

      |   |
a:    0 0 0
sum:  0 0 0

      |   |
a:    0 0 0 -1 0
sum:  0 0 0  0 0

      |     |
a:    1 0 0 0 -1 0
sum:  1 0 0 0  0 0

         |
a:   -3 -1 -2
sum:  0  0  0
[Hat tip to JE, AP]

Sunday, July 19, 2015

longest substring in s1 with all chars of s2

(s1, s2):
    if s1 == null || s2 == null:
        throw "args"
    s2set = s2.toset()
    i = count = maxcount = start = 0
    while i < s1.length:
        count = 0
        while i < s1.length && s2set.has(s1[i]):
            count++
            i++
        if count > maxcount:
            maxcount = count
            start = i-count
        if count == 0:
            i++
    return {substring: s1.substring(start, maxcount), index: start}

intersection of two sorted lists

// a, b are sorted lists
intersection(a, b):
    if a == null || b == null:
        throw
    intersection = new
    ai = 0, bi = 0
    while ai < a.length && bi < b.length:
        if a[ai] == null:
            ai++
            continue
        if b[bi] == null:
            bi++
            continue
        c = a[ai].compare(b[bi])
        if c < 0:
            ai++
        else if c > 0:
            bi++
        else: // a[ai] == b[bi]
            // intersection does not have duplicates
            if intersection.count == 0 
                || intersection[intersection.length-1] != a[ai]:
                intersection.add(a[ai])
            ai++
            bi++
    return intersection