Cookie Queue
No dogma, just what I'm learning and thinking about right now.
Comments and feedback are welcome on Mastodon.
"If you're thinking without writing, then you just think you're thinking."
—Leslie Lamport
Implementing an abstract datatype for managing cookie jars. :) Or, three solutions to a playful problem.
Disappointment is the mother of invention
I’m currently in the midst of a job search, and coding challenges are a fact of life. I recently had a bad experience with a coding challenge interview–bad because I didn’t do a good enough job. I rushed to a solution, thinking that this was the only goal: could I solve the problem. But my solution failed to demonstrate my understanding of higher concepts, like object-oriented design. In short, my design was not resilient to change–which quickly became evident in the code review.
I decided to revisit some coding challenge sites to practice more–not just solutions, but design. And that brought me to this challenge.
The Cookie Jar Problem
In this problem, you are given a collection of cookies of varying sweetness. However, the boss will only accept cookies of a certain level of sweetness. Your job is combine the two least-sweet cookies to create a new cookie. The sweetness of the new cookie will be equal to the sweetness of the least-sweet cookie, plus double the sweetness of the second-least-sweet cookie. The question is, how many “steps” (combining of cookies) would it take to get the whole batch up the minimum sweetness? If this is not possible, return -1 in place of the number of steps.
Like most of these challenges, it helps if you know the correct algorithm or data structure to use, since “naive” solutions will usually time out in the test suite. Nevertheless, I decided to implement a naive solution first to help me understand the problem.
First Solution: Brute Force
In my first solution, I started by sorting the batch (array) of cookies, then iteratively combined the two least-sweet cookies until all of the remaining cookies reached the required sweetness, finally returning the number of steps needed to get there. The only way to fail is if combining all of the cookies in the batch is still insufficiently sweet.
This worked correctly, but half of the tests were timing out. Not unexpected, but not good. The issue with time complexity in this challenge is the insertion of the “new” cookies into the sorted cookie batch. Manual insertion has an exponential complexity–that wouldn’t cut it in this challenge. Even if you only work on the “less sweet” cookies, and completely removed the sweeter cookies, a sufficiently large problem batch would still time out.
I knew the textbook answer at this point was to choose and implement an appropriate data structure to reduce the time complexity. But a niggling thought kept tugging at me: what if I could work with the new cookies separately, without merging them back into the original batch? I imagined that this solution would still have an insertion problem, just within a smaller set. That wasn’t sufficiently performant when I trimmed off the “sweet enough” cookies, so I didn’t think it would work fast enough here either. Better to stick to the textbook.
Second Solution: A Min Heap Process Queue ✨
A process queue is basically an ordered, sorted set. Insertions are automatically placed in their proper order, and there is a pop or poll or take function that returns the minimum value in the queue (or the maximum value, as the case may be). I believe this datatype is usually implemented using a heap–in this case, a “min heap.” So I decided to implement a min heap in Ruby.
A heap is a binary tree data structure where the nodes are sorted in some way, usually by ascending (a min heap) or descending (a max heap) values. A min heap is a good choice for this problem because the time complexity for insertions is logarithmic (better than exponential). I expected this to be fast enough to solve my time out issues.
I was very happy with my min heap implementation. It had only four public instance methods: push, pop, peek, and size. Nice and simple. More importantly, my “runner” was way nicer, with all of the procedural code of my first solution replaced with this:
def cookies(k, a)
# Write your code here
cookie_jar = MinHeap.new(a)
steps = 0
until cookie_jar.size == 1 || cookie_jar.peek >= k do
cookie_jar.push(cookie_jar.pop + (2 * cookie_jar.pop))
steps += 1
end
return -1 if cookie_jar.peek < k
steps
end
Nice! More importantly, it worked: all tests were passing. But . . . I couldn’t escape that nagging thought. Min heaps are fast and all, but they still require these fiddly insertions and rejiggering when a value is “popped.” Plus the code is filled with peek and pop. What do these terms have to do with cookie jars?
That’s when inspiration hit: if you start with a sorted batch of cookies, then each “new” cookie made would be at least as sweet as the last new cookie made! The sweetness would never go down! New cookies would always be created in a pre-sorted order! This changed everything. I decided to create a new queue. A double queue that stores “old” cookies and “new” cookies separately–a CookieQueue!
I started by writing the interface that I wanted to use. I changed the “runner” method to look like this:
def cookies(k, a)
# Write your code here
cookie_jar = CookieQueue.new(a)
steps = 0
until cookie_jar.size == 1 || cookie_jar.sweeter_than?(k) do
new_cookie = cookie_jar.take_cookie + (2 * cookie_jar.take_cookie)
cookie_jar.add_cookie(new_cookie)
steps += 1
end
return steps if cookie_jar.sweeter_than?(k)
-1
end
If you’re wondering about the conditionals here, there are three possible outcomes. They go like this:
- All of the cookies reach the minimum sweetness (success).
- There is only one cookie left, and it is sweet enough (success).
- There is only one cookie left, and it is not sweet enough (failure).
It looks like I only need to implement four methods to make this work (in addition to initialize): add_cookie, take_cookie, size, and sweeter_than?. Let’s look at each of them.
For initialize, we only need to create two “queues”: old_cookies and new_cookies. We’ll sort the incoming batch (array) argument and assign it to @old_cookies. @new_cookies will start as an empty array.
def initialize(batch)
@old_cookies = batch.sort
@new_cookies = []
end
Next, add_cookie will add any new cookies to the new_cookie queue.
def add_cookie(cookie)
@new_cookies.push(cookie)
end
Next up is take_cookie. This is the most complicated method because it needs to decide from which queue to take the next cookie. In looking at this method, you may wonder why there is no guard clause for when both queues are empty. That is because this cannot occur within the parameters of this problem: there will always be at least one cookie in one of the queues.
def take_cookie
return @old_cookies.shift if @new_cookies.empty?
return @new_cookies.shift if @old_cookies.empty?
return @old_cookies.shift if @old_cookies.first <= @new_cookies.first
@new_cookies.shift
end
The next method is size, the sum of the sizes of the two queues.
def size
@old_cookies.size + @new_cookies.size
end
Finally, we have sweeter_than?. If you know your Ruby Array methods, you may know that calling #all? on an empty array always returns true (as odd as that may be). However, once again, we do not have to guard against that situation in this method because at least one of the queues is guaranteed to have one cookie.
def sweeter_than?(sweetness)
[@old_cookies.first, @new_cookies.first].compact.all? { |cookie| cookie >= sweetness }
end
And that’s it! We have a CookieQueue! If I’m not mistaken, this implementation is the fastest of the three. All of the magic is in the add_cookie method: since every new cookie will be at least as sweet as the previous new cookie, we can simply push each new cookie into the queue. Faster even than the fancy-pants min heap! I believe this approach brings this solution down to linear time.
Sweet! (yeah, sorry 😒)
Thank you for reading! The complete CookieQueue class is below. Discussion, feedback, and corrections are welcome on Mastodon.
class CookieQueue
def initialize(batch)
@old_cookies = batch.sort
@new_cookies = []
end
def add_cookie(cookie)
@new_cookies.push(cookie)
end
def take_cookie
return @old_cookies.shift if @new_cookies.empty?
return @new_cookies.shift if @old_cookies.empty?
return @old_cookies.shift if @old_cookies.first <= @new_cookies.first
@new_cookies.shift
end
def size
@old_cookies.size + @new_cookies.size
end
def sweeter_than?(sweetness)
[@old_cookies.first, @new_cookies.first].compact.all? { |cookie| cookie >= sweetness }
end
end