Warming Up
The programming exercises in EPI are representative of what you will be asked
in an interview. We do not provide textbook-style review questions.
In this document, we present a small set of programming exercises suitable for
someone who needs to review basics. (You are unlikely to be
asked these questions - their purpose is to bootstrap reading EPI.)
When you write your solutions to these exercises, please code to the following constraints:
- Do not use library calls.
- Do not try to design clever solutions. (This means it is fine to use brute-force approaches.)
- Assume valid inputs, and ignore internal errors like overflow, IO exceptions, etc.
- Write unit tests for your programs.
- Analyze your programs for time and space complexity.
Exercises, one for each EPI chapter
- Primitive types: write a program that takes as input an integer, N, and prints
all the integers from 1 to N, replacing numbers divisible by 3 with “fizz”, numbers divisible by
5 with “buzz”, and numbers divisible by both with “fizz buzz”. - Arrays: Write a program that tests if a 2D square array is symmetric about the diagonal
from (0,0) to (n-1,n-1). - Strings: Write a program to find the longest substring that consists of a single
character in an input string. - Linked Lists: Implement a doubly linked list of integers class. Write a reverse method for your list class
that reverses a list without changing the node contents. - Stacks and Queues: Write a programt to evaluate arithmetical expressions that use + and applied
to nonnegative integer arguments. Expressions are in reverse-Polish notation, e.g., 3 4 + 5 , 1 3 + 5 7 + *. - Binary Trees: Write inorder, preorder and postorder traversal methods for a binary tree. (You will need
to implement a class suitable for representing binary trees, but do not need to implement
add, lookup, delete, etc. methods.) - Heaps: Write a program that builds a max-heap from an integer array. (You will need to implement
a class suitable for representing heaps, but do not need to implement extract-max, insert key, etc.) - Searching: Write a nonrecursive program to perform binary search over a sorted array.
- Hash tables: Write a program that finds the most common object in an array of objects. The
objects consists of pairs of strings. Treat strings as being the same if they are equal when converted to lower case. - BSTs: Write a program that searches a BST on integer keys for a given value. (You will need to
implement a class suitable for representing BSTs, but do not need to implement
add, lookup, delete, etc. methods.) - Write a recursive program that takes as input positive integers x and N, and returns x to the power N.
You should use O(log N) multiplications. - Dynamic Programming: Write a program that takes a positive integer N, and returns the number
of binary strings of length N such that there are no consecutive 1s. For example, if N = 3, the result
is 5, corresponding to the strings 000, 001, 010, 100, 101. - Greedy Algorithms and Invariants: Write a program that takes an input a positive integer
N, and returns the minimum number of coins in the US coinage system to create N cents. For example, if
N = 37, the answer is 4, corresponding to a quarter, a dime, and two pennies. - Graphs: Implement Depth First Search and Breadth First Search. (You will need to implement
classes suitable to representing graphs.) - Parallel Computing: Write a program which uses two threads to print the numbers from
1 to 100 in order. One thread can only print odd numbers, the other can only print even numbers.