Software Engineering Interviews

[darwinrlo]

It is April 23rd. My interview at Google is May 19th, which is on a Tuesday. This means I have 24 days left to prepare -- just about three weeks.

I'd like to spend the final week on the distributed systems course and approximate methods for solving NP-complete problems. For my ambitions, there is a real time crunch here.

The two days before that date will be spent reviewing already-processed material. No new material will be processed during those two days. Effectively, there is a deadline of midnight the Sunday before for the processing of new material.

On the morning of the interview, I will undergo a recall & reconstruction sequence to load the most high-impact knowledge into my working memory. I will tinker with this sequence between now and then. I need a first draft of this sequence by the end of this weekend.

[darwinrlo]

Cracking the Coding Interview, p. 67:

You have a chunk of work that's done repeatedly.

I think typically this will be optimizing or removing inner loops.

[darwinrlo]

Cracking the Coding Interview, p. 71:

Optimize & Solve Technique #3: Simplify and Generalize

IMO, it should be "simplify and extend." And a better illustration of the technique than the one presented in the book is 4.9 BST Sequences -- though admittedly it is a more complicated example.

[darwinrlo]

To save time, check your proposal or pseudocode against the solution in the book before coding it up before coding it up.

[darwinrlo]

Most people need to work on coding on a whiteboard. Few people seem to need to work on talking out loud as they think. My difficulties are flipped.

[darwinrlo]

I've been practicing in Java. If I could go back, I would use Python from the start. Python more closely matches my thinking. Luckily, it's not too late to switch.

OTOH, I do find programming in Java to be quite enjoyable. Scala could be a good middle ground.

I think there is a substantial increase in the odds of success with Python.

[darwinrlo]

In their implementation of binary search, the middle element is computed by (a + b)/2. As we know, a+b can overflow. There is a way to write this to reduce the incidence of overflows.

[darwinrlo]

What I really like about CtCI is that there is very little waste: The background materials are minimal, and every problem teaches me something new.

[darwinrlo]

Fahim ul Haq

The CEO of Educative was a software engineer at Facebook.

[darwinrlo]

M-W: interpose

to place in an intervening position

[darwinrlo]

Space complexity is interesting. With time complexity, every unit of work is contributes to the total running time. Space OTOH can be freed. A lot of things might take up space, but the space complexity is the maximum amount of space used at any given time.

[darwinrlo]

I don't think it's a requirement to come up with the expected solution. In fact, it is likely better if it's different while having the same or better time and space complexities.

[darwinrlo]

Peter Thiel called out Google for hoarding cash and not knowing what to do with it. One possible answer is funding and supporting startups -- if they don't know what to do with it, give it to others who do.

Also, Google can lead the way for remote working. If you can pass the technical interviews and you're Googley, then you can work at Google no matter where you are -- even Kansas.

(Look for the video clip. Get the time and place.)

[darwinrlo]

It'd be really great to work with John Carmack at Facebook. Or on Reason. Or React. Or Yann LeCun.

Or with Peter Norvig at Google. Or Jeff Dean and Sanjay Ghemawat.

• Flutter

[darwinrlo]

Make sure you enjoy the technology you're using. For me, Coda works. But I can see how, with someone else, pen and paper would work better.

[darwinrlo]

Workflowy might be better for quiz-and-recall.

[darwinrlo]

These problems require an insight, or even a trick, in order to solve. And as much as people don't like to admit it, it took someone a long time to acquire these insights. These are plausible interview problems because, when these problems were first posed, the interviewer expected to have to give you hints in order for you to make progress.

The landscape has changed. People go into these interviews knowing these insights already. They don't need as many hints, if any at all. These are the people you will be compared with.

[darwinrlo]

Insights

• Review (using active recall) of the insights of the field of competitive programming is the single most important thing you can do to succeed at a software engineering interview (or competitive programming). It is imperative to compile these insights and review them until they are internalized. Review is a high-return activity that most people spend very little time on, preferring instead to do large quantities of problems, which is must less efficient.

• The next most important thing is practice writing the sort of code that is involved in these problems.

How to approach a practice problem in CtCI

• Take 1 minute to extract takeaways from the problem description. Try to do it in 30 seconds.

• Spend 14 minutes drawing out examples, making observations, and coming up with insights. If possible, describe a high-level approach. The description of the approach should truly be high-level: No code, not even pseudocode, is written; just notes, perhaps in the form of a bulleted list, will suffice.

• Spend 45 minutes going through the solution. As you read, extract takeaways and generate corresponding review questions on the fly. Try to figure out the 10% that will get 90% of the result.

• Move onto the next problem.

• Every week -- perhaps even every evening -- try your hand at a coding contest.

  • LeetCode has a contest every Saturday evening. After each contest, reflect on why things didn't go as well as you would've liked and make a plan to improve upon these things.
  • LeetCode's past contests are available online. You can set up your own contests each evening.

[darwinrlo]

Putting things into our own words is something we should all practice, starting from a young age. And it does take practice to get good at.

I remember that Jerry Cain seemed to be good at this -- he usually had a unique way of phrasing things. So did several people I knew while growing up.

Also, being able to articulate things key, for me at least, to understanding things in discrete math. (I wonder if Hungarian is better suited to express ideas in discrete math. The way to test this would be to articulate ideas from discrete math in English and get someone to translate them into Hungarian.)

Being able to say things in your own words is mentioned in passing or as afterthought. It should be something we focus on front-and-center.

[darwinrlo]

Jeff Bezos:

I set my first meeting for 10 a.m. I like to do my high IQ meetings before lunch, like anything that’s going to be really mentally challenging, that’s a 10:00 a.m. meeting

Christoph Randler:

People whose performance peaks in the morning are better positioned for career success, because they’re more proactive than people who are at their best in the evening.

Source: [CNBC]

[darwinrlo]

Jeff Bezos to Thrive Global:

If you shortchange your sleep, you might get a couple of extra ‘productive’ hours, but that productivity might be an illusion. When you’re talking about decisions and interactions, quality is usually more important than quantity.

Source: [CNBC]

[darwinrlo]

I'm already pretty good at putting the pieces together. What I need are the pieces.

[darwinrlo]

It is important for me to feel both closure and progress. Marking something as done is very impactful.

Feeling unresolved hinders the feeling of momentum.

[darwinrlo]

The insights you can use when you're on the spot is the stuff at the top of your head.

[darwinrlo]

Cal Newport on the Quiz-and-Recall Method for Technical Sources:

First, narration is key. You can’t just write out the steps to an answer. You have to lecture, as if you are presenting the solution to an imaginary class, about each step and why you are doing it.

Second, the technical discussion questions (also discussed here) help make sure you understand the underlying concepts.

Source

Cal Newport on technical explanation questions for complicated problems:

Given a complicated example of a certain type of problem, a good TEQ might have you provide detailed annotation on each step; explaining the logic behind each.

Source

Cal Newport on working on internalizing which techniques apply in which situations:

In many technical courses, a big part of the challenge is figuring out which technique to apply to a given problem. A good TEQ might have you discuss the criteria for choosing from a set of different techniques for a certain type of problem.

Source

The above could be used on the 16 patterns in Grokking.

For all its virtues, CtCI will not infrequently present a solution without explicitly explaining key aspects. You have to recognize when this happens, identify a suitable TEQ, and include it in your review.

[darwinrlo]

Mega Problem Sets:

I take this one step further by discussing how to construct Mega Problem Sets (MPS), which include, in addition to your weekly homework, selected examples from your lecture notes. If you can answer the problems in every MPS, then you are more than prepared for your upcoming test.

The problems in CtCI are a great source for the software engineering interview prep analogue of "selected examples from your lecture." The problems in LeetCode are a bit random. The problems in CtCI are extremely well chosen as the examples in lecture would be in the ideal case.

Source

[darwinrlo]

Boundary conditions are very tricky to get right. Getting them right must be worked on explicitly.

Loops

• The initial value for the iteration variable
• The loop condition. What the inequalities should be given

[darwinrlo]

Relish the times in which you find things that don't come quickly to you -- you are spending time on the concepts you most need to spend time on.

[darwinrlo]

Do your work in a way that sets you up to love your work -- even if it means being less efficient in the short term. So-called efficient methods disregard an important variable: you. So-called efficient methods are only effective on a short timescale. Over the long term, the system that you enjoy will be both more effective and more efficient.

[darwinrlo]

Lead the interviewer to Aha! moments. Epiphanies feel highly rewarding. If you can do this, this reverses the power balance, shifting it from the interviewer to you.

Recall the skit under discussion on the first day of drama class.

[darwinrlo]

Why are we still coding up recursive algorithms by hand?

[darwinrlo]

For "true" mastery, write the algorithm using pen and paper.

[darwinrlo]

It is important to do practice problems, make mistakes, and learn from them. Avoiding pitfalls and traps helps improve efficiency and thus speed.

For example, let's say you have a function foo. You need two parameters, one for an array and one for an index into that array. You might be tempted to call the latter parameter i, i.e. foo(arr, i). But this will give you trouble once you're inside the function body ー you won't be able to use i as an iteration variable for your for-loops!

Inside CtCI, you will see index used without explanation... this is why.

Another example is accessing a grid by row and column instead of by x- and y-coordinates. See p. 361 in CtCI.

[darwinrlo]

CtCI 8.2 -- the solution backtracks from the target position. But it seems to me you could just as easily go forward from the origin.

But backtracking does cause the points to be added to the path in the right order.

[darwinrlo]

Creating a todo list is invaluable for breaking up work into chunks that feel manageable. The chunks could even be segments of text within something you have to read. Marking a todo as [current] commits you to it. And marking it with an [x] makes you feel done with, allowing you to release your emotional "lock" on it and move on.

[darwinrlo]

Turning off automatic capitalization, spelling, and link correction:

Correct your spelling & grammar in Google Docs

Tools - Preferences - General

[darwinrlo]

• The purpose of taking notes during class is to capture what you need to know and what you need to figure out outside of class.
• The purpose of taking notes outside of class is to put things into your own words, which is critical for achieving understanding.

[darwinrlo]

In school, during the week, notes are taken of lecture (putting things into one's own words) and review questions are generated.

Over the weekend, review using active recall is done.

[darwinrlo]

Peter Norvig's lecture notes do a great job on graph search and even dynamic programming.

[darwinrlo]

I want to teach my queue technique. Maybe I even want to develop a software system for it.

I can demonstrate it on Lustig's neuroscience paper.

This could be a significant contribution.

This is a very engaging way to learn.

[darwinrlo]

Observation: Once a question is explicitly verbalized, my subconscious is triggered to work on it. Often, it is able to surface a feeling for what the answer might look like almost right away.

But the question has to be explicitly posed or else my subconscious won't be triggered to work on it.

[darwinrlo]

Biology class

• Didn't do well on the first biology midterm
• Achieved the mean on the second biology midterm

Came all the way back from Davis. Went through slides with him together at a Starbucks. Looked at each thing and posed questions about what these things meant. This is not just a box. It's a cell membrane.

Interpreter -- never thought so hard in his life.

[darwinrlo]

After articulating something -- either through writing or speech -- I am able to see a picture in my head. It seems that the paintbrush for the canvas in my brain is explicitly articulating thoughts using language.

[darwinrlo]

I really need to work on not making off-by-one errors. I need to compile a list of representative problems that exercise nuances that lead to off-by-one errors and do them at the start of every day.

It's a good idea in general, I think, to do quiz-and-recall on important things.

[darwinrlo]

I believe this reasoning is incorrect.

Since, in each step, the number of subsets doubles as we add each element to all the existing subsets, the time complexity of the above algorithm is O(2^N), where ‘N’ is the total number of elements in the input set.

Educative: Subsets (easy)

This seems to assume creating a copy of an ArrayList (and creating a new subset by adding another element) takes O(1) time. In fact, it is proportional to the size of the array.

If linked lists were used, then it would take O(1) time to create a new list with a new head. But this is not what was done.

[darwinrlo]

The brute-force solution doesn't actually enumerate the items. It just gives the achievable "profit."

Educative: 0/1 Knapsack (medium)

[darwinrlo]

The optimal substructure of a dynamic programming problem is just the recursive structure.

[darwinrlo]

I discovered something that worked -- it took a long time -- when I was taking a class in digital systems.

[darwinrlo]

Feeling on the spot -- or otherwise judged -- results in impaired ability to perform cognitive tasks. If you feel judged inappropriately, it is something you must overcome -- perhaps through exposure therapy.

[darwinrlo]

Consider the following two ways to pose a question.

1. Why do we have to do X?
2. Do Y. (And expect that you will remember to do X.)

1 is a good initial question. Make it a goal to advance to 2.

[darwinrlo]

1. Go through the material. Put things into my own words.
2. Pull out takeaways.
3. Create quizzes on the takeaways.
4. Take the quizzes. Answer questions using speech. (This is the single most high-return activity during prep.)