Difference between revisions of "POTW 20091029"

From CSLabsWiki
Jump to: navigation, search
m (Addressed sign)
(Added a question)
Line 292: Line 292:
  
 
A: No. The problem statement has been updated to reflect this.
 
A: No. The problem statement has been updated to reflect this.
 +
 +
Q: Is the random decimal test case wrong (I only count 201/1000 bars)
  
 
== Submissions ==
 
== Submissions ==

Revision as of 17:21, 12 November 2009

Problem Statement

Largest Rectangle in a Histogram
Question posed by: Zach Shepherd
Source: Google Interview Question
Date Posed: 2009-10-29


The problem is to compute the area of the largest rectangle in a histogram given an array of inputs representing the height of the bars in the histogram.

The input will be the name of a file beginning with a line containing the width of each bar in the histogram, a line containing the number, n, of bars in the histogram, and n lines containing the height of a bar in the histogram. The bars are presented in order. The width and the height of each bar will be non-negative real numbers with no more than 80 characters in its decimal representation. The number of bars will be a non-negative integer less than 2^32.

$ ./largestrectangle path_to_input_file

Your goal is to produce a solution with the best worst-case asymptotic running time. In the case of a tie, the running time on sample inputs will be used as a tiebreaker.

Sample Input/Output

Ascending Histogram

This represents a histogram with 10 bars of 1 unit wide with the ith bar being i units tall.

Input File

1
10
1
2
3
4
5
6
7
8
9
10

Output

30

Flat Histogram

Input File

.2
5
5
5
5
5
5

Output

5

Random Decimal Numbers

Input File

.23
1000
8.58
96
8.7
13.28
13.08
34.19
20.31
75.25
5.16
26.67
634
31.44
8.32
24.5
1.47
5.06
3
2.86
17.83
10.9
42.53
5.48
10.4
11.46
7.37
11
0.4
44.7
5.93
4
15.77
14.36
17
91.25
10.25
7.61
9.37
12.09
46.29
5.92
7.63
6.29
10.05
4.64
16.29
1.53
25.83
14.17
9.87
8.46
3.78
1.77
49
50.54
0.78
8.19
8.47
2.81
5.6
5.76
2.17
1.08
8.93
9.63
9.08
8.55
3.51
6.09
8.9
78.7
13.4
24.84
4.73
11.74
30.77
13.41
5.67
21.88
2.92
12.27
6.07
9.8
9.63
13.23
41.14
4.41
15.58
18.4
11.54
17
6.84
9.96.23
1000
8.58
96
8.7
13.28
13.08
34.19
20.31
75.25
5.16
26.67
634
31.44
8.32
24.5
1.47
5.06
3
2.86
17.83
10.9
42.53
5.48
10.4
11.46
7.37
11
0.4
44.7
5.93
4
15.77
14.36
17
91.25
10.25
7.61
9.37
12.09
46.29
5.92
7.63
6.29
10.05
4.64
16.29
1.53
25.83
14.17
9.87
8.46
3.78
1.77
49
50.54
0.78
8.19
8.47
2.81
5.6
5.76
2.17
1.08
8.93
9.63
9.08
8.55
3.51
6.09
8.9
78.7
13.4
24.84
4.73
11.74
30.77
13.41
5.67
21.88
2.92
12.27
6.07
9.8
9.63
13.23
41.14
4.41
15.58
18.4
11.54
17
6.84
9.96
6.67
5.2
10.01
8.13
43.07
98.71
8.76
35.7
6.67
5.2
10.01
8.13
43.07
98.71
8.76
35.7

Output

145.82

Submission and Grading

There will be three winners:

  • the first person to submit a program that handles "basic" test cases,
  • the first person to submit a program that handles all test cases (see Q&A),
  • the "best" answer as determined by the problem poser.

You should the source code for a working program, a makefile to compile your code if applicable, and a short write-up describing the memory usage of your function. You may use any language that can be compiled/interpreted on the ITL Linux build (C, C++, Java, Scheme, Prolog, Python, Perl, Lisp, etc.). Please submit your solution by emailing it to the problem poser.

After your submission has been evaluated, you will receive an email with the results (whether you passed the basic test cases or all of the test cases).

Requests for Clarification

Please make all requests for clarification here in the form of:

Q: Question

Q: Will the size of the input file fit be less than the size of the memory of the machine on which the programs will be tested?

A: The problem statement does not guarantee this. UPDATE: For the basic test cases, all files will fit into memory. For the complete set, some will not. Given the constraints on the number size and file length, the input file could be, at most, 320 GB.

Q: Can bars have negative heights/widths?

A: No. The problem statement has been updated to reflect this.

Q: Is the random decimal test case wrong (I only count 201/1000 bars)

Submissions