Hash Tables
While not all problems can be solved with hash tables, a
shocking number of interview prob-
lems can be Before
your interview, make sure to practice both using and implementing
hash tables
1 public
HashMap<Integer, Student> buildMap(Student[] students) {
2
HashMap<Integer, Student> map = new HashMap<Integer,
Student>();
3 for (Student s :
students) map.put(s.getId(), s);
4 return map;
5 }
ArrayList (Dynamically Resizing Array):
An ArrayList, or a dynamically resizing array, is an array
that resizes itself as needed while
still providing O(1) access
A typical implementation is that when a vector is full, the array
doubles in size Each
doubling takes O(n) time, but happens so rarely that its amortized time
is still O(1)
1 public
ArrayList<String> merge(String[] words, String[] more) {
2
ArrayList<String> sentence = new ArrayList<String>();
3 for (String w :
words) sentence.add(w);
4 for (String w :
more) sentence.add(w);
5 return sentence;
6 }
StringBuffer / StringBuilder
Question: What is the running time of this code?
1 public String
makeSentence(String[] words) {
2 StringBuffer
sentence = new StringBuffer();
3 for (String w :
words) sentence.append(w);
4 return
sentence.toString();
5 }
Answer: O(n^2), where n is the number of letters in
sentence Here’s why: each time you
append a string to sentence, you create a copy of sentence
and run through all the letters in
sentence to copy them over
If you have to iterate through up to n characters each time in the
loop, and you’re looping at least n times, that gives you an
O(n^2) run time Ouch!
With StringBuffer (or StringBuilder) can help you avoid this
problem
1 public String
makeSentence(String[] words) {
2 StringBuffer
sentence = new StringBuffer();
3 for (String w :
words) sentence.append(w);
4 return
sentence.toString();
5 }
Linked list questions are extremely common These can range from simple (delete a node
in
a linked list) to much more challenging Either way, we advise you to be extremely
comfort-
able with the easiest questions Being able to easily manipulate a linked list
in the simplest
ways will make the tougher linked list questions much
less tricky With that said, we present
some “must know” code about linked list manipulation You should be able to easily write
this code yourself prior to your interview
Creating a Linked List:
1 class Node {
2 Node next = null;
3 int data;
4 public Node(int
d) { data = d; }
5 void
appendToTail(int d) {
6 Node end = new Node(d);
7 Node n = this;
8 while (n.next !=
null) { n = n.next; }
9 n.next = end;
10 }
11 }
Deleting a Node from a Singly Linked List
1 Node
deleteNode(Node head, int d) {
2 Node n = head;
3 if (n.data == d)
{
4 return
head.next; /* moved head */
5 }
6 while (n.next !=
null) {
7 if (n.next.data
== d) {
8 n.next =
n.next.next;
9 return head; /*
head didn’t change */
10 }
11 n = n.next;
12 }
13 }
Whether you are asked to implement a simple stack /
queue, or you are asked to implement
a modified version of one, you will have a big leg up on
other candidates if you can flawlessly
work with stacks and queues Practice makes perfect! Here is some skeleton code for a Stack
and Queue class
Implementing a Stack
1 class Stack {
2 Node top;
3 Node pop() {
4 if (top != null)
{
5 Object item =
top.data;
6 top = top.next;
7 return item;
8 }
9 return null;
10 }
11 void push(Object
item) {
12 Node t = new Node(item);
13 t.next = top;
14 top = t;
15 }
16 }
Implementing a Queue
1 class Queue {
2 Node first, last;
3 void
enqueue(Object item) {
4 if (!first) {
5 back = new
Node(item);
6 first = back;
7 } else {
8 back.next = new
Node(item);
9 back =
back.next;
10 }
11 }
12 Node
dequeue(Node n) {
13 if (front !=
null) {
14 Object item =
front.data;
15 front =
front.next;
16 return item;
17 }
18 return null;
19 }
20 }
Trees and graphs questions typically come in one of two
forms:
1 Implement a tree /
find a node / delete a node / other well known algorithm
2 Implement a
modification of a known algorithm
Either way, it is strongly recommended to understand the
important tree algorithms prior to
your interview If
you’re fluent in these, it’ll make the tougher questions that much easier!
We’ll list some of the most important
When given a binary tree question, many candidates assume
that the interviewer means
“binary search tree”, when the interviewer might only mean
“binary tree ” So, listen carefully
for that word “search
” If you don’t hear it, the
interviewer may just mean a binary tree with
no particular ordering on the nodes If you aren’t sure, ask
Binary Trees—”Must Know” Algorithms
You should be able to easily implement the following
algorithms prior to your interview:
» In-Order: Traverse
left node, current node, then right [usually used for binary search
trees]
» Pre-Order:
Traverse current node, then left node, then right node
» Post-Order:
Traverse left node, then right node, then current node
» Insert Node: On a
binary search tree, we insert a value v, by comparing it to the root If v
> root, we go right, and else we go left We do this until we hit an empty spot in the
tree
Note: balancing and deletion of binary search trees are
rarely asked, but you might
want to have some idea how they work It can set you apart from other candidates
Graph Traversal—”Must Know” Algorithms
You should be able to easily implement the following
algorithms prior to your interview:
» Depth First
Search: DFS involves searching a node and all its children before proceed-
ing to its siblings
» Breadth First
Search: BFS involves searching a node and its siblings before going on
to any children
