字节常见问题
是从面经里扒拉出来的算法题
最后更新于
线程1打印a，线程2打印b，线程3打印c，要求循环打印abc10次。
计算从一棵多叉树（节点取值不相同）的根节点走N步，能走到节点x的概率，任何一个走过的节点不能走第二次（即不能往回走），如果没路可以走可以原地走，如果有路可走，但是步数没用完需要接着走。
口述一下过程
空间复杂度O(1)
算法 给你数组 实现堆排序的过程(我刚开始i说 用优先队列 他说不用这么麻烦，只要给我输出是最大堆的形式，我都卡半天不知道干嘛 最后才想起来用堆的特性 父节点与子结点交换，不知道对不对)
要求只扫一次且空间复杂度为O(1)
这就是求倒数第k个结点吧
已知一个model类new一个对象，并将该对象作为HashMap的key， value为Hello，修改该对象中某一个属性的值，再去HashMap中get此key，此时的value值是什么？
（连续子串长度与a相同，每个字符位置可以不同）
O(n^2)就可以
解释了一下子序列，解释了一下严格递增，O(n2)写了，让优化……提示提示提示，我死活想不出来，这时候面试官的提示越来越高大上，提示包含关系，提示命题的逆否，提示到我越来越想不起来……过了很久很久。然后说我们下一个环节【此时已经知道肯定没戏了】【力扣334】
char[] www.people.com.cn char[] www.elpoep.moc.nc //在原数组上操作，不使用 String 的类方法，不创建额外的空间（数组、堆、栈、对列等）
// 现在用这个random7去实现一个random10.
struct treeNode{ treeNode left, right; int val; }; //实现是否为AVL树的判断 bool isBalance(treeNode root){ }
讲讲快排。把一个完全有序的序列排序时间代价最小的是哪种？（插入排序）
复杂度是多少，最优和最坏情况复杂度是多少，怎么算出来的。
（我这里了讲一种要排序的，一种不用排序然后用hashmap，他问我时间复杂度各是多少）
讲了二分查找。
为什么数组查找快，链表插入快。
最好和最坏情况下是多少。
如/a/b/../.可简化成/a
给一个日志文件，精确到秒，同一时间可能会有多条日志。给一个时间，精确到分钟，找到这一分钟所有的日志。
日志是按时间顺序的，可以用二分查找
复杂度O(n)
力扣环形链表
（只能买卖一次和或任意次
无数根各处粗细不均匀的绳子，烧完是一个小时，怎么计时出45分钟。
两个人轮流投掷硬币，规定正面赢，正反面各50%概率，计算先投的人获胜的概率（用级数去解决）
【利用快排的思想很快就可以做出来】
每一步只能移动到下一行中相邻的结点上。 例如，给定三角形： [ [2], [3,4], [6,5,7], [4,1,8,3] ] 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）【遍历路径求和】
byte返回倒序排列后的byte如输入10110000返回00001101【面试官提醒可以用移位保存每个位置的值然后再倒序】
String，对其求和如"999","2"->"1001"【转为char[]倒序相加，注意进位】
想着用无序数组的中位数来解决，但是面试官说如果选择了数组的最小值或最大值这怎么办，经过我东扯西扯，面试官可能懂了，问了这个方法的时空复杂度。
可以从头找，如果当前值小于最小值，那就更新最小值，然后向后找一个比它大的就可以了
(这个算法没写完，面试官见时间不够了就让我别写先了)
扑克牌三带二(算一算出现的概率，太菜了)
扑克牌五张同色的概率(降低难度，花了一会时间才算出，太菜了)
扑克牌乱序发牌(一开始想着交换乱序，后来想了一段时间，构造乱序数组)
给一对无序数组，给一个target整数，找出数组中两个数字相加为target，并输出下标(不能用哈希) // 就是两数之和呀，不让哈希的话就只能先排序再双指针？
// 数组双指针 链表递归
复杂度要求 O(n)
要求实现删除，添加，反转方法
给一个target整数，每target长度反转一次
手上握有一堆牌，分两步
1.把顶上的牌发出去
2.把顶上的牌放到底部
重复1-2步，直到手上没牌
给出桌子上的发牌顺序，求原来手牌顺序
（先求所有合数）
（实现原理/平均复杂度/能否提前结束/谁性能更优）
（怎么实现调整堆结构/k个最大的数）
给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组
剑指有这一题
力扣应该有一题环形链表
// % &
AB抛硬币，A先抛硬币，正面为赢，直到其中一个人抛出正面
求A赢的概率 // 好多硬币题目啊我不想做
(通过公共祖先结点的距离和)先说出思路，回溯获得根到子节点的路径
0-100 1000w个小数（后面改成了两位小数）（很详细） -> 桶排序 复杂度
给了我一段代码，让我讲一下这个函数的作用是什么，大概是：
int isPair(int a,int b){
int sum=a+b;
return sum>100? 1:(sum<100?-1:0);
}
int countPair(int []array){
//Todo...}
讲完后，让我实现下面那个函数，让我求出数组里有多少对相加等于100的，我想的是排序后，用头尾指针，我写完代码后，他说你这就结束了？让我想一下哪里有问题，还让我想一想如果不排序怎么做。
然后说今天面试结束了，面试官就下线了（也没让我提问....）
回溯
给定一个[Int] Arr，给定数：N、Sum。要求在Arr中找出N个数和为Sum，如果找不到，则返回nil。只需找出一组解即可。
大数要多做几道
每次只能向值比自己小的方向走，且每次只能向下或者向右走 口述搜索、写了dp转移方程，然后实现dp（没跑数据，写出来就行）
力扣那个机器人的题吧
优先队列就行了。。然后他提了句还可以胜者树败者树，表示这个我知道但是一般好像是外存中用的比较麻烦学的时候也没讲实现也不会写 然后优先队列怎么实现，堆，实现堆有哪些要注意的（我也不知道有什么好注意的。。就说了几句实现细节）
电梯从一层往上走时，我们只允许电梯停在其中的某一层。所有乘客从一楼上电梯，到达某层后，电梯停下来，所有乘客再从这里爬楼梯到自己的目的层。在一楼的时候，每个乘客选择自己的目的层，电梯则计算出应停的楼层。 问：电梯停在哪一层楼，能够保证这次乘坐电梯的所有乘客爬楼梯的层数之和最少？（直觉是中位数，不过没想出来严谨的证明，换了种写法，前缀和后缀和搞了一下，面试官期望的应该是DP，不过面试官表示认同我的解法。
如何优化前面说的那种思路？
在升序数组中找出绝对值最小的那个数
没刷到过这个题，一开始满脑子都是快排思想，面试官提示用动态规划的思路后才写出来
给出三种方法
力扣上好几个股票题
追问怎么优化，有没有更好的办法
www.baidu.com ➡️ com.baidu.www