Apollys

Results 14 comments of Apollys

A knob to turn on string splitting

I think this is a major hole in this formatter. One of the primary reasons I started using this was so that it could handle this kind of tedious manual...

Design an algorithm that takes a 2d black and white grid and an index pair (i, j), and sets the value specified by (i, j) to black. It then returns the size of the largest black region after the pixel (i, j) has been changed to black (note: book is ambiguous on this). Optimize runtime for many repeated calls to this algorithm.

> If we end up merging 2, 4, 8, 16, ... cells, I suspect it will be O(n * log n) ? This is since we have to update "region_id_matrix"....

Design an algorithm that takes a 2d black and white grid and an index pair (i, j), and sets the value specified by (i, j) to black. It then returns the size of the largest black region after the pixel (i, j) has been changed to black (note: book is ambiguous on this). Optimize runtime for many repeated calls to this algorithm.

Remember what I wrote: > For a two-region merge, the time complexity is O(size of smaller region) We don't rewrite the region id's of the largest region!

Solve the k-sum problem: determine if there exist k elements in the input array that sum to a given target sum. Assumption: values may be reused as many times as we want (extremely unclear from the book which version they want us to solve).

I see what you're getting at - applying the knapsack DP idea to this scenario. The complexity analysis and optimal algorithm design gets a little trickier with negative numbers permitted....