## NetApp Interview Question for SDE-3s

Country: India

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Go through the critical points - that is - end or start of range and check if the kth order statistic lies inside rectangle between this and previous critical point.

``````"""
0123456789ABC
XXXXXXXXXXXXX
XXXX   XXX
XX
"""
def kth(ranges, k):
assert k >= 0
events = []
for start, end in ranges:
events.extend([(start, 1), (end + 1, 0)])
events.sort()
depth = 0
previous_pos = 0
for pos, is_start in events:
length = pos - previous_pos
area = length * depth
if depth and k < area:
return previous_pos + k / depth
k -= area
if is_start:
depth += 1
else:
depth -= 1
previous_pos = pos
raise ValueError("k is larger than length by", k)

def kth_stupid(ranges, k):
lst = sum((range(s, e + 1) for (s, e) in ranges), [])
return sorted(lst)[k]

import random
for i in xrange(500):
ranges = []
s = 0
for n in xrange(50):
left = random.randrange(99)
right = random.randrange(left + 1, 100)
s += right - left + 1
ranges.append((left, right))
for k in xrange(s):
assert kth_stupid(ranges, k) == kth(ranges, k), (ranges, k)``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.