Be prepared

2015-04-01
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:


  1. Do not use library calls.
  2. Do not try to design clever solutions. (This means it is fine to use brute-force approaches.)
  3. Assume valid inputs, and ignore internal errors like overflow, IO exceptions, etc.
  4. Write unit tests for your programs.
  5. Analyze your programs for time and space complexity.

Exercises, one for each EPI chapter


  1. 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”.
  2. Arrays: Write a program that tests if a 2D square array is symmetric about the diagonal
    from (0,0) to (n-1,n-1).
  3. Strings: Write a program to find the longest substring that consists of a single
    character in an input string.
  4. 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.
  5. 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 + *.
  6. 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.)
  7. 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.)
  8. Searching: Write a nonrecursive program to perform binary search over a sorted array.
  9. 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.
  10. 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.)
  11. 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.
  12. 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.
  13. 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.
  14. Graphs: Implement Depth First Search and Breadth First Search. (You will need to implement
    classes suitable to representing graphs.)
  15. 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.
Read More

2015-03-31
Tools

Building and maintaining programs


  1. What version control system do you use?
  2. What coverage tool do you use?
  3. What build system do you use?
  4. What documentation system do you use?
  5. What bug tracking system do you use?
  6. How is branching implemented in a version control system?
  7. Are deltas in the branching for a revision tree stored out forwards
    or backwards? What are the benefits of each approach?
  8. What are the advantages and disadvantages of a version control system that locks files?

The Shell

There are scores, if not hundreds of books on the UNIX shell and related tools.
We have enjoyed LINUX 101 Hacks by Natarajan. It introduces
these tools through useful hacks, such as the use of find
to find all files that have not been modified in the past 100 days
and are larger than 100~megabytes in size, sorting the password file on the third field, etc.


  1. Write a regular expression for identifying social security numbers in a file.
  2. Write a command that prints out lines in a text file which contain the
    strings foo and bar in any order.
  3. Write a command which replaces every occurrence of a foo followed by a bar (with
    possibly some other characters in between) by widget.
  4. Given a text file with two columns of integers, i.e., two integers encoded in ASCII per line, write a filter which sorts lines in the file by the second integer.
  5. How would you take two documents in PDF and create a new document which consists of the pages of the two original documents interleaved in order?
  6. How would you write a program which checks every hour if a network connection is up?
  7. How would you write a program which checks the price of a Nikon D5300 DLSR each day on amazon.com?
Read More

2015-03-31
General facts about C, C++, Java, Python

Core language


  1. What are the types in C, Java, C++, and Perl? How many bits does it take
    to represent the basic types?
  2. What do floating point numbers look like in
    memory? Specifically, how many bits are there in a double and
    what sequence to the bits appear in?
  3. What is twos-complement notation?
  4. How would you implement a bit array class?
  5. Does the check x == x + 1 always return false for integer x?
  6. What does a C struct look like in memory? What does a C++
    object look like in memory? What does a Java object look like in
    memory?
  7. What is the difference between an interpreted and a compiled language?
  8. What is garbage collection?
  9. How would you determine if call stack grows up or down relative
    to memory addresses?
  10. Give an example of a memory leak in Java.
  11. What is tail recursion? How can it be removed automatically?
  12. Is the natural recursive program for computing n! tail recursive?
  13. Your manager reads an online article that says it is 10X faster to code in Python than in C++. He wants you to code exclusively in Python from now on. What would you say to him?
  14. What does an executable look like as a sequence of bytes?

Libraries

A programmer who regularly implements complex algorithms such as KMP
string matching or the Dijkstra shortest path computation quickly
will not advance very far. Solutions to such problems are well-known and have
high quality, thoroughly tested, and debugged implementations, often
available as open source. Programmers should know and use these libraries.


  1. Give an example of a function which is in the C standard library.
  2. Give an example of a commonly used function which is not in the C standard library.
  3. What library would you use to determine the current date in Java?
  4. What library would you use in Java if you had to implement a tinyurl service?
  5. How does STL implement sets?
  6. How does the library code compute trigonometric functions?
  7. The strtok(char s1, char s2) function in the C standard library successively returns occurrences of the characters in s2 in string s1; it returns null if there are no more occurrences.
  8. What makes this a dangerous function to use in a multithreaded program?

Programming language implementation


  1. Give an example of a language which cannot be parsed by any computer.
  2. What problems does dynamic linkage solve? What problems does it introduce?
  3. What is a functional language?
  4. What is a virtual function?
  5. How is method dispatch implemented in Java?
  6. What is automatic garbage collection and how is it implemented?
  7. What is a type-safe language?
  8. What is the difference between a lexer and a parser?
  9. Give an example of a language which cannot be recognized by a lexer.
  10. Give an example of a language which cannot be parsed by a parser.
Read More

2015-03-31
General facts about Operating Systems

Modern Operating Systems by Tanenbaum is widely used;
one of its claims to fame is that Linux was developed from the Minix
OS developed in an earlier version of this book.


  1. What is a system call?
  2. How is a system call different from a library call?
  3. What is a device driver?
  4. What is livelock? What is deadlock? Give examples of each.
  5. What is a race? What can you do to prevent races?
  6. What is a mutex? What are semaphores? How are they implemented?
  7. Give examples of system calls that are not related to input-output.
  8. Give examples of library functions that call a system function all the time, none of the time, and some of the time.
  9. What is the time lag between the system call on the client side and the receipt of the packet on the server on a LAN?
  10. How fast can you write a gigabyte of data from RAM to disk?
  11. How does TCP/IP work?
  12. What is DNS?
Read More

2015-03-31
General Programming Questions

Our book is focused on questions that entail writing programs. You may be asked
questions related to general programming practices, which are conceptual and/or
knowledge-based, and do not require writing a program. (The extent to which
you are asked such questions depends on the company, your experience, the job, etc.)

Such questions tend to be narrow, and as such are not appropriate for our book.
We have begun the process of collecting representative questions, which you can see below.

Languages,
Debugging and Testing,
Operating Systems,
Tools,

We have also put together a small list of warm up exercises that are appropriate
for someone who is a little rusty.

Read More

2015-03-31
Debugging and Testing

Debugging and testing are topics which are not usually the focus of university teaching.
We highly recommend The Practice of Programming by Kernighan and
Pike, which teaches much more than just writing code. Specifically, it covers testing,
debugging, portability, performance, and design alternatives.


  1. What was your last bug? What was your hardest bug?
  2. How would you debug a distributed program?
  3. A program works sometimes and fails other times - why?
  4. A program works sometimes and fails other times on the exact same input - why?
  5. How would you determine where a program spends most of its time?
  6. How does JUnit make the process of testing easier?
  7. List five ways in which C code can be non-portable. What can you do to make the code portable?
  8. Write tests for implementation of an isupper() function.
  9. Should you test private methods? Should you test one line methods?
  10. If you find and fix an error by adding debug code, should you remove the debug code afterwards? Should you leave them in with a conditional compilation flag or with a run time flag?
  11. What is a buffer overflow and how can hackers exploit it?
  12. How can you use Valgrind to solve segfault problems?
  13. How does Valgrind catch access uninitialized memory?
Read More

2015-02-27
EPI in Python

We’ve begun the process of writing Python solutions!

Python versions of the program in the EPI sampler are listed below and
we would really appreciate your thoughts on them with respect to idiomaticity and clarity.

Python has exceptionally powerful libraries. Our programs by design use a simple subset of the
library but in many cases we also provide alternative Pythonistic solutions.

Solutions are written for Python 3.4.

Read More

2015-01-01
Register

Register

Fill out this registration form to get updates on interviewing trends, good practice problems, links to our blog posts, and updates to the book/website.


For example, we are implementing an online solution checking system, and would like to be able to let you know when it’s ready.


We will not be spamming you, and you will always have the option of opting out of receiving emails at any time. We reach out to you individually for feedback.

Read More

2014-11-16
EPI Ebook on Google Play

We’re happy to announce EPI is now available as an Ebook through Google Play!

Here’s the link, to the C++ version, which includes a sample. Here’s a link to the Java version.

You can read Google Play books on Android, IOS, and your computer:
Android instructions,
IOS instructions,
reading on your computer.

The Ebook is identical to the printed copy.

Read our post EPI in a nutshell to get a broader overview of our book.

Navigating the Ebook

The typographic quality of iBooks and Kindle is unacceptable for a book like EPI that has sophisticated tables, drawings, equations, code, etc. (The input to these formats is HTML and the result is hideous - trust us, we’ve tried.)

Google Play is the only ebook format that will render EPI perfectly. The PDF we provide Google includes hyperlinks that allow you to click on problems in the table of contents, and referenced page numbers. However, despite multiple attempts on our part, Google Play strips these links out, making the ebook slower to navigate and search.

With Google Play you buy the book, try it out, and ask for a refund within a certain time period, and we encourage you to take advantage of this facility.

Offline viewing
Some readers have had problems viewing the book offline. Here’s one reader’s experience, and his solution.

Last night when I disabled wifi, I noticed the book disappeared. Upon connecting to the wifi again I noticed the book eventually came back. I thought I had synced all pages manually, but I noticed I was missing a few pages in the middle. Apparently the app won’t let you view the book offline until all pages are synced. I noted that during all these times the blue circle with checkmark was to the bottom right of the book as if the book is synced, but that wasn’t the case.

I decided to sync those missing pages manually, but I noticed a weird thing after they were synced like a repetition of the same pages, like 65-68 couple of times in a row. I decided at that time to remove the book from downloads, and close the app altogether (double tap on home key and scroll up the app in the background). I thought about reinstalling the book app, but didn’t.

Then I started the download of the book again overnight…

This morning I noticed the blue checkmark, as if the book is synced. Upon opening it, I saw that the pages weren’t synced either. This time I went to the beginning of the book, and scroll to the end (faster if you put the device in horizontal/landscape/2pages mode). Making sure that all pages are synced. Then did a couple of tests relaunching the app after:

  • wifi disabled (app still in background)
  • wifi disabled, close app.
  • wifi disabled, rebooted ipad

and they all worked and I was able to read the book offline this time. Maybe the book was corrupted before ?

But I can tell that blue checkmark on the bottom right of the book doesn’t mean sync (at least not here)

Read More

2014-08-29
Why we wrote EPI

We wrote EPI for you!

EPI began as a Google Doc which we prepared for our friends who wanted to join companies
like Google, Facebook, Amazon, Microsoft, as well as hot startups.

Like you, they had talent, but were not familiar with the interviewing style
at these companies, and often failed to land their dream job.

For example, many of our friends had engineering and science degrees, or had been out of college for a while,
and were not prepared for data structures and algorithms interview questions.

EPI evens the playing field. Combined with your hard work, it will enable you
to interview successfully at the best companies.

Read our post EPI in a nutshell to get a broader overview of our book.

Read More