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