Monday, May 17, 2004

Software Interviews

by Asim Jalis

Here are some common interview questions. Reading these should help you in technical interviews at software companies. SCALABILITY Start with a simple example, then how do you scale it to 10,000 users, then again to 100,000. C++ AND JAVA EXCEPTIONS What are the differences between C++ and Java exceptions? (Checked and unchecked, C++ doesn't have an exception type, you can throw anything.) ROMAN NUMERALS Write a C function, int rtoa(char* s), that converts roman numerals such as XIX to integers. PERMUTE ARRAY Write a C function that permutes an array, int* a, in place without allocating any more memory, so that every permutation is equally likely. Prove that every permutation is equally likely. FIND THE MISSING INTEGER Consider an array, int a[N], of size N, that contains all the integers from 1 to N+1, with one of them missing. Since there are N slots one of them has to be missing. Write C code (or describe an algorithm) that finds which one is missing in O(n) time using no additional memory allocation. ELEVATOR CONTROL SYSTEM Design the high-level architecture of an elevator control system. Assume the system receives an event every time someone presses a button in the elevator, every time someone presses a button on a given floor. The system can also find out the current floor of the elevator, the state of the doors (open or close). The system controls the motor that moves the elevator, and can tell the elevator to go to a particular floor. This is an incomplete description of the system, so first you should ask questions from the interviewer to understand the system better. Then list the requirements. Then design the system. No coding is necessary. VENDING MACHINE Explore the issues involved in designing a preference based vending machine. The machine remembers what people ordered based on their RFID badges. It builds a database over time. There are multiple machines on different floors. What should the database store as a way to predict what people will order next time they go to a vending machine. How would you predict what to stock in the machine. Define what data needs to be stored. Describe algorithms for forecasting. Describe all the components of the system (the database, the machines, the management console, the wireless alerts to the stock supplier, etc) QUICK MATH Suppose you want to build a database containing all the people in the US (population approximately 250 million). Do back of the envelope calculations to estimate how large the database must be. The information about what should be stored in the database is deliberately left unspecified. You must ask the interviewer and/or make reasonable assumptions. MAXIMIZE SUBARRAY SUM Suppose you have an array of N random integers (can be positive, negative or zero), int a[N]. Find the indices i, j < N, such that the sum from a[i] to a[j] (inclusive) is the maximum. Find an O(N) algorithm for this. SCALING FOR E-COMMERCE Architect an e-commerce website. Start with a single web server, a single database. Now assume the traffic starts going up. How will you scale the site? Design the site so that it can be scaled to meet demand by adding more machines without rearchitecting it every time the traffic goes up. WHICH WAY DOES THE STACK GROW In C either the system stack grows up or grows down. Write a program that can determine whether the stack is growing up or down. C++ COPY CONSTRUCTOR In C++ what is the difference between a copy constructor and an assignment operator? What is the difference in what happens under the hood? Ignore the obvious difference in syntax. IDENTICAL BIRTHDAY PROBLEM Suppose you use a 64-bit random number to identify users of a system. If you pick two such random numbers, what is a probability that there will be a collision (they will be the same)? What is the probability that there will be a collision with 3 numbers? With 4? With 5? Let's say you pick N numbers. For what value of N will the probability of a collision be 0.5? IMPLEMENT STACK USING QUEUE Suppose you are given a stack implementation with the normal stack operations (create, delete, push, pop). How would you implement a queue using these stacks? All the queue operations (create, delete, enqueue, dequeue) should take O(1) time. FIND SMALLEST WITHOUT SORTING Given N integers find the 10 smallest in O(N) time. Suppose you have N points in 2D coordinates (each point is made up of x and y, which are both floats). Find the 10 points closest to the origin. The algorithm should take O(n) time. O(n*log n) algorithms are not acceptable, but you may want to try that first as a way to warm up to the problem. PRINT TREE BY LEVELS Suppose you have a binary tree containing N nodes. Each node has a Name, a LeftChild and a RightChild. Describe an algorithm to print the tree by levels. Print the root first, then all the children of the root, then all the grandchildren of the root. This is not as easy as it sounds. Your algorithm must take O(N) time. C# TRIVIA What are the two ways of implementing two dimensional arrays in C#? In C# what is generational garbage collection? JAVA TRIVIA In Java can you over-ride fields? If yes, then what is the difference between over-riding fields and methods? Suppose you have Foo x = new Bar() where Bar extends Foo. Suppose Bar over-rides both the methods and the fields of Foo. If you access the fields in x, whose fields will be accessed (the ones in Foo or the ones in Bar)? If you access the methods in x, whose methods will be accessed (Foo's or Bar's)? In J2EE, how do you store session information without using EJBs?