Python Interview with a Google engineer

Interview Summary

Problem type
Minimum cost to construct string

Interview question

1. Use ABCD to construct a string.

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. Finding interesting triplet
   Given an integer array arr, an interesting triplet is defined as
   0 <= i < j < k < arr.size()
   such that arr[i] < arr[j] < arr[k]

Please check whether arr has at least one interesting triplet.

Read more about the questions

• Minimum Cost to Construct String

Interview Feedback

Feedback about Massively Parallel Squirrel (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?
  4/4

Amazing.
Support strong hire.
Good communications.
Good code style and algorithm designing.
Good test cases/dry running.

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

• The interviewer asked two interesting questions which I had not seen before
• They provided an insightful answer to my question about mentorships at Google
• They had a friendly attitude which made the interview process more enjoyable

Interview Transcript

Rocket Wind: Hello.
Massively Parallel Squirrel: Hi.
Rocket Wind: We'll have mock interview. So before doing that, could you briefly introduce, like, describe your expectation on the interview?
Massively Parallel Squirrel: Sure. So I'm going to apply for an L four position at Google, around two years of experience. Two and a half years of experience. And yeah, I just want to do this interview so I can better prepare myself when I have my Google interview. Cool.
Rocket Wind: Left that. Let me paste a question. Yeah, just paste one. Could you see whether it's clear enough to you?
Massively Parallel Squirrel: Sure. Okay, let me give it a read. For each position, the cost to use each character. Okay, got it. You cannot have two consecutive positions with the same character. Calculate the smallest cost to make a string of large N. I see. By the way, for this interview, are we just going to be doing it in text mode or do you want me to pick a programming language?
Rocket Wind: We use plain text for real Google interview. We don't use IDE as well.
Massively Parallel Squirrel: Okay, cool. Got it. So just to explain my understanding of it, like you mentioned, we need to create a string N. And these strings can only consist of like, four characters, right? ABCD. And then the cost is there in the cost array that you provided. And we want to minimize the total cost, right? So minimize total cost of string. And then one condition is, like, no consecutive characters.

(Continued explanation and discussion about algorithm can be expanded as needed.)

Additional Details

• Pseudocode for algorithm:

function minimize_cost(cost, n):
    # Helper function implementation  
    return min_cost

Conclusion

The mock interview overview provides insight into both problem-solving and technical skills witnessed during the interview with thorough feedback encapsulating communication and overall performance.