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.

OKAY THEN.

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.

TA DA.

10 Things I Learned at My First Hackathon

IMG_4450

I forgot to mention it last week, but I finally attended my first hackathon! Ryan helped me score tickets to TechCrunch Disrupt’s Hackathon, a 24 hour test of “coding endurance.” This was the big time! I pulled together a small team of San Francisco Learn-ers, plus my roommate.

I didn’t have a concrete goal for the event. Mostly I just wanted to take it all in and have fun, meet some new people and feel inspired. Our team ended up pivoting at the last minute and running out of time to finish our project,  but I did learn a ton just by being there. So, in no particular order of importance, here are some tips for your first hackathon:

  1. Don’t go hungry – Usually food and drinks are available, but just in case there’s nothing to your liking, pack some backup snacks and drinks.
  2. Be comfy – Wear layers. Wear stretchy pants. It might get cold if they jack up the AC. In our case, the event was held in a huge drafty refurbished pier that was right on the water. Cold wind blew through the open doors at all hours. My classmate who was only in a t-shirt was miserable by nightfall.
  3. Decide whether you’re going to sleep over and if so, bring a sleeping bag! I felt like an idiot at first for bringing mine, but as the hours crept on, the sleeping bags came out. Some people even brought cots!
  4. If possible, form your team beforehand, and pick a team leader. It seems like it naturally comes about based on whose idea is used, but it helps so much having one person keeping everyone else on task.
  5. Possibly more important, come to the event with project ideas, and an idea of what technologies you’d like to use. We spent wayyyy too long just bouncing around ideas.
  6. There were some great API workshops at the hackathon, but you would have a leg up if you spent the day before the event brushing up on the available APIs. You can find this information on the hackathon’s website. Just check out the rules or sponsors section.
  7. GitHub + Trello = Organization! We immediately created a repo for our work, but having a Trello board would have helped us keep tabs on the state of the project. GitHub has a new projects feature, which is very similar to Trello, so I’m looking forward to using that in my next group project.
  8. You may be going HAM on your project, but be sure to make some time to network! Chat with the reps manning the booths, do silly things to get schwag (I jumped through so many hoops with Cisco Spark to score pizza for my team), meet your neighbors… and of course be nice to the poor staff working the event.
  9. Don’t be afraid to change your project idea at the last minute. All the cool kids are doing it. We changed ours at oh… approximately 7pm.
  10. Your project doesn’t have to be perfect. Just get the damn thing working enough to show it off. Don’t make it any more complicated than you need to!

Here are some more pictures from the event:

IMG_4452

IMG_4459
Several hours in and the tables were covered in pizza, candy, charging cables, coffee, schwag, and… makeshift standing desks
Midnight
Midnight
3am study break
3am study break
IMG_4475
4 am

 

IMG_4474
Sleepy time

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 Codewars.com.

  • 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!

 

Scroll To Top