Ex1.1

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

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

Design an algorithm and write code to remove the duplicate characters
in a string without using any additional buffer. NOTE: One or two
additional variables are fine. An extra copy of the array is not.
FOLLOW UP
Write the test cases for this method.
Ex1.5

Write a method to replace all spaces in a string with ‘%20’.
Ex1.5

Write a method to replace all spaces in a string with ‘%20’.
Ex1.6

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?
Ex.1.7

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

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”).
Ex2.1

Write code to remove duplicates from an unsorted linked list. FOLLOW UP
How would you solve this problem if a temporary buffer is not allowed?
Ex2.2

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

Implement an algorithm to delete a node in the middle of a single
linked list, given only access to that node.
EXAMPLE
Input: the node ‘c’ from the linked list a->b->c->d->e
Result: nothing is returned, but the new linked list looks like
a->b->d->e
EX2.5
Ex3.1
EX.3.2

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.
EX3.3

Imagine a (literal) stack of plates. If the stack gets too high, it
might topple. There- fore, in real life, we would likely start a new
stack when the previous stack exceeds some threshold. Implement a data
structure SetOfStacks that mimics this. SetOf- Stacks should be
composed of several stacks, and should create a new stack once the
previous one exceeds capacity. SetOfStacks.push() and SetOfStacks.pop()
should behave identically to a single stack (that is, pop() should
return the same values as it would if there were just a single stack).
FOLLOW UP
Implement a function popAt(int index) which performs a pop operation on
a specific sub-stack.
EX.3.4

In the classic problem of the Towers of Hanoi, you have 3 rods and N
disks of different sizes which can slide onto any tower. The puzzle
starts with disks sorted in ascending order of size from top to bottom
(e.g., each disk sits on top of an even larger one). You have the
following constraints:
(A) Only one disk can be moved at a time.
(B) A disk is slid off the top of one rod onto the next rod.
(C) A disk can only be placed on top of a larger disk.
Write a program to move the disks from the first rod to the last using
Stacks.
Ex3.5

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

Write a program to sort a stack in ascending order. You should not make
any assump- tions about how the stack is implemented. The following are
the only functions that should be used to write this program: push |
pop | peek | isEmpty.
Ex5.1

You are given two 32-bit numbers, N and M, and two bit positions, i and
j. Write a method to set all bits between i and j in N equal to M
(e.g., M becomes a substring of N located at i and starting at j).
EXAMPLE:
Input: N = 10000000000, M = 10101, i = 2, j = 6
Output: N = 10001010100
Ex5.2

Given a (decimal - e.g. 3.72) number that is passed in as a string,
print the binary rep- resentation. If the number can not be represented
accurately in binary, print “ERROR”