小红书面试

如何判断单链表有环

 1public boolean IsLoop(Node head){
 2  Node fast = head;
 3  Node slow = head;
 4  if(head = null){
 5    return false;
 6  }
 7  
 8  while(fast != null&& slow ！= null){
 9    fast = fast.next.next;
10    slow = slow.next;
11    if(fast = slow){
12      return true;
13    }
14  }
15  
16  return false;
17}

三次握手，为什么要三次

A -> B SYN=1, seq = x;

A <- B SYN = 1, ACK=1, seq = y, ack = x+1;

A-> B SYN = 1, ACK =1, seq = x+1, ack = y+1;
- 实现信息对等，双方的收发报文能力
- 防止脏连接
TCP/UDP

TCP 是面向连接的可靠传输，具有流量控制和拥塞避免

UDP 是不可靠的，
线程和进程

进程是资源分配的最小单元

线程是调度的最小单元

二叉树先序遍历，递归和非递归

1// 递归先序遍历
2public void preOrder(TreeNode node){
3  if(node == null ){
4    return;
5  }
6  System.out.print(node.val);
7  preOrder(node.left);
8  preOrder(node.right);
9}

 1public void preOrder(TreeNode root){
 2  if(root==null){
 3    return;
 4  }
 5
 6  Stack<TreeNode> stack = new Stack<>();
 7  stack.push(root);
 8
 9  while(!stack.isEmpty()){
10    TreeNode node = stack.pop();
11    System.out.print(node.val);
12    if(node.left != null){
13      stack.push(node.left);
14    }
15    if(node.right !=null){
16      stack.push(node.right)
17    } 
18  }
19}

map 的扩容，HashMap

HashMap的容量为 2^n^, 所以每次扩容都为2倍，在重新分配元素的时候会比较快
索引的实现

B+Tree 平衡搜索树

前缀树

 1class TireNode{
 2  private TireNode[] links;
 3  private final int R = 26;
 4  private boolean isEnd;
 5  public TireNode(){
 6    links = new TireNode[R];
 7  }
 8
 9  public boolean containsKey(char ch){
10    return links[ch - 'a'] != null;   
11  }
12  public TireNode get(char ch){
13    return links[ch -'a'];
14  }
15  public void put(){
16
17  }
18}

redis 的好处

存取速度快，可以保证数据一致性

一个从1加到n不用循环求和递归啊

1public static int sum(int n){
2	if (n==1) {
3		return 1;
4	}else {
5		return n+sum(n-1);//加法
6		// return n*sum(n-1); //乘法
7	}
8}

一个字符串数字结合遇到数字重复前面字符，求第n个字符
Hashmap底层实现＋如何扩容

13.二叉树的几种搜索方式 NLR LNR LRN 前中后层次遍历

14.两种二叉树深搜方式的差别深度优先搜索算法的实现运用的主要是回溯法，类似于树的先序遍历算法。广度优先搜索算法借助队列的先进先出的特点，类似于树的层次遍历 https://blog.csdn.net/liupeifeng3514/article/details/83819583

1面

1.编程题：给你一个可以生成0-6随机数的函数，设计一个可以生成0-9随机数的函数

面试官提示的思路是：先生成两位0-6的随机数，然后7进制转10机制，如果转化结果<=39，就用结果对10求余，因为生成0-39的概率是相等的，所以获得0-9的概率也相等

2.编程题：给你两个数组，求并集

3.操作系统：常用的线程调度算法有哪几种？

有先来先服务，最短作业优先，基于优先权的调度算法，时间片轮转等

4.操作系统：线程和进程的区别？

5.操作系统：线程同步有哪几种方式？

线程同步的方式主要有: 临界区（Critical Section）、互斥量（Mutex）、信号量（Semaphore）、事件（Event）。

他们的主要区别和特点如下：

**1）临界区：**通过对多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问。在任意时刻只允许一个线程对共享资源进行访问，

如果有多个线程试图访问公共资源，那么在有一个线程进入后，其他试图访问公共资源的线程将被挂起，并一直等到进入临界区的线程离开，临界区在被释放后，其他线程才可以抢占。

**2）互斥量：**采用互斥对象机制。只有拥有互斥对象的线程才有访问公共资源的权限，因为互斥对象只有一个，所以能保证公共资源不会同时被多个线程访问。

互斥不仅能实现同一应用程序的公共资源安全共享，还能实现不同应用程序的公共资源安全共享。

**3）信号量：**它允许多个线程在同一时刻访问同一资源，但是需要限制在同一时刻访问此资源的最大线程数目。

4）事件： 通过通知操作的方式来保持线程的同步，还可以方便实现对多个线程的优先级比较的操作。

2面 1.C++：有哪几种智能指针？

2.C++：简述模板以及为什么使用模板的时候#include<***.hpp>？

3.编程题：用递归和迭代两种方式写反转二叉树

4.编程题：每k个一组反转链表

5.数据库：redis和其他数据库的区别是什么？什么时候选择redis？

5.设计模式：写一个单例模式

3面 1.计算机网络：TCP/IP4层模型有哪4层？

2.计算机网络：mac层寻址过程

3.编程题：从文本中查找敏感词

面试官希望使用前缀树来做这道题

4.编程题：给你一个含有()和[]的字符串，输出括号每对括号的位置下标如（1,2），如果有不合法括号返回空

5.操作系统：有哪几种IO模型？阻塞IO在底层阻塞在了哪里？

拓展听到的一些别人的问题

1.编程题：第k大的数

2.编程题：判断一个二叉树是不是完全二叉树

3.编程题：反转链表

4.编程题：用栈实现队列

5.编程题：全排列

6.编程题：从二维数组中查找数（每列递增，每行递增）

Airren Ren

小红书面试

Table of Contents