Go Interview with a FAANG engineer

Interview Summary

Problem type
Generate Valid Strings

Interview question
Write a program to generate all "valid strings" up to a certain length. A valid string is a string that starts with an "allowed starting character", and in which every character is followed by an "allowed" character. You are given a list of starting allowed characters and a dictionary mapping each character to a list of allowed characters that can follow it in valid strings. You are also given an integer n > 0 and you should generate all valid strings up to and including length n.

Interview Feedback

Feedback about Cunning Bathrobe (the interviewee)
Advance this person to the next round?
Yes
How were their technical skills?
4/4
How was their problem solving ability?
4/4
What about their communication ability?
3/4

Overall solid performance! You understood the problem very quickly and immediately mentioned BFS which showed you are very sharp and comfortable with basics of computer science and algorithms. The initial solution was the non-trivial BFS solution and was correct and working right on first attempt. Most of the feedback provided was aimed at polishing your performance to make sure you provide as much high-quality senior+ level signal as you can to any interviewer. I'll summarize the suggestions below:

• Practicing being somewhat more expressive while coding. Explaining your thought process and the code you're writing as you go will be helpful.
• Using comments and/or more expressive variable names to help with readability and maintainability of the code.
• Making sure efficient data structures are used and that you are aware of the underlying implications of your choices.
• The discussion of runtime and space complexity was solid. I do recommend practicing that type of analysis more and becoming more comfortable with doing basic mathematical analysis and derivation of big-O notation conclusions.

Best of luck with everything!
PS: The word I was looking for was "symmetric"! If a = b implies b = a then the relation is symmetric.

Feedback about Stateless Samurai (the interviewer)
Would you want to work with this person?
Yes
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

Interview Transcript

Stateless Samurai: I saw that you're fairly experienced. In the profile it said, I think 12 years of experience. Is that right?
Cunning Bathrobe: Yes, like around 13 years of experience.
Stateless Samurai: 13 years of experience. Okay, sounds good. Let me start a document here. So I'm going to write notes as we go so I can give you good feedback at the end. And so if you hear me typing, that's what's going on. I'm not being distracted. Cool.

Stateless Samurai: Let me start the interview. So here’s the question. I just pasted it in. You can read it, and then we can look at the two examples and then we can go from there.

Cunning Bathrobe: Sure. So I'm just reading it loud. Write a program to generate all valid strings up to a certain length. A valid string is a string that starts with an allowed static character and in which every character is followed by an allowed character. So there are a bunch of allowed characters and we have to create strings based on those. So you are given a list of starting allowed characters and a dictionary mapping each character to a list of allowed character that can follow it in a valid string.

Stateless Samurai: Sounds good. Anything else before I start?
Cunning Bathrobe: I think I'm good for now.