Week Twelve —
Preparing For Interviews: Tricks, Tips, and Tests

As you wind down this semester, your last one as an LMU CS undergrad [...gets misty-eyed a bit...] you are probably [nay, HOPEFULLY] considering what your next steps will be. For most of you that means some form of [cue the theme from Psycho....] employment! With that in mind, Erica Eddings from the Career and Professional Development office has set up a special session for us. Thusly, tonight's class will be focused on giving you a heads-up for your industry interviews!!

AGENDA

1. 16:20 – 16:30: Class — Review & Prep
2. 16:30 – 17:30: Tech Interview Tips Panel [including Q & A
3. 17:30 – 17:45: Networking time [informal]
4. 17:45 – 18:45: Coding Test Practice [(]some panelists may stay, but not all are able]
5. 18:45 – 19:20: Class — Debriefing session

We will have four or five people on the panel, and your humble professor will assist the Divine Ms. E with moderating duties. Topics to be discussed will include but not [necessarily] be limited to:

• What are the top sought after skills desired and required to be successful in the field?
• How can students prepare now for a technical interview?
• Any applicant/recruitment pet peeves?
• What does your day-to-day look like?
• What is the best piece of advice you can give college students in the job market?

Coding Interview Questions: Free Play!!

The following questions are glommed from the book Cracking the Coding Interview by Gayle Laakmann McDowell [ISBN: 978-0-9847828-0-2 – 2013 edition]. The problems are presented below, and are grouped into easy, medium, and hard problems. The several different topics are all mixed together so feel free to pick one or two that interest you or seem like good puzzles and have at it! It's probably not a bad idea to work in small teams of two or three people, to discuss possible solutions, and you are welcome to ask the panel members or your humble professor for advice or to discuss things with us, but do NOT ask for solutions, until you've at least tried it out for yourself first.

I will have my copy of the book in class, so after the hour is over, I can show you or tell you the book solutions. Obviously, this is for PRACTICE, not for grade, but in the spirit of the exercise, try not to use your own copy of the book... the thrust here is to use your critical thinking skills!

Coding Problems, Exercises, and Questions

The Good – Low Difficulty

• Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures? [1.1 p.73]
• Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2b1c5a3. If the compressed string would not become smaller than the original string, your method should return the original string. [1.5 p.73]
• Write code to remove duplicates from an unsorted linked list. A follow-on question: how would you solve this problem if a temporary buffer is not allowed? [2.1 p.77]
• Implement a function to determine if a linked list is a palindrome [2.7 p.78]
• Implement a function to check if a binary tree is balanced. For the purposes of this question, a balanced tree is defined to be a tree such that the heights of the two subtrees of any node never differ by more than one. [4.1 p.86]
• You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum to a given value. The path does not need to start or end at the root or at a leaf. [4.9 p. 86]
• A monochrome screen is stored as a single array of bytes, allowing eight consecutive pixels to be stored in one byte. The screen has width W where W is divisible by 8 [that is, no byte will be split across rows]. The height of the screen, of course, can be derived from the length of the array and the width. Implement a function drawHorizontalLine( byte[] screen, int width, int x1, int x2, int y) which draws a horizontal line from (x1, y) to (x2, y). [5.8 p.92]
• Given two lines on a Cartesian plane, determine whether the two lines would intersect. [7.3 p.102]
• Design and implement a hash table which uses chaining [linked lists] to handle collisions. [8.10 p.106]
• Imagine you are reading in a stream of integers. Periodically, you wish to be able to look up the rank of a number X [the number of values less than or equal to X]. Implement the data structures and algorithms to support these operations. That is, implement the method track(int x), which is called when each number is generated, and the method getRankOfNumber(int x), which returns the number of values less than or equal to X [not including X itself]. [11.8 p.122]
  EXAMPLE: Stream [in order of appearance]: 5, 1, 4, 4, 5, 9, 7, 13, 3
  getRankOfNumber(1) = 0
  getRankOfNumber(3) = 1
  getRankOfNumber(4) = 3

The Bad – Medium Difficulty

• 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? [1.6 p.73]
• 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 the second is a rotation of the first using only one call to isSubString() (e.g., waterbottle is a rotation of erbottlewat. [1.8 p.73]
• You have two numbers represented by a linkd list, in which each node of the list contains a single digit of the number. The digits are stored in reverse order, such that the one's digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list. [2.5 p.77]
  EXAMPLE input: [7-> 1-> 6] + [5-> 9-> 2] meaning 617 + 295
  EXAMPLE output: [2-> 1-> 9]
• Write a program to sort a stack in ascending order [with the biggest items on the top]. You may use at most one additional stack to hold items, but you may NOT copy the elements into any other data structure [such as an array]. The stack supports the following operations: pushd, pop, peek, and isEmpty. [3.6 p.81]
• Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure. NOTE: this is not necessarily a binary search tree. [4.7 p.86]
• You have 20 bottles of pills. Nineteen bottles have 1.0 gram pills, but one has pills of weight 1.1 grams. Given a scale that provides an exact measurement, how how would you find the heavy bottle? You can only use the scale once. [6.1 p.95]
• Design an algorithm to find the kth number such that the only prime factors are 3, 5, and 7. [7.7 p.102]
• Imagine you have a call center with three levels of employees: respondent, manager, and director. An incoming telephone call must be first allocated to a respondent who is free. If the respondent can't handle the call, s/he must escalate the call to a manager. If the manager is not free or is not able to handle it, then the call should be escalated to a director. Design the classes and data structures for this problem. Implement a method dispatchCall() which assigns a call to the first avialable employee.
• You have a stack of n boxes with widths W_i, heights H_i, and depths D_i. The boxes cannot be rotated and con only be stacked on top of one another if each box in the stack is strictly larger than the box above it in width, height, and depth. Implement a method to build the tallest stack possible, where the height of a stack is the sum of the heights of each box. [9.10 p.110]
• You are given two sorted arrays, A and B, where A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order. [11.1 p.121]
• You are given the source to an application which crashes when it is run. After running it ten times in a debugger, you find it never crashes in the same place. The application is single-threaded, and uses only the C standard library. What programming errors could be causing this crash? How would you test each one?

The Ugly – High Difficulty

• In the classic problem of the Towers of Hanoi, you have three towers 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 (i.e., each disk sits atop a larger one). You have the following contstraints:
  
  • only one disk can be moved at a time
  • a disk is slid off the top of one tower and onto the next tower
  • a disk can only be placed on top of a larger disk
  Write a program to move the disks from the first tower to the last tower using stacks. [3.4 p.81]
• You have two very large binary tree: T1 with millions of nodes, with millions of nodes and T2 with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1. A tree T2 is a subtree of T1 if there exists a node n in T1 such that the subtree of n is identical to T2. That is, if you cot off the tree and node n, the two trees would be indentical. [4.8 p. 86]
• An array Acontains all the integers from 0 to n, except for one number which is missing. In this problem, we cannot access an entire integer in A with a single operation. The elements of A are represented in binary, and the only operation we can use to access them is fetch the jth bit of A[i], which takes constant time. Write code to find the missing integer. Can you do it in Big-O(n) time? [5.8 p. 92]
• Imagine a robot sitting on the upper left corner of an X by Y grid. The robot can only move in two directions: right, and down. How many possible paths are there for the robot to go from [0,0] to [X,Y]?
  FOLLOW UP: Imagine certain spots are off limits, such that the robot cannot step on them. Design an algorithm to find a path for the robot from the top left to the bottom right. [9.2 p.109]
• Given a boolean expression consisting of the symbols 0, 1, &, |, and ^, and a desired boolean result result, implement a function to count the number of ways of parenthesizing the expression such that it evaluates to result. [9.11 p.110]
  EXAMPLE:
  Expresson: 1^0|0|1
  Desired result: false or (0)
  Output: 2 ways: 1^((0|0)|1) and 1^(0|(0|1))
• Given an input file with four billion non-negative integers, provide an algorithm to generate an integer which is not contained in the file. Assume you have 1 GB of memory available for this task
  FOLLOW UP: What if you have only 10 MB of memory? Assume that all the values are distinct and we now have no more than one billion non-negative integers. [10.3 p. 115]
• In the famous dining philosophers problem, a bunch of philosophers are sitting around a circular table with one chopstick between each of them. A philosopher needs both chopsticks to eat, and always picks up the left chopstick before the right one. A deadlock could potentially occur if all the philosophers reached for the left chopstick at the same time. Using threads and locks, implement a simulation of the dining philosophers problem that prevents deadlocks. [16.3 p. 160]
• Write a method to count the number of 2's that appear in all the number between 0 and n [inclusive]. [18.4 p.167]
  EXAMPLE:
  Input: 25
  Output: 9 [2, 12, 20, 21, 22, 23, 24, and 25] Note that 22 counts for two 2's.
• You have a large text file containing words. Given any two words, find the shortest distance [in terms of the number of words] between them in the file. If the operation will be repeated many times for the same file [but different pairs of words], can you optimize your solution? [18.5 p.167]
• Given a string S and an array of smaller string T, design a method to search S for each small string in T. [18.8 p.168]
• Given an NxN matrix of positive and negative integers, write code to find the submatrix with the largest possible sum. [18.12 p.168]

Coding Session: Free Play!!