Implement an algorithm to determine if a string has all unique characters. What if you can not use additional data structures?

Write code to reverse a C-Style String. (C-String means that “abcd” is represented as !ve characters, including the null character.)

Note: One or two additional variables are okay. An extra copy of the array is not.

Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?

Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0.

Assume you have a method isSubstring which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring (i.e., “waterbottle” is a rotation of “erbottlewat”).

Follow Up: How would you solve this problem if a temporary buffer is not allowed?

Implement an algorithm to find the nth to last element of a singly linked list.

Result: nothing is returned, but the new linked list looks like a->b->d->e

A (corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list.

1. Describe how you could use a single array to implement three stacks.

How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.

Follow Up: Implement a function popAt(int index) which performs a pop operation on a specific sub-stack.

SetOfStacks should be composed of several stacks, and should create a new stack once the previous one exceeds capacity.

pop() should return the same values as it would if there were just a single stack).

Write a program to move the disks from the first rod to the last using Stacks.

Implement a MyQueue class which implements a queue using two stacks.

You should not make any assumptions about how the stack is implemented.

The following are the only functions that should be used to write this program: push | pop | peek | isEmpty

A balanced tree here is defined to be a tree such that no two leaf nodes differ in distance from the root by more than one.

Given a directed graph, design an algorithm to find out whether there is a route between two nodes.

Given a sorted (increasing order) array, write an algorithm to create a binary tree with minimal height.

Write an algorithm to find the 'next' node of a given node in a binary search tree where each node has a link to its parent.

Note: it can be any path in the tree - it doesn't have to start at the root.

e.g. M becomes a substring of N located at i and a starting at j

If the number can not be represented accurately in binary, print "ERROR"

Given an integer, print the next smallest and next largest number that have the same number of 1 bits in their binary representation.

Prove your answer (by providing an example, or showing it's impossible).

Note: The jugs are oddly shaped, such that filling up exactly 'half' a jug would be impossible.

The men cannot tell each other (in any way) that they have a hat.

You're given 2 eggs. Find N, while minimizing the number of drops for the worst case.

After his 100th pass in the hallway, in which he toggles only locker number 100, how many lockers are open?

Explain how you would sub-class it to implement particular card games.

If the TL is not free or not able to handle it, then the call should escalate to PM.

Design the data structures and explain an algorithm to solve the puzzle.

Each Othello piece is white on one side and black on the other.

When a piece is surrounded by its opponents on both the left and right sides, or both the top and bottom, it is said to be captured and its color is flipped.

On your turn, you must capture at least one of your opponent's pieces.

Describe the data structures and algorithms that you would use to implement a garbage collector in C++.

That is, given a screen (represented by a 2-dimensional array of Colors), a point, and a new color, fill in the surrounding area until you hit a border of that color.

Given an infinite number of quarters, dimes, nickels, and pennies, write code to calculate the number of ways of representing n cents.

Write an algorithm to print all ways of arranging eight queens on a chess board so that none of them share the same row, column or diagonal.

You are given two sorted arrays, A and B, and A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order.

Write a method to sort an array of strings so that all the anagrams are next to each other.

If you have a 2 GB file with one string per line, which sorting algorithm would you use to sort the file and why?

Find “ball” in [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”, “”, “dad”, “”, “”] will return 4

Find “ballcar” in [“at”, “”, “”, “”, “”, “ball”, “car”, “”, “”, “dad”, “”, “”] will return -1

Given a matrix in which each row and each column is sorted, write a method to find an element in it.

Input (ht, wt): (5, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110)

Output: The longest tower is length 6 and includes from top to bottom: (56, 90) (60,95) (65,100) (68,110) (70,150) (75,190)

Game #2: You get three shots and you have to make 2 of 3 shots.

If p is the probability of making a particular shot, for which values of p should you pick one game or the other?

Similarly find the probability of collision with 'n' ants on an 'n' vertex polygon.

Given two lines on a Cartesian plane, determine whether the two lines would intersect.

Given two squares on a two dimensional plane, find a line that would cut these two squares in half.

Given a two dimensional graph with points on it, find a line which passes the most number of points.

Design an algorithm to find the kth number such that only prime factors are 3, 5, and 7.

How would you load test a webpage without using any test tools?

Describe different methods you considered and why you would recommend your approach.

The feed will be used by 1,000 daily users in a web application.

The array may have duplicate entries and you do not know what N is.

With only 4KB of memory available, how would you print all duplicate elements in the array?

If you were designing a web crawler, how would you avoid getting into infinite loops?

Write a function to swap a number in place without temporary variables.

Design an algorithm to figure out if someone has won in a game of tic-tac-toe.

Write an algorithm which computes the number of trailing zeros in N factorial.

The computer has four slots containing balls that are red (R), yellow (Y), green (G) or blue (B). For example, the computer might have RGGB.

You, the user, are trying to guess the solution. You might, for example, guess YRGB.

When you guess the correct color for the correct slot, you get a "hit". If you guess a color that exists but is in the wrong slot, you get a "pseudo-hit" .For example, the guess YRGB has 2 hits and 1 pseudo hit.

For each guess, you are tld the number of hits and pseudo-hits.

Write a method that, given a guess and a solution, returns the number of hits and pseudo hits.

Given an integer between 0 and 999,999, print an English phrase that describes the integer (eg, "One Thousand, Two Hundred and Thirty Four")

Design a method to find the frequency of occurrences of any given word in a book.

Element -> Element Attr* END Element END [aka, encode the element tag, then its attributes, then tack on an END character, then encode its children, then another end tag]
Attr -> Tag Value [assume all values are strings]
END -> 01
Tag -> some predefined mapping to int
Value -> string value END

Is there anything else you could do to (in many cases) compress this even further?

Write a method to generate a random number between 1 and 7, given a method that generates a random number between 1 and 5 (i.e. implement rand7() using rand5())

Design an algorithm to find all pairs of integers within an array which sum to a specified value.

Assume that you are given a random number generator which is perfect.

It must be a perfect shuffle - in other words, each 52! permutations of the deck has to be equally likely.

Assume that the computer memory can hold all one billion numbers.

Given a string s and an array of smaller strings T, design a method to search s for each small string in T.

Write a program to find and maintain the median value as new values are generated.

Design an algorithm to find the maximum subsquare such that all four borders are filled with black pixels.

Given an NxN matrix of positive and negative integers, write code to find the submatrix with the largest possible sum.

Given a dictionary of millions of words, give an algorithm to find the largest possible rectangle of letters such that every row forms a word (reading left to right) and every column forms a word (reading top to bottom).