Joyce' Blog
0%

bytedancer-interview-note

发表于 更新于

search-in-rotated-sorted-array

题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

题解

重点在于确定下一次搜索范围在右边还是左边。

如果nums[mid]>nums[left]，说明左边是有序的；这个时候如果nums[left]<target<nums[mid]，那么在左边继续搜索，否则在右边搜索。

如果nums[mid]<nums[left]，说明右边是有序的；这个时候如果nums[mid]<target<nums[right]，那么在右边继续搜索，否则在左边搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int search(vector<int>& nums, int target) {
        int size=nums.size();
        int left=0,right=size-1;
        int mid;
        while(left<=right)
        {
            mid=(left+right)/2;
            if(nums[mid]==target)
                return mid;
            if(nums[mid]<nums[left])
            {//右边有序
                if(nums[mid]<target&&target<=nums[right])
                {
                    left=mid+1;
                }
                else
                {
                    right=mid-1;
                }
            }
            else
            {//左边有序
                if(nums[left]<=target&&target<nums[mid])
                {
                    right=mid-1;
                }
                else
                {
                    left=mid+1;
                }
            }
        }
        return -1;
    }

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗：6.6 MB, 在所有 C++ 提交中击败了100.00%的用户

search-in-rotated-sorted-array-ii

题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。

  • nums 可能包含重复元素。
  • 这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？
题解

相比于上面多出了nums[mid]==nums[left]这种情况，此时不知道哪半边是有序的，所以只能一位位地移动，left++。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
bool search(vector<int>& nums, int target) {
        int size=nums.size();
        int left=0,right=size-1;
        int mid;
        while(left<=right)
        {
            mid=(left+right)/2;
            if(nums[mid]==target)
                return true;
            if(nums[mid]<nums[left])
            {//右边有序
                if(nums[mid]<target&&target<=nums[right])
                {
                    left=mid+1;
                }
                else
                {
                    right=mid-1;
                }
            }
            else if(nums[mid]>nums[left])
            {//左边有序
                if(nums[left]<=target&&target<nums[mid])
                {
                    right=mid-1;
                }
                else
                {
                    left=mid+1;
                }
            }
            else
            {
                left++;
            }
        }
        return false;
    }

执行用时：4 ms, 在所有 C++ 提交中击败了97.26%的用户

内存消耗：6.7 MB, 在所有 C++ 提交中击败了100.00%的用户

虚拟内存 共享内存 常驻内存

虚拟内存

虚拟内存的设计是为了让操作系统对进程地址空间进行管理，这是一个逻辑上的概念。页表将虚拟内存空间映射到物理内存空间，内核为每个进程维护一份相互独立的页表，“页”是映射的基本单位。在程序运行过程中虚拟内存空间中==需要被访问==的部分会被映射到物理内存空间中。

驻留内存

驻留内存是指==被映射==到进程虚拟内存空间的==物理==内存，进程的驻留内存就是他实际上占用的内存。

共享内存

进程运行过程中，会用到操作系统的动态库，例如 libc.so、libld.so等，这些库对于每个进程都是公用的，在内存中只加载一份，这部分成为共享内存，是同一块物理地址，但不是同一块虚拟地址。

DNS

Domain Name System，根据域名查出IP地址。

本机需要先知道DNS服务器的IP地址。DNS服务器的IP地址，可能是动态的（DHCP机制，每次上网时由网关分配），也有可能是静态的（事先指定）。

分级查询：主机名.次级域名.顶级域名.根域名，两种查询方式：递归和迭代。

每一级域名都有自己的NS记录，NS记录指向该级域名的域名服务器。这些服务器知道下一级域名的各种记录。从根域名开始，依次查询每一级域名的NS记录，直到查到最终的IP地址，过程大致如下。（http://www.ruanyifeng.com/blog/2016/06/dns.html）

  1. 从”根域名服务器”查到”顶级域名服务器”的NS记录和A记录（IP地址）
  2. 从”顶级域名服务器”查到”次级域名服务器”的NS记录和A记录（IP地址）
  3. 从”次级域名服务器”查出”主机名”的IP地址

为什么数据库索引不使用hashmap而是B+树

（hash的查询效率高于B+树）

  • hash表只能匹配是否相等（”=”,”IN”和”<=>”），不能实现范围查找。select * from xxx where id>4
  • 当数据量很大时，hash冲突的概率会很大

emm网上说，当需要按照索引排序时，hash值无法辅助排序（B+树可以？？）select * from xx order by score desc; score为建立索引的字段；hash运算前后不会保持原有的大小关系，所以数据库无法利用索引的数据来避免任何排序运算。

另外，组合索引可以支持部分索引查询，如(a,b,c)的组合索引，查询中只用到了a和b也可以查询的，如果使用hash表，组合索引会将几个字段合并hash，没办法支持部分索引。

socket通信

不同计算机上的进程之间的通信，调用操作系统提供的socket接口。

socket套接字。socket()、bind()、listen()、connect()、accept()、read()、write()、close()，三次握手、四次挥手。

网络协议

OSI：应用层、表示层、会话层、传输层、网络层、数据链路层、物理层

应用层：文件传输，电子邮件，文件服务，虚拟终端；HTTP，FTP，SMTP，DNS

传输层：提供端对端的接口；TCP，UDP

网络层：为数据包选择路由；IP，ICMP，RIP，OSPF，BGP，IGMP

数据链路层：传输有地址的帧以及错误检测功能；ARP

另外，能记起来的、被问到的全部问题：

计网

  • dns
  • 有哪些网络层协议
  • 有哪些传输层协议
  • tcp udp有啥区别和适用范围
  • tcp如何实现拥塞控制
  • 滑动窗口

操作系统

  • 进程间通信方式，细问了共享内存和两种管道，哦，还有socket，从而牵扯出了 七/五层模型
  • 共享内存 虚拟内存 常驻内存

数据库

  • 索引，用了b+树，为啥索引不用hashmap，hashmap怎么实现的
  • redis

c++

  • 一个类占空的空间大小计算(32bit/64bit)
  • static
  • virtual
  • const，问的很细
难顶哦，我怀疑他们是在以秋招的标准来要求一个想日常实习的孩子

我太菜了。