We helped write the sequel to "Cracking the Coding Interview". Read 9 chapters for free
Valid Word Abbreviation
Watch someone solve the valid word abbreviation problem in an interview with a FAANG engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.
Interview Summary
Problem type
Valid Word Abbreviation
Interview question
1) Given a pattern such as “i18n” , check if input string “internationalization” matches it. “f6k” should match “facebook”, but not “focus”. 2) Given an m x n integers matrix, return the length of the longest increasing path in the matrix. From each cell, you can either move in four directions: left, right, up, or down Input: [[9,9,4], [6,6,8], [2,1,1]] Output: 4 Explanation: The longest increasing path is [1, 2, 6, 9].
Interview Feedback
Feedback about Secret Zebra (the interviewee)
Advance this person to the next round?
NoHow were their technical skills?
3/4
How was their problem solving ability?
2/4
What about their communication ability?
4/4
Problem solving - Asked good clarifying questions, disambiguated the problem: key signal for senior engineer - Came up with the optimal solution and runtime analysis for the first problem immediately - Had trouble with finding the optimal solution for the second one but had the right intuition Coding - Speed was good on the first problem, took a bit of time on BFS - Split up the parts into modular chunks (isNum, getNeighbors): key signal for senior engineer - Did not have time to finish the second problem Communication - Clearly explained the solution before starting on the coding: another key signal for senior - Talked throughout writing code, explaining their thought process Testing - Came up with good tests and ran through the code with comments - Good timing on the tests, didn't waste too much time - Missed on bug while running through the code though Things to watch out for ------------------------ - Practice BFS, graph problems - Write out the abstractions first if you're low on time so that you can focus on the key bits
Feedback about Continuous Hedgehog (the interviewer)
Would you want to work with this person?
YesHow 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
Gave really helpful concise feedback with 2 key things to focus on. Thank you!
Interview Transcript
Continuous Hedgehog: So we're doing a coding interview today, right?
Secret Zebra: Yes, and I'm not actually applying to fang companies, but I'm applying to mid size startups and I'm sure some of the hiring will be interviews will be somewhat similar and I'm targeting senior software engineer type positions.
Continuous Hedgehog: Okay, got it. Yeah, that's good to know. So I can calibrate feedback. Okay. Have you used this platform before? Are you familiar with the UI?
Secret Zebra: Yes.
Continuous Hedgehog: Okay, perfect. Okay, so we've got an r. I guess we could do coding questions for like 40 minutes and then do feedback for the last 20. Does that sound good?
Secret Zebra: That sounds perfect.
Continuous Hedgehog: Okay, awesome. I'm going to go ahead and paste a question in. Can you choose the language?
Secret Zebra: Yes, I'll go ahead. Javascript. There we go.
Continuous Hedgehog: Awesome. Can you see the question? Yes, this is title. There you go. Much better.
Secret Zebra: Print I 18 n matches it. F six k to match Facebook, but not focus. Yes. Okay. Even a pattern such as. All right, in this pattern that I'm seeing here, this first example, it's a letter, and then the number is representing the number of letters in between. It could be any letters in between and then the next letter in. Yes. Does that sound right? Will all of the inputs like this be of the format? One character, a number, then another character? Or might there be a series of them like this?
Continuous Hedgehog: Yeah, that's a good question. So they could be of any pattern. So there could be a series that could be just a number or just alphabets. It could be anything.
Secret Zebra: Cool, awesome. I assume with that we could have multiple characters next to each other. So for example, we might have in 17 n could match the above, is that correct? Yes. And then what about multiple numbers? Because that won't really work with using digits. How we have, will there ever be two numbers next to each other?
Continuous Hedgehog: Right? I mean, there are two numbers here, right?
Secret Zebra: One and, well, two digits. Sorry. I guess just based on the data structure, I think I'm answering my own question. There can't be like 1718. That would be 1718, yes, exactly. Okay cool, awesome. And I assume an empty string would not match anything except for another empty string, right?
Continuous Hedgehog: Yes.
Secret Zebra: All right, not match Facebook and the matching string. So I'm going to start showing an interface here which would look like does match and it's going to be pattern, let's say. And input will, input will never have any of the pattern type things in it. Right? Like input will never have, yeah, it.
Continuous Hedgehog: Won't have numbers in it.
Secret Zebra: Yeah, exactly. Okay cool. All right, let's see if there's anything else. I wanted to ask any edge cases if we get null for either of these, do we want like an error or do we want just to return null, you think?
Continuous Hedgehog: Yeah, just create that as like an empty string. That's what I'm.
Secret Zebra: Empty. All right. Cool. And are we thinking, do we want to keep this modular for something else? I'm trying to think what that could be like. For example, will we ever, you think, get an array of inputs where we won't want to match them one by one?
Continuous Hedgehog: I think it's fine for now. I think just assume that you call this with a unique pattern and a unique input so you don't have to worry about that.
Secret Zebra: Cool. All right, well I'm going to dive into a little bit of a strategy here. Does that sound good?
Continuous Hedgehog: Yes.
Secret Zebra: All right, so what I'm thinking is that we have some letters and numbers in a sequence, right? And so I think first what we are doing is we want to parse letter or number. And so this would be, in the above case this would be I or 18 depending on which one we're at. So we're not going to parse one. Eight. If there's digits we're going to string them together.
Continuous Hedgehog: Got it.
Secret Zebra: Yes.
Continuous Hedgehog: Nice. All right, makes sense to me.
Secret Zebra: Yeah, I think I'm ready to code that, unless you have any clarifying questions there.
Continuous Hedgehog: What about the space complexity?
Secret Zebra: Yeah, we're not creating any new streams.
Continuous Hedgehog: All right, coded up.
Secret Zebra: That's okay.
Continuous Hedgehog: I think you're missing. Maybe it's this one that's missing closing print and that's messing everything up.
Secret Zebra: I see.
Continuous Hedgehog: Maybe it's that.
Secret Zebra: So let's go through it with. Actually, let's just use the example we have here. I'm going to use Facebook because it's a little shorter.
Continuous Hedgehog: Okay.
Secret Zebra: So we're going to cancel out. And then down here we're going to check PI does not equal PI link at that point because it's two. And so we're going to return false.
Continuous Hedgehog: Got it.
Secret Zebra: Focus and Facebook work with this example.
Continuous Hedgehog: Nice. Okay. Yeah. Let's move on to the next question.
Secret Zebra: Okay, great.
Continuous Hedgehog: We can go over any questions you might have.
Secret Zebra: Yeah, I think I understand that problem. So let's see. Can I assume that if m or n is zero, then the answer is just zero, right?
Continuous Hedgehog: Yes.
Secret Zebra: I think I would handle it the same way. But might we have negatives?
Continuous Hedgehog: Yeah, I think you can, but maybe, I don't know if it makes it easier. Let's assume not.
Secret Zebra: I don't think it will make it easier.
Continuous Hedgehog: Okay.
Secret Zebra: Breath verse search and see how many levels deep that can go. But that seems pretty wasteful. So I think what would be a more reasonable approach?
Continuous Hedgehog: Well, what's the worst case runtime of the brute force solution?
Secret Zebra: Able to do that.
Continuous Hedgehog: Okay.
Secret Zebra: Is if I'm running. Yeah. If I'm running the bfs and I'm seeing that something is already on the pathway. No, but it's not going to be Monet. Yeah, but I don't think it won't be like you could have two pathways that are both increasing out of the same cell.
Continuous Hedgehog: Right. But we only care about the maximum.
Secret Zebra: Right? Yeah. So we could clear out all the ones that are not the maximum depth.
Continuous Hedgehog: Right.
Secret Zebra: And then what I'm thinking is, now you have. Now you have a graph, essentially, that is all of the, you know, it's a directed graph with all of the increasing nodes. And now you just have to find the longest way to string those together.
Continuous Hedgehog: Mmhmm.
Secret Zebra: And so what that will look like, I suppose that still ends up being a breath first search a. We have this type of graph.
Continuous Hedgehog: Well, this is your press.
Secret Zebra: Sorry, what was that?
Continuous Hedgehog: Is this describing the bfs or is this setting up the queue for the bfs? I'm not sure what.
Secret Zebra: Yeah, so this is actually trying an approach with the bfs where I don't have to go through each node or through each. Yeah. And so what I was thinking is, yes, it's essentially setting up a queue. What I'm doing is setting up a directed graph which has all of the increasing node movements. Right, or node transitions. And then what I was going to do is iterate on those to string them together into the longest path.
Continuous Hedgehog: Would that mean actually. Yeah, sorry, go for it.
Secret Zebra: N. Will it still be login? Yeah, because it's still going to be a breath first search over it. So I don't know, maybe I may just say I'm going to go with the bfs. I know that's going to be in login and as I get to implementing it.
Continuous Hedgehog: Yeah, I think that makes sense. Yeah, I think that's a very good call. Let's start on the.
Secret Zebra: So I may have explained this. Not so great. Is it understandable or would you like me to maybe write out a little pseudo stuff? Okay, I'll start coding.
Continuous Hedgehog: No, let's start coding.
Secret Zebra: Length by quite a bit.
Continuous Hedgehog: Yeah, I think this could be a good time. Stop. Actually, I want to leave them for feedback.
Secret Zebra: Yeah, for sure.
Continuous Hedgehog: Cool. So before I give feedback, do you have any questions for me?
Secret Zebra: No, I may after the feedback, but yeah. First of all, I thought how you presented the problems was great, so thank you.
Continuous Hedgehog: Awesome. Yeah, it was useful and you liked it. Okay. So since you're senior, I'm going to calibrate my feedback for that call. That's also why I try to keep quiet and not give a lot of hints is I usually expect senior candidates to solve the problem on their own. So I'm going to divide up my feedback on different categories and then give you feedback as I would have given if this was an actual interview and I had to write feedback for you.
Secret Zebra: Right.
Continuous Hedgehog: And then I'll point out all the signals I saw and signals I would have liked to see as well. So for starting off. Yeah, I think you were really good. You asked some really good clarifying questions. You spent some time to disembig with the problem, figure out what the problem is actually. So that's a good signal for a senior candidate. That's something that I watch out for, because usually folks who don't have much experience, they just jump into the coding question and start coding rather than trying to understand the problem. So I would write that my feedback, your problem solving was very good. You came up with the optimal solution right away. You explained it really well, your communication was really good, and then your complexity analysis was good. I would write all of this for my feedback. Then we started coding at like ten minutes in, which is good. I think coding was fine. I didn't really see any big issues. The one thing I wrote in my notes is like, would be nice to use an abstraction, like if digit, and then like 1 second later you wrote that abstraction. So, so yeah, I think that was nice. One other thing that was interesting to is that you did the is number. I mean you did the index access before doing the length check, which is okay in Javascript, I guess. I don't know if you run out of bones and throw.
Secret Zebra: Oh no, I think you could even in javascript.
Continuous Hedgehog: Okay. Right.
Secret Zebra: Yeah, I think with a raise. Yeah.
Continuous Hedgehog: So it should be the other way around where you do the let check and then do the access.
Secret Zebra: Yes.
Continuous Hedgehog: So this is something I would like, doc points I would mention in my feedback saying I would expect like a senior engineer to not do this, to do the access check first. And then I think this one other thing is that I think you created the s num, which is like the string of numbers, right. But then you parsed by instead, which is the index. So I think that's another bug that I would mention in my feedback. I don't know if this is like super minor, I would not even mention it. But it was interesting that you went with this and not equal to. Oh yeah, that was interesting.
Secret Zebra: No, that's a good point.
Continuous Hedgehog: I would not even mention this, but I've never seen anyone do this. It stood up.
Secret Zebra: Yeah.
Continuous Hedgehog: I think that's mostly it. And then maybe one other abstraction that I like from senior engineers is that I would like this to be refactored out into a separate function, which is like a part non function. I've seen that quite often with successful senior candidates. I'm not going to mention this in my feedback. I'm just like telling you that would be nice. I want doc points for this. I think I got a good signal already that you were thinking about abstractions and the right way to design with this, with the ISno. So I think that's fine. Your testing was good. You wrote comments and then you had tested both failing and the passing test. But then I would like dock points for not catching this bug. That's something I expect seniors to catch.
Secret Zebra: Yes.
Continuous Hedgehog: I think the first one is fine. I don't think there's anything to nut pick other than this. I think this bug was the only thing that I would mention as a negative. Everything else is positive on that. And then the second question I think you asked similarly very good clarifying questions asked about all of the edge cases. All of these are good signals I would mention in my feedback for a senior, I think you were a bit stuck with the. I don't know if you're not super comfortable with graph algorithms, but it would have been nice to not spend so much time on the problem solving. I think we started coding only at like 15 minutes in. It would have been nice to start coding at like ten minutes in so that you would have had time to finish the code. That's the one thing I would say. And then I think you got the right solution, which is do the bfs and then memorize the bits so that you don't have to recompute. So I think your problem solving is actually good. I would also mention that in my feedback I did give you a hint saying you only need to store the max path, but we didn't get to using it. So that's okay. I think your runtime was a bit off. I think brute force is over n squared here because you don't actually stop in a brute force solution. In a brute force solution, you go through the entire matrix starting at each point, which is oven squared. Right. I think you optimized the brute force solution actually a little bit.
Secret Zebra: Yeah.
Continuous Hedgehog: Right. But to be clear, the optimal solution is oven. So there is a more optimal one, which you did get right. Like the memorizing is the right solution. So problem solving, I would say like kind of got to the right solution, had the right intuition, had some issues with the runtime complexity analysis of the brute force solution, and then would say took a little more time than expected on problem solving. For coding, I think your coding bit is fine. I don't understand. Well, I'm not confident this would give the right answer, but I'm confident you would have figured it out by testing it if we had time. One thing that I noticed is this max length thing, which basically runs for the entire length of the to do right. And then to do here is basically the entire matrix.
Secret Zebra: My strategy here though was going to be to process. Were you going to break exactly each time? I was going to process all of to do until new to do stayed empty because we didn't add anything new to it. Each iteration was one, what do you call it? One hierarchy, one step in the level of the tree.
Continuous Hedgehog: Got it. Okay. Yeah. So for coding, I would say we didn't have time to finish writing code, but the candidate was on the right track. And then I would say use the right helper methods. I think that was good to use the get matrix neighbors. Yeah. I think one general feedback I would say is like if you're running low on time, start using a lot more abstractions. Like here for example. This is like trivial code. I don't really need to see this. You could instead say like initialize matrix or something, or initialize q and then go on with your pfs and then come back to it when you have time. Because since you were running low on time, this is what I cared about the most.
Secret Zebra: Yes, that makes sense.
Continuous Hedgehog: So yeah, I think this is basically the feedback.
Secret Zebra: I just wrote that in my notes. That's a really helpful tip, is to use those abstractions if I'm running long time. Oh yeah, thank you for that.
Continuous Hedgehog: So I'll just paste it in the feedback, the notes I was writing. But this is basically what we just went over. Yeah, you can look at it later. But do you have any questions for me?
Secret Zebra: I think super helpful feedback. I know I didn't catch the parsent, so maybe that's the answer to my own question. But the dry run process in general, how did that go?
Continuous Hedgehog: I think that was great, actually. The comments was great. Picking one passing test case and one failing test case is perfect. And I think your pace was perfect. So I would not change anything. I think you interviewed really well. I would not change anything on that. I think the only thing I would tell you to this is like a minor thing. I don't think this is your makeup break in this interview. I think not solving the second one is your makeup break on this question.
Secret Zebra: Yeah, that makes sense.
Continuous Hedgehog: I think the feedback, I think watch out for time and then maybe do more practice questions on graphs, bfs and dfs just so that you can just crank it out.
Secret Zebra: Yeah. So that it's just intuitive. Right. When I look at.
Continuous Hedgehog: So much, it.
Secret Zebra: Cool. Well, this was super helpful. I'm trying to think if I have any other questions, but I think that's happy to answer.
Continuous Hedgehog: Any other questions?
Secret Zebra: Yeah, I think that's it. I really appreciate it. It's good to know where to focus on my action items. I'm going to be looking at some more bfs problems. And then I want to remember what you said about abstractions because that's a really good point. Getting kind the important stuff.
Continuous Hedgehog: Yeah. Awesome. Yeah. Good luck with your prep and your interviews. I'm glad this is useful.
Secret Zebra: Awesome. Thanks so much. Bye bye.
Continuous Hedgehog: Yeah, bye.
We know exactly what to do and say to get the company, title, and salary you want.
Interview prep and job hunting are chaos and pain. We can help. Really.
