Algorithms: Max Length of the Subarray Where the Sum of Elements is Less than or Equal to K

Here’s a recent coding challenge that I completed for a job interview. Recent as in… I finished it about 30 minutes ago… I had a devil of a time figuring out what to call this problem, but basically…

You’re given an array and an integer k. Return the length of the longest subarray where when you add up the elements inside the subarray, it’s less than or equal to k.

Input:  ( [1, 2, 3] , 3 )

Output:  2

# So, just to clarify here… All of the possible subarrays in the above example would be:

[1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3].

[1, 2] is the largest subarray where the sum is less than or equal to 3. [1, 2].length = 2, so we return 2.


I’ve been learning about creating recursive functions with the help of helper methods, or helper lambdas in Ruby’s case. For this code challenge I felt like I didn’t have time to play around with new techniques so I just created two separate methods.

find_subarrays takes an array and spits out the combination of subarrays. I called [1..-1] because I didn’t want to include the empty array that is included in the beginning.

My max_length function takes in an array and the integer k, creates a holder variable qualified_subarrays_lengths. Originally I was going to throw the entire subarrays into the variable when I found a match, but then I decided that just the length would be enough to solve the problem.

First I found all the subarrays by calling find_subarrays. Then I iterated over this array and checked to see if the sum of elements were equal to or below k (*oh look it’s our good friend Inject, thanks for being helpful!). If so I pushed the length of the subarray onto the qualified_subarrays_lengths array. After iterating across all subarrays, I just took the max value from qualified_subarrays_lengths.


Ruby Basics: Inject & Reduce

As you might imagine, my days have been full of all things job hunt. I mentioned earlier that a large part of my preparation is learning data structures and algorithms for the dreaded technical interview.

But before one even gets to the technical interview, there’s usually the coding challenge or toy problem. This can appear several different ways. Perhaps HR sends you a link to a private and timed HackerRank challenge. Or maybe suddenly your 15 minute meet and greet phone call turns into a 45 minute surprise technical screen (true story). Coding challenges are their own unique pressure.

Most code challenges that I’ve encountered so far have involved string or array manipulation. I suppose that these problems are good indicators for how comfortable you are with the basics, and based on your style, how well you know your language of choice.

Ruby’s Inject (AKA Reduce) is a lovely method that makes your code SO MUCH CLEANER. It’s great stuff, you just gotta learn the pattern. Here’s the official description of Inject/Reduce from the Ruby docs:

Combines all elements of enum by applying a binary operation, specified by a block or a symbol that names a method or operator.

If you specify a block, then for each element in enum the block is passed an accumulator value (memo) and the element. If you specify a symbol instead, then each element in the collection will be passed to the named method of memo. In either case, the result becomes the new value for memo. At the end of the iteration, the final value of memo is the return value for the method.

If you do not explicitly specify an initial value for memo, then the first element of collection is used as the initial value of memo.

Inject is great for those problems that are like “what’s the product of all the odd numbers found in this array?” Here’s a simple example problem that shows the use of reduce. It’s from

  • Create a function that returns the sum of the two lowest positive numbers given an array of minimum 4 integers. No floats or empty arrays will be passed.
  • For example, when an array is passed like [19, 5, 42, 2, 77], the output should be 7.
  • [10, 343445353,3453445, 3453545353453] should return 3453455.
  • Tip: Do not modify the original array but create a new one.
  • Create a function that calculates the sum of the two lowest numbers given an array of positive integers.

My First Pass Solution:

In my initial answer I decided to grab the last two numbers with min, which returns an array of the two smallest values which I saved under the variable lowest_nums. Then I returned the sum of these two elements.

But there is a better way!

In the top example, we’re chaining inject on to the result of numbers.min(2). It will take that array and perform the + operation on all of the elements of the array. The second example is the same function but in block form. It’s more verbose, but I think it’s easier to understand upon a quick glance.

Whether you go the symbol or block route, in both cases you can pass inject a starting value like this

inject(0, :+) or inject(0) { |sum, n| sum + n }

but if you don’t, as seen in my examples above, then it assumes the starting amount that is operated on is 0.

Happy injecting!


Algorithms: Compute the nth Fibonacci Number

So I’ve been using a variety of resources for studying algorithms, from InterviewCake to FreeCodeCamp to Coursera, and many more. This is a problem that keeps coming up everywhere, so I thought that it would be helpful to walk through it.

Problem: Write a function fib(n) that takes an integer n and returns the nth Fibonacci number. Example functionality: fib(1) => 1, fib(3)=> 2, fib(5) = 5.

Background: In the Fibonacci sequence, each number is the sum of the previous two Fibonacci numbers. The first few numbers (0 and 1) are base cases. Here are the first few numbers of the sequence:

0, 1, 1, 2, 3, 5, 8, 13, 21…


Since Fibonacci numbers are created by adding together previous numbers in the sequence (also themselves Fibonacci numbers), handling this with recursion is an option.

fib(n) = fib(n – 1) + fib(n-2)

Recursive Solution:

Adding in base cases for 0 and 1, the function would look something like this.

def fib(n)
   if n == 0 || n == 1 # base cases
       return n
   return fib(n-1) + fib(n-2)

Of course all of this recursion will require a lot of time, O(2^n) to be exact. This exponential time cost comes from the fact that we’re repeating quite a bit of work. Memoization is a technique that we can use to save results and avoid repeated work, but instead of recursion, we can also go the other way and solve the problem iteratively, AKA “Bottom up.”

Iterative Solution: 

def fib(n)
   # edge cases of negative entries, 0 and 1
   if n < 0
       raise Exception, “Index can’t be negative.”
   elsif n == 0 || n == 1
       return n

   first_num = 0
   second_num = 1

   (n-1).times do
       current_num = first_num + second_num
       first_num = second_num
       second_num = current_num
   return current_num

The time complexity for this version of the solution depends on just how big n is, so O(n). The recursive solution is beautiful and short, but I think that the iterative version makes more sense in my head. Shockingly, it’s also faster!

Algorithms: Binary Search

Lately I’ve been all in on the job hunt. I’ve been tweaking my resume and LinkedIn. I’ve been thinking deeply about who I am and what I bring to the table for a potential employer, and how I might best express that in an interview conversation. I’ve been attending events and trying to get involved in the local community as best I can. I’ve been coding away on a number of silly little projects. I feel ready to start applying for jobs, except for one little thing…

The technical interview. Interviewing is hard enough, but knowing myself, I am terrible at performing on the spot. My thinking freezes up. Then you throw in the anecdotes that technical interviews are all around stressful and are meant to push you to your breaking point… well, I feel a bit intimidated.

So I’ve been preparing the best way I know how. Studying and practicing technical interview stuff until it feels routine. Taking in as much information as possible. Basically I’m trying to cram a semester of data structures and algorithms into my head. I still don’t feel ready at all, but I thought that it might help me cement some concepts by trying to explain them here.

Binary Search

Let’s start with the good ole’ binary search algorithm. Binary search is one approach to the problem “How do you find something in a sorted array?”. Note the word SORTED, that is key here.

To use binary search, you start in the middle of your array, then compare that item’s value to the value that you’re looking for. Is it bigger or smaller than your target? Whichever it is, you now know which half of the array you need to search next. With this, you’ve effectively cut the number of items you need to search in half. You continue along in this fashion, repeatedly comparing values and eliminating options until you come to your value (or not!).

A real world example of using the Binary Search Algorithm is when you go up to pick up a graded assignment from your teacher’s desk. They’ve sorted all the assignments alphabetically by last name. My last name is “Tran”, so in order to find my assignment I’d check the stack somewhere in the middle, perhaps see that where I’ve stopped is “Hall”, and then I’d limit my search to the second half of the stack. Then I’d check a random spot in this stack, and see “Vick”, and realize that I went too far. And on, and on, until I got to my paper.

Time Considerations

The worst case scenario for searching a sorted array would be O(n), where n is the number of items in the list. This is assuming that you have to check every single item in the list to find what you’re looking for.

Using binary search, every time you check the array, you’re splitting the problem in half. This results in a time cost of O(log n), also expressed in shorthand as O(lg n), which I don’t understand how saving the time of “o” is really all that big of a time save, but so it is…

Further Resources

Learn set me up with a subscription to InterviewCake, and I’ve found it helpful so far. Their intro page on Binary Search includes links to relevant practice problems at the bottom.

Scroll To Top