# 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.