directory

preface

In July, I received a letter of intent. Today, I have time to sort out my face and share it with you. I also want to share my good luck with you.

A brief introduction of personal information:

Before the interview: sword point offer brush, Leetcode about 70. The operating system review is finished, the database will not, the network will not.

Later: a week in front of the database, three three days in front of the network. Over the course of two weeks, I went through 80 LeetCodes.

Hope this article can be helpful to you, I wish you a lot of offer!

Three rounds of the surface by the

I did not have an internship, so I was not asked questions about the project.

Problem composition: hand tear code, basic knowledge, scene problem.

The “basics” are all fixed answers, so in this article, only the questions will be shared, not the answers.

One side

  • Hand code

Easy question: Convert Chinese strings into numbers. Example: “five hundred thirty-six thousand three” -> 5306003. Constraints: The input amount should be less than 100 million yuan. Requirements: do a certain amount of fault tolerance, bug free.

This is a fairly simple problem, and you can probably think of a way to do it. It just requires bug free and fault-tolerant handling, so write code with refinement in mind. For example, the input is abnormal (whether the string is valid, “five hundred five hundred” is not legal, “three hundred five” is not legal).

  • Hand code

原 文 : Determine whether a string meets the Fibonacci rule, e.g. “199100199”. Because 1 + 99 = 100, 99 + 100 = 199.

This question is under the guidance of the interviewer step by step to think of the best solution. (Blowing the interview experience, the interviewer is very patient in the guidance, nice!)

The key point here is how to find the first two numbers, N1 and n2. After finding these two numbers, we can use the rule n = n1 + n2 to determine whether the Fibonacci rule is complied with in a single pass. Find the first two numbers can only be violent search, the code is as follows:

public boolean solve(String str){ if(str == null) return false; int n = str.length(); for(int i = 1; i < n; i++){ int n1 = Integer.parseInt(str.substring(0, i)); For (int j = I + 1; j < n; j++){ int n2 = Integer.parseInt(str.substring(i, j)); If (judege(STR, n1, n2, start)) return true; }} return false; Boolean judge(String STR, int n1, int n2, int start){int n = str.length(); for(int i = start; i < n;) { int n3 = n1 + n2; int len = (n3 + "").length(); if(start + len > n || n3 ! = Integer.parseInt(str.substring(i, i + len))) return false; N3 I += len; n3 I += len; } return true; }

Time complexity: O(n^3), O(n^2) to find the first two numbers, O(n) to determine whether the string complies with the rule.

This problem can be pruned to slightly reduce the time consumption, you can optimize.

  • Hand code

1 billion unordered integers find the median.

This question old wang is also under the guidance of the interviewer just thought of the best solution step by step. (Blowing the interview experience again)

Because it’s a billion integers, it can’t be processed in memory. In other words, you have to use a proper external sorting algorithm.

You can do bucket sort here, take n buckets of uniform interval, walk through the integers, store them in the corresponding interval bucket, and count the number of numbers in the bucket. So you can find the bucket where the median is, and if there’s still a lot of numbers in the bucket, you can sort the bucket, otherwise you can sort it in memory.

Second interview

  1. ACID properties of transactions
  2. Index structure used by Innodb
  3. The advantages of b+ tree, why use it
  4. Select * from a where a = 1 and c = 1 where c = 1 (Knowledge of left-most prefix matching)
  5. The execution process of an SQL statement (not)
  6. The difference between processes and threads
  7. The difference between concurrency and parallelism
  8. Process scheduling policy
  9. The cause of the deadlock
  10. Hand code
  • Leetcode, original problem 41 (No, another one)

Given an unsorted array of integers, find the smallest positive integer that is not present.

If you want to find the smallest positive integer in an array of n digits, the smallest missing positive integer must be in [1, n + 1].

So you can hash the array itself, walk through the array, put the number I in [1, n] on the corresponding subscript I – 1.

Go through the array again, the first nums[I]! = I + 1, I + 1 is the smallest missing positive integer.

The code is as follows:

public int firstMissingPositive(int[] nums) { int n = nums.length; for(int i = 0; i < n; i++){ while(nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] ! Int temp = nums[I] -1; int temp = nums[I] -1; nums[i] = nums[temp]; nums[temp] = temp + 1; } } int i = 0; for(; i < n && nums[i] == i + 1; i++); Return I + 1; return I + 1; }

Time complexity: O(n), although there is a while loop, but each number can be exchanged at most once to the corresponding index.

  • Leetcode original question 3

Given a string, find one that does not contain duplicate characters
The eldest son ofThe length of the.

Train of thought: very classic a problem, slide the window can solve.

The code is as follows:

public int lengthOfLongestSubstring(String s) {
  if(s == null) return 0;
  Map<Character, Integer> map = new HashMap<>();
  int start = 0, ans = 0;
  for(int i = 0; i < s.length(); i++){
    char c = s.charAt(i);
    if(map.getOrDefault(c, -1) >= start) start = map.get(c) + 1;
    map.put(c, i);
    ans = Math.max(ans, i - start + 1);
  }
  return ans;
}

On three sides

  • Hand code

Algorithm: two-dimensional array, incremented by row, incremented by column, ask if you can find a certain number

Use the increment feature to iterate from the bottom left corner (the maximum value in this column, the minimum value in this row). Compare with target numbers:

< target number means that all columns are < target number, so the column index is + 1

> number of targets, indicating that the row is > number of targets, so the row index is -1

This way, each comparison can exclude a row/column.

The code is as follows:

public boolean canFind(int[][] matrix, int target){
 if(matrix == null || matrix.length == 0) return false;
 int rows = matrix.length, cols = matrix[0].length;
 int row = rows - 1, col = 0;
 while(row >= 0 && col < cols){
   if(matrix[row][col] == target) return true;
   if(matrix[row][col] > target) row--;
   else col++;
 }
 return false;
}
  • Hand code

Algorithm:
2 * 1The little rectangle fills up
2 * nHow many options can I have for the big rectangle of PI?

This is a simple dynamic programming problem

The code is as follows:

public int nums(int n){
 if(n < 0) return 0;
 int[] dp = new int[Math.max(n, 2)];
 dp[0] = 1;
 dp[1] = 1;
 for(int i = 2; i < n; i++) dp[i] = dp[i - 2] + dp[i - 1];
 return dp[n];
}

Here the space complexity is O(n), and you can reduce the space complexity to O(1) by dp.

  • Scene design

100 billion unsigned integers. Find the largest 100. What should I do if I run out of memory? What if I have enough memory? Partition’s scheme is not stable. Is there any stable method?

Not enough memory for heap sort, not enough memory for count sort.

  1. How is HTTPS encrypted
  2. Pagefault in OS
  3. Underlying index structure in mysql? Why this structure
  4. Is HashMap thread safe? What if you want to be thread safe?
  5. Scene design

Breakpoint continuation of large files

There are many solutions on the Internet. Wang is referring to the SLIDING window and retransmission mechanism of TCP to answer.

Large files are divided into blocks and numbered. The receiver acknowledges the blocks in order, and if a block is not received, tells the sender to resend it.

The sender records the number of the last transmission and starts the transmission from this number when the breakpoint is resumed.

Because of load balancing, you need to determine from which server it was sent, which allows the receiver to record the identity of the sender.

About the byte

  1. Work intensity: size week, 10 10 5.5. No mandatory overtime, finish can go, but the workload generally to work overtime to complete. It varies from person to person.
  2. Benefits: all meals included, afternoon tea, room allowance of 1500, free gym (basically you will get fat after working for a year, HHH)
  3. Atmosphere: flat management, network spread the wind comment is quite good.
  4. New person training: Mentor system, one to one to guide new people familiar. However, compared with the old BAT, the documents are not perfect, and the training process of new people is still a little deficient.
  5. Byte school admissions focus: the back end of the words, is basically to go/ Python, so not how to investigate the language.

Main investigation “operating system”, “database principle”, “net” and “hand tear code”, byte is very important hand tear, this must be well prepared. Of course, students who do a good job in the project, also have bonus points.

Wang’s comment: The work intensity is great, the challenges are many, and the pay is great. Suitable for students with strong ability and strong ability to work under pressure. But it’s a bit of a test for new couples.

eggs

  1. Although the byte tore code is more difficult, but the question bank is limited, multiple brush through the algorithm, there will be a great probability of the original problem.
  2. For those who have failed on three sides and want to apply to Shanghai data department, Lao Wang can help contact HR Zhilao.
  3. I wish you a lot of offers. If you don’t like it, you can offer more. Hee hee ~
  4. I heard that saying “Everything’s going to be okay! , everything is really good!