剑指Offer——腾讯+360+搜狗校招笔试题+知识点总结

剑指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

美文美图

剑指Offer——腾讯+360+搜狗校招笔试题+知识点总结 

剑指Offer——腾讯+360+搜狗校招笔试题+知识点总结

剑指Offer——腾讯+360+搜狗校招笔试题+知识点总结

上一篇:1.docker学习之简介


下一篇:剑指Offer——京东校招笔试题+知识点总结