Python Interview with a FAANG engineer

Interview Summary

Problem type
Clone Graph

Interview question

1. Given a reference of a node in a connected undirected graph.
   Return a deep copy (clone) of the graph.
   Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.

2. Given two sparse vectors, compute their dot product.
   Implement class SparseVector:

• SparseVector(nums) Initializes the object with the vector nums
• dotProduct(vec)
• Compute the dot product between the instance of SparseVector and vec

A sparse vector is a vector that has mostly zero values; you should store the sparse vector efficiently and compute the dot product between two SparseVectors.

Interview Feedback

Feedback about Ferocious Singularity (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

TC solved both problems quickly and without bugs, ran through the code and identified bugs and fixed them. Correct complexity analysis for both problems.

Areas of improvement:

• Stay focused during dry run; I had to prompt TC to rerun a line of code in which they had a bug. This is not something that would lead to a reject but still worth avoiding in a real interview.
• Complexity analysis for DFS mentioned O(N) whereas it's actually O(V+E).

Feedback about Admiral Hex (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

Admiral Hex: Alright, great. So this is your interview with interviewing IO...

Ferocious Singularity: Yeah, that sounds great.

Admiral Hex: Alright, let's get started with the question, if you're ready.

Ferocious Singularity: Sure. Yeah, let's do it.

Admiral Hex: Okay, great. Okay, so this question is going to be really simple to communicate. It's basically like you're given a graph and you have to clone it...

Ferocious Singularity: So it's an undirected graph. And I start with a node to start with...

Admiral Hex: Yes, you're given a node in the graph.

Ferocious Singularity: Okay. My first thought is I could just do DFS, but use a seen or visited set to keep track of the nodes I've seen already...

Admiral Hex: Right. And why would you need a hashmap?

Ferocious Singularity: Because I need to return the created node...

Admiral Hex: Can you just walk through how it would work with, let's say, just a simple example...

• If there's a cycle, it shouldn't repeat because of the seen set...
• Run the DFS unless it is in my seen set...

Time and Space Complexity

• Time complexity would be O(V+E) for vertices and edges.
• Space complexity would also be O(n) for the hashmap excluding output.

Conclusion

You did very well. Keep practicing your communication skills to further improve.