Round 1
Questions:
Nested List Weight Sum
- I came up with the recursive solution and coded it in time.
- Interviewer asked follow-up about coming up with better space complexity.
- For the recursive solution, the call stack would have a memory complexity of O(d) where d is the max depth of the list.
- I mentioned that another solution I could think of is by solving it iteratively and using a BFS approach with a queue, but that wouldn’t improve the memory complexity still.
- He then asked whether the input could be represented as a different data structure to improve memory complexity, to which I replied mentioning a tree-like structure with elements in different levels of an n-ary tree but kind of messed up explaining it since I was just thinking out loud.
Candidate's Approach
I proposed a recursive solution initially. When discussing space complexity, I acknowledged the O(d) memory usage due to the call stack. I suggested an iterative BFS approach but recognized it wouldn't improve memory complexity. I also attempted to explain a tree-like structure for input representation but struggled with clarity.
Interviewer's Feedback
Not sure if his response was positive or negative, but we moved on to the next question at the 20-minute mark.
Basic Calculator II
- This was an easier variant that involved only * and +.
- I explained my approach of keeping track of cur, prev, and curOP, reversing the previous + operation if we encounter a * operation.
- This was the best solution since it was constant space complexity (better than the stack solution).
- Did a try run of my test cases and code seemed okay.
- After the interview, I realized that I made some indexing issues with the iteration but hopefully the interviewer overlooked it.
Candidate's Approach
I explained my approach of maintaining variables for the current value, previous value, and the current operation. I aimed for constant space complexity by avoiding a stack-based solution. I ran through my test cases, but later realized I had an indexing issue during iteration.
Interviewer's Feedback
No feedback provided.