字节移动OS一二三四面

写在前

一直在用牛客的资源，这次写一篇回馈牛客。

说明一下，这是21届校招非实习，四轮都是技术面，已收到感谢信。

下面的内容只记录比较特殊或者少见的问题，并且附上一些我的扩展，其他的问题基本上可以在其他的面经中可以找到，大家可以一起来学习一下（有错误的话还请指出！）。

第一轮面试

1.输入url到显示的过程，其中涉及多少结点（有没有大佬解释一下结点是什么内容，是指那个渲染时候的DOM树吗）

2.文件描述符fd

大家可以先看这篇文章：http://www.itqiankun.com/article/file-fd

做个小总结：

• linux中万物皆文件，fd相当于文件的索引，是一个非负整数，在程序打开或者创建文件的时候就会返回。

• 系统维护fd创建了三个表

  进程级的文件描述符表（标志，文件指针...）

  系统级的文件描述符表（文件偏移量，访问模式，i-node指针...）

  文件系统的i-node表（文件类型，文件锁...）

  关系为你获得的fd值=进程fd表的索引，然后得到进程fd表中的文件指针去获取系统级的fd表文件偏移量，最后通过偏移量找到i-node指针，有了i-node就可以找到对应文件的内容。

• 其他：遍历fd需要开销，所以大家可以串联IO多路复用的那部分知识

3.消息机制中MessageQueue.next()的方法

面试官先问的是消息机制的流程，这个过程相信大家都已经很熟悉了，后面就提到next()方法里面的具体内容，这里给大家扩展一下。

• MessageQueue的数据结构

首先需要明白next()方法，是通过MessageQueue对象调用，所以我们应该清楚MessageQueue的数据结构。表面上说他是队列，其实他里面是一个单链表的结构，链表具有插入和删除的优势，他有一个mMessage:Message变量保存链表的第一个元素，然后Message类里面会有一个next指向下一个Message的位置。然后我们知道handler可以sendMessageDelayed()，也就是发送延迟的消息，MessageQueue的排序规则就是按时间顺序排成一列的。

• MessageQueue.enqueueMessage(Message msg, long when)

上面提到MessageQueue是按时间顺序排列，而且是单链表，我们就来看看MessageQueue是怎样添加结点了。

我先强调几个点，你们再看下面的源码应该就能看得比较明白：

①enqueueMessage()的位置在handler.sendXXXMessage() -> sendXXXMessageDelayed() -> sendMessageAtTime() -> handler的enqueueMessage() -> 这里才到MessageQueue.enqueueMessage(msg, uptimeMillis);

②MessageQueue.enqueueMessage(Message msg, long when) 中，msg就是你handler发送的消息，when是SystemClock.uptimeMillis() + delayMillis，也就是系统开机到当前的时间总数+设置的延迟时间

③重点看中间的for(;;)循环，他本质就是一个单链表的遍历，然后比对when的值，按照when值升序找到要插入的位置，然后break出来进行一次结点添加。如果when=0就是插在第一个的位置(头插结点)。

④我们知道消息队列没有消息的时候会阻塞，所以需要有类似生产者-消费者的模型，在有消息的时候唤醒循环，使用就是最后nativeWake(mPtr);这个native方法。

这是enqueueMessage的源码：

    boolean enqueueMessage(Message msg, long when) {
        //必须要有target是因为后面loop()方法里面就会通过msg.target.dispatchMessage(msg) 这个方法来回调我们new Handler的写的回调方法，比如handlerMessage(msg)
        if (msg.target == null) {
            throw new IllegalArgumentException("Message must have a target.");
        }

        if (msg.isInUse()) {
            throw new IllegalStateException(msg + " This message is already in use.");
        }

        synchronized (this) {
            if (mQuitting) {
                IllegalStateException e = new IllegalStateException(
                        msg.target + " sending message to a Handler on a dead thread");
                Log.w(TAG, e.getMessage(), e);
                msg.recycle();
                return false;
            }

            msg.markInUse();
            msg.when = when;
            Message p = mMessages;//mMessage就是消息队列的头结点
            boolean needWake;
            if (p == null || when == 0 || when < p.when) {
                // p为null即没有头结点，消息队列没有消息
                //该分支就是将当前msg设置为头结点
                msg.next = p;
                mMessages = msg;
                needWake = mBlocked;
            } else {
                //p不为空说明消息队列里面有其他结点，这个时候我们在插入新节点的时候，需要遍历单链表，然后将每个结点的when和当前when进行比较，如果当前结点的when比较大，就遍历下一个，知道找到准确的位置，然后进行插入。
                //遍历的时候使用prev遍历保存前一个结点
                // Inserted within the middle of the queue.  Usually we don't have to wake
                // up the event queue unless there is a barrier at the head of the queue
                // and the message is the earliest asynchronous message in the queue.
                needWake = mBlocked && p.target == null && msg.isAsynchronous();
                Message prev;
                for (;;) {//遍历找到当前结点的位置
                    prev = p;
                    p = p.next;
                    if (p == null || when < p.when) {
                        break;
                    }
                    if (needWake && p.isAsynchronous()) {
                        needWake = false;
                    }
                }
                //插入新节点的操作
                msg.next = p; // invariant: p == prev.next
                prev.next = msg;
            }

            // We can assume mPtr != 0 because mQuitting is false.
            //这里可以理解为生产者消费者模式的唤醒机制，消息队列插入新结点后，唤醒执行next()方法里面的取出操作
            //该方法是一个native方法
            if (needWake) {
                nativeWake(mPtr);
            }
        }
        return true;
    }

• MessageQueue.next()

看完上面的添加，相信大家应该对MessageQueue有一定的了解了，现在讲一下next()这个方法应该就比较好理解了。

老规矩先看提示在看源码：

①next()方法是在Looper.loop()的方法里面的for(;;)循环中调用

②重点关注nextPollTimeoutMillis这个变量，他在下方多次出现，初始为0，然后通过 nextPollTimeoutMillis = (int) Math.min(msg.when - now, Integer.MAX_VALUE);来赋值修改，其中now = SystemClock.uptimeMillis();。每次进入循环，都会调用nativePollOnce(ptr, nextPollTimeoutMillis);这个native方法，这个方法就是通过Native层的MessageQueue阻塞nextPollTimeoutMillis毫秒的时间。

nextPollTimeoutMillis的值不同会有不同的处理操作：

如果nextPollTimeoutMillis=-1，会一直阻塞，等待enqueueMessage()方法中的nativeWake(mPtr)来唤醒。

如果nextPollTimeoutMillis=0，不会阻塞，立即返回。

如果nextPollTimeoutMillis>0，阻塞最长的时间为nextPollTimeoutMillis毫秒(超时)，其中如果有唤醒会立即返回。

③观察代码下方有mPendingIdleHandlers这个变量，不知道大家还记不记得IdleHandler（下方有添加代码），当我们的MessageQueue空闲的时候，就会回调这个接口的方法。在next()中当判断MessageQueue没有消息的时候，就会mPendingIdleHandlers = mIdleHandlers.toArray(mPendingIdleHandlers);将我们添加的所有IdleHandler转化成数组，然后通过一个 for (int i = 0; i < pendingIdleHandlerCount; i++)循环一个一个地调用idler.queueIdle()，也就是回调我们自己写的方法逻辑。如果我们在queueIdle()方法中return false的话，调用一次后就会被移除掉。

Looper.myQueue().addIdleHandler(new MessageQueue.IdleHandler() {
            @Override
            public boolean queueIdle() {
                  //在空闲的时候处理逻辑              
                return false;
            }
        });

next()的源码：

    @UnsupportedAppUsage
    Message next() {
        // Return here if the message loop has already quit and been disposed.
        // This can happen if the application tries to restart a looper after quit
        // which is not supported.
        final long ptr = mPtr;
        if (ptr == 0) {
            return null;
        }

        int pendingIdleHandlerCount = -1; // -1 only during first iteration
        int nextPollTimeoutMillis = 0;
        for (;;) {
            if (nextPollTimeoutMillis != 0) {
                Binder.flushPendingCommands();
            }
            //这里就会进行阻塞的操作
            nativePollOnce(ptr, nextPollTimeoutMillis);

            synchronized (this) {
                // Try to retrieve the next message.  Return if found.
                final long now = SystemClock.uptimeMillis();
                Message prevMsg = null;
                Message msg = mMessages;//取出链表头结点
                if (msg != null && msg.target == null) {
                    // Stalled by a barrier.  Find the next asynchronous message in the queue.
                    do {
                        prevMsg = msg;
                        msg = msg.next;
                    } while (msg != null && !msg.isAsynchronous());
                }
                if (msg != null) {
                    if (now < msg.when) {
                        // Next message is not ready.  Set a timeout to wake up when it is ready.
                        //找到有消息对象后，进行nextPollTimeoutMillis的修改
                        nextPollTimeoutMillis = (int) Math.min(msg.when - now, Integer.MAX_VALUE);
                    } else {
                        // Got a message.
                        //得到消息对象，在链表中移除结点，然后标记在使用，同时返回出去
                        mBlocked = false;
                        if (prevMsg != null) {
                            prevMsg.next = msg.next;
                        } else {
                            mMessages = msg.next;
                        }
                        msg.next = null;
                        if (DEBUG) Log.v(TAG, "Returning message: " + msg);
                        msg.markInUse();
                        return msg;
                    }
                } else {
                    // No more messages.
                    nextPollTimeoutMillis = -1;
                }

                // Process the quit message now that all pending messages have been handled.
                if (mQuitting) {
                    dispose();
                    return null;
                }

                // If first time idle, then get the number of idlers to run.
                // Idle handles only run if the queue is empty or if the first message
                // in the queue (possibly a barrier) is due to be handled in the future.
                //下面的代码就是进行IdleHandler的对象的方法回调了，判断没有消息空闲的时候会进行处理
                if (pendingIdleHandlerCount < 0
                        && (mMessages == null || now < mMessages.when)) {
                    pendingIdleHandlerCount = mIdleHandlers.size();
                }
                if (pendingIdleHandlerCount <= 0) {
                    // No idle handlers to run.  Loop and wait some more.
                    mBlocked = true;
                    continue;
                }

                if (mPendingIdleHandlers == null) {
                    mPendingIdleHandlers = new IdleHandler[Math.max(pendingIdleHandlerCount, 4)];
                }
                mPendingIdleHandlers = mIdleHandlers.toArray(mPendingIdleHandlers);
            }

            // Run the idle handlers.
            // We only ever reach this code block during the first iteration.
            for (int i = 0; i < pendingIdleHandlerCount; i++) {
                final IdleHandler idler = mPendingIdleHandlers[i];
                mPendingIdleHandlers[i] = null; // release the reference to the handler

                boolean keep = false;
                try {
                    keep = idler.queueIdle();
                } catch (Throwable t) {
                    Log.wtf(TAG, "IdleHandler threw exception", t);
                }

                if (!keep) {
                    synchronized (this) {
                        mIdleHandlers.remove(idler);
                    }
                }
            }

            // Reset the idle handler count to 0 so we do not run them again.
            pendingIdleHandlerCount = 0;

            // While calling an idle handler, a new message could have been delivered
            // so go back and look again for a pending message without waiting.
            nextPollTimeoutMillis = 0;
        }
    }

算法题

1.url反转（要求原地处理，不使用库函数）

问了面试官可以用char[]吗，他说可以。

我的做法是先翻转一次，然后分部分再翻转一次，写的有点粗糙，但是逻辑还是比较好懂的

public static void main(String args[]){
    String url = "www.haha.com";
    char[] ch = url.toCharArray();
    reverse(ch,0,ch.length-1);
    int preIndex = 0;
    for(int i = 0; i < ch.length; i++){
        if(ch[i] == '.'){
            reverse(ch,preIndex,i-1);
            preIndex = i+1;
        }
    }
    //注意别漏了“moc”的翻转
    reverse(ch,preIndex,ch.length-1);
}

public void reverse(char[] ch,int i,int j){
    while(i < j){
        char temp = ch[j];
        ch[j] = ch[i];
        ch[i] = temp;
        i++;
        j--;
    }
}

2.路径总和

问题是路径总和I，也就是判断树中是否有符合根节点到叶子结点的路径

使用先序遍历和一个变量就可以进行判断

需要注意的一点就是判断到了叶子结点是使用root.left == null && root.right == null，如果没要求一定到达叶子结点，这个判断就可以去掉。

class Solution {
    private boolean isTrue = false;
    public boolean hasPathSum(TreeNode root, int targetSum) {
        preOrder(root,targetSum);
        return isTrue;
    }
    public void preOrder(TreeNode root,int sum){
        if(root == null){
            return;
        }
        if(root.left == null && root.right == null && sum == root.val){
            isTrue = true;
            return;
        }
        preOrder(root.left,sum-root.val);
        preOrder(root.right,sum-root.val);
    }
}

第二轮面试

1.关于Error的类

这里面试官强调要问我关于Java层的Error类的情况，不问平常的虚拟机错误呀之类的。

大家自己看看咯：https://www.sohu.com/a/127968069_631340

顺便给个结构树

2.https流程中客户端怎么验证证书

学习大佬文章：https://blog.csdn.net/liuxingrong666/article/details/83869161

总结其中要点：

• HTTPS的流程

  • 客户端请求HTTPS连接
  • 服务端返回证书（非对称加密的公钥），证书包含多种信息，如颁发机构，过期时间等
  • 客户端解析验证证书，验证成功则生成随机（对称）密钥
  • 使用（非对称加密的）公钥对（对称）密钥加密，然后发送给服务端
  • 服务端使用（非对称）私钥解密（对称）密钥，这样服务端也获得对称加密的密钥了
  • 双方使用（对称）密钥通信

• 由上面的流程可以看出验证证书的过程，发生在客户端，也就是发生在浏览器当中，验证的方式主要有三个要点：

  • 验证证书是否为受信任的权威机构颁发的

    浏览器收到证书后，从证书中得到颁发机构，然后从浏览器系统中去寻找此颁发机构的根证书（世界上权威CA机构的根证书都是预先嵌入到浏览器中的），在浏览器系统中没有找到对应的根证书，就代表此机构不是受信任的。

  • 验证证书是否被篡改

    使用根证书中的根公钥后去解密该证书的数字签名，解密成功后获得该证书的指纹和指纹算法，指纹是证书内容通过指纹算法计算得到的一个hash值，我们假设他是h1，然后此时浏览器再对证书使用指纹算法进行一次hash计算得到另一个值h2，如果h1=h2，说明证书没有被篡改。

  • 验证是否为服务器发过来的，而不是第三方发的

    证书中包含网站地址URL（具有唯一性），通过对比证书上的URL和我们请求的URL是否相同，我们还是可以判断当前证书是不是服务器发的证书。

3.Kotlin使用上的一些问题

因为简历上写了kotlin，所以这个也被面试官提问了一下，自从kotlin去年热度上来后，我相信新接触Android的同学也是多多少少对kotlin有一定的接触，这里列一下我自己的总结。

• 变量

  val var lateint

• 函数

  扩展函数
  静态函数
      companion object
      @JvmStatic
  高阶函数
      (a,b) -> Unit

• 类
  空指针检查
  协程

  轻量型速度快
  在单线程下模拟多线程变成的效果
  用于简化回调函数，避免写太多匿名接口实现类

• 其他

  字符串嵌入表达式
  运算符重载

算法题

1.剑指 Offer 09. 用两个栈实现队列

高频题+送分题了0.0应该很多人都做过了吧，栈A负责添加，栈B负责弹出，栈B的值从栈A取过来，即两次”后进先出“等于”先进先出“

class CQueue {
    LinkedList<Integer> a,b;
    public CQueue() {
        a = new LinkedList<>();
        b = new LinkedList<>();
    }

    public void appendTail(int value) {
        a.addLast(value);
    }

    public int deleteHead() {
        if(!b.isEmpty()) return b.removeLast();
        if(a.isEmpty()) return -1;
        while(!a.isEmpty()) b.addLast(a.removeLast());
        return b.removeLast();
    }
}

2.单例模式

线程安全懒汉和双重校验锁，并由此展开对synchronized和volatile相关知识的提问：

• 锁升级
• 为什么双重校验锁要用volatile而懒汉不用

懒汉线程安全：

//Java
public class Singleton {
    private static Singleton instance;
    private Singleton(){}

    public synchronized static Singleton getInstance(){
        if (instance == null){
            instance = new Singleton();
        }
        return instance;
    }
}
//kotlin
class Singleton private constructor() {
    companion object {
        private var instance: Singleton? = null
            get() {
                if (field == null) {
                    field = Singleton()
                }
                return field
            }
        fun get(): Singleton{
         return instance!!
        }
    }
}

双重校验锁：

//Java
public class Singleton {
    private volatile static Singleton instance;
    private Singleton(){}

    public static Singleton getInstance(){
        if (instance == null){
            synchronized (Singleton.class){
                if (instance == null) instance = new Singleton();
            }
        }
        return instance;
    }
}
//kotlin实现
//也可以像上面那样写，对应属性使用@volatile、@synchronized注解标记就行
class Singleton private constructor() {
    companion object {
        val instance: Singleton by lazy(mode = LazyThreadSafetyMode.SYNCHRONIZED) {
        Singleton() }
    }
}

第三轮面试

三面Leader面是我觉得这次面试最有价值的一个面试，也是我发挥失误的一次。

我先捧一波三面面试官：

• 知识渊博，擅长引导，我能明显感觉到他对于Android底层原理的熟悉，在我没有看过ListView源码的情况下，给我一些适当的引导提示，同时又不影响我思考发挥的空间。
• 认真负责，有耐心，逻辑缜密，一打我们开始视频聊天的时候，三面面试官就全程注意力在我身上，就跟当面眼神交流一样，然后写代码的时候，他也全程认真审视我的代码，思考我为什么会写出这样的代码，来判断我的逻辑思维。
• 看重个人解决问题的能力，遇到不会用的api的，他说没关系，按我的个人经验或者想法讲一下思路就可以。
• 替团队着想，我发现三面面试官问的问题大部分跟实际部门业务涉及到的场景或者知识有关，比如等下要提到的ListView的设计、在校课程之类的，这些都在反问环节他有提到。

啊0.0，有能力+认真负责+有耐心的Leader实在让我佩服，面试结束前他还主动给我讲了部门的业务和问我意向城市，我还想着有机会进字节一定要好好向他学习呢，可惜呀，没机会呢。

好了，看回题（算法题和面试题基本上是混在一起的）。

1.设计ListView

根据回忆在面试官交流中，提到大概以下问题

• 让你设计一个ListView，你会考虑什么问题
• 当我滑动ListView的时候，那些被滑走的View会发生什么，那些进来的View发生什么
• ListView中View的数据你是怎么处理的，是以怎样的方式处理
• 如果让你加载1000条数据，你会怎么操作
• ……

不管是哪个问题，其实都是围绕着ListView的原理去展开的，所以有必要去了解一下它的内部逻辑。（我没有看过0.0，所以当时回答是凭感觉围绕View复用+数据缓存方式等方面去扣题的）

大家可以看一下郭霖大佬的分析：https://blog.csdn.net/guolin_blog/article/details/44996879

我做下简单的总结，具体的话还请回归到文章中去细看，多看几遍：

• ListView的RecycleBin缓存机制起了很大的作用（后面提到的方法都来自它），当你滑动ListView，划出一个View的时候，就会调用addScrapView ()缓存划出的View，划入的时候就会调用getScrapView()，所以复用View的个数维持在可见的常数量（我想假如子View刚好5个填充满一个页面，往上滑动一点点可见应该是维护6个，第1个的一部分和第6个的一部分都进入界面了，这个有待考证），就可以节省很多资源，当然第一次进来的时候没有缓存就得直接加载布局。

• 正常View的绘制流程会进行两次onLayout()，普通View不影响，但是ListView中的layoutChildren()如果执行两次，就会产生多一份重复数据。ListView的解决方法：第一次onLayout()走正常流程得到一份视图数据，然后在第二次的时候，有判断子元素已经不等于0，所以触发调用RecycleBin缓存机制的fillActiveViews()方法，将视图数据全部缓存到mActiveViews（注意代码中设定mActiveViews中的每一个都是一次性使用，用完就回收）中，Detach第一次加载的数据，然后开始执行layoutChildren()方法时，判断发现mActiveViews不为空，然后循环attach到ListView，这样子视图又显示了。

• 在AbsListView.onTouchEvent()中有做滑动判断，代码集中在Move当中，处理的逻辑如下：

  • （ListView都是上下滑动的）计算Y轴的位移距离
  • 通过位移距离判断第一个View是否完全滑出，滑出就RecycleBin.addScrapView()添加到废弃缓存中，然后Detach
  • 所有子View都会随之滑动位移距离，代码中判断ListView中最后一个View的底部已经移入了屏幕，或者ListView中第一个View的顶部移入了屏幕时，就会对ListView进行填充

  所以1000条数据要加载的话，也是慢慢地来。（哈哈哈，机智的我回答了后端控制分页查询，面试官居然没叼我，哎，毕设后遗症）

  看看最核心的代码：

  View obtainView(int position, boolean[] isScrap) {  
      isScrap[0] = false;  
      View scrapView;  
      scrapView = mRecycler.getScrapView(position);  
      View child;  
      if (scrapView != null) {  
      |一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一|
      |child = mAdapter.getView(position, scrapView, this);|
      |____________________________________________________|    
          if (child != scrapView) {  
              mRecycler.addScrapView(scrapView);  
              if (mCacheColorHint != 0) {  
                  child.setDrawingCacheBackgroundColor(mCacheColorHint);  
              }  
          } else {  
              isScrap[0] = true;  
              dispatchFinishTemporaryDetach(child);  
          }  
      } else {  
          child = mAdapter.getView(position, null, this);  
          if (mCacheColorHint != 0) {  
              child.setDrawingCacheBackgroundColor(mCacheColorHint);  
          }  
      }  
      return child;  
  }

  @Override  
  public View getView(int position, View convertView, ViewGroup parent) {   
      View view;  
      if (convertView == null) {  
          view = LayoutInflater.from(context).inflate(resourceId, null);  
      } else {  
          view = convertView;  
      }   
      return view;  
  } 

  看见了没，各位大佬，这个就是为什么我们平常ListView的时候要做判断，因为convertView就是scrapView，如果每次都inflate的话，就很消耗资源，ListView对于我们new的View都缓存好了，拿来吧你0.0

2.LRU的设计和测试

因为前边缓存方式提到了LRU，所以面试官让我写一个，高频题相信大家大部分都写过吧

代码如下：

package com.zhangxiaotou;

import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;

public class LruCache {
    public static void main(String args[]) throws Exception {
        LRUCache lruCache = new LRUCache(6);
        lruCache.put(1, 1);
        lruCache.put(2, 2);
        lruCache.put(3, 3);
        lruCache.put(4, 4);
        lruCache.put(5, 5);
        lruCache.put(6, 6);
        lruCache.get(1);
        System.out.println(lruCache.getHead());
        System.out.println(lruCache.getTail());
    }

    static class LRUCache {
        LinkedHashMap<Integer, Integer> map;
        int capacity;

        public LRUCache(int capacity) {
            map = new LinkedHashMap<>();
            this.capacity = capacity;
        }

        public int get(int key) throws Exception {
            if (!map.containsKey(key))  throw new Exception("找不到");
            int value = map.remove(key);
            map.put(key, value);
            return value;
        }

        public void put(int key, int value) {
            if (map.containsKey(key)) {
                map.remove(key);
                map.put(key, value);
                return;
            }
            map.put(key, value);
            if (map.size() > capacity) {
                map.remove(map.entrySet().iterator().next().getKey());
            }
        }

        public int getTail() {
            Iterator<Map.Entry<Integer, Integer>> iterator = map.entrySet().iterator();
            Map.Entry<Integer, Integer> tail = null;
            while (iterator.hasNext()) {
                tail = iterator.next();
            }
            return map.get(tail.getKey());
        }

        public int getHead() {
            return map.get(map.entrySet().iterator().next().getKey());
        }

    }
}

哈哈，是不是有点不一样，不一样就对了，因为看你写的快，总不能这么轻易就跳过吧，面试官问了大概以下问题

• 你怎么给你写的LruCache做测试呢

• 如果get()方法一定不能return -1(力扣原题都是返回-1)你怎么办？

• 结合你的debug经验，你怎么设计测试用例呢

• ……

上面是利用LinkedHashMap的性质去实现的LRU算法，实际上Android中的LruCache也是利用它是去实现，所以我有必要搞懂它。大家先去做一下力扣原题，学一下题解。然后我提一下，LinkedHashMap的最近最少未使用的在队头，最常使用在队尾，然后结合问题再去看代码应该就看得懂了。

算法题

字节每一个面试基本上两题吧，面试官看了看时间，说不如再来一题吧，然后我就a不出这个题了0.0

面试题 16.26. 计算器

题目大概是给出这样一个字符串 "1 + 2 * 3 / 4 =" 然后输出一个结果。

没做过这个题（字符串的题做得少T.T），但是有一点思路，正因为有一点思路，然后在关键点的判断出错，导致面临很多种要处理的情况，就a不出来了。面试官也是看出我思路，最后做不出来给我提示了一下，我就秒懂了0.0

• 思路一：双栈

这是我一开始的思路

基本思路：

①栈1存储整数，栈2存储运算符

②从左到右遍历字符数组，做以下判断：

​ 若为空格，则跳过。（力扣题例子有空格，面试不要求）

​ 若为数字，提取连续整数（力扣题存在多位数，面试不要求），存入栈1

​ 若为运算符时，如果ch[i]的优先级比栈2顶的运算符高，那么ch[i]入栈2；如果不是，则弹出栈2栈顶运算符，和栈1两个整数，进行计算后存回栈1（面试时我在这里就判断错误，如果时一遇到优先级高话就计算的话，就得处理很复杂的多种情况，而当判断判断优先级低的时候才弹出计算的话，就可以排除很多种情况。）

③遍历完字符数组后，要对栈2内剩余的运算符进行处理，使用while循环

④最终结果保留在栈1栈顶，弹出即可。

代码如下：

//参考力扣题题解大佬https://leetcode-cn.com/problems/calculator-lcci/solution/shuang-zhan-suan-fa-by-jason-2-ctqy/
class Solution {
    Stack<Integer> stack1 = new Stack<>();
    Stack<Character> stack2 = new Stack<>();
    public int calculate(String s) {
        char[] ch = s.toCharArray();
        for(int i = 0 ; i < ch.length; i++){
            if(ch[i] == ' '){
                continue;
            }else if(Character.isDigit(ch[i])){
                int d = 0;
                //力扣题case存在多位数
                while((i< ch.length)&&Character.isDigit(ch[i])){
                    d = d*10 + (ch[i] - '0');
                    i++;
                }
                i--;
                stack1.push(d);
            }else {                
                while(!stack2.isEmpty() && !priority(ch[i],stack2.peek())){
                    cal();
                }
                stack2.push(ch[i]);
            }
        }
        //处理栈2剩余运算符
        while(!stack2.isEmpty()){
            cal();
        }
        return stack1.pop();
    }

    public void cal(){
        int b = stack1.pop();
        int a = stack1.pop();
        char op = stack2.pop();
        int res = 0;
        switch(op){
            case '+':res = a + b;break;
            case '-':res = a - b;break;
            case '*':res = a * b;break;
            case '/':res = a / b;break;
        }
        stack1.push(res);
    }
    //判断优先级
    public boolean priority(char a,char b){
        if(a == '+' || a == '-'){
            return false;
        }else if(a == '*' || a == '/'){
            return (b == '+'||b =='-');
        }
        return false;
    }
}

• 思路二：单栈

大家直接看这里吧，大佬讲得巨细，就不重复了：https://leetcode-cn.com/problems/calculator-lcci/solution/shu-ju-jie-gou-he-suan-fa-shi-yong-zhan-h9r0r/

• 其他情况：带括号

出现表达式带括号的情况，可以利用上面单栈的思路+递归，来实现括号内的计算。具体参见大佬：https://blog.nowcoder.net/n/65fcad0be1a543359effef1228ae5d2e

第四轮面试

一开始以为约的是HR面，还有些开心，知道是加面之后，心想着大概率就是凉凉了，只能说四面体验一般吧。

1.介绍了一下其中一个项目，没提问题

2.OOP有什么特性

3.设计模式知道多少

4.面向对象六大原则

5.知道哪些数据结构

6.知道B+树吗，有什么特点，为什么能够查询得快

7.扯到hashmap结构，提到红黑树，问红黑树的特性以及和平衡二叉树的区别

8.问红黑树和B+树的区别

9.知道跳表是什么吗，面试官给我科普了一下

算法题

跳表的查询

猛男落泪T.T，我想问问大家这个是不是第一次考呢

查了力扣也确实有跳表的题，跳转入口在这里：1206. 设计跳表

不过力扣比较难，而且是设计全部，这里只要求我写一个查询而已，我也是第一次知道这个概念，接下来我们一起来学习一下。

请先阅读大佬文章：https://zhuanlan.zhihu.com/p/200815425?ivk_sa=1024320u

总结如下：

• 跳表是多级链表，每次新增一层索引链表的结点个数是上一层链表的一半，查找上一层结点所需的访问次数也相应减少了一半，相当于使得有序链表能够二分查询。

• 假设原始链表有n个结点，那么索引的层级就是log(n)-1，在每一层的访问次数是常量，因此查找结点的平均时间复杂度是O（logn），但是优化之后的数据结构所占空间，是原来的2倍。这是典型的以空间换时间的做法

• 查询：最上层会提供一个Head结点，假如我们要查询20，开始找的时候，是从最上层（如图第2层索引）的索引开始查找，找到该层中仅小于结点20的前置索引结点12，然后顺着结点12访问下一层索引，在该层中找到结点20，最后就定位到原始链表的20，即查询得到。

• 插入和删除请仔细看上面文章，这里不做展开，注意插入的时候会有“晋升”的操作，删除的时候会连带删除

• 虽然理解的时候是图示是单链表，但是实际上跳表使用的是双向链表，每个结点相互指向，头结点和尾结点会有一边指向无穷。

看完上面的文章，应该能理解个大概了，然后看看查询代码：

这个是文章中大佬写的：

    //查找结点
    public Node search(int data){
        Node p= findNode(data);
        if(p.data == data){
            System.out.println("找到结点：" + data);
            return p;
        }
        System.out.println("未找到结点：" + data);
        return null;
    }

    //找到值对应的前置结点
    private Node findNode(int data){
        Node node = head;
        while(true){
            while (node.right.data!=Integer.MAX_VALUE && node.right.data<=data) {
                node = node.right;
            }
            if (node.down == null) {
                break;
            }
            node = node.down;
        }
        return node;
    }

代码不是很复杂，应该能看懂吧。再次强调一点就是，head结点是最上层索引的第一个结点，面试的时候因为第一次接触并且面试官的图单独画出一个head，我一直以为head是独立出来的最上层索引，知道我看了上面文章才知道。

各位大佬，还是好好做题吧，说不定下次就出跳表的插入和删除了呢。

写在后

相信很多同学都是遇到惜败的情况，这里也希望大家不要灰心，毕竟面试本来就是一个学习和弥补不足的一个过程，你去付出时间和尝试肯定是会有收获的。

当然其中也是有运气成分在里面啦，各种原因都可能导致失败，总不可能每个人都那么幸运，除非你十分的优秀。

虽然刷了很多题了，但是还是会遇到没有做过的题，这个只能是脚踏实地去弥补了。当然我个人觉得算法不是全部咯，具体还是得看个人解决实际问题的能力，所以大家也不要因为失败而灰心。

最后，感谢每一个给我机会面试的公司和面试官，一起加油！