美团在线聊天和智能推荐面经

系统管理员 2023-05-30 10:58 58阅读 0赞

### 算法题 ###

###### 交换二叉树的左右节点 ######

递归做法：由父节点出发，考虑特殊情况，交换两个子节点，对子节点递归，直到最后一个  
非递归做法（没答出来）：利用栈实现，若当前父节点不为空，入栈，当栈不为空事物，入栈，取出栈顶元素，交换该元素的左右子节点，若左右节点不为空加入栈中。以下为牛客cpp

/*
    struct TreeNode {
     int val;
     struct TreeNode *left;
     struct TreeNode *right;
     TreeNode(int x) :
       val(x), left(NULL), right(NULL) {
     }
    };*/
    class Solution {
        
    public:
        void Mirror(TreeNode *pRoot) {
        
            stack<TreeNode *> s;
            if(pRoot)
                s.push(pRoot);
            while(!s.empty()){
        
                TreeNode* cur = s.top();
                s.pop();
                TreeNode *temp = cur->left;
                cur->left = cur->right;
                cur->right = temp;
                if(cur->left)
                    s.push(cur->left);
                if(cur->right)
                    s.push(cur->right);
            }
        }
    };

###### 树的遍历，只问点不展开 ######

前序、中序、后序遍历，层次遍历

###### 判断两个链表相交，找到交点 ######

明确两个链表呈现 “ Y ”字形![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2ODA0MzYz_size_16_color_FFFFFF_t_70]  
1. 暴力法（只答了这个）：两个for循环找到相同节点。从头开始遍历第一个链表，遍历第一个链表的每个节点时，同时从头遍历第二个链表，看是否有相同的节点，第一次找到相同的节点及第一个交点。若第一个链表遍历结束后没有找到相同的则不存在交点，时间复杂度 O ( n 2 ) O(n^2) O(n2)  
2. 栈（没答出来）：用两个栈分别来保存两个链表，存入后判断栈顶元素是否相等，不相等则不相交，若相等，就循环出栈，直到两个出栈的节点不相同，则不相等的上一个出栈节点就是第一个相交的节点。

node temp =NULL;
    while(!stack1.empty() && !stack2.empty())
    {
        
    	temp = stack1.top();
    	stack1.pop();
    	stack2.pop();
    	if(stack1.top()!=stack2.top())
    	{
        
    		break;
    	}
    }

3. 记录链表长度同时遍历两个链表到尾部，记录两个链表长度，若两个链表最后一个节点相同则两个链表相交。  
有两个链表长度后，设长链表的长度为L1，短链表长度为L2，先让较长的链表向后移动（L1-L2）个长度，开始从当前位置同时遍历两个链表，当遍历到的链表节点相同时，这个节点就是第一个相交的节点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2ODA0MzYz_size_16_color_FFFFFF_t_70 1]4. 哈希表法 两个链表相交，相交节点有相同的内存地址，通过判断两个链表中是否存在内存地址相同的节点判断两个链表是否相交。做法：遍历第一个链表，并利用地址建立哈希表，遍历第二个链表，看看地址哈希值是否和和第一个表中的节点地址值有相同的，则说明两个链表相交。  
 5. 问题转换成判断一个链表是否有环问题先遍历第一个链表到尾部，将尾部的next指向第二个链表头，把两个链表和成一个链表，若链表有环，则两个链表一定相交，否则不相交。用快慢指针法，low和fast指针从链表头开始 ，low每次走一步，fast每次走两步，两节点在low没有走到链表结尾之前相遇说明存在环，此时快节点从头开始每次走一步，与原low节点相遇点即为环入口。  
附牛客网判断有环demo

ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        
            //stack<ListNode*> s1,s2;
            ListNode *t1 = pHead1;
            ListNode *t2 = pHead2;
            while(t1 != t2){
        
                t1 = ((t1==NULL) ? pHead1:t1->next);
                t2 = ((t2==NULL) ? pHead2:t2->next);
            }
            return t1;
     }

参考[判断两个单链表是否相交及找到第一个交点][Link 1]

###### 一个数组奇数升序排序，偶数降序排序 ######

答：先分奇数偶数两部分，再用快排对两个部分排序  
提示：归并排序，奇数一组，偶数一组，分别排序

###### 归并排序，提示我第上一题可以这样写 ######

归并排序思路，自上而下先取一半到2个元素排序，再自下而上合并排序

### 计算机网络 ###

###### ios七层协议 ######

物理层，链路层，网络层，传输层，会话层，表达层，应用层  
tcp/ip五层协议：物理层，链路层，网络层，传输层，应用层

###### TCP协议哪一层、IP协议那一层 ######

传输层、网络层

###### HTTP协议，端口号，状态码 ######

http 位于应用层，端口号80  
200：成功  
301：资源被永久转移到其他URL  
403：服务器拒绝访问，无访问权限  
404：请求资源不存在  
500：服务器内部错误  
502：作为网关或代理工作的服务器尝试执行请求时，从远程服务器接收到一个无效响应  
1\*\*：消息  
2\*\*：成功  
3\*\*：重定向  
4\*\*：请求错误  
5\*\*：服务器错误码

###### 三次握手 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2ODA0MzYz_size_16_color_FFFFFF_t_70 2]

###### 为啥要四次挥手 ######

因为TCP是全双工，发送方和接收方都需要FIN报文和ACK报文  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2ODA0MzYz_size_16_color_FFFFFF_t_70 3]

###### Linux命令行，查看IP、端口，查看内存，查看磁盘 ######

答：Windows是ifconfig  
linux查看IP信息：ifconfig  
查看端口号：  
1、lsof -i:(端口号)，比如`lsof -i:8000`  
2、netstat -tunlp：查看所有端口占用情况  
地址管理：ip  
空闲内存查看：free  
free -m：查看linux系统内存使用量和交换区使用量  
df -h：查看linux系统各分区的使用情况  
 cat /proc/meminfo：查看linux系统内存大小的详细信息，查看总内存，剩余内存，可使用内存  
cat /proc/cpuinfo |grep “physical id”：筛选出多核CPU信息  
cat /proc/cpuinfo ：查看linux系统的CPU型号类型以及大小

ip --help  
参考：  
[linux ip 命令和ifconfig命令][linux ip _ifconfig]  
[linux 查询端口被占用命令][linux]

###### git、maven代码管理工具 ######

没有了解（要求要熟悉掌握命令行！）

###### 怎么查看CPU占用，CPU占用过高如何解决 ######

先找到是哪个进程占用高，找到进程后再看是哪个线程，再看怎么解决。  
在linux中：  
top  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2ODA0MzYz_size_16_color_FFFFFF_t_70 4]  
查看某个进程情况top -H -p 进程号  
![在这里插入图片描述][20191110153542785.png]  
转为16进制：printf “%\\n” 进程号

定位到代码：jstack 进程号|grep 16进制异常线程号 -A90：定位异常代码位置，最后的-A90是日志行数，也可以输出为文本文件或使用其他数字。

参考[linux服务器定位CPU高占用率代码位置经历][linux_CPU]

最后还问了数据库的知识点，但直接说我不会就过了！

面试官真的很好，问问题答不出来的时候会提示我，真的不会的时候会跟我讲一遍，比如最后一个问题说要怎么怎么样。还跟我说了一些面试技巧，在不确定的时候不要犹犹豫豫，吞吞吐吐，确定一点回答，不会就是不会，说错了也没关系。在方向上给了蛮多建议，就是我太久没有复习，没有准备好，辜负面试官的热情。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2ODA0MzYz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191110131707652.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2ODA0MzYz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2ODA0MzYz_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191110134225369.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2ODA0MzYz,size_16,color_FFFFFF,t_70
[Link 1]: https://blog.csdn.net/fengxinlinux/article/details/78885764
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2ODA0MzYz_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191110145650354.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2ODA0MzYz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2ODA0MzYz_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20191110145704116.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2ODA0MzYz,size_16,color_FFFFFF,t_70
[linux ip _ifconfig]: https://www.cnblogs.com/0to9/p/9591315.html
[linux]: https://www.cnblogs.com/ming-blogs/p/11101423.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2ODA0MzYz_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20191110153427404.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2ODA0MzYz,size_16,color_FFFFFF,t_70
[20191110153542785.png]: https://img-blog.csdnimg.cn/20191110153542785.png
[linux_CPU]: https://blog.csdn.net/zhu19774279/article/details/51303000