This is the second part of my old study guide for programming interviews.

Programming interviews have two components. There is a “*memorization of trivia from your first semester of Computer Science which you forgot about 4 years ago*” component and then there is a mental exercise (white boarding) component which is basically about how efficiently your brain can solve problems with someone breathing down your neck judging your every move and clicking their pen the whole time.

The mental exercise preparation component involves sitting down 30 minutes a day with a pad of paper and writing out solutions to problems without the help of a compiler. You can basically watch tv and do it, it isn’t too bad. I have found, historically, I can go from incompetent to passable at the white boarding thing by spending about 3-5 days working through a few of these problems on a daily basis. For the record I am not all that talented at this but this practice works for me. Too hard? Do an easier one. Trust your brain to get “in shape” when you do these…it happens when you sleep, the next day you will be 20% smarter each time.

These interviews are about efficiency. The more you practice + sleep, the more efficient your brain gets. If you are going through an all day interview, if you are not efficient you will get tired and make mistakes towards the end.

**Online Tests**

**Common Questions And Answers**

**http://maxnoy.com/interviews.html**

Reading: http://javarevisited.blogspot.com/2011/06/top-programming-interview-questions.html

- Find the middle element in a linked list:
- Solution: Use two pointer incrementers and advance one at half the speed of the other. When the leader hits the end you have the middle. 2x vs 1x.

- Find a loop in a linked list:
- Solution: Use two pointers, if they overlap at some point then its a loop e.g. one moves at 2x, the other at 1x

- Find the third element from the end of a linked list:
- Solution: Two pointers, one starts n – 3 of the other

- Implement Bubble sort and insertion sort
- Implement insert in a binary tree
- Shuffle cards in O(N)
- Feed cards into a binary tree picking left / right randomly then squash
- Spray values into an array at random by systematically performing a conversion on each card’s value of some sort

- What is the difference between insertion sort and selection sort
- Reverse words in a string (words are separated by one or more spaces). Now do it in-place.
- Write a program to print the fibonacci sequence + same with recursion

Note: use memoization

`fib(n): if n is in memo: return memo[n] if n <= 2: f = 1 else: f = fib (n-1) + fib(n-2) memo[n] = f return f`

- Given a binary tree, write code to print the tree out line by line
- Write a program to check if a number is a palindrome
- What is a binary search tree
- Implement a stack in java
- Rotate a matrix 45 degrees
- Reverse a linked list
- Do it with recursion
- Do it with iteration

- Difference between stack and queue?
- Stack = LIFO
- Queue = FIFO

- Stack vs. Heap
- Write a program that sorts a list of points by their X coordinate
- Write all permutations of a string
- Write a program to find all palindromes in a string
- Given two arrays, find the numbers not present in the second array
- Write a roman numeral converter
- Write a FizzBuzz solver
- Write a program that prints out the first 100 prime numbers
- Reverse a doubly linked list
- Given a dictionary and a list of letters, find the longest word using only the letters from the string
- Find a shortest path in a N*N matrix maze from (0,0) to (N,N), assume 1 is passable, 0 is not, 3 is destination, use memorization to cache the result
- Traverse a binary tree…
- Breadth first
- Depth first
- In order

- Write a routine to reverse every k nodes in a given linked list
- You are given a large set of integers, which are not sorted. Figure out a method to retrieve the largest 1000 elements, in O(n) time.
- How would you implement division without +, – or multiplication
- Given 10,000 servers containing a Billion integers each how would you find how to find the median?
- Write code to check if a number is a prime number
- Implement a seive of erasthanes (did I mention I think programming interviews are ridiculous?)
- How would you determine the “randomness” of an array of numbers
- Tell me all about Two’s compliment, make it super boring please
- Write a function to add two numbers without +, -, *, /

`int badd(int n1, int n2){ int carry, sum; carry = (n1 & n2) << 1; // Find bits that are used for carry sum = n1 ^ n2; // Add each bit, discard carry. if (sum & carry) // If bits match, add current sum and carry. return badd(sum, carry); else return sum ^ carry; // Return the sum. } int bsub(int n1, int n2){ // Add two's complement and return. return badd(n1, badd(~n2, 1)); }`

- Algorithm to determine if a tictac toe board is “Winning”
- Use dynamic programming to implement a fibonacci algorithm
- Remove every other item from a linked list, producing two linked lists
- How would you multiply two strings: “123” * “45”, without any casting
- N Choose K Problems (knapsack problems?)
- In order matrix transformation

`public void rotateInPlaceRecursive() { if( rowCount != colCount ) { throw new IllegalStateException("Matrix must be square"); } doRotateInPlaceRecursive(0); } public void doRotateInPlaceRecursive(int shrink) { if( shrink == rowCount/2 ) { return; } for (int col = shrink; col < colCount-shrink-1; col++) { int row = shrink; int top = tab[row][col]; int left = tab[rowCount-col-1][row]; int bottom = tab[rowCount-row-1][rowCount-col-1]; int right = tab[col][rowCount-row-1]; tab[row][col] = right; tab[rowCount-col-1][row] = top; tab[rowCount-row-1][rowCount-col-1] = left; tab[col][rowCount-row-1] = bottom; } doRotateInPlaceRecursive(shrink+1); }`

- Given a List structure where each node contains a Next node and optionally a pointer to another list, flatten that list

`L1 --> L2 --> L3 --> L7 --> L8 | v L4 --> L5-->L6`

WIll be flattened to

`L1 --> L2 --> L3 -->L4 -->L5-->L6-->L7-->L8`

**Practice Problems**

- Reading: http://leetcode.com/2010/04/hacking-google-interview-from-mit.html
- Reading:http://www.careercup.com/page

**Bit Manipulation**

- 0110 + 0010 = ?
- 0011 * 0101 = ?
- 1101 >> 2 = ?
- 1101 ^ 0101 = ?
- 1101 ^ (~1101) = ?
- 1101 & (~0 << 2) = ?
- does 0110 + 0110 = 0110 * 2?
- ^ == XOR
- ~ == ! (NOT), negation
- ~0 = !0 = 1
- Get, set, clear update a bit

**Implementation Problems**

- Implement bubble sort
- Implement insertion sort
- Implement quicksort
- Implement heap sort
- Implement a stack
- Implement a queue
- Implement a linked list
- Implement a binary tree
- Implement binary search

**Traversals**

- Trees:
- In order, post-order, pre-order traversals
- Breadth first, depth first

- Graphs
- BFS / DFS

**Data Structures**

**Binary Math**

- Byte, Bit, Megabyte, Megabit
- bit: 1 or 0
- Byte: 8 bits
- Megabyte: 1000^2 bytes

- Bit shift operations
- & (and)
- | (or)
- ^ (xor)
- ~ (not)

- Pointer arithmetic