Python Interview with a Google engineer

Interview Summary

Problem type
Minimum cost to construct string

Interview question

1. Suppose you can only use character A, B, C and D to form a string of length n. You are also given a 2-D integer array of cost[n][4] meaning for each position (0..n - 1), the cost to use each character (0..3 means A..D). cost[i][j] means the cost to put character j on position i. You cannot have 2 consecutive positions with the same character.

Calculate the smallest cost to make a string of length n.

2. Given a permutation of from 1 to n (an array), the only way you have to change it is to select any integer and put it into the end of the list. Return the minimal number of operations to sort the array.

Read more about the questions

• Minimum Cost to Construct String

Interview Feedback

Feedback about Intrepid Panda (the interviewee)

• Advance this person to the next round? Yes
• How were their technical skills? 3/4
• How was their problem solving ability? 4/4
• What about their communication ability? 4/4

Good points:

1. Figure out the DP algorithm super fast.
2. The implementation of DP only takes ~15 min
3. Dry run the code carefully.
4. Good communications.
5. Understand the time & space complexities correctly. And even do the optimization on the space complexity.
6. Good code style, bug-free.

Suggestions:

1. Probably we can do the dry-run faster (It takes ~13 min to do the dry run), particularly, I think we can just use dp[i][j] = min(a, b, c) + cost[i][j] and write the result for each value directly instead of doing (simulating) the run step by step.
2. We didn't discuss the explanation of dp, I'll give suggestion here. For DP question, we can use this framework/question which makes it very simple to explain the idea and change it into implementation. Just ask & answer the 3 questions:
   • (2.1) what is the state?
   • (2.2) How to do induction (including the base case and induction expression)
   • (2.3) What to return?
3. As you mentioned during our talk, focusing on sample test cases/hints is useful sometimes.
4. In terms of "popular" categories, I think dp, graph and binary search (as a sub-step of a complicated question) are very popular categories for google interview though they are still very wide.

Feedback about Rocket Wind (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

Great experience!
They provided great hints and guided me throughout the process. The second question they gave me was a great question and I learnt a new perspective to look at questions because of that.

Interview Transcript

Intrepid Panda: Hello. Rocket Wind: Hello. Intrepid Panda: Hi. Good morning. Rocket Wind: Morning. We will have mock interview, so before doing that, do you mind briefly describe your expectation on the interview? Intrepid Panda: Yeah. So I am going to be interviewing for Google on site level four, and it's going to be like they told me there's going to be three coding questions and one Google enos and leadership round. So for this one, I want practice with the coding part. Rocket Wind: Okay, sorry, why? You mentioned three coding questions. You mean three coding rounds, right? Intrepid Panda: Yeah, three coding rounds. Sorry. Yeah, three coding rounds and one leader Google in this round. Rocket Wind: Sure. Let me give you a quick question here. Let's see whether you encountered this before. Intrepid Panda: Okay. Rocket Wind: Let’s create a string using A, B, C, D. If we set costs for each index in the string, where adjacent indexes can't hold the same character, what's the minimum total cost to construct the string? Intrepid Panda: Okay! Rocket Wind: Your idea sounds cool to me. Implement that, and let me know your time and space complexity! Intrepid Panda: Sure! I'll get started.