Accepted

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
      // if the letter is bigger than the biggest in our sorted input then
      // just pick the smallest one since letters "wrap around"
      if (letters.back() <= target) return letters[0];

      int low = 0;
      int high = letters.size() - 1;
      char res;

      while (low <= high) {
        int mid = low + (high - low)/2;
        if (letters[mid] <= target) {
          low = mid + 1;
        } else {
          res = letters[mid];
          high = mid - 1;
        }
      }

      return res;
    }
};

I recently decided to apply for a VISA to India and needed to get a passport photo made. The tutorial here proved to be useful.

Capturing some notes from my own experience.

Problem

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.

Note: Your algorithm should run in O(n) time complexity and O(1) space complexity.

Example 1:

Input: [1,2,3,4,5]
Output: true

Example 2:

Input: [5,4,3,2,1]
Output: false

Requirements

• return whether an increasing subsequence of length 3 exists or not
• Your algorithm should run in O(n) time complexity and O(1) space complexity.
• Return true if there exists i, j, k such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.

Examples

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Given [1,20,5, 4,34,3,4,5]

Let's define an array of size two as follows
sub = [INT_MAX, INT_MAX, INT_MAX]

iterate through given
i = 0
sub = [1, INT_MAX, INT_MAX]

i = 1
sub = [1, 20, INT_MAX]

i = 2
sub = [1, 5, INT_MAX]

i = 3
sub = [1, 4, INT_MAX]

i = 4
sub = [1, 4, 34]

First Attempt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int sub[] = {INT_MAX, INT_MAX};
        for (int e: nums) {
            if (e < sub[0]) {
                sub[0] = e;
            } else if (e < sub[1]) {
                sub[1] = e;
            } else {
                return true;
            }
        }
        return false;
    }
};

This fails for the following input.

1

[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]

Problem

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Note:

There may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n^2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

Constraints etc

• Your algorithm should run in O(n^2) or better complexity.
• subsequence need not consist of adjacent numbers

Accepted quadratic

TBD

Accepted logarithmic

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

class Solution {
    int get_index(vector<int>& vec, int val) {
      int low = 0;
      int high = vec.size() - 1;
      while (low <= high) {
          int mid = low + (high - low) / 2;
          if (vec[mid] < val) {
               low = mid + 1;
          } else if (vec[mid] > val) {
               high = mid - 1;
          } else return mid;
      }
      return low;
    }
    void pr(vector<int>& vec) {
      cout << "{ ";
      for (auto e: vec) {
        cout << e << ", ";
      }
      cout << " } \n";
    }
public:
    int lengthOfLIS(vector<int>& nums) {
      vector<int> tails;

      for (int i = 0; i < nums.size(); i++) {
        //cout << "index = " << i << endl;
        int pos = get_index(tails, nums[i]);
        //cout << "pos = " << pos << endl;
        //cout << " Before :";
        //pr(tails);
        if (pos == tails.size()) { tails.push_back(nums[i]); }
        else { tails[pos] = nums[i]; }
        //cout << " After :";
         //pr(tails);
      }
      return tails.size();

    }
};

Understanding the resultant array

Given this example [8, 2, 5, 1, 6, 7, 9, 3]
And the resultant array sub = [1, 3, 6, 7, 9]

Let’s look at the each of the values in sub and use the given input array to see the possible subsequences for each size.
At index 0, 1 is the smallest tail that can give us a subsequence of size 1
At index 1, 3 is the smallest tail that can give us a subsequence of size 2, [1,3] or [2,3]
At index 2, 6 is the smallest tail that can give us a subsequence of size 3, [2,5,6]
At index 3, 7 is the smallest tail that can give us a subsequence of size 4, [2,5,6,7]
At index 4, 9 is the smallest tail that can give us a subsequence of size 5, [2,5,6,7,9]

For index 0, we can basically pick any element. But, 1 is the smallest value possible. By ordering the elements in sub in ascending order we are trying to ensure that the largest number in the subsequence ending at each position (i.e. the tail) is as small as possible. This means that we can maximize the probability of being able to pick subsequent subsequences of length 4, 5 etc.
When we select 9 for a subsequence of length 1, we can no longer pick any other increasing numbers that result in an increasing subsequence.

As another example, for subsequence of size 3, the possible subsequences are [2,5,6] [2,6,7] [2,7,9] [5,6,7] [1,6,7] [6,7,9]. Our algorithm ended up picking [2,5,6] by placing the 6 at that position.

Problem

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Example 1:

Input: 121
Output: true

Example 2:

Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Could you solve it without converting the integer to a string?

Constraints

1. don’t convert to string
2. Negatives are automatically disqualified

Approach

1. We can push all digits to an array and check start and end as we converge pointers
2. To avoid using O(n) extra space, we can generate a reversed number of the original and compare

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
public:
    bool isPalindrome(int x) {
      if (x < 0) return false;
      int reversed = 0;
      int temp = x;
      while (temp) {
        int digit = temp % 10;
        reversed = reversed*10 + digit;
        temp /= 10;
      }
      return (reversed == x);
    }
};

Test cases

1. negative numbers
2. 1234
3. Large numbers to see if we get time out
4. test 0 and other single digits

Problem

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

Example:

Input: 38
Output: 2
Explanation: The process is like: 3 + 8 = 11, 1 + 1 = 2.
Since 2 has only one digit, return it.

Follow up:
Could you do it without any loop/recursion in O(1) runtime?

Accepted Non-optimal

The O(N) solution involves using some bitwise operations.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    int addDigits(int number) {
      while(number > 9) {
        int n = number;
        int sum = 0;
        while (n) {
          int digit = n % 10;
          sum += digit;
          n /= 10;
        }
        number = sum;
      }
      return number;
    }
};

Optimal

The best solution works in O(1) time! Because of a mathematical property. However, I need to fully get it before I can discuss it further. Stay tuned.

Technology is the not the endgame. It is the tool we use to accomplish the real endgame.

But what is that end-game? Technology was supposed to be the enabler of a better life. It was supposed to free us from the bondage of physical labour.

Sometimes I come across interesting projects and think to myself, “this would be a real cool project!” and then I forget about it. Even if I bookmark it. Creating a dedicated page to hopefully revisit such projects at a later date.

Weekend Scope

• Surprising small isometric game using SDL
• Handcrafting TCP/IP packets for a better understanding

More than a week or so

• TODO

More than a month

• Obey the testing goat - whimsical test-driven django

  • Started this a while ago. But got caught up with other things. Would love to come back and finish this.

• Javascript30

  • I had started this, but taking a hiatus for the time being

Tech talks

• Building a bank with Go

Cool open-source projects to study

• Katran - L4 load balancing from Facebook
• Flutter

Startup Resources

• Selling software online
• Personal Developer Can Beat Big Company with User Support

In this post, I am capturing some notes to fully evaluate whether using Kotlin to build a MVP is a viable option. There has some buzz around it lately (mostly in Android land). However, since it works on the JVM, it would seem to be a good option for backend development as well. The other benefit of this is that we can leverage the same skillset for the frontend Android app for our service.

Benefits

• Strong typing
• JVM performance

Tradeoffs

• no namespace
• no static modifier

References

• Kotlin the good bad and ugly
• Vert.x
• https://engineering.khanacademy.org/posts/kotlin-adoption.htm
• Algorithms in Kotlin

Problem

An undirected, connected graph of N nodes (labeled 0, 1, 2, …, N-1) is given as graph.

graph.length = N, and j != i is in the list graph[i] exactly once, if and only if nodes i and j are connected.

Return the length of the shortest path that visits every node. You may start and stop at any node, you may revisit nodes multiple times, and you may reuse edges.

1
2
3
4
5
6
7
8
9
10
11

Example 1:

Input: [[1,2,3],[0],[0],[0]]
Output: 4
Explanation: One possible path is [1,0,2,0,3]

Example 2:

Input: [[1],[0,2,4],[1,3,4],[2],[1,2]]
Output: 4
Explanation: One possible path is [0,1,4,2,3]

Note:

• 1 <= graph.length <= 12
• 0 <= graph[i].length < graph.length