// 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

## Friday, July 29, 2016

### knapsack problem

## 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).

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.

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.

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 -).

Another logic that works is this. The loop point is the next point when the sum is least if sum >= 0 in end.

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.

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)

Subscribe to:
Posts (Atom)

## Search This Blog

Loading...

## Blog Archive

## Contributors |