1. 两个有序链表合并, 时间复杂度是多少? 什么情况下不 work ?
当链表有环或链表有公共节点时不 work
2. N 个数, 任意选出两个数求其和, 结果的集合为 S, S 中所有元素之和是多少 ?
朴素解法: 枚举, o(n^2) 的复杂度
3. A,B 两个有序数组, 从 A, B 各选出一个元素, 使其和为 target, 给出时间复杂度.
朴素求法: 枚举 A 中的元素, 到 B 中找 target - A[i], 时间复杂度为 o(n*logn)
编程之美单个有序链表求和为 target 的两个元素的位置的变形题.
设置两个游标 i, j 分别在 A[0], B[n-1] 处. A[i] + B[j] < target -> i ++. else j --;
如果没有找到, 再设 i,j 分别在 A[m-1], B[0] 处, 再遍历一遍.
时间复杂度为 o(m+n)
4. 在一个 o(n*n) 的方块中, 有一条环形路径, 该路径上的点标号为 1, 其他坐标上的点标号为 0, 求出环形路径围起来的面积.
Leetcode 原题, 使用 BFS, DFS 都可以.
5. 进程之间的数据共享
a. 共享内存
b. 管道
c. 消息队列
d. 信号量
e. 本地域 socket
6. 百度地图中存在需要标注的很多点，并且这些点都需要带描述，现将描述假设为矩形，并且可以位于点的左边或右边，但点不能移动，如果两个点间的描述发生覆盖，则需要将其中的一个点进行删除
1.在一个区域内，请设计算法将有效的点进行输出（尽可能多的点）？
2.如果区域足够大，点足够多，算法会出现性能的瓶颈，请设计详细的算法来说明并解决问题？
1. 默认描述在点的左边, 若左边不可放置则放到右边, 若右边也不可放置, 把该点删除
2. 可以对点附上权值, 优先摆放权值较高的点
7. 字符串 "alibaba" 共有几种排列方式
7!/(3!*2!) = 840
8.
|
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 |
#include <iostream>#include <stdio.h>using
namespace std;class
Base {public: int
Bar(char
x) { return
(int)x; } virtual
int Bar(int
x) { return
(2*x); }};class
Derived : public
Base {public: int
Bar(char
x) { return
(int)(-x); } int
Bar(int
x) { return
(x/2); }};int
main() { Derived Obj; Base *pObj = &Obj; printf("%d\n", pObj->Bar((char)(100))); printf("%d\n", pObj->Bar(100));} |
输入 100, 50. As expected.
9. 下列那个不是线性表? (c)
A. 一个线程可以改变另一个线程的程序计数器（program counter）
B. 一个线程既不能读也不能写另一个线程的栈（stack）
C. 一个线程可以读写另一个线程的寄存器（register）
D. 以上都不对
11. 关于双链表的搜索给定元素操作的说法正确的是
A. 从两个方向搜索双链表，比从一个方向搜索双链表的速度慢
B. 从两个方向搜索双链表，比从一个方向搜索双链表的方差要小
C. 从两个方向搜索双链表，比从一个方向搜索双链表速度要快
D. 以上说法都不正确
个人倾向于选择 D, 单方向和双方向是等价的
12. 对n个数字进行排序，期中两两不同的数字的个数为k，n远远大于k，而n的取值区间长度超过了内存的大小，时间复杂度最小可以是
A. 720/13分钟 B. 720/11分钟 C. 60分钟 D. 以上都不正确
原文：http://www.cnblogs.com/zhouzhuo/p/3630360.html