精华内容
下载资源
问答
  • 面经_牛客网

    2021-01-13 17:02:04
    4、求Y型链表的交点 有没有更的算法 记录两个链表的长度差。然后长的那个先出发,当剩下的长度和短的相同时,短的链表也发。 当两个链表遍历到结点相同时,为相交结点。 若两个链表无交点,则最后...

    原帖子链接:https://www.nowcoder.com/discuss/563162

    我把自己能回答的东西补充上,欢迎大家指正。

    写一个翻转字符串

    4、求Y型链表的交点  有没有更快的算法

    记录两个链表的长度差。然后长的那个先出发,当剩下的长度和短的相同时,短的链表也发。

    当两个链表遍历到结点相同时,为相交结点。

    若两个链表无交点,则最后结点为NULL,直接返回即可

    5、设计题:多线程并发 生产者消费者问题

    不能换,产生死锁,生产者先mutex->P(),然后emptyBuffer->P,empty<0,睡眠,消费者也因为mutex=0,无法获取面包,产生死锁 

    6、设计模式中的单例模式?

    构造函数写成private,通过函数调用,这样对象只有一个实例。

    7、 Hashmap底层实现

    我们都知道HashMap是数组+链表组成的,bucket数组是HashMap的主体,而链表是为了解决哈希冲突而存在的,但是很多人不知道其实HashMap是包含树结构的,但是得有一点 注意事项,什么时候会出现红黑树这种红树结构的呢?我们就得看源码了,源码解释说默认链表长度大于8的时候会转换为树。(Java实现里,C++不确定是不是也包含红黑树)

    8、 Timewait什么时候产生,有什么作用

    9、设计题:大文件统计单词频率

    map<string,int>

    10、 Gdb多线程调试

    11、程序死掉了 没有core文件怎么查

    7.7 

    1、malloc和new区别

    C++中free()与delete的区别

    • new/delete是C++的操作符,而malloc/free是C中的函数。
    • new做两件事,一是分配内存,二是调用类的构造函数;同样,delete会调用类的析构函数和释放内存。而malloc和free只是分配和释放内存。
    • new建立的是一个对象,而malloc分配的是一块内存;new建立的对象可以用成员函数访问,不要直接访问它的地址空间;malloc分配的是一块内存区域,用指针访问,可以在里面移动指针;new出来的指针是带有类型信息的,而malloc返回的是void指针。
    • new/delete是保留字需要头文件支持;malloc/free需要头文件库函数支持。

    2、进程和线程的区别

    进程和线程的区别  

    进程和线程的根本区别是进程是操作系统资源分配的基本单位,而线程是处理器任务调度执行的基本单位。另外区别还有资源开销、包含关系、内存分配、影响关系、执行过程等。

    资源开销:每个进程都有独立的代码和数据空间(程序上下文),程序之间的切换会有较大的开销;线程可以看做轻量级的进程,同一类线程共享代码和数据空间,每个线程都有自己独立的运行栈和程序计数器(PC),线程之间切换的开销小。

    包含关系:如果一个进程内有多个线程,则执行过程不是一条线的,而是多条线(线程)共同完成的;线程是进程的一部分,所以线程也被称为轻权进程或者轻量级进程。

    内存分配:同一进程的线程共享本进程的地址空间和资源,而进程之间的地址空间和资源是相互独立的。

    影响关系:一个进程崩溃后,在保护模式下不会对其他进程产生影响,但是一个线程崩溃整个进程都死掉。所以多进程要比多线程健壮。

    执行过程:每个独立的进程有程序运行的入口、顺序执行序列和程序出口。但是线程不能独立执行,必须依存在应用程序中,由应用程序提供多个线程执行控制,两者均可并发执行。

    进程和线程的根本区别是进程是操作系统资源分配的基本单位,而线程是处理器任务调度和执行的基本单位

    3、IPC

    IPC(Inter-Process Communication)进程间通信,提供了各种进程间通信的方法。在Linux C编程中有几种方法
    (1) 半双工Unix管道
    (2) FIFOs(命名管道)
    (3) 消息队列
    (4) 信号量
    (5) 共享内存
    (6) 网络Socket

    4、线程的同步和互斥

    初始时设置mutex=1,

    thread1 进入临界区 进行P操作(减1到0),退出时V操作,唤醒thread2,thread2开始执行(同步操作)。

    5、TCP和UDP,如果UDP想可靠怎么做   TCP/UDP区别以及UDP如何实现可靠传输

    由于在传输层UDP已经是不可靠的连接,那就要在应用层自己实现一些保障可靠传输的机制

    简单来讲,要使用UDP来构建可靠的面向连接的数据传输,就要实现类似于TCP协议的

    超时重传(定时器)

    有序接受 (添加包序号)

    应答确认 (Seq/Ack应答机制)

    滑动窗口流量控制等机制 (滑动窗口协议)

    等于说要在传输层的上一层(或者直接在应用层)实现TCP协议的可靠数据传输机制,比如使用UDP数据包+序列号,UDP数据包+时间戳等方法。

    目前已经有一些实现UDP可靠传输的机制,比如

    UDT(UDP-based Data Transfer Protocol)
    基于UDP的数据传输协议(UDP-based Data Transfer Protocol,简称UDT)是一种互联网数据传输协议。UDT的主要目的是支持高速广域网上的海量数据传输,而互联网上的标准数据传输协议TCP在高带宽长距离网络上性能很差。 顾名思义,UDT建于UDP之上,并引入新的拥塞控制和数据可靠性控制机制。UDT是面向连接的双向的应用层协议。它同时支持可靠的数据流传输和部分可靠的数据报传输。 由于UDT完全在UDP上实现,它也可以应用在除了高速数据传输之外的其它应用领域,例如点到点技术(P2P),防火墙穿透,多媒体数据传输等等。

    6、GET和POST  GET和POST两种基本请求方法的区别

    • 表面上区别,GET把参数包含在URL中,POST通过request body传递参数
    • GET和POST本质上就是TCP链接,并无差别。但是由于HTTP的规定和浏览器/服务器的限制,导致他们在应用过程中体现出一些不同。
    • GET产生一个TCP数据包;POST产生两个TCP数据包。对于GET方式的请求,浏览器会把http header和data一并发送出去,服务器响应200(返回数据);

       

      而对于POST,浏览器先发送header,服务器响应100 continue,浏览器再发送data,服务器响应200 ok(返回数据)

    7、讲一下红黑树的特点   红黑树的特性   图示讲解AVL平衡二叉树的左旋和右旋

    8、常用的排序算法有哪些, 哪些是稳定,哪些是不稳定

    具体的复习这篇博客912. Sort an Array排序复习 快速排序,选择排序,插入排序,归并排序,堆排序 

    9、后缀表达式复原

    复原其实就是后缀表达式的计算过程了,比如6/3变成后缀表示式63/,op1=3,op2=6, op2 +   操作符c  +   op1就是结果了,"6/3"

    10、智能指针介绍一下

    智能指针的行为类似常规指针,重要的区别是它负责自动释放所指向的对象。

    【C++】智能指针详解

    11、虚函数说一下

    non-virtual函数:你不希望子类derived class重新定义override它

    virtual函数:你希望子类重新定义它,且你对它已经有默认定义

    pure virtual函数:你希望子类一定要重新定义它,你对它没有默认定义

    7.12 

    1、聊一聊从一层到四层

    TCP/IP协议族四层模型简述

    2、介绍一下重传机制

    TCP超时与重传机制

    3、TCP怎么建立连接

    tcp建立连接为什么需要三次握手

    4、TCP挥手过程

    tcp挥手

    5、TIMEWAIT说一下

    6、closewait说一下

    7、select、poll、epoll

    select、poll、epoll之间的区别

    8、epoll为什么用红黑树

    9、讲讲HTTPS怎么建立起来的

    10、数据库ACID

    11、

    LRU

    算法,怎么实现

     

    12、快排原理说一下,怎么优化,为什么这么优化、

    主要的优化就是在选取pivot的时候,选择一个合适的,最好整个序列的中间值,这样能保证每次左右2边元素个数相同,复杂度是真正的log,所以优化就是三数取中,

    待排序序列为:8 1 4 9 6 3 5 2 7 0

    左边为:8,右边为0,中间为6.取三个数排序后,中间那个数作为枢轴,则pivot枢轴为6。可以阅读这篇博客快速排序的5种优化方法

    13、算法题:两个有序数组,找到第K个数

    7.14 

    1、自我介绍

    2、北京的实习经历,深挖(10多分钟)

    3、TCP协议有几层( ????没听说过这个概念,是TCP/IP协议栈吧??)

    4、TCP超时重传机制,时间是多少

    5、RTT是什么

    6、TCP的慢启动,拥塞避免

    7、epoll模型的优点

    8、想做运维还是开发?

    7.14 

    1、先说项目

    2、epoll原理说一下

    3、项目性能测过吗

    4、C++比C多了哪些内容

    5、C++多态,虚函数

    6、类的成员函数前后const有什么作用

    7、static作用(围绕这个问了很多)

    8、const作用

    9、C++的堆和栈区别

    10、C语言中的volatile

    11、线程同步的方式

    12、进程通信的方式

    13、线程和进程的区别

    14、指针和引用的区别

    15、i++和++i区别

    7.15 

    1、自我介绍

    2、局域网两台主机怎么跨路由访问192.168.1.1 ------192.168.100.1

    3、ARP深挖原理,字段

    4、TCP包的内容以及大小

    5、数据包头有什么,多大

    6、IP包详细讲

    7、为什么划分子网

    8、socket api详细说Bind绑定哪些信息,可以不bind吗?

    9、accept是阻塞还是非阻塞,有什么区别,怎么设置

    10、端口只有65536个,那么连接只能建立这么多吗

    11、一个连接大概消耗服务器多少内存

    12、TCP哪些情况会超时

    13、套接字属性怎么改

    14、阻塞IO、非阻塞IO,怎么设置呢,其他IO模型

    15、epoll的触发方式,除了epoll还有哪些,有什么区别

    7.16 

    1、自我介绍

    2、算法题

    写一个程序,在一个100万的有序数组中,判断是否存在两个数的和等于key。

    bool  find_sum_key(int [] arr,  int len,  int  key);

    3、linux进程内存空间布局

    4、堆和栈的区别

    5、构造函数能不能是虚函数

    6、基类的析构函数为什么是虚函数

    7、引用和指针的区别

    8、代码哪些情况会产生coredump

    9、TCP断开连接为什么多一次

    10、timewait怎么产生

    11、查看网络连接命令,如果大量timewait是什么原因

    说明关闭了很多连接?

    12、线程和进程的区别

    7.17

    1、自我介绍

    2、平台大量timewait什么原因,timewait最长多久

    3、大量SYN半连接,怎么预防?

    4、socket 的写服务端建立连接的步骤?

    服务端先建立一个sockaddr_in这样的一个结构体存放ip地址和port号,然后再使用bind()函数把它和一个socket变量(sock)结合,然后开始listen监听套接字sock,再新建一个client的sockaddr_in这样一个结构,然后就可以利用accept函数去sock接受这样的一个client连接了。

    再之后就可以用recv函数来接收数据了。

    linux网络编程基础api

    5、虚函数怎么实现的?

    6、对象,成员,父类成员构造,析构顺序?

    7、STL  map的底层实现?

    8、应用层协议都有哪些?

    9、https 证书机制

    10、国密算法 椭圆?

    11、char  buf[10]; delete[] buf;  delete  buf; 有什么区别?

    12、写一个单生产者单消费者,的一个环形队列

    13、想做哪一块工作

    7.18 

    1、自我介绍

    2、手撕代码 归并排序

    3、归并排序和快速排序的特点,以及使用场景,如果近似有序用什么

    4、数据流每次调用函数返回一个数,使他们有序

    5、

    LRU

    怎么实现的

     

    7.18 

    1、项目介绍

    2、读过什么书,看过什么源码(说了STL源码剖析),问了vector push_back实现

    3、

    反转链表

     

    4、struct A { char a; int b;} 和 struct A { int b; char a; } 32位下sizeof多大

    5、较长字符串求子串

    6、IP层的协议,应用场景

    7.20 

    1、项目介绍,AC自动机复杂度,怎么优化,

    LRU

    ,EPOLL

     

    2、timewait closewait

    3、服务器大量closewait 客户端只有少量连接怎么回事

    4、raii机制

    5、new和malloc,malloc底层原理

    6、共享内存介绍一下

    7、进程内存分布,每个区都存什么内容

    8、GDB调试

    9、函数怎么运行的

    10、数据库索引有哪些

    11、hash索引扩容?冲突处理

    12、同步和异步,阻塞和非阻塞

    13、二叉树找第K大的数

    7.20 

    1、项目介绍

    2、TCP三次握手,怎么优化

    3、epoll对比select poll 的优点,是同步还是异步

    4、

    LRU

    算法,劣势是什么,怎么弥补 (答了LFU)

     

    5、LFU怎么设计

    6、阻塞和非阻塞

    7、c++11特性知道哪些,智能指针的原理,右值引用的作用

    8、malloc和new,free和delete

    9、malloc底层原理

    10、怎么在一个端口绑定多个进程

    11、用过什么排序,堆排序讲一讲

    12、GDB一般用哪些

    13、一个大数据量日志文件,内存有限,怎么找到访问频率最高的100个IP

    14、用过什么锁,自旋锁和互斥锁的区别,使用场景

    15、无锁编程

    7.21

    1、项目介绍,

    LRU

    ,为什么用hash,hash缺点,怎么实现的hash表

     

    2、排序算法有哪些,快排和归并分析区别,场景

    3、熟悉哪些树,怎么存

    4、项目介绍继续

    7.23 

    1、项目介绍

    2、作为组长需要关注哪些事情,从中做了哪些工作

    3、项目中遇到压力最大的事,怎么解决的

    4、项目中的问题,事后总结了吗

    5、除了通宵修改,还有其他方案吗

    6、本科的四年时间怎么分配的

    7、为啥对JAVA不感兴趣

    8、优势和缺点,针对不足怎么改进

    9、最近半年系统学过什么,学习途径,看过什么书

    10、linux文件系统简述一下

    11、常用的linux命令

    12、用C语言单向链表实现一个栈的pop 和 push

    13、TCP和UDP区别,应用场景

    14、如果入职公司三个月,领导分配一个完全新的任务,怎么完成

    15、对于工作选择有什么规划

    16、工作地点意向

    7.28 

    1、项目介绍(深挖)

    2、epoll和poll区别,epoll底层实现,什么情况poll会更快

    3、继续项目和实习经历

    4、快排原理,最坏情况是什么样

    5、访问百度完整流程

    7.31

    1、项目介绍

    2、epoll select poll

    3、阻塞 非阻塞

    4、LRU

    5、IPC,线程同步方式

    6、两个进程通信,收到一个包,怎么区分具体是打给哪个进程

    7、网卡收到包的内核实现

    8、线程池的作用

    9、排查问题用到哪些命令,工具

    7.31

    1、项目介绍(深挖)

    2、用户态和内核态,怎么切换

    3、虚拟内存、页表、页面置换算法

    4、IP转发的过程

    5、接下来问了十多个生活问题

    8.3 

    1、毕设+项目介绍 十分钟就完事了。。。

    8.3

    1、自我介绍

    2、map和hashmap

    3、手写hashmap的find和insert

    4、项目中怎么设计针对某条流,流量过大

    5、对加班怎么看

    6、如果组员任务没完成,明天deadline,怎么办

    8.4 

    1、自我介绍,项目难点(详细说了radix tree)

    2、对编程语言的倾向(主要做JAVA)

    3、手撕代码

    Vector<int> nums{1,2,3,4,5}

    Int k = 4;

    Int x = 3;

    输出2 3 4 5

    给定有序数组,找到最接近x的k个数

    4、老家哪?愿意来上海吗

    8.4 

    1、看程序说结果

    一个基类,一个派生类,实例一个派生类对象。考察构造和析构顺序

    2、关于虚函数的考察,也是看程序,运行时多态

    3、override

    4、智能指针和原生指针的区别,实现原理,vector容器里可以放unique_ptr吗为什么

    5、四种类型转换,区别,还是看程序,需要用哪种转换,为什么

    6、c++11 特性 move auto

    7、#ifdef 的作用 (主要为了防止重定义)

    8、TCP三次握手,socket编程介绍

    9、高并发下的epoll模型

    10、五中IO模型,非阻塞和阻塞,非阻塞式异步模型吗,非阻塞读到什么情况结束

    11、epoll底层原理

    12、页表,TLB,MMU

    13、项目

    14、线程池的作用,线程数量怎么确定

    8.4 

    1、c++多态怎么理解,虚函数表有深入了解吗

    2、c++ this

    3、深拷贝和浅拷贝,默认的拷贝构造函数是深拷贝还是浅拷贝

    浅拷贝,c++的默认拷贝构造函数,从深度拷贝和浅拷贝说起

    4、C++使用new一个对象,可不可以用malloc(其实就是考察区别)

    5、c++引用用在什么时候

    https://blog.csdn.net/msyyxwf/article/details/92969556

    6、const在*的左右侧区别

    const出现在星号左边,表示被指物是常量;如果出现在星号右边,表示指针自身是常量;出现在星号两边,表示被指物和指针两者都是常量。

    有些人习惯不同,以星号的左边右边为判断准则。

    7、static作用

    static对象,其寿命从被构造出来一直到程序结束为止。不会因为函数返回而失效

    当static作用于非类内函数的局部变量时,每次函数调用不会随着函数返回而失效,当static作用于类内成员时,由该类所有对象共同维护和使用,从而实现同一个类的不同对象数据共享。 

    C++中的static的作用

    8、vector底层原理,reserve和resize区别,erase中间元素会发生什么

    9、map、红黑树

    10、C++析构函数和析构函数可以为虚函数吗

    11、进程通信方式

    12、socket编程过程

    13、select和epoll

    14、数据库了解吗?(了解不深。。)什么是事务

    15、聚簇索引和非聚簇索引

    16、隔离级别,什么情况幻读,哪种隔离级别可以避免幻读

    17、快速排序原理

    8.5 

    1、项目介绍

    2、close wait,为什么要有这个状态

    3、客户端断开连接的TCP状态机,timewait作用,如果没有timewait怎么样

    4、

    LRU

    设计,为什么

     

    5、多进程和多线程区别,为什么用多线程,缺点

    6、线程的私有和共有,文件句柄共享吗,信号处理函数共享吗,收到一个信号多线程怎么处理。

    7、陷入内核态的方式有哪些,举例说明

    8、malloc是通过什么方式进入内核

    通过brk和mmap这两个系统调用

    9、异常了解吗,分配内存的过程,是物理内存吗,会产生什么异常

    10、#ifdef作用

    11、define和static inline区别

    12、C语言用过哪些attribute,#pragma pack(n)和__attribute__ ((packed))区别

    13、大端小端,写个程序验证一下

    14、访问一个163.com经过的过程,详细说,NAT在哪里设置

    15、iptables了解吗

    16、免费ARP

    17、事务是什么

    18、隔离级别

    19、索引,索引实现方式,区别

    20、

    写一个二分查找,补充,数据可能重复,要找到第二个目标值

     

    8.5

    1、TCP和UDP区别

    2、因为是数据,对数据库要求比较高,问了数据库,不会。。

    3、算法:检验字符串是否是合法IP

    总结:不合适。。不知道为啥捞我,很迷

    8.5

    1、自我介绍,突出特点(感觉是个四十多岁大佬,经常打断我,只想听重点)

    2、举例佐证自己的那些特点

    3、两个项目都深挖,问到了SNI的作用(没说好,大佬牛逼)

    给我讲证书是跟SNI绑定的,而不是IP,所以需要SNI。

    4、算法题

    用两个栈,实现一个队列

     

    5、期望工作地点,目前的找工作进度

    8.6

    1、const作用

    https://www.cnblogs.com/readlearn/p/10806546.html

    2、this指针

    3、指针和引用的区别

    4、main函数执行前有哪些流程,操作系统运行一个程序的流程

    https://blog.csdn.net/junbopengpeng/article/details/14143995

    5、extern C

    6、空类包含哪些函数

    7、构造函数可以是虚函数吗

    8、析构函数可以抛异常吗

    9、new和malloc

    10、sort支持哪些容器,用的什么排序算法

    Vector deque string array 这些支持随机迭代器的可以

    11、linux fork有几个返回值,底层实现

    https://www.cnblogs.com/tp-16b/p/9005079.html#_label2

    12、线程和进程的区别

    13、IPC,最快的方式是什么,共享内存的实现原理

    14、共享内存加锁怎么加,还有其他方式吗

    锁放在共享内存里

    15、文件锁了解吗

    16、信号量的原理

    17、linux文件系统,linux内核怎么读出文件的内容呢,怎么找到inode

    18、read的返回值

    19、TCP怎么做到可靠的

    20、TCP状态机,timewait

    21、select和epoll,最重要的区别

    22、TCP长连接,突然拔掉网线会怎么样,如果传输数据呢

    23、什么是事务

    24、ACID,原子性怎么做到的

    25、隔离级别,为什么要隔离,不同隔离级别会产生哪些问题

    26、快速排序

    27、

    链表有环

    思路

     

    28、map底层,红黑树,优点,应用场景,和B+树的区别

    8.6 

    1、项目介绍

    2、static。

    3、内联函数可以递归吗

    4、TCP标志位有哪些,紧急指针可以携带数据吗

    8.6 

    1、项目介绍

    2、socket耗尽了怎么办

    使用端口快速回收

    3、端口快速回收怎么做

    net.ipv4.tcp_tw_recycle = 1

    4、select和epoll

    5、epoll触发模式,ET如果buf是1M,但是缓冲区有10M怎么处理

    6、read被信号中断怎么处理

    linux下read被信号中断后,中断处理返回后,read可能的操作有两种情况:

    1,read停止读取行为,返回读取数,继续下一条指令的执行。

    2,read被重启,即继续执行read操作。

    linux有个变量用来对这两种行为操作的选择。即SA_RESTART参数。

    7、c++多态父类指针指向子类,会调用子类虚函数,从内存模型解释一下

    8、虚指针初始化在哪

    9、进程和线程怎么理解

    10、IPC

    11、多进程共享内存怎么同步

    12、如果把很大内存,拆成一行一行数据库表一样的记录,想对记录互斥,用什么机制

    13、共享内存和文件锁怎么建立映射关系

    14、HTTP和HTTPS区别,加密过程

    15、TCP和UDP怎么理解

    16、TCP面向连接是什么意思,为什么需要三次握手

    17、在map中删除数据,怎么防止迭代器++ --失效

    18、隔离级别

    19、聚簇索引

    8.11 

    1、访问toutiao.com发生什么

    2、localdns查toutiao.com递归查询的过程,发出什么类型请求,查询什么信息,拿到信息以后去哪查

    3、递归查询和迭代查询的区别,客户端可以控制哪种查询类型吗,DNS协议中的控制这个的标志位知道吗

    4、ARP是多播、单播、还是广播?由谁发起,由谁响应

    5、服务端收到fin回ack处于什么状态,发起fin方处于什么状态

    6、客户端怎么验证证书信任,通过什么机制,多级签发商怎么验证,证书链知道吗

    7、HTTP请求分为几个部分,header中0.9到1.0的多了标识一个端口可以识别多个域名是哪个字段

    8、TLS怎么实现一个端口服务多个域名

    9、HTTP2特点,server push过程,知道push promise吗,怎么知道服务端推送的内容是我需要的或者说怎么判断我要请求的内容,服务端是否已经推给我了

    10、CSS选择器怎么匹配到DOM树中的节点并生效,前端了解多少?

    11、网卡收到一个tcp包后,怎么传递到应用层并处理,怎么通知内核处理,内核做哪些处理

    12、这个包怎么进的内存,内核针对解header需求,涉及到一个缓冲的数据结构了解吗

    13、虚拟内存和物理内存映射机制,页表存在哪

    14、MMU、缺页中断机制

    15、项目介绍

    16、怎么看close wait数量、ss命令

    17、epoll和select改进点

    18、dpdk,xdp

    19、虚函数表怎么实现,举例子说明什么应用场景用虚函数

    20、算法

    如何实现一个数组的原地旋转?(不允许显式地新申请变量, 只能使用swap进行)

    (旋转指将12345向左旋转一位后, 变成23451)

    函数原型:

    def rotate(direction, distance, original_array):

    示例调用:

    rotate('L', 3, [1,2,3,4,5,6,7,8,9])

    8.11

    1、简历问题,保研还是考研,本硕成绩怎么样,本科项目经历,研究生项目经历

    2、项目挑战目标,QPS多少,定制内核

    3、radix tree和TLS和字典树介绍一下,如果匹配*.github.com怎么做

    4、科研经历,目前在做什么,最近半年做什么

    5、研究生以来进步最大的地方,代码量有多少,将来想做什么方向的工作

    6、实习做什么

    7、哪个项目收获最大,如果自己做这个项目能做到什么程度

    8、项目中最大的教训,为什么不用C++写,如果用智能指针能解决内存问题吗

    9、手撕代码:

    括号匹配

    8.13

    1、实习经历,遇到什么问题,怎么解决的

    2、项目中的挑战,亮点是什么

    3、服务器大量closewait会怎么样,怎么解决,有什么后果

    4、线程池的线程怎么工作的,线程数量怎么设,CPU密集型为什么N+1,N+2,N+N不行吗?线程上下文切换开销有哪些,数据栈怎么保存?

    5、五种IO模型,以及应用场景,信号驱动IO怎么工作,是一个线程池专门来处理信号吗?这样处理有什么问题?

    6、为什么投网易啊,想做什么样的工作

    7、面试官介绍自己的部门和小组是网易互娱的云网络,主要提供对梦幻西游、阴阳师、荒野行动这种游戏的高性能私有云服务

    8、有啥offer,一定要SP吗,能接受普通offer吗,工作意向

    业务部门:负责网易互娱游戏的私有云建设,对网络和操作系统要求高一些

    8.17

    1、做题,六个图片,程序改错,看程序说结果,上台阶,数据库判断,IO多路复用判断,SQL语句,

    2、TCP、UDP区别

    3、TCP可靠性如何保证

    4、项目介绍

    5、为什么想来做游戏,对游戏开发流程了解吗

    8.17

    1、项目介绍

    2、指针和引用的区别

    3、智能指针

    4、堆和栈,为什么不都用堆或栈呢

    5、构造函数和析构函数可以抛异常吗

    6、虚函数可以内联吗

    7、虚函数机制

    8、TCP断开连接为什么不是三次

    9、服务端收到客户端的fin回ack进入什么状态

    10、TCP慢启动和快启动(没听过有快启动这概念啊????快重传+快恢复??)

    11、做六个小题,洗牌,堆调整,杀怪,看程序写结果,IO复用选择题,数据库连接

    12、项目的模块延时

    13、平时通过什么方式学习

    14、为什么想投游戏,玩什么游戏

    8.17

    1、自我介绍

    2、HTTP2.0新特性

    3、https加密过程

    4、TCP可靠性

    5、socket编程过程

    6、客户端connect成功代表什么

    7、socket怎么做长连接,keepalive有什么作用

    8、可以在一个端口同时绑定TCP和UDP吗

    9、理论一个服务器最多支持多少长连接

    10、数据库缓存用过吗?

    11、协程了解吗

    12、一个进程的生命周期(五种状态)

    13、僵尸进程,怎么处理

    14、软链接和硬链接,如果源文件删掉,这两种会失效吗,会产生什么错误

    15、iNode,一个文件有几个iNode

    16、linux一个目录下最多有多少个文件限制

    17、

    LRU

    怎么实现的,复杂度

     

    18、算法:力扣179

    8.17

    1、sizeof有关题目

    2、算法:力扣151

    3、TCP有哪些定时器

    4、为什么要有timewait

    5、IPC分别介绍一下

    6、HTTPS加密过程

    7、cookie和session区别

    8、epoll讲一下

    8.18

    1、项目介绍

    2、讲一下字典树和epoll

    3、算法:一个数组,至少三个元素,A[0] >= A[1],A[n-1] >= A[n-2] ,找波谷值

    4、算法:计算二叉树最大宽度

    5、什么是事务,ACID怎么实现的

    6、了解哪些排序,快排复杂度,最差什么情况,怎么改进

    7、HTTPS加密

    8、一个C语言到最终可执行程序,有哪些阶段,作用是什么

    8.20 

    1、项目介绍

    2、算法

    链表相加

     

    3、一个端口可以绑定多个进程吗,可以产生多少连接

    4、用过mysql和缓存吗

    5、inner join,left join

    6、epoll和select区别,select扫描是在用户态还是内核态

    7、HTTP状态码400,502,504,301,302,304

    8、你做后端有什么优势?抗压能力?

    9、怎么处理线上问题的

    10、怎么抓包,用什么看?

    11、项目https加解密怎么做的,对称加密还是非对称加密,证书分发

    12、urlencode了解吗,为什么做这个

    13、TLS和SSL有什么关系,改进在哪

    14、有什么offer

    15、timewait和closewait,其他状态机呢

    16、写了多少代码,刷了多少题

    17、项目的缓存怎么做的,有哪几个模块,怎么做的

    8.21

    1、项目和实习

    2、算法

    接雨水

     

    8.21

    1、HTTP报文分为哪几个部分,该怎么解析,怎么区分头部和体部

    2、chunk怎么读

    3、closewait,怎么解决

    4、项目中的难点

    5、

    LRU

    实现

     

    6、智力题

    甲乙两人,A箱子5个球,B箱子7个球,一次只能在其中一个箱子取至少一个球,谁出手后把球取光谁获胜,甲先手有必胜策略吗

    如果谁出手把球屈光谁失败,甲先手有必胜策略吗

    7、多叉树的祖先怎么求

    8、算法

    求数组的逆序对

     

    9、逆序对为什么用归并,不用快排

    8.24 

    1、项目

    2、五层网络及其一些协议

    3、网卡收包过程

    4、中断类型

    5、TCP和UDP区别

    6、拥塞控制详细说一下

    7、select、poll、epoll区别

    8、分页和分段

    9、进程、线程、协程

    10、算法

    最长递增子序列,结果按字典序排列

     

    11、算法:字符串交错 力扣97

    8.25 

    1、算法

    10.0.0.1/20,a

    10.0.0.1/21,b

    10.2.3.4/20,c

    10.5.6.4/24,d

    根据ip查询所在地区

    输入10.0.0.1 输出a

    2、算法

    对用户访问API在连续一小时内不能超过5W次

    补充说明:多用户,多API

    3、项目

    4、PC端微信登录怎么做

    8.30 

    1、c++多态

    2、epoll

    3、epoll的触发模式,为什么要有这两种模式,nginx用的哪种模式

    4、一个服务器最多有多少个连接,还有什么因素影响

    5、http的优缺点,http2了解吗

    6、线程池怎么实现的,都需要哪些元素

    7、字典树怎么实现的,时空复杂度

    8、c++11智能指针,sizeof求shared_ptr等于多少(16)

    9、map和unordered_map使用场景,hash扩容原理

    10、堆和栈上分配内存哪个快(堆需要加锁)

    11、GDB调试

    12、closewait

    13、通常服务器先关还是客户端先关连接(不考虑长连接,一般是看body长度是否可知吧),如果已经关闭连接再发数据包会怎么样

    14、算法:对于字符串abcdASJDN,在最大字符后面加上(max)

    输入abcdabcd

    输出abcd(max)abcd(max)

    15、算法:A->1  B->2 C->3 …….Z->26

    AA->27 AB->28 ZY->701

    8.30 

    1、算法:leetcode5:Leetcode 5.Longest Palindromic Substring N^3变N^2

    2、项目,性能,稳定性,监控怎么优化

    3、怎么用轻量级的方式验证服务是否可用

    4、算法:线程安全的单例模式

    5、了解哪些数据库信息

    6、ACID

    7、传统数据库和OLEP数据库,HIVE实现上有什么区别

    8、如果你设计一个分布式系统,需要考虑哪些因素

    8.30 

    1、项目

    2、TCP头字段

    3、算法

    LRU

     

    4、算法:线程安全的单例模式

    5、算法:力扣33:搜索旋转排序数组

    6、怎么衡量你的工作做的怎么样,有一些指标吗

    7、项目中速度效率怎么优化的呢

    9.1

    1、项目深挖

    2、https加密过程

    3、公钥是在什么时候拿到的

    4、五层协议介绍一下

    5、UDP需要做什么保证可靠性

    6、TCP三次握手

    7、HTTP协议是什么,1.0和2.0区别,多路复用具体怎么实现的

    8、算法

    二叉树的中序遍历

     

    9、算法:快排

    10、算法:对于每个元素找到身后大于它的元素,找不到返回-1

    输入7 3 8 6 5 8

    输出 8 8 -1 8 8 -1

    11、vector扩容机制

    12、static 和 const可以同时修饰成员函数吗

    13、c++分配内存的方法

    14、c++面向对象的设计特性

    15、

    LRU

    是什么,怎么实现

     

    16、线程池怎么实现的

    17、项目,radix tree和字典树,TLS握手协议,closewait,数据库

    18、UDP的好处

    面向无连接直接传送 不需要TCP三次握手 没有校验包的 没有确认请求 ,传输时开销小。缺点:不可靠。

    19、了解现在一些最新的技术吗

    20、设计模式

    9.1 

    1、项目深挖

    2、linux怎么解决惊群,如果是你怎么解决

    3、IO怎么优化,从TCP/IP协议栈的角度

    4、了解高性能转发技术吗,如果是你的项目怎么进行优化满足上线

    5、对TCP/IP协议栈有过了解吗

    6、了解dpdk,nginx吗,翻过墙吗

    展开全文
  • //遍历整个链表并返回最后一个元素,下同 STATUS* GetLastNodeOpen(); void RemoveClose(STATUS* Node); //移除链表指定结点,下同 void RemoveOpen(STATUS* Node); void AI() { int num = 0...
  • HashMap原理jdk7和jdk8的区别

    千次阅读 2019-01-18 10:06:34
    加在头部比较,因为不需要一个个遍历到最后。jdk1.7的createEntry,看看它是怎么把数据放到链表的头部的。 3、jdk1.7默认初始化大小16,加载因子0.75。如果传入了size,会变为大于等于当前值的2的n次方的最小的数...

    一、hashMap的jdk1.7和jdk1.8区别

    1、实现方式:

    jdk7中使用数组+链表来实现,jdk8使用的数组+链表+红黑树

    2、新节点插入到链表是的插入顺序不同

    jdk7插入在头部,jdk8插入在尾部
    jdk7中,如何在头部插入?看addEntry的createEntry方法:

        /**
         * Like addEntry except that this version is used when creating entries
         * as part of Map construction or "pseudo-construction" (cloning,
         * deserialization).  This version needn't worry about resizing the table.
         *
         * Subclass overrides this to alter the behavior of HashMap(Map),
         * clone, and readObject.
         */
        void createEntry(int hash, K key, V value, int bucketIndex) {
            Entry<K,V> e = table[bucketIndex];
            table[bucketIndex] = new Entry<>(hash, key, value, e);
            size++;
        }
    

    其实很简单的道理,就是创建一个new Entry,这个newEntry的next是e(参照new Entry<>(hash,key,value,e)的实现),这个e就是之前的头结点,然后把当前table的位置放上新建的Entry,也就是插入在链表的头部了。为什么jdk7要插入在头部呢?因为插入头部效率高,不需要遍历整个链表。
    jdk8中,代码放在尾部,代码实现是putVal的一段代码:

                        if ((e = p.next) == null) {
                            p.next = newNode(hash, key, value, null);
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                                treeifyBin(tab, hash);
                            break;
                        }
                        if 
    

    可以很容易看出是放在尾部。
    jdk8中为什么新来的元素是放在节点的后面?我们知道jdk8链表大于8的时候就要树化,本身就要算这个链表的长度有多大,链表算大小就要一个个去遍历了,遍历到了才能知道数量,也可以直接把数据放到后面了,这样也是很方便,减少了把数据移动到头数组位置这一步,效率也提高了。而且,jdk7中出现的那个HashMap死循环bug不会有了,因为这里是只是平移,没有调换顺序。

    3、jdk8的hash算法有所简化

    jdk7默认初始化大小16,加载因子0.75。如果传入了size,会变为大于等于当前值的2的n次方的最小的数。

            // Find a power of 2 >= toSize
            int capacity = roundUpToPowerOf2(toSize);
    

    为什么是2次方数?因为indexFor方法的时候,h&(length-1),length是2的次方,那么length-1总是00011111等后面都是1的数,h&它之后,其实就相当于取余,与的效率比取余高,所以用了这种方式达到高效率。
    下面是jdk7的indexfor的实现:

        /**
         * Returns index for hash code h.
         */
        static int indexFor(int h, int length) {
            // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
            return h & (length-1);
        }
    
    

    另外在hash函数里面方法里面,数会经过右移,为什么要右移?因为取余操作都是操作低位,hash碰撞的概率会提高,为了减少hash碰撞,右移就可以将高位也参与运算,减少了hash碰撞。
    哈希函数如下:

        /**
         * Retrieve object hash code and applies a supplemental hash function to the
         * result hash, which defends against poor quality hash functions.  This is
         * critical because HashMap uses power-of-two length hash tables, that
         * otherwise encounter collisions for hashCodes that do not differ
         * in lower bits. Note: Null keys always map to hash 0, thus index 0.
         */
        final int hash(Object k) {
            int h = hashSeed;
            if (0 != h && k instanceof String) {
                return sun.misc.Hashing.stringHash32((String) k);
            }
    
            h ^= k.hashCode();
    
            // This function ensures that hashCodes that differ only by
            // constant multiples at each bit position have a bounded
            // number of collisions (approximately 8 at default load factor).
            h ^= (h >>> 20) ^ (h >>> 12);
            return h ^ (h >>> 7) ^ (h >>> 4);
        }
    
    

    所以总体来说jdk7的hash算法复杂
    jdk8的右移比较简单,没有jdk7那么复杂。
    jdk8的哈希函数如下:

        /* ---------------- Static utilities -------------- */
    
        /**
         * Computes key.hashCode() and spreads (XORs) higher bits of hash
         * to lower.  Because the table uses power-of-two masking, sets of
         * hashes that vary only in bits above the current mask will
         * always collide. (Among known examples are sets of Float keys
         * holding consecutive whole numbers in small tables.)  So we
         * apply a transform that spreads the impact of higher bits
         * downward. There is a tradeoff between speed, utility, and
         * quality of bit-spreading. Because many common sets of hashes
         * are already reasonably distributed (so don't benefit from
         * spreading), and because we use trees to handle large sets of
         * collisions in bins, we just XOR some shifted bits in the
         * cheapest possible way to reduce systematic lossage, as well as
         * to incorporate impact of the highest bits that would otherwise
         * never be used in index calculations because of table bounds.
         */
        static final int hash(Object key) {
            int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }
    

    为什么jdk8的hash函数会变简单?jdk8中我们知道用的是链表过度到红黑树,效率会提高,所以jdk8提高查询效率的地方由红黑树去实现,没必要像jdk那样右移那么复杂。

    扩容机制有所优化

    在jdk8中,实际上也是通过取余找到元素所在的数组的位置的,jdk8里面取余的方式在putVal里面:

    i = (n - 1) & hash
    

    上面那段代码就是。
    我们假设,在扩容之前,key取余之后留下了n位。扩容之后,容量变为2倍,所以key取余得到的就有n+1位。在这n+1位里面,如果第1位是0,那么扩容前后这个key的位置还是在相同的位置(因为hash相同,并且余数的第1位是0,和之前n位的时候一样,所以余数还是一样,位置就一样了);如果这n+1位的第一位是1,那么就和之前的不同,那么这个key就应该放在之前的位置再加上之前整个数组的长度的位置,也就是这段代码:

                                hiTail.next = null;
                                newTab[j + oldCap] = hiHead;
    

    这样子就减少了移动所有数据带来的消耗,jdk为了优化,真是“费尽心思”。

    其他区别

    节点表示

    在jdk7中,节点是Entry,在jdk8中节点是Node,其实是一样的。

    关于jdk7HashMap的一些细节

    1、jdk7里面addEntry方法扩容的条件size>threshold,还有一个很容易忽略的,就是null!=table[bucketIndex],这个是什么意思?意思是如果当前放进来的值的那个位置也被占用了,才进行扩容,否则还是放到那个空的位置就行了,反正不存在hash冲突。(但是在jdk8里面取消了这个限制,只要达到了threshold,不管原来的位置空不空,还是要扩容)

    2、jdk7resize方法多线程死循环的bug:http://www.importnew.com/22011.html 在jdk8的这个bug已经解决了。

    关于jdk8HashMap的一些细节

    1、jdk8 默认初始化大小16,加载因子0.75。还有一个默认的树化的大小8。非树化大小为6,也就是红黑树的元素小于6的时候,又会变回一个链表。为什么是8和6?
    参考:
    HashMap在JDK1.8及以后的版本中引入了红黑树结构,若桶中链表元素个数大于等于8时,链表转换成树结构;若桶中链表元素个数小于等于6时,树结构还原成链表。因为红黑树的平均查找长度是log(n),长度为8的时候,平均查找长度为3,如果继续使用链表,平均查找长度为8/2=4,这才有转换为树的必要。链表长度如果是小于等于6,6/2=3,虽然速度也很快的,但是转化为树结构和生成树的时间并不会太短。
    还有选择6和8,中间有个差值7可以有效防止链表和树频繁转换。假设一下,如果设计成链表个数超过8则链表转换成树结构,链表个数小于8则树结构转换成链表,如果一个HashMap不停的插入、删除元素,链表个数在8左右徘徊,就会频繁的发生树转链表、链表转树,效率会很低。
    2、jdk8的putVal方法:i = (n - 1) & hash这个其实也就是取余操作了。

    关于HashMap的一些其他细节

    1、为什么重写对象equals方法的时候,要重写hashcode,跟hashmap有关系吗?
    java object类默认有一个hashcode方法,返回的是对象的地址。
    hashmap是根据hashcode返回value的,如果没有重写hashcode,即使重写了equals方法之后,两个对象equals之后相同,但是hash之后却不同,在使用hashMap的时候通过一个对象作为key去获取另外一个对象为key存进去的value的时候,很有可能返回为空,这就是原因。所以和hashmap有关系,不如说和hashcode有关系。

    2、ConcurrentModificationException为什么会有这个错误?
    首先我们看一段代码:

      public static void main(String[] args) {
            HashMap<Integer,Integer> hashMap = new HashMap<>();
            hashMap.put(1,1);
            hashMap.put(2,2);
            for(Integer key:hashMap.keySet()){
                if(key.equals(1)){
                    hashMap.remove(1);
                }
            }
        }
    

    上面这个会报错
    下面这个不会:

    public static void main(String[] args) {
            HashMap<Integer,Integer> hashMap = new HashMap<>();
            hashMap.put(1,1);
            hashMap.put(2,2);
            for(Integer key:hashMap.keySet()){
                if(key.equals(2)){
                    hashMap.remove(1);
                }
            }
        }
    
    

    为什么呢?我们把上面的代码转换一下,我们把foreach变为下面这个也是一样的原理:

     Iterator<Integer> iterator = hashMap.keySet().iterator();
            while(iterator.hasNext()){
                Integer key = iterator.next();
                if(key.equals(1)){
                    hashMap.remove(1);
                }
            }
    

    看源码expectedModCount的位置,HashIterator.nextNode的位置会出现这个错误,看看源码。

            final Node<K,V> nextNode() {
                Node<K,V>[] t;
                Node<K,V> e = next;
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
                if (e == null)
                    throw new NoSuchElementException();
                if ((next = (current = e).next) == null && (t = table) != null) {
                    do {} while (index < t.length && (next = t[index++]) == null);
                }
                return e;
            }
    

    在上面的例子中,到了一定的时间,expectedModCount是2,但是modCount变成3,就会报错。
    在多线程情况下,一个线程在遍历,一个线程在remove就会出现这种情况。
    其实也不一定在最后面添加的判断就不会,具体看hash实现情况。

    3、设计hashmap需要解决的问题,1、找到hash函数 2、解决冲突

    展开全文
  • 深信服一面面经

    2021-03-31 12:44:30
    (堆排序,没想出来,只说了一个排序,平均最快nlogn) 堆排序是怎么排序的?(承接上面的问题,给我提示,但是我完全没意识到) 二叉排序树为什么要平衡? new和malloc的区别? fock函数在调用时进行了哪些工作? ...

    深信服一面-C++开发工程师 云计算/网络安全方向-校招

    (大概半小时不到)

    数据结构:
    多态是怎么实现的?

    继承和重载有什么关系?

    数组和链表有什么区别?

    数组里找第k个最大的数有什么方法?(堆排序,没想出来,只说了一个排序,平均最快nlogn)
    堆排序是怎么排序的?(承接上面的问题,给我提示,但是我完全没意识到)

    二叉排序树为什么要平衡?

    new和malloc的区别?

    fock函数在调用时进行了哪些工作?

    快速排序是怎么排的,有序和无序的情况哪个速度慢(有序),为什么?(不知道…)那怎么优化呢?(先遍历一遍看看是不是有序?去掉最坏情况…)

    计算机网络:
    TCP和UDP的区别(又问的这个,高频考点)

    手撕代码:
    写一个类,对其实例化的对象做计数(静态数据成员),写出构造和拷贝构造函数以及析构函数,测试一下。

    总结:
    幸好昨天字节面完看了一下网络编程相关,写代码的时候不太记得静态数据成员是怎么初始化的了,还有怎么使用,面试官帮我改了,有点尴尬,这题目不难也没做对。最近直接开始恶补计算机网络,加油。

    展开全文
  • sicily 1024 magic island

    2018-09-16 23:56:39
    直接思路就是深搜,用 T *g[] 这种形式来构造邻接链表,注意是无向图。 从出发点开始搜,标记已访问点,遍历未访问的邻接点,把所有可能都计算一次, 全局变量记录最大距离。 很不幸,不知为何超时。(后来发现...

    发现n年前草稿。。

    最直接思路就是深搜,用 T *g[] 这种形式来构造邻接链表,注意是无向图。

    从出发点开始搜,标记已访问点,遍历未访问的邻接点,把所有可能都计算一次,

    全局变量记录最大距离。

    很不幸,不知为何超时。(后来发现时忘记 把图清空了)

     

    后来想了想,似乎没说图中有无环,有无孤立点。

    应该做访问标记的是 边,而不是点。于是开始胡思乱想怎么才能快速判断 边 是否已访问。

    根据 两端点号 a*b*17%n 进行 hash 似乎可以。

     

    接着又想 深搜会不会太多 分支会超时?

    n点仅有n-1边,十分稀疏啊,应该没问题。

     

    网上搜到几个题解,试试自己设计的数据,发现总是 比自己预期结果少算一条边。

    因为我的数据设计是有环 和 孤立点的, 从结果来看来应该 题目需要的图是无环的。

     

    再后来,看了几遍题目,发现一句超级重要的:

    There are N cities and N-1 roads in Magic-Island. You can go from one city to any other.

    后面那句就是说图是连通的,没有孤立点!

    再加上 n点n-1边, 图就是无环的。

     

    咳咳,所以这图就是一颗树。

    所以 访问标记 可以对边 也可以对点 做;

    图的存储还是 之前的邻接表;

    要深 要广 随你搜。

     

    我的代码自己实现了简单的 vector<T> g[n], 性能应该没有stl 的那么好。

     

    0.12sec 1344 KB

     

    #include <cstdio>
    #include <cstring>
    int maxDis;
    char isVisited[10001];
    struct node{
    	int dis, dst;
    	void show() const{
    		printf("[%d %d], ", dst, dis );
    	};
    };
    
    template< typename T > 
    struct adjlst{
    	enum {  initCapacity=2, extendTimes=2,   };   /* initCapacity 初始邻接点容量, extendTimes扩容倍数。 */
    	T **a;
    	int num, *count, *max;  /* num 总共点数, count邻接点数目, max 最大容量。*/
    	
    	adjlst( int n ){  
    		num = n;
    		a = new T*[n];	
    		count = new int[n];
    		max  =  new int[n];
    		for( int i=0; i<n; i++){    //初始化邻接表只有 initCapacity 容量。  
    			a[i] = new T[initCapacity];
    			max[i] = initCapacity;
    			count[i] = 0;
    		}
    	}
    	~adjlst(){
    		for( int i=0; i<num; i++ )
    			delete [] a[i];
    		delete [] a ;
    		delete [] count ;
    		delete [] max ;
    	}
    	void addNode( int row, const T& x ){
    		int i, pos;
    		if( count[row] >= max[row] ){   // 满了,需要扩容 extendTimes 倍 
    			max[row] *= extendTimes;
    			T* temp = new T[ max[row] ];
    			//for( i=0; i<count[row]; i++ )   temp[i] = a[row][i];
    			memcpy( temp, a[row], sizeof(T)* count[row] );
    			delete [] a[row];
    			a[row] = temp;
    		}
    		pos = count[row]++;   
    		a[row][pos] = x;
    		/*
    		x.show();
    		printf("\n");*/
    	}
    	void show( int st, int ed ) const{
    		int i,j, n;
    		for( i=st; i<ed; i++ ){
    			printf("--- %d %d: ", max[i], i );
    			n = count[i];
    			for( j=0; j<n; j++ )
    				a[i][j].show();
    			printf("\n");
    		}
    	} 
    	void clear(){
    		memset( count, 0, sizeof(count[0])*num );
    	}
    };
    
    void dfs( const adjlst<node>&g, int st, int curDis ){
    	int i,j,n, dis, dst;
    	n = g.count[st];
    	if( curDis > maxDis )  maxDis = curDis;	
    	for( i=0; i<n; i++ ){
    		dst = g.a[st][i].dst;
    		if( isVisited[  dst ] == 0 ){
    			isVisited[  dst ]  = 1;
    			
    			dis = g.a[st][i].dis;
    			dfs( g, dst, curDis+dis );
    		//	printf("====%d\n", maxDis );
    			
    			isVisited[  dst ]  = 0;
    		}
    	}
    }
    
    int main(){
    	int num_city, capital, i, src,dst;
    	node temp;
    	adjlst<node>  graph( 10001 );
    	while(scanf( "%d %d", &num_city, &capital ) != EOF  ){
    		for( i=1; i<num_city; i++ ){   // 插入 n-1 条边 
    			scanf("%d %d %d", &src, &dst, &temp.dis );
    			temp.dst = dst;
    			graph.addNode( src, temp );
    			temp.dst = src;
    			graph.addNode( dst, temp );
    		}
    		//graph.show(0, num_city );
    		
    		maxDis = 0;
    		memset( isVisited, 0, sizeof(isVisited) );
    		isVisited[ capital ] = 1;
    		dfs( graph, capital, 0 );
    		printf ( "%d\n", maxDis );
    		graph.clear();
    	}
    	return 0;
    }

     

     

     

     

     

    AC之后又有新的问题了。

    如何生成随机数据?

    要保证数据生成的图是无环,连通的该怎么搞?

     

     

     

     

     

    展开全文
  • 整理——百度面试

    2016-08-17 10:20:28
    五种布局中哪个运行最快,为什么? 3.1T的数据,均是数字,每行一个数,怎么从中找出最大的10个数?(遍历一次) 定义一个数组a[10],开始读数据,将前10个数放入数组并从大到小排序,继续读数据,每读一个数M,...
  • 强烈推荐大家使用谷歌商店安装, 这样如果有更新可以自动安装,毕竟咱们的插件更新还是蛮的。 :exclamation:怎么刷 LeetCode? 我是如何刷 LeetCode 的 算法小白如何高效、快速刷 leetcode? 刷题效率低?或许...
  • 大话数据结构

    2018-12-14 16:02:18
    双向链表既然是比单链表多了如可以反向遍历查找等的数据结构,那么也就需要付出一些小的代价。 3.15总结回顾 84 3.16结尾语 85 如果你觉得上学读书是受罪,假设你可以活到80岁,其实你最多也就吃了20年苦。用人生...
  • 易学C++,C++入门

    2009-12-06 14:30:11
     9.6.1 链表的创建和遍历   9.6.2 链表的查询  9.6.3 插入结点   9.6.4 删除结点   9.6.5 清除链表   9.7 方法指导   9.8 习题  第二篇 实战程序设计  第10章 高效阅读程序代码   10.1 ...
  • 但是怎么解决快速查找的问题,尤其是在有大量数据存在时?如果查找的时间复杂度还不如链表,那就没有意义了。 我们知道在一个排好序的数组中进行二分查找的时间复杂度是 O(logn), 是非常高效的&#...

空空如也

空空如也

1 2
收藏数 35
精华内容 14
关键字:

链表怎么遍历最快