Summary

In a block storage system, new data is written in blocks. We are going to represent the flash memory as one sequential array. We have a list of block writes coming in the form of arrays of size 2: writes[i] = [first_block_written, last_block_written].

Each block has a rewrite limit. If rewrites on a block reach a certain specified threshold we should run a special diagnostic.

Given blockCount (an integer representing the total number of blocks), writes (the list of block-write arrays of size 2), and threshold, your task is to return the list of disjoint block segments, each consisting of blocks that have reached the rewrite threshold. The list of block segments should be sorted in increasing order by their left ends.

Examples

For blockCount = 10, writes = [[0, 4], [3, 5], [2, 6]], and threshold = 2, the output should be blockStorageRewrites(blockCount, writes, threshold) = [[2, 5]].

After the first write, the blocks 0, 1, 2, 3 and 4 were written in once;
After the second write, the blocks 0, 1, 2 and 5 were written in once, and the blocks 3 and 4 reached the rewrite threshold;
After the final write, the blocks 2 and 5 reached the rewrite threshold as well, so the blocks that should be diagnosed are 2, 3, 4 and 5.
Blocks 2, 3, 4 and 5 form one consequent segment [2, 5].

For blockCount = 10, writes = [[0, 4], [3, 5], [2, 6]], and threshold = 3, the output should be
blockStorageRewrites(blockCount, writes, threshold) = [[3, 4]]

For blockCount = 10, writes = [[3, 4], [0, 1], [6, 6]], and threshold = 1, the output should be
blockStorageRewrites(blockCount, writes, threshold) = [[0, 1], [3, 4], [6, 6]]

Constraints

• 1 ≤ blockCount ≤ 10**5


• 0 ≤ writes.length ≤ 10**5


• writes[i].length = 2


• 0 ≤ writes[i][0] ≤ writes[i][1] < blockCount

First try

from itertools import groupby



def group_blocks(num_writes, threshold):

    i = 0

    for key, group in groupby(num_writes, lambda x : x >= threshold):

        # This is faster compared to len(list(g))

        length = sum(1 for _ in group)

        if key:

            yield [i, i + length - 1]

        i += length



def blockStorageRewrites(blockCount, writes, threshold):

    num_writes = [0] * blockCount

    for lower, upper in writes:

        for i in range(lower, upper + 1):

            num_writes[i] += 1

    return list(group_blocks(num_writes, threshold))

Here I just do exactly what is asked, I create an array of blockCount size, loop over the writes and lastly group the consecutive ranges with itertoos.groupby

After trying to optimize

I'm not quite sure what the complexity was, but I tried to lessen the load, yet I still didn't pass the TLE constraints

def get_bad_blocks(blockCount, writes, threshold):

    cons = False

    u = l = -1

    for i in range(blockCount):

        count = 0

        for lower, upper in writes:

            if lower <= i <= upper:

                count += 1

            if count >= threshold:

                if not cons:

                    cons = True

                    l = i

                    u = -1

                break

        else:

            u = i - 1

            cons = False



        if u != -1 and l != -1:

            yield [l, u]

            l = -1

    if cons:

        yield [l, i]





def blockStorageRewrites(blockCount, writes, threshold):    

    return list(get_bad_blocks(blockCount, writes, threshold))

Questions

You can review any and all, but preferably I'm looking for answers that:

• Tell me if my first example is readable


• I'm less concerned about readability in my second try, and more interested in speed


• Please ignore the PEP8 naming violations as this is an issue with the programming challenge site

First off when you're optimizing code you need to know what to optimize. At first I thought the problem code was not the groupby, but instead the creation of num_writes. And so I changed your code to be able to find the performance of it.

import cProfile

import random



from itertools import groupby



def group_blocks(num_writes, threshold):

    i = 0

    for key, group in groupby(num_writes, lambda x : x >= threshold):

        # This is faster compared to len(list(g))

        length = sum(1 for _ in group)

        if key:

            yield [i, i + length - 1]

        i += length





def build_writes(block_count, writes):

    num_writes = [0] * block_count

    for lower, upper in writes:

        for i in range(lower, upper + 1):

            num_writes[i] += 1

    return num_writes





def blockStorageRewrites(blockCount, writes, threshold):

    num_writes = build_writes(blockCount, writes)

    return list(group_blocks(num_writes, threshold))





block_count = 10**5

writes = 

for _ in range(10**4):

    a = random.randrange(0, block_count)

    b = random.randrange(a, block_count)

    writes.append([a, b])





cProfile.run('blockStorageRewrites(block_count, writes, 10**4)')

Resulting in the following profile:

         200008 function calls in 25.377 seconds



   Ordered by: standard name



   ncalls  tottime  percall  cumtime  percall filename:lineno(function)

        1    0.002    0.002   25.377   25.377 <string>:1(<module>)

   100001    0.019    0.000    0.025    0.000 lus.py:10(<genexpr>)

        1   25.342   25.342   25.342   25.342 lus.py:16(build_writes)

        1    0.000    0.000   25.375   25.375 lus.py:24(blockStorageRewrites)

        1    0.000    0.000    0.033    0.033 lus.py:6(group_blocks)

   100000    0.007    0.000    0.007    0.000 lus.py:8(<lambda>)

        1    0.000    0.000   25.377   25.377 {built-in method builtins.exec}

        1    0.007    0.007    0.033    0.033 {built-in method builtins.sum}

        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

Changing the code as per Georgy's comment to:

def build_writes(block_count, writes):

    num_writes = dict(enumerate([0] * block_count))

    for lower, upper in writes:

        num_writes[lower] += 1

        num_writes[upper] -= 1

    return list(accumulate(num_writes))

Gets the following profile, which is orders of magnitude faster:

         200011 function calls in 0.066 seconds



   Ordered by: standard name



   ncalls  tottime  percall  cumtime  percall filename:lineno(function)

        1    0.002    0.002    0.066    0.066 <string>:1(<module>)

   100002    0.021    0.000    0.028    0.000 lus.py:10(<genexpr>)

        1    0.025    0.025    0.025    0.025 lus.py:16(build_writes)

        1    0.003    0.003    0.064    0.064 lus.py:24(blockStorageRewrites)

        2    0.000    0.000    0.036    0.018 lus.py:6(group_blocks)

   100000    0.008    0.000    0.008    0.000 lus.py:8(<lambda>)

        1    0.000    0.000    0.066    0.066 {built-in method builtins.exec}

        2    0.008    0.004    0.036    0.018 {built-in method builtins.sum}

        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}