YoungForest's blog

Today I participated in LeetCode weekly contest 117 and used a different strategy: writing the blog summary while solving the problems. I hoped this would record my real thoughts more faithfully and improve my blogging efficiency. The previous two times, writing the blog afterward always delayed things by several days.

965. Univalued Binary Tree

A very simple, almost silly problem. Direct DFS/BFS is enough. Since BFS can return immediately when it encounters an invalid node, it is more convenient. I chose a BFS implementation.

It is time for the weekend LeetCode weekly contest again. This time the result was not good. The main reason was that I wanted to solve both the second and third problems, and ended up solving neither. If I had focused all my time on the second problem, I probably could still have ACed it.

961. N-Repeated Element in Size 2N Array

This problem always felt like something I had already done on LeetCode before, and I still remembered the direction of the solution.
The idea is: since half of the elements are the same, randomly pick two elements and check whether they are equal. Probabilistically, there is a chance that it never finishes, but in practical use it works well.

I have not participated in LeetCode weekly contests for a while. Recently, because I am preparing for Google’s phone interview at the end of January, I need to pick algorithms back up again. Reviewing algorithm books is one part; the other part is preparing by solving problems. Since time is limited, LeetCode weekly contests are a good choice. The contest has a time limit, so it is closer to a real interview.
The weekly contest lasts one and a half hours, has four problems of different difficulty levels, and starts at 10:30 every weekend. Previously it was 9:30, maybe because of U.S. winter time, so it was delayed by one hour.
As before, I only completed two problems. For the third problem, I had some idea, later proven wrong. I glanced at the fourth problem and decisively gave up.
Below I share the ideas and solutions for the four problems. Of course, the latter two were completed afterward.

958. Check Completeness of a Binary Tree

Determine whether a tree is a complete binary tree.
For tree problems, recursion, BFS, and DFS are common tools. It is easy to see that BFS is the most suitable for this problem.
Once a node is found to be missing a child, set no_child to True. During the subsequent search, no other node is allowed to have children.

Merry Christmas!

There are still five days before 2019, and 2018 is about to end. A year passes so quickly. I wonder how your 2018 was. How many of the New Year’s plans you made a year ago did you accomplish?

In my 2017 New Year’s plan, I once wrote this passage:

Last week I sent my resume to a classmate interning at SenseTime and scheduled an interview with HR for this Thursday. On Friday I received another call from HR to discuss the offer. I have to say, SenseTime’s recruiting efficiency is really high. From another angle, this also reflects the fact that they are very short of people. Many SenseTime classmates asked me whether I had other classmates to recommend for internships.

SenseTime alumni are jokingly called the “BUAA lab,” because SenseTime has recruited a large number of BUAA interns, and many full-time employees were converted directly from internships. When I was an undergraduate, almost an entire class was interning there.

During my interview process, the person who referred me was a classmate who had been interning there for a long time. The first-round interviewer was the TA from my junior-year compiler lab. The second- and third-round interviewers were also my undergraduate classmates. So it can be said that if you are a BUAA student, entering SenseTime is much easier than for students from other schools.

Recently, because of English study needs, I often download large files from Baidu Cloud. As everyone knows, Baidu Cloud limits download speed. Without their membership, the download speed is only a few dozen KB/s. I really could not tolerate it, so I searched for speed-limit bypass tools and got the download speed up to 15 MB/s, haha. Sharing it here with everyone.
One thing to note: Baidu Cloud also updates its speed-limit mechanism to prevent abuse, so it is not surprising if the method in this article stops working. You can still search online for other updated methods. Trust the power of programmers.
As of November 5, 2018, this method is workable.

Copyright belongs to the author. For any form of reposting, please contact the author.
Author: YoungForest (from Douban)
Source: https://www.douban.com/note/694767558/

Recently I have kept feeling that I cannot control my own life.

First, which is more important: living happily, or working hard to become what others expect? Right now, I identify more with the latter. Since childhood, I have been the “other people’s child”: obedient, well-behaved, no video games, no early romance, no fighting, and good grades. But was that life happy? Not necessarily. Now, even after graduating from college and already becoming ordinary among the crowd, I still cannot avoid gradually living more and more like what others expect. I even think this kind of life seems more meaningful. At the end of the day, I am still a person in “society”. I need recognition from parents, classmates, teachers, and friends in order to keep going.

The key point of this problem is understanding “average O(1) time”, which is also an important concept in time-complexity analysis: “amortized”.
In Algorithms, Fourth Edition, the analysis of many data-structure operations uses this method. So “amortized time complexity” is often associated with operations on the corresponding data structure. When I interviewed at Megvii in May, the second problem asked me to construct a queue data structure that maintains the maximum value, and the final requirement was that the operation time complexity be “amortized O(1)”. Unfortunately, at that time I was not familiar with the concept of “amortized”. I could analyze worst-case time complexity, and although I eventually derived the correct answer under the interviewer’s guidance, the final result was predictably no hire.

Description: https://leetcode.com/problems/insert-delete-getrandom-o1/description/
Solution: None
Difficulty: Medium

answer

I happened to encounter this classic problem during my interview at JingChi. It was asked by Eric in the second round. I had not done this problem before, but I had done the related 2Sum problem, after all it is the first LeetCode problem and probably many people have done it. Also, when Algorithms, Fourth Edition discusses algorithm complexity, it uses the same kind of problem, though the details may differ, such as requiring no duplicate triplets in the result. I still had some impression of it at the time. I smoothly wrote an O(n^2) time-complexity solution, although afterward I found small bugs, such as list sort being in-place. But it did not really matter.
Today I organized the solution from the interview, submitted it, and unexpectedly got Time Limit Exceeded.

Description: https://leetcode.com/problems/3sum/description/
Solution: None
Difficulty: Medium

Solution During the Interview

I have not practiced LeetCode for four weeks. On one hand, the sense of urgency decreased; on the other, I lacked execution.
Recently I have another interview to prepare for: an algorithm intern interview for the video team at Xiaohongshu.
On one side, I need to look at machine learning knowledge to avoid repeating the mistakes from the Kuaishou interview; on the other, I need to review my coding ability. Sure enough, after four weeks without practicing, I can no longer even write code well. As a future programmer, how can poor coding ability be acceptable? I still need to start practicing LeetCode again in a planned way.

Description: https://leetcode.com/problems/divide-two-integers/description/
Solution: none
Difficulty: Medium

Brute Approach