SDE Interview Coding Example

hello uh my name is seychelles philippa i work as a software developer within uh kindle the books so the kindle organization amazon um a website called kindle direct publishing essentially for independent authors to publish their work with with amazon so someone like myself who's not necessarily an author by trade doesn't want to go through a publisher it can go and upload their book there and then publish with us and i'm here to help you with the interview section specifically the coding part hopefully provide you with some some tips as to things we look for things

to avoid um i'll be doing that just through the an example coding exercise so i'll be essentially pasting in some code walking through um kind of some of the things we look for when uh when writing the code and before and after and things to avoid i'll start with the tool you'll be using for your interview it's called life code i have that shared on my screen essentially it's just a text editor you don't have the ability to compile or run code but you could choose it's just a language for for highlighting for syntax highlighting

we'll go to java um and your interviewer will just paste a question for you so i'll start pasting the question and you'll be given some time about 25 minutes or so is a typical time so recommend the first thing you do is obviously read through the question but but take take your time to eat the questions take at least two to three minutes um in this case i'll just read through it real quick it looks like when we provide a time series it's a two dimensional array like it has ones and zeros and those represent

robot positions one is where a robot exists zero it doesn't and we're asked to essentially return true or false for whether a time series is valid or not this condition we see here is robots can only travel up to one index further than their previous than the position one step before and so in this first example this first robot moved one to the left the second robot moved one to the right so it is valid the second example the first robot essentially stayed the same position um and whereas the second robot moved two positions to

the left so it's not valid to return false um so at a high level it seems like a fairly fairly simple solution the first thing i recommend doing here is just kind of understanding asking clarifying questions to help understand the problem and uh there are a couple of things you can ask clarifying questions about the first one is just a data input data format kind of um what what the constraints are for for the data fields that we're getting so one one would be for example like okay are the array lengths the same um and

they are in this case um two is is the number of robots going to be uh like negative or zero and we'll go with it could be zero or positive integer for here uh three is is there a minimum length for these um for these arrays provided it's going to be uh one uh same question for about kind of kind of are the the arrays guaranteed to have the same length or that or the time series is going to have the same length and the answer to that is yes and so that'll get us to

essentially an understand understanding as to what the data coming in is there's also a second aspect of clarifying questions just around kind of some of the use cases for the problem and kind of if we if we don't ask any additional questions we might end up with a solution uh or it might seem like a really simple problem uh in which all we need to do is just walk through an array and then for the deciding to check positions on the next array if it's to see if they're one or or not and so we

may end up with a solution like this in which again just walk through when we find a one we just check the row before or thereafter in this case before we check three positions negative one um the same position above it and plus one if you find one anywhere we return false and this is this won't work it has a bunch of issues uh but the first one is just out of bounds uh starting from row zero negative one here for both rows and columns columns also starting with zero but this will throw out of

bounds and zero out of bounds um we're not checking number of us in in any way even though it's it's provided and we also uh we didn't consider cases such as um something like this in which um so these two robots have valid positions now um but this robot doesn't um and so robots we haven't asked clarifying questions around some of the use cases for the problem so one would be can robots essentially collide or can you occupy the same slot the answer is no um and two kind of we can ask question around the

number of robots specified or could we be past the parameters as number robots and and what is that used for or is there a guarantee as to how many ones there are in every row the answer to that is no we will be provided number robots but we need to essentially check that we have the same number of us whenever you're ourselves because we just passed in like a bunch of random zeros and ones in this case um and so uh again asking clarifying questions one of the main things we look for in this case

should have clarified some of the the use cases here um but now we have and now we have a better understanding so we have decision to make essentially do we want to um write an optimal solution to start or do we want to instead write a solution that works and then optimize it later and we we advise using the the second method more often the first because it's better to have a working solution because then we have that data point uh and then correct that later um and so in this case we'll i'll just paste

in a working solution you can walk through it uh it's it's fairly simple even though it's a lot of code um so we need to recognize that we need to do two things we need to one count the number of robots again and we need two to check that they're valid but also that they don't occupy the same slot so that they did it they don't um essentially collide in any way and so for this solution as you'll notice it's broken down into the same initial checks counting the number of robots per row checking against

the number of robots if we don't match just return false the second step is the kind of the bulk of the problem which is okay now and we might choose to do this a bunch of different ways we can choose to modify the grid in place or um you know check a row against the one after it and then check the other way around as well or the way we're doing right now is we just remap the indices of the robots and then we just compare them against each other and so we create those um

arrays that it was just responsible for storing the positions of the robots and uh we essentially get this for the first row because we want to start from our one career to the row before um before we roll we get the the indices um and we'll check if it's valid against indices of the previous row if it's not returned false otherwise you just update to check against uh it's actually the next row so we update the current one to check against next one is just checked on the next iteration of the loop uh it falls

okay we just return true after i mean you'll notice some of the syntax isn't perfect and we don't expect perfect syntax because you don't have the ability to um to compile or run code and so it's more about kind of the the logical approach you take to solve the problem um although we do recommend having your code be as readable as possible um not just not in terms of syntax but just in terms of kind of having distinct functions being responsible for doing uh different things um not having a lot of repetitive code um kind

of making sure to add comments if there's some some code that's complex that someone may may not be able to read very easily so we we do watch for that data point specifically just not so much that syntax aspect of it um so we have two output functions here just one that creates this indices for us just finds ones in a row essentially and just updates this array and returns it at the end the other one is just checks um two array positions essentially two two indices uh into respective arrays for where the positions are

and you'll notice i'm using a helper function here um just because you're comparing three values uh you know negative one zero and one are fine in this case um and that's typically okay to do is use library functions as long as you just mention it to your interviewer um there are certain cases in which library function just you know solves a problem for you which is clearly not the date point we're looking for so in that case they'll maybe ask you to implement that developer function but as in general it's fine to use library functions

just mention that to your to an interviewer so um here we ended up with a solution that is um uh it's working um but typically we recommend if you have the time to take some time to look at the code and test it on your own um and test it you can't run tests obviously but writing a test case that might break it and walking through the the code line by line is typically helpful to find bugs because otherwise um you know you won't be able to detect those bugs that might be uh fairly fairly

obvious a lot of times just typos or things like that um so recommend if you have the time again take uh take a little bit of time write a case that's not a happy case uh to test your code uh try try to break it um you'll also be asked about time and space complexity in this case uh time complexity you'll notice is n squared but it's 2 n squared because we're looking about two arrays twice uh n squared or n times them but both are fine in this case length time width um but the

space complexity is also um oven because we're using these uh arrays here and um it could be that number indices just the length of the uh the grid so um you'll also be asked what the optimal uh time space complexity are in this case it's um we can improve on both time and space complexity and in time complexity n squared there's like we still need n squared it's just we don't need to have to set like two separate checks so so small low can be improved but in space complexity you can actually run this in

in constant uh time and so kind of making sure you have enough time saved at the end if you choose to write a non-optimal solution is usually a good idea because you'll get time you'll get the chance to improve on that on that solution so in this case we will skip forward to the optimal version of the solution just to to help walk through that real quick and you'll notice for this it's kind of very similar um in some in certain aspects and so we're still counting robots except we're doing this as part of walking

through the grid one time um uh right here but the the main aspect of it is is kind of moving or not using this index this array for positions anymore because um we recognize that if you just move left to right um a robot is forced to move into the the earliest available position essentially and so keeping track of where the latest one is that we've used so far and kind of uh preventing robot from moving to that index but having it move um after it basically is is guaranteed to give us an answer we

don't need to store in a no event array um so in this case uh you'll notice last used index gets updated to where the position that we find the latest robot if we either don't find robots so there are there's zeros in the available slots or they're ones but they're used um then we just return false uh otherwise walk through the end we count the number of robots we return true and in this case you know time complexity is n squared still but we don't have to do you know separate for loops for camera robots

versus solving the problem um the space complexity is constant because we don't declare any arrays or anything like that here um so at a high level kind of i know this is a quick walkthrough this is how we'd solve a problem but specifically what you can expect from a coding interview is you'll ask you'll be asked this problem is kind of similar but it could use um kind of some of the standard algorithms things like you know tree traversal uh greedy algorithms like dynamic programming uh sorting um and so it's likely to have those kind

of aspects in the problem uh it's likely that you'll have to use some data structures as well some of the standard ones like um you know trees heaps uh sets lists uh maps arrays um so so recommend kind of having more like a breadth of understanding of data structures more so than being a super in depth um on on one of them um and the the biggest part i think is is to kind of maybe uh time yourself taking some of those exercises so that because you have you're gonna have like 25 minutes for the

coding question um and you'll want to probably start with a non-optimal solution and optimize later um and so just timing yourself we find helps a lot because time tends to go by quickly when you're when you're writing code um overall as long as you uh one just keep track of the time take time to read the question ask the right clarifying questions around not just data input but also use cases as you code kind of pay attention to the readability of the code not necessarily syntax but just you know how easy it is to follow

along and not have a lot of duplicate code use the appropriate data structures um test your code if possible just by walking through to to kind of confirm some assumptions that they make and uh yeah make sure you understand the the time and space complexity of your of your solution when they are able to reason through trade-offs in both time and space as well as the the optimal solution um i hope that that helps we're we hope you interview with us and we we hope to see you working in amazon thank you you