GA Interview Questions

This page contains interview questions that have been used for deciding on who gets GA positions in the department. For each problem, you should produce a description of how your solutions works as well as a program that solves the problem correctly. You should put the description of how your solution works as a comment at the top of your code.

You should also include at the top of each solution a list of anything you used as a reference for your solution; if we find that you used something and did not cite it there is roughly 0% chance we would award you a GA position.

You should use a programming language that is supported on the CS server. We will compile and run your solutions, so make sure they work. Supported programming languages include - C, C++, Python, Java, R, php, javascript, Octave. If you would like to use a different programming language, please check with us first.

To submit your solutions, attach your solutions and reply by email to the director of CS. Good luck!

Spring 2019

The following are the interview questions to be solved for those being interviewed in the spring of 2019.

Mod-7 Exponents

Determine the value of the expression (2018²⁰¹⁹ + 2019²⁰¹⁸) mod 7. Use whatever means you would like to determine the correct answer. Once you have the correct answer, write up a proof that the answer is correct. It is possible to compute the answer using a single piece of paper, if you use the right results from mathematics.

• Solution filename: mod7-exponent.* (txt, docx, pdf, etc.)
• Partial credit: Determine the correct answer and explain how you got it (if you used a program, then include the code for the program).
• Full credit: A proof that fits on one page and is easy enough to understand.

012 Graph Coloring

Your program should determine if a given graph can be "012 colored". A 012 coloring has the following property. For any edge (x, y) in the graph, if x has the color i then y must have the color (i+1) mod 3. Your program should output simply "yes" or "no".

• Solution filename: 012-coloring.* (c, py, java, etc.)
• Input format: your program should read a directed graph as an adjacency matrix or adjacency list.
• Partial credit: not likely
• Full credit: correct
• Additional files: When submitting your solution, you should also attach text files for a few of the test graphs that you tested.

10 Smallest

Your program should output the 10th smallest integer from a given input sequence.

• Solution filename: 10-smallest.* (c, py, java, etc.)
• Input format: sequence of at least 10 integers
• Partial credit: produce correct answer, good explanation for your algorithm
• Full credit: algorithm that is, roughly speaking, as fast as possible

Diagonal Walks

Your program should determine how many proper diagonal walks are possible between two points on a grid, subject to certain rules. We imagine that you start by standing in a Euclidean plane at the origin, (0, 0). You want to walk to the point (k, 0). We assume k is an integer. Each step you take should be one unit closer to your destination on the x axis. Thus the x coordinate of your location is first 0, then 1, then 2, etc. You can choose your y coordinate to be either +1 or -1 from your current location. From the origin, you could arrive at position (1, 1) or (1, -1). If you choose position (1, 1) then your next move could be to (2, 2) or (2, 0).

You must determine how many diagonal walks follow these rules and take you from (0, 0) to (k, 0).

• Solution filename: diagonal.* (c, py, java, etc.)
• Input format: a single integer k, the distance along the x axis of your walk
• Partial credit: produce correct answer, good explanation for your algorithm
• Full credit: algorithm that is, roughly speaking, as fast as possible