Problem

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

Advertisements

Tags: ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: