String Questions in Interviews

String questions are often some of the more straightforward interview questions out there. After all, which computer science student hasn’t been subject to endless assignments requiring string manipulation? (Remember all those reverseString recursion problem sets?)

Still, string questions can be tricky, and designing and implementing an efficient approach, while being scrutinized, is no easy feat. Here is a guide, compiled from various books, articles and friends, to help you defeat the dreaded string interview question.

A Brief Summary

String Merging

First off, remember that Strings are in fact, at a lower abstraction level, arrays of Characters. Java and C programmers will be acutely aware of this. Higher-level languages, such as Python or Javascript, tend to hide such details. No matter your language of choice, keep the structure of Strings in mind when tackling String problems.

This means that String and Array questions share similar approaches. For example, sorting according to a certain key, or finding the difference between the biggest and smallest element in a list. String questions are instead mostly limited to permutations of the existing data within the Character array. There are 5 fairly common types of String questions:

  1. Generate all permutations of a given String
  2. Substrings of a given String
  3. Reversing a given String
  4. Substitution/Replacing specific letters
  5. String Compression

Remember the StringBuffer

Before we begin analyzing each problem, there is one String attribute often overlooked: Strings are immutable.

A common practice is to create a String accum variable and update it with every iteration of the loop. For example, this function that reverses a String.

public static String reverseWrong(String x) {
  // convert x into an array
  char[] string = x.toCharArray();
  // create variable to hold answer
  String ans = "";
  // iterate from the back of the array, each time adding a character to ans
  for (int i = string.length - 1; i >= 0; i--) {
    ans += string[i];
  }
  // return as a String
  return ans;
}

Figure 1: Java sample function

Strings’ immutability means that the String variable `ans` is actually destroyed and re-created every time a new character is added to it. Each time a new String is created for `ans`, Java allocates a new array of size `x + 1`, where `x` is the number of characters in the existing String. Java then copies the existing `x` character over and inserts the new character into the last slot. If `n` is the size of the given String, the loop means this happens `n` times. Thus, the total time spent computing ans is `O(1 + 2 + 3 + … + n)`. By summation, this reduces to `n(n+1)/2` or `O(n^2)`. No matter how efficient the algorithm, the function has at best quadratic runtime – terrible.

 

The solution is to use a `StringBuffer`. This is an array pre-allocated with spare memory, with additional characters inserting into the array itself. Dynamic arrays can also be used, if sizes are not known beforehand. The final String is only created once all String manipulation operations have concluded. With only one pass through the characters, total time drops to `O(n)` – linear.

Java has kindly provided the helpful `StringBuffer` class for this. Unlike `Strings`, the `StringBuffer` class is mutable, eliminating our quadratic runtime problem. Figure 2 demonstrates the optimal way of String manipulation in Java, note the use of `StringBuffer`.

public static String reverseCorrect(String x) {
  // convert x into an arrayj
  char[] string = x.toCharArray();
  // create the StringBuffer object
  StringBuffer buffer = new StringBuffer();
// iterate from the back of the array, each time adding a character to buffer
  for(int i = string.length - 1; i >= 0; i--) {
    buffer.append(string[i]);
  }
  return buffer.toString();
}

Figure 2: Java StringBuffer example

Since Python does not possess a dedicated StringBuffer data structure. Python programmers often use a list. New characters are added to the list, and the final String is created by joining all elements in the list

As long as you follow the StringBuffer’s basic concept, it is not necessary to strictly adhere to these implementations during your interview. If the precise syntax is fuzzy, feel free to create your own.

Note that not all interviewers will fuss over this, and that this does not apply to all questions. But it never hurts to know.

String Question Type 1 – Generate all permutations of a given String

This is one of the most common interview questions given, and will be good to know by heart. Because your first instinct is to look for an elegant algorithm (which is a good habit), the question may initially seem daunting. The trick here is to realize that generating all permutations of a given String of size n always results in a O(n!) time, both iteratively and recursively.

Consider the string “abc”. The first character ‘a’ can be placed in 3 slots – first, second and third. ‘b’ can be placed in only 2 slots, since one slot is already taken by ‘a’. ‘c’ has no choice but to go into the remaining slot. Hence the total permutations are 3 x 2 x 1 = 6 = 3!. Correspondingly, there are 6 permutations: “abc”, “acb”, “bac”, “bca”, “cab” and “cba”.

We implement a recursive solution as it is more elegant and thus easier to understand (Figure 4).

public static void permutate(String str) {
  permutation("", str);
}
  
private static void permutation(String ans, String remain) {
  int n = remain.length();
  // ans serves as an accumulator variable
  // base case: we print out ans since there are no more letters to be added
  if (n == 0) {
    System.out.println(ans);
  }
  // recursive case
  else {
    for (int i = 0; i < n; i++) {
      // we call permutation, each time combining prefix with the individual letters in str
      // we also remove these letters from str
      permutation(ans + remain.charAt(i), remain.substring(0,i) + remain.substring(i+1, n));
    }
  }
}

Figure 4. Java Recursive String Permutation function

 

Note that since the runtime is factorial, StringBuffer is redundant here.

I do not recommend testing this code with an input size longer than 15 characters, not because it isn’t efficient, but because there are simply too many possibilities. Feel free to also implement an iterative version!

Question Type 2 – Substrings of a given String

There are several questions that fall into this category.

First, check if a two strings are substrings of each other.

This is a relatively simple one. Refrain from reinventing the wheel by utilizing Java’s indexOf or contains method for Strings and Python’s “in” keyword. Hey Presto! Solved in three lines!

However, this is often an easy lead up to String rotations and the next question will likely be: “Now check if one string is a rotation of another.

For example, “forinterviewscoding”, “interviewscodingfor” and “dingforinterviewsco” are all valid rotations of the string “codingforinterviews”, while “codngiforinterviews” is not.

The key to this is observing that the original string is a substring of the rotated string added to itself.

Consider, the original string “codingforinterviews” and the rotated string “dingforinterviewsco”.

Let, x = “codingforinterviews” and y = “dingforinterviews”

Further, let “codingforinterviews” be broken up into 2 substrings, a and b.

Hence x = ab.

Let a = “co” and b = “dingforinterviews”.

Thus y =“dingforinterviewsco” = ba,

and y + y = baba = “dingforinterviewscodingforinterviewsco”.

Therefore, if y is a substring of x, x will always be a substring of (y + y)

Similarly, the code for this is straightforward (Figure 5).

// it is better practice to separate functions
public static boolean isSubstring (String a, String b) {
  // we first check the length of the strings 
  if (a.length() < b.length()) {
    return b.contains(a);
  }
  // feel free to use indexOf
  return a.contains(b);
}
  
// assuming that a is the rotated string
public static boolean isRotation (String a, String b) {
  if (a.length() != b.length()) {
    return false;
  }
  return isSubstring(a+a,b);
}
  
// the entire function can be optimized to this
public static boolean isRotation2 (String a, String b) {
  return (a.length() == b.length() && isSubstring(a+a,b));
}

Figure 5. Java String Rotation function

Comparing the lengths of the two strings takes O(n), where n is the length of the longer string, while Java’s contains method operates in O(n), bringing the function’s runtime to a very efficient O(n), with no additional space needed.

Lastly, we tackle the problem:

String Question Type 3 – Determine if one string is a permutation of another

The brute-force method, and simplest, is to compute and store all possible string permutations in an array, and iterate through, checking. However, as discussed above, this results in an terrific O(n!) time – unacceptable.

Instead, the optimal approach here is to realize that considering specific ordering adds an unnecessary layer of complexity since all permutations of a given string have the same number of characters as the original string. We can solve this problem by counting characters (Figure 5).

public static boolean isPermutation (String a, String b) {
  // first check if both strings are the same length
  if (a.length() != b.length()) {
    return false;
  }
  // change a to char array to be iterated through
  char[] astr = a.toCharArray();
  // initialize an array as a counter
  int[] count = new int[128];
  // then we count a's characters
  for (char character : astr) {
    count[character]++;
  }
  // match a's count with b
  char[] bstr = b.toCharArray();
  for (char character : bstr) {
    if(--count[character] < 0) {
      return false;
    }
  }
  return true;
}

Figure 5. Java String Permutation function

Comparing length and counting operations both take O(n), since both are completed in one pass. Hence overall time is a nifty O(n), with O(n) extra space utilized for the arrays.

Another acceptable approach is to sort both strings, comparing each entry of the sorted strings. Since all permutations have the same number of characters, the sorted strings must be identical. Sorting, however, is dependent on input sequence, and adds another layer of complexity to the code. Counting characters is simple and direct.

String Question Type 4 – Reversing Strings

String reversal questions are also common. Similar to substrings, such questions often consist of 2 parts, reversing a given string, and then reversing words within a given sentence.

Let’s start with reversing a given string.

This is as simple as string questions can get. Such questions are commonly known as “filibusters”, and are intended to weed out the 95% of candidates who strangely, for some reason, are unable to write viable code. There are no hidden tricks or fancy algorithms, with the exception of StringBuffer. Figure 2 provides the iterative version with StringBuffer integrated.

Because we do this in one pass, the time taken is O(n) with additional O(n) space for the array.

Now, using the above function, reverse the words in a string. For example, “coding for interviews” is reversed to “interviews for coding”.

The trick here is to notice that reversing the entire sentence immediately reverses the sequence of words, though the words themselves are jumbled. “coding for interviews” turns into “sweivretni rof gnidoc”. We then reverse each individual word back to its correct orientation, generating “interviews for coding” (Figure 6).

public static String reverseSentence (String x) {
  // first reverse the string x using the previous function
  x = reverseCorrect(x);
  // split x, effectively extracting the individual words
  String[] words = x.split(" ");
  // create a StringBuffer
  StringBuffer buffer = new StringBuffer();
  // reverse and add the entries in words to buffer
  for (int i = 0; i < words.length; i++) {
    System.out.println(words[i]);
    buffer.append(reverseCorrect(words[i]) + " ");
  }
  return buffer.toString();
}

Figure 6. Java Reverse Sentence function

The reversal function is a constant O(n) since it only requires one pass. Splitting and appending both take O(n), as they too complete their tasks in one pass. Hence the overall function completes in O(n) time, with O(n) additional space for word extraction. This is also a fantastic example of StringBuffer’s practicality. Without a buffer, the overall time would have at least been an absymal O(n^2) no matter the algorithm.

Note that there are shorter ways to solve the question if the interviewer goes straight to reversing words in a sentence. As Figure 7 demonstrates, Java has excellent inbuilt libraries for this task.

public static String reverseSentenceQuick (String x) {
  // use the split method
  String[] words = x.split(" ");
  // create a StringBuffer	
  StringBuffer buffer = new StringBuffer();
  // we append starting from the end of words
  for(int i = words.length - 1; i >= 0 ; i--)
  {
     buffer.append(words[i]);
  }
  return buffer.toString();
}

Figure 7: Java Reverse Sentence Library Implementation function

Because some interviewers frown on using certain built-in methods, it is beneficial to know both approaches and confirm with your interviewer a certain appproach is OK.

String Question Type 5 – Replacements and Deletions

Common and easy to implement, String replacement/deletion are also common filibuster questions, especially for the initial phone screens before the actual on-site interviews. Getting a good grasp of them doesn’t necessary set you apart, but primes the interviewer to expect more from you, which is always good.

First, we tackle: Write a method to replace all whitespaces in a string with #20.

I am sure you recognise a pattern by now: our algorithm should finish its task within one pass of the string for optimal efficiency. This means that iterating through the String and replacing whitespaces with #20, though straightforward, is perhaps the best and simplest approach. As always, the devil is in the details.

 

Most programmers get caught up in their excitement and tap out the following function (Figure 8).

public static String replaceWrong (String x) {
  char[] word = x.toCharArray();
  // iterate through x, replacing whitespace
  for (int i = 0; i < x.length(); i++) {
    if (word[i] == ' ') {
       word[i] = 'a'; // <---- issue here
    }
  }
  return new String(word);
}

Figure 8. Buggy Java String Replacement function

This function will not work as it is does not account for the additional whitespace the inserted characters will take up. Forestall any embarrassment by remember to first count the whitespaces, ensuring your array contains enough spaces. It is also wise to demonstrate initiative to the interviewer by removing any hard-coded values. The resultant function should look something like this.

public static String replaceCorr (String x, String replace) {
  // count the number of whitespace to be replaced
  int count = 0;
  for (int i = 0; i < x.length(); i++) {
    if (x.charAt(i) == ' ') {
      count++;
    }
  }
  // create an array, including the whitespace
  char[] word = new char[x.length() + count * replace.length() - 1];
  int index = 0;
  //iterate through x, replacing whitespace
  for (int i = 0; i < x.length(); i++) {
    if (x.charAt(i) == ' ') {
      for (int j = 0; j < replace.length(); j++) {
        word[index++] = replace.charAt(j);
      }
    }
    else {
      word[index++] = x.charAt(i);
    }
  }
  return new String(word);
}

Figure 9. Correct Java String Replace function

The time taken is O(m), where m is the length of the original string including the additional characters. As this is achieved in one pass, it is optimal.

There is however, further possible optimization. Remember StringBuffer? This is where your knowledge of such a function will make you shine. Proper usage of StringBuffer here further shortens the code (Figure 10).

public static String replaceCorrBuff (String x, String replace) {
  // create a StringBuffer
  StringBuffer buffer = new StringBuffer();
  // iterate through x, replacing whitespace
  for (int i = 0; i < x.length(); i++) {
    if (x.charAt(i) == ' ') {
      buffer.append(replace);
    }
    else {
      buffer.append(x.charAt(i));
    }
  }
  return buffer.toString();
}

Figure 10. Java String Replace function using StringBuffer

Though improvement in performance is marginal, and this is a filibuster question, it is always good to demonstrate an ability to improve and optimize.

Here the #20 is a mere placeholder, and your interviewer might well use other characters, or throw in multiple replacements. This approach should apply, nonetheless.

Not surprising, deletion is a much easier, since there are no additional spaces to account for. As with replacements, and String questions in general, we go through the list, deleting the specified characters. Use StringBuffer whenever appropriate.

String Question Type 6 – String Compression

Though less frequent, String Compression questions do pop up a significant portion of the time. Though phrased differently, the questions are often variations of string compression through character counts. For example, compressing the string “aaabbbcccc” to “a3b3c4”.

Here, the naive approach – iterating through the string, counting characters as they appear – is somewhat correct. As above, the crux lies in using a StringBuffer. Without doing so, the runtime will be O(n + q^2), where n is the length of the original string and q is the number of character sequences. With a StringBuffer, runtime is now O(n + q), since string concatenation is limited to only the character sequences, and no longer quadratic (Figure 1).

public static String compressString(String x) {
  // create a buffer
  StringBuffer buffer = new StringBuffer();
  // to hold the current alphabet
  char current = x.charAt(0);
  // to hold the current count
  int count = 1;
  // iterate through the array, counting
  for (int i = 1; i < x.length(); i++) {
  // update buffer if the letter has changed
    if (current != x.charAt(i)) {
      buffer.append(current);
      buffer.append(count);
      current = x.charAt(i);
      count = 1;
      }
    else {
      // increment the counter
      count++;
    }
  }
  // remember to add the last character
  buffer.append(current);
  buffer.append(count);
  // return a string
  return buffer.toString();
}

Figure 11. String Question Solution: Java String Compression with StringBuffer

There is however, one logical error. If we were doing this by hand, we would only compress the string if its compressed version is shorter than the original. Else, we return the original string. Figure 12 shows the final solution.

public static int countCompress(String x) {
  // total size of string
  int size = 0;
  // count for each char
  int count = 1;
  char current = x.charAt(0);
  // iterate through, counting
  for (int i = 1; i < x.length(); i++) {
    // update if current character is different
    if (current != x.charAt(i)) {
      current = x.charAt(i);
      // we add the length of the char and its count
      size += 1 + String.valueOf(count).length();
      count = 1;
    }
    // increment count if similar
    else {
      count++;
    }
  }
  // we update size to include the last char
  size += 1 + String.valueOf(count).length();
  return size;
}

public static String compressString(String x) {
  // first use countCompress
  int length = countCompress(x);
  if (length > x.length()) {
    return x;
  }
  // create a buffer
  StringBuffer buffer = new StringBuffer();
  // to hold the current alphabet
  char current = x.charAt(0);
  // to hold the current count
  int count = 1;
  // iterate through the array, counting
  for (int i = 1; i < x.length(); i++) {
  // update buffer if the letter has changed
    if (current != x.charAt(i)) {
      buffer.append(current);
      buffer.append(count);
      current = x.charAt(i);
      count = 1;
    } else {
      // increment the counter
      count++;
    }
  }
  // remember to add the last character
  buffer.append(current);
  buffer.append(count);
  return buffer.toString();
}

Figure 12. Full Java String Question solution for String Compression.

Though somewhat long, if you made it this far and your interviewer is able to push you to this point during the session, bonus points for being comprehensive and robust!

Onward to String Question Mastery!

String questions are not necessarily easy, and not necessarily difficult — they come in all shapes and sizes. Interviews can be nasty, stressful and nerve-wrecking affairs, and you’ll want to go in there as confident as you can be. Spread your preparation out and make sure to tackle the most important topics. Don’t hyper-focus on BSTs, for example, but then completely gloss over string manipulation. Yes, this can happen!

String questions you get will typically be variants of those listed above. Be flexible. Perhaps the input you need to compress is jumbled? In that case, sort before doing anything. Or maybe what needs replacing is not whitespace but an entire substring?

In any case, these approaches should still apply. Remember, Strings often require iteration, and the key is to limit this to just one pass. Oh yes and StringBuffer is, almost always, a must.

Good luck!

Posted in Preparation, Strings

Greg Jordan on the Google Interview

Greg Jordan, one of my three (!) older brothers, recently had his first ever programming interview—at Google!

In this take-no-prisoners, violate-no-NDAs podcast interview, Greg talks about:

This is the episode I wish I had back when I did my first interviews.

Thanks Greg!

EDIT: Reader Hao asked a great question about some resources for Javascript “gotchas”. Two of my favorites are JS scope, JS pass-by-*, and Hao suggests JS Gotchas

Posted in Interview Experiences, Podcast

Choosing a Programming Language for Interviews

Most popular programming languages of 2014

Last week at the MIT January term course Hacking a Technical Interview, after a class period finished a student asked me the question:

I know many different programming languages. How do I choose which one to use during my interview?

Why choose just one?

Don’t get me wrong—I advocate learning and writing code in many programming languages. But when it comes time for programming interview preparation, I feel it’s important to choose one language to focus your prep on and get to know it very well.

While many interviewers don’t mind you writing pseudocode during the early planning step of answering a question, others I’ve come across really want you to show you can write compilable code without an IDE. Not only that, but that you appear very comfortable writing real code.

How to pick

Now back to our polyglot student—how might they approach choosing just one?

Choose a language you know well

If you’re fresh out of school and throughout your college career you were instructed in Java, C or C++, stick with what you know.

Imagine this: what if I asked you right now, at your computer, to please, using a programming language (not your bash-fu or vimscript):

  1. Read in a file full of numbers, one number on each line
  2. Represent those numbers as integers in your program
  3. Replace each number with that number times its line number
  4. Write the file out elsewhere
  5. And complete the task right now at your computer as fast as possible, you’re being timed

Think—what language would you immediately reach for? Do you start your experimentation with ipython, or irb? Do you pop open Eclipse and write some Java? Or create a new .cpp file?

Make sure it’s widely readable

Ideally you’re most comfortable with a language that your interviewer has used before, but at the very least it should be readable by a wide audience.

Some solid, standard choices for interviewing, then, are: Java, C / C++ / C#, Python, Javascript, and maybe Ruby. PHP, AS3, Lua, Haskell, Go, LISP/Scheme and the ilk are potentially appropriate when the company uses them.

Consider this great visualization of the most popular coding languages of 2013 from the interactive practice problem website CodeEval:

Most popular programming languages of 2014

Most popular programming languages of 2014

If you’re using a non-standard feature of your language that might not show up in others (dense Python list comprehensions, Ruby functional programming techniques, higher-order functions)—it’s a good idea to be cognizant of the interviewer’s comfort with the language and gently offer explanations of concepts they might not have exposure to yet.

Bias towards the one they use

Some advice from the book Programming Interviews Exposed—all things equal, bias slightly towards the language your target companies use if it’s one of the ones you’re most comfortable with.

For example, if the company you’re applying to is primarily a Ruby shop and you’re fairly confident with your Ruby, go with that. If you’re applying to a low-level hardware manufacturer working mostly in C and Assembly, go with that. Game company that uses ActionScript, and you’re writing a game in it now? Go with that.

Here are some oft-used languages at various companies as reported in Cracking the Coding Interview and on Quora:

  1. Facebook: PHP, C++, Python, Java, Perl. High regard for dynamic/scripting languages. (source)
  2. Google: officially C/C++, Java, Python, Javascript, Go (source)
  3. Amazon: Java, Javascript, Ruby, Python, Perl (source)
  4. Microsoft: C++, C#, Java, Python (source 1, 2)

Once you’ve picked your language

Excellent, so you’ve chosen a language to focus your preparation on and to use for your interviews. Now what do you do?

Practice in your language

When you are doing practice problems, try to always write with the language you’ll be using in your interview.

The couple of weeks leading up to your interview, when you’re doing personal projects and hacking on things for fun, try to use that language as well.

Know thy common operations

Make sure you have at least the following operations down pat:

  1. Initializing and using hash-backed maps (dictionaries) and sets
  2. Performing queue and stack operations (whether using an array, like with Ruby’s pop/shift, or an explicit standard library implementation like Java’s Stack and Linked List-backed Queue classes)
  3. Defining classes with constructors and attributes, static and instance methods, and defining a subclass and interface
  4. Throwing exceptions for (1) invalid input and (2) custom messages
  5. Iterating through arrays and dictionaries (both key and values)—including iterating while maintaining an index (Ruby’s each_with_index, Python’s enumerate)
  6. Casting between strings and integers
  7. Strings: get character at index, get range, concatenate
  8. Initializing 2d arrays
  9. Arithmetic: modulus (remainder), division (if the first operand is an integer, will it round the result to an integer?), rounding (ceiling and floor)
  10. (Bonus) Switch statements
  11. (Bonus) Built-in language sorting. Quickly defining a comparator to sort an array.
  12. (More advanced candidates) The 5 standard bit manipulation operations (L/R shifts, not, or, and, xor)

Know the best practices

Especially if the company you’re applying to has experience with your language, it can be helpful to brush up on the best practices for your language. Sometimes you’ll get trivia questions, or be asked about some language-specific patterns.

If you’re going with Java, for example, and applying to Amazon, where Java is heavily used, consider reading through some of the best practices material.

There are some great books like Effective JavaSecrets of the Javascript NinjaEffective C++, and The Ruby Programming Language  which cover language-specific best coding practices.

Have some opinions about it

Some classic “technical chit-chat” interview questions are:

  • What do you like about language X?
  • What don’t you like about it?
  • How does it compare to (another language you profess to know)? Similarities/differences?

Formulating some smart opinions about your language is generally a good idea.

Where does your language fall among the different programming language paradigms? A book like Seven Languages in Seven Weeks is a good starting point if your breadth of language paradigm understanding is lacking.

Programming Language Paradigms

Programming Language Paradigms Table from Wikipedia

Now Prepare!

Now you’ve got your language and some steps to take to know it better for your interviews. Go forth and prosper!

Of course, as noted earlier, it’s not necessary to always stick to one language when not preparing for interviews—learning new languages is fun and can lead you to understand your go-to language better. But the week or few days before your interview, be sure to drill deep into one.

What is Coding for Interviews?

Each week, Coding for Interviews members receive two things:

  1. A programming interview question
  2. A distilled computer science topic review (with silly gifs)

You send in your answer and the next week we review solutions.

We practice a little bit each week. The idea is, the next time our group members are looking for jobs, we will be prepared.

New group members are always welcome!

One email each week. No spam. Easy unsubscribe.

Email
Posted in Preparation

Say you don’t know

A Coding for Interviews weekly practice problem group member mentioned after making it through a long round of programming interviews at different companies (emphasis added to quotes throughout post):

What I always have learned to do is just be honest and explain everything you are doing. Start with a solution that works, explain what you are doing, then refine the solution to be more efficient, if they would like. Also, if I didn’t know something, I would say that I don’t. Then try to formulate an educated guess, thinking aloud.

Indeed, I’ve seen this sentiment echoed among many smart, creative individuals. One of the best habits you can build in life and interviews is admitting when you don’t know something.

Derek Sivers of CDBaby in his essay “Smart people don’t think others are stupid“:

Being stupid means avoiding thinking by jumping to conclusions. Jumping to a conclusion is like quitting a game: you lose by default. That’s why saying “I don’t know” is usually smart, because it’s refusing to jump to a conclusion.

Leah Hager Cohen wrote an entire book on the subect—“I Don’t Know: In Praise of Admitting Ignorance (Except When You Shouldn’t)”. In her book and NPR interview on the subject,

Cohen notes:

I think those words [“I don’t know”] can be so incredibly liberating.

They can just make your shoulders drop with relief. Once you finally own up to what you don’t know, then you can begin to have honest interactions with the people around you.

Fear of effort and losing face

Sometimes I have trouble saying “I don’t know” and asking for clarification, or will often cut short an opportunity to learn something by saying “oh, okay, sure I get it”. Saying “I don’t know” feels scary. It’s uncomfortable. It means feeling an obligation to engage with the speaker and think harder, maybe learn something from them. And perhaps more subconsciously, it means setting the ego up to take a quick hit.

But that’s a local minima. You end up seeming much smarter when you learn more and show you have an understanding of your own knowledge.

In the words if Richard Fenyman’s wife, and title of his book:

What do you care what other people think?



Looking smarter

Indeed, admitting you don’t know something puts you in a better position to make yourself look good. Mark Gumz, president and CEO of the Olympus Corporation notes:

If you don’t know the answer, say you don’t know the answer. People will accept that you don’t know the answer.

But what they can’t accept is if you tell them something that’s wrong, because they’re going to act on that. And then if you have to come back later with a different answer, you’ll lose credibility”

Sussing out interesting things “eh… maybe it is”

In “I don’t know”, Cohen connects the fear of saying “I don’t know” with the 1982 Air Florida 90 crash in Washington DC.

The co-pilot says “that doesn’t look right, does it? That’s not right…”, and the pilot brushes it off as “yeah, that’s fine”. The co-pilot says again “I don’t think that’s right…”, then:

Ehhh… maybe it is.

Saying “ehh… maybe it is” stops a previously interesting line of inquiry in your head in its tracks.

Saying “I don’t know” provides fuel to the fire.

Give yourself the chance to learn more



Something I’ve noticed from MIT students and graduates (perhaps an ingredient of their culture’s secret sauce?) is a willingness to say “I don’t know” and go deep down lines of inquiry without cutting them off. In recorded OCW lectures, you might notice that students tend to ask good questions. Not, “I was sleeping and missed this part of the lecture” questions, but “wait… this doesn’t make sense yet” questions—even questions that might sound basic.

MIT professor Rosalind Picard, founder of MIT’s Affective Computing research group wrote this wonderful essay on being curious. Professor Picard notes:

Worrying what other people think is a huge waste of time. What’s keeping you from learning and trying something new? It’s so easy to type something on the web and begin a search of the literature. Or admit you don’t know something somebody said, and ask them how to learn more about it. Scared of looking foolish? I’d rather look foolish and get to learn, than waste the moment looking like I know something instead of learning it. Usually it’s a simple fear that’s keeping you from a lot of fun and discovery.

Jessica Banks, former MIT graduate student and founder of RockPaperRobot notes:

My grad school experience at MIT was a rebirth of wonder. I came up with the idea for my company there.

And when asked what advice she would give her 23-year-old self,

It’s easier to admit you don’t know something than to pretend you do.

Another MIT grad, Kevin Rustagi, MIT ’11 and co-founder of the Ministry of Supply notes in a Tech article on startups at MIT:

It’s important not to let pride get in the way — be willing to admit you don’t know everything, and that you can’t do it alone. It’s not an ego thing to do it on your own, and it’s not bad to network and connect with other people.

And Jake Beal, yet another MIT grad, notes in a rant on winning AI:

Admit you don’t know things […] Not knowing something is a good start for a project.

Professing to not know something is a great launchpad for further learning.

Follow up with positive enthusiasm

Saying you don’t know and following up with “but let’s work through an educated guess” is a great way to show you are honest and self-aware—and that you don’t give up when you’re faced with a challenge.

If you do, or might know…

In the interview context, especially for more open-ended questions like “why would you like to work here at UltraMegaCorp Technologies?”, an “I don’t know” can sound like a snarky retort, easily mis-read as a big red flag for an interviewer.

You can be honest about wanting a second to think. Tactfully give yourself a few seconds to formulate a response. If appropriate, talk a bit through your thought process.

Give it a shot

Here’s an exercise—next time you’re in a conversation and get a bit stuck, ask a followup question and try to achieve clarity. Catch yourself about to say “Ehhh… maybe it is”, and follow the thread instead.

What do you think you’ll learn next? Feel free to share a comment here or reach out to me at brian@codingforinterviews.com, I’d love to hear it.

What is Coding for Interviews?

Each week, Coding for Interviews members receive two things:

  1. A programming interview question
  2. A distilled computer science topic review

You send in your answer and the next week we review solutions.

We practice a little bit each week. The idea is, the next time our group members are looking for jobs, we will be prepared.

New group members are always welcome!

One email each week. No spam. Easy unsubscribe.

Email
Posted in Preparation

Read your Damn Standard Libraries

WCowDoW

A Coding for Interviews weekly practice problem group member mentioned during our Skype call that reading through the Java collections library was the most valuable step he took while preparing for his programming interviews. In addition to getting a better understanding the standard data structures, hearing a candidate say “well the Java collections library uses this strategy…” is a strong positive signal.

Reading the rubygems source

Indeed, other HNers echoed the sentiment:

Wael Khobalatte writes (link added),

I usually have a fun time going from method to method just exploring any of the implementations in that library. Josh Bloch (One of the writers of the library I think) uses a lot of examples from the Java collections in his book “Effective Java“, which I also recommend to everyone.

And dev_jim provides a great suggestion,

It helped me when I was a bit rusty with data structures and was looking for a new job recently. And if you can try and re-implement the data structures in a different way. For example, the JDK HashMap uses chaining so try and build an open addressing one. Not only does it teach you about data structures themselves but it gets you practicing coding very quickly for these toy coding problems that get thrown at you during interviews.

Reading the standard libraries of your favorite programming languages is really worth it. Give it a shot. Here’s why.

Learn the best practices and idioms

Reading standard libraries can not only show you what is available, it often teaches you how to write Good Code™ in your language as well.

  • Do you include newlines after blocks?
  • How are variables, classes and methods normally named?
  • What state is kept and why?
  • How and when do enums, structs and plain old classes get used?

Know your language better

As a Ruby programmer, reading the standard libraries of Ruby and Ruby on Rails has been especially enlightening.

Writing Rails for the first time, it feels like you are writing pseudo-code.

Helpful::Application.routes.draw do
  use_doorkeeper do
    controllers :applications => 'oauth/applications'
  end

  if Rails.env.development?
    require 'sidekiq/web'
    mount Sidekiq::Web, at: "/sidekiq"
  end

  root to: 'pages#home'
end
  • Where is this function root defined?
  • What makes the use_doorkeeper code’s call to controller different than another?
  • From another example: why and how does User.find_by_favorite_food('pizza') have the variable name food embedded inside of the method name?

Beginners will make mistakes that seem bizarre for people who have programmed before—calling methods with the names of methods or classes, declaring symbols instead of making function calls, forgetting to pass a block to something that requires it.

Once you begin diving in to the internals of what makes Rails (and Ruby itself) tick, it becomes clear where these top-level-seeming functions are going and how methods can apparate out of thin air.

For Rails specifically:

Learn what’s there

Reading through the libraries (and even just reading through the full API docs) will expose you to a number of utility functions and data structure parameters you might not have known existed. Did you know you could specify the load factor for a Java hashtable?

Clear your intentional blindspots

A lot of times standard libraries contain the types of data structures and algorithms you seldom encounter when you are programming at the application level. Often times, then, when you step into an interview and they ask you how you might implement a hash table, you panic. Whenever you wanted to use a hash table, you would reach for HashMap<K,V>.

Reading the low level constructs of your language will help you prepare for your interviews and learn how some of the more insteresting things in computer science are implemented in the real, road-tested systems.

How do you get started?

Give it a shot in your language of choice!

  • Java: GrepCode is a nice viewer for the standard Java libraries
  • Python: pure python libraries are available in /Lib (web viewer), and C modules are in /Modules (web viewer). The Django framework is also a good project to read (github), and there’s a great video about the Python dict implementation.
  • Ruby: Qwandry is a neat tool for popping open Ruby and Ruby on Rails libraries with just one shell command. You can also read the Ruby source on GitHub. /lib (on GitHub) is a good place to start.
  • C++: libstdc++ STL implementation has a number of interesting libraries (web viewer, click on “Go to the source code of this file” to view sources)
  • PHP: interpreter code (on GitHub)
  • C#: see the Mono implementation (on GitHub) or install ILSpy to read sources of standard API.

What is Coding for Interviews?

Each week, Coding for Interviews members receive two things:

  1. A programming interview question
  2. A distilled computer science topic review

You send in your answer and the next week we review solutions.

We practice a little bit each week. The idea is, the next time our group members are looking for jobs, we will be prepared.

New group members are always welcome!

One email each week. No spam. Easy unsubscribe.

Email
Posted in Preparation

Learning to Code Online to Get a Job

Guest post from Pete Huang, student at Northeastern University making the switch to programming as a career

It was time.

For years, I played around in the WordPress editor scanning lines and lines of CSS, stripping down themes to their bare minimum and hacking together pieces of copied and pasted PHP to support my scrappy, shady “make money online” schemes.

But I moved on, and soon, I found myself looking to do bigger things. I’ve wanted to program awesome things for a while now. It’s college, it’s four years to learn whatever I want, it’s a series of opportunities to do new things. Indeed, it was time. I opened TryRuby and got to work.

TryRuby

This was April of 2013. I had been fed up with not knowing, while people were out there building. I thought I’d be able to be the “non-technical founder”. I soon realized that not knowing is just as powerful as knowing, just it’s in the entirely wrong direction. I shot my brother, a CS major, a text asking him where I should start. He said “Look up TryRuby and the Hartl tutorial. Good luck.”

Today, seven months later, I’m shooting my resume out to as many companies as I can.

Learning to program has been a highly self-driven initiative. School was too slow for my timeline, because back in April, I told myself that I’d be a decent candidate for internships come Fall 2013. I had to learn everything I needed to get there in six months time by myself. I noted that I needed to emulate a computer science major from beginning to end, except I had much less time. It’s an essential paradigm shift going from “I’m just going to learn a bit” to “I’m behind and I need to catch up”, and it puts you in a position to cut the fat and optimize your learning.

It hasn’t been a totally smooth ride, though. I struggled with understanding the deeper meaning of everything. That sounds a bit vague, but most beginners will know that doing TryRuby or Codecademy teaches you to be good at memorizing syntax and following instructions/hints. Once you finish, you know how to write an if/else statement, but you don’t really know what to do with it. Placing everything in context and finding out what it can be used for is the toughest part of learning to program because it’s not something other people can teach you. The understanding seems to be a result of your own exploration.

After making a few things, I felt like it was time to nail down what was necessary to succeed in a technical interview. I bought a textbook (Algorithms, 4th edition by Sedgewick), studied the Big-O Cheat Sheet and completed the Coding for Interviews practice every week. A lot of it was new stuff, and the same frustrations that came with learning to program also came with learning new data structures. I’m still in this process, and it continues to stump me once in a while, but sticking with it has definitely helped, especially as you see more problems that end up being very similar because of the underlying structure.

Coding for Interviews

Coding for Interviews: the weekly code practice email

This coming summer, I hope to see myself in an internship that will help me understand more about computer science and move into less web-heavy areas. Ruby on Rails barely skims the surface of computer science as a field, so my next steps are definitely to see what else is out there. It’s a fantastically deep subject.

Until then (and probably for years after), I’ll be doing a few things. First, I’ll be building more and more complex things. Twitter clones can only get you so far. I want to move away from Rails and do things like wrapping awesome APIs and writing HTTP servers. Second, I’ll be studying more algorithms and practicing more coding interview questions. There is a wealth of resources for this, from Coding to Interviews to Cracking the Coding Interview to CareerCup. Finally, I’ll be networking my best to see what awesome things people are doing out there. After all, it’s not just about you. If anything, the tech community is all about giving back and teaching others.

Hopefully, by next year, doing these things will position me to work for an awesome company. The Big 4 come to mind, but companies like Palantir and Panorama Education are also helping to solve very important problems in the world.

Posted in Learning Experiences

My Technical Interview Experience

Guest post by Tuhin Chakraborty, Hacker in Residence at HackReactor

The almighty technical interview has struck fear in the hearts of budding engineers throughout the history of computing. Some see it as an antiquated, inefficient, even useless procedure, that simply tests a candidate’s ability to answer a very specific type of question and not much else.

Others still reject it entirely, favoring methods like “try before you buy”. But despite rising opposition, there is little debate the technical interview is still the industry’s most popular evaluation tool.

I recently had an interview at Pandora for the position of Senior Software Engineer. The interview was a classic example of a grueling technical interview. It took five hours with a different person, one after another, grilling me at the whiteboard as I tried desperately to solve the problems they threw at me while hiding the sweat puddling at my feet.

The fourth interview stood out most. The interviewer, we’ll call him Ben, was introduced as one of Pandora’s best engineers. Still reeling from the morning onslaught, I was shaking in my boat shoes.

He walked in, grinned, looked at the whiteboard — a tangled slop of circles and lines, the aftermath of a graph traversal gone horribly wrong — and then said, “They still ask this kind of stuff?” Was he joking? Making light of my ruined state?

“I can’t do any of that kind of stuff,” he assured me. “I can write code, but I could never do that.”

He then proceeded to ask me a question many orders of magnitude more difficult than what I’d just been asked. It was a question that, as he put it, had never been solved.

That night, I cried.

But alas, that is the nature of the game we software engineers must play. Rather than fight or lament it, it is better to realize this can work for us rather than against us.

Anyone can get improve their interview game, and the more the skill with which you play, the more you will win.

Hack Reactor is a software career accelerator that understands that game very well. That’s why we, the students, spend two weeks of the 12-week program — 14 hours a day, six days a week — studying algorithms and data structures.

We spend an hour of every morning — often the first waking hour of our days — for twelve weeks, practicing the kinds of problems I was asked at the whiteboard at Pandora. We do linked lists, binary trees, n-ary trees, red-black trees, prefix trees, and tree traversals: depth first, breadth first, pre-order, in-order, post-order traversals. And then we do sets, and queues, and stacks, and sorting algorithms. Quicksort, merge sort, insertion sort, even bubble sort for fun, on the days we’re feeling cute. And of course, don’t forget hash tables. Don’t ever forget hash tables!

Brian note: Barack Obama thinks Bubble Sort is the wrong way to go :)

We also do pair programming at Hack Reactor, which teaches you to speak eloquently about the code you’re writing to someone you don’t know. This is an invaluable skill for an engineer. It means when I’m at the whiteboard and I have no idea what to do next, I can vocalize my thought process and give insight into the decision trees I’m traversing in my head. It also teaches you how to be a human — a surprisingly rare trait among engineers. We have such a tightly knit community here at the school, we understand what it’s like to love the people you work with, and to work as a team to build something beautiful. Those are the intangibles that make a difference when you’re sitting in a small room trying to convince someone they should hire you.

It was the weeks of targeted practice — studying the precise things interviewers ask in their technical interviews — in combination with the more subtle qualities we, as students, learned over time — the intangibles that separate developers from software engineers — those there the things that made me a contender for a Senior Software Engineer position after only 13 weeks of writing Javascript. And although I shed tears the night after my interview, those were the things that brought me a wonderful e-mail the following morning with the subject line, “Next Steps!”

Posted in Interview Experiences