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

—