Skip to content

Latest commit

 

History

History
198 lines (143 loc) · 16.3 KB

牛客商的腾讯内推实习二面（前端岗）.md

File metadata and controls

198 lines (143 loc) · 16.3 KB
Raw

牛客上的腾讯内推实习二面（前端岗）

  1. 判断两个链表是否相交并找出交点

    • 两个链表均不含有环
      • 直接法，遍历两个链表，判断第一个链表的每个结点是否在第二个链表中
        • 时间复杂度为O(len1*len2)，耗时很大 len是长度

      • hash计数法

        • 如果两个链表相交，则两个链表就会有共同的结点；而结点地址又是结点唯一标识。因而判断两个链表中是否存在地址一致的节点，就可以知道是否相交了。
        • 可以对第一 个链表的节点地址进行hash排序，建立hash表，然后针对第二个链表的每个节点的地址查询hash表，如果它在hash表中出现，则说明两个链表有共 同的结点。这个方法的时间复杂度为：O(max(len1+len2)；但同时还得增加O(len1)的存储空间存储哈希表。这样减少了时间复杂度，增加 了存储空间

      • 先遍历第一个链表到他的尾部，然后将尾部的next指针指向第二个链表(尾部指针的next本来指向的是null)。这样两个链表就合成了一个链表，判断原来的两个链表是否相交也就转变成了判断新的链表是否有环的问题了：即判断单链表是否有环？

        • 如果新链表是有环的，那么原来第二个链表的头部一定在环上。因此我们就可以从第二个链表的头部进行遍历的，从而减少了时间复杂度(减少的时间复杂度是第一个链表的长度，这种方法可以判断两个链表是否相交，但不太容易找出他们的交点。image

      • 仔细研究两个链表，如果他们相交的话，那么他们最后的一个节点一定是相同的，否则是不相交的。因此判断两个链表是否相交就很简单了，分别遍历到两个链表的尾部，然后判断他们是否相同，如果相同，则相交；否则不相交。示意图如下：image

        • 判断出两个链表相交后就是判断他们的交点了。假设第一个链表长度为len1，第二个问len2，然后找出长度较长的，让长度较长的链表指针向后移动|len1 - len2| (len1-len2的绝对值)，然后在开始遍历两个链表，判断节点是否相同即可。

    • 两个链表都有环

      • 找到第一个链表的环点，然后将环断开（当然不要忘记了保存它的下一个节点），然后再来遍历第二个链表，如果发现第二个链表从有环变成了无环，那么他们就是相交的嘛，否则就是不相交的了。
        • 如果相交点在环外，那么切掉环点，问题回到变成2个无环的链表求交点
        • 如果相交点在环内，那么遍历它

    • 当一个链表中有环，一个链表中没有环时，两个链表必不相交。

  2. 说说http，知道哪些响应码

    • HTTP，超文本传输协议

      • HTTP是无状态的，所以引入了cookie来保持状态

      • HTTP消息的结构

        • 通用头部 header
          • request Url：请求的web服务器地址
          • request method：请求方法
          • status code：请求返回的状态码
          • remote address：请求的远程服务器地址（会转为IP？）？？？？
        • 请求/响应头部 http header
          • 常用的请求头部
            • Accept: 接收类型，表示浏览器支持的MIME类型（对标服务端返回的Content-Type）
            • Accept-Encoding：浏览器支持的压缩类型,如gzip等,超出类型不能接收
            • Content-Type：客户端发送出去实体内容的类型
            • Cache-Control: 指定请求和响应遵循的缓存机制，如no-cache
            • If-Modified-Since：对应服务端的Last-Modified，用来匹配看文件是否变动，只能精确到1s之内，http1.0中
            • Expires：缓存控制，在这个时间内不会请求，直接使用缓存，http1.0，而且是服务端时间
            • Max-age：代表资源在本地缓存多少秒，有效时间内不会请求，而是使用缓存，http1.1中
            • If-None-Match：对应服务端的ETag，用来匹配文件内容是否改变（非常精确），http1.1中
            • Cookie: 有cookie并且同域访问时会自动带上
            • Connection: 当浏览器与服务器通信时对于长连接如何进行处理,如keep-alive
            • Host：请求的服务器URL
            • Origin：最初的请求是从哪里发起的（只会精确到端口）,Origin比Referer更尊重隐私
            • Referer：该页面的来源URL(适用于所有类型的请求，会精确到详细页面地址，csrf拦截常用到这个字段)
            • User-Agent：用户客户端的一些必要信息，如UA头部等
          • 常用的响应头部
            • Access-Control-Allow-Headers: 服务器端允许的请求Headers
            • Access-Control-Allow-Methods: 服务器端允许的请求方法
            • Access-Control-Allow-Origin: 服务器端允许的请求Origin头部（譬如为*）（跨域问题经常碰到）
            • Content-Type：服务端返回的实体内容的类型
            • Date：数据从服务器发送的时间
            • Cache-Control：告诉浏览器或其他客户，什么环境可以安全的缓存文档
            • Last-Modified：请求资源的最后修改时间
            • Expires：应该在什么时候认为文档已经过期,从而不再缓存它
            • Max-age：客户端的本地资源应该缓存多少秒，开启了Cache-Control后有效
            • ETag：请求变量的实体标签的当前值
            • Set-Cookie：设置和页面关联的cookie，服务器通过这个头部把cookie传给客户端
            • Keep-Alive：如果客户端有keep-alive，服务端也会有响应（如timeout=38）
            • Server：服务器的一些相关信息
          • 一般来说，请求头部和响应头部是匹配分析的。
        • 请求响应体 body

          • http请求时，除了头部，还有消息实体，一般来说

            请求实体中会将一些需要的参数都放入进入（用于post请求）。

            譬如实体中可以放参数的序列化形式（a=1&b=2这种），或者直接放表单对象（Form Data对象，上传时可以夹杂参数以及文件），等等

            而一般响应实体中，就是放服务端需要传给客户端的内容

            一般现在的接口请求时，实体中就是对于的信息的json格式，而像页面请求这种，里面就是直接放了一个html字符串，然后浏览器自己解析并渲染。

      • get和Post的区别

        • GET提交的数据会放在URL之后，以?分割URL和传输数据，参数之间以&相连，如EditPosts.aspx?name=test1&id=123456. POST方法是把提交的数据放在HTTP包的Body中.
        • GET提交的数据大小有限制（因为浏览器对URL的长度有限制），而POST方法提交的数据没有限制.
        • GET方式需要使用Request.QueryString来取得变量的值，而POST方式通过Request.Form来获取变量的值。
        • GET方式提交数据，会带来安全问题，比如一个登录页面，通过GET方式提交数据时，用户名和密码将出现在URL上，如果页面可以被缓存或者其他人可以访问这台机器，就可以从历史记录获得该用户的账号和密码
    • 状态码

      • 200——表明该请求被成功地完成，所请求的资源发送回客户端 304——自从上次请求后，请求的网页未修改过，请客户端使用本地缓存 400——客户端请求有错（譬如可以是安全模块拦截） 401——请求未经授权 403——禁止访问（譬如可以是未登录时禁止） 404——资源未找到 500——服务器内部错误 503——服务不可用

    • cookie

  3. 说说tcp

    • TPC/IP协议是传输层协议，主要解决数据如何在网络中传输，而HTTP是应用层协议，主要解决如何包装数据。

    • 术语TCP/IP代表传输控制协议/网际协议，指的是一系列协议。“IP”代表网际协议，TCP和UDP使用该协议从一个网络传送数据包到另一个网络。把IP想像成一种高速公路，它允许其它协议在上面行驶并找到到其它电脑的出口。TCP和UDP是高速公路上的“卡车”，它们携带的货物就是像HTTP，文件传输协议FTP这样的协议等。

    • TCP提供有保证的数据传输，而UDP不提供

  4. 对https了解吗

    • HTTP协议传输的数据都是未加密的，也就是明文的

    • HTTPS是以安全为目标的HTTP通道，简单讲是HTTP的安全版，即HTTP下加入SSL层，HTTPS的安全基础是SSL，因此加密的详细内容就需要SSL。

      • SSL，一种非对称的加密算法。TLS与SSL在传输层对网络连接进行加密

    • http和https使用的是完全不同的连接方式，用的端口也不一样，前者是80，后者是443

    • HTTPS比HTTP更加安全，对搜索引擎更友好，利于SEO（搜索引擎优化）

      • （1）为保护用户隐私安全,谷歌优先索引HTTPS网页、
      • （2）百度开放收录https站点，https全网化势不可挡

  5. 什么时候开始学前端，如何学习的

  6. 如何自主学习，解决问题，从项目中举一个例子，说明自己的学习能力

  7. 排序算法知道哪些，时间复杂度

    • 插入排序（Insertion Sort），平均时间复杂度n^2，稳定排序
    • 快速排序（quick sort）平均时间复杂度是nlogn，不稳定排序
    • 二分插入：时间复杂度 n^2，不稳定排序
      • 二分法插入排序是在插入第i个元素时，对前面的0～i-1元素进行折半，先跟他们中间的那个元素比，如果小，则对前半再进行折半，否则对后半进行折半，直到left>right，然后再把第i个元素前1位与目标位置之间的所有元素后移，再把第i个元素放在目标位置上。
    • 希尔排序，非稳定排序，最差nlogn，最优是n，增量以/3递减是最快的，时间复杂度为O(n^1.5)，希尔排序对中等大小规模数据表现良好，对规模非常大的数据排序不是最优选择：https://www.cnblogs.com/leoin2012/p/3910889.html
    • 希尔排序原理：一个书架放着一排书，现在从第一本书起每数X本书，就在那本书上贴红色贴纸，贴完红色贴纸后，再次从第二本书起每数X本书就贴上蓝色贴纸（跟之前颜色不同即可），重复贴纸过程，直到所有书都贴满贴纸。接着对有相同颜色贴纸的书做插入排序。然后撕掉所有贴纸后重新对书进行贴纸，这次则每数Y本书就贴纸（Y>X）,所有书贴满后再进行插入排序。重复贴纸排序、贴纸排序这个过程，直到最后每数1本书就贴纸（也就是每本书都贴同样颜色贴纸），再插入排序为止。
    • 选择排序，就遍历然后找最大的放在数组头， n^2，不稳定
    • 冒泡排序，时间复杂度 n^2，稳定
      • 双向冒泡排序，时间复杂度不变，
        • 比较相邻两个元素的大小。如果前一个元素比后一个元素大，则两元素位置交换
        • 对数组中所有元素的组合进行第1步的比较
        • 奇数趟时从左向右进行比较和交换
        • 偶数趟时从右向左进行比较和交换
        • 当从左端开始遍历的指针与从右端开始遍历的指针相遇时，排序结束
    • 堆排序 复杂度是：nlogn
      • 将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了
      • 构造堆
        • 自底向上构造：首先无脑构造完全二叉树，然后从最后的父母节点开始，到根位置，检查这些节点是否满足父母优势，如果不满足，就把该节点与子女中较大的节点进行交换
        • 自顶向下构造：不断的把一个新的节点插入到当前堆的最后一个叶节点后面，然后比较父母优势，直到满足父母优势
      • 每次删除/拿出 最大键，然后对剩下的堆继续删除
      • 堆的删除
        • 根的键和最后一个键K做交换
        • 按照自底向上构造进行堆化
    • 归并排序 merge sort 平均时间复杂度是nlogn 最好nlogn 最差n 稳定排序
    • 不断拆分，直到不能拆分，比较，然后合并为有序数组
    • https://www.cnblogs.com/chengxiao/p/6194356.html 这里有详细介绍 合并的步骤
    • 桶排序 (Bucket sort) 平均时间复杂度是n 稳定排序
    • 输入是由一个随机过程产生的[0, 1)区间上均匀分布的实数。将区间[0, 1)划分为n个大小相等的子区间（桶），每桶大小1/n：[0, 1/n)， [1/n, 2/n)， [2/n, 3/n)，…，[k/n, (k+1)/n )，…将n个输入元素分配到这些桶中，对桶中元素进行排序，然后依次连接桶输入0 ≤A[1..n] <1辅助数组B[0..n-1]是一指针数组，指向桶（链表）。
      • 这里写图片描述
    • https://www.cnblogs.com/ECJTUACM-873284962/p/6935506.html 又有这种说法？？？
    • 计数排序(Counting sort)，复杂度为Ο(n+k)（其中k是整数的范围），而且当O(k)>O(nlog(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(nlog(n)), 如归并排序，堆排序）
    • 基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数（此处并非比较各元素的大小，而是通过对元素值的计数和计数值的累加来确定）。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。例如，如果输入序列中只有17个元素的值小于x的值，则x可以直接存放在输出序列的第18个位置上
    • https://blog.csdn.net/gaoruxue918/article/details/61467416 具体实现
      • 首先遍历一次数组，找到最大和最小元素
      • 统计数组中每个值为i的元素出现的次数，存入数组C的第i项
      • 对所有的计数累加
      • 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个 元素就将C(i)减去1
    • 基数排序
    • img

  8. 前端主要做PC端还是移动端，我回答PC端，他说那你知道现在移动端流量更大嘛。。。一首凉凉送给自己。

  9. 了解hashmap吗？对其它后台语言有了解吗？

    1. hashmap是和C++里的Map一样用来存储Key-Value键值对的集合

  10. 平时使用什么来控制版本？为什么使用svn？而不是git？

  11. web worker

1. 当在 HTML 页面中执行脚本时，页面的状态是不可响应的，直到脚本已完成。

   web worker 是运行在后台的 JavaScript，独立于其他脚本，不会影响页面的性能。您可以继续做任何愿意做的事情：点击、选取内容等等，而此时 web worker 在后台运行。