ByteDance Interview Review Review 2021 Passing Bureau

Faced with the byte-oriented Java back-end, I was actually a bit panicked before the interview. I have been preparing papers recently, but I haven’t reviewed it much. Occasionally I help students do the questions and take a look. Basically, I use them to check the information and study. . Therefore, this interview by Byte is not an exaggeration. After the interview, the lesson from this incident is: first, we must carefully review, brush more questions, practice more hands, programming questions because of the use of, there is no need for reminders and code supplements. All, I didn't write the definition of the array directly; the second is that the resume is very detailed, it is best to review it in time, and a lot of knowledge is accumulated in peacetime. Let’s review the interview questions below:

1. First ask what database you have used, and then ask the index of the database, let’s design a database structure based on the TikTok watch list

At that time, I answered Mysql and introduced the index used by the project. Because I didn't use a lot and almost forgot, the interviewer gave an example for me to analyze. For the follower list of Douyin, I designed the ID of the following user and the ID, avatar, nickname and follow timestamp of the followed user. Considering that the two IDs are foreign keys, the query needs to join the table, so the avatar and nickname are added. It is also said that this will be faster but will cause inconsistent information. Then the interviewer asked how to add the index, hoping to get the results sorted by timestamp.

First come to popular science, an index is a structure for sorting the values ​​of one or more columns in a database table. Using an index can quickly access specific information in a database table. If you want to find a specific employee by his or her last name, the index helps to obtain information faster than searching all rows in the table. Indexes are divided into clustered indexes and non-clustered indexes. Clustered indexes are ordered according to the physical location of data storage, while non-clustered indexes are different; clustered indexes can improve the speed of multi-row retrieval, and The non-clustered index is fast for single-row retrieval. According to the function of the database, three kinds of indexes can be created in the database designer: unique index, primary key index and clustered index.

I feel that the index cannot be sorted, so I only added the primary key index to the ID. What I think is that the lookup table is also based on the ID as the where condition. For sorting, you can use order by to sort directly, and you shouldn’t need an index.

2. A design question requires an input: similar to this, and then output a , request This output can uniquely correspond to one input, and each output of the same input is different. It feels like the invitation code. Given that there are five final characters, the value range is 62 regular characters. It is required to design an algorithm with this function. The input and output are all strings, and the interviewer can use the database.

输入: 输出:

It feels like just using a hash function, I talked about adding a timestamp each time to hash, and then save the corresponding relationship of the result to the database. Then the interviewer asked about the specific hashing process and completely forgot, mainly how to generate a string that meets the requirements. Finally, I just say that hashing can realize the mapping from high-dimensional space to low-dimensional space. It was used directly before, so I didn't go into details!

Hash, also known as hash, is to transform an input of any length into a fixed-length output through a hash algorithm. This output value is the hash value. Several common Hash algorithms:

① Division hash method Formula: hash(key) = key mod M (Note: M is usually a "prime number")

② Multiplicative hashing formula: hash(key) = floor( M/W * ( a * key mod W) ) where floor means rounding down the expression

  1. Usually M is set to a power of 2.
  2. W is the computer word length (also a power of 2).
  3. a is a number very close to W.

In fact, the idea of ​​"multiplicative hash" is to extract the k digits in the middle of the key.

③ Fibonacci (Fibonacci) hashing is "by Fa Haxi law" when a ≈ W/φ, 1/φ ≈ (√5-1)/2 = 0.618 033 988when the situation. However 1/φ ≈ (√5-1)/2 = 0.618 033 988,, can be called the golden section point.

After reading it, I feel that the interviewer actually asked how to deal with strings. Continue to Baidu: By the nature of the hash function, for a string:, we convert each character into idx(si)=si -'a'+1 Of course, it can also be expressed directly by the ASCII code of the string. The hash model is Hash(i)=Hash(i-1)*p+idx(si), where p is a prime number. The finally calculated Hash(n) is used as the hash value of the string.

I also think that it is also good to use existing hash algorithms such as md5 and sha256, and You can remember it. For the number of generated digits of 5, I think it can be intercepted directly, or the generated result can be cyclically added to take the modulus.

3. How does the memory management of the operating system course work? I haven't learned it at all. I also asked how to allocate memory to the process?

The memory in JVM can be divided into several different data areas, which are mainly divided into: program counter, virtual machine stack, local method stack, heap, and method area.

For specific details, please refer to:

4. The last question is a powerful programming question. Given a one-dimensional array used to describe an altitude, the adjacent altitudes are different, there will be water in the low-lying depressions after it rains. Assuming enough rainwater can be filled Fill all low-lying areas and calculate the total water storage capacity of all low-lying areas after rain. For example, the given array is: 5, 2, 1, 4, 3. Then: the amount of water storage in all low-lying areas is 5

I probably did it, but it doesn’t feel right, I still need to brush more~

import java.util.ArrayList; public class Main {    public static void main(String[] args) {        //Scanner in = new Scanner(;        //int a = in.nextInt();        //System.out.println(a);        System.out.println("Hello World!");        int[] a = {5, 2, 1, 4, 3};        ArrayList<Integer> max = new ArrayList<>();//存放峰值        int allWater = 0;        for (int i = 0; i < a.length; i++) {            if (i != 0 && i != a.length - 1) {                if (a[i] >= a[i - 1] && a[i] >= a[i + 1])//去重复                    max.add(i);            }        }        for (int j = 0; j < max.size() - 2; j++) {            if ((max.get(j + 1) - max.get(j)) > 1) {                int high = (a[max.get(j)] >= a[max.get(j + 1)] ? a[max.get(j + 1)] : a[max.get(j)]);                int water = 0;                for (int k = max.get(j) + 1; k < max.get(j + 1); k++) {                    water += (high - a[k]);                }                allWater += water;            }        }        System.out.println(allWater);    }}