Free DP cheat sheet, email validation solutions and the question of the week.

Quotes of the week

"Habit is overcome by habit." -Desiderius Gerhard Erasmus

Coding for Interviews 2014 Survey

Who are you (anonymously)?! For those with 30 seconds, this is a quick demographic survey with a wee present for those who submit it:

If the results are interesting, I'll send out any neat graphs I make from it!

Links of the week

Topic of the Week: Dynamic Programming

Talking with group members who successfully got jobs at Google, Amazon and Microsoft about the most important things they did to prepare, one thing that stood out was that they kept track of the problems they failed at while practicing and after interviews. Cracking the Coding Interview's timeline and preparation map also notes: "Create a list to track mistakes you've made solving problems". It's important to hammer on your blind spots to improve your interview prospects.

A tough topic

For a handful of group members I spoke with during mentorship calls, a particularly difficult topic to improve on has been Dynamic Programming. While putting together the Coding for Interviews course (list member discount MEMBER-JAN-2014 valid until the end of January), this was one of the toughest topics to write about—it's a problem approach strategy I've struggled to become proficient with myself.

Don't be too scared by the name—the term "dynamic programming" was invented in the 1950s to make the topic sound impressive during a defense administration hostile to mathematical research. Dynamic programming was considered a term "not even a Congressman could object to"—because "it's impossible to use dynamic in a pejorative sense".

The good news is that, like bit manipulation problems, dynamic programming problems show up fairly rarely in interiews because of how difficult and time consuming they can be to solve, code up and test. The bad news is that sometimes you'll get these questions asked anyway.

Learning it

While I perused a number of dynamic programming tutorials and university lectures and notes on dynamic programming, I found that (1) writing about dynamic programming and (2) trying dynamic programming practice problems were the most effective activities I did to get better at approaching DP problems.

So let's get that done right now!

Dynamic programming: a hands-on approach

  1. Research and read up on dynamic programming while doing activity #2 below. Here's your free copy of the DP cheat sheet (scribd) I've written to post to the Coding for Interviews Udemy course (which you can join with list member discount MEMBER-JAN-2014)
  2. In a gist using Markdown, write your own "explain it like I'm 5" description of dynamic programming. Guiding questions: (1) what is dynamic programming? (2) how can you recognize a dynamic programming problem? (3) how do you solve a dynamic programming problem?
  3. Solve and submit your solution to this week's dynamic programming practice problem

This week's challenge: Making Change

This week's problem (github, CFI HackerRank) is to enumerate how many ways a given list of coins can be used to make change for a given cash amount (in cents).

So, for example, given the amount 4(¢) and coins of values [1, 2, 3] (1¢, 2¢ and 3¢), your program would output 4—the count of the four solutions:

  1. 1¢, 1¢, 1¢, 1¢
  2. 1¢, 1¢, 2¢
  3. 1¢, 3¢
  4. 2¢, 2¢

Sample function signature: public int coinChangePossibleSolutions(int amount, int[] denominations)

Try this problem out on the Coding for Interviews HackerRank section.

Special thanks to CFI problem team members Alan, Asim and Austin for writing and reviewing practice problems.

Submitting your answer

Reply directly to me with your solutions (photos of paper or whiteboards uploaded to imgur get bonus points) and you may be featured in next week's email. If you typed your solution out, you can post your code as a gist and reply with the link.

Make a note if you're looking for jobs and would like to include your email and location with your solution so others can send you job tips.

Last week's problem:

Last week's problem was to write an email validator. Given an email address, solutions verify whether it is, indeed, a valid email address.

Some chose to use regular expressions (my favorite book on the subject), while others opted to code their own state machines to analyze the emails.

Submitted solutions

How's it going?

Got the job?! Just started a search?

While my mailing list fees have been fueled by your donations, I am fueled by your encouraging stories.

Even if you can't get the Udemy course at an early discount, it's great to hear when people are enjoying the week's issue—reply to me and let me know how your interview preparation is going!

Expand your friends' minds

I end up putting some significant time into preparing our topic overviews and collecting submissions—but the upshot of it is something that's roughly the same amount of work no matter how many of our friends receive this weekly prep. It's like O(log (us and our friends)).

Give your friends and colleagues a link to join us:

so you can practice with them.

Tweets about Interviews

I set up a Twitter account for Coding for Interviews updates on the sporadic schedule, questions for member feedback, and early peeks at your sweet interactive submissions I just can't keep to myself until the next issue.

Miss the topic overview? Suggestion for next week's problem? Let me know:

Follow the group at:

Code every day. Continue improving,

Brian @interviewcoding

PS. If you happen to order the course and would like the full CFI issue archive, email me with the full name you registered with on Udemy and I'll send you the back issues.