Algorithms: Binary Search, Revisted

A while back I walked through the basic idea of binary search. Knowing what binary search is, and implementing it however, are very very different things.

I’ve been taking a technical interviewing course, in order to add some sort of method to the madness of my job hunt. Pretty much every day we’re whiteboarding and mock interviewing. Last night I received the following question while I stood at the whiteboard:

Number of Ones
Given a sorted bit array (values of 0, and 1) determine the number of 1’s in the array.

Input: Array of elements with values belong to the set S : { 0, 1 }
Output: Integer
Example
Input: [0, 0, 0, 1, 1, 1] => Output: 3
Input: [0, 0, 0, 0] => Output: 0

Constraints
Time Complexity: O(log n) A linear search is not acceptable for runtime.
Auxiliary Space Complexity: O(1)

So, the naive solution here would be to iterate over the entire array, and keep count of how many ones we encounter (or just use Ruby’s built in count method…). But of course to check every item in the array that would be time of O(n). Linear search runtime isn’t acceptable!!!

Several things made my mind jump to binary search. First off, the array is sorted. Second, the very obvious time complexity of O(log n). And also the entire array is binary. Isn’t that cute.

But just because you know what to do doesn’t mean that it will be easy. I decided in my approach to have a “middle_index” that I was moving around throughout the array, but I forgot to implement a start_index and an end_index to keep track of my new subarrays. GAH!!! I kept trying to make only middle_index work until I ran out of time. When I was told about the additional markers, it felt so so obvious to me, and so much simpler. In fact, when I was walking through my diagram of the problem on a test array, my hands were the natural bounds of the start_index and the end_index. It just didn’t register.

Anyways, today I went back and finished up my ruby method for this problem. I almost forgot to account for the two cases that might drive me into an infinite loop: an array of all 0’s or all 1’s. I think it will take me several more runs of this, but hopefully someday implementing binary search will be fast and breezy.

And here’s my general Ruby implementation of Binary Search.

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.

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!

 

Meetups: Women Who Code SF

wwc

Event: Ruby and Web Tuesdays

This is a study group and you are welcome to work on anything you would like in our friendly and helpful environment. Organizers and core team members of the Ruby Study group will be present to help you with any Ruby related questions. We welcome many levels of attendees: brand new beginners, coders new to Ruby/Rails, experienced Rubyists, and anyone in between. Work on tutorials, personal projects, or just network! 

Agenda

6:30 Dinner 

7:00 Introductions

7:05 – 7:15 Introduction to Premise Data by Yang Hong

7:15 – 7:25 “Authentication, Authorization, and Why You Need Them Both!” with Ellie Day

7:25 – 9 Code!

Group: Women Who Code SF

Women Who Code is a global nonprofit organization dedicated to inspiring women to excel in technology careers by creating a global, connected community of women in technology. The organization tripled in 2013 and has grown to be one of the largest communities of women engineers in the world.

Women Who code is a professional community for women in tech. We provide an avenue for women to pursue a career in technology, help them gain new skills and hone existing skills for professional advancement, and foster environments where networking and mentorship are valued.

Location: Premise Data

Experience: So, I went to a Women Who Code study group way back, about 5 months ago! It was WWCode East Bay’s Programming and Dev study group held at Clef. I had a mixed experience at that event, mostly due to the long commute and lack of structure to the night.

My experience at the Ruby and Web Tuesdays (why don’t they just call it Ruby Tuesdays???) study group was much better, and I can attribute most of that to the fact that we were all there to study Ruby. There were two quick talks to start off the night (an overview of Premise Data, the company who was hosting the study group that night, and a very clear introduction to authentication and authorization), and they were both interesting, but also just the right length. Turnout at this event was stronger, with about 30 people. The women I met were of all skill levels, some a few years into web development, and one woman who had just created her GitHub account the other day! I got a bit of studying done, and managed to help a person or two, but as usual, going to this study group was really more about being around other people.

Verdict: It was a positive experience in a supportive environment. I’m definitely adding it to my regular rotation of meetups, and since it happens every other week, I think that’s sustainable.

Meetups: Hire Ruby Engineers

Event: July Hire Ruby 

It’s never been a better time to be a Ruby developer, or a more challenging time for companies to find an appropriate fit in the Bay Area. We’re excited to provide free opportunities for talent and companies to meet in the real world. Some presenting companies from past events include:User Testing, TouchOfModern, HumbleBundle, Enjoytech, Stitchfix, Tapjoy, MatterMark, Razer, Adobe, and many more. 

Here’s the run of show:

6:00 – 6:45 pm: Doors open, food and drinks sponsored by Hired

7:00 – 7:30 pm: Startup interviews, quick pitches, and announcements

7:30- 8:30pm: Meet developers and companies, mix it up

Group: Hire Ruby Engineers

Location: The Vault

Experience: I’ve been curious about the “Hire Ruby” events ever since I saw them pop up on Meetup.com way back when. Now that I’m finished with my program and looking for a new job, this was the first time that I felt truly ready to attend one of these events.

The program was pretty straightforward. I showed up, grabbed a beer and some pizza, then scoped out a seat. The room was packed, but I found a seat up front next to one of my bootcamp classmates.

Basically, hiring managers / company representatives volunteered on the spot to be interviewed by the meetup coordinator. They gave a bit of an overview of their company, and tried to sell themselves as a great place to work. The audience then got to ask a few questions, usually about the tech stack, company growth, or current challenges. It was a little strange, like a dating show. Once the main interviews were over, there was something of a lightning round – a few more hiring managers each had about a minute to introduce themselves and their company.

Then it was time to mingle. I’ve attended recruiting events before, and this was similar chaos. Large groups of hungry job hunters encircled each hiring manager, eager to shake hands and get about a minute or two to chat and push their resume, with the rest of the circle watching as well. So awkward!

Verdict: Was it worth it? Well, I didn’t end up speaking directly to a hiring manager. I joined a circle, hoping to talk to a hiring manager for a healthcare startup, but I ended up moving on, deciding that I would email the man later. It was just too unorganized.

On the other hand, I did learn of several promising companies that I’d never heard of before, and I got a read on the type of work they do and what the general company culture was like. I also got to see bootcamp friends again, and enjoy some free pizza and beer. So overall, a win.

Scroll To Top