Mock Interviews

[darwinrlo]

5/8/2020

Similar Problem: LeetCode: 4Sum

Observations & Insights

• From start to finish, it took me 35 minutes to do this problem.
• Now that the difficulty level has been changed to Champ, the problems seem more fitting. 4Sum is a LeetCode Medium.
• Pramp is very good for getting the perspective of the interviewer. For example, it feels annoying when someone actually codes up the brute-force solution. It also feels a little bit annoying when someone retreats into their mind when they get stuck -- I think, say, drawing something is better than going silent.

What Went Well

• The interviewer said I did about as well as he would expect anyone to be able to do.
• By testing the code visually and using speech -- i.e. without writing comments -- I was able to identify a significant bug in my initial implementation on my own. Basically, due to the possible presence of dupes, I need to make sure that there are enough instances of the number needed to achieve the target sum to cover the instances in the quadruplet.
• I tested the empty list and a list that contained fewer than 4 elements.
• The code was very close to bug-free.

Missteps

• I didn't crystallize enough of the brute-force solution to assess its time complexity. I only went through the motions of sketching out the the brute-force solution. Then I attempted to use dynamic programming, which was unnecessary and/or would've been a dead end.

• I incremented a dictionary instead of a dictionary entry. Next time, make sure I have properly indexed a dictionary.

• My initial thought was to create a hash table that maps numbers to their indices. It turns out this was overkill. Since I don't need to provide indices in the solution, I just need to know if there are enough occurrences in the array to cover the number of occurrences in the quadruplet under inspection. This means it is sufficient to map numbers to their counts.

• There was a bug in my program. I got the subtraction backward -- substantially due to my chosen capitalization. s was the function parameter and S was my variable, so I did S - s when the correct expression was s - S. Going forward, make sure I am subtracting the numbers in the right order. Be aware that I may be misled by the capitalization of the variable names.

Learnings and Opportunities for Improvement

• I could've come up with more test cases. I should've thought to test: arr=[4, 4, 4, 4]; s=16.
• I should've tested failure cases, that is, cases that should yield the empty list.

Possible Next Steps

• Think through why a dynamic programming approach wasn't suitable for this problem. (My suspicion is it would've worked but it wouldn't have improved the time complexity.)
• I believe this or a similar problem may have been discussed in Cracking the Coding Interview in the chapter on technical interviews. Have a look at it.
• This problem seems to represent a class of problems. I might do others in the class: 3Sum Closest, Search in Rotated Sorted Array II, and 4Sum II.
• For future problems, I may want to come up with test cases and desired results before even starting (per pgbovine's advice).
• Look into whether this has an even more optimal solution.

My Advice for My Practice Partner

• He had a mental block. He didn't think to change what he used for the hash table keys, only thinking to use words as keys. In the optimal solution, there is a second data structure in which the counts are keys. And since there is a fixed set of counts ー the number of words in the document ー a list can be used as opposed to a hash table.
• Don't code up the brute-force solution, which burns cycles unnecessarily. Iterate on pseudocode and notes until you've gotten the optimal solution.
• For L4 and above, the code has to be working and bug-free. It is better to move slowly and write bug-free code than it is to move quickly and write buggy code.
• To get L5 or L6, in addition to being working and bug-free, the solution needs to be as optimal as it could be.
• During an interview, implement the most optimal solution you can implement in a bug-free manner.
• Jot down observations. You never know what will contribute to the solution.
• Coming up with the optimal solution is done by iteration: by coming up with concrete proposals, identifying flaws and inefficiencies, and thinking through how to fix them.
• The code has to be bug-free. It is better to move slowly and write correct code than it is to move quickly and write buggy code.
• You have to come up with a variety of test cases.

Appendix: defaultdict

Don't do:

d = {}

for e in arr:
  if e in d.keys():  # Instead of doing this, use a defaultdict.
    d[e] = 0
  d[e] += 1

Do:

from collections import defaultdict

d = defaultdict(int)  # int is a factory method

for e in arr:
  d[e] += 1. # If e is not already present in d, it is created and mapped to 0.

d = defaultdict(list)  # Maps unmapped keys to the empty list.

Appendix: enumerate

To pair each element of an iterable with its index, use enumerate, which returns an iterator that gives the next element in a tuple with its index. (To get the next element of an iterator, use next().)

words = ["apple", "banana", "carrot"]
for i, w in enumerate(words):
  # w is an element of the words list. i is its corresponding index.
  pass

[darwinrlo]

5/8/2020

Practice session with Adil

What Went Well

• I am very comfortable with computing the running median of a stream of numbers.
• I am very comfortable with merging overlapping intervals.

Areas for Improvement

• I caught the mistake on my own, but I forgot that heaps in Python are min-heaps, and to get a max-heap, we have to negate the key upon insertion and extraction.
• I did not feel confident in my explanation for why sorting the intervals put overlapping intervals next to each other.
• I modified the input list (sorted it). I probably should've created a copy of the input list.
• I wrote out the algorithm in English before coding it up. I may be able to save time by just saying what I'm going to do out loud.

[darwinrlo]

5/13/2020

Context

LeetCode: Move Zeroes

Morning session on Pramp

Solution

• Let there be a pointer, start, to a contiguous sub-array of 0s.
• Let there be another pointer, end, that points to the first non-zero element after the sub-array of 0s.
• Initially, start points to the first 0 in the array. end is initialized to the first non-zero element after this 0.
• While end points to a non-zero number (as opposed to one past the end of the array), swap it with the first 0 in the contiguous sub-array of 0s. Eventually, all the 0s will be at the back of the array.

What Went Well, What I Should Keep Doing

• Though there is still room for improvement, I am getting better and better at talking while coding. My narration is being well-received.

Missteps

• I got stuck. I didn't think of using two pointers, which is a very common pattern for array problems. Going forward, when I get stuck on an array problem, I should immediately think through whether having two pointers would help. If that doesn't work out, see if I can use a sliding window.
  • Observation: The problem I worked on yesterday (LeetCode: Maximum Subarray), for which I ultimately used a red-black tree, also could've been solved (much more simply) using two pointers.
• I checked zeroPointer for None by using it as a Boolean, i.e. if not zeroPointer. This pattern doesn't work because 0, which is a valid value for zeroPointer, also evaluates to False. The correct pattern for numbers is if zeroPointer is None. It is for lists, for which None and [] are often treated the same way, that if myList can be used.
  • This is a mistake I make repeatedly. I need to proactively remind myself not to do this before every session.

Opportunities for Improvement

• Keep working on thinking out loud. Don't be afraid to bail out of a sentence and restart if I reach a dead end or think I can do better. I need to be OK with taking 2-3 attempts to articulate something abstract and non-obvious. Continue checking for understanding, e.g. "Did you get that?"
• If possible, try not to say extraneous things. These might be distracting to the interviewer.
• Continue vigorously executing on an idea until a conclusion about its viability is reached. If it doesn't work out, continue working on characterizing precisely why it didn't work.
• Instead of writing out complete sentences in the editor, just say the sentences and write down key words and phrases. These key words and phrases can be used as placeholders for code and should be the minimum needed to allow me to recall what I was thinking.

[darwinrlo]

5/12/2020

Mock Interview

LeetCode: Maximum Subarray

[darwinrlo]

Round #2 with SN

• Instead of actually removing the chosen element from the list, create a parameter called currentIndex and increment it.

[darwinrlo]

5/15/2020

Missteps

• I did not successfully enumerate all cases before beginning to solve the problem. For some reason, I thought that rectangles did not overlap. It would be good practice make sure to draw out examples even if I think I got it.

pgbovine:

When the interviewer presents a question to you, immediately sketch out a bunch of examples and ask a ton of clarifying questions to make sure you understand exactly what the interviewer is asking you to do.

Draw several examples and ask your interviewer questions of the form, "for this case, you want the result to be X, right?" Do not make any assumptions without first checking them over with your interviewer.

LeetCode: Maximal Rectangle Geeks for Geeks: Maximum sum rectangle in a 2D matrix

• Largest Sum Contiguous Subarray

Other

• LeetCode: Maximum Sum of Rectangle No Larger Than K
• Geeks for Geeks: Print Maximum Sum Square of a Given Size

Maximum Sum Subarray

LeetCode: Maximum Sum Subarray

• Make sure to consider boundary cases, such as when the maximum-sum sub-array is a single-element sub-array at the very end of the array.

[darwinrlo]

5/19/2020

Session with Anthony on Pramp LeetCode: Decode Ways

What Went Well

• Small mistakes aside, my solution was correct at high level. I was able to articulate the approach before coding.

Missteps

• I misunderstood that the input was a list. It was a string. I need to make sure to clarify pre- and post-conditions before even beginning to think of a solution.
• My interviewer asked me to start coding and I complied. It turns out that my solution was not asymptotically optimal. The optimal solution is a bottom-up dynamic programming solution with a time complexity of O(n) time and a space complexity of O(1).
• Popping from the front of a list is O(n), not O(1). For O(1) popping from the front of a sequence, use a deque instead of a list.

Areas of Weakness

• I succeeded, but it was a bit of a struggle to come up with the time complexity. Basically, in the worst case, each element in the string is a decision point with two choices. I need to work on recognizing this pattern instantly.

Opportunities for Improvement

• When a solution involves recursing on the remainder of a list or sequence, prefer using a parameter for an index into the list over popping elements from the list. I made this mistake at SambaNova as well. I need to stop making it.

[darwinrlo]

May 26 Mock Interview with Anonymous Facebook Software Engineer

Summary

• At minimum, implement the naive solution and just explain the optimal solution. Come up with and articulate the naive (brute-force) solution. If nothing comes to mind, just start coding up the naive solution; at minimum, a working deliverable must be delivered. Proper edge case handling can be sacrificed if necessary though base cases for recursive algorithms are more important than other kinds of edge cases.

  • I am at the point where I can always think of and implement the naive solution. I am not yet at the point where I will always be able to come up with the optimal solution. A more reasonable goal is to demonstrate good problem-solving technique. If I am able to come up with the optimal solution, then that's performing beyond expectations.

• Afterward, if the optimal solution has occurred to me, explain what it would be and give its time and space complexity. Give the sense that it would be a waste of time for me to actually code it up. Depending on the interviewers' impression of me, I may be able to skip coding it up.

• Facebook literally just wants you to chug out solutions to two LeetCode Mediums, edge cases be damned. For the first problem, try to move past the edge cases. Really internalizing the patterns from Grokking the Coding Interview will help a lot here... I can do this over the weekend.

Missteps

• Took too long on both problems. The reasons were taking taking too long to clarify the approach before beginning to code, which was primarily due to thinking through the edge cases. Going forward, thinking through the edge cases can safely be omitted until after a working implementation of the high-level solution has been delivered.
  • If the interviewer doesn't seem to be resonating with this approach, just jump straight to coding.
• The interviewer did not seem to follow along with the diagrams or the code. Test the code along the way to ensure that the interviewer stays on the same page. This is especially true for multi-part problems. Check with the interviewer periodically for understanding. "Have I given a sufficiently clear explanation of what should be done in this case?"
• The high-level solution was not the critical part of the problem -- it was finding the rotation point. I should've made sure I produced a working implementation of this before spending time on getting the high-level algorithm correct.
  • Check with the interviewer periodically for understanding. "Have I given a sufficiently clear explanation of what should be done in this case?" If the interviewer doesn't seem to be resonating with this approach, just jump straight to coding.

Next Steps

• Use my intuition to determine what it is critical and what is not. As this mock interview demonstrated, it won't necessarily be the high-level algorithm -- it could be a helper function.
• In a Facebook interview, if an optimal solution does not come to mind immediately, just go ahead and code up the naive solution. Working code must be delivered for both problems.
• The interviewer cares mostly about working code for the optimal solution. It is OK to leave edge cases to the end.
• Demonstrate to the interviewer it'd be a waste of time for me code up helper functions and whatnot.

[darwinrlo]

May 26 Mock Interview with Anthony

[darwinrlo]

May 28 Mock Interview With Facebook engineer

• Working code for optimal solution to first problem. Pseudocode for optimal solution to second problem.
• Definitely put Marley away during the actual interview.

[darwinrlo]

To pop from the left of a deque, use popleft. pop pops from the right side of the deque.

[darwinrlo]

May 31 Morning

Facebook Similar: LeetCode: Spiral Matrix

Don't do:

output = [[None]*C]*r

Instead, do:

output = [[None] for _ in range(C)] for _ in range(R)]

Opportunities for Improvement

• I over-explained my thoughts, which burned a lot of time. In the future, use my judgment to calibrate the level of explanation. Check with the interviewer. Also, heed hints from the interviewer -- at the beginning, he said, "Don't overthink this."
• Instead of keeping track of remaining horizontal and vertical space, just check to see if the next element in the same direction is None or a number. This would've resulted in less implementation complexity. Next time, after coming up with a solution, if there is implementation complexity, think through how the implementation complexity could be reduced before beginning implementation.
• I got confused while simulating the code on some examples. Be extra careful when doing this and make sure all pertinent parts of the state are explicitly in my model.
• For intricate problems that are not conceptually dense, reduce explanation and lean more toward coding.

[darwinrlo]

6/23/2020

Pramp: Shortest Cell Path

To add to the right of the queue, use append (not appendright). To add to the left side, use appendleft.

To remove an element from the right side of the queue, use pop. Use popleft to remove an element from the left side of the queue.

Use BFS to find the shortest path as opposed to DFS.