CtCI

17 Jan 2014

####Google

Pay attention to Bit Manipulation

####General

Scalability

####Build a strong network

1. Meetup.com or alumni network
2. Be open
3. LinkedIn
4. Be helpful

####Compile a preparation grid

See Page.40

####Power of 2 table

See Page.47

####5 Steps to a technical question

1. Resolve ambiguity
2. Design an algorithm
3. Write pseudocode first(tell about it)
4. Write code at moderate pace
5. Test and fix

####5 Algorithm approaches

1. Examplify
2. Pattern matching
3. Simplify and generalize
4. Base case and build
5. Data structure brainstorm

##Interview Questions

###Data Structures

###1. Arrays and Strings

#####Hash Tables Implementing a hash table…

#####ArrayList(Dynamically Resizing Array)

#####StringBuffer Implement your own version of StringBuffer

#####1.1

• Forgot the fact that if the string contains unique chars, then the length should be $<=$ length of alphabet
• Need to familiaze with bit manipulation

#####1.3

• For string equal, use String.equals(anotherStr), == only determines if it is identical
• If possible, try to cut out some temporary variables
• If one is permutation of another, they must have the same length
• Always think of some property to minimize the computation
• The pattern to sort an string: toCharArray then sort
• Forget about case sensitive and whitespace

#####1.4

• Watch out about i++ etc
• I really don’t know that I’ll have the true length of the string(But it says it in the question)Read!!
• Starting backwards is really a excellent idea.

#####1.5

• Forget about the last sentence: the addition case
• As long as there is loop, watch out for array out of index!
• An alternative to StringBuffer would be declare the char array with enough space upfront
• Review the countCompression when possible

#####1.6

• It is not neccessary to use recursion
• It’s easy to fall into the thinking pattern that every index, position starts with 0
• It’s actually matrix transformation

#####1.7

• The thinking is easy
• But think further to reduce the space
• We only care about if one row or column has an zero, we don’t care about the exact location

#####1.8

• Abstract the problem!
• Again, length of strings

---

###2. Linked Lists

#####Creating a Linked List

First find the tail, then append the node at the end.

#####Deleting a Node

• Watch out if it’s a singly linked list or doubly linked list
• In C, C++ you’ll also have to care about memory management

#####The “Runner” Technique

Introduce a second pointer, different pointers have different pace of movement.

#####Recursive Problems

Using recursion is a way out, but that means O(n) space.

#####2.1 Remove duplicates

• LinkedListNode
• HashTable is an important thing(constant to add, find)
• Watchout if head is null
• The loop condition: (n != null)
• The code is very subtle

#####2.2 kth to last element

• Edge case!! Care about every parameter
• You never know if n.next is a null pointer or not, So check everytime you access next field

#####2.3 delete node with only access to that node

• Think harder
• Think outside the box, you may not need to actually eliminate the node in the memory, just make the linked list right after “delete”
• If n is the last node, you cannot delete it. Because you cannot make it null. Consider marking the node as dummy.

#####2.4 partition linked list around value x

• Watch out when you return something, it should not be some value instead of null
• Think about the special case where the linked list is un-balanced around x
• Be careful about pointer operations

#####2.5 linked list addition

• The recursive way is very sutle, pay attention
• Think about all the possible state of the function call
• To put code in separate method is a very clean way
• Must do it again!

#####2.6 beginning of the loop

• Find collision point is easy: runner
• But find the beginning is another story
• Need to do the math and use the property of loop

#####2.7 palindrome detect

• Only need to detect if the front half is the reverse of the second half
• Reverse order: the help of stack!

---

###3. Stacks and Queues

#####3.1 three stacks in one array

• Read the question carefully, seriously
• Maybe use a linked list to store all index of the stacks, take O(n) to initialize but doesn’t waste space

#####3.2 stack returns minimum in constant time

• The min changes when you push and pop
• Pay attention to memory optimization

#####3.3 set of stacks

• Need to revisit the FOLLOW-UP

#####3.4 Hanoi using stack

Base Case and Build approach:

1. $$n = 1$$

   Pretty easy

2. $$n = 2$$

   Tower 2 as a buffer

3. $n = 3$ etc

• Don’t be afraid of recursion!

#####3.5 MyQueue with two stacks

• don’t settle for naive solution, try to optimize it!