-
Sudoku
Write an algorithm for Soduku puzzle
-
Dictionary Lookup
What method would you use to look up a name in a dictionary?
-
Stack Growth
How would you find out if a machine's stack grows up or down in memory?
-
Random
Given a function which produces a random integer in the range 1 to 5,
write a function which produces a random integer in the range 1 to 7.
-
DFS
Describe the algorithm for a depth-first graph traversal.
-
Card Game
Design a class library for writing card games.
-
Phone Numner
You need to check that your friend, Bob, has your correct phone number,
but you cannot ask him directly. You must write a the question on a
card which and give it to Eve who will take the card to Bob and return
the answer to you. What must you write on the card, besides the
question, to ensure Bob can encode the message so that Eve cannot read
your phone number?
-
Special Debugging
You are given a the source to a application which is crashing when run.
After running it 10 times in a debugger, you find it never crashes in
the same place. The application is single threaded, and uses only the C
standard library. What programming errors could be causing this crash?
How would you test each one?
-
Next Prime
Given a number, describe an algorithm to find the next number which is prime.
-
Order functions
Order the functions in order of their asymptotic performance
* 2^n
* n^Googol ( 10^100)
* n!
* n^n
-
BST
what is the best and worst performance time for a hash tree and binary search tree?
-
String
What is the best and worst time for the operation 'equals'
How do you spedup the 'equals' operation
Write a function (and dictate it to your interviewer) that reverse the
order of words in a sentence. The final algorithm should work
in-place!! E.g.: "This is a sample" --> "sample a is This"
-
Multi Threading
Trade offs between a multi threaded and single threaded implementation ?
N threads .. n resources .. what protocol do you use to ensure no deadlocks occur?
-
N N-1
There are a set of 'n' integers. Describe an algorithm to find for each
of all its subsets of n-1 integers the product of its integers.
-
Sorting
Describe Sorting algorithms and their complexity - Quick sort, Insertion Sort, Merge Sort,Shell,Radix,Heap
If you had a million integers how would you sort them and how much memeory would that consume?
-
Check for Square
Describe an alogrithm to find out if an integer is a square?
-
Adwords
How would you determine if adwords was up and running and serving contextual content ?
-
NXN Matrix
Suppose you have an NxN matrix of positive and negative integers. Write
some code that finds the sub-matrix with the maximum sum of its
elements.
-
Division
Implement division (without using the divide operator, obviously).
-
Infinite Queries
You have a stream of infinite queries (ie: real time Google search
queries that people are entering). Describe how you would go about
finding a good estimate of 1000 samples from this never ending set of
data and then write code for it.
-
Trees
Tree search algorithms. Write BFS and DFS code, explain run time and
space requirements. Modify the code to handle trees with weighted edges
and loops with BFS and DFS, make the code print out path to goal state.
-
Minimum of List
You are given a list of numbers. When you reach the end of the list you
will come back to the beginning of the list (a circular list). Write
the most efficient algorithm to find the minimum # in this list. Find
any given # in the list. The numbers in the list are always increasing
but you don’t know where the circular list begins, ie: 38, 40, 55, 89,
6, 13, 20, 23, 36.
-
Google Home Server
Design a web server that serves the Google homepage. a) What are the
requirements. b) Design a multi threaded web server that uses shared
memory instead of disk access. c) Design a work load balancer for their
data centers. d) Design a DNS server that returns the IP address of a
data center that has the best connectivity relative to your IP.
-
SnS Link Amazon Interview Questions Puzzles and Algorithms