A summary of the latest BATJ interview questions in 2019 has been released! (Including answer analysis)

In 2019, the latest technical interview questions from major manufacturers such as Alibaba, Tencent, Baidu, Meituan, and Toutiao have been compiled and sorted out recently. The analysis and summary of the experts and the answers are also being gradually completed. At present, the project has obtained more than 10,900 Stars on GitHub. The content is divided into Ali articles, Huawei articles, Baidu articles, Tencent articles, Meituan articles, Toutiao articles, Didi articles, JD articles, MySQL articles, Redis articles, MongDB articles , ZooKeeper, Nginx, Algorithm, Memory, CPU, Disk, Network Communication, Security, Concurrency. Not much to say, let's take a look. ( The free collection method is attached at the end of the article )


## Ali

1.1.1 How to achieve an efficient reverse output of a singly linked list?

Questioner: Alibaba Expert: Yunlong/Alibaba Cloud Elastic Artificial Intelligence Leader

Reference answer: The following is one way of writing, but there can also be different ways of writing, such as recursion. for reference.

typedef struct node{
	int           data;
	struct node*  next;
	node(int d):data(d), next(NULL){
	}
}
node;
void reverse(node* head)
{
	if(NULL == head || NULL == head->next){
		return;
	}
	node* prev=NULL;
	node* pcur=head->next;
	node* next;
	while(pcur!=NULL){
		if(pcur->next==NULL){
			pcur->next=prev;
			break;
		}
		next=pcur->next;
		pcur->next=prev;
		prev=pcur;
		pcur=next;
	}
	head->next=pcur;
	node*tmp=head->next;
	while(tmp!=NULL){
		cout<<tmp->data<<"t";
        tmp=tmp->next;
    }
}

####1.1.2 It is known that sqrt(2) is approximately equal to 1.414. It is required that the math library is not used, and the accuracy of sqrt(2) is 10 digits after the decimal point.

Subject: Alibaba Expert: Wenjing/Alibaba Cloud CDN Senior Technical Expert

Reference answer:

*  Survey point

1. The flexible application ability of basic algorithms (Students who have studied data structure in the dichotomy method know it, but not necessarily in this direction; if students who have studied numerical calculations, they should also be able to think of Newton's iteration method and explain clearly)

2. Design of exit conditions

*  Solution

1. Knowing that sqrt(2) is approximately equal to 1.414, then it can be divided into two in the interval (1.4, 1.5)

Find, such as: a) high=>1.5 b) low=>1.4 c) mid => (high+low)/2=1.45 d) 1.45*1.45>2 ?high=>1.45: low => 1.45 e) loop To c)

2. Exit conditions

a) The absolute value of the difference between the previous two times <=0.0000000001, then you can exit

const double EPSINON = 0.0000000001;

double sqrt2( ){
    double low = 1.4, high = 1.5;
    double mid = (low + high) / 2;
    
    while (high - low > EPSINON){
        if (mid*mid > 2){
            high = mid;
        }
        else{
            low = mid;
        }
        mid = (high + low) / 2;
    }
    
    return mid;
}

####1.1.3 Given a binary search tree (BST), find the Kth smallest node in the tree

Subject: Alibaba Expert: Wenjing/Alibaba Cloud CDN Senior Technical Expert

Reference answer:

*   Survey point

1. Understanding of basic data structure and coding ability

2. Recursive use

  • Example
       5
      / \
     3   6
    / \
   2   4
  /
 1

Description: Ensure that the input K satisfies 1<=K<=(number of nodes)

For tree-related problems, I think of recursive solution at first glance, and the left and right subtrees are traversed separately. Reminiscent of the nature of the binary search tree, root is greater than the left subtree and smaller than the right subtree. If the number of nodes in the left subtree is equal to K-1, then root is the result, otherwise if the number of nodes in the left subtree is less than K-1, then The result must be in the right subtree, otherwise it is in the left subtree. Therefore, the number of nodes is returned at the same time when searching, and the result can be obtained by comparing with K.

/**
 * Definition for a binary tree node.
 **/
 
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
 
class Solution {
    private class ResultType {
 
        boolean found;  //是否找到
 
        int val;  //节点数目
        ResultType(boolean found, int val) {
            this.found = found;
            this.val = val;
        }
    }
 
    public int kthSmallest(TreeNode root, int k) {
        return kthSmallestHelper(root, k).val;
    }
 
    private ResultType kthSmallestHelper(TreeNode root, int k) {
        if (root == null) {
            return new ResultType(false, 0);
        }
 
        ResultType left = kthSmallestHelper(root.left, k);
 
//左子树找到,直接返回
        if (left.found) {
            return new ResultType(true, left.val);
        }
 
//左子树的节点数目 = K-1,结果为 root的值
        if (k - left.val == 1) {
            return new ResultType(true, root.val);
        }
 
//右子树寻找
        ResultType right = kthSmallestHelper(root.right, k - left.val - 1);
        if (right.found) {
            return new ResultType(true, right.val);
        }
 
//没找到,返回节点总数
        return new ResultType(false, left.val + 1 + right.val);
    }
}
  • 1.1.4 LRU caching mechanism
  • 1.1.5 Regarding the difference between epoll and select, which of the following statements are correct
  • 1.1.6 From the analysis of innodb index structure, why the key length of the index cannot be too long
  • 1.1.7 How to restore MySQL data to any point in time?
  • ...

Huawei articles

  • 2.1.0 What is the use of static? (Please specify at least two)
  • 2.1.1 What is the difference between reference and pointer?
  • 2.1.2 Describe the basic characteristics of real-time systems
  • ...

Baidu articles

  • 3.1.0 Define a character array in a function. When inputting a string with the gets function, if the input is out of bounds, why does the program crash?
  • 3.1.1 The difference between references and pointers in C++
  • 3.1.2 Memory partition of C/C++ program
  • ...

Tencent

Meituan

Headlines

Didi articles

Jingdong articles

MySQL articles

Redis articles

MongDB articles

Zookeeper articles

Nginx articles

Algorithm

Memory

cpu articles

Disk articles

Network communication

Security

Concurrency

Wait, because the length of the article is too long, it is difficult for the editor to do too many displays in the same article. Later, I will update the article in sections, so stay tuned! (If you need the information in the above picture, you can privately write to the editor)

If you like or think it is useful to you, add a concern, thank you!

Save the article**

cpu articles

Disk articles

Network communication

Security

Concurrency

[External link image is being transferred...(img-N52TdeFx-1622703715307)]

Wait, because the length of the article is too long, it is difficult for the editor to do too many displays in the same article. Later, I will update the article in sections, so stay tuned! (If you need the information in the above picture, you can privately write to the editor)

If you like or think it is useful to you, add a concern, thank you!