DEV Community: Jake Z.

What I Didn't Expect to Learn From Running My Side Hustle

Jake Z. — Thu, 17 Sep 2020 12:37:01 +0000

The past few months, my side hustle and technical interview course AlgoDaily hit $3k USD MRR. It's a small amount compared to my software engineering position at a large tech company, but it covers rent and gave me something to work on during COVID. While running this project, I learned a ton of stuff that's been really useful for both the business, as well as for at work. Here's a small sampling.

Engineering Quality Does Not Matter

This statement is of course being facetious, but not to a tremendous extent. Many outsiders will think that in a software project, engineering should roughly consume 50% of your time, and marketing/sales/biz dev the other half.

This is great in theory, but it turns out that marketing/sales brings in 100% of the money-- shocking, right? The old adage rings true: you can literally have the best product in the world, but if no one knows about it, it won't really matter. Likewise, when people are on your site or app, they just care that the button works when it's clicked. Only fellow developers will find it cool that you're using turbolinks or react-dom-router.

For the first year and a half of running AlgoDaily, I spent nearly all the time improving the product, and refining it technically. I built a daily coding newsletter and wrote hundreds of long-form, quality solutions. Then added an editor and runtime to the site so folks could execute solutions. Then I hired a team to add solutions in other languages. Then I worked with a team to create hundreds of beautiful visualizations and diagrams. None of these things improved sales dramatically.

You know what did work? Telling people about it! Sharing my work with communities (shout out Hacker News and dev.to), asking email subscribers to check out the premium course, getting and sharing testimonials, and spreading the word via social media/youtube/meetups-- getting people's attention was by far the most crucial thing for the sustainability of a small business.

Are You a Content or a Platform Play?

One huge mistake I made in the very beginning was mistaking content plays with platform plays. It's too easy for a software product to just be labeled "software", and for its founder/maker to start listening to generalized advice that may not apply.

For example-- "it needs to be 10x better". Not if you're a content business! An online course, newsletter, or Youtube channel only needs to be marginally better to have users make the switch. Think about it-- if I have the option to watch Selling Sunset or Million Dollar Beachhouse, I'm picking Selling Sunset every time even though it's just a minor improvement in quality.

Another one-- "build an MVP first and iterate". If you're trying to offer articles, tutorials, videos, or podcasts-- an MVP is just episode one. You won't learn much until episode 100 or so!

Side Hustles Need Help Too

AlgoDaily really started to take off when I got burned out after the first year for several months. I then started hiring people to help with nearly everything, and only then did it start seeing traction. If you're a solo maker, don't hesitate to hire!

The term "indie hacker" is kind of bull, largely because there's no such thing as a pure one-person business. Yes, one person may oversee or run things, but the second you need vendors (hosting, forms, newsletter, graphics, design), you've started to build a team. It may be a low-touch team, but if any part of your business depends on a third-party solution, you're no longer on your own.

Less Reading, More Experimenting

I think the majority of entrepeneurial advice/content is largely useless in the moment that it's being consumed. I now strongly believe in favoring just in time advice versus just in case advice.

What's the difference? Just-in-case advice is when you peruse indiehackers.com or pick up a business book for entertainment. You'll read a case study to get motivated, or to get inspired, but it's probably not useful to you at that moment. There's nothing wrong with this-- in fact, I'm having a great time reading Reed Hasting's new book on Netflix-- but I know that it's infotainment.

Just-in-time advice, on the other hand, is when you don't know how to do something and look up a tutorial. It's when you feel chronic fatigue and see a doctor, or have a specific legal question and seek out a lawyer. I've found business advice to be much more useful here, because it's specific to the problem at hand.

It's cool to read up on how an ivy league grad launched a multi-billion dollar startup when she was 21, but almost none of what they did or said will ever apply to someone creating a small online course while trying to start a family. Learning about morning routines and what founders read is dope, but what will actually help your hustle is to try everything and learn from failures.

Customer Quality Really Does Vary By Price

99.9% of AlgoDaily users are lovely. I've corresponded with hundreds, if not thousands of you at this point, and for the most part you're all great! I've made several mistakes along the way, and the AD community has been extremely forgiving and encouraging even during big mishaps.

However-- there really is a correlation between willingness to pay and customer quality. The nastiest emails I've ever gotten have been from folks who've bought a subscription during a sale, paid for a month (the absolute minimum), and then demanded a refund while deriding myself and the product. On the other hand, the folks who pay for the most expensive packages upfront, or stay subscribed for many years, never complain and are usually the first to give testimonials and praise in public.

I'm not sure what to make of this. I price AlgoDaily at a ridiculously low price. You get a daily coding email, hundreds of illustrations, and video solutions for what amounts to $5-6/month if you pay annually. I do this to try to help folks and give back to the dev community, obviously while also learning some things about running a business-- but why people will be rude and mean while getting so much value (and often completely free content) will never make sense to me. What a fascinating phenomenon.

As every thought leader now says, hope this brought you some value. If you're preparing for technical interviews, consider the best and most accessible course available.

Memoization in Dynamic Programming Through Examples

Jake Z. — Sat, 05 Sep 2020 19:31:13 +0000

Dynamic programming is a technique for solving problems, whose solution can be expressed recursively in terms of solutions of overlapping sub-problems. A gentle introduction to this can be found in How Does DP Work? Dynamic Programming Tutorial.

Memoization is an optimization process. In simple terms, we store the intermediate results of the solutions of sub-problems, allowing us to speed up the computation of the overall solution. The improvement can be reduced to an exponential time solution to a polynomial time solution, with an overhead of using additional memory for storing intermediate results.

Let's understand how dynamic programming works with memoization with a simple example.

This lesson was originally published at https://algodaily.com, where I maintain a technical interview course and write think-pieces for ambitious developers.

Fibonacci Numbers

You have probably heard of Fibonacci numbers several times in the past, especially regarding recurrence relations or writing recursive functions. Today we'll see how this simple example gives us a true appreciation of the power of dynamic programming and memoization.

Definition of Fibonacci Numbers

The nth Fibonacci number f(n) is defined as:

f(0) = 0                                       // base case
f(1) = 1                                       // base case 
f(n) = f(n-1) + f(n-2)    for n>1              // recursive case

The sequence of Fibonacci numbers generated from the above expressions is:

0 1 1 2 3 5 8 13 21 34 ...

Pseudo-code for Fibonacci Numbers

When implementing the mathematical expression given above, we can use the following recursive pseudo-code attached.

Routine: f(n)
Output: Fibonacci number at the nth place

Base case:
1. if n==0 return 0
2. if n==1 return 1

Recursive case:
1. temp1 = f(n-1)
2. temp2 = f(n-2)
3. return temp1+temp2

The recursion tree shown below illustrates how the routine works for computing f(5) or fibonacci(5).

If we look closely at the recursive tree, we can see that the function is computed twice for f(3), thrice for f(2) and many times for the base cases f(1) and f(0). The overall complexity of this pseudo-code is therefore exponential O(2^n). We can very well see how we can achieve massive speedups by storing the intermediate results and using them when needed.

Memoization of Fibonacci Numbers: From Exponential Time Complexity to Linear Time Complexity

To speed things up, let's look at the structure of the problem. f(n) is computed from f(n-1) and f(n-2). As such, we only need to store the intermediate result of the function computed for the previous two numbers. The pseudo-code to achieve this is provided here.

The figure below shows how the pseudo-code is working for f(5). Notice how a very simple memoization technique that uses two extra memory slots has reduced our time complexity from exponential to linear (O(n)).

Routine: fibonacciFast
Input: n
Output: Fibonacci number at the nth place
Intermediate storage: n1, n2 to store f(n-1) and f(n-2) respectively

1. if (n==0) return 0
2. if (n==1) return 1
3. n1 = 1
4. n2 = 0
5. for 2 .. n
    a. result = n1+n2           // gives f(n)
    b.   n2 = n1                // set up f(n-2) for next number
    c.   n1 = result            // set up f(n-1) for next number
6. return result

Maximizing Rewards While Path Finding Through a Grid

Now that we understand memoization a little better, let's move on to our next problem. Suppose we have an m * n grid, where each cell has a "reward" associated with it. Let's also assume that there's a robot placed at the starting location, and that it has to find its way to a "goal cell". While it's doing this, it will be judged by the path it chooses. We want to get to the "goal" via a path that collects the maximum reward. The only moves allowed are "up" or "right".

Using a Recursive Solution

This awesome tutorial on recursion and backtracking tells you how to enumerate all paths through this grid via backtracking. We can use the same technique for collecting the "maximum reward" as well, via the following two steps:

1. Enumerate all paths on the grid, while computing the reward along each path
2. Select the path with the maximum reward

Let's look at how this code will work. The below illustration has a 3 x 3 grid. We've kept the grid small because the tree would otherwise be too long and too wide. The 3 x 3 grid only has 6 paths, but if you have a 4 x 4 grid, you'll end up with 20 paths (and for a 5 x 5 grid there would be 70):

We can very well see that such a solution has exponential time complexity-- in other words, O(2^mn) -- and it's not very smart.

Dynamic Programming and Memoization

Let's try to come up with a solution for path-finding while maximizing reward, by using the following observation:

If the path with the maximum reward passes through cell (r, c), then it is also the best path from the start to (r, c), and the best path from (r, c) to goal.

This is the fundamental principle behind finding the optimum, or best path, that collects the maximum reward. We have broken down a large problem into two smaller sub-problems:

Best path from start to (r, c)
Best path from (r, c) to goal

Combining the two will give us the overall optimal path. Since we don't know in advance which cells are a part of the optimal path, we'll want to store the maximum reward accumulated when moving from the start to all cells of the grid. The accumulated reward of the goal cell gives us the optimal reward. We'll use a similar technique to find the actual optimal path from start to goal.

Let's use a matrix array called reward that will hold the accumulated maximum reward from the start to each cell. Hence, we have the following matrices:

// input matrix where:
w[r, c]  = reward for individual cell (r, c)

// intermediate storage where:
reward[r, c] = maximum accumulated reward along the path from the start to cell (r, c)

Here is the recursive pseudo-code that finds the maximum reward from the start to the goal cell. The pseudo-code finds the maximum possible reward when moving up or right on an m x n grid. Let's assume that the start cell is (0, 0) and the goal cell is (m-1, n-1).

To get an understanding of the working of this algorithm, look at the figure below. It shows the maximum possible reward that can be collected when moving from start cell to any cell. For now, ignore the direction matrix in red.

Routine: maximizeReward
Start cell coordinates: (0, 0)
Goal cell coordinates: (m-1, n-1)
Input: Reward matrix w of dimensions mxn

Base case 1:
// for cell[0, 0]
reward[0, 0] = w[0, 0]

Base case 2:
// zeroth col.  Can only move up
reward[r, 0] = reward[r-1, 0] + w[r, 0]  for r=1..m-1

Base case 3:
// zeroth row.  Can only move right
reward[0,c] = reward[0, c-1] + w[0, c] for c=1..n-1

Recursive case:
1. for r=1..m-1
    a. for c=1..n-1
        i. reward[r,c] = max(reward[r-1, c],reward[r, c-1]) + w[r, c]
2. return reward[m-1, n-1]           // maximum reward at goal state

Finding the Path via Memoization

Finding the actual path is also easy. All we need is an additional matrix, which stores the predecessor for each cell (r, c) when finding the maximum path. For example, in the figure above, when filling (1, 1), the maximum reward would be 8+5 when the predecessor in the path is the cell (0, 1). We need one additional matrix d that gives us the direction of the predecessor:

d[r,c] = coordinates of the predecessor in the optimal path reaching `[r, c]`.

The pseudo-code for filling the direction matrix is given by the attached pseudocode.

Routine: bestDirection
routine will fill up the direction matrix
Start cell coordinates: (0,0)
Goal cell coordinates: (m-1,n-1)
Input: Reward matrix w

Base case 1:
// for cell[0,0]
d[0,0] = (-1, -1)      //not used

Base case 2:
// zeroth col.  Can only move up
d[r,0] = (r-1, 0)   for r=1..m-1

Base case 3:
// zeroth row.  Can only move right
reward[0, c] = d[0,c-1] for c=1..n-1

Recursive case:
1. for r=1..m-1
    a. for c=1..n-1
        i. if reward[r-1,c] > reward[r,c-1]) 
                then d[r,c] = (r-1, c)
           else
                 d[r,c] = (r, c-1)
2. return d

Once we have the direction matrix, we can backtrack to find the best path, starting from the goal cell (m-1, n-1). Each cell's predecessor is stored in the matrix d.

If we follow this chain of predecessors, we can continue until we reach the start cell (0, 0). Of course, this means we'll get the path elements in the reverse direction. To solve for this, we can push each item of the path on a stack and pop them to get the final path. The steps taken by the pseudo-code are shown in the figure below.

Routine: printPath
Input: direction matrix d
Intermediate storage: stack

// build the stack
1. r = m-1
2. c = n-1
3. push (r, c) on stack
4. while (r!=0 && c!=0)
    a. (r, c) = d[r, c]
    b. push (r, c) on stack
// print final path by popping stack
5. while (stack is not empty)
    a. (r, c) = stack_top
    b. print (r, c)
    c. pop_stack

Time Complexity of Path Using Dynamic Programming and Memoization

We can see that using matrices for intermediate storage drastically reduces the computation time. The maximizeReward function fills each cell of the matrix only once, so its time complexity is O(m * n). Similarly, the best direction also has a time complexity of O(m * n).

The printPath routine would print the entire path in O(m+n) time. Thus, the overall time complexity of this path finding algorithm is O(m * n). This means we have a drastic reduction in time complexity from O(2^mn) to O(m + n). This, of course, comes at a cost of additional storage. We need additional reward and direction matrices of size m * n, making the space complexity O(m * n). The stack of course uses O(m+n) space, so the overall space complexity is O(m * n).

Weighted Interval Scheduling via Dynamic Programming and Memoization

Our last example in exploring the use of memoization and dynamic programming is the weighted interval scheduling problem.

We are given n intervals, each having a start and finish time, and a weight associated with them. Some sets of intervals overlap and some sets do not. The goal is to find a set of non-overlapping intervals to maximize the total weight of the selected intervals. This is a very interesting problem in computer science, as it is used in scheduling CPU tasks, and in manufacturing units to maximize profits and minimize costs.

Problem Parameters

The following are the parameters of the problem:

1. n = total intervals.  We'll use an additional zeroth interval for base case.
2. Each interval has a start time and a finish time.  
    Hence there are two arrays s and f, both of size (n+1)
    s[j] < f[j] for j=1..n and s[0] = f[0] = 0
3. Each interval has a weight w, so we have a weight array w.  w[j] >0  for j=1..n and w[0]=0
4. The interval array is sorted according to finish times.

Additionally we need a predecessor array p:

6. p[j] = The non-overlapping interval with highest finish time which is less than f[j].  
            p[j] is the interval that finishes before p[j]

To find p[j], we only look to the left for the first non-overlapping interval. The figure below shows all the problem parameters.

A Recursive Expression for Weighted Interval Scheduling

As mentioned before, dynamic programming combines the solutions of overlapping sub-problems. Such a problem, the interval scheduling for collecting maximum weights, is relatively easy.

For any interval j, the maximum weight can be computed by either including it or excluding it. If we include it, then we can compute the sum of weights for p[j], as p[j] is the first non-overlapping interval that finishes before I[j]. If we exclude it, then we can start looking at intervals j-1 and lower. The attached is the recursive mathematical formulation.

The below figure shows the recursion tree when T(5) is run.

Routine: T(j)
Input: s, f and w arrays (indices 0..n).  Intervals are sorted according to finish times
Output: Maximum accumulated weight of non-overlapping intervals

Base case:
1. if j==0 return 0

Recursive case T(j):
1. T1 = w[j] + T(p[j])
2. T2 = T(j-1)
3. return max(T1,T2)

Scheduling via Dynamic Programming and Memoization

From the recursion tree, we can see that the pseudo-code for running the T function has an exponential time complexity of O(2$^n$). From the tree, we can see how to optimize our code. There are parameter values for which T is computed more than once-- examples being T(2), T(3), etc. We can make it more efficient by storing all intermediate results and using those results when needed, rather than computing them again and again. Here's the faster version of the pseudo-code, while using an additional array M for memoization of maximum weights up to nth interval.

Routine: TFast(j)
Input: f, s and w arrays (indices 0..n).  Intervals sorted according to finish times
Output: Maximum accumulated weight of non-overlapping intervals
Intermediate storage: Array M size (n+1) initialized to -1

Base case:
1. if j==0 
    M[0] = 0;
    return 0

Recursive case Tfast(j):
1. if M[j] != -1            //if result is stored
    return M[j]             //return the stored result
1. T1 = w[j] + TFast[p[j]]
2. T2 = TFast[j-1]
3. M[j] = max(T1, T2)
4. return M[j]

The great thing about this code is that it would only compute TFast for the required values of j. The tree below is the reduced tree when using memoization. The values are still propagated from leaf to root, but there is a drastic reduction in the size of this tree.

The figure shows the optimal weight array M:

Finding the Interval Set

There is one thing left to do-- find out which intervals make up the optimal set. We can use an additional array X, which is a Boolean array. X[j] indicates whether we included or excluded the interval j, when computing the max. We can fill up array X as we fill up array M. Let's change TFast to a new function TFastX to do just that.

We can retrieve the interval set using the predecessor array p and the X array. Below is the pseudo-code:

Routine: printIntervals
1. j=n
2. while (j>0)
    a. If X[j] == 1             //Is j to be included?
       i.     print j
       ii.    j = p[j]          //get predecessor of j 
        else
            j = j-1

The whole process is illustrated nicely in the figure below. Note in this case too, the intervals are printed in descending order according to their finish times. If you want them printed in reverse, then use a stack like we did in the grid navigation problem. That change should be trivial to make.

Routine: TFastX(j)
Input: f,s and w arrays (indices 0..n).  Intervals sorted according to finish times
Output: Maximum accumulated weight of non-overlapping intervals
Intermediate storage: Array M size (n+1) initialized to -1,
                      Array X size (n+1) initialized to 0

Base case:
1. if j==0 
M[0] = 0;
X[0] = 0
return 0

Recursive case TfastX(j):
1. if M[j] != -1            // if result is stored
return M[j]                 // return the stored result
1. T1 = w[j] + TFast[p[j]]
2. T2 = TFast[j-1]
3. if (T1 > T2)
        X[j] = 1                    // include jth interval else X[j] remains 0
4. M[j] = max(T1, T2)
5. return M[j]

Time Complexity of Weighted Interval Scheduling via Memoization

The time complexity of the memoized version is O(n). It is easy to see that each slot in the array is filled only once. For each element of the array, there are only two values to choose the maximum from-- thus the overall time complexity is O(n). However, we assume that the intervals are already sorted according to their finish times. If we have unsorted intervals, then there is an additional overhead of sorting the intervals, which would require O(n log n) computations.

Well, that's it for now. You can look at the Coin Change problem and Longest Increasing Subsequence for more examples of dynamic programming. I hope you enjoyed this tutorial as much as I did creating it!

This lesson was originally published at https://algodaily.com, where I maintain a technical interview course and write think-pieces for ambitious developers.

How Do We Get a Balanced Binary Tree?

Jake Z. — Tue, 01 Sep 2020 02:44:13 +0000

Binary Trees

A binary tree, as the name suggests, is any tree in which each node has at the most two child nodes. A binary tree can be empty, implying zero nodes in the tree. The cool thing about binary trees is that they are recursive structures. This means a rule can be applied to the entire tree by applying it turn by turn to all of its subtrees.

To define a binary tree, we need two data structures. One would be the overall binary tree structure that keeps track of the root node. The other would be the node structure that keeps track of the left and right subtrees.

class binaryTree {
  public:
    node * root; //a pointer to the root
};

Now let's define the node structure, which would keep track of both left and right child nodes, and contain a piece of data, which in this case we call the key.

class node {
  public:
    node * left; //a pointer to the root of the left subtree
    node * right; //a pointer to the root of the right subtree
    int key;
};

Here, we are assuming that key data type is an integer, just to keep things simple. But it should be noted that the key type can be any data structure which allows comparison operators, i.e.., <, >, >=, <=, ==.

This lesson was originally published at https://algodaily.com, where I maintain a technical interview course and write think-pieces for ambitious developers.

Binary Search Trees

Binary search trees (or BST for short) are a special case of binary trees, which have an added constraint on the placement of key values within the tree. Very simply, a BST is defined by the following rule:

All nodes in the left subtree have key values less than or equal to the key value of the parent
All nodes in the right subtree have key values greater than or equal to the key value of the parent

The figure below shows an example of a binary search tree:

Balanced BST

A balanced BST is a BST in which the difference in heights of the left and right subtrees is not more than one (1). These example diagrams should make it clear.

How to Balance a BST

There exist balancing algorithms for a BST, e.g., red black trees or AVL trees. In these structures, the insertion and deletion of keys within the BST takes place in such a manner that the tree remains balanced.

However, when given an unbalanced tree, how do you convert it to a balanced tree in an efficient manner? There is one very simple and efficient algorithm to do so by using arrays. There are two steps involved:

Do an in-order traversal of the BST and store the values in an array. The array values would be sorted in ascending order.
Create a balanced BST tree from the sorted array.

So there's two steps in our plan so far:

Step 1: In-order Traversal

Step 2: Create a balanced BST

Let's explore them. Pseudo-code to efficiently create a balanced BST is recursive, and both its base case and recursive case are given below:

Base case:

If the array is of size zero, then return the null pointer and stop.

Recursive case:

Define a build method.
Get the middle of the array and make it the root node.
Call the recursive case build on the left half of the array. The root node’s left child is the pointer returned by this recursive call.
Call the recursive case build on the right half of the array. The root node’s right child is the pointer returned by this recursive call.
Return a pointer to the root node that was created in step 1.

The above pseudo-code's elegance stems from the fact that the tree itself is recursive. Thus, we can apply recursive procedures to it. We apply the same thing over and over again to the left and right subtrees.

You may be wondering how to get the middle of the array. The simple formula (size/2) returns the index of the middle item. This of course assumes that the index of the array starts from 0.

Let's look at some examples to see how the previous pseudo code works. We'll take a few simple scenarios and then build a more complex one.

Array: [30]

First we look at the following array with just one element (i.e. 30).

Array: [31, 37, 38]

Now let's look at an array of size 3.

Array: [10, 11]

Let us now go for an even sized array with two elements.

Array: [10, 11, 17, 19]

We can now extend the example to an even sized array with four elements.

Array: [10, 11, 17, 19, 30, 31, 37, 38]

An even sized array with eight elements.

Now that we understand how balancing works, we can do the fun part, which is coding. Here is the C++ helper function, which is the recursive routine build that we had defined earlier.

The code below shows how you can call the above helper recursive function build:

void build(int *arr, int size, binaryTree &tree) {
    tree.root = build(arr, 0, size-1);
}

// build returns a pointer to the root node of the sub-tree
// lower is the lower index of the array
// upper is the upper index of the array
node * build(int * arr, int lower, int upper) {
  int size = upper - lower + 1;
  // cout << size; //uncomment in case you want to see how it's working
  // base case: array of size zero
  if (size <= 0)
    return NULL;
  // recursive case
  int middle = size / 2 + lower;
  // make sure you add the offset of lower
  //  cout << arr[middle] << " "; //uncomment in case you want to see how it's working
  node * subtreeRoot = new node;
  subtreeRoot - > key = arr[middle];
  subtreeRoot - > left = build(arr, lower, middle - 1);
  subtreeRoot - > right = build(arr, middle + 1, upper);
  return subtreeRoot;
}

Before trying out the above code, it is always best to sit down with a paper and pen, and conduct a dry run of the code a few times to see how it works. The previous code has a complexity of O(N), where N is the number of keys in the tree.

Inorder traversal requires O(N) time. As we are accessing each element of the array exactly once, the build method thus also has a time complexity of O(N).

This lesson was originally published at https://algodaily.com, where I maintain a technical interview course and write think-pieces for ambitious developers.

Getting Your First Software Job Without Professional Experience

Jake Z. — Thu, 27 Aug 2020 13:45:47 +0000

I’ve had a few friends recently ask me about breaking into the software industry. Most have been looking for advice on getting a developer job at a consumer-facing web/internet company-- though places like Tesla and WeWork are also very popular.

These friends have probably heard about the amazing slew of benefits; like interesting work, smart and passionate colleagues, and free food/snacks/alcohol galore. It doesn’t hurt that compensation is usually above market at these companies, and career prospects are second-to-none for talented technologists.

There’s already an abundance of information out there on obtaining software engineering jobs, but much of the advice is geared towards people who have experience already. Technical interview prep is important only if you can even get the interview.

If you've never worked in software, breaking in can be challenging unless approached the right way. Here’s a few tips that are less common that have helped me and others in the past.

This lesson was originally published at https://algodaily.com, where I maintain a technical interview course and write think-pieces for ambitious developers.

First: You Don’t Need to Code

Just getting this out of the way: many people forget that you don't need to code to break into the software industry. It’s pretty amazing that there's still the notion that software businesses are just engineers cranking away in text editors. The most successful tech companies usually have talented engineers, but also wonderful managers, sales reps, customer success advocates, product managers, marketing wizards, designers, and writers.

You may need to cater your craft and experience a bit towards software : for example, focusing a bit more on SEO and digital advertising if you are a person who loves to write. However, know there’s always a place for existing talents.

But if you're sure you want to pursue software engineering...

That First Gig is the Hardest

The most frustrating part for new entrants into tech is the dichotomy in the job search for newcomers versus experienced candidates.

I said earlier that most articles and blog posts about getting a software engineering job is geared towards those with experience. With the tech job market being so hot, senior candidates usually have several options (or even offers in hand) for where they want to go and what they want to do.

This obviously isn’t true for one’s first tech job search. There will certainly be some initial pain, and it could take a while. It might be beneficial to note that an amazing aspect of the industry is how fast one can “level up”. It’s defeating to initially be rejected from dozens of entry-level positions, for sure. But once you’re in, a bit of hustle and hard work to cultivate experience will lead to a much easier path down the road.

Now how to get this experience if you don't have any? Here are some ways.

Get An Internship

If you're in university, the traditional route is to get an internship via your school's recruiting office. The process is almost identical to getting a full time position -- an application, and a few rounds of behavioral and technical interviews. These internships often convert to full-time positions through a return offer.

However, you probably wouldn't be reading this article if you're in this boat, so how else might you build your resume?

Get Experience Via Your Own Projects

One thing a lot of people miss out on is how impressive it is to build a full-fledged application by yourself. If you're able to make a frontend talk to a backend, back it up with a database, and maybe even optimize performance a bit-- you're doing the software engineering work of an entire team!

The other benefit people don't realize about personal or side projects is this: despite not having your code reviewed by others, you do end up learning a lot of maintainable patterns and good habits.

This is because it's ultimately you that will need to do the maintenance of the code-- so you quickly learn not to write spaghetti code or do a quick and dirty job. In a sense, you learn the why behind good naming, shorter methods, clean separation of classes, etc.-- because you end up feeling the pain when you don't stick to good coding standards.

These projects are great things you can add under your resume as experience-- especially if you are able to generate revenue from it. And if you can grow it to something like IndieHackers.com -- jobs might just come to you.

Do Some Contract Work

Another way is to start consulting and do some contract work. Visit temp agencies and freelance websites. Many of the clientele care less about your resume and more about your portfolio.

Additionally, it's a great source of income until you land a full-time job-- though you may have to charge less at first. It's also not rare to hear of the client hiring the consultant or contractor via a temp-to-perm role, especially if you demonstrate that you're providing a return on their investment.

If you've been building stuff for yourself, it may be enough to snag a contracting gig that you can then put on your resume. Many people are drawn to the variety that full-time consulting or contracting offers, and make an entire career out of this.

Contribute to Open Source Software

Another underrated way of getting experience is through contributions to open source software. Not only does it integrate you into a software engineering team (allowing you to build collaboration skills) and get generally valuable experience to trade up, but you also get to work on something that you or others use!

Again, it's also not unheard of-- but certainly not common-- for strong OSS contributors to get hired by a firm after they've worked on the company's software for free. The author of Redux, Dan Abramov, is a good example.

Put Yourself Out There and Meet People

I used to be of the opinion that heads-down good work would always speak for itself. However, much like a good SaaS product needs to focus just as much on marketing/sales as on the product itself, a new technologist needs to make sure that their work is getting recognized and heard about.

On the job-front side, this means asking people for informational coffees and referrals (most people will say yes!), building a portfolio and asking for feedback, and tracking down every lead and opportunity to show off your talents.

Conferences and meetups are great for meeting others who are interested in the same thing you are. They often also lead to opportunities if you are a presenter, or even if you simply strike up the right conversation.

The Domain Matters

Something to note-- an AdTech (advertising-technology) firm will have different values, cultures, goals, and people than a FinTech (financial-technology). The engineering groups will be especially different in terms of pace of work, culture, and dress code.

Working at Jane Street is a completely different experience than working at Etsy. Be careful when generalizing the software industry, and look for opportunities aligned to your personality and interests. You can also use this to your advantage. If you are coming to software from a different industry, your past relevant experience is extremely valuable.

Think about it-- a large part of the job of a developer is to translate business requirements into logic. If you already know the requirements; whether it be finance, the law, compliance, medicine, biology, mathematics, or even music; your vantage point will be strongly appreciated as a software engineer.

If you're coming from finance, look at fintech startups or software engineering roles at banks. Or if you used to make music, Spotify or Pandora might be more willing to give you a interview when you talk about how you built a music collection app in your spare time. At the very least, you'll be able to connect to the product more.

It Could Take a While

Friends who are eager to get into a tech company for the first time as developers often overlook how long it takes to succeed. I've worked with brilliant engineers who took a while to get their first job-- unfortunately, with all things, there is an element of luck involved.

In today's job climate, provided you keep improving your resume, it could take anywhere from one to six months to land something after graduating from school or a bootcamp. If you've been building up your resume with personal projects, contract/consulting work, and OSS projects-- and it takes longer than six months-- you should try to identify what the biggest blocker might be.

Past that, it takes about a year to get really comfortable with basic syntax and getting things up and running, and three to five years to deeply understand how software systems/architectures work and make important technical decisions. Though these numbers drastically vary, this is what I've seen anecdotally.

Always Be Learning (The Fundamentals)

One last thing once you get the first software job-- the change of pace in the industry takes a while to adapt to .

For an example that afflicts web developers in particular, google “Javascript Fatigue”. However, what you’ll find is that trends tend to come up hard and fast, but most don’t stick.

If you’re a developer, the core data structures (lists, stacks, graphs, etc.), the most common algorithms/patterns, and good OOP design patterns have been around forever, and most new ideas are just re-implementations with slight tweaks.

Similarly, if you’re in engineering management-- building relationships, understanding the competitive landscape, and talking to your reports are things that will always be useful and never really go away.

I make this point because landing your second software job will be less about "does this person have experience" and more about "what does this person bring to the table with their experience".

With all that said, though software technology is getting a lot of buzz at the moment, there are numerous industries and professions that are just as enjoyable and meaningful to be in.

Hope this helps someone break in this year. Being a developer is an awesome blessing, and I encourage everyone to try it out and see if they like it.

This lesson was originally published at https://algodaily.com, where I maintain a technical interview course and write think-pieces for ambitious developers.

How to Implement a Hash Map

Jake Z. — Tue, 25 Aug 2020 22:17:11 +0000

Arrays are amazing for looking up elements at specific indices as all elements in memory are contiguous, allowing for O(1) or constant time lookups. But often we don't, or can't, perform lookups via indices. Hash maps and hash tables are a way around this, enabling us to lookup via keys instead.

Can you implement the Map class from scratch? Only two methods are necessary-- get and set. Many programming languages have a built-in hash or dictionary primitive (like Javascript Objects and {} notation), but we don't want to use that for this exercise.

This lesson was originally published at https://algodaily.com, where I maintain a technical interview course and write think-pieces for ambitious developers.

Note: Regular Javascript objects and the Map class are both simple key-value hash tables/associative arrays, with a few key differences:

A Map object can iterate through its elements in insertion order, whereas JavaScript's Objects don't guarantee order. In addition, Objects have default keys due to their prototype, and Maps don't come with default keys. Here's a good breakdown of the two. For the purpose of this exercise, let's assume the same functionality for both.

For the two methods you'll define:

get(key: string) should be given a key, and return the value for that key.
set(key: string, val: string) should take a key and a value as parameters, and store the pair.

Additionally, we've supplied the below hashing function hashStr. It tries to avoid collision, but is not perfect. It takes in a string value and returns an integer.

function hashStr(str) {
    let finalHash = 0;
    for (let i = 0; i < str.length; i++) {
        const charCode = str.charCodeAt(i);
        finalHash += charCode;
    }
    return finalHash;
}

console.log(hashStr('testKey'))

Let's call our new class the Hashmap class, and use it like such:

const m = new Hashmap();
m.set('name', 'Jake');
console.log(m.get('name'));

Let's begin by revisiting how a general hash table works, the theory being what our Hashmap data structure will be based off. As we've noted, in many programming languages, there is a Hashmap class that's based off a legacy Hashtable. Let's step through our suggested implementation of this code.

So we know that hash tables work by storing data in buckets. To access those buckets, we'll need a way to convert a key to an bucket number. (The buckets can be modeled using both arrays and binary search trees, but to keep things simple and maximize speed, we'll stick with using arrays.)

Using keys decouples us from having to know where the data is in the array. Our data structure thus needs a hash function, provided in this case as hashStr, to calculate an index into buckets where the wanted value is stored. We're essentially mapping the key to an array index via our hashStr hash function.

hashStr('r')
// 114

// array = [  _  ,  X  ,  _  ,  _ ]
// index     113   114   115   116

As you can see, all hashStr does is take the key provided in set(), and computes a location for us. We'll thus need another data structure for the actual storage and buckets that the values are placed. Of course, you already know it's an array!

Fill In

The slots or buckets of a hash table are usually stored in an _______ and its indices.

Solution: Array

A good start to writing the class is to initialize it with just the storage array:

class Hashmap {
  constructor() {
    this._storage = [];
  }
}

We'll use the returned index of hashStr to decide where the entered value should go in this._storage.

A word on a collisions: collisions are when a hash function returns the same index for more than one key and are out of the scope of this question. However, there are ways to handle such issues using additional data structures.

Multiple Choice

Which of the following is a solution for collisions in a hash table implementation?

There is no good solution for collisions, the hash function must be unique
Use separate chaining, often with a linked list, where the index of the array consists of a chain of values
Use a trie to store values at every index
Concatenate all the values as one single string at that bucket

Solution: Use separate chaining, often with a linked list, where the index of the array consists of a chain of values

At this point, we have our building blocks, so let's go ahead and implement the set method. The method will:

take the key passed
run it through the hash function, and
set the value in our storage at that particular index

Notice the way we're storing it as well: each index in this._storage (this._storage[idx]) is itself an array, thereby primitively solving for the collision problem.

set(key, val) {
  let idx = this.hashStr(key);

  if (!this._storage[idx]) {
    this._storage[idx] = [];
  }

  this._storage[idx].push([key, val]);
}

The set method now seems pretty straightforward, right?

It's the same concept with our get method. What we're doing there is also running the passed key through the hashStr method, but instead of setting, we'll go to the resulting index and retrieve the value.

  for (let keyVal of this._storage[idx]) {
    if (keyVal[0] === key) {
      return keyVal[1];
    }
  }

One caveat we should note is that it's possible to pass a key that doesn't exist (or has not been set), so we should handle that by returning undefined if that's the case.

get(key) {
  let idx = this.hashStr(key);

  if (!this._storage[idx]) {
    return undefined;
  }

  for (let keyVal of this._storage[idx]) {
    if (keyVal[0] === key) {
      return keyVal[1];
    }
  }
}

That should about do it! Let's try it out.

class Hashmap {
  constructor() {
    this._storage = [];
  }

  hashStr(str) {
    let finalHash = 0;
    for (let i = 0; i < str.length; i++) {
      const charCode = str.charCodeAt(i);
      finalHash += charCode;
    }
    return finalHash;
  }

  set(key, val) {
    let idx = this.hashStr(key);

    if (!this._storage[idx]) {
      this._storage[idx] = [];
    }

    this._storage[idx].push([key, val]);
  }

  get(key) {
    let idx = this.hashStr(key);

    if (!this._storage[idx]) {
      return undefined;
    }

    for (let keyVal of this._storage[idx]) {
      if (keyVal[0] === key) {
        return keyVal[1];
      }
    }
  }
}

This lesson was originally published at https://algodaily.com, where I maintain a technical interview course and write think-pieces for ambitious developers.

How to Validate a Palindrome

Jake Z. — Mon, 24 Aug 2020 21:33:48 +0000

Given a string str, can you write a method that will return True if is a palindrome and False if it is not? If you'll recall, a palindrome is defined as "a word, phrase, or sequence that reads the same backward as forward". For now, assume that we will not have input strings that contain special characters or spaces, so the following examples hold:

let str = 'thisisnotapalindrome';
isPalindrome(str);
// false

str = 'racecar';
isPalindrome(str);
// true

For an extra challenge, try to ignore non-alphanumerical characters. The final solution that we present will handle all edge cases.

This lesson was originally published at https://algodaily.com, where I maintain a technical interview course and write think-pieces for ambitious developers.

True or False?

A string is defined as a palindrome if the reversal of the string is equal to the original string.

For example, “toot” is a palindrome, but “boot” is not.

Solution: True

This is a classic question, and there are multiple ways to solve this. For the sake of learning, let's cover all of them!

Using built-in methods

This would probably be invalid in an actual interview, but you can rely on the built-in String method to accomplish a quick reversal. In Javascript, you can simply call reverse() and in Python, you can call [::-1] You can then compare the reversed string to the original:

function isPalindrome(str) {
    // Calling reverse function
    const reversed = str.split('').reverse().join('');

    // Checking if both strings are equal or not
    if (str == reversed) {
        return true;
    }
    return false;
}

console.log(isPalindrome('racecar'));

Order

What's the order of successfully finding out if a string is a palindrome?

Open a while loop to perform while low is less than high
Continue until end of loop and return true
Define two variables: high and low, as 0 and (length of string - 1)
If `string[low]` does not equal `string[high]`, return false. Increment low, decrement high

Solution:

Continue until end of loop and return true
If `string[low]` does not equal `string[high]`, return false. Increment low, decrement high
Open a while loop to perform while low is less than high
Define two variables: high and low, as 0 and (length of string - 1)

Multiple Choice

What will the following pseudocode do to an input string?

def reverse_str(str):
  start = 0
  end = len(str)-1
  str_copy = [letter for letter in str]
  while start < end:
    temp = str_copy[start]
    str_copy[start] = str_copy[end]
    str_copy[end] = temp
    start += 1
    end -= 1
  return "".join(str_copy)

Make a copy
Reverse the string
Swap the first and last letters
Infinite loop

Solution: Reverse the string

With a while loop:

We can cut down on the number of operations by recognizing that we don't need to do len(str)-1 iterations. Instead of using just one pointer that simply iterates through the string from its end, why not use two?

function isPalindrome(str) {
    let left = 0;
    let right = str.length - 1;
    let leftChar;
    let rightChar;

    while (left < right) {
        leftChar = str.charAt(left);
        rightChar = str.charAt(right);

        if (leftChar == rightChar) {
            left++;
            right--;
        } else {
            return false;
        }
    }

    return true;
}

console.log(isPalindrome('racecar'));

What we're doing above is specifying two pointers, start and end. start points to the beginning of the string, and end is a pointer to the last character. Taking the example input racecar, as we run through it, these are the comparisons we'll see:

racecar
^     ^
racecar
 ^   ^
racecar
  ^ ^
racecar
   ^
True

Multiple Choice

What is the run time of the following code?

def reverse_str(str):
  start = 0
  end = len(str)-1
  str_copy = [letter for letter in str]
  while start < end:
    temp = str_copy[start]
    str_copy[start] = str_copy[end]
    str_copy[end] = temp
    start += 1
    end -= 1
  return "".join(str_copy)

O(log n)
O(n)
O(n log n)
O(n^2)

Solution: O(n)

Final Solution

function isPalindrome(str) {
  if (!str || str === "") {
    return true;
  } else {
    let left = 0;
    let right = str.length - 1;
    let leftChar;
    let rightChar;

    while (left < right) {
      leftChar = str.charAt(left).toLowerCase();
      rightChar = str.charAt(right).toLowerCase();

      if (isAlphaNumeric(leftChar) && isAlphaNumeric(rightChar)) {
        if (leftChar == rightChar) {
          left++;
          right--;
        } else {
          return false;
        }
      } else {
        if (!isAlphaNumeric(leftChar)) {
          left++;
        }
        if (!isAlphaNumeric(rightChar)) {
          right--;
        }
      }
    }

    return true;
  }
}

function isAlphaNumeric(c) {
  if (/[^a-zA-Z0-9]/.test(c)) {
    return false;
  } else {
    return true;
  }
}

console.log(isPalindrome("A Santa Lived As a Devil At NASA"));

Check out more visual tutorials for technical challenges at AlgoDaily.com and try out our daily coding problem newsletter!

How to Get the Intersection of Two Arrays

Jake Z. — Sat, 22 Aug 2020 16:11:00 +0000

Oftentimes, interviewers will test you on things that are deceptively easy. We saw this in Reverse a String, and will see more in future challenges. But sometimes you might get tested on a concept that, while a bit trivial, is really useful in day to day software engineering.

One of those things is array manipulation, or basically doing things to an array that creates some kind of transformation.

Prompt

Can you write a function that takes two arrays as inputs and returns to us their intersection? Let's return the intersection in the form of an array.

Note that all elements in the final result should be unique. Here's one example:

const nums1 = [1, 2, 2, 1];
const nums2 = [2, 2];

intersection(nums1, nums2);
// [2]

And here's another one:

const nums1 = [4,9,5];
const nums2 = [9,4,9,8,4];

intersection(nums1, nums2);
// [9, 4]

This lesson was originally published at https://algodaily.com, where I maintain a technical interview course and write think-pieces for ambitious developers.

Brute Force

We'll start off slowly, by using the smallest sample inputs possible to examine the make-up of the problem. We know we'll need a result array to return, so hold that in mind:

const results = [];

Let's say we need to find the intersection of two arrays: [1] and [1]. In this case, we know that the output is also [1]-- it's rather simple, because we just need to do a straight comparison of 1 and 1. We go through the first [1], see the 1, and locate it in the second array. Because they're the same, we just return a result with that match.

So we need to expand beyond this. Let's say the two inputs are modified to [1] and [2]. Well, when we compare the two single elements, we know that they're not the same. We thus don't need to do anything with result.

As this continues beyond one array element, we can continue this process of checking if each element in the first array exists in the second.

let intersection = firstArray.filter((el) => {
  return secondArray.includes(el);
};

The concept of intersection is from set theory, so this problem is really simple if we just use Sets! In mathematics, the intersection of two sets A and B is the set that contains all elements of A that also belong to B.

Sets are an object type in most languages that allow you to store unique values of most primitives.

If we transform our input arrays into sets, we can make use of the filter method, and apply it to one of the sets-- filtering out anything not in the other set.

function intersection(nums1, nums2) {
  const set = new Set(nums1);
  const fileredSet = new Set(nums2.filter((n) => set.has(n)));
    return [ ...fileredSet ];
}

This would have a time complexity of O(n).

The other way is to not use Sets and keep arrays to model the inputs. With that approach, we'll also need a hash Object to ensure uniqueness. This works because object keys must be unique.

We can collect unique intersections by doing an indexOf check and then returning it in array form:

function intersection(nums1, nums2) {
    let intersection = {};

    for (const num of nums1) if (nums2.indexOf(num) !== -1) intersection[num] = 1;

    return Object.keys(intersection).map((val) => parseInt(val));
}

Despite there being two methods, it might be helpful to use the Set if you encounter a similar problem during your interview. This is because it demonstrates knowledge of a commonly used data structure and a background in mathematics.

Check out more visual tutorials for technical challenges at AlgoDaily.com and try out our daily coding problem newsletter!

How to Reverse a String

Jake Z. — Wed, 19 Aug 2020 00:35:10 +0000

The only way to get better at solving algorithms and data structures is to power through a few.

We covered the best ways to prepare in this lesson, in this one, and here. Be sure to visit those if you need some more guidance. Otherwise, let's jump into it.

Reverse a String

Let's reverse a string!

Can you write a function that reverses an inputted string without using the built-in Array#reverse method?

Let's look at some examples. So, calling:

reverseString("jake") should return "ekaj".

reverseString("reverseastring") should return "gnirtsaesrever".

This lesson was originally published at https://algodaily.com, where I maintain a technical interview course and write think-pieces for ambitious developers.

True or False?

In Java, C#, JavaScript, Python and Go, strings are immutable. This means the string object's state can't be changed after creation.

Solution: True

On Interviewer Mindset

Reversing a string is one of the most common technical interview questions that candidates get. Interviewers love it because it's deceptively simple. After all, as a software engineer, you'd probably call the #reverse method on your favorite String class and call it a day!

So don't overlook this one-- it appears a surprising amount as a warm-up or build-up question. Many interviewers will take the approach of using an easy question like this one, and actually judge much more harshly. You'll want to make you sure really nail this.

How We'll Begin Solving

We want the string reversed, which means that we end up with all our letters positioned backwards. If you need a quick review of strings, check out our lesson on arrays and strings.

We know that strings can be thought of as character arrays-- that is, each element in the array is a single character. And if we can assume that, then we know the location (array position) of each character, as well as the index when the array ends.

There's a caveat to thinking of strings as character arrays-- it's not always true. As readers and viewers have pointed out, a string represents text formed from graphemes (the smallest functional unit of a writing system)-- formed by combining character sequences in unicode.

Though strings and arrays contain similar methods like length, concat, and character position access-- they are not identical. As an example, arrays are mutable and strings usually are not. Before we can operate on the string as an array, we'll need to separate the units (in JS by calling the .split() method, or bypass this property by generating a brand new string instead of trying to operate on the original.

However, after the split operation, we can apply that paradigm to operating on this string. Thus we can step through each of its indices. Stepping through the beginning of the string, we'll make these observations at each point:

const str = "JAKE";
// position 0 - "J"
// position 1 - "A"
// ...

Since a reversed string is just itself backwards, a brute force solution could be to use the indices, and iterate from the back to the front.

See the code attached and try to run it using Run Sample Code. You'll see that we log out each character from the back of the string!

function reverseString(str) {
  let newString = '';

    // start from end
  for (let i = str.length-1; i >= 0; i--) {
    console.log('Processing ', newString, str[i]);
        // append it to the string builder
    newString = newString + str[i];
  }

    // return the string
  return newString;
}

console.log(reverseString('test'));

Fill In

We want to console.log out:

What's the missing line here?

var arr =  [1, 2, 3, 4, 5];

for (var i = ___________; i >= 0; i--) {
    console.log(arr[i]);
}

Solution: arr.length - 1

Can We Do Better Than Brute Force?

However, it wouldn't really be an interesting algorithms question if there wasn't a better way. Let's see how we can optimize this, or make it run faster. When trying to make something more efficient, it helps to think of things to cut or reduce.

One thing to note is that we're going through the entire string-- do we truly need to iterate through every single letter?

Let's examine a worst case scenario. What if the string is a million characters long? That would be a million operations to work through! Can we improve it?

Yes, With More Pointers!

Well, we're only working with a single pointer right now. The iterator from our loop starts from the back, and appends each character to a new string, one by one. Having gone through The Two Pointer Technique, we may recognize that some dramatic improvements can be had by increasing the number of pointers we use.

By this I mean, we can cut the number of operations in half. How? What if we did some swapping instead? By using a while loop and two pointers-- one on the left and one on the right.

With this in mind-- the big reveal is that, at each iteration, we can swap the letters at the pointer indices. After swapping, we would increment the left pointer while decrementing the right one. That could be hard to visualize, so let's see a basic example listed out.

jake    // starting string

eakj    // first pass
^  ^

ekaj    // second pass
 ^^

Multiple Choice

What's a good use case for the two pointers technique?

Shifting indices to be greater at each iteration
Reducing a solution with a nested for-loop and O(n^2) complexity to O(n)
Finding pairs and duplicates in a for-loop
None of these

Solution: Reducing a solution with a nested for-loop and O(n^2) complexity to O(n)

With two pointers, we've cut the number of operations in half. It's much faster now! However, similar to the brute force, the time complexity is still O(n).

Why Is This?

Well, if n is the length of the string, we'll end up making n/2 swaps. But remember, Big O Notation isn't about the raw number of operations required for an algorithm-- it's about how the number scales with the input.

So despite requiring half the number operations-- a 4-character string would require 2 swaps with the two-pointer method. But an 8-character string would require 4 swaps. The input doubled, and so did the number of operations.

Final Solution

function reverseString(str) {
  let strArr = str.split("");
  let start = 0;
  let end = str.length - 1;

  while (start <= end) {
    const temp = strArr[start];
    strArr[start] = strArr[end];
    strArr[end] = temp;
    start++;
    end--;
  }

  return strArr.join("");
}

A Visual Guide to How to Actually Invert a Binary Tree

Jake Z. — Sun, 16 Aug 2020 11:38:36 +0000

Can you invert a binary tree over its vertical axis? This is a famous problem made popular by this tweet:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.
— Max Howell (@mxcl) June 10, 2015

Given a binary tree like this:

     4
   /   \
  2     7
 / \   / \
1   3 6   9

Performing an inversion would result in:

Output:

     4
   /   \
  7     2
 / \   / \
9   6 3   1

The definition of a tree node is as follows:

function Node(val) {
  this.val = val;
  this.left = null;
  this.right = null;
}

This lesson was originally published at https://algodaily.com, where I maintain a technical interview course and write think-pieces for ambitious developers.

This is the famous question that Homebrew author Max Howell famously got wrong in a Google Interview. Hopefully this prevents you from having the same misfortune!

Let's think about brute force-- how would we do it without any clever algorithms? We can start with a very basic input as follows:

  1
 / \
2   3

So to invert it vertically, we'd start at 1, where there's nothing to flip or swap, and it would stay put. We've now processed the first row.

Moving on to the second, we encounter 2 and 3, so we'd swap them and get:

  1
 / \
3   2

Interesting, this seems to have inverted it! Is it as simple as swapping when there's more than one node?

What if we had more than two nodes to swap per level though? If there was an additional level, it might look like this:

That final row is currently directionally 4 -> 5 -> 3, but we'd want the outcome to be 3 -> 5 -> 4 to be properly inverted.

However, we can achieve this by doing two separate swaps. Notice that the below is what we'd get if we swapped 4 and 5 to obtain 5 -> 4, and then swapping 5 -> 4 with 3.

So, to put it all together: we can perform an in-order traversal and do a swap at each iteration.

A caveat that was pointed out by readers-- if we're dealing with a substantially large binary tree, then a recursive solution might cause problems due to call stack size. There are two ways to get around this:

Using a stack to mimic the recursion
Using a queue, visiting the levels one by one in a BFS fashion and swapping the left and right nodes to invert the tree.

Here's what the final code looks like:

function invertTree(head) {
  if (head) {
    var temp = head.left;
    head.left = head.right;
    head.right = temp;

    invertTree(head.left);
    invertTree(head.right);
  }

  return head;
}

Check out more visual tutorials for technical challenges at AlgoDaily.com and try out our daily coding problem newsletter!

Using the Two Pointer Technique

Jake Z. — Sat, 15 Aug 2020 16:41:12 +0000

The Two Pointer Technique

The two pointer technique is a near necessity in any software developer's toolkit, especially when it comes to technical interviews. In this guide, we'll cover the basics so that you know when and how to use this technique.

This lesson was originally published at https://algodaily.com, where I maintain a technical interview course and write think-pieces for ambitious developers.

What is the pattern?

The name two pointers does justice in this case, as it is exactly as it sounds. It's the use of two different pointers (usually to keep track of array or string indices) to solve a problem involving said indices with the benefit of saving time and space. See the below for the two pointers highlighted in yellow.

But what are pointers? In computer science, a pointer is a reference to an object. In many programming languages, that object stores a memory address of another value located in computer memory, or in some cases, that of memory-mapped computer hardware.

When do we use it?

In many problems involving collections such as arrays or lists, we have to analyze each element of the collection compared to its other elements.

There are many approaches to solving problems like these. For example we usually start from the first index and iterate through the data structure one or more times depending on how we implement our code.

Sometimes we may even have to create an additional data structure depending on the problem's requirements. This approach might give us the correct result, but it likely won't give us the most space and time efficient result.

This is why the two-pointer technique is efficient. We are able to process two elements per loop instead of just one. Common patterns in the two-pointer approach entail:

Two pointers, each starting from the beginning and the end until they both meet.
One pointer moving at a slow pace, while the other pointer moves at twice the speed.

These patterns can be used for string or array questions. They can also be streamlined and made more efficient by iterating through two parts of an object simultaneously. You can see this in the Two Sum problem or Reverse a String problems.

Running through an example

One usage is while searching for pairs in an array. Let us consider a practical example: assume that you have a sorted array arr.

You're tasked with figuring out the pair of elements where arr[p] + arr[q] add up to a certain number. (To try this problem out, check the Two Sum and Sorted Two Sum problems here.)

The brute force solution is to compare each element with every other number, but that's a time complexity of O(n^2). We can do better!

So let's optimize. You need to identify the indices pointer_one and pointer_two whose values sum to the integer target.

Let's initialize two variables, pointer_one and pointer_two, and consider them as our two pointers.

pointer_one = 0
pointer_two = len(arr)-1

Note that len(arr)-1 helps to get the last index possible in an array.

Also observe that when we start, pointer_one points to the first element of the array, and pointer_two points to the last element.

This won't always be the case with this technique (we'll explore the sliding window concept later, which uses two pointers but have them move in a different direction). For our current purposes, it is more efficient to start wide, and iteratively narrow in (particularly if the array is sorted).

def two_sum(arr, target):
    pointer_one = 0
    pointer_two = input.length - 1

    while pointer_one < pointer_two:

Since the array is already sorted, and we're looking to process an index at each iteration, we can use two pointers to process them faster. One pointer starts from the beginning of the array, and the other pointer begins from the end of the array, and then we add the values at these pointers.

Once we're set up, what we want to do is check if the current pointers already sum up to our target. This might happen if the correct ones are on the exact opposite ends of the array.

Here's what the check might look like:

if sum == targetValue:
  return true

However, it likely will not be the target immediately. Thus, we apply this logic: if the sum of the values is less than the target value, we increment the left pointer (move your left pointer pointer_one one index rightwards).

And if the sum is higher than the target value, we decrement the right pointer (correct the position of your pointer pointer_two if necessary).

elif sum < targetValue:
  pointer_one += 1
else:
  pointer_two -= 1

In other words, understand that if arr[pointer_one] < target-arr[pointer_two], it means we should move forward on pointer_one to get closer to where we want to be in magnitude.

This is what it looks like all put together:

def two_sum(arr, target):
    pointer_one = 0
    pointer_two = input.length - 1

    while pointer_one < pointer_two:
        sum = input[pointer_one] + input[pointer_two]

        if sum == targetValue:
            return true
        elif sum < targetValue:
            pointer_one += 1
        else:
            pointer_two -= 1

    return false

It's crucial to see that how both indices were moving in conjunction, and how they depend on each other.

We kept moving the pointers until we got the sum that matches the target value-- or until we reached the middle of the array, and no combinations were found.

The time complexity of this solution is O(n) and space complexity is O(1), a significant improvement over our first implementation!

Another Example

In addition, to the previous example, the two pointer technique can also involve the pattern of using a fast pointer and a slow pointer.

Node fast = head, slow = head

One usage is through detecting cycles in a linked list data structure. For example, a cycle (when a node points back to a previous node) begins at the last node of the linked list in the example below.

1 -- > 2 --> 3 --> 4
             ^     |
             |     |
             <- - -

The idea is to move the fast pointer twice as quickly as the slow pointer so the distance between them increases by 1 at each step.

while(fast!=null && fast.next!=null){
  slow = slow.next;

  fast = fast.next.next;

However, if at some point both pointers meet, then we have found a cycle in the linked list. Otherwise we'll have have reached the end of the list and no cycle is present.

if (slow==fast) return true;

The attached code is what the entire method would look like all together.

The time complexity would be O(N) or linear time.

public static boolean detectCycle(Node head){
    Node fast = head, slow = head;

    while(fast!=null && fast.next!=null){
        slow = slow.next;

        fast = fast.next.next;

        if(slow==fast) return true;

    }
    return false;
}

A Beginner's Reference to SQL vs. NoSQL

Jake Z. — Fri, 14 Aug 2020 11:53:02 +0000

Many new developers wonder what the difference is between SQL and NoSQL. The subjects come up often in theoretical discussions and systems design interview preparation.

In this tutorial, we will be looking at the difference between SQL and NoSQL based on certain parameters. Before we begin, let’s analyze each individually to develop our understanding of these contrasting concepts.

This lesson was originally published at https://algodaily.com, where I maintain a technical interview course and write think-pieces for ambitious developers.

What is SQL?

Some definitions to start:

SQL stands for Structured Query Language. As evident from the name, it is a querying language that is used to perform various data operations. It is supported on almost all Relational Databases.

And what is a Relational Database? A relational database, often synonymous as a SQL Database, is a collection of data records that may have predefined associations or relationships with each other.

By extension, a Relational Database Management System (RDMS) is an interface (application or UI) to manage the records, usually by way of SQL. It's used to store, edit, read, and write such data in the form of tables. It's also often visually shown as a spreadsheet-like shape.

SQL Databases

SQL databases, or Relational Databases, employ the traditional way of storing data (where each database may contain several tables). However, it is worth mentioning that in RDBs, each table contains rows that have the same attributes or "shape". As an example, in a "restaurant" database, you may have one table for customers, another for orders, and yet another for restaurant locations.

Now here comes the importance of columns. Each column describes one specific piece of information about the record. The type of data that each column will contain is also predefined. For example, in a customer table, one column may contain the customer id (an integer type column). Another may show the customer order id (another integer), and a third may contain information about customer address (varchar).

Properly defining tables and columns is upfront work to be done to gainfully use a database. Then, the day to day task becomes adding new rows. This is where the SQL language comes in handy. It offers a convenient way to create tables, define columns, add records, delete them, etc. It also allows us to "connect" or associate (create relationships for) multiple tables by using the concept of primary and foreign keys.

Types of SQL DBs

Here's a selection of the various SQL Databases.

What is NoSQL?

Let's move on to the definition of NoSQL. Several NoSQL database systems have grown rapidly in popularity over the last few years. They are non-relational DMSs that support structured data, unstructured, semi-structured, and polymorphic data.

At a high level, NoSQL just means not only SQL. Thus, it doesn't speak to a single database offering-- rather, it's a collection of diverse technologies. Don't assume that the databases are similar in nature either.

As stated, there are no official rules as to what makes a database NoSQL. The term describes more about what they aren’t.

NoSQL Databases:

typically don't use SQL
usually don't store data in tables
usually don't care about relationships
usually don't provide ACID transaction
usually don't require formal data schemas (making them more flexible)

Types of NoSQL Technologies

Let's run through a list of data store offerings within the NoSQL flavor.

Document DB/Document Stores:
These are organized around the idea that the fundamental thing to store is a self-contained piece of data (called a document). Such a document describes its own schema-- this is in opposition to individual rows of data constrained in well-defined columns. With documents, there generally are no restrictions in shape or structure. It may be in XML format, but often it's JSON-- a loose structure based on plain old Javascript objects.

Example: store a simple piece of data consisting of two pieces of information: title and rating. The title is a string and rating is an integer.

In the next piece of data, we have different descriptions and utilize nesting of information.

When we are schema-less, we can simply add new documents in this data store freely. The only constraint is that each document will be given a unique id. But beyond that, you often have total flexibility. There's no need to provide a formal schema and no need to define relationships. One downfall of this is that the database needs to provide a more flexible way of querying the data-- thus arrived solutions like CouchDB and MongoDB.
Key-value databases are another category. Its main emphasis is on having no predefined schema for your data. All it does is store and retrieve everything based on key-value pairs. In some ways, it's like a two-column table (if you had a key column and value column), and nothing more is enforced. It could be any data type. You could fit in bits of XML or JSON.

Furthermore, It is worth mentioning that many products in this category are specifically designed with fault-tolerant distributed architecture. Simplified, this means you can easily install them across multiple machines. As such, no one machine is a point of failure-- the database can survive machine failures and continue functioning.
Graph: Yet another category of NoSQL tech. It is a data store in which everything is kept in the form of connecting nodes, in a graph structure. There is no one "master" point. Although many other NoSQL DBMS tend to de-emphasize relationships, graph databases are all about having nodes of data connected to each other, describing relationships among them.
Column-oriented database: In a traditional row-oriented database, when we try to retrieve a specific record, every single row is scanned. Indexing certain columns may improve the lookup speed-- however, indexing every column slows down the updating (write) speed. Sometimes it may require you to lock the tables-- if not completely, then partially-- by locking certain parts of your table.

This is where column-oriented databases come in handy. They store individual columns separately, allowing an efficient scan when we have a limited number of columns (because there is only one data type in each table). Therefore, it is very efficient to add new columns. However, adding an entire record becomes more difficult. Although they may look similar to traditional databases, the method of storing and retrieving data is where the actual difference lies. They are best for analytics. Examples of the column-oriented database include but not limited to Cassandra (released by Facebook as an open-source project), Hypertable, Google BigTable, and Apache HBase.

Comparison of the Two

Now that we know the fundamentals of both SQL and NoSQL, we can dive into the technical details and compare them across certain factors. Analyzing across these parameters will help us understand their differences.

Theoretical difference

In short, SQL databases are primarily Relational Database Management Systems, while NoSQL databases are non-relational distributed databases and datastores.

Schema:

A schema refers to the organization and shape of records within a database. Both of these database types have a very contrasting data storage models.

SQL databases usually deal with structured data that is organized in the form of tables. On the other hand, NoSQL databases, along with support for structured data, offer the convenience of storing unstructured, semi-structured, and polymorphic data as well.

NoSQL databases can store information in the form of document stores, key-value pairs, graphs databases, and column stores. These DBs do not have predefined schemas that they need to adhere to.

This distinction makes them useful for specific scenarios. For example, RDBs are intuitively useful for accounting systems because they model the accounting ledger well. NoSQL is preferred in "Big Data" scenarios where the flexibility of data types are essential.

Scalability

Scalability refers to how a database technology adapts to an ever-increasing amount of data without sacrificing performance.

In this regard, singular SQL databases tend to be vertically scalable, in the sense that additional load can be handled by using more efficient and newer hardware (CPUs, RAM and SSD). On the flip side, NoSQL databases tend to be more horizontally scalable (they can automatically handle more traffic by distributing it among more servers in the database cluster).

Note that relational databases can also be scaled via more hardware-- however, there is some additional work to be done to unify the various database instances. This is why NoSQL databases are preferred in the case when our data is increasing at a very high rate.

Support

Historically, SQL database were in the market long before the NoSQL ones arrived. Therefore, it shouldn’t come as a surprise that almost all the SQL database vendors provide substantial support to their users. Moreover, a huge community of independent consultants is there to help with the large deployment of SQL databases.

Of course, the same is starting to also be true for NoSQL databases. However, many are still in their embryonic stage, and thus depend more (or often solely) on the open source community for support. Furthermore, independent consultants are also more scarce when it comes to the setup and deployment of large-scale NoSQL databases.

Languages Used

SQL databases support Structured Query Language (SQL) which allows us to perform various operations on the database. It accomplishes this by providing different types of commands. These commands can be categorized based on their functionality:

Data Definition Language (DDL)
Data Manipulation Language (DML)
Data Control Language (DCL)
Transaction Control Language (TCL)
Data Query Language (DQL)

Though SQL is the most stable and widely used option for performing database operations, it may be restricting in the sense that it requires users to predefine the structure of tables and records. There's also the constraint that all data it stores must be consistent in observing that structure.

On the other hand, NoSQL databases are dynamic and flexible. They allow storing unstructured data in multiple ways. Depending on the nature of data, NoSQL options include document stores, key-value pairs, graph databases, and column-oriented stores. As mentioned, you are not required to come up with the structure of data before-hand. Each document may have its own unique structure. This is referred to as Unstructured Query Language (UnQL) and syntax will vary between products.

ACID vs BASE Model:

SQL databases never compromise on ACID (Atomicity, Consistency, Isolation, Durability) properties. On the flip side, most of the NoSQL DBs observe the Brewers CAP theorem (Consistency, Availability and Partition tolerance) and the BASE Model (Basic Availability, Soft-state, Eventual Consistency).

Examples

Finally, let's provide some examples. Although there are many RDBs and NoSQL, we will restrict this list to the most popular ones:

SQL DBs include MS-SQL, Oracle, SQLite, MySQL, and Postgres.

NoSQL DBs include CouchDB, MongoDB, BigTable, Cassandra, Redis, RavenDB, HBase, and Neo4j.

This lesson was originally published at https://algodaily.com, where I maintain a technical interview course and write think-pieces for ambitious developers.

How to Get Better at Approaching Coding Interviews

Jake Z. — Thu, 13 Aug 2020 12:25:48 +0000

How to Get Better at Approaching Coding Interviews

So you want to get better at interviewing? It's all in the approach-- this guide is a step by step walkthrough on exactly how to answer coding interview question from companies like Facebook, Amazon, Microsoft, Netflix, or Google.

This article will cover a lot. It'll walk you through a common technical (whiteboard or non-whiteboard) interview question, and you'll be exposed to things like:

The mentality you need to conquer nerves
Every step to take during the interview
What patterns to brush up on

And much more. Let's start by tackling the mental aspects of the interview before the tangible steps to approaching such problems.

Getting Over Nerves

Software engineering and technical interviews are nerve-wracking. We all know this, but rarely do we ask why.

Why do these kinds of interviews specifically conjure up such dread?

Really, there are few consequences.

Worst case scenario, you fail to correctly express the algorithm they're looking for. Or maybe you can't think of the correct definition for something. You then probably don't get the job.

That's not a great outcome, but there are far worse things. You can always just go home, brush up on what you missed, and try to apply elsewhere.

Knowing that doesn't seem to help though, and here's why.

Our fears usually derive from uncertainty. That is, the belief that there's a chance you'll be presented with a question or challenge that you have no idea how to solve.

But this is not actually the case!

First off, with the right approach-- which the rest of this article will explore in-depth, you can solve any problem.

Secondly-- yes there is a chance you're asked something completely out of left field. But for the most part, interviewers really do want to see how you think. As someone who's been on the other end quite a number of times, know that we want you to do well.

If nerves are still in the way, there are some other solutions. Some things that might be helpful are daily meditation, eating a healthy meal that fuels your brain, and regular aerobic exercise.

What to Do If You Blank Out Completely

With almost any technical challenge, if you have the right approach, you can figure out a way to solve a problem. But what if you genuinely have no idea where to start?

So let's address something quickly-- if you really have no clue, here's what to do.

Let's say you're a frontend engineer with a few years of Javascript Single Page App development under your belt. You're asked the following technical question in an interview.

When would you apply asynchronous communication between two backend systems?

You freeze, and suddenly your chest tightens. You've never worked on any backend systems, and you've forgotten what asynchronous means. For a few seconds, you stare at the interviewer, and your mind has nowhere to go.

Here's two potential ways to address this:

Link it to something you've done
Emphasize how excited you are to learn and work on such things

The first response works because it still allows you to demonstrate your experience:

I haven't directly worked on backend systems, but can you remind me what asynchronous means again? Ah, a form of a programming that allows work to be done separately from the primary application thread? I've done something similar with React-- sometimes inserting data into the database via a REST endpoint takes some time, but we want to give immediate feedback to the user that it's being persisted. So **my educated guess* is that it would be when you want to have a process do something while waiting for something else to complete.*

In this case, it may not be 100% what the interviewer wanted to hear, but you've shown some technical acumen. You were also able to include some discussion about past experiences.

On the other hand, what if there's nothing at all you can relate the question to? Talking about how excited you are and how you would learn this might be a good alternative:

To be honest, I'm not sure, but I've heard the term asynchronous and would love to learn more about backend systems. I'll be sure to read up on it after this interview, do you recommend any books or articles to start with?

Are Whiteboard Algorithm Interviews Good?

The rest of this lesson will be talking about approaching standardized data structures and algorithm based questions. It will be still relevant, but less so, to small sample challenges like "here's a basic setup, implement a REST API with some scaffolding".

Yes, whiteboard algorithm interviews are controversial. However, there are several reasons they still persist. Firstly, they give several strong signals to the interviewer, such as:

Can the candidate can think with clarity in front of others (what this lesson aims to address)
Do they sound like they've prepped for the interview (signal for work ethic)
Do they have a reasonable amount of logical ability?
Can they tell a good solution from a bad one?
How is their grasp of computer science fundamentals?

Secondly, they are easy to do at scale, a consideration especially important if you are a conglomerate that needs to make thousands of annual hires.

Yes, there are take-home assignments, build-a-feature type of interviews, and week-long "trial" periods. I'm sure these are all great methods.

However, the standard "can you solve this problem in front of me" data structure and algorithm questions are still very much the standard at most software companies.

Let's figure out how to tackle them.

The Approach of Good Interviewees

Before we dive in, here's an important note. For any of this to work, you've got to have your data structures and algorithms down pat.

The more practice you have with these topics, the easier it will be to pattern-ize them. It'll also be easier to retrieve them from memory come interview time.

A good starting point is, of course, AlgoDaily's Premium Course and daily newsletter problem. Other recommendations can be found in our lesson around How to Prepare for a Technical Interview.

With all that said, here's the typical steps we recommend for solving whiteboard questions. We'll spend plenty of time exploring each in depth.

Run through a few (1-3) example inputs to get a feel for the problem
Unpack the brute force solution quickly by asking how a human would do this
Tie the brute force solution back to a pattern, data structure, or Computer Science technique
Optimize and run through the same test cases from step 1 again
If you have time, call out edge cases and improvements to the problem

Communication During the Interview

It's not a secret that a big part of the interview is a test of your communication skills. Software engineering is a team sport.

The myth of the lone genius programmer is simply that-- a myth. This is especially for big, hairy, impactful projects that require hundreds of thousands of engineers.

How do you demonstrate strong communication skills?

You must keep talking - I can't emphasize this enough. Unless you need complete silence to think-- which is fine-- you should be voicing your thoughts.

If you're stuck, let the interviewer know
If you don't understand the problem, ask more clarifying questions
If you have no idea what's going on, say you need more context
If you need a hint, let them know!

If you're shy, that's perfectly fine. But with regards to the interview-- know that you might be working with either this person, or someone of a similar aptitude and technical ability. For better or worse, how the interviewer sees you during the interview is what they think they'll get when you come on board. Try your best to be friendly and vocal, if only for the few hours it takes to land the job.

How to Gather Requirements

Let's move on to practical technical interview tips. We can examine the Zeros to the End problem. Here's the prompt:

Write a method that moves all zeros in an array to its end.

The very first thing you should do is to clarify the requirements. Until you know exactly what the problem is, you have no business trying to come up with a solution. Here's why:

Candidate: Cool, zeros to the back, nonzeros in front. That's it right?

Seems simple enough. Why not jump right to the solving it? Because the interview might then say:

Interviewer: Also, note that you should maintain the order of all other elements. Oh, and this needs to be done in O(n) time.

If you hadn't considered that, you might have gone a very bad path. It's crucial to always repeat the question in your own words and clarify heavily. Get the full scope of requirements, and repeat it so they know you've fully grasped the entirety of the problem

Candidate: So we want to move all the zeros to the back, while keeping nonzeros in front. We want to also keep the order the nonzeros were originally in, and the algorithm should run in linear time.

Interviewer: Right on.

Start With Inputs and Outputs

The very next thing to do is either ask for few sample arrays, or come up with your own. Start building your test cases. It helps you start to process how to transform the inputs to get the outputs.

Try to start with a very small input, and increase its size as you do more examples. Here's what you might say:

Candidate: Very interesting problem. Alright, just to make sure I understand the transformation and result that we want, let me run through a few examples. So if I'm given [0, 1], we'd want [1, 0] back?

Interviewer: Yes, exactly. (Candidate begins to think of how to move that lone zero in the first example)

Candidate: Hm, for that one, we just needed to swap the 0 with the 1. Now, if given [1, 0, 2, 0, 4, 0], I would want [1, 2, 4, 0, 0, 0] back.

Interviewer: Correct.

Candidate: And [0, 0, 4] becomes [4, 0, 0]. Hm...

How to Come Up With a Brute Force Solution

Now that you've tried some inputs and outputs, the primary question to ask is this:

If a machine were not available, how would a human manually solve this?

Remember, computers are just tools. Before we had them, humans had to calculate things by hand. So asking yourself how you'd do it manually is a great way to start brainstorming ways to solve the problem. When loops and conditionals aren't available, you're able to say in plain English what you need to do.

Candidate: Hm, yeah, for these examples, the result keeps returning an array of the non-zeros plus an array of the zeros at the end. Thinking through a very basic implementation, what I've been doing is: iterating through, finding the non-zeros, and just putting them in an another temp array. Then I've been filling the rest of the result array with 0s until we've gotten the original length.

Interviewer: Interesting. Want to write that implementation out?

Use Pseudocode To Clarify Your Thoughts

Unless an algorithm is extremely simple, you'll want to write pseudocode first.

This is especially true for brute-force solutions. The interviewer may be okay with just the pseudocode for the first pass, and could ask you to spend the remaining time solving and coding an optimized solution.

Additionally, thinking in pseudocode is much easier to modify should you find a deleterious error. Here's what it might first look like:

temp = []
zero_count = 0
iterate through array:
  if nonzero, push to new temp
  if zero, increment count
for zero_count times:
  push to temp
return temp

It's a good sign you're on the right track if the interviewer modifies the problem to make it a bit more complicated. They might do this by adding a constraint (do this in constant time), or by making the input significantly larger. In my experience, most interviewers will plan to do one easy problem and one harder problem.

Interviewer: Great, now can you do this without instantiating a new array?

Don't lose your cool at this point, and also don't get too excited about passing the first part. It's time to tie our brute force solution to a technique to improve it. We will now cover a number of ways to do so.

How to Optimize With Patterns and Abstractions

After you've done about ~50-100 practice interview challenges, you'll begin to recognize patterns you can leverage. Here's an example of one: If you want speed, you usually need more space/memory. This is especially relevant to the next section about using a data structure.

Look at each step in your solution so far and think about any potential ways to simplify it or break it down. Are there any ways to reduce its complexity?

One trick is to think about what you're doing from a higher-level. By this, I mean get yourself out of the weeds of the logic, and go back to input-to-output. In the above example, yes we're moving zeros to the end by concatenating arrays, but what are the actual things we'll need to do? The process might be thought of as:

Identify the non-zero elements
Put elements at different indexes
Find out how many 0s there are

The beauty of having clear steps like the above is that you can now explore alternative ways to accomplish each one.

For example, to identify the non-zero elements, you can iterate over the array and use a conditional.
Alternatively, you can use a filter method.
And if that's not helpful, you can also look for multiple zeros in a row and splice a new array out.

Something else to ask yourself: What am I trying to do in plain English?

Another very easy way to make progress is to try to futz with the input.

If it's a collection, does sorting or grouping help?
If it's a tree, can we transform it into an array or a linked list?

If tweaking the input doesn't make a dent, maybe it's time to make a bigger transformation.

Introduce a Data Structure or Abstract Data Type

This is where a study of data structures (and experience implementing and using them) really helps. If you can identify the bottleneck, you can start to try to throw data structures at the problem to see if there are any performance or spatial gains.

Going back to the Zeros to the End problem we did earlier, our bottleneck is likely the step of putting elements at different indexes. In that case, we may realize that using a counter variable is beneficial.

Note that the data structure doesn't need to be fancy. In our case, we're literally introducing a single int variable-- but sometimes that's all you need.

What should the counter be counting? Well, once we've split the array up into non-zeros ([1, 2, 3]) and zeros ([0, 0, 0]), we only really care about where the non-zeros end.

Because we don't need to worry about what is in the array after non-zero elements, we can simply keep a separate pointer to track the index of the final array. It will let us know where to start the zeros.

We could then write the follow pseudocode to utilize this strategy:

insert_position = 0
for i in nums
  if i is not 0
    increase insert_position
    keep it in insert_position
  fill the rest in with 0

Despite having two loops, the time complexity simplifies to O(n). However, the space complexity is constant since we're using the same array, so we have an improvement!

A Tactical Data Structure Cheatsheet

Need access to an element in a collection really fast? An array already has the location in memory.

Have to insert data quickly? Add it to a hash table or linked list.

Need a maximum or minimum in O(1) time? Call in a heap.

Need to model connections? Get a graph in there.

The more data structures you know, the better. You can check the curriculum for a list of absolute requirements.

It's also useful (but not necessary) to play with more advanced structures-- think AVL trees, tries, priority queues, suffix arrays, and bloom filters. They are less likely to be needed, but they are useful in industry and can be impressive to pull out during an interview.

A special note about hash tables:

Get to know these guys very well! They can be used in a surprising number of solutions. Many problems can be reduced to searching for elements in a large data collection, finding duplicates in said collection, or storing/retrieving items. Hash tables/hash maps do these things extremely well, so always have it top of mind.

If an additional data structure doesn't help, it may be time to try out an old-school (but reliable) technique.

Introduce a Computer Science Algorithm Technique

There are a few techniques that everyone should be aware of. Usually these are covered in Intro to Algorithms classes to categorize algorithms.

They are generally tools not just beneficial for interviews, but for software engineering work in general, so get to know them!

Divide and Conquer: try to divide the problem into sub-problems that are easier to think through or solve. This allows for the possibility of..

Recursion - see if you can leverage a function that calls on itself. Be especially wary of recursion for trees.

Memo-ization- Can the partial results you've generated in the brute force solution can be used for larger or different inputs? If so, leverage caching of some sort. What data can you store in memory (or create and store in memory) to help facilitate the algorithm?

Greedy - think about what the best move at each iteration or step is. Is there an obvious one at each step? This comes up a lot in graph traversal problems like Dijkstra's algorithm.

What to Do When None Of the Above Worked

So none of the above patterns, data structures, or techniques are shining any light on the problem. What to do?

You have two options.

Ask more questions.

Say, I'm stuck. Can I please get a hint?

Keep communicating! Interviewers are usually more than happy to give a hint-- in fact, that's their job. Certain interview questions will unfortunately have one or two "key intuitions" that you must grok before you can get to a solution.

After You Have A Working Solution

Here's a huge key that takes a while to click. After you've written pseudocode for an optimized solution, manually run through 1-3 example inputs, step by step, through your pseudocode to make sure it works. Warning: nerves will be there, and you may lose your place from time to time, but this is extremely important.

Good engineers test their code thoroughly and can step through logic. The space between having a pseudocode solution and writing code on the whiteboard is a good time to demonstrate this.

At this point, you'll also be able to weed out incorrect assumptions or make important realizations ("oh wait, we should use a Map instead of a JS object instead").

Candidate: Let's start with [1, 0, 3], I think that's a good test candidate. OK, starting with 1, we see that it's not a zero, so it can stay put. We're going to the next element so let's increment our final array index counter. Now we have 0, let's skip. OK, 3, not a zero, our counter is at 1 so we put it after 1 and we have [1, 3]. Great! Then we put a 0 at the end and we get the results we want.

The interviewer will likely say something like "great, let's code it up", or they may try to find out how confident you are in your solution. If the input-outputs check in, you should feel good about moving on.

Note: if you're going to be interviewing on a whiteboard, buy a Magnetic White Board Dry and practice handwriting code on it.

There's many things that people don't consider about coding on a whiteboard: space management mostly, but also how to use shorter variables, and writing horizontally.

Anyway, you've now written this code:

function zerosToEnd(nums) {
    let insertPos = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] != 0) {
            nums[insertPos++] = nums[i];
        }
    }

    for (let j = insertPos; j < nums.length; j++) {
        nums[j] = 0;
    }

    return nums;
}

Once you've written your solution code out, the technical portion should be done.

The interview will now steer towards questions for the interviewer. Make sure that you have questions prepped, and try your best not to think about your performance.

At that point, whatever happened is out of your control, so be forward looking and keep your mind in the present with the interviewer. You'll come across as much more professional if you can maintain your composure, even if the interview didn't go exactly how you wanted.

I hope you've found this guide helpful. Remember that any coding challenge can be solved with the right approach, and the right mentality. Best of luck!

This lesson was originally published at https://algodaily.com, where I maintain a technical interview course and write think-pieces for ambitious developers.