Cracking the Coding Interview

Chapter 1. Arrays and Strings

  1. Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures? [C++]
  2. Implement a function void reverse(char* str) in C or C++ which reverses a null-terminated string. [C++]
  3. Given two strings, write a method to decide if one is a permutation of the other. [C++]
  4. Write a method to replace all spaces in a string with ‘%20’. You may assume that the string has sufficient space at the end of the string to hold the additional characters, and that you are given the “true” length of the string. (Note: if implementing in Java, please use a character array so that you can perform this operation in place.)[C++]
    EXAMPLE
    Input: “Mr John Smith ”
    Output: “Mr%20John%20Smith”
  5. 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.[C++]
  6. 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?
  7. Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0.
  8. 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 s2 is a rotation of s1 using only one call to isSubstring (i.e., “waterbottle” is a rotation of “erbottlewat”).[C++]

Chapter 2. Linked Lists

  1. Write code to remove duplicates from an unsorted linked list.
    FOLLOW UP
    How would you solve this problem if a temporary buffer is not allowed?
  2. Implement an algorithm to find the nth to last element of a singly linked list.
  3. Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node.
    EXAMPLE
    Input: the node c from the linked list a->b->c->d->e
    Result: nothing is returned, but the new linked list looks like a->b->d->e
  4. Write code to partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x.
  5. You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1’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.
    EXAMPLE
    Input: (7->1->6) + (5->9->2). That is, 617 + 295.
    Output: 2->1->9. That is, 912.
    FOLLOW UP
    Suppose the digits are stored in forward order. Repeat the above problem.
    EXAMPLE
    Input: (6->1->7) + (2->9->5). That is, 617 + 295.
    Output: 9->1->2. That is, 912.
  6. Give a circular linked list, implement an algorithm which returns the node at the beginning of the loop.
    DEFINITION
    Circular linked list: A (corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list.
    EXAMPLE
    Input: A->B->C->D->E->C [the same C as earlier]
    Output: C
  7. Implement a function to check if a linked list is a palindrome.

Chapter 5. Bit Manipulation

  1. You are given two 32-bit numbers, N and M, and two bit positions, i and j. Write a method to insert M into N such that M starts at bit j and ends at bit i. You can assume that the bits j through I have enough space to fit all of M. That is, if M = 10011, you can assume that there are at least 5 bits between j and i. You would not, for example, have j = 3 and i = 2, because M could not fully fit between bit 3 and bit 2.
    EXAMPLE
    Input:    N = 10000000000, M = 10011, i = 2, j = 6
    Output: N = 10001001100
  2. Given a real number between 0 and 1 (e.g., 0.72) that is passed in as a double, print the binary representation.
    If the number cannot be represented accurately in binary with less than 32 characters, print “ERRIR.”
  3. Given a positive integer, print the next smallest and the next largest number that have the same number of 1 bits in their binary representation.
  4. Explain what the following code does: ( ( n & (n-1) ) == 0).
  5. Write a function to determine the number of bits required to convert integer A to integer B.
    EXAMPLE
    Input: 31, 14
    Output: 2
  6. Write a program to swap odd and even bits in an integer with as few instructions as possible (e.g., bit 0 and bit 1 are swapped, bit 2 and bit 3 are swapped, and so on).
  7. An array A contains 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 j-th bit of A[i],” which takes constant time.
    Write code to find the missing integer. Can you do it in O(n) time?
  8. 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, not 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).

Leave a Reply