腾讯常见问题

蛮看重排序算法的哦。
喜欢问一些智力题、数学题。
海量数据问题
问红黑树

数组中重复的数据 // leetcode442

讲思路：玻璃球临界碎点的问题 // 知乎

讲思路：爬楼梯问题 // dp

再问你一个数据结构的问题，数组和链表有什么区别？

如果要让你对数组中的数字进行排序你会有哪些方法？// 快排堆排blabla

快速排序是稳定的排序吗？有什么方法尽量避免变量选取不好的情况？

假如说，现在有一个数组，需要你去找到最大的 K 的数字，该怎么实现？ // 堆

笔试题1：删除无序链表中的重复结点（能否优化）// leetcode-面试题02.01移除重复节点

笔试题2：先说一下二叉树的有哪些遍历方法。写一个二叉树前序遍历的非递归形式。// 前中后

代码题是一道遍历View树 // Android算法题给定ViewGroup打印其内所有的View 递归 bfs dfs 就是考察树的遍历

编程题：二叉树先序遍历的非递归实现 // leetcode144

如何找链表倒数第n个元素？快慢指针 // leetcode19

一个数组插入删除查找和链表的效率对比？如果一个数组要反复插入删除怎么优化降低时间复杂度？（一开始没想到，面试官提示其实就是垃圾回收的算法原理就是“标记-查找”。每次删除的时候元素不是真的被删除了，而是先标记，最后统一移动数组元素，减少移动次数） // 原来如此

效率高的排序方法 // 时间复杂度是nlogn的：快排、堆排

快速排序时间复杂度 // nlogn

最坏情况 100 个数不排序，怎么找到中位数，内存只能装 10 个数 // 解法使用快排的思想，不停的partition

反转链表两个链表相交，怎么找到那个相交点 // 双指针 lcof52

一大段文章，怎么找到想要的字符串 kmp 算法

红黑树的查找复杂度// logn

红黑树插入复杂度 // logn 查找、插入、删除的时间复杂度都是 logn

数组和链表的区别 // √

数组和链表的优缺点？// √

常见的效率较高的排序算法？时间复杂度分别是多少 // √

如何找出数组中的重复元素？（排序）如果不排序呢？（哈希表）// √

如何实现链表反转？// lcof24 递归和双指针迭代

海量数据如何实现排序后写入文件？前提是内存不够一次性写入所有数据

海量数据如何寻找中位数？不能排序，乱序数组中查找

// 别让我碰到小Q的题，谢谢

算法题：N亿个数，找出里面不重复的数，分配的内存很有限

N多个数，找出里面重复最多的数

链表和队列，队列和栈 // 数据结构基础

算法题：字符串根据字典分割的问题。一开始给的解决方法时间复杂度太高，一直要求优化。

数据结构，好像问了集合？// Collection。Java容器那一节要熟悉

跳台阶 // 斐波那契数列

判断链表相交 // 双指针

判断回文链表 // 使用快慢指针找到链表中点后，反转后半段链表，再进行比较即可

算法：判断AVL树 // wiki 平衡二叉树 lcof55

算法：判断二叉查找树 // BST wiki leetcode98

面试官选了一道算法题：从n个数中选出出现次数为奇数次的两个数，并从小到大排序输出 // 异或

// 1 1 2 2 3 3 4 4 4 5 5 5

// a^a=0 a^0=a

手撕生产者消费者代码 // 不想撕

手撕客户端和服务端通信代码 // 还考这种的吗

还有一些问题遗忘了，最后是做一道编程题，二叉树查找相关的，用递归完成了。// 看Notes BST相关

智力题：两个骰子（6面）如何表示2月全部日期 //

编程题考查二叉树Z字型遍历，不能用STL库。// 层次遍历分奇偶层即可 lcof32

两个人轮流投掷硬币，规定正面赢，正反面各50%概率，计算先投的人获胜的概率 // https://www.zhihu.com/question/290055193/answer/467894271

编程题两道：中序和后序推导出前序（二叉树递归完成）// lcof07 重建二叉树

给出一个链表删除倒数第五个节点 // leetcode19 快慢指针

编程题是：数组中每个值看作一栋楼的高度，站在数组中的一个位置求前后能看到的楼的数目（高楼挡在前面会看不到后面的楼）

概率题：x%的人喜欢篮球、y%的人喜欢排球、z%的人喜欢足球，问同时喜欢篮球和排球的人是多少

编程题是：两个超大的字符串文件，求他们的最长回文子串，要求不能调用库（当时用动态规划完成，但是时间复杂度为N^2，其实用马拉车算法可以降低复杂度，但当时我并没有练过，所以就把代码交上去了）

// 会个dp差不多啦 leetcode5 最长回文子串

跳台阶知道吧，怎么做啊。// 斐波那契数列

一个链表，让你找最中间的节点，你怎么找？ // leetcode876

两个大文件，一个比较大，一个比较小，让你求交集，你怎么做？

我们再问两个智力题吧，没有固定答案，不要限制自己的思路，想到啥说啥，一个粗细不一样的绳子，完整的烧完1个小时，你怎么让他烧15分钟（不一定烧完）。

结合从两头开始烧，半个小时烧完，我给他叭叭了一下，但具体怎么回答的忘了，面试官还给我讲了讲，然后就说嗯，好吧，这题就算你过了。。

一副全新的扑克牌，按顺序的，AAAA，2222，3333，这种，你怎么洗牌能洗散开？

说了几种，我把平时洗牌的绝学亮出来了，他还让我说，我想不出来了，他说，嗯好的，这个题算你过吧。

题目大概和leetcode 59题类似。大概如下，从右上角开始顺时针。剑指offer上也有类似的，反正就是刷题，刷题，刷题啊！！！

输入: 3 输出: [  [ 7, 8, 1 ],  [ 6, 9, 2 ],  [ 5, 4, 3 ] ]

那我们再说说链表和数组？比较一下它们有啥区别吧，然后再说说数组里面删除一个元素会怎么样，插入一个元素会怎么样，修改一个元素会怎么样，会发生什么事情？

快排思想，稳不稳定，怎么判断稳定性，快排空间复杂度，时间复杂度

手撕生产者消费者的伪代码，问，如果队列满了怎么办

一个字符串，找出出现次数最多的字符，建立哈希表

介绍二叉树，介绍B+树，红黑树，用途

了解哪些排序算法，说一下怎么实现的。

快排是什么？时间复杂度多少？

七大排序分别是什么？

二叉树原理？

红黑树是什么？

线段树 B+树？

正式批：字符串出现频率中位数、最长公共子串问题LCS

二叉树

B树（插入/删除过程）

上来大数相乘，我做的眼泪都快流出来了。

考了道算法题，求1-1000有多少个1

两道算法题，一道是一个数分解成两个质数和，问有多少对，比如10，分解成(5，5)，（3，7），分解成两对。

算法就问了求链表交点问题

有两个无序的整型数组如何快速找出它们的交集

（思考了5秒以后就回答了使用Map 然后再和他分析了一下怎么快速找出元素如何扩容之类的。）

8bit的数，怎么判断4个1

数据结构哪些地方学的不好，为什么

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

7. 稳定排序？nlogn的稳定排序

二叉树的问题

二叉树的几种遍历方法，如何进行先序遍历？从左还是从右开始遍历？从左开始遍历后如何再i进行遍历？

常用的几种排序？每个排序的时间复杂度和空间复杂度。

有一个3L水的杯子和5L水的杯子，如何倒出4L的水

算法题两数之和 // leetcode1

这个题，，，基本上就是签到题，我是用HashMap优化的，有点取巧了

智力题瓶子从100楼往下扔，一共两个瓶子，问从那个楼扔瓶子刚好碎 // leetcode887

这个题是腾讯最爱问的智力题，这块我一开始想到二分的方法，但是仔细一想这个方法不可以，然后我就想到分段的方法，第一个瓶子10层10层间隔扔，确定大范围，然后第二个瓶子确定小范围，然后面试官说这个方法还是不对，但是比上一个方法好一点，让我再想想，然后我就很着急就想不出来//最后在吴师兄的推文里面看到了解答

红黑树概念，二叉树遍历 // 红黑树我可以不看了吗

因为上一个问题讲到红黑树了，然后讲了下红黑树的概念，然后问其他的我真的不会了，就问了下二叉树的前，中，后遍历方式

算法题如何判断一个数是2的次方如何优化时间复杂度 // leetcode231 位运算判断 n & n-1 是否等于0即可

快排的思想如何优化时间复杂度

这个也是基本问题，然后讲了下快排的思想，然后优化的方式讲了下中间值取值的优化，然后为什么这样做

大数据排序

给1亿的int类型的数，如何找到最大的100个，这种问题肯定不可能直接排序，先分开存储，然后我的思路是用桶排的思想进行处理，可能我的方法不是最优解。

快排和归并排序的复杂度（快排的最差复杂度）

快排为什么比其他 nlogn 快（常数项）// 知乎

稳定排序？nlogn 排序哪些是稳定的？// 快排堆排都不稳定，只有归并排序是稳定的

最后算法题，判断一个8bit串只含有4个1，要求比较次数小于遍历。（一如既往的悔恨啊，逼到面试官最后直接爆答案）// 位运算？

说一说快排 // 捋一遍思路

怎么评价一个算法的时间复杂度// 当然o(1)是最好

将1-100随机放入到长度为100的数组里面，得到的随机数组中不允许有重复数字 // 解法

写快排。// 手推

大数相乘。 // 看看

1、两个字符串s1、s2,字符串里只包含左括号和右括号，要求将两个字符串作合并，最后得到的串能够有正确的左右括号匹配格式，并且合并的串中的字符保持原s1和s2中顺序不变，算出有多少种合并情况。（知道怎么做，没说清楚）//

2、有3000根萝卜，要运到3000千米外，现在有一头驴，它一次可以驼1000根萝卜，然后驴每走1千米，驴哟啊吃掉一根萝卜。问你怎么样运萝卜可以将最多的萝卜运到终点。（算错了，很尴尬）// 解法

3、一群人开舞会，每人头上都戴着一顶帽子。帽子只有黑白两种，黑的至少一种。每个人都能看到其他人的帽子的颜色，却看不到自己的。主持人先让大家看别人头上戴的是什么帽子，然后关灯。如果有人认为自己戴的是黑色的帽子，就拍手。第一次关灯，没有声音。于是再开灯，大家再一看，关灯时候仍然是鸦雀无声。一直到第三次关灯，再有噼噼啪啪的拍手声音响起。问有多少人戴着黑色的帽子。// 解法

快排 // 手推

堆排序 //

给两个数组求最长公共子串 // dp

八皇后

概率论题。挺简单的，一套猛推。推着推着数字记错了。结束才想到

给电话区号，最快的方法找到对应的城市（关系已知）

二叉树有几种遍历方式 // 前中后

说一下堆和栈的特点 // 可以说数据结构层面的也可以说一点os层面的

介绍一下队列和栈，它们在数据进出顺序的方面有什么不同点。//

红黑树查找和插入的时间复杂度

反转单词（最小的空间复杂度）// lcof58 双指针实现从尾部开始向前遍历

算法题：递增序列两数之和，输出乘积最小的两数 // 啥意思，这到底是一个题还是俩题