字节跳动Java岗6月9号一面经验分享，是真的有难度

前言

• 自我介绍
• 看你简历上写了死锁，简单介绍一下？ 更改你的代码，使死锁解除？
• 讲讲系统调用？
• 进程线程区别？
• 进程通信几种方式？哪种方式最快？为什么？
• 进程怎么分配的？PCB里面都有什么？为什么进程上下文切换消耗大量资源？
• 进程调度算法？
• 刚刚你说到零拷贝，简单说一下过程？
• 谈谈你常用的数据结构
• 你都知道哪些树结构？说说他们特性？（搜索树、平衡树、红黑树、B树、B+、霍夫曼）
• 细讲红黑树
• 霍夫曼树算法贪心策略证明。
• 刚刚你说到栈和队列可以互相转换，写出代码。
• 说说常见的排序算法
• 快排缺点？怎么避免？手撕上面3个算法？

• 我还有什么需要增强的？
• 如果可以参加项目开发，我还需要学习什么新技术？

题解

1、自我介绍

• 我是谁
• 我的三个亮点，最近最相关的经历？
• 我为什么想要这份工作？

2、死锁怎么解决

• 死锁预防
• 死锁避免
• 死锁检测
• 死锁解除

3、系统调用

系统调用的功能与其作用一样——涉及计算机资源的操作

• 设备管理：完成设备的请求/释放以及设备的启动
• 文件管理：完成文件的读写、删除、创建等功能
• 进程控制：完成进程的创建、撤销、阻塞以及唤醒等功能
• 内存管理：完成内存的分配、回收以及获取作业占用内存区大小和地址等功能

4、进程线程的区别

5、进程通信的几种方式

• 无名管道( pipe )：管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。
• 高级管道(popen)：将另一个程序当做一个新的进程在当前程序进程中启动，则它算是当前程序的子进程，这种方式我们成为高级管道方式。
• 有名管道 (named pipe) ： 有名管道也是半双工的通信方式，但是它允许无亲缘关系进程间的通信。
• 消息队列( message queue ) ： 消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。
• 信号量( semophore ) ： 信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。
• 信号 ( sinal ) ： 信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。
• 共享内存( shared memory ) ：共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的 IPC 方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号两，配合使用，来实现进程间的同步和通信。
• 套接字( socket ) ： 套接口也是一种进程间通信机制，与其他通信机制不同的是，它可用于不同机器间的进程通信。

6、进程调度算法

• 先来先服务（FCFS）调度算法
• 短作业优先（SJF）调度算法
• 时间片轮转（RR）调度算法
• 最高优先级优先调度算法
• 多级反馈队列(MFQ)调度算法

7、零拷贝过程

8、常用的数据结构

9、霍夫曼树算法贪心策略证明

• 我们把每个字符看作一个节点，并且附带着把频率放到优先级队列中。
• 我们从队列中取出频率最小的两个节点 f（20）、e（30）
• 然后新建一个节点 x（50），把频率设置为两个节点的频率之和，并把这个新节点 x（50）作为 f（20）和 e（30）的父节点。
• 最后再把 x（50）放入到优先级队列中。重复这个过程，直到队列中没有数据。

• 现在我们统一给每一条边画一个权值，指向左子节点的边我们通通标记为 0，指向右子节点的边，我们通通标记为 1，那么从根节点到叶节点的路径就是叶节点对应字符的霍夫曼编码。

10、栈和队列转换代码

	#include <iostream>
#include "LinkQueue.h"
#include "LinkStack.h"
using namespace std;
using namespace DTLib;
template < typename T >
class QueueToStack : public Stack<T>
{
    protected:
        LinkQueue<T> m_queue_1;
    LinkQueue<T> m_queue_2;
    LinkQueue<T>* m_pIn;
    LinkQueue<T>* m_pOut;
    void move() const   //O(n)
    {
        int n = m_pIn->length() - 1;
        for (int i = 0; i < n; i++)
                {
            m_pOut->add(m_pIn->front());
            m_pIn->remove();
        }
    }
    void swap() //O(1)
    {
        LinkQueue<T>* temp = NULL;
        temp = m_pIn;
        m_pIn = m_pOut;
        m_pOut = temp;
    }
    public:
        QueueToStack()
        {
        m_pIn = &m_queue_1;
        m_pOut = &m_queue_2;
    }
    void push(const T &e)   //O(1)
    {
        m_pIn->add(e);
    }
    void pop()      //O(n)
    {
        if(m_pIn->length() > 0)
                {
            move();
            m_pIn->remove();
            swap();
        } else
                {
            THROW_EXCEPTION(InvalidOperationException, "No element in current stack ...");
        }
    }
    T top() const   //O(n)
    {
        if(m_pIn->length() > 0)
                {
            move();
            return m_pIn->front();
        } else
                {
            THROW_EXCEPTION(InvalidOperationException, "No element in current stack ...");
        }
    }
    void clear()    //O(n)
    {
        m_queue_1.clear();
        m_queue_2.clear();
    }
    int size() const
        {
        return m_queue_1.length() + m_queue_2.length();
    }
}
;
int main()
{
    QueueToStack<int> qs;
    for (int i = 0; i < 10; i++)
        {
        qs.push(i);
    }
    while(qs.size() > 0)
        {
        cout << qs.top() << "  ";
        qs.pop();
    }
    return 0;
}

	#include <iostream>
#include "LinkQueue.h"
#include "LinkStack.h"
 
 
using namespace std;
using namespace DTLib;
 
template < typename T >
class StackToQueue : public Queue<T>
{
protected:
    mutable LinkStack<T> m_stack_in;
    mutable LinkStack<T> m_stack_out;
 
    void move() const   //O(n)
    {
        if(m_stack_out.size() == 0)
        {
            while(m_stack_in.size() > 0)
            {
                m_stack_out.push(m_stack_in.top());
                m_stack_in.pop();
            }
        }
    }
 
public:
    void add(const T &e)    //O(1)
    {
        m_stack_in.push(e);
    }
    void remove()   //O(n)
    {
        move();
 
        if(m_stack_out.size() > 0)
        {
            m_stack_out.pop();
        }
        else
        {
            THROW_EXCEPTION(InvalidOperationException, "No element in current queue ...");
        }
    }
    T front() const     //O(n)
    {
        move();
 
        if(m_stack_out.size() > 0)
        {
            return m_stack_out.top();
        }
        else
        {
            THROW_EXCEPTION(InvalidOperationException,"No element in current queue ...");
        }
    }
    void clear()    //O(n)
    {
        m_stack_in.clear();
        m_stack_out.clear();
    }
 
    int length() const  //O(1)
    {
        return m_stack_in.size() + m_stack_out.size();
    }
 
};
 
int main()
{
    StackToQueue<int> sq;
 
    for(int i = 0; i < 10; i++)
    {
        sq.add(i);
    }
 
    while(sq.length() > 0)
    {
        cout << sq.front() << "  ";
 
        sq.remove();
    }
 
    return 0;
}

小结