Practice programming exam.

Exam rules: open course materials, which includes the course textbook, the booksite, the course website, your course notes, and code you wrote for the course. Note that the booksite has a custom search feature (linked at the bottom left of the main page). Please use it as you are not supposed to use generic google searches.

Note that this practice exam is meant purely for you to practice solving a problem that involves data structures and/or problem solving in an exam-like environment. The actual exam may differ from the practice exam in the difficulty level and/or type of task you have to implement.

All testing is done locally, with uploading done at the very end. Assume this is a 80 minute exam. Time yourself strictly so that when you have 5 minutes left to upload code that is compiling and passes as many local tests as possible.

Note that this (and the actual) exam will be graded solely on how they do on tests. Therefore your top priority should be to create code that compiles, and passes as many tests as possible. Considerations such as efficiency are secondary. The test platform you are getting will automatically log things as you run, so if you break something we will be able to recover some of your points.

Given an NxN matrix of integers, find the largest number that appears (at least) once in each row (or report that no such number exists).


Your class should contain the following API:
public class LCN {
    public LCN(int[][] tiles)
    public int solution()          // return solution value; Integer.MIN_VALUE if no solution exists
    public boolean isASolution()   // return true if a solution exists, else false
    public static void main(String[] args) // unit testing
}

Performance requirements. For full credit, the constructor should take N^2 log N time or better. The methods should be constant time. There are no restrictions on main; we will not run it. The memory needed should be no more than N^2.

The actual exam in two weeks will have three (shorter) parts. A rough matching of letter grades to performance on this test is as follows:

C-range: finish the assignment with no running time or space constraints in up to 120 mins;

B-range: finish the assignment with the prescribed time/space performance in 65-80 mins (B+ is 65, B- is 80).

A-range: finish the assignment with the prescribed time/space performance in 40-60 mins (A is 40, A- is 60).

Note that these are very approximate, since the actual exam will not be on time but on completing tasks of varying difficulty (easy, medium, hard).

File you should download and unzip: practice_exam_s18.tar.gz OR practice_exam_s18.zip

You should only modify the designated parts of LCN.java. Running its main should toggle the testing. You may add your own tests if you like, but it's not required.