Preparing for the Tech Interview

Preparing for technical interviews can be a daunting task. Here are some useful tips and resources to stay on track.

Coding

  1. Practice, a lot. There is no way around it. But rather than doing all 600 problems on Leetcode, cover all types and spend time understanding each problem thoroughly.
  2. Go for the hardest ones. After those the rest all become easy.
  3. If stuck on one problem for over two hours, check out the solutions. More time might not be worth it.
  4. After solving one problem, check out the solutions. I was often surprised by how smart and elegant some solutions are, especially the Python one-liners.
  5. Use a language that you are most familiar with and that is common enough to be easily explained to your interviewer.

System design

  1. Understand the requirements first, then lay out the high-level design, and finally drill down to the implementation details. Don’t jump to the details right away without figuring out what the requirements are.
  2. There are no perfect system designs. Make the right trade-off for what is needed.

Topics for review

Behavioral

  1. Dealing with difficult customer

  2. Did you ever tell a customer they were wrong about something, and how?

  3. Strengths and weaknesses

My brain dump

Software Design and Architecture

Tutorial

References

Contains Duplicate III 🚧

Problem

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

Example 1:

Input: nums = [1,2,3,1], k = 3, t = 0
Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1, t = 2
Output: true

Example 3:

Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false

Incorrect Attempt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        //if (k == 0) return true;
        if (k >= nums.size() || nums.size() == 0 || k <= 0 ) return false;

        int a = 0;
        int b = a + k;

        for (; b < nums.size(); a++, b++) {
            if ((abs(nums[a] - nums[b])) <= t) return true;
        }
        return false;
    }
};

This fails for input

1
2
3
[2,2]
3
0

Also, the discussions involve more elaborate solutions. So this naive solution is incorrect.

Understand the problem

I was missing a key point in the problem. The words “at most“. That changes the problem! 😮

We need to think of a dynamic sliding window that goes from length 1 to length k.

Let’s check an example:

Given Input: nums = [1,2,3,1], k = 3, t = 0

Here the max window length is 3 and thus 1 - 1 satisfies the condition.

Let’s see another example where the answer where the result is true.

1
2
3
[12,14,15]
1
1

This is because 15 - 14 satisfies within the given window of 1.

And k can exceed the size of your given vector! So the below one also results in true.

1
2
3
[12,14,15]
11
1

Now for this example we expect a false because the max window size is 2 and the max difference we can accept is 5. Which is only possible for 15 - 10 or 104 - 100 here.

1
2
3
[112,104,15,60,100,1,10]
2
5

Increasing window size (k) to 3 results in true.

Analysis

The brute-force approach would be to try every pair until we find one that works for the given constraints. But then we end up visiting the same pairs of indices many times. It would be a good idea to cache them somehow.

Accepted

After scouring the discussion over a few days I think I have pieced the logic together.

The idea is that we use a set to represent a sliding window.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        set<long> window; // set is ordered automatically
        for (int i = 0; i < nums.size(); i++) {
            if (i > k) window.erase(nums[i-k-1]); // keep the set contains nums i j at most k
            auto pos = window.lower_bound((long)nums[i] - t);
            if (pos != window.end() && abs(*pos - (long)nums[i]) <= t) return true;
            window.insert(nums[i]);
        }
        return false;
    }
};

Explained

1
2
3
4
5
6
7
|a -b| <= t
implies
(a - b) <= t
or (b - a) <= t

If a and t are known then we can search for a number equal to or just greater than (a - t).
If found then we can test it to see if satisfies the given constraint of |a - b| <= t.

Side note about std::set

C++ provides an API for the set which allows us to find the number equal to or next greatest than given value.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// set::lower_bound/upper_bound
#include <iostream>
#include <set>
using namespace std;

int main ()
{
  std::set<int> myset;
  std::set<int>::iterator itlow,itup;

  for (int i=1; i<10; i++) myset.insert(i*10); // 10 20 30 40 50 60 70 80 90

  itlow=myset.lower_bound(1200);                //       ^
  if (itlow != myset.end()) cout << "lower = " << *itlow << endl;
  itlow=myset.lower_bound(5);                //       ^
  if (itlow != myset.end()) cout << "lower = " << *itlow << endl;
  itup=myset.upper_bound (65);                 //                   ^
  cout << "upper = " << *itup << endl;
  myset.erase(itlow,itup);                     // 10 20 70 80 90

  std::cout << "myset contains:";
  for (std::set<int>::iterator it=myset.begin(); it!=myset.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

Results in:

1
2
3
lower = 10
upper = 70
myset contains: 70 80 90

Explore here

01 Matrix 🔨

Problem

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.
The distance between two adjacent cells is 1.

Example 1:
Input:

0 0 0
0 1 0
0 0 0

Output:

0 0 0
0 1 0
0 0 0

Example 2:
Input:

0 0 0
0 1 0
1 1 1

Output:

0 0 0
0 1 0
1 2 1

Note:

The number of elements of the given matrix will not exceed 10,000.
There are at least one 0 in the given matrix.
The cells are adjacent in only four directions: up, down, left and right.

Analysis

DFS ❓

Attempt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    unordered_set<int*> visited;
    int dfs(int i, int j, vector<vector<int>>& v) {
        if (visited.find(&v[i][j]) != visited.end()) return v[i][j];
        visited.insert(&v[i][j]);
        if (v[i][j] == 0) {
            return 0;
        }

        int res = INT_MAX;
        if (j > 0) {
          //left
          res = min(res, dfs(i, j - 1, v));
        }
        if (j < v[0].size() - 1) {
          //right
          res = min(res, dfs(i, j + 1, v));
        }

        if (i > 0) {
          //top
          res = min(res, dfs(i - 1, j, v));
        }
        if (i < v.size() - 1) {
          //bottom
          res = min(res, dfs(i + 1, j, v));
        }

        v[i][j] = res;
        return res;

    }
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
      for (int i = 0; i < matrix.size(); i++) {
        for (int j = 0; j < matrix[0].size(); j++) {
          dfs(i, j, matrix);
        }
      }
      return matrix;
    }
};

Whoops! We are supposed to add distances at each step!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    unordered_set<int*> visited;
    int dfs(int i, int j, vector<vector<int>>& v) {
        if (visited.find(&v[i][j]) != visited.end()) return v[i][j];
        visited.insert(&v[i][j]);
        if (v[i][j] == 0) {
            return 0;
        }

        int res = INT_MAX;
        if (j > 0) {
          //left
          res = min(res, 1 + dfs(i, j - 1, v));
        }
        if (j < v[0].size() - 1) {
          //right
          res = min(res, 1+ dfs(i, j + 1, v));
        }

        if (i > 0) {
          //top
          res = min(res, 1 + dfs(i - 1, j, v));
        }
        if (i < v.size() - 1) {
          //bottom
          res = min(res, 1 + dfs(i + 1, j, v));
        }

        v[i][j] = res;
        return res;

    }
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
      for (int i = 0; i < matrix.size(); i++) {
        for (int j = 0; j < matrix[0].size(); j++) {
          dfs(i, j, matrix);
        }
      }
      return matrix;
    }
};

This failed to work in this case:
[[1,1,1],[1,1,0],[1,1,1]]

A majr flaw here is that while nodes are being updated, we still count them as “visited” but that’s not correct.

BFS

Attempt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
class Solution {
    void push_n(vector<vector<int>>& q, unordered_set<int*>& s, int i , int j) {
      // push neightbor if not in set (and if value <= 1? optimize for later? we may wanto avoid any values already resolved)
      // we want to make sure we don't check any nodes
      int m = v[0].size() - 1;
      int n = v.size() - 1;

      // left
      if (j > 0) {
        if (s.find(&v[i][j-1]) == s.end()) {
          v.push_back([i,j-1]);
        }
      }

      // right
      if (j < m) {
        if (s.find(&v[i][j+1]) == s.end()) {
          v.push_back([i,j+1]);
        }
      }

      // up
      if (i > 0) {
         if (s.find(&v[i-1][j]) == s.end()) {
          v.push_back([i-1,j]);
        }
      }

      // down
      if (i < n) {
         if (s.find(&v[i+1][j]) == s.end()) {
          v.push_back([i+1,j]);
        }
      }
    }
public:
    vector<vector<int>> u pdateMatrix(vector<vector<int>>& v) {
        for (int i = 0; i < v.size(); i++) {
            for (int j = 0; j < v[0].size(); j++) {
                int dist = INT_MAX;
                if (j > 0)
                    dist = min(dist, v[i][j-1]);
                if (i > 0) dist = min(dist, v[i-1][j]);
                if (dist == 1) continue;
                int level = 0;
                vector<vector<int>> q;
                unordered_set<int*> vis;
                q.push_back([i,j]);
                vis.insert(&v[i][j]);
                while(!q.empty()) {
                    if (level >= dist) break;
                    bool done = false;
                    for(int len = q.size();len>0; len--) {
                        auto t = q.front();
                        q.pop();
                        int x = t[0];
                        int y = t[1];
                        if (v[x][y] == 0) {
                            done = true;
                            break;
                        }
                        vis.insert(&v[x][y]);
                        push_n(q, vis, x, y);
                    }
                    if (done) break;
                    level++;
                }
                dist = min(dist, level);
                v[i][j] = dist;
            }
        }
        return v;
  }
};

Accepted - very slow 😧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <vector>
#include <unordered_set>
using namespace std;

class Solution {
    void push_n(vector<vector<int>>& v, vector<vector<int>>& q, unordered_set<int*>& s, int i , int j) {
      // push neightbor if not in set (and if value <= 1? optimize for later? we may wanto avoid any values already resolved)
      // we want to make sure we don't check any nodes
      int m = v[0].size() - 1;
      int n = v.size() - 1;

      // left
      if (j > 0) {
        if (s.find(&v[i][j-1]) == s.end()) {
           vector<int> a = {i, j-1};
          q.push_back(a);
          //printf("pushed left %d %d\n", i, j-1);
        }
      }

      // right
      if (j < m) {
        if (s.find(&v[i][j+1]) == s.end()) {
            vector<int> a = {i, j+1};
          q.push_back(a);
        }
      }

      // up
      if (i > 0) {
         if (s.find(&v[i-1][j]) == s.end()) {
             vector<int> a = {i-1, j};
          q.push_back(a);
        }
      }

      // down
      if (i < n) {
         if (s.find(&v[i+1][j]) == s.end()) {
             vector<int> a = {i+1, j};
          q.push_back(a);
        }
      }

    }

public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& v) {
        for (int i = 0; i < v.size(); i++) {
            for (int j = 0; j < v[0].size(); j++) {
                int dist = INT_MAX;
                if (j > 0)
                    dist = min(dist, v[i][j-1]+1);
                if (i > 0) dist = min(dist, v[i-1][j]+1);
                if (dist == 1) continue;
                int level = 0;
                vector<vector<int>> q;
                unordered_set<int*> vis;
                vector<int> a = {i,j};
                q.push_back(a);
                vis.insert(&v[i][j]);
                while(!q.empty()) {
                    //cout << "level = " << level << endl;
                    if (level >= dist) break;
                    bool done = false;
                    for(int len = q.size();len>0; len--) {

                        vector<int> t = q.front();
                        q.erase(q.begin());
                        int x = t[0];
                        int y = t[1];
                        //cout << "got elem =" << v[x][y] << endl;
                        if (v[x][y] == 0) {
                            done = true;
                            break;
                        }

                        vis.insert(&v[x][y]);
                        push_n(v, q, vis, x, y);
                    }
                    if (done) break;
                    level++;
                }
                dist = min(dist, level);
                //cout << "dist = " << dist << endl;
                v[i][j] = dist;
            }
        }
        return v;
  }
};

I’m most likely checking too many nodes on every iteration. Need to come up with a better solution.

JavaScript Drum Kit

Preface

I’m investing a major portion of this month working on the JavaScript30 course by Wes Bos. The course is free and the content looks quite promising. It uses vanilla JS, so it looks like a decent way to build some JS chops without getting bogged down in JS framework hell. Here goes 🤞…

Day 1: JavaScript Drum Kit

In this section we build a fun little drumkit. The exercise files are here.

Step 1: Understand the CSS and HTML provided

  1. We see that there is a bunch of styles provided in style.css.
  2. The html links to that css in the head tag.
  3. We can use querySelector with data-xyz data attribute to get the right audio element for the selected key!

We define the key as part of the div below:

1
2
3
4
<div data-key="65" class="key">
  <kbd>A</kbd>
  <span class="sound">clap</span>
</div>

And there is a corresponding audio element on the page as follows:

1
<audio data-key="65" src="sounds/clap.wav"></audio>

Very Cool! 😎

Step 2: Hooking up the audio to the key event

To allow a key event to generate the correct audio we use a query selector in our event listener as follows:

1
2
3
4
5
6
const audio = document.querySelector(`audio[data-key="${e.keyCode}"]`);
if (audio) {
  /* rewind the audio clip so we can play as soon as user hits key */
  audio.currentTime = 0;
  audio.play();
}

The rewinding is important so that our clip plays as soon as key is hit.

Step 3: Animation

We want to apply a highlight to the key being played. This can be done by temporarily adding a new style and then removing it.

To do this, we need to get the element on which we need to apply the style using a query selector again. And we apply the playing class to it while it is playing.

See list of CSS selectors here.

However, we also need to be able to disable it once it has finished.

It turns out that there is a way to determine when a transition has stopped. We can use this as the trigger.

Working demo is here.
Code is here.

That’s all folks! 🤗

Good advice for any programmer

Came across this gem on hackernews the other day and thought it would be a good idea to keep it at hand for myself and for my daughter when she grows up. While it was originally meant for a budding programmer, I think it is more generally applicable to any aspiring learners in any field of study.

  1. Keep practicing. Practice makes perfect. Explore different languages, frameworks, and problem spaces (interfaces, servers, distributed systems, statistics, etc.) to see what you find most interesting. You will make mistakes, and that is okay. That is how you learn.

  2. Take frequent breaks. Programming is hard work. It can be truly exhausting, and you should not be afraid to step away and go for a walk or something.

  3. The most valuable people in the industry are called “T”s. i.e. people with a little bit of knowledge/experience across broad range of topics (the horizontal part of the letter T), but who have deep knowledge/experience in one or a couple particular topics (the vertical shaft of the letter T).

  4. Begin to develop the skill of taking feedback and accepting criticism. There’s a lot of people out there who will be quick to criticize everything you do if you put it out into the open. It’s a whole skill in itself to be able to interpret this feedback and separate the signal from the noise. Try to empathize with the person or group providing feedback and understand that their motives/perspective may be different from yours. Sometimes that’s a useful thing. Sometimes it’s a distraction.

  5. Don’t take things too personally. You are not your code. A criticism of your code is not a criticism of your character. The less you take things personally, the easier it is to work with others. After all, the most impressive systems require immense collaboration.

  6. Don’t take yourself too seriously. Have some fun with it! Programming is super fun, so you should ask yourself regularly “am I still having fun?”. If the answer is “No”, maybe find something else interesting to focus on for a bit.

  7. Broaden your perspective. Along the lines of #1 and #2, it’s important to maintain a broad perspective and push yourself to keep expanding your perspective. This doesn’t just apply to technical problem areas or languages or frameworks. The best engineers are good problem solvers because they have a broad perspective not just of the problem space but also more generally of the world they inhabit. Try to learn about different industries, cultures, people, and places. You will become a more well-rounded character for doing so, with a higher ability to empathize with others and understand the complex mechanics of how the world works.

  8. Be social. I made the mistake of hiding in my room on a computer for much of my childhood, and it wasn’t until high school that I really began to understand the value of social interaction and maintaining strong solid friendships. It’s as important to spend time away from the computer as it is to keep practicing.

Two Sum II

Problem

Givens

  • Your returned answers (both index1 and index2) are not zero-based.
  • You may assume that each input would have exactly one solution and you may not use the same element twice.

Analysis

  • Array is sorted, so we can exploit the fact and stop when we reach a certain threshold.
  • When we see sorted array, binary searches can be a viable option.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
      /* if array is all positives then bin search */
      if (numbers[0] >= 0) {
        int low = 0;
        int high = numbers.size() - 1;

        while (low <= high) {
          int mid = (low + high) / 2;
          if (numbers[mid])
        }
      }
    }
};

Two Sum

Problem

Analysis

The brute force way would be to check every two digits from the given list. This would be a O(n^2) solution which is not very useful. The other option I thought of was to sort the array first. Unfortunately, for the given problem sorting would accomplish nothing. Is there a way to solve this in O(n) time? Perhaps, if we could trade some extra space for time.

EDIT: sorting is actually useful! Have a look at Two Sum II.

First Attempt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
      /* keep track of numbers that we have
         encountered already from the input vector
      */
      unordered_set<int> set;
      vector<int> ans;
      for (int e: nums) {
        int remainder = target - e;
        /* if remainder already exists in our set then we are done */
        if (set.find(remainder) != set.end()) {
          ans.push_back(e);
          ans.push_back(remainder);
          break;
        }
        set.insert(remainder);
        set.insert(e);
      }
      return ans;
    }
};

The first attempt failed. I failed to read the complete requirement. The question is asking for a list of indices 🙄. And the other problem with this solution is that we are inserting remainder as well. This is wrong 🙀!!! We end up inserting numbers into the set that don’t even exist in the input.

Accepted

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
      /* keep track of numbers that we have
         encountered already from the input vector
      */
      unordered_map<int, int> m; // nums value --> nums index
      vector<int> ans;
      for (int i = 0; i < nums.size(); i++) {
        int remainder = target - nums[i];
        /* if remainder already exists in our map then we are done */
        if (m.find(remainder) != m.end()) {
          ans.push_back(i);
          ans.push_back(m[remainder]);
          break;
        }
        m.insert({nums[i], i});
      }

      sort(ans.begin(), ans.end());
      return ans;
    }
};

Lesson learned

Please read the question more carefully!!!

Reverse Linked List 2 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
      ListNode** s = &head;
      ListNode *a = nullptr, *b = nullptr;
      int i = 1;
      while (i < m - 1) {
        s = &((*s)->next);
        i++;
      }
      a = *s;
      b = (*s)->next;

      while (i < n) {
        i++;
        ListNode *tmp = b;
        b = b->next;
        tmp->next = a;
        a = tmp;
      }

      (*s)->next->next = b;
      (*s)->next = a;

      return head;

    }
};

This fails for input [5], 1, 1 since we always blindly try to do the reversal operations.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
      ListNode** s = &head;
      ListNode *a = nullptr, *b = nullptr;
      int i = 1;
      while (i < m - 1) {
        if (*s) {
          s = &((*s)->next);

        }
        i++;
      }
      a = *s;
      if (*s) {
        b = (*s)->next;
      }

      while (i < n) {
        i++;
        ListNode *tmp = b;
        if (b) b = b->next;
        if (tmp) tmp->next = a;
        a = tmp;
      }

      // always null check before deref
      if (*s && (*s)->next) {
        (*s)->next->next = b;
        (*s)->next = a;
      }

      return head;

    }
};

This fails when we have `[3,5], 1, 2`.

We never reverse it.

# Accepted Solution
```cpp
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
      ListNode** s = &head;
      ListNode *a = nullptr, *b = nullptr;
      int i = 1;
      if (m < n) {
          while (i < m ) {
            if (*s) {
              s = &((*s)->next);
            }
            i++;
          }
          a = *s;
          if (*s) {
            b = (*s)->next;
          }

          while (i < n) {
            i++;
            ListNode *tmp = b;
            b = b->next;
            tmp->next = a;
            a = tmp;
          }


          // always null check before deref
          if (*s && (*s)->next) {
            (*s)->next = b;
            *s = a;
          }
      }

      return head;

    }
};

Illustrated Explanations

Example 1

Example 2

Flatten Binary Tree

Problem

First Attempt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    TreeNode *postorder(TreeNode* root) {
        if (root == nullptr) return root;
        /* base case - if leaf node, then return itself */
        if (!root->left && !root->right) return root;

        TreeNode* leaf = root->left;
        /* left most node that is not leaf */
        if (root->left) {
            leaf = postorder(root->left);
        }

        /* Move my right subtree into the left leaf node */
        if (root->right) {
            postorder(root->right);
            leaf = root->right;
            root->right = nullptr;
        }

        return leaf;
    }
public:
    void flatten(TreeNode* root) {
        (void) postorder(root);
    }
};

Unfortunately this is not a correct solution. The problem does not explicitly talk about the order in which nodes need to appear in the final list, and I was assuming flattening with postorder to the left would work. But I was mistaken 😲!

Second Attempt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    TreeNode *postorder(TreeNode* root) {
        if (root == nullptr) return root;
        /* base case - if leaf node, then return itself */
        if (!root->left && !root->right) return root;

        TreeNode* leaf = postorder(root->left);


        /* Move my right subtree into the left leaf node */
        if (root->right) {
            postorder(root->right);
            if (leaf) leaf->left = root->right;
            else root->left = root->right;
            root->right = nullptr;
        }

        return leaf;
    }
public:
    void flatten(TreeNode* root) {
        (void) postorder(root);
    }
};

This was just an embarrassing regression and I would rather not talk about it too much :roll_eyes:. Suffice it to say, it bombed 💣.

Third Attempt

The problem actually has a requirement to flatten to the right. That was not explicitly stated in the question and is fixed here.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    TreeNode *postorder(TreeNode* root) {
        if (root == nullptr) return root;
        /* base case - if leaf node, then return itself */
        if (!root->left && !root->right) return root;

        TreeNode* left_leaf = postorder(root->left);

        /* Move my left subtree into the right */
        TreeNode* right_leaf = postorder(root->right);
        if (right_leaf) {
            right_leaf->right = root->left;
        }
        else {
            root->right = root->left;
        }
        root->left = nullptr;

        return right_leaf;
    }
public:
    void flatten(TreeNode* root) {
        (void) postorder(root);
    }
};

This solution actually does flatten the tree, but LeetCode is enforcing a specific order as well so this does not result in the correct answer.

Fourth Attempt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    TreeNode *traverse(TreeNode *root) {
        if (root == nullptr) return root;
        /* base case - if leaf node, then return itself */
        if (!root->left && !root->right) return root;

        TreeNode* left_leaf = traverse(root->left);
        TreeNode* right_leaf = traverse(root->right);

        // if we have a left leaf then attach left subtree
        // in between root and right subtree
        if (left_leaf) {
            left_leaf->right = root->right;
            root->right = root->left;
            root->left = nullptr;
        }

        /* right leaf is the the only leaf remaining, return this */
        return right_leaf;

    }
public:
    void flatten(TreeNode* root) {
        traverse(root);
    }
};

This solution does not account for the fact that when right subtree of a given root is null then the resultant right leaf will actually be the left leaf.

See diagram below.

TODO

Accepted Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    TreeNode *traverse(TreeNode *root) {
        if (root == nullptr) return root;
        /* base case - if leaf node, then return itself */
        if (!root->left && !root->right) return root;

        TreeNode* left_leaf = traverse(root->left);
        TreeNode* right_leaf = traverse(root->right);

        // if we have a left leaf then attach left subtree
        // in between root and right subtree
        if (left_leaf) {
            left_leaf->right = root->right;
            root->right = root->left;
            root->left = nullptr;
        }

        /* if right leaf was null then when we return leaf leaf */
        return (right_leaf?right_leaf:left_leaf);

    }
public:
    void flatten(TreeNode* root) {
        traverse(root);
    }
};

Lessons Learned

  1. Visualization is super important in tree related problems
  2. Always consider the cases of null subtrees
  3. Don’t give up!