Explain OO

Explain Object Oriented Programming to a non-technical person. Try and explain the basics as well as the more advanced topics. Include discussion on polymorphism, inheritence, design patterns, etc.

Most importantly explain the pros and cons of this programming model.

Measuring Search Quality

How would you measure the quality of a search engine?

Google PM Question

k closest points to the origin

given n points in 2d space, write an efficient method that will return the k closests points to the origin. Analyze the complexity of the algorithm.

Find a sum in an array

Given an array of integers and a single integer, X. Determine if two integers in the array sum to make X.

Provide a variety of solutions focusing on possible optimal aspects: time complexity, space complexity, in place, closest pair, etc.

Unique, Union, Intersection

Given two lists of IP addresses, describe, design and impliment an efficient algorithm to find the unique IPs in each list, the union of the two lists and the intersection of the two lists.

open and closing doors

There are a hundred doors all closed. Starting from the first door, I open every other door. Then from the beginning again, I open/close every 3rd door, depending on it's current state. In this case, I would open the 3rd door, but close the 6th door which was open from the first pass. Repeat this for every 4th, 5th, 6th etc until I only toggle the 100th door.

Given any door number, can you tell me if it will be open or closed at the end?

Unmatched number

An array has pairs of positive integers in random order. One integer is accidently changed to -1. Return the array to its original state.

O(n) time.
O(1) space.

final, finally, finalize [java]

in java, what are final, finally and finalize used for?

Spinning Disk

half a disk is painted black, the other half white.
a sensor can detect if a point on the disk is black or white.

what is the minimum number of sensors you need and where would you place them in order to determine if a disk was spinning clockwise or counter-clockwise?

atoi

a very common question. implement atoi(String), where String is an object or type or pointer or array depending on your language of choice. Obviously, do not use libraries which would make this conversion trivial such as Integer.parseInt(String s) in java.

Stacks and Queues

Implement a stack using two queues. [push(), pop()]

Implement a queue using two stacks. [enqueue(), dequeue()]

List some test cases.

Processes in *nix

If you claim to be a "linux guru"... you should be at least be able to name one of the commands that list the processes that are currently running.

You don't have to be overly humble on your resume... but don't make claims you can't support in an interview.

Reverse a linked list

Simple one today, but surprising how many people can't actually code this properly.

Reverse a singly linked list.

Breaking a linked list with a cycle

Given a singly linked list with a cycle, break the cycle.

This can be done in O(n) time, O(1) space.