# 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
(http://savenseek.com/page/Amazon_Interview_Questio)
