剑指Offer——腾讯+360+搜狗校招笔试题+知识点总结
9.11晚7:00,腾讯笔试。选择题与编程、设计题单独计时。
栈是不是顺序存储的线性结构啊?
首先弄明白两个概念:存储结构和逻辑结构。
数据的逻辑结构包括线性结构、树、图、集合这四种,在线性结构里面又有线性表、栈、队列等等。
而数据的存储结构只有两种:顺序存储结构和链式存储结构,这两种存储结构,前面一个是利用数据元素在存储器中的相对位置表示其逻辑结构,另外一个是用指针来表示其逻辑关系。
结论:线性结构的数据在存储结构方面,既可能是顺序存储,也可能是链式存储。线性表是线性结构,也是顺序存储结构。
腾讯编程题
某幢大楼有100层。你手里有两颗一模一样的玻璃珠。当你拿着玻璃珠在某一层往下扔的时候,一定会有两个结果,玻璃珠碎了或者没碎。这幢大楼有个临界楼层。低于它的楼层,往下扔玻璃珠,玻璃珠不会碎,等于或高于它的楼层,扔下玻璃珠,玻璃珠一定会碎。玻璃珠碎了就不能再扔。现在让你设计一种方式,使得在该方式下,最坏的情况扔的次数比其他任何方式最坏的次数都少。也就是设计一种最有效的方式。在网上看到有个解释:
http://blog.csdn.net/maggiedorami/article/details/7964766
360编程题
最强大脑
时间限制:C/C++语言 1000MS;其他语言 3000MS
内存限制:C/C++语言 65536KB;其他语言 589824KB
题目描述:
小B乘火车和朋友们一起在N市到M市之间旅行。她在路途中时睡时醒。当她醒来观看窗外的风景时,注意到每个火车站都有一种特别颜色的旗帜,但是她看到的旗帜仅仅是经过的一小部分。小B在乘车过程中有两次清醒的时间,她到达旅程终点时处于睡梦中。出站时,她和朋友们谈论着一路的见闻,朋友们觉得很有意思。
他们把N到和M之间经过车站的旗帜颜色依次列出来,然后告诉你小B记得的旗帜颜色序列,让你判断小B究竟是从N和M之间哪些方向才能看到所说颜色的旗帜,还是根本就不 可能看到?颜色用字母代表,相同的字母代表相同的颜色,不同的字母则表示不同的颜色。
输入
输入中有多组测试数据。每组测试数据包含三行,第一行为一个由小写拉丁字母构成的非空字符串,长度不超过10^5,表示N到M之间车站的颜色。火车从M向N运行时,经过的车站相同,只是方向相反。第二行为小B在第一次睡醒时看到的颜色序列,第三行为小B在第二次睡醒时看到的颜色序列。两个序列都是小写的拉丁字母构成的字符串,长度不超过100个字母。每个序列的颜色顺序排列按小B看到的时间顺序排列。
输出
对每组测试数据,在单独的行中输出小B的旅行方向。
forward – 由N到M方向;
backward – 由M到N方向;
both – 两种方向都有可能;
invalid – 不可能看到这样的颜色序列;
样例输入
atob
a
b
aaacaaa
aca
aa
样例输出
forward
both
Hint
火车假定时刻处于运动状态,不会两次看到同一个旗帜。N市和M市的车站没有旗帜。
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { String t = sc.next(); String a = sc.next(); String b = sc.next(); boolean res1 = isCan1(t, a, b); char[] tArr = t.toCharArray(); for (int i=0,j=tArr.length-1; i<j; i++,j--) { char tmp = tArr[i]; tArr[i] = tArr[j]; tArr[j] = tmp; } t = new String(tArr); boolean res2 = isCan1(t, a, b); if (res1 && res2) System.out.println("both"); else if (res1) System.out.println("forward"); else if (res2) System.out.println("backward"); else System.out.println("invalid"); } } private static boolean isCan1(String t, String a, String b) { int i = t.indexOf(a); if (i == -1) return false; int j = t.substring(i+a.length()).indexOf(b); return j != -1; } }
内存管理
题目描述:
物联网技术的蓬勃发展,各种传感器纷纷出现。小B所在的项目组正在开发一个物联网项目,她们在研究设计一种新的传感器。这种传感器有自己的基本处理单元,具有一定的自主性,能够进行简单的数据收集、处理、存储和传输。为降低系统功耗并保证系统可靠性和可控性,他们要对内存进行基本的管理。研究小组计划开发一个实验性内存管理器,实现对内存的分配、释放和整理。对应的接口为new、del和def,使用语法为:
new size:分配size字节大小的内存块,返回该内存块的句柄handle,size为正整数;
del handle:释放句柄handle指向的内存块;
def:整理内存碎片,将所有已分配内存块按地址从低到高的顺序迁移,使空闲内存碎片在高地址端拼接在一起;
初始内存为 initSize 字节大小的整片空闲内存,编号为 1 到 initSize 。
new size操作中,若存在不小于size的连续空闲内存,则按照小地址优先的原则从空闲内存区域中分配size大小的内存块,标记该内存块状态为已分配,并返回指向该内存块的句柄。若无法分配,则返回空(NULL)。
del handle操作释放由handle标记的内存块,标记被释放的内存状态为空闲。若handle为无效句柄,则返回ILLEGAL_OPERATION。
def 完成内存整理工作,无返回值。
根据设计,每次成功内存分配返回的句柄为一个正整数,从1开始,依次计数。失败的存储分配操作不影响计数。
项目小组将此项任务分配给小B,小B向你求助,你能帮她吗?
输入
输入中有多组测试数据。每组测试数据的第一行为两个正整数T和MaxMem(1<=T<=10000, 1<=MaxMem<=10000),其中T为操作次数,MaxMem为初始内存大小,随后有T行操作指令。
输出
对每组测试数据,按操作顺序输出操作结果。对每个new操作,在单独行中输出结果,成功时输出其返回句柄值,失败则输出NULL。若del操作失败,输出ILLEGAL_OPERATION。def不产生输出。
样例输入
6 10
new 5
new 3
del 1
new 6
def
new 6
样例输出
1
2
NULL
3
搜狗编程题
* 1.题目描述:定义两个大于2的偶数之间的距离,为这两个数之间质数的个数。
* 从小到大输入n个大于2的偶数,输出所有数两两之间距离的总和(应该有n*(n-1)/2个距离,输出总和就好)。
* 输入
* 第一行是输入偶数的个数,最小为2,最大可能到几万。之后每行为一个偶数,最小是4,最大可能是几百万,不重复的升序排列。
* 输出
* 输入数据两两间距离的总和,这应该是一个不小于0的整数。
* 样例输入
* 3
* 4
* 6
* 12
* 样例输出
* 6
* 2.题目描述:求一个字符串的最大回文前缀长度。回文是指正反方向读起来都一样的字符串,比如“abcdcba”就是一个回文。
* 输入
* 一个文本文件,至少包含一个字节。每个字节是一个字符。最大长度可能有几十万字节。
* 输出
* 最大回文前缀的长度。
* 样例输入
* sogou
* 样例输出
* 1
美文美图