# CS61B Resources

Note: This page will likely change as I get more time to work on this, but I'll try not to move too many things around. Additionally, these are unofficial resources that I am posting up which have not been quality-checked by the rest of the CS61B course staff.

Official course resources can be found on the Resources section of the CS61B website.

## Teaching (Spring 2015)

I teach the following discussion sections and labs:

• DIS 129: Tu 6-7pm at 12 Haviland

• DIS 132: W 9-10am at 3111 Etcheverry

• LAB 29: Th 7-9pm at 273 Soda

My office hours are Wed 10-11am in Garabini Lounge. I am also available by appointment; please email me to set up a time to meet.

Discussion worksheets can be found at on the course website.

Additional resources which I have created for my sections are linked below:

## Interview Resources

This is by no means a comprehensive list of resources, and was quickly thrown together in about 30 minutes before my discussion section for the week. I will try to find time to polish these a little bit in the near future.

Technical Interview Workshop (Prepare for the Trivial)

These are some notes that I took from an interview workshop which was hosted by Hackers at Berkeley back in March 2012. I'll try to clean it up and make it more understandable as I have time. This was the workshop where I first learned the basics of tech interviews.

Cracking the Coding Interview (Gayle McDowell)

This is an excellent book with many, many practice questions. It is also a good resource for reviewing a lot of material that is common in technical interviews.

This is a draft version of the textbook that is used in UC Berkeley's CS170 course. Most of these I wouldn't worry too much about until you are a junior. The most important things you will probably see in technical interviews are:

• Asymptotic Analysis (incl. Master's Theorem)

• Search Algorithms: Breadth First Search, Depth First Search, Djikstra's Algorithm, Bellman-Ford Algorithm

• Dynamic Programming

• NP-Hard Problems and Reductions

The problems in this book are hard! You'll encounter plenty of them when you take CS170.

Glassdoor

This is a website with reviews about companies to work for. You will often find examples of some interview problems which serve as good practice. Go through these not with the intention of trying to memorize past interview questions -- it is painfully clear if you are trying to fake that you have not seen a certain interview question, and honestly, your time would be better spent doing other preparation -- but so that you get an idea of what level of questions to expect.

Topcoder

Another good resource for plenty of interview questions.

Get That Job at Google (Steve Yegge)

This is a blog post that I was linked to as an interview prep resource by a Google recruiter. You may find this helpful.

### Practice Set 1

Released: March 10, 2015 (Solutions)

These questions have been modified and adapted from interview questions I have seen before.

For each of the below questions, remember to: (1) talk through a high-level algorithmic idea, (2) code in the language of your choice, (3) check your code with some test cases, and (4) discuss the runtime and space complexities of your solution. At first, focus on just getting a solution that is reasonably efficient; you can always go back and optimize your code later. The times I have included are rough target times; don't worry too much about these.

Question 1. (15 min) Implement a function pow(a, b) which takes in two integers $$a$$ and $$b$$ and computes $$a^{b}$$. You may assume that $$b$$ is a non-negative integer.

Question 2a. (10 min) Consider a scenario where you have a String, a starting index, and an ending index. Write a function which counts the number of spaces between the two indices, inclusive.

Question 2b. (15 min) Now let's say we have a really long String and it doesn't change (the indices, however, may be different each time). You will be running many queries on this String. How would write a more efficient solution?

### Practice Set 2

Released: March 16, 2015 (Solutions)

These questions have been modified and adapted from interview questions I have seen before.

For each of the below questions, remember to: (1) talk through a high-level algorithmic idea, (2) code in the language of your choice, (3) check your code with some test cases, and (4) discuss the runtime and space complexities of your solution. At first, focus on just getting a solution that is reasonably efficient; you can always go back and optimize your code later. The times I have included are rough target times; don't worry too much about these.

For each of the below, you may assume that you have a TreeNode class which knows its parent, its left child, its right child, and its value. If you need any additional behavior, you will need to write the code yourself.

Question 1. (20 min) Implement a function which takes as input a preorder traversal and inorder traversal of a binary tree, and outputs the root of the reconstructed tree.

Question 2. (15 min) Given a sorted array of integers, write a function which converts the sorted array into a balanced binary search tree.

Question 3. (10 min) Reverse each word in a given input String. For example: "I love CS61B" would become "I evol B16SC".

### Practice Set 3

Released: March 30, 2015 (Solutions)

Question 1. (20 min) Write a function which reads a text file and finds the ten most occurring words in the file.

Question 2. (30 min) Write a function which takes as input a tree and returns a list of all duplicate subtrees. For example:

Input:    1         Output: [ 2  ,  3  ]
/ \                [  \       ]
2   2               [   3      ]
\   \
3   3


### Practice Set 4

Released: April 13, 2015 (Solutions Delayed, sorry)

Question 1. (10 min) Assume there is a sorted array that has been "rotated" k times. For instance:

[a, a, b, c, d, e, f, f]  -- Rotate by 3 -> [e, f, f, a, a, b, c, d]


Given this rotated array, reconstruct the original array.

Question 2. (15 min) Imagine you're driving across the country and you turn on the car's stereo. You wish to write a program that will automatically set the six presets on your stereo to the six frequencies which are strongest at the time. Write a function which takes as input, the minimum frequency, the maximum frequency, and the interval between frequencies, and returns the six frequencies you want to set. You are given a helper function which takes in the min frequency and max frequency of a frequency band and returns the signal strength.

Question 3. (15 min) Given the following API, write a function that takes as input a NestedInteger and computes the weight of a nested list. We define weight as the sum of all integers in the list weighted by their depth. For example, given the list {{1, 1}, 2, {1, 1}}, the function should return 10 (four 1's at depth 2, one 2 at depth 1). As another example, the list {1, {4, {6}}} should have a weight of 27 (one 1 at depth 1, one 4 at depth 2, and one 6 at depth 3).

You may assume that the NestedInteger class has the following interface:

                
public interface NestedInteger {
/**
* @return true if this NestedInteger holds a single integer, rather than a nested list
*/
boolean isInteger();

/**
* @return the single integer that this NestedInteger holds, if it holds a single integer
* Return null if this NestedInteger holds a nested list
*/
Integer getInteger();

/**
* @return the nested list that this NestedInteger holds, if it holds a nested list
* Return null if this NestedInteger holds a single integer
*/
List getList();
}



### Practice Set 5

Released: April 20, 2015 (Solutions on April 27)

Question 1. (25 min) Consider the problem where you have an old-fashioned weighing scale and many balls. All of these balls are identical in weight except for one, which is slightly heavier. Return the index of the ball which is the heavier one. You may assume you have the following method signatures available:

int heavyBall(Ball[] balls) -- the function you will be writing

int weigh(Ball[] balls) -- returns -1 if left side is heavier, 0 if equal, and 1 if right side is heavier

Question 2. (15 min) Given an array of integers A, you want to find a magical number in that array. The magical number is defined as any number in the array where A[i] = i. When you find this number, return the index, otherwise return -1. (You may assume there is at most one magical number for now.)

Question 3. (10 min) You have a list of sorted lists. Write a function which merges these lists into a single list in sorted order.