Technical Interview 1
Questions:
-
- How large inputs can be? very huge
- How inputs will be given to me? strings
- Can I use any inbuilt methods such as BigInteger (in java)? of course no
- What would be max length of these strings? 100
- Will there be any signs (-/+) at the front? no
- Will there be anything other than digits - invalid cases? no
- Will there be any leading zeroes? no
- Can we have just 0 as a number? yes
Explained the intuition on how I would leverage elementary math concepts to multiply these large numbers (strings). Gave initial approach where I would store intermediate products that come from multiplying the first number with each digit of the second number and then will store it in a list and at the end add all of them to get the product.
- Had extra time and huge extra space.
- Thought for a bit and came across an approach where I can maintain a single int array and update the products as I move forward. Cuts down a lot of time and limits space to O(n + m) (previously O(n * m)).
- Wrote clean code and did a dry run. Interviewer impressed and moved to the 2nd question with no follow-ups.
-
Variant of Robot Cleaner
The goal was, there is a machine whose purpose is to clean an entire room, the room has several blocks, our job is to clean the room, that's it. Machine object has a few methods such as we can move(), clean() etc. Machine can move in 4 directions. There can be some blocks too, in such cases the machine can't move in that direction.
- How the input will be given to me? machine object
- There is no initial location? no
- Will there be any grid on which I can move? no
- Will I have values of number of rows and columns I can move? no
- Do I have to clean the room in min number of steps? No, just clean
- What's the initial direction of the robot? consider any direction
- What if the initial location itself has a wall? just return
Mentioned both DFS and BFS approaches and went ahead with DFS (reasoned why). After explaining the approach realized there will be a case where the machine might clean the same block multiple times hence created a visited set and introduced imaginary indices to cache cleaned positions.
- Wrote clean code and did dry run.
- After dry run I realized that backtracking isn't handled properly and that's when I added an anti-direction array for moving back side, fixed the issue and dry ran again.
- Interviewer seemed to be satisfied and we moved towards the questions.
Candidate's Approach
- For the Multiply Strings problem, I initially proposed a solution that used O(n * m) space but later optimized it to O(n + m) by using a single int array to store intermediate products.
- For the Robot Cleaner problem, I implemented a DFS approach with a visited set to avoid cleaning the same block multiple times and added logic for backtracking.
Interviewer's Feedback
- The interviewer was impressed with the clean code and the dry runs I performed.
- They seemed satisfied with my approach and reasoning throughout the interview.
Technical Interview 2
Questions:
-
Copy Linked List with Random Pointer
- Should I implement the node myself or assume? Implemented
- Can we have duplicate values inside the node? Yes
- Can node value cross 32 bit integer? No
- What's max number of nodes we can have in the input? Is it within largest 32 bit integer?
- How the input's given to me? root
- What should I do if the root itself is null? return null
Gave the hashmap approach and interviewer agreed to code. Wrote the clean code with comments at crucial places. Did the dry run with pointers, shown how the copying happened through each iteration.
Follow up: Interviewer asked about a solution without extra space - talked about how I can attach copied nodes beside every original node and reconnect them to achieve O(1) but that would require changing input and I advocated that changing input isn't recommended especially with Linked List.
-
- How the input will be given to me? root node or the array? root
- Do I print the nodes in vertical order or add them to list and print at the end? print
- Can we have skewed trees? yes
- Can we have perfectly balanced trees? yes
- What if there are multiple nodes in the same row index how do I prioritize order? any order
- Should I implement the tree node myself or assume? Implemented
- What's max and min number of nodes and how big the values within the node will be? within 100
Gave BFS approach with a hashmap (key - col index, value - list of nodes in the column). Initially decided to store the pair of (col index and node value) inside the queue after writing a few lines of code realized that it won't work because I need to move through next levels hence then replaced col value to node itself.
Wrote clean code with no extra steps and did neat dry run. Interviewer seemed happy with the solution and we moved to questions.
Candidate's Approach
- For the Copy Linked List problem, I proposed a hashmap-based solution and explained the dry run process thoroughly.
- For the Vertical Order Traversal, I used a BFS approach with a hashmap to store nodes by their column index and adjusted my initial implementation to ensure it worked correctly.
Interviewer's Feedback
- The interviewer was satisfied with my solutions and the clarity of my explanations.
- They appreciated my thoroughness in the dry runs and the clean code I provided.
Behavioral Interview
Questions:
- Interviewer seemed chill, asked around 6 - 7 questions nothing surprised.
- Asked a lot of follow-up questions based on my answer, at some point she wanted to know how business impact was measured.
Candidate's Approach
- I maintained a calm demeanor and answered all questions thoughtfully, providing detailed examples from my past experiences.
Interviewer's Feedback
- The interviewer engaged in a detailed discussion and seemed interested in my responses.
Self Verdict Tech 1: Hire / String Hire - May be lean hire considering O(n) space solution but I did talk about O(1) solution and advocated for O(n) space due to input manipulation.
Self Verdict Tech 2: Hire / String Hire
Self Verdict Behav: Hire / String Hire
Reasons:
- Asked tons of clarifying questions which is an important signal and shows ability to think through different scenarios, edge cases and trim down the scope of the problem / requirement.
- Communicated intuition clearly and wrote every thought on the coder pad, along with pseudo code, comments and verification steps which kept me and interviewer on the same page all the time.
- Coded every question neatly with descriptive variable names.
- I was able to optimize inefficient parts of code immediately by identifying issues in the current solution (such as improving O(n*m) space to O(n+m) space in the multiply strings question).
- I was able to find out bugs immediately by myself and fix them showing debugging signals, for example, I immediately found that having node value isn't enough and included node itself in the queue pair, I also found out issues in the backtracking logic and fixed it by adding anti-directions etc.
- Most importantly, I kept talking and writing (typed a lot of scratch work), hence my packet included everything I spoke which must have helped HC go through everything I communicated during the interview. (Wrote more than 100 lines for each interview - yeah I type fast)
I hope this is helpful. Please UPVOTE this so that others can benefit and learn from my experience.
Thank you and All the best!