Memcached Programming Challenge: Adding Atomic Multiplication

The best engineering interview question challenges candidates to creatively extend a database's functionality while navigating complex code.

### The Best Engineering Question: A Deep Dive into a Memcache Challenge
* 🛠 The author reflects on their favorite engineering interview question encountered at MemSQL in 2013, which involved a **complex database challenge** that **remains relevant today**.
* 💻 This programming challenge revolved around **Memcached**, an in-memory key-value store, where candidates had to demonstrate their understanding of **database interactions and commands**.
* 📜 The interviewee describes the process of using telnet to communicate with Memcached, explaining how to **set and retrieve key-value pairs**, such as storing "**John Smith**" under the key "**full name**."
* 🔄 A unique aspect of the challenge was the requirement to implement an **atomic multiplication command**, as existing commands only allowed for **addition and increment operations**.
* 🤔 The author categorizes candidates into three types based on their approaches to the problem, noting that those who could **creatively solve the challenge by extending existing functionality** were more likely to succeed.
* 🔍 The discussion highlights the intricacies of working with legacy codebases, emphasizing the **importance of understanding existing implementations** while also being able to **innovate**.
* 📊 The author critiques the interview question's design, questioning whether it effectively assesses a candidate's **problem-solving skills** or merely their ability to **copy and paste code**.
* 💬 Ultimately, the piece underscores the **evolving nature of programming challenges** and the necessity for interview questions to **reflect real-world complexities** in software development.

the best engineering question I've ever gotten, part one. I didn't realize that there's a part D to this. It's been a while since I was on the receiving end of a software engineering interview, but I still remember my favorite interview question. It was at MemSQL circa 2013.

I haven't kept their name, so I assume they're not still relying on the specific interview question. I don't feel bad for revealing it. It's a great story that I tell people a lot. I've just never blogged about it. I'd say that if you, if

you're asking a question in 2013, you're still asking the same question in 2024. Yeah, fair, fair and factual. Okay, so this is a question per se. It's a programming challenge. I forget how much time they gave for it. Let's say three hours. O

that's a long one. Uh, to explain the problem, since MemSQL is a database company, this is a database challenge. Okay, so I am probably not capable of understanding this one. I have never done anything with, with, with databases like in the implementation side of

things. MemSQL questions are wild. I could imagine they're quite wild. Introducing Memcached. You know about Memcached? No? Well, it's an in-memory key-value store. Read, uh, let's see, read its about page here. Let's download the code and build it so I can

show you what it does. You may need to brew install lib event and maybe some other stuff in order to build Memcached successfully. It won't be too difficult to figure out. But anyways, wrangling your environment wasn't part of the test. You can assume interviewees were given

access to a Linux box with all the right dependencies in place already if you give me access to a Linux box with all the right dependencies I have already failed because I can't I can't type on query right are you are you assuming my keyboard layout

absolutely unhinged uh for an authentic 2013 experience let's bypass the GitHub repo and untar the Contemporary Source distribution Shazam now we've built the mcash executable let's start running it mcash we can talk to the server via the default mcash port Port 11211 I love

palindromes oh my goodness I love this its protocol is basically plain text so we used the old plain telnet to talk to it if you don't have telnet anymore substitute words Nick D C for telnet all right telnet this guy trying to connect

let's go escape character okay who has not pressed the Escape character who has not pressed that while telnetting there was a time when I used to have when I was when I was at my previous company where I had to use telnet to get like

debugging messages out oh my gosh one would telnet quite regularly uh playing with mcash mcash is a key value store that means we can tell it to remember something and associate between a key and a value and then ask it later for the key again and it'll tell us the

value it remembered in memcache keys are always ASCII strings and values are always arbitrary byte streams which means you must specify their length manually for example type this into the telnet session set full name 0 3600 1 um 10 would be John Smith okay so

3600 must be the expiration. This tells MC to remember the association, uh, the string key, full name, and the 10 byte value, John Smith. The other numbers on that line are flags, value zero to remember alongside the byte stream value, and an exp, expiry timeout 3600, measured

in seconds. Nice. Okay. After which MCash will forget the association anyways. After you type these two lines, MCash will respond, "stored." Okay, so right now this is 2013 and MCash just outperformed Valve, the open source project, has more security and storage ability than Valve does. This

is impressive. Okay. This is really impressive because in 2013 Valve was getting defeated by a text file over and over again. Meanwhile, MCash out here just, just pretending to be a database is already doing better. Uh, now you can retrieve the value of the full name by

typing into the same telnet session, "get full name value." This, John Smith. And nice. I love good old-fashioned Cobal style. Oh man, who wouldn't want to write, who would not want to write a parser for this? It sounds so good right now. This

would actually be a fun parser because you'd have to hit this, you'd have this, this would be the, the key that comes back, which is just awesome that it responds with the key you gave it and then it responds with the text range and then it responds with an end like there

must be a reason to this. Maybe it returns multiple values. I'm not exactly sure why this happens, but man this is so good. This is so good. You can overwrite a value association with a full name by using another set full name command. You can also ask MCash to modify the key in

certain ways, for example, there are special dedicated commands to append and prepend. Append full name Jones. Oh my gosh, is that Alex Jones? No, it's John Smith Jones. Completely ridiculous. Uh, store get full name, get full name 0 to 16. Okay, okay, okay. I like it, of course.

You'll want to append Jones to full name from within a client program. You could do something like this: Python install M Cas, M Cas get full name, set Jones. Let's go. Okay. But the advantage of M Cash's dedicated append command is that it's guaranteed to execute atomically if you

have multiple clients connected to the same M Cash server. They're all trying to append to the same key at the same time, and the get set version might cause some of those updates to be lost. Whereas with append, you're assured that they'll all be accounted for. Another dedicated command

that executes atomically is increment. Awesome. Okay, set age uh 2 37. Nice. This is how many bytes this number is stored in ASCII. Increment that age. Let's go. He also, oh nice, M Cash also is written by Brad Fitz, who did the Ghost standard library. Cool. Let's go.

This response is useful because of the multiple clients thing. Oh really? M Cash responds with the post-incremented value, but it doesn't respond with the key and the length and all that stuff, cuz it does, it seems to be doing this for, for the other ones. All right, interesting.

Interesting. This response is useful because of the multiple clients thing. If you issued a separate get, uh get age command, you might see the new command, uh new value only after several other clients had done their own updates. If you're intending to use the value as a

serial number or as a let's see or a SQL primary key or something like that, then it's very good that there's a way to see the incremented value atomically. M-Cache remembers the incremented value too, of course. Note that 37 and 38 are still being stored

and returned as byte strings. They're decoded from ASCII into integers and back as part of the atomic operation. If you increment a non-integer value, you'll get an error. Okay, nice. Right now, this is very exciting. I feel like I'm I'm really ready for this one. I feel

like my my soul is ready for this interview question. Finally, note that uh in-core is a full-fledged addition operator. You can increment uh by any positive, not just one. Okay, oh nice. By the way, when you're done talking to M-Cache and want to kill the connection

you can type M-Cache quit if you're using Nick, control D, or just go to the terminal window where the M-Cache server is running and control C to bring it down. The challenge modifying M-Cache via its increment and decrementing commands. M-Cache provides a built-in way to

atomically add K to a number, but it doesn't provide any arithmetic operations. In particular, there is no atomic multiply by K operation. Your programming challenge: add a mult command to Memcache. When you're done, it should be able to tell your M-Cache client and looks like this: You have 3 hours. Go. Oh

this is actually a pretty cool question. One reason why I right off the rip think this is a pretty exciting question is the fact that you're going to touch a lot of things here. You're going to touch parsing, right? You're going to have to

figure out how to add commands you're going to have to work with the database you're going to have to do all of it run ink cake times I failed right 3 hours is insane I failed nerd sniped again I'm not getting nerd sniped I'm not going to

spend 3 hours doing this though I want to the problem is I don't have infinite time I know I just stream for a living but man I can feel it in me right uh dude you want to write a parser for this so bad I do parsing is so much fun

I love parsing I love parsing okay shut up this sounds so exciting do it no I refuse I refuse because I because I want to write simulation testing okay so I have to make a choice am I writing simulation testing or am I writing a parser for M cash from

2013 I don't want to do it okay I don't want to do that all right I already know what I want to do I'm not WR I'm not parsing why not both because time is limited I want to spend all the time I

want to spend all the time I can on this because I have to refactor so much stuff here I don't care about a poll guys you must understand that this is not a democracy okay this isn't in fact not a democracy I'm not I'm not doing it the

best engineering question part two before you read this post which contains spoilers you should read this one we've already read this one okay not doing it the challenge modifying mcash via its in-core and Decker commands mcash provides a built-in way to automatically add K to a

number, but it doesn't provide other arithmetic operations, in particular, there is no atomic multiplying by K operation. Your program challenge is to do it. Analysis: This is a great interview problem because it's pretty cleanly partitioned, uh, partitions the candidate pool into three

different types. Type zero is just completely stumped by the challenge of interacting with the real code base. Well, if they're also not familiar with C, dude, I have not seen very much in my life. Okay, I've seen a decent amount but not that much. And so a lot of the

struggle for me would be, you know, I know this is a network to host long, right? Long, long, technically it's a long long. This is just a long, but still, there's like a lot of effort one would have to put in to, you know, to do

it right. Assert long long, man, dude, it's a long long, man, right? Do it. No, I don't think many people in this category would get all the way to this point in the interview process anyways. If you discover that the candidate is in this group, well, don't hire them. Yep, by the

time my sequel, uh, MySQL 2013 was doing deeply arcane high-performance C++ 11, so uh, the fact that this challenge incidentally requires fluency in C was a plus, not a minus for their purposes. If your code base is all Python and Go, you

probably wouldn't use C++ for your interview challenge. Yes, there's definitely a language barrier here, right? Type one folks, uh, looks at the problem and says, "Ah, I know just what to do. Multiplication is just a repeated addition, and we already have an

ready-made addition subroutine in the form of in-core, so I'll just build on top of that. Ah, but instead of adding a con, let's see a constants to X values, we need to add X value to itself. The whole thing needs uh to be atomic. Let's look

at how to the new locking works. They spend all three hours going deeper and deeper down various rabbit holes, never produce anything that works. Candidates in this group don't get hired. Damn, so they try to make, they try to make ad work and then get stuck on

locking. Okay, type two, look at the problem and says, "Ah, I know just how to do this. Multiplication is just like addition, except whenever addition does plus, we should just do multiply." And they copy and paste changes, uh change all the pluses to uh stars and they're done in

90 minutes. Candidates in this group, let's see, stand a really good chance of being hired. Interesting. I would not have expected that would be the one that you wanted to to do the best. Candidates will notice they've got lots of time left and polished their submission, for example by

making sure its formatting is consistent, adding unit tests, and revising their design decisions to make sure they can justify them if asked. Okay, to make sure my time estimates were in the right ballpark yesterday afternoon, I did the whole thing myself. This section is likely to bore all but the most

masochistic readers. Feel free to skip down to the conclusion. Let's get masochistic. I started for gring with in-core. Okay, I started with the exact, I feel like I, I started with the exact same approach, right? Since we want to imitate

uh the existing incore command we must uh it must be paired somewhere that led me to the part of the process command function that looks like this all right nice okay there it is let's go uh the argument with the value okay so where where is this one

in process command there we go so you'd have this one right here which has so this is where this is where we're hitting end of message out of string client it cannot increment or decrement in a non-numeric value nice look at that so we have an ad Delta I feel like we

were already here at ad Delta earlier and then there's a lot of different versions of this exact same thing I feel like we were nice okay and there you go lock unlock hash value okay nice look at this nice little beautiful piece of code you're just doing this so the do the do

ad must be where where this is where this is happening right and there's some implementation of do ad that does it in a nice beautiful way it's in M cast see do get item does all this remove this me cache increment command oh man we're already in the world's greatest

thing ever which have we have we officially hit everybody's favorite let's go let's go let's go we're we're in it we're into the macro system does anybody have any idea what's happening no no you don't no you don't because I don't even know how

this and this work at this point nobody knows how that works all right the argument with a value zero or one corresponds to the parameter bull Inc and I change that uh int to op code to change to the cers okay if tokens equals four or five and

tokens equals incore then we do this equals zero then process arithmetic tokens one one else if tokens do this and we process it with the two nice so just add another if statement and call this uh all right hey that that's good enough for me uh these magic numbers

were a pretty bad design decision but the quick decision keeps me moving forward ah what I see is pretty horrible I will just copy it and move on I'm a good citizen 10 minutes later I realized a better solution Revisited the code I skim over the body of process arithmetic

command looking for a reference of incrementing and uh decrementing the error message client error cannot increment or decrement a non-numeric value seems a little suboptimal so I changed that to code uh change that code to this one okay nice similarly just below I do op code

this one Mal misses all right nice if op code equals two do that okay nice nice mental note that I'll have to add multi misses of field uh to wherever C thread stats is but for now I press forward and I forget the compiler error will remind me ah nice let's go there's

this add Delta here we go Okay add Delta oh interesting so they're actually going to go with not just inor but op code okay gripping forward down the ad Delta let's go do ad Delta let's go we're there nice changing it to op code very

cool CH this signature violates my guidelines for const correct code in that it passes a lot of things by const value but let's not take that bait replace bool with an int and keep going let's go let's go finally we found a place where we're looking for the

where we need the change there it is let's go there's that ink command what the hell is this command doing I don't even know what this command's doing what the hell is it right what the hell is this thing mental note to implement

M-cash malt and press on onward a little further down uh note that the slab stats needs malt hits field we've reached the end of the do add Delta wait this is a do add Delta so what's the add Delta ah it's called from two places the

first place sets bull Inc uh to C command protocol binary command increment gripping for primary command increment reveals that there's an enumeration for all commands in the protocol binary. I should use that add protocol command multiply to that enumeration and refactor all the work I've done so

far to use the protocol binary command decrement this one this one instead of magic numbers 012. Nice. Int op code can stay as an INT since grepping for the enumeration types name uh reveals that literally nothing in the codebase uses the type by name.

Dude creates an enumeration and then immediately never uses it oh that is so good that is so so good that's like everything we've ever wanted dual pointer reference referenced yeah nothing seems better implementing M cached command malt in traced H tells me that I need a macro named M-cash malt

enabled so what's this used it's not let's see so where is that used it's not okay okay anyways Chesterton's fence I don't know why these are enabled macros exist then I certainly shouldn't try to do anything novel with my new one I'll

Follow The Herd, what a great usage of Chesterton's fence, by the way. It already exists, keep the fence there. You know, we were just looking at that going, "What the heck is this thing? Right, what are you doing? What is this enabled, and why is it a"

zero? Right? What the heck? Right? And I only see it once, so I don't know what that even means. I'm not good at, like, this is where my C breaks down is once we get into the macro area. I feel very generally confused. Finishing up the REM, uh, remaining compiler errors.

I add malt hits to the struct slab, uh, stats, right next to the increment hits and decrement hits. Uh, get grep ink hits, shows a lot of places it's used. When I'm done, grep hits, uh, hits shows the same number of uses. All right, nice. Hey, that's

a great, by the way, that's a great way of doing it. You already know ink hits exists. If you can have the exact same amount of malt, malt hits, then you probably are on the right track. That's good. It's sneaky because I had to modify

my, uh, my copy of it in two places. I also added malt misses field to the struct and thread stats, and ready change. Uh-oh, uh-oh. See now we have a switch. Yep, there it is. Nice. Okay, good. We don't technically need to change add Delta

itself from taking a const int increment or to taking a const int in op code, but I think it's a good idea. Uh, so I reached, uh, the code completion milestone in 25 minutes. Let's try it out. A crap! I returned to the one place where

multiplication is supposed to be happening ah that should be using my new protocol binary command multiply I fixed that in fact I grabbed for op code equals and I fixed let's see and fix a few more places I'd miss I reached code really

complete milestone in 32 minutes this time the code really does seem to work I run a few manual tests nice nice I check its behavior on instruction wraparound and I check the syntax multiply 10 no reply to make sure that it's not it's also supported since I

implemented everything by copying and pasting there's basically no way these things won't work just as well as they work in increment and decrement hm with all this manual testing I should probably write some actual tests are there tests in the repo yes under T mate uh test builds run them so I copy T

inker and T- malt and modify it nice let's go I imagine a candidate who didn't mess with the test would still pass the interview priorities in an interview are different from priorities when making a pull request therefore this is a great place for even most

introverted candidates to raise their head and interact a little bit I think I've got something that works do you want me to take a look or do you want to take a look this is good by the way this is very interesting this is pretty sweet I see there's more tests in the

binary te I guess I should take a look at them too even though I don't feel like it yeah yikes there's another copy of the command enumeration in there I should add command multiply to it at least I should also test for the new stats in stats T actually because one of

These tests simply count the number of stats returned. I've added two more stats, and let's see that test would fail if I didn't modify it. Then around the 60-minute mark, I hit the code and test pass milestone for the second time. But as I

puzzle my way through the UDP, I find lots of tests devoted to the binary protocol as opposed to the plain text protocol we talked about in the problem statement. Should I modify the binary protocol as well as the plain text one? Actually, I have already, thanks to the mindless diff

in the function dispatch bin command. Nice for those, I see people asking for the uh article. There you go. There's the article. You can have the article too. Uh, 100% I would have just used the anchor function multiple times and hoped it worked. The problem with that, Steve, is

that you automatically introduce a uh race condition because even though the the addition function is in fact itself um what's it called? The addition function itself is atomic, right? So you'd have a lock and an unlock, and then you'd have an add in the

middle. You'd have to do the four, you know, the the four I equals uh zero up to M problem, right? And then you'd be adding N, right? So the problem here is that it's locked, unlocked. If you have two of these running at the same time, you will not

get the you will not get the response you were hoping for, right? You will not get the response you were hoping for, and it'll be sag, but higher up. Uh, I see quite uh quiet versions of the same op codes. Uh, oh, I am not sure what those

are for but in order to do my copy paste trick in UDP I'll have to add one of those to the Manchester on fence against I don't know why these quiet op codes are important but if Inc and deck have them then malt should have one

too so I add protocol binary command multiply well telnet is a TCP right so I would assume that there's must be some sort of UDP there must be some sort of UDP thing at this point I'm just repeating uh running make test and banging my head

against the idiosyncrasies of the test code which is all written in Perl and full of five and six parameter functions I belatedly realize that some of the test files are failing simply because they start with a

cryptic indication that says I plan to run exactly 95 test cases but I've added extra tests and this makes the plan fail dear goodness around 90 minutes I call it a day some of the binary protocol Pearl tests are still failing but I'm confident that that's a

problem with my test not with the server code itself here's the secret downside to just copy and paste the and change the names the Pearl tests for incor are basically in the same form nicely obfuscated through a number of layers and indirect direction so when I

let's see when I do the obvious thing for multiplication it comes out like this that's pretty bad test now if if making good tests was the point of the programming challenge I'd spend an extra hour on it or if I were doing this to get a job instead of for a blog post I'll

spend a couple uh I'll spend the extra hour on it but for this blog post I call it a day by the way this is fantastic I love this um you know now looking at over this I'm not convinced this is actually that great of an interview question

honestly if the goal is just to see how good you can grip through it and get to this point and how much like how hard you can go on Chesterton's fence slash um of being a good citizen it doesn't really feel like it's a it's a win in the

sense that do you want like it's good that somebody can mimic and go into a code base they've never seen and mimic its behavior and add something it's not bad but do you want that right do you want somebody that can just go in and just

hack away or like do you want the person that wants to refactor right because this is like very different than how you would approach it for maybe your job what's wrong with that well it's not that it's just that you have someone speedrunning a

change Do you want a speedrun change Is that what we're aiming for how do you know that you're getting the right behavior isn't that uh typical for an employee but do you want an employee that do that uh that does that do you want an employee

that what they do is just copy and paste their way through things or do you want somebody yeah for junior devs that's fine or do you want somebody that actually asks questions and go hey I'm not sure you know he took shortcuts I mean shortcuts are valid sometimes you

got to know when to take a shortcut maybe this is a better test saying that he knows how to take a shortcut when he's supposed to take a shortcut as opposed to doing the right thing just given the time we've got a deadline people we'll patch

it later if needed and that's how everybody hates their life so I'm not saying this is good or bad speedrun employees create technical debt yeah I'm not even sure if this would be considered technical debt is this technical debt I don't think this is really

technical debt it's just adding yet another little you know Branch to your to your your parsing it's just kind of interesting to be like how fast can you find and copy and paste out exactly what to do and if you go the wrong route you're dead it doesn't feel

good because I want I I always want challenges that a user should be able to think through if they're familiar like my personal favorite one that I always did at Netflix was uh async uh async Q I want to be able to take a bunch of tasks coming in and I

The Best Interview Question For Devs

This is a place for all the things that are awesome on stream. 

ThePrimeTime

Introduction of a MemSQL Interview Question from 2013

The speaker recounts their favorite software engineering interview question from MemSQL in 2013.

The speaker states they don't remember the interviewer's name and feels comfortable sharing the question.

The question is described as a three-hour programming challenge involving a database.

The speaker acknowledges their limited experience with database implementation.

The challenge involves Memcached, an in-memory key-value store.

Explanation of Memcached and its Functionality

The speaker explains how to interact with Memcached using telnet or netcat.

Memcached's key-value storage mechanism is described, including key and value specifications.

An example of setting a key-value pair with expiration is demonstrated.

Memcached's performance is compared to Valve in 2013, highlighting its superiority.

Retrieving values using the 'get' command is explained.

The Programming Challenge: Adding a 'mult' Command to Memcached

The challenge is to add a 'mult' command for atomic multiplication, lacking in Memcached.

The speaker highlights the multifaceted nature of the challenge, involving parsing, command addition, database interaction, and concurrency.

The speaker initially hesitates due to time constraints.

The challenge is reiterated, emphasizing the lack of atomic multiplication.

Analysis of Candidate Responses to the Challenge

Three types of candidate responses are categorized: those stumped by the codebase, those stuck on locking, and those who successfully implement the 'mult' command.

Type zero candidates are unfamiliar with C and struggle with the codebase.

The suitability of the challenge depends on the company's tech stack.

Type one candidates attempt a repeated addition approach but get stuck on locking.

Type two candidates successfully implement the solution in approximately 90 minutes.

The speaker solves the challenge themselves, providing a detailed walkthrough.

The speaker starts by examining the 'incore' command's implementation.

The speaker adds an 'if' statement to handle the new 'mult' command.

The speaker refactors the code for better error handling.

The speaker addresses the use of protocol binary commands and refactors using an enumeration.

Evaluation of the Interview Question's Effectiveness

The speaker questions the effectiveness of the interview question, highlighting its focus on speed and code mimicry rather than deeper understanding or design choices.

The speaker debates whether the question prioritizes speedrunning over thoughtful problem-solving.

The speaker suggests that the question might test the ability to take shortcuts appropriately, but acknowledges potential drawbacks.

The speaker discusses whether the solution creates technical debt.

Alternative Interview Question Suggestion: Asynchronous Queue

The speaker proposes an alternative interview question focusing on asynchronous queue implementation with max parallelization.

This question's simplicity allows for assessing JavaScript proficiency.

The question can be approached from either a client or server perspective.

The speaker suggests evaluating candidates' approaches to testing and extensibility.

The speaker mentions follow-up questions about error handling and retries.

The speaker summarizes the Memcached challenge as a microcosm of real-world programming in large codebases.

The speaker emphasizes the well-crafted nature of the question, guiding qualified candidates towards a correct solution.

The speaker compares the question's effectiveness to FizzBuzz for programmers.

The speaker discusses the distinction between software engineers and programmers.

The speaker mentions the importance of asking questions before replicating code.