LeetCode 75 (I)

I’ve spending way too much time on basic data structure recently because I felt so incompetent about how to use them wisely. And still quite don’t understand how to prepare for a technical interview. Although as a relatively senior developer, data structure/algorithm still feels like my weak spot.

While I was traveling to Philippine a couple of weeks ago. A Japanese recruiter sent me a pre-interview invitation for a fintech company based in Tokyo. Although I don’t feel like I’m ready for anything, and I’m not even actively applying for jobs right now… But I still accepted it.

Since I accidentally got a job interview. I think it’s about time to put my skill into the test once again after almost two years. And get some practical… Or maybe I should say “practical for a job interview setup” exercise.

Question 1768: Merge Strings Alternately

This is the first question in the LeetCode 75 collection. And it should be super simple for everyone with just a little bit of coding experience.

And the following is the description of this question.

You are given two strings word1 and word2. Merge the strings by adding letters in alternating order, starting with word1. If a string is longer than the other, append the additional letters onto the end of the merged string.

Return the merged string.

Example 1:

Input: word1 = "abc", word2 = "pqr"
Output: "apbqcr"
Explanation: The merged string will be merged as so:
word1:  a   b   c
word2:    p   q   r
merged: a p b q c r

Example 2:

Input: word1 = "ab", word2 = "pqrs"
Output: "apbqrs"
Explanation: Notice that as word2 is longer, "rs" is appended to the end.
word1:  a   b 
word2:    p   q   r   s
merged: a p b q   r   s

Example 3:

Input: word1 = "abcd", word2 = "pq"
Output: "apbqcd"
Explanation: Notice that as word1 is longer, "cd" is appended to the end.
word1:  a   b   c   d
word2:    p   q 
merged: a p b q c   d

Here’s my steps to solve the problem.

• Define an out variable as my answer.
• Find the longest string to determine how many loops do I need. This can be achieved by Math.max.
• And if the string contains i characters, append into my out.

Constraints:

• 1 <= word1.length, word2.length <= 100
• word1 and word2 consist of lowercase English letters.

function mergeAlternately(word1: string, word2: string): string {
    // step 1
    let out = '';
    // step 2
    const len = Math.max(word1.length, word2.length);
    for(let i = 0; i < len; i++) {
        // step 3
        if(word1[i]) {
            out += word1[i];
        }
        if(word2[i]) {
            out += word2[i]
        }
    }
    return out;
};

And that’s it. It’s probably not the most efficient code. But the time complexity is O(n) as it only loop through the longest input’s length. Not so terrible, I’m fine with it.

Question 1071: Greatest Common Divisor of Strings

The second question from LeetCode 75. Seemingly easy, but a bit tricky.

For two strings s and t, we say "t divides s" if and only if s = t + t + t + ... + t + t (i.e., t is concatenated with itself one or more times).

Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.

Example 1:

Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"

Example 2:

Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"

Example 3:

Input: str1 = "LEET", str2 = "CODE"
Output: ""

Constraints:

• 1 <= str1.length, str2.length <= 1000
• str1 and str2 consist of English uppercase letters.

Since this is about “Greatest common divisor”, so maybe I can work on this first. First of all, let me create a helper function that can find the greatest common divisor between two numbers.

function gcd(a: number, b: number) {
    if(!b) return a;
    return gcd(b, a % b);
}

Now, we can use this helper function to find the greatest common divisor between the two strings.

function gcdOfStrings(str1: string, str2: string): string {
    // find the greatest common divisor
    const n = gcd(str1.length, str2.length);
    const sub1 = str1.substr(0, n);
    const sub2 = str2.substr(0, n);
    if(sub1 !== sub2) return '';
    return sub1;
};

But here comes a problem. If str1 is ABCDEF, and str2 is ABC, this solution will fail.

So, let’s think about the base case. Since the inputs are formed by repeated sub-string. So, if we concatenate them together, they should always be the same.

If str1 is ABCABC and str2 is AB, ABABCABC !== ABCABCAB. So, we know they don’t have a common divisor string.

If str1 is ABABAB and str2 is AB, ABABABA === ABABABA. Then we know they do have common divisor of AB.

function gcdOfStrings(str1: string, str2: string): string {
    // base case, the concatenation of two string should be equal
    if(str1 + str2 !== str2 + str1) return ''
    return str1.substr(0, gcd(str1.length, str2.length));
};

With the base case, this can be our valid solution. And it has a decent time complexity, since we are not loop through the whole string, the only thing… Well theoretically only thing that increase the time complexity is the gcd recursion, and it creates O(log(n)) or something similar… I’m bad at this… It could be better to use iterative approach to calculate the greatest common divisor if we really need to be super anal about it.

Question 1431: Kids With the Greatest Number of Candies

There are n kids with candies. You are given an integer array candies, where each candies[i] represents the number of candies the ith kid has, and an integer extraCandies, denoting the number of extra candies that you have.

Return a boolean array result of length n, where result[i] is true if, after giving the ith kid all the extraCandies, they will have the greatest number of candies among all the kids, or false otherwise.

Note that multiple kids can have the greatest number of candies.

Example 1:

Input: candies = [2,3,5,1,3], extraCandies = 3
Output: [true,true,true,false,true] 
Explanation: If you give all extraCandies to:
- Kid 1, they will have 2 + 3 = 5 candies, which is the greatest among the kids.
- Kid 2, they will have 3 + 3 = 6 candies, which is the greatest among the kids.
- Kid 3, they will have 5 + 3 = 8 candies, which is the greatest among the kids.
- Kid 4, they will have 1 + 3 = 4 candies, which is not the greatest among the kids.
- Kid 5, they will have 3 + 3 = 6 candies, which is the greatest among the kids.

Example 2:

Input: candies = [4,2,1,1,2], extraCandies = 1
Output: [true,false,false,false,false] 
Explanation: There is only 1 extra candy.
Kid 1 will always have the greatest number of candies, even if a different kid is given the extra candy.

Example 3:

Input: candies = [12,1,12], extraCandies = 10
Output: [true,false,true]

Constraints:

• n == candies.length
• 2 <= n <= 100
• 1 <= candies[i] <= 100
• 1 <= extraCandies <= 50

I think this one is easy to come up a O(n) solution, with two loops. We find the kids with most candies with the first loop and give candies to each kid to see if they can have at least the same number of candies as our target.

function kidsWithCandies(candies: number[], extraCandies: number): boolean[] {
    const result: boolean[] = new Array(candies.length);
    let target = 0;
    for(let i = 0; i < candies.length; i++) {
        if(candies[i] > target) target = candies[i];
    }
    for(let i = 0; i < candies.length; i++) {
        if(candies[i] + extraCandies >= target) {
            result[i] = true;
        } else {
            result[i] = false;
        }
    }
    return result;
};

With the big O notation convention, two parallel loops won’t increase our time complexity. So, this is somewhat acceptable.

For now, I don’t think I can make it more efficient in terms of time complexity. Although there’s way to make it shorter, and with some JavaScript’s internal optimization it can be faster. But in the grand scheme of things, I don’t think it will make the solution any better.

Question 605: Can Place Flowers

You have a long flowerbed in which some of the plots are planted, and some are not. However, flowers cannot be planted in adjacent plots.

Given an integer array flowerbed containing 0's and 1's, where 0 means empty and 1 means not empty, and an integer n, return true if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule and false otherwise.

Example 1:

Input: flowerbed = [1,0,0,0,1], n = 1
Output: true

Example 2:

Input: flowerbed = [1,0,0,0,1], n = 2
Output: false

Constraints:

• 1 <= flowerbed.length <= 2 * 104 (this should be 10 power of 4)
• flowerbed[i] is 0 or 1.
• There are no two adjacent flowers in flowerbed.
• 0 <= n <= flowerbed.length

To achieve O(n) of this question is simple too. But there’s some corner case need to be noted. All we need to do is create a loop, and when we are on a slot that is 0, we then check if the i+1 and i — 1 are both 0, or if it’s out of bounds, then we can plant the flow in the slot.

function canPlaceFlowers(flowerbed: number[], n: number): boolean {
    for (let i = 0; i < flowerbed.length; i++) {
        if(n === 0) break;
        if (
            flowerbed[i] === 0
            && !flowerbed[i - 1]
            && !flowerbed[i + 1]
        ) {
            flowerbed[i] = 1
            n--;
        }
    }
    return n === 0;
};

Question 345: Reverse Vowels of a String

This one kind of makes me paused a little bit, I’m not sure it’s because I’m already feeling some fatigue or anything. But it’s still an easy array question.

This is the description:

Given a string s, reverse only all the vowels in the string and return it.

The vowels are 'a', 'e', 'i', 'o', and 'u', and they can appear in both lower and upper cases, more than once.

Example 1:

Input: s = "hello"
Output: "holle"

Example 2:

Input: s = "leetcode"
Output: "leotcede"

Constraints:

• 1 <= s.length <= 3 * 105 (this should be 10 power of 5)
• s consist of printable ASCII characters.

This is my steps to solve it…

• Create a table that store all the vowels
• And then create two pointers, one start from the beginning, one from behind.
• While the two pointers do not meet each other, we loop.
• When one pointer is a vowel, we stop there. Until another pointer encounter a vowel, we swap them.
• And move the pointers if there’s no vowel, or when we swap.

const vowels = { a: true, e: true, i: true, o: true, u: true, A: true, E: true, I: true, O: true, U: true };

function reverseVowels(s: string): string {
    const arr = s.split('')
    let i = 0;
    let j = s.length - 1;
    while (i <= j) {
        if (vowels[s[i]] && vowels[s[j]]) {
            arr[i] = s[j];
            arr[j] = s[i];
            i++, j--;
        } else if(!vowels[s[i]]) {
            i++;
        } else {
            j--;
        }
    }
    return arr.join('')
};

I’m actually not sure if it’s better if we don’t make a string array, instead of swap the characters on the spot? But my guess in JavaScript it’s probably not that important because it’s inherently slow…

And here concludes all the easy part of Array questions in LeetCode 75 collection.

Actually, I don’t really care about if I can get this job or not. I think I would be excited if I received the invitation from this company back in 2 ~ 3 years ago. But consider the cost of living and the salary/tax/exchange rate situation in Japan right now, this could definitely make me poorer than what I’m having right now. And I do feel like I have some other place to go, I don’t know…

But I guess why not?