Archive for the ‘Interviewing’ Category

Problem

July 20, 2008

A while ago, in an interview, I was given this problem:

Write a program that runs on a normal desktop PC and reads closed
extents from “extents.txt” and points from “numbers.txt”, and writes, to
standard output, the number of extents that contain each point, in the
order the points are given, one result per line. A closed extent [A,B]
contains a point (P) iff A <= P <= B.

extents.txt” contains extents, one per line, with each line in the
format A <whitespace> B. The file contains no more than 50 million
extents. “numbers.txt” contains a list of points, one per line. The file
may contain billions of points. Both files may contain duplicates, and
may or may not end with a <newline>. You may assume that the input is
valid, and that all numbers can be represented by an unsigned integer.

We are looking for EFFICIENCY, SIMPLICITY and COMPACTNESS.

Example 1:

extents.txt
0 10
100 131
132 133
11 32

numbers.txt
1
2
4
12
53
23
53
12
32

output
1
1
1
1
0
1
0
1
1

Example 2:

extents.txt
0 10
0 10

numbers.txt
3
3

output
2
2