I applied for ByteDance’s early batch, for a backend development role in the Technology Middle Platform.
I did not review computer science fundamentals well enough, so my answers were poor.
Wishing for an offer.

First Round

Self-introduction.

I lost a lot of time debugging the last problem. In the end, I found that the cache in the range function was written incorrectly because I modified the function parameters. I must remember in the future to mark memoized parameters as const.
For the third problem, I could not think of a more efficient DP solution and kept getting TLE.

1475. Final Prices With a Special Discount in a Shop

My contest ability has declined recently. In last night’s biweekly contest, I also failed to solve one Q3, and now I failed to solve the last problem. I am not familiar with binary lifting on trees for Q4.

1480. Running Sum of 1d Array

This week’s problems were not too hard. It was a speed contest for problems 3, 4, 5, and 6, and the last 1,000 people got AK.
I was reasonably fast on the first three problems, but spent a relatively long time on the last one and got TLE twice because of implementation issues. I originally thought I did pretty well, but after seeing the ranking I realized everyone was very strong. I still need to keep working hard and try to get my rating into the global top 500.

1470. Shuffle the Array

A speed contest of decent quality. Some problems are worth thinking about: only after discovering the essence can you solve them quickly.

1460. Make Two Arrays Equal by Reversing Sub-arrays

This week’s last problem was honestly quite difficult and involved probability, combinatorics, and related knowledge. It happened to hit a blind spot in my knowledge, so I did not solve it. Students who are strong in math should have a much easier time with it.

1464. Maximum Product of Two Elements in an Array

Reference: C++ Standard Library: A tutorial and reference, Second version Chapter 7.9.2: Creating and Controlling unordered Container

All solutions I found in Google use XOR to generate hashcode of pair, which is totally bad. see why-is-xor-the-default-way-to-combine-hashes. However, the book has given us the best solution, using hash_combine, which is taken from Boost. The solution is much better than XOR when I tested it in Online Judge(Atcoder). I organized the code as a template as follow. You can copy and paste it as much as you can. And it is convenient to change it to fit any custom struct/class.

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

#include <functional>
// from boost (functional/hash):
// see http://www.boost.org/doc/libs/1_35_0/doc/html/hash/combine.html template
template <typename T>
inline void hash_combine(std::size_t &seed, const T &val) {
    seed ^= std::hash<T>()(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
// auxiliary generic functions to create a hash value using a seed
template <typename T> inline void hash_val(std::size_t &seed, const T &val) {
    hash_combine(seed, val);
}
template <typename T, typename... Types>
inline void hash_val(std::size_t &seed, const T &val, const Types &... args) {
    hash_combine(seed, val);
    hash_val(seed, args...);
}

template <typename... Types>
inline std::size_t hash_val(const Types &... args) {
    std::size_t seed = 0;
    hash_val(seed, args...);
    return seed;
}

struct pair_hash {
    template <class T1, class T2>
    std::size_t operator()(const std::pair<T1, T2> &p) const {
        return hash_val(p.first, p.second);
    }
};

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    unordered_map<pair<ll, ll>, ll, pair_hash> slopeCount;
    unordered_set<pair<ll, ll>, pair_hash> seen;
    return 0;
}

Today, while solving an AtCoder problem, one test case kept getting TLE. I studied the difference between that test case and the others, but could not figure it out no matter how hard I thought. Later, I replaced unordered_map with map and it passed. Although the difference between HashMap and TreeMap is not large on small datasets, HashMap should still be better when the data volume is large. So the best practice is to use a HashMap when ordering is not needed.

I had also never encountered a case before where HashMap performed so much worse than TreeMap. After spending the whole morning on it, I finally located the issue: my hash function implementation for pair was terrible. Since the C++ STL does not provide a hash specialization for pair, if you want to use pair as a key in unordered_map, you need to implement the hash function yourself. I had directly copied an implementation from the internet: std::hash<T>()(pair.first) ^ std::hash<U>()(pair.second). To avoid misleading anyone, I will not paste that code here. This copied implementation really hurt me: the hash function had severe collisions, causing very low efficiency. Surprisingly, this wrong implementation is everywhere online, both in Chinese and in English. I only found the root cause and the correct implementation in an obscure corner, namely the comment section of a Stack Overflow question. So I am summarizing it in this post to help more people avoid the pitfall.

std::hash()(x.first) ^ std::hash()(x.second); - that’s a spectacularly collision-prone way to hash a pair, as every pair with two identical value hashes to 0, and every pair {a, b} hashes the same as {b, a}. For vaguely demanding use, much better to find a hash_combine function and employ that.

Last night, my dad helped me clean my ear, and accidentally made it bleed. I went to the district hospital early this morning for a checkup. Fortunately, it was nothing serious; only the external ear canal was injured. Rest for a week and it should heal naturally. As long as it does not get infected, it is fine. I was prescribed some amoxicillin.
So I skipped the weekly contest and solved the problems after the contest.

1455. Check If a Word Occurs As a Prefix of Any Word in a Sentence

C++ does not have a built-in method for splitting strings, but we can use our own template. Implement the split through stringstream, with O(N) complexity.

Last month, because my Round B result was decent, I received a “Congraduation” email from Google CN HR. This month, I will keep going and work hard toward the dream of joining Google.

A. Countdown