directory

  • preface
  • Three rounds of the surface by the
  • About the byte
  • eggs

preface

July harvest byte letter of intent, today free to sort out the book to share with you, also take this to share good luck to everyone.

A brief introduction to personal information:

Before the interview: finished brushing offer, Leetcode about 70. Operating system review finished, database will not, the net will not.

Later: one in front of a week to learn the database, three in front of three days to learn the network. In two weeks, I swiped 80 Leetcodes.

I hope this article can be helpful to you. I wish you a lot of offers!

Three rounds of the surface by the

I was not an intern, so I was not asked questions about the project.

Question composition: tore code, basic knowledge, scene questions.

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

One side

  • Hand code

Easy question: Chinese string into numbers. Example: “5.306,003” -> 5306,003. Constraint: The input amount is less than 100 million. Requirements: do certain fault tolerance, bug free.

This is a relatively simple problem, the method should be you can think of. It just requires bug free and fault-tolerant handling, so consider improvements when writing code. For example, input exceptions (whether the string is valid, “five hundred” is not valid, “three hundred and five” is not valid).

  • Hand code

Determine whether a string meets Fibonacci rules, e.g. “199100199”. Since 1 + 99 = 100, 99 + 100 = 199.

This problem Lao Wang is under the guidance of the interviewer step by step to think of the optimal solution. (Blow up the interview experience, the interviewer is very patient guidance, nice!)

So the trick here is to find the first two numbers, n1, n2. If these two numbers are found, Fibonacci’s rule can be determined by a traversal of n = N1 + n2. The only way to search for the first two numbers is to search the code 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)); // Get the first number

   for(int j = i + 1; j < n; j++){

     int n2 = Integer.parseInt(str.substring(i, j)); // Get the second number

     if(judege(str, n1, n2, start)) return true;// Determine if the rule is met

   }

 }

 return false;

}



// Given n1, n2, determine if the string conforms to Fibonacci rules

boolean judge(String str, int n1, int n2, int start){

 int n = str.length();

 for(inti = 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; // The subscript is exceeded, or the last number is not equal to n3

   i += len;

 }

 return true;

}

Copy the code

Time complexity: O(n^3), O(n^2) is required to find the first two digits, and O(n) is required to determine whether the string conforms to the rule.

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

  • Hand code

1 billion unordered integers find the median.

This problem Lao Wang is also under the guidance of the interviewer step by step to think of the optimal solution. (Blow the interview experience again)

Because it is a billion integers, it cannot be processed in memory. That is to say, use a proper external sorting algorithm.

Here you can use bucket sort, take n evenly spaced buckets, iterate over the integers, store them in the buckets of the corresponding interval, and count the number of digits in the buckets. If the number in the bucket is still too large, sort the bucket. Otherwise, sort the bucket in memory.

Second interview

  1. ACID properties of transactions

  2. Index structure used by Innodb

  3. B + tree, why use it

  4. Where a = 1 and c = 1 (a, b, c); (Left-most prefix matching knowledge)

  5. The execution flow of an SQL statement (no)

  6. The difference between processes and threads

  7. The difference between concurrency and parallelism

  8. The process scheduling policy

  9. The cause of deadlock

  10. Leetcode 题 41 (No, change a question)

Given an array of unsorted integers, find the smallest positive integer that does not appear in it.

If there are n digits in the array, the smallest positive integer missing must be in [1, n + 1].

So we can hash the array itself, walking through the array, placing the number I in [1, n] at the corresponding index i-1.

Iterate through the array again, the first nums[I]! The number 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] != nums[i]){ // Put the number of (0, n] on the corresponding subscript

      int temp = nums[i] - 1;

      nums[i] = nums[temp];

      nums[temp] = temp + 1;

    }

  }

  int i = 0;

  for(; i < n && nums[i] == i + 1; i++); // Find the first positive integer that does not appear

  return i + 1;

}

Copy the code

Time complexity: O(n), although there is a while loop, each digit can be swapped at most once to the corresponding subscript.

  1. Leetcode original question 3

Given a string, find the length of the smallest string that does not contain repeating characters.

A very classic problem, sliding window can be solved.

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;

}

Copy the code

On three sides

  1. Hand code

Arithmetic: array, increment by row, increment by column, ask if you can find a number.

Use the increment property to iterate from the bottom left corner (maximum value for this column, minimum value for this row). Comparison with target numbers:

< the number of targets, indicating that this column is < the number of targets, so the column subscript + 1

> number of targets means that all lines are > number of targets, so the subscript is -1

In this way, one row/column can be excluded from each comparison.

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;

}

Copy the code
  1. Hand code

Algorithm: How many ways can a 2 * 1 small rectangle fill a 2 * N large rectangle?

Very 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];

}

Copy the code

The space complexity here is O(n), and you can reduce it to O(1) by pressing dp.

  1. Scene design

100 billion unsigned integers. Find the largest 100. What’s the solution for running out of memory? What if I have enough memory? Partition’s solution is unstable. Is there any way to stabilize it?

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

  1. How is HTTPS encrypted

  2. Pagefault in OS

  3. The underlying index structure in mysql? Why use 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 online solutions to this problem. Lao Wang was referring to TCP’s sliding window and retransmission mechanism to answer.

The large file is divided into blocks and numbered, and the receiver confirms the blocks in an orderly manner. If a block is not received, the sender is told to resend it.

The sender records the number of the last transmission, and the breakpoint continues from this number.

Because of load balancing, it is necessary to determine the server from which the message was received. This allows the receiver to record the identity of the sender.

About the byte

  1. Working intensity: size week, 10 10 5.5. Do not force overwork, finish can go, but workload wants overwork to finish commonly. Vary from person to person, there are fish.

  2. Benefits: all-inclusive meals, afternoon tea, room allowance of 1500 yuan, free gym (basically after working for a year, I will eat fat, HHH)

  3. Atmosphere: flat management, net spread wind reviews are quite good.

  4. New person training: mentor system, one to one guide new people to get familiar with. However, compared with the old BAT, the document is not perfect, and the training process of new staff is still lacking.

  5. The focus of byte correction: the back-end language is basically to go/ Python, so it does not examine the language.

The main investigation “operating system”, “database principle”, “network” and “rip code”, byte is very important to rip, this must be well prepared. Of course, students who have done well in the project will also get extra points.

Lao Wang comments: The work intensity is high, the challenge is many, the salary is also good. Suitable for strong ability, strong ability to resist pressure of the students, can withstand pressure to grow quickly. But it’s a bit of a test for new recruits, depending on who you are.

eggs

  1. Although the byte tear code is more difficult, but the question bank is limited, the algorithm questions in the multi-brush face, there will be a great probability to meet the original question.
  2. For those who want to invest in Shanghai data department, Lao Wang can help contact HR for direct fishing.
  3. I wish you a lot of offers. If you don’t have a “like”, you should offer a lot. Hee hee ~
  4. “It’s going to be all right! And everything will be fine!
Everything will be all right