Two years ago, I started this blog with (mostly) a series of posts on the small coding problems that came across my path at the time. Most of these were told to me by my brother-in-law who had been interviewing for his first software engineering position. He had been given dozens of problems such as, “Given a bishop in a given position on a chess board, and a target position, determine the number of moves the bishop would take to arrive at the destination,” or, “Find all pairs of numbers in an array that sum to a given number.”
Recently another one of these crossed my path, and I thought it was a great problem.
Given an array of integers, and a target sum, find out if there is a subarray that sums up to that value.
What I like about this problem is that it is similar to some well-known algorithm problems but tweaked just enough that it is unique. Also, it can be solved in a variety of ways, some more efficient than others. If you enjoy puzzling through coding problems, please try to solve this and see if you can do it in O(n) time. Then, when you are ready, visit the gist of my solution (done in Java since more people know it) and let’s compare notes!