EPI: Ch18 Greedy and invariants

18.1 word with freq, find the coding scheme with smallest average length?

Hoffman coding: greedy, construct coding tree. Combine two nodes with the lowest frequencies, new combined node is the sum of the freq of two children. Because the code cannot be prefix of any others, the word node must be leafs. The Hoffman coding tree leafs get assigned with code. E.g. left edge -> 0, right edge ->1. Proof easy.

Complexity: T = nlgn, S = n


18.2 Each job has processing time, schedule job such that total waiting time is minimized?

Greedy pick the job with smaller processing time.


18.3 Trapping water

Same as trapping water in LC.

Three ways:

1. Running max, T = n S = n

2. 2 ptrs, T = n S = 1

3. find max, T = n, S = 1

Variant 18.3.1 online algorithm

Go from the first element, store elements in stack

if current element is smaller than running max, clear the stack and update the sum

else go on read the next element

T = n S = n


18.4 n users, each asks for bi storage, m servers. find assignment that minimize the maximal storage required for the servers. Condition: each consecutive two users must be assigned to one server or two consecutive servers.

Solution1: DP L(p, q) = min(max(L(x, q – 1), sum(bi))

Solution2: BS + greedy, search for the upper bound and check


18.5 Implement first fit algorithm for packing.

Tournament tree. Boxes are the leafs and each internal node records the max remaining space for the children boxes.


18.6 3 sum

Variant 18.6.1 distinct 3 sum

Variant 18.6.2 K sum, number of ways of K sum

for(int i = 1; i <= A.length; i ++){
for(int j = 1; j <= k && j <= i; j ++){
for(int t = 1; t <= target; t ++){
ways[i][j][t] = (t >= A[i – 1] ? ways[i – 1][j – 1][t – A[i – 1]] : 0) + ways[i – 1][j][t];
}
}
}

Variant 18.6.3 3 sum code


Gasup problem

The same as LC gas station.

for(int i = 0; i < gas.length; i ++){
costs += cost[i];
gass += gas[i];
if(costs > gass){
start = i + 1;
costs = 0;
gass = 0;
}
}

if(start < gas.length){
return start;
}else{
return -1;
}


18.8 first k number in the form of a + b * sqrt(2)

This is the same as the problem to find the first k numbers which have 3, 5, 7 has factors.

1. Min heap, T = klgk S = k

2. Always insert the smaller element into an array, two ptr, T= k, S = k


18.9 majority element

The same as LC majority element.

Discard two different elements, T = n, S = 1


18.10 2 sum for sorted array on absolute value

1. HashMap, T = n, S = n

2. 2 pointer. find first positive element, last negative element and do normal two pointer sum, T = n, S = 1

Variant 18.10.1

1. HashMap, T = n, S = n

2. 2 pointer. Two pointers start from the beginning of the array (both) and move accordingly. T = nlgn + n, S = 1


18.11 trapping water (|j – i| * min(a[i], a[j]))

Two pointer, move the index with smaller a value, T = n, S = 1.


18.12 find words with frequency of more than ceiling(n / k). Memory should be K and can read for twice.

Discard k different words, HashMap count, get a superset of candidates (at maximum k elements), then read the sequence again to filter out the elements with frequency less than n / k.


 

18.13 longest subarray with sum less or equal to k

1.Brute force, prefix sum, T = n2, S = n

2.Prefix sum, two ptr a and b, find the furthest element c such that prefix[c] – prefix[a] is the smallest, forward ptr b accordingly, T = n, S = n

3. DP, two arr, with/wo, T = n, S = n

Variant 18.13.1

Same as original question.


18.14 max rectangle

This is the same as LC max rectangle. By using a stack T = S = n.

Variant 18.14.1 when there is a largest rectangle, check whether there is a square in there.

 

 

Advertisements
Posted in EPI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s