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?
