Python Interview with an Amazon engineer

Watch someone solve the substring concatenation problem in an interview with an Amazon engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Substring Concatenation

Interview question

1) Count the amount of words in a string. 2) You are given a string s and an array of strings words of the same length. Return all starting indices of substring(s) in s that is a concatenation of each word in words exactly once, in any order, and without any intervening characters.

Interview Feedback

Feedback about Nimble Panda (the interviewee)

Advance this person to the next round?

How were their technical skills?

3/4

How was their problem solving ability?

3/4

What about their communication ability?

4/4

This was a solid interview performance. You are really good at communicating your problem solving thought process. You identified edge cases and asked great clarifying questions. One way you can improve is to break down a problem into bite-size chunks that are easier to solve. You should feel empowered to suggest simplifying assumptions for your first implementation.

Feedback about Sizzling Shadow (the interviewer)

Would you want to work with this person?

How excited would you be to work with them?

4/4

How good were the questions?

4/4

How helpful was your interviewer in guiding you to the solution(s)?

4/4

I thought the interviewer communicated his thoughts well and also provided good insights into the process during the Q&A portion at the tail end of the interview. In addition, the interviewer kept a positive tone and made the process feel less nerve-wracking, which allowed me to focus better on coding instead of being anxious.

Interview Transcript

Sizzling Shadow: Can you hear me well?

Nimble Panda: Yes, I can. Can you hear me okay?

Sizzling Shadow: Yeah, perfectly. So I'll start with a quick introduction. Although it's anonymous, so I'll share my background. So I worked at Amazon for seven years as a software engineer, and then software engineering manager and I moved to a startup at the beginning of this year to build automation for filing requirements, that companies, so the government, and so with that, I'll pass it over to you to give me a quick introduction about your background.

Nimble Panda: Okay, so I actually worked as a data engineer for about three years now. The reason I'm doing this is trying to brush up my software engineering skills, because I am doing interviews where they do sort of ask some SE questions. I don't feel like I'm technically as strong as say a pure SE is, but I've been trying at least to practice. So yep, I'm currently interviewing for my next role.

Sizzling Shadow: Great. Sounds good. With that, I think we'll kick off the coding question, if that works for you?

Nimble Panda: Okay, yep.

Sizzling Shadow: So what language would you like to use to code it?

Nimble Panda: I like to use Python, actually.

Sizzling Shadow: Okay, let's switch the IDE to Python. And is it your first interview on interviewing.io?

Nimble Panda: So yeah, it is.

Sizzling Shadow: Okay, great. Well, you'll notice that there's actually an interpreter. So if you run the code, you will be able to see the output on the right side. You should be able to see my cursor, and I can see yours as well, so it'll make collaborating easier. So let's start with a very, like a warm up question. So I'd like you to write a function that given a string will return the number of words in the string, and I pasted the description right here.

Nimble Panda: Okay, cool. So I can just get started?

Sizzling Shadow: Yeah, go for it.

Nimble Panda: All right. Cool. So, um, I guess just in my thought, so there's, we have a string of words. Like just saying the string of words, there's going to be... you can probably go by the spaces, there's always going to be s minus one spaces. Right?

Sizzling Shadow: Yes, that's a reasonable assumption.

Nimble Panda: Um, then I guess we have to watch out for an empty string. And yeah, if this is for a warm up, hopefully, it won't be too complex in terms of the code. So I'm gonna probably go ahead and start from here.

Sizzling Shadow: That's a reasonable assumption.

Nimble Panda: And let's say, I'm pretty sure there's a built in function, right? I guess one thing that could happen is, you know, if there's multiples consecutive spaces, or whitespace till the end, should I account for that? Or are we assuming it's pretty clean?

Sizzling Shadow: Let's assume it's pretty clean, but never do the...

Nimble Panda: Okay, cool. So let's run this real quick. I guess this is fairly straightforward. So it looks good. On here, let's say we took something like string of words... So we don't return zero. No, say zero string count spaces, it'll count two spaces. So it's plus one. So its two spaces and three words. Yeah, I think that makes sense.

Sizzling Shadow: Looks pretty good. Should we run it on an example?

Nimble Panda: Yeah, sure. Um, can I just use print or?

Sizzling Shadow: Yep. You can see you have sample code at the top that shows you how I mean to run stuff in the IDE.

Nimble Panda: Oh, okay. Um, so, yes.

Sizzling Shadow: Nice. Well, that looks pretty good. And I'll ask you a question about this algorithm, can you determine what the time complexity for it is?

Nimble Panda: Um, I believe it should still be O(n), because it's counting through a string. It's an iterating through it one by one. So it has to iterate through the whole string, so O(n)?

Sizzling Shadow: Yeah, makes perfect sense. So thanks a lot for going through this. We'll move to my next question. Does that work for you?

Nimble Panda: Oh, yeah, yeah. So this is a word combinations problem. And I'll paste the description right here. Give you a minute to read through it. And let me know if you have any questions.

Sizzling Shadow: Alright, interesting. So in your example, rock star, rock star rock with an S rocks and tar. Mm hmm. I see a duplicate star. So should I be counting two rock and star's?

Nimble Panda: That's a great question. Let's say yes. I think that's reasonable.

Sizzling Shadow: Okay. Hmm. All right. Let me brainstorm real quick. So naively, maybe it's a naive solution, maybe would be we iterate through it. So we hit rock star. And then we have to check. Every time through the list they'll give us O(n^2) method to it. Is there a better way? So let's see. Let's start with I guess, going for an naive solution, if it is, if there is a better and then we'll see if I get any insights on if there's a different way to implement it. So an array through list of words, and I see a potentially large so I'm guessing there might be a better way of doing this. For each word, iterate through the list again, and identify the word. And let's see if there's rock star rock star. Play go all the way back. How would I compare the word if the word is part of it. Might even add some more time complexity to it. Rock rocks. Now to keep track of the part, and I guess a question about two or more words, well, that makes it even more tricky with a super high complexity. So I guess, how would I even map two words to a single word? Because, right, there definitely should be a different way to use because I'm thinking, say a word is... Let's say a word is like superhighway, which is made out of three words. How do I know to stop checking a through the list over and over? Without maybe I guess specifying the length of...?

Nimble Panda: So I think that's a reasonable question. How about we start with maybe two words, right? And then we can think about how we might solve for any length. Right for the combination? Does that sound good?

Sizzling Shadow: Sounds good. All right. So I think we have a good idea of what's going on here. So let's call this... so first thing I do is iterate through the list of words and then we'll probably need a counter. Okay, our first check for the length. And we're saying here, we're doing a comparison, right? Is this... is there a starts with function for strings? I'm going to assume yes, for now, if not, go I'll go back and code for it.

Nimble Panda: That sounds right. You know, I'll do a quick look online, see if that's the right function. I'll let you know.

Sizzling Shadow: Cool, thanks. I appreciate it. Looks like I'll have to keep track of two things just for, so that I don't have to keep unpacking and repacking. Potential string price equals s. Then too, alright, so let's say it's rock and star and we covered rock. And then we want to go along with this. So I think one way would be for our word we want to adjust it. Then we have to keep track of potential string. So if we have a current string and it becomes shorter, so say rock star, and we found rock then if we, if we drop the rock part, and then try to match the next part? That's a potential as well to... what would be the time without adding too much complexity? So one way is, so we start current word here. So we found rocks and found rock and then I want to trim off the rock part, um, guess one way is to slice. Okay, and this might see, hopefully we'll handle two, then we would... be able to append our final list, right? All right. So hopefully, if we, this is not very... So I can't do this right away, this check because it might match. So I'm thinking now if you have rockstar, obviously we want to want to distinguish between matching one whole word, but if we're trimming down and we have star leftover since we found rock and star matches star, then...

Nimble Panda: Yep, I'm tracking. Yeah, that makes sense.

Sizzling Shadow: Okay, but the way we're doing it, I guess it won't account for this, this duplicate. Or now we can maybe go back and see what we can do about that. So this is just the length of board. So I think that would handle if it been the same string for checking. So here we should do a check. So I'm thinking if we have a duplicate, then we can keep this and try it again or we can track it separately. I'm guessing that the best way, I'm just thinking the best way to handle duplicates is sort of maybe keep a separate count and double check if we've touched that. It would add space complexity but it will help if say we have multiple words, multiple substrings of it.

Nimble Panda: Yeah, we can revisit that later. Just like the multiple word breakdown. Okay, although it looks like your algorithm would work with multiple words, like superhighway would actually be broken down into three words right?

Sizzling Shadow: Um, let me see. It would if... the only catches was thinking for multiple if it's superhighway, right? If way and high positions were switched, it wouldn't be able to catch that. Qhich I didn't like my method as much in the beginning. But, given this order and ignoring that duplicate star, let's... actually even append it to... takes it out of this loop. So lock in my code real quick. Take this down here. For now I'm going to remove this. Alright, so for word in our list, I start with rockstar I set the current to rock star, for string in our list, if the length is the same, they're going to be your same rock star matches rockstar continues because that's not actually valid. If then we move to rock and it starts with rock. So we're gonna append rock to our potential composite list and then... So nom not for this. So 0123 and four onwards, leave us with star as our current. We move on to star. So, rock star is larger than star so this condition would hold. If current starts with star potential composite dot append. So like I can already see something happening down here, but let's finish walking through this. If current equals s, so star matches star, then we found one. We don't want to break because rockstar, rock star and rocks tar. So let's see how we can fix our logic for that. So, first of all, we don't want to exit the loop early. Let's set it again. So alright, so we restarted to rockstar. And on this one is going to check it's going to be okay. Alright, so one glaring thing is my method only definitely works if the substrings happen after the word. So is that true?

Nimble Panda: Actually, yeah, that's a good catch. Suggestion. How about we track the things you've identified that need to be improved for the function to cover all the different edge cases. And like below this as comments, and once we do that, let's try and see if we can run it on an example. Does that work for you? And then we can go to adding support for the edge cases you've identified.

Sizzling Shadow: Okay, sounds good. So give me one quick moment. So if we hit rock stars, I do... would start again at rock star would not find an s. So that fit, so for rock star, rock rock rock star star. Superhighway, high, rock star. Then I made it into an s. Okay, so I mean, we can try running it on something that's in order. But I think, is that okay with you for now? Or should I just go ahead and try to make at least work out of order?

Nimble Panda: Let's try as it is right now. And just note that working with the order is one of those things we can improve. Does that sound good?

Sizzling Shadow: Sounds good.

Nimble Panda: Right. I think you've identified order. You've identified finding multiple examples of like duplicates. We talked about multiple keywords, but I think that's supported. Yeah, okay. Yeah, that's pretty good. And also I checked starts with is a function and it's actually with all lowercase. This is how it's spelled. I believe that will work.

Sizzling Shadow: Interesting. Cool. I guess Python doesn't like camel cases in its base code. All right, right.

Nimble Panda: Snake case, right. That's why it's called Python.

Sizzling Shadow: I'm going to go ahead and rearrange this list real quick. There are a lot of conditions because I have a feeling when we hit superhighway, I'll be able to catch super highway, but it'll forget about super, so it won't be able to catch this multiple actually. So, um, we can actually test two versions of this.

Nimble Panda: Sounds good.

Sizzling Shadow: I would like to try and highway. Other function composite works. Let's give this a whirl. Did not error out, that's one good thing. Some spaces share visual clarity. So, first of all, it's not giving our list of lists that we like, but rock star, so I'm not resetting potential composite, so that's probably because of that. So that's one thing. Rock Star rock star. Yeah, I'm just appending the same thing over and over with a final so look at this one. Rock Star, rock star, rock star. Super, super high. I can't scroll to the right?

Nimble Panda: What are you trying to look at?

Sizzling Shadow: It's wrapping, that's why I thought there was more things to the right of output.

Nimble Panda: Okay, yeah.

Sizzling Shadow: Super highway and high way. Superhighway highway. So yeah, this outputs kind of jumbled for me right now. So let's clean that up real quick. Let's at least get that better looking. So potential composite, where should I reset this? Potential composite? So it should be sure. Why do I get this weird long one still. In highway, I'm missing the super. So debugging this real quick, rock star rock super highway. Where does this happen? So rock star, rock star, doesn't have both as we see. So it goes to rock star rocks tar. Rock Star gets rock star and rock but somehow it gets super and highway.

Nimble Panda: Another preset thing. So append for this string. Should the question... so are you familiar with the difference between append and extend?

Sizzling Shadow: I am. Yeah. Should one be used like in either of those places instead of the other. I don't think so. Right? Because append is like adding an element to a list?

Nimble Panda: Yeah, yeah, it looks right. So this is definitely an append. This is a string of strings. So this is also should be append, right? Let me... give me one moment. I know, I'm probably spending too much time on this one problem. But here it goes. Rock Star rock star. I'm guessing it does error out on rock stars. So this should technically make it an int s and it should not match ever again. So I'll keep in mind what you said as well. When none of this, never happens again. Am I not clearing something that I should be? Sorry, I'm genuinely confused why?

Sizzling Shadow: A little bit. Yeah, same here. Actually, I'm stumped. Maybe printing what the, you know, W and S are in your loops will help us follow the algorithm as it's going through. Does that make sense?

Nimble Panda: Okay. Yeah, if you don't mind, I know sometimes people...

Sizzling Shadow: Go for it.

Nimble Panda: Alright, cool. So let's try. Guess if we really wanted to just run one. See if we can find those. So what happens here?

Sizzling Shadow: I think I have the start of intuition for what's going on. The rock stars are repeating, right?

Nimble Panda: Sorry?

Sizzling Shadow: Just saying, so I think I have an intuition for what might be going on.

Nimble Panda: Sorry, I'm gonna take a guess before, take a stab, before you go reveal to me. I'm guessing that because of this condition here, there's... or perhaps this one here where they don't match. Along the way potential composite doesn't get cleared. Because it didn't find a match. So this never triggers. So potential composite stays populated. So we get this weird behavior of no match, but potential composite still filled out. Was that what you were gonna say?

Sizzling Shadow: That's, yeah, that's right. That's where where I was going. I think you're correct that there's a reset, that doesn't happen for some reason.

Nimble Panda: Okay. Cool. So this reset starts with it... if it finishes the loop, I guess. So that makes. Let's see, if it runs through, and it runs through everywhere possible. There's no match, then yeah, I think it should reset here. That's one thing we didn't reset properly. And we don't want to reset our composites because that's just our master list. Curr does get reset here as well.

Sizzling Shadow: Okay, I think you got like, at least what you've just fixed is what I was thinking of, the reset for the potential composite.

Nimble Panda: Okay, cool. Should we give it a whirl?

Sizzling Shadow: Yeah, let's do it. Maybe without all this green? Yes. Well, whoops. Um, well, that looks pretty good.

Nimble Panda: Almost. The second thing that I was hoping would be accounted for. Um, yeah.

Sizzling Shadow: You got the breakdowns into two words, at least all of them.

Nimble Panda: Oh, yeah, that's true. Because we have a highway here. So. Yeah, cool. Um, how are we on time? I'm happy to try to continue on.

Sizzling Shadow: Yeah, I mean, this is a pretty good breakpoint. Usually, like, it's around 45 minutes. Towards the end, I like to turn it around and have the candidates ask questions to me, the interviewer. Right, so we could roleplay it a little bit. I'm curious to know what questions you might ask.

Nimble Panda: Okay. I'm just going to ask a quick, just outside meta question is basically on I think you mentioned yet a lot of experience as an engineer. For me, obviously, my reason for using interview.io is because it's good practice. I guess, what's the motivation, because I'm guessing you guys have plenty of experience, I would at least think at first in interviewing people. But what's basically your motivations for using interview.io?

Sizzling Shadow: Oh, good question. So on the interviewer side, it's good practice in general. And it's like, there's an aspect of it, which is about giving back, like making sure that the, you know, everyone in the community gets an opportunity to practice interviews so that they eventually get like, the roles that they're looking for. So that's why I do this with interviewing.io. I've also recently, when making my switch to a startup, I went back to the interviewing.io to take interviews myself, and this is because the day to day work is different from the interview. The interview is really an exercise that you prepare. It's like an imperfect way to quickly evaluate people's skills and familiarity with data structures, algorithms, coding in general. But since it's a bit contrived, right, like, when you work day to day, you rarely write algorithms from scratch, usually, you know, can Google for things, look at Stack Overflow, you also work with your IDE, your write tests and check whether your tests pass or not. And that's how, how we code. And so interview questions are a little bit different. And coming to terms with that, and accepting that you have to practice to get back in shape for an actual interview is, I think, true for engineers, even people who spent our days, you know, working as engineers, probably will need to do some interview practice before going through an interview.

Nimble Panda: I see, yeah, that's a great answer actually. Um, so maybe going back into what I would probably ask during my interviews, I guess most of my questions are relevant to day to day at X company. So for you like what, say, at that point, like what I've been working on, what are some maybe pain points? What's going on, or some needs that the company is trying to fill?

Sizzling Shadow: Yeah, that makes sense. What I can share is like some other questions I've heard and things that usually makes sense. So an interview goes both ways. Oftentimes, you also interview the team that you're going to join. So having an understanding of their, you know, day to day practice, if they use a version of, you know, Scrum or Kanban. And understanding of the challenges, because, as you said, like that someone's working on. And one way I've heard it framed that question that actually works really well is, what's a project that you're looking forward to in the near future? And even more specifically, I've heard someone ask, what's the tech debt project that you're looking forward to? And this is a good way to get an understanding for one, is there interesting work going on? And two? Is the team on top of there, the quality of the software, right, like, understanding whether there's a lot of operational load being working on fixing bugs, right, or urgent issues, versus new Greenfield work?

Nimble Panda: I see that it's very interesting. I never thought about it that way. Yeah, I guess, for your experience, how much do you value someone who's demonstrates a willingness to learn versus the actual skills like, well, how would you weigh on an interview like 80% being able to get the right the right solution? 90%?

Sizzling Shadow: Good question. I'd say what matters most is the ability to write code, right? So this is like a binary test, pass or fail. Like if you can write code, we then look at communication, problem solving, dealing with ambiguity. And the, I think the depth and fluency will determine the level right, like, for the role you might enter might be an entry position, or it might be like a more senior position. But that's what comes into an interview and testing for the willingness to learn, the ability to, you know, take feedback and act on it. That's actually key. Because at any level of experience as an engineer, like you just keep learning every few years, few months, the landscape changes so much that the part of the skill set is being ready to, you know, unlearn things, and learn new things and adapt to to field.

Nimble Panda: Yeah, that's a pretty great answer. I mean, to the common, you know, like, we always keep learning. But I guess, now that you mentioned it, they probably, you know, set through separate, you know, that aspect to behavioral interviews, and the technical line is a bit more binary. I would assume I know...

Sizzling Shadow: Yes and no. In my experience, the coding questions are, like, have a binary component, again, it's "Can you write the code or not", right? And once you pass that bar, really, it's all about, you know, probing for those softer skills around development. Knowledge of, you know, data structures and algorithms for sure. But really also, you know, how do you react to maybe a bug you see in the function and how do you think about all the edge cases, can you break down a big problem into smaller chunks where you iterate to work towards a solution. A lot of those things are what interviewers look for when doing the technical interview.

Nimble Panda: I see I see. Okay, um, those are some good points, I think I do definitely need to work on how to break down these problems into smaller ones.

Sizzling Shadow: One thing I'll share is like you did pretty well, I think like it since I tend to ask, you know, similar questions over and over again, like, you're one of the few people who have arrived at the working solution in this coding question. It's not, it's not a straightforward one. So like, that's another, you know, leveling thing to be aware of. The warm up question was really the binary, Can you code or not? And the second one was really, you know, it has drawers so you can go deeper and deeper in terms of depth and complexity. We're going to get into solutions already, you know, passing a bar.

Nimble Panda: I see. I see. Okay, cool. Because, I mean, as an interviewee, I'm always like, one, we know, we don't lose anything by keeping on trying, but it's always like that dreaded moment where you don't actually know all the answers. But, um, yeah, being able to hear I guess, feedback and be we're breaking down in my head a bit more definitely does help. I think that's all the questions I had, for now.

Sizzling Shadow: Make sense. Sounds good. I mean, this could be a good break point for the for the interview. So one last thing I might ask you, this is something that probably would have come up is what's the time complexity for the algorithm you wrote?

Nimble Panda: Okay, so let's take a look. So we already have two for loops through our one list. So that's already going to be O(n^2). And this is going to be additive. Also additive. So it's O(n^2).

Sizzling Shadow: Yeah, that's right. And you're asked if there were like, ways to make it, you know, more more efficient. And so there definitely are. So this is like, it's a fun, interesting question that, again, has a lot of depth and can go into optimization. Recursion can also be helpful in some cases. So...

Nimble Panda: I see, so is this actually a dynamic programming problem?

Sizzling Shadow: I'm actually not familiar with dynamic programming as a category of problems.

Nimble Panda: I see, I guess, basically recursion, right. Since, let's see... Hmm, interesting.

Sizzling Shadow: Yeah. Because essentially, when you finally breakdown, like the next step is trying to find a breakdown for the subset of the word that you've identified. So that's one way to think about it. But like, another thing that can help is sorting, sorting by length. So you only look at stuff that is relevant. That's another way to shorten the actual search. You had great intuition from the get go thinking about the length of the words. So.

Nimble Panda: Actually, I probably missed them. I was just trying to think of what you just said, if we did sort, and then sort of maybe implement some sort of recursion at a high level. I'll have to think about this. I obviously wasn't able to come up with that on the fly, but cool. I will keep that in mind.

Sizzling Shadow: Okay, cool. Well, it was a pleasure doing this interview with you. And so best of luck with the next one.

Nimble Panda: Yeah, thanks a lot. This is a this is definitely at least for me, very valuable practice. And I appreciate the feedback as well.

Sizzling Shadow: Great, good to hear. Have a good rest of the day.

Nimble Panda: Cool, awesome. You as well. Take care.

Sizzling Shadow: Bye.

Nimble Panda: Bye.