Amazon Coding Sample (SIP)

[Music] I'm Erica Gomez and I'm a senior manager of engineering at Amazon today what we're gonna talk through is how to do coding on the whiteboard now I know it seems really intimidating but it doesn't have to be there's a super structured way to walk through these types of problems so what is it that we're looking for when we talk about whiteboard coding well there are a few things that as a company we're trying to understand about your skill set the first one is do you know your computer science fundamentals how are you on data

structures and algorithms the second is do you have a heuristic for problem solving or do you just kind of randomly approach problems and the third thing is is do you write clean logical maintainable code that other people can readily understand so why are we doing this well because this is the kind of stuff that you do every single day at Amazon you're going to be using the core principles of computer science to tackle super hard problems and chances are at some point other people are gonna be reading and maintaining your code so how do we

go about this well there are a few key principles that I want you to keep in mind as you think about these types of problems it's really not about have you done every single sample problem that you found online it's one do you not jump into the problem immediately without looking at the space that it's in to do you try and disambiguate the problem ask questions try and understand the inputs and outputs what are some of the edge cases that you need to be thinking about and three do you talk this out loud this is

a dialogue with your interviewer it's you know not a recitation and so try and make sure that as you're writing code on the board you're helping us understand what you're thinking and why and how you're trying to solve that problem and so once you've gone through this process I'm going to talk you through an example problem of how to actually go through solving the problem on the whiteboard talking out loud and thinking about all the things that you need to do in order to finish these types of problems successfully when you interview at Amazon you

can expect somewhere between two and four questions like this and so this is a good to build for your interview here so why don't we jump right in one thing I do want to remind you of is this is not a test of domain knowledge if interviewer asks you a question about rugby we don't expect you to know the rules of rugby this is about seeing can you take an ambiguous problem try and disambiguate the edges and then you know come up with a reasonable working solution so the problem that we're going to work through

today is run-length encoding now it's fine if you've never heard of this this is an older lossless compression algorithm from the 60s 70s and it was a way to compress image files if you think of an image file is just a series of pixels that you can then compress a run if you will what it looks like is this so let's say I have a string of characters a a a b b c CC if i encode this what I should get is this for a 2 B 3 C that's the desired output so to

write a function that's going to do this compression we've got to do a few things first don't just jump into the problem think about what are the ambiguities here what are some of the edge cases or the gotchas that you might encounter we're trying to solve this for example what happens if we just throw another a on the end there well sometimes candidates think oh okay this just becomes 5 a but that's not the case because order matters and run length encoding what this should be is 1 a so this is going to start dictating

the kinds of data structures that you might think about a lot of candidates immediately jump to oh I need a hash implementation but if order matters yeah you can do it with a hash map but it's not optimal so then I might think okay well what about something like this 8 seedy well yeah it's as inefficient as it looks 1a 1b 1c 1d and that's okay like I said this is just how the algorithm works so now we're kind of teasing out the edges of this problem so the next thing that you want to think

about is well how am I going to actually solve it chances are this is a pretty straightforward iterative problem I'm gonna walk through each character in the string I'm gonna compare the character to the previous character if it's the same I'll increment some kind of counter and if it's different then I know I've hit the end of a run and I'm gonna add that to my output in this case I'll probably solve it in Java just because that's the language I'm comfortable in but it's up to you if you want to solve it in a

language that you're more comfortable and just let your interviewer know what you'd like to use so with that let's get started so let's get into implementation so now that we know that we're gonna take an iterative approach to solving this problem we're just gonna walk through a string array let's start by thinking about our inputs and outputs and how we're going to specify the function reminder right now I'll just preface that I'm going to write this in Java my function header because it's going to return a string and it's also going to take a string

so what I want to do first well we don't generally get very fussy about whether or not your inputs validated but for this case because we've got a simple input validation that we can do which is namely is our input and all let's just do a quick check here so if it's normal we return the empty string now we need to start initializing the variables that we're going to need to solve the problem because we're going to be walking through an array of characters we should probably convert this to a char array and also because

we need to track whatever the previous character was we should create a variable to store that and because we're going to need to keep a count of how many we've observed in the run we need a counter so now let's get into the algorithm well the first thing we want to do is see if the current is equal to the previous and if it is it's simple we just increment the counter now if it's different and it's not null then we know we've hit a switch in the run we've hit the end of a run

and we're going into a new run and that means that we want to append to whatever return string we're going to be building out and one thing that I notice I've done here is I have forgotten to actually initialize my string builder and that's okay like if you don't get everything the first time that's fine just notate here make it clear for the interviewer what you're doing and so I'm just gonna say all right I forgot this line I don't want to erase everything so let's initialize the string builder now it's going to be super

tempting to use really shorthand variables or to just say okay we know we're initializing a new string builder but I'm gonna really recommend that you don't do this just take a couple extra seconds and write out everything fully it'll be clear for you it'll be clear for the interviewer it'll also just result in overall clean code it's a good habit to get in the practice of so now that we have our string builder we can actually go in a pen to the previous chart and whatever the counter value is and then if these cases don't

Hold'em we've already switched well then we need to reset some of our variables here so we're going to say previous char is equal to the new char that we're iterating through and our counter equals 1 and that terminates our for loop but that means we've reached the end of our input array so we need to spit out the last of our compressed values so I will just make it very clear that I'm continuing my code over here and then finally I'll return the string and there's our implementation so we have our implementation but there are

a couple things that I want to point out that I was doing throughout the implementation process you probably noticed that I was talking out loud the whole time and that was very intentional it's not something I'm doing for this it's to let the interviewer know what I'm thinking and what I'm trying to accomplish with the code that I'm writing because sometimes it's not obvious as you're going through the process the other thing I did is you probably notice these somewhat trivial comments it might seem trivial but it's a great cue for both you and your

interviewer and it shows that you care about writing maintainable code because someone's eventually gonna look at it and try to understand what you were doing and that first person in this case is your interviewer and the other thing I was doing is you know I can't really ask questions in this context but you can ask questions to clarify with the interviewer and the interviewer may interrupt and ask some questions with you it's a dialogue that's fine if they cut you off don't worry they're just trying to get a little more information about what you're doing

or what your approach is so now that we have our implementation let's test it right this is the next phase of structured problem-solving I'll just move this here for clarity we know our input is a a b c c so how do we test this well I've got a couple of variables that I've been tracking this whole time I've got the previous char I've got my counter so let's walk through it at first the previous char is zero and my counter is zero and when I get into my for loop I'm here at the first

a so then I say okay well does this equal the previous char nope all right so I can skip that and I set the previous chart to a and the counter to one go back to the top of the for loop now I here I am at the second egg okay does this equal the previous charge yes it does so we increment the counter then we go back out and now we're here at B and so does this equal the previous chart nope we go into this elsif condition' and it's not zero so then we

say all right time to append to our stringbuilder so counter is currently two and a our previous chart but then we reset everything so this becomes B and this becomes 1 so we go back to the top of the for loop again and we've got C is C equal to the previous one nope so this becomes let's see where am i we append again and we've got one and B we reset this to C and one go back to the top of the for loop here we are incrementing n but actually don't we don't increment

my mistake we actually come out of this and then or we ask we have incremented sorry and then we get to the last append and we've got to C and this is what we return so now you've tested you know this kind of brute force solution with some pretty simple input what good practice is next is to start thinking about what kinds of input might break this well you know maybe some obvious choices would be like ABCD or just a long run of the same characters yeah and I'll leave that as an exercise for you

to try to see how you might break this and then we want to talk about optimizations it's really good to be familiar with how you compute time and space complexity let's go over time complexity real quickly so we know that in this case with our string input we are going to walk through every character in the input one one time so for example if our N equals 5 we're to execute this for loop five times so our time complexity is going to be O of n so just try and get familiar with that and have

that calculation ready for any kind of algorithm that you're going to be implementing and then the next things that you want to think about are there any optimizations that you could perform are there more optimal solutions that you can talk through there's actually a second part of this problem which is decoding this string and it has a bunch of interesting little tricks there and I very much recommend that you try it as an exercise we won't go through it today but that's something that you can try at home but I'll just leave you with practicing

this you know on a whiteboard so that you get familiar with the process of testing so now that you've actually had a chance to see what a coding question on the whiteboard really looks like I recommend that you take advantage of the many resources that are online whether it's leak code or career cup or the great book cracking the code interview and try some of these problems for yourself the other thing that I recommend is that you get a real white board and you time yourself so that you get an idea of what it's like

to do these types of questions to solve these questions in an environment that's going to be a lot more like the interview that you're actually going to do when you practice on a white board you'll have the opportunity to get good at some of these principles that we're looking for whether it's CS fundamentals your data structures and I'll go s your structured approach to problem-solving and writing logical and maintainable code which is very different on a white board than it is in an IDE with that I wish you best of luck see you soon [Music]

you [Music]