LeetCode Weekly Contest 130

So… Simply put, I've been playing with the Competitive Programming these days. This article is mainly some nonsense about my recent life in intership interviews and a simple review of the Weekly Contest 130 on LeetCode as a (good?) start of a regular (might not) review article in following weeks.

Whiteboard Interviews?

To be honest, the reason is mainly for my recent experience of struggling with the summer internships applications for some companies. If you ever got to know the situtation where companies hire student for interships or long-term jobs, you might've heard that they normally don't require much experience about software engineering from student applicants. But, of course, if one is able to show these abilities, they is surely welcome.

Let's talk about interviews then. Either students or matural ready workers are expected by themselves and interviewers to be able to show skills as much as possible during the interview session. But it's not possible to get interviewers know all the things that you want them know about you in such a short time. In most cases, it comes to a scene where the interviewers ask and the interviewee answer. In software engineering domain, it's more obvious that a interviewee will get a sequence of different aspects of knownledge of technical questions put forward by interviewer and answer them correctly as expected. The most frightening part is "whiteboard interview", or so-called "coding interview".

Typically, interviewers will ask you to work out a solution on the spot by writing your code on a whiteboard while the interviewing team observes and peppers you with questions. The problem may take up to an hour to solve, and the entire interview may last a day. - Everything You Need to Know to Rock Your Next Whiteboard Test

Though it's called "whiteboard" interview, an interviewee is possibly required to write down code on a online realtime co-coding website or screenshare remotely to show the work in their own IDE if it's a remote interview.

I've been through multiple interviews in the past month. I applied for interships in Tencent, Alibaba, Bytedance. They share the similarity that interviewers normally gives you one or many questions no matter how impressive your introduction is or how well your answers to their previous questions. (Yeah, of course…)

So what's frightening? It's tension you may get during the coding and the embrassing occured when you can't get them sovled. During the session, you are watched by interviewer and are apparently not allowed to check the documentation or stackoverflow for hints, etc. The bad results might leads you to a position where the demostrating shows a bad understanding of the behaviours of the program or breaks the good impression just minutes before.

The difficulties of problems are varied. Most of them are quite easy if you don't make silly mistakes and be careful. While some are hard that might requires you to do much training before it happens.

For example, some questions impressed me during my past interviews:

Little Q is the CEO of an IT company. The company has N engineers, and each engineer has different programming abilities. The salary given by Little Q is related to the ability ranking of the engineer. If an engineer ranks Xth in the ability ranking from small to large, and the engineer's programming ability is Y, then the engineer's salary is Y - X yuan per month.

Now given the programming ability value of these N engineers. Little Q asked M questions. For each question, he will give a number K, asking for how many programmers in this company has got a salary for K yuan per month.

(Followed by some samples...)

This is my first whiteboard interview question. I wrote in JavaScripts but failed. I passed all the custom tests however failed in some cases where it gave me "time exceeded". I.e. Not a good solution in algorithm, like big complexity or so.

Another easy-to-understand example:

There are a total of 10 stairs. Each time you can go 1, 2 or 3 stairs, how many ways to finish these stairs.

This is a classic dynamci programming quesiton. However I only got to know this after the interview finished. My answer in interview are kept by the online interview website (thanks?):

function calc(steps) {
    const goToNext = (remain) => {
        if (remain - 1 === 0) {
            return 1
        } else if (remain - 2 === 0) {
            return 2
        } else if (remain - 3 === 0) {
            return 4
        }
        return goToNext(remain - 1) + goToNext(remain - 2) + goToNext(remain - 3)
    }
    return goToNext(steps)
}

console.log(calc(10))

In such a short time, I was only able to come up with a recursive way to solve it, which is obviously not a good approach. As asked by the interviewer as well, I admitted that if the given number is too large, it would take so much time to figure out the answer, or even causes stack overflow. So the following question is how to improve it. Ha… I was thinking about tail recursion to save the space or something and failed. If you are curious, one good solution is dynamic programming. Yeah, go search to explore your world.

Just another different example to show that some questions may not directly lead to the algorithm part. They just test your understanding of languages:

Find the same characters in two strings.

function findChars(str1, str2) {
    const obj = {}
    str1.split("").forEach(c => {
        obj[c] = 1
    })
    const allChars = []
    str2.split("").forEach(c => {
        obj[c] && allChars.push(c)
    })
    return allChars
}

(Don't ask me why my answers are all in JavaScript. Because I applied for frontend engineering...)

You may question why interviewers love to ask these hard things that are never gonna happen in real work. Well, it annoies me as well. As far as I know, job interviews for student in UK is not so much hard. Though there's also whiteboard question, it's more about soring solution or so. But things in China is not easy because we have many people to compete for a limited number of work positions… Yeah, just a personal opinoin for now. You also have to say that it does show your skills in some way.

Alright, I think that's enough. You may have found that most questions requires your good knowledge of improving the algorithm of solutions. That leads me here - trying to explore the world of competive programming… (Hmm…) Just to clarify, I found it also really interesting. I'm not only chasing for a job application.

So, LeetCode, right? Just consider it as a training website. You can work out problems there. It also holds contest per week.

Weekly Contest

Aaaalright, this week, I didn't participate in because it started at 3.30 a.m. yesterday in UK. I just gave a quick look (at the virual contest) and try after the contest today. I'll try to attend the next contests. Hope that it'll give me some progress.

Btw, I decided to use CPP as the language to solve problem.

1018. Binary Prefix Divisible By 5

Problem

Given an array A of 0s and 1s, consider N_i: the i-th subarray from A[0] to A[i] interpreted as a binary number (from most-significant-bit to least-significant-bit.)

Return a list of booleans answer, where answer[i] is true if and only if N_i is divisible by 5.

Example 1:

Input: [0,1,1]
Output: [true,false,false]
Explanation: 
The input numbers in binary are 0, 01, 011; which are 0, 1, and 3 in base-10.  Only the first number is divisible by 5, so answer[0] is true.

Example 2:

Input: [1,1,1]
Output: [false,false,false]

Example 3:

Input: [0,1,1,1,1,1]
Output: [true,false,false,false,true,false]

Example 4:

Input: [1,1,1,0,1]
Output: [false,false,false,false,false]

Note:

1. 1 <= A.length <= 30000
2. A[i] is 0 or 1

https://leetcode.com/contest/weekly-contest-130/problems/binary-prefix-divisible-by-5/

Solution

(Just found that LeetCode allows you to use standard libraries with writing #include, which is totally great!)

The idea is that the decimal number at this bit is the decimal number at the previous bit doubled and plusing this bit.

Example:

[0,1,1]
// start with 0
0 // -> 0 * 2 + 0 = 0
1 // -> 0 * 2 + 1 = 1
1 // -> 1 * 2 + 1 = 3

So, the answer:

class Solution {
public:
    vector<bool> prefixesDivBy5(vector<int>& A) {
        vector<bool> ans;
        int num = 0;
        for (int i = 0; i < A.size(); i++) {
            num = (num * 2 + A[i]) % 5;
            ans.push_back(num == 0);
        }
        return ans;
    }
};

Also note that we don't need keep the num summed up. In each step, we can just make it a remainder of dividing by 5.

1017. Convert to Base -2

Problem

Given a number N, return a string consisting of "0"s and "1"s that represents its value in base **-2** (negative two).

The returned string must have no leading zeroes, unless the string is "0".

Example 1:

Input: 2
Output: "110"
Explantion: (-2) ^ 2 + (-2) ^ 1 = 2

Example 2:

Input: 3
Output: "111"
Explantion: (-2) ^ 2 + (-2) ^ 1 + (-2) ^ 0 = 3

Example 3:

Input: 4
Output: "100"
Explantion: (-2) ^ 2 = 4 

Note:

1. 0 <= N <= 10^9

https://leetcode.com/contest/weekly-contest-130/problems/convert-to-base-2/

Solution

Another binary problem which is also easy. It's the same idea of converting to base-2.

class Solution {
public:
    string baseNeg2(int N) {
        if (N == 0) {
            return "0";
        }
        string ans;
        while (N != 0) {
            int r = abs(N % -2);
            ans = to_string(r) + ans;
            N = (N - r) / -2; // note: not N = N / -2;
        }
        return ans;
    }
};

1019. Next Greater Node In Linked List

Problem

We are given a linked list with head as the first node. Let's number the nodes in the list: node_1, node_2, node_3, ... etc.

Each node may have a next larger value: for node_i, next_larger(node_i) is the node_j.val such that j > i, node_j.val > node_i.val, and j is the smallest possible choice. If such a j does not exist, the next larger value is 0.

Return an array of integers answer, where answer[i] = next_larger(node_{i+1}).

Note that in the example inputs (not outputs) below, arrays such as [2,1,5] represent the serialization of a linked list with a head node value of 2, second node value of 1, and third node value of 5.

Example 1:

Input: [2,1,5]
Output: [5,5,0]

Example 2:

Input: [2,7,4,3,5]
Output: [7,0,5,5,0]

Example 3:

Input: [1,7,5,1,9,2,5,1]
Output: [7,9,9,9,0,5,0,0]

Note:

1. 1 <= node.val <= 10^9 for each node in the linked list.
2. The given list has length in the range [0, 10000].

https://leetcode.com/contest/weekly-contest-130/problems/next-greater-node-in-linked-list/

Solution

Just use double loops for this. The outer loop pushes the next larger number into the ans vector. The inner loop keeps track of next nodes until it comes to a larger one.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> nextLargerNodes(ListNode* head) {
        vector<int> ans;
        while (head != NULL) {
            ListNode* current = head;
            while (current != NULL && current->val <= head->val)  {
                current = current->next;
            }
            if (current == NULL) {
                ans.push_back(0);
            } else {
                ans.push_back(current->val);   
            }
            head = head->next;
        }
        return ans;
    }
};

1020. Number of Enclaves

Problem

Given a 2D array A, each cell is 0 (representing sea) or 1 (representing land)

A move consists of walking from one land square 4-directionally to another land square, or off the boundary of the grid.

Return the number of land squares in the grid for which we cannot walk off the boundary of the grid in any number of moves.

Example 1:

Input: [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
Output: 3
Explanation: 
There are three 1s that are enclosed by 0s, and one 1 that isn't enclosed because its on the boundary.

Example 2:

Input: [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
Output: 0
Explanation: 
All 1s are either on the boundary or can reach the boundary.

Note:

1. 1 <= A.length <= 500
2. 1 <= A[i].length <= 500
3. 0 <= A[i][j] <= 1
4. All rows have the same size.

https://leetcode.com/contest/weekly-contest-130/problems/number-of-enclaves/

Solution

I didn't get much time to finish this one. The idea is to check the boundary first and mark all 1's to 2's. And shrink to check the next "boundaries". If there's a 2 in a 1's up, down, left, or right position, also mark it as 2. Finally, we count all remaining 1's.

See you next week...