Friday, July 29, 2016

knapsack problem

// O(2^n) time
knapsack(items, capacity):
    ways = combine(items)
    maxvalue, maxway = max(ways, capacity)
    return maxvalue, maxway

combine(items):
    ways = new
    combine(item, way: new, ways, 0)
    return ways

combine(items, way, ways, start):
    if start > 0:
        ways.add(copy(way))
    if start == items.length():
        return
    for i = start, i < items.length(), i++:
        way.add(items[i])
        combine(items, way, ways, i+1)
        way.removelast()

max(ways, capacity):
    maxvalue = 0
    maxway = null
    for way in ways:
        value = 0
        weight = 0
        for item in way:
            value += item.value
            weight += item.weight
            if weight > capacity:
                break
        if weight <= capacity && value > maxvalue:
            maxvalue = value
            maxway = way
    return maxvalue, maxway

Thursday, July 28, 2016

cake thief (knapsack problem)

Cake has weight and value. Given different types of cakes with infinite number of each type, and a capacity for duffel bag, get the max value a thief can steal.

ex:
cakes = [(7, 160), (3, 90), (2, 15)]
capacity = 20

returns (555, [(3, 90), (3, 90), (3, 90), (3, 90), (3, 90), (3, 90), (2, 15)])

There could be a cake with 0, +ve weight or value, ex: (0, 0), (1, 0), (0, 1).
cake:
    weight //0+
    value  //0+

max(cakes, capacity):
    for cake in cakes:
        if cake.value > 0 && cake.weight == 0:
            return int.max, yield-infinite(cake)
    maxvalue = {value = 0}
    maxcakes = new
    max(cakes, capacity, maxvalue, maxcakes, 
        bag: {weight = 0, value = 0, cakes = new})
    return maxvalue.value, maxcakes

max(cakes, capacity, maxvalue, maxcakes, bag):
    if bag.weight > capacity:
        return
    if bag.value > maxvalue.value:
        maxvalue.value = bag.value
        maxcakes.clear()
        maxcakes.add(cake for cake in bag.cakes)
    for cake in cakes:
        if cake.value == 0:
            continue
        bag.weight += cake.weight
        bag.value += cake.value
        bag.cakes.add(cake)
        max(cakes, capacity, maxvalue, maxcakes, bag)
        bag.weight -= cake.weight
        bag.value -= cake.value
        bag.cakes.removelast()

yield-infinite(cake):
    while true:
        yield cake
[Hat tip to IC]

rand7 from rand5

rand5 gives 1..5 equally.
matrix = 
[1,2,3,4,5,6,7, //7
 1,2,3,4,5,6,7, //14
 1,2,3,4,5,6,7, //21
 0,0,0,0]       //25

rand7():
    while true:
        i = (rand5()-1)*5 + rand5()-1
        if 0 <= i <= 20:
            return matrix[i]
[Hat tip to IC]

Wednesday, July 27, 2016

find the repeating number

Find the repeating number (any one) in n+1 numbers in range 1..n. There could be more than one number repeating and a number could repeat any number of times.

There are solutions (a. O(n^2) time, O(1) space; b. O(n) time, O(n) space). This works by dividing the range of possible numbers that the duplicate could occur in into half every iteration. For n there will be logn iterations, so O(nlogn) time and O(1) space.
a: 1 2 5 4 5 4

l h m ec ac
1 5 3  3  2
4 5 4  1  2
4 3

a: 1 2 3 4 5 4

l h m ec ac
1 5 3  3  3
4 5 4  1  2
4 3

a: 1 2 3 5 5 4

l h m ec ac
1 5 3  3  3
4 5 4  1  1
5 5
//O(nlogn) time, O(1) space
(a):
    n = a.length()-1
    low = 1
    high = n
    while low < high:
        mid = low + (high-low)/2
        expected = mid-low+1
        count = 0
        for i = 0, i < a.length(), i++:
            if low <= a[i] <= mid:
                count++
        if count <= expected:
            low = mid +1
        else:
            high = mid -1
    return low // low != high

beast mode

This approach treats the array as a graph where value at index i points to index a[i]-1 (so value 1 points to index 0). There is at least 1 repeating number, so the graph will be cyclic. There are n+1 elements and the max is n, so the last node a[n+1] will never be a part of a cycle but will enter a cycle. This is important as this last node is the start node for traversal. Note that if a node which is part of a cycle is used as start node with slow (1x) and fast (2x) pointers then they meet at that same node itself which is not useful. Let's call the converging node as meet node. If the meet node is k hops away from the cycle node, the start node will also be k hops away from the cycle node. This logic is same as finding the cycle node in a cyclic linked list. The array is traversed a max of 3 times so O(n) time and O(1) space.
i: 0 1 2 3
   |-|---|
a: 2 1 3 2
   |-|

i: 0 1 2 3
   |-| |-|
a: 3 1 2 3
   | |-|
   |---|

i: 0 1 2 3 4 5
   |---|-| |-|
a: 3 4 2 3 1 5
   | |-| | |
   | |---| |
   |-------|
//O(n) time, O(1) space
findrepeating(a):
    x = findrepeating(a, findmeet(a), a[a.length() -1])
    return x

findmeet(a):
    slow = fast = a[a.length() -1]
    while true:
        slow = a[slow-1]
        fast = a[a[fast-1]-1]
        if slow == fast:
            break
    meet = slow // or fast
    return meet

findrepeating(a, meet, start):
    m = meet
    s = start
    while m != s:
        m = a[m-1]
        s = a[s-1]
    return m // or s
[Hat tip to IC]

Tuesday, July 26, 2016

get 2nd largest item in bst

(n):
    if n == null:
        throw
    max2 = null
    if n.right != null:
        max2 = n
        while n.right != null:
            max2 = n
            n = n.right
    else if n.left != null:
        max2 = n.left
        while max2.right != null:
            max2 = max2.right
    return max2
[Hat tip to IC]

Tuesday, July 19, 2016

get weakly related items given strongly related items map

Given a map of strongly related items for items, get weakly related items for any item.
a - [b, c, d]
b - [a, c]
c - [a, b, e]
d - [a]
e - [c, f]
f - [e]
g - []

strong(a) = [b, c, d]
So, weak(a) = [e, f]
The weakly related items are item's descendants (subtree) except the item and item's children (direct descendants). As the relations are a graph, the set weak acts as a visited set too.
weakitems(id, map):
    set weak = new
    weakitems(id, map, weak)
    weak.remove(id)
    for sid in map[id]:
        weak.remove(sid)
    return weak

weakitems(id, map, weak):
    if weak.has(id):
        return
    weak.add(id)
    for sid in map[id]:
        weakitems(sid, map, weak)

Monday, July 18, 2016

circular tour

Given gas stations with gas at each gas station and distance between them, return any gas station starting from which a loop exists. All gas stations need to be visited, in order, only once.

Note:
- A loop exists if there is enough gas starting from any gas station. i.e. loop exists if total gas >= total distance (assume 1 mpg).
- If a loop exists clockwise for gas stations, it also does anti-clockwise. So direction does not matter.

We get this array with a surplus or deficit at each gas station.
- If sum >= 0 at the end, a loop exists. The loop gas station is the first one after which sum stays >= 0 till end. This logic does not work for all valid loop gas stations but works for at least one gas station if loop exists (see examples with -).
d: -1  4 -3 -1  1
s: -1  3  0 -1  0
       -        |

d: -1  3 -4  0  1
s: -1  2 -2 -2 -1
                  // no loop

d: -1  6 -3 -1  1
s: -1  5  2  1  2
       |        -

d: -1  5 -7  4  2 -6  5
s: -1  4 -3  1  3 -3  2
             -        |

point:
    gas
    distance
// time O(n), O(1) space
(points):
    looppoint = null
    sum = 0
    for point in points:
        delta = point.gas - (point.distance / mpg)
        sum += delta
        if sum >= 0:
            if looppoint == null:
                looppoint = point
        else:
            looppoint = null
    return looppoint
[Hat tip to B]

Another logic that works is this. The loop point is the next point when the sum is least if sum >= 0 in end.
(points):
    loopi = 0
    sum = 0
    minsum = 0
    for i, point in points:
        delta = point.gas - (point.distance / mpg)
        sum += delta
        if sum < minsum:
            minsum = sum
            loopi = i+1
    if sum < 0:
        loopi = -1
    looppoint = 0 <= loopi < points.length() ? points[loopi] : null
    return looppoint

word ladder

int (start, end, words):
    startn, endn = (start, end, words)
    count = (startn, endn)
    return count

// time O(n)
(startn, endn):
    mind = null
    q = new
    q.push({startn, 0})
    while !q.isempty():
        n, d = q.dequeue()
        if n == endn:
            mind = d
            break
        if visited.has(n):
            continue
        visited.add(n)
        for nn in n.neighbors:
            q.enqueue({nn, d +1})
    if mind != null:
        mind +=2
    return mind

node:
    word
    neighbors

// time O(n^2)
(s1, s2, words):
    all = [words, s1, s2]
    for word in all:
        wordnodemap[word] = new node(word)
    start = wordnodemap[s1]
    end = wordnodemap[s2]
    for word in all:
        wordn = wordnodemap[word]
        for other in all:
            if word == other:
                continue
            if areladderwords(word, other):
                othern = wordnodemap[other]
                wordn.neighbors.add(othern)
    return start, end

areladderwords(s1, s2):
    count = 0
    for c1, c2 in s1, s2:
        if c1 != c2:
            count++
            if count > 1:
                break
    return count == 1
[Hat tip to A]

index for multi-dimensional array

indices   : i
dimensions: m
index     : i

indices   : i j
dimensions: m n
index     : i*m + j

indices   : i j k
dimensions: m n o
index     : i*m*n + j*n + k

indices   : i j k l //i
dimensions: m n o p //d
index     : i*m*n*o + j*n*o + k*o + l
//O(n^2)
index(indices, dimensions):
    index = 0
    for i = 0, i < n, i++:
        offset = indices[i]
        for d = i, d < n-1, d++:
            offset *= dimensions[d]
        index += offset
    return index

//O(n)
index(indices, dimensions):
    index = indices[n-1]
    product = 1
    for i = n-2, i >= 0, i--:
        product *= dimensions[i]
        index += indices[i] *product
    return index
[Hat tip to M]

Sunday, July 17, 2016

if points are vertically symmetric

The vertical line of symmetry is at average of x for all points (assuming points have no dupes). If a mirrored point exists within points for all points, then the points are vertically symmetric.

note: consider only distinct points as dupes skew xavg.
bool (points):
    if points == null:
        throw
    result = true
    distinctpoints = points.distinct()
    // xavg using distinct as dupes skew avg
    xavg = distinctpoints.avg(p => p.x)
    for p in distinctpoints:
        if !distinctpoints.has(mirror(p, xavg))
            result = false
            break
    return result

mirror(p, xavg):
    return point(xavg + (xavg-p.x), p.y)