Introduction

The general format of the interview process at software companies for software engineers consists of three parts: recruiter screen, technical screen, and on-site interview. A phone screen is usually the only part of the technical screen and the immediate barrier to being brought on-site for the final stage. The technical phone screen is where you complete a set of coding challenges given through some shared collaboration editor while speaking to another person who is evaluating your performance.

Continue reading “How to pass your technical phone screens”

Introduction

Dynamic programming (DP) is just recursive programming with caching. The cache comes in for saving the results of smaller subproblems.

Because we ultimately have to solve smaller subproblems, we have to traverse our solution space. You can think of the solution space as a directed acyclic graph where each node represents a subproblem. Each outward edge from a node represents immediate dependence on a smaller subproblem. The solution space DAG (directed acyclic graph) will have leaf nodes which have no outward edges. These leaf nodes are base cases.

There are two general ways we might go about solving a dynamic programming problem and they are labeled top-down or bottom-up. Solving a DP problem top-down is like traversing the solution space in post-order depth first search (DFS) starting at the root node. Solving a DP problem bottom-up is like processing the nodes in breath first search traversal starting at the leaf node. That last statement is not quite true from a technical standpoint, but the general idea of computing sub-problems in order of “closeness” to the base case is accurate. In the bottom-up approach, we only compute a sub-problem when all smaller sub-problems have been computed. One implication of this is that the bottom-up approach doesn’t involve recursion.

Continue reading “Interesting case study in dynamic programming”