4
\$\begingroup\$

I have this typical code interview type problem.

Suppose you have a stick of length n. You make X cuts in the stick at places x1, x2, x3 and so on. For every cut in X cuts you need to print the length of current longest piece.

Here is my current code:

def get_index_binary_search(list_thing,index, j):

    start = 0
    end = j

    while start<= end:
        mid = (start+end)//2
        if list_thing[mid]==index:
            return mid
        elif list_thing[mid]<index:
            start = mid + 1
        else:
            end = mid - 1
    return end + 1


n, m = [int(x) for x in str(input()).split()]

sticks = [0,n] # the whole stick without cuts
cuts = [int(x) for x in str(input()).split()]
#biggestrange = [0,n]
minimum_range = 0
maximum_range = n



maximum = n
for j in range(m):
    
    cut = cuts[j]

    
    

    i = get_index_binary_search(sticks, cut, j)
    

    sticks.insert(i,cut)

    if minimum_range<cut and cut<maximum_range:

        # we need to calculate the biggest range again
        
        maximum = 0
        for counter in range(len(sticks)-1):
            value = sticks[counter+1]-sticks[counter]
            #print(value)
            if value > maximum:
                maximum = value
                minimum_range = sticks[counter]
                maximum_range = sticks[counter+1]

    
    
    print(maximum)
    

The code works but I do not know of a more efficient way to solve this problem and my code doesn't run in the required time frame. How do I improve it? Thanks in advance for the help!

\$\endgroup\$
0

3 Answers 3

1
\$\begingroup\$

Two reviewers advised how to avoid establishing the length of current longest piece from scratch, as that promises worst case run time at least quadratic in the number m of cuts.
In greybeard's proposal, there is hand-waving about how to establish the stick cut - using bisect.insort() results in O(m²).
janos' proposal skimps over BST implementation (including remove, predecessor&successor, insert optional. And remove the piece from the heap - I think heap use uncalled for.)
- Lets try to mock up something somewhat plausible in a job interview context.

Assume cuts are unique (and between 0 and n, exclusive).
Let print the length of current longest piece mean after the cut.

Processing from the final configuration looks promising -
If the customer (in professional coding, there is one - here: interviewer) wanted to specify cuts one by one, the task specification would have to be refined.

One insight is that deleting from a "doubly linked" list is cheap given the node:
After ascendantly ordering the cuts, make a node for each linked with its neighbours as lengths
and keep a dict sticks mapping cut to node.
Establish the greatest length longest.
For every cut in reverse input order

  • append longest to a list after
  • remove cut from lengths
    This increases the length of the stick starting at the predecessor end to cut's end:
    update longest where necessary

print reversed after

For the hell of doubly linked list library support, object disorientation and naked code:

def longest_after(length, cuts):
    """ Starting with a stick of length length,
        return an iterable of the lengths
                           of the longest stick after each cut in cuts.
    """
    ordered = [0] + sorted(cuts) + [length]  # to avoid special casing [i+-1]
    sticks = {key: index for index, key in enumerate(ordered)}
    if ordered[1] < 0 or length < ordered[-2] or len(sticks) < len(ordered):
        pass  # ToDo: handle error
    pred = list(range(-1, len(cuts) + 1))  # predecessor?
    succ = [i + 2 for i in pred]           # list(range(1, len(cuts) + 3))
    # from 3.10: itertools.pairwise(ordered)
    lengths = [-1] + [end - start for end, start in zip(ordered[1:], ordered)]
    longest = max(lengths)
    after = [longest]
    # the first cut would append longest = length before 1st cut: unwanted
    for cut in reversed(cuts[1:]):
        index = sticks[cut]
        p = pred[index]  # pred_index?
        s = succ[index]
        merged = lengths[s] + lengths[index]
        lengths[s] = merged
        if longest < merged:
           longest = merged
        succ[p] = s
        pred[s] = p
        after.append(longest)
    return reversed(after)
\$\endgroup\$
0
3
\$\begingroup\$

Hm. Interview.
You tried something simple (good!) and it doesn't fit the time frame (pity).
Well, if it seems to work, give it a name and use it as a test for advanced implementations.
Make it a function with parameters like length and cuts (a sequence).
You get to document what it does.

To keep the sticks, you don't need both start&end if you keep them ordered:
The first stick starts at 0. Store the ends, every non-first stick starts at the end of its left neighbour.
(Using a dummy/sentinel may prove easier.)
When storing the sticks in a list, this makes it easy to use bisect.insort() - inserts will be O(m).
Instead of re-establishing maximum if cut, what if one keeps the lengths in a priority queue?
Replace the maximum with one of its parts(heapq.heapreplace(lengths, part)), add the other.
(Saving special casing of part length 0(?allowed?)/maximum length 2 for later.)
Fine, but what if a non-maximal stick was cut?
Using a balanced BST should work, but feels oversized. (Due to lack of library support?)
Would mapping from length to count fill the gap? (If top length maps to 0, pop)


Stick to the Style Guide for Python Code - I find your code avoidably hard to grasp for the (StackExchange) keyhole I'm looking through at multiple blank lines not necessarily separating something.

Naming looks pretty good - I gather m and n are straight from the problem statement.
(Likely exception: The parameters to get_index_binary_search().
I'd like sequence better than list_thing - matter of taste? But index is not an index (a key, rather),
and j would better be end).

Rather than indexing into cuts

for j in range(m):
    cut = cuts[j]

, iterate them:

for cut in cuts:

Where needing j like since the introduction of get_index_binary_search(), it may seem "more pythonesque" to use

for j, cut in enumerate(cuts):

- I happen to not particularly like it, thinking it a (performance) artefact of interpreting Python.

Another way to set "minimax_range" was

                minimum_range, maximum_range = sticks[counter:counter+2]
\$\endgroup\$
1
  • \$\begingroup\$ The use of j as a parameter to get_index_binary_search() deserves a comment. (Just as get_index_binary_search() deserves a docstring… or replacement by bisect.bisect()/insort().) \$\endgroup\$
    – greybeard
    Commented Sep 18, 2022 at 17:47
3
\$\begingroup\$

Consider time complexity

When the code works but it runs too slow, it's usually because the algorithm doesn't scale well to larger inputs. It's good to review the time complexity and look for improvement opportunities.

The current algorithm:

  • Track the applied cut points in a sorted list
  • Track the largest piece's range
  • For each cut point -- \$O(n)\$
    • Find the insertion point in the sorted list using binary search -- \$O(\log n)\$
    • Insert the cut point into the sorted list -- \$O(n)\$
    • If the cut point falls within the range of the largest piece
      • Loop over the cut points to find the new largest piece -- \$O(n)\$

With \$n\$ cut points, the overall time complexity is \$O(n^2)\$.

Although using binary search is a nice idea, unfortunately it's not effective here, because it's dominated by the slow insertion.

There are two key parts that need to be improved to make the algorithm faster:

  • For computing the new largest piece, we need a faster way than checking all the piece sizes, faster than \$O(n)\$.
  • For tracking the cut points so far, which is necessary for computing the new largest piece, we need a faster way than \$O(n)\$.

To compute the current largest piece, we can use a max-heap in \$O(\log n)\$ time:

  • Starts with the full size
  • For each cut:
    • Remove the piece that was cut
    • Add the 2 new pieces
    • The new largest piece is the top of the heap

To find the piece to cut, binary search seems a good direction, unfortunately the fast lookup is ineffective due to the slow insertion. What can we do?

  • Using a regular BST would support well all inputs: when the cut points are sorted, a regular BST will grow into a linked list, and set us back to \$O(n)\$.
  • Using a balanced BST would solve that problem, but I'm not aware of a balanced BST implementation in the standard library, and it would be hard to implement during an interview.

Here's an idea that's perhaps feasible (amended with an improvement suggested by @greybeard, dropping the use of a heap altogether):

  • Make a sorted copy of the cut points, and use it to:
    • Build a balanced BST: insert the middle of the list, then the middle of the left half and the right half, and so on, recursively
    • Find the largest cut piece and start a list of results with it
  • For each cut point in reverse of the original order:
    • Find the cut point in the BST, and:
      • Find its predecessor and successor to compute the length of the "uncut" piece
        • Update the largest cut piece if this "uncut" piece is larger
      • Add to the list of results the largest cut piece
    • Delete the cut point from the BST
  • Reverse the list of results

This would improve the overall time complexity to \$O(n \log n)\$, at the expense of a custom BST implementation.

... And as @greybeard pointed out in a community wiki answer, a simpler implementation is possible replacing the BST with a double-linked list. The nodes are sorted by cut point, and a mapping from the original order of the cuts to list nodes makes it fast to remove nodes from the list. The time complexity remains \$O(n \log n)\$, due to the sorting of the cut points.

Simplify the binary search

The last parameter of the function looks suspicious:

def get_index_binary_search(list_thing,index, j):

On closer look, the value of j is always the size of list_thing. You can remove it, and use len(list_thing) inside the function.

But then, the function matches the signature and behavior of Python's bisect.bisect, so you can simply remove it.

Simplify chained comparison

Instead of:

if minimum_range<cut and cut<maximum_range:

You can write simpler:

if minimum_range < cut < maximum_range:

Simpler iterating pairwise

Instead of:

for counter in range(len(sticks)-1):
    value = sticks[counter+1]-sticks[counter]
    #print(value)
    if value > maximum:
        maximum = value
        minimum_range = sticks[counter]
        maximum_range = sticks[counter+1]

A more elegant way to iterate over pairs is using zip:

for left, right in zip(sticks[:-1], sticks[1:]):
    value = right - left
    if value > maximum:
        maximum = value
        minimum_range = left
        maximum_range = right

As of Python 3.10, an even more elegant way using itertools.pairwise:

for left, right in itertools.pairwise(sticks):
    value = right - left
    if value > maximum:
        maximum = value
        minimum_range = left
        maximum_range = right

Use better names

I suggest to use more precise and descriptive variable names, for example:

  • list_thing -> items
  • minimum_range, maximum_range -> largest_start, largest_end or largest_left, largest_right
  • i -> index
\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.