请你说一说洗牌算法？
参考回答：
考察点：
公司：腾讯
1、Fisher-Yates Shuffle算法
最早提出这个洗牌方法的是 Ronald A. Fisher 和 Frank Yates，即 Fisher–Yates Shuffle，其基本思想就是从原始数组中随机取一个之前没取过的数字到新的数组中，具体如下：
1）初始化原始数组和新数组，原始数组长度为n(已知)。
2）从还没处理的数组（假如还剩k个）中，随机产生一个[0, k)之间的数字p（假设数组从0开始）。
3）从剩下的k个数中把第p个数取出。
4）重复步骤2和3直到数字全部取完。
5）从步骤3取出的数字序列便是一个打乱了的数列。
时间复杂度为O(n*n)，空间复杂度为O(n)。
2）Knuth-Durstenfeld Shuffle
Knuth 和 Durstenfeld 在Fisher 等人的基础上对算法进行了改进，在原始数组上对数字进行交互，省去了额外O(n)的空间。该算法的基本思想和 Fisher 类似，每次从未处理的数据中随机取出一个数字，然后把该数字放在数组的尾部，即数组尾部存放的是已经处理过的数字。
算法步骤为：
\1. 建立一个数组大小为 n 的数组 arr，分别存放 1 到 n 的数值；
\2. 生成一个从 0 到 n - 1 的随机数 x；
\3. 输出 arr 下标为 x 的数值，即为第一个随机数；
\4. 将 arr 的尾元素和下标为 x 的元素互换；
\5. 同2，生成一个从 0 到 n - 2 的随机数 x；
\6. 输出 arr 下标为 x 的数值，为第二个随机数；
\7. 将 arr 的倒数第二个元素和下标为 x 的元素互换；
……
如上，直到输出m 个数为止
时间复杂度为O(n)，空间复杂度为O(1)，缺点必须知道数组长度n。
-
本文向大家介绍请你说一说OS缺页置换算法相关面试题，主要包含被问及请你说一说OS缺页置换算法时的应答技巧和注意事项，需要的朋友参考一下 参考回答： 当访问一个内存中不存在的页，并且内存已满，则需要从内存中调出一个页或将数据送至磁盘对换区，替换一个页，这种现象叫做缺页置换。当前操作系统最常采用的缺页置换算法如下： 先进先出(FIFO)算法：置换最先调入内存的页面，即置换在内存中驻留时间最久的页面。按
-
本文向大家介绍请你说一说推荐算法，fm，lr，embedding相关面试题，主要包含被问及请你说一说推荐算法，fm，lr，embedding时的应答技巧和注意事项，需要的朋友参考一下 参考回答： 推荐算法： 基于人口学的推荐、基于内容的推荐、基于用户的协同过滤推荐、基于项目的协同过滤推荐、基于模型的协同过滤推荐、基于关联规则的推荐 FM： LR： 逻辑回归本质上是线性回归，只是在特征到结果的映射中
-
本文向大家介绍请你来说一说协程?相关面试题，主要包含被问及请你来说一说协程?时的应答技巧和注意事项，需要的朋友参考一下 参考回答： 1、概念： 协程，又称微线程，纤程，英文名Coroutine。协程看上去也是子程序，但执行过程中，在子程序内部可中断，然后转而执行别的子程序，在适当的时候再返回来接着执行。 例如： 由协程运行结果可能是12x3yz。在执行A的过程中，可以随时中断，去执行B，B也可能在
-
本文向大家介绍请你说一说epoll原理？相关面试题，主要包含被问及请你说一说epoll原理？时的应答技巧和注意事项，需要的朋友参考一下 调用顺序： int epoll_create(int size); int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event); int epoll_wait(int epfd, struc
-
本文向大家介绍请你说一说C++两种map？相关面试题，主要包含被问及请你说一说C++两种map？时的应答技巧和注意事项，需要的朋友参考一下 参考回答： unordered_map（哈希表)和map（红黑树）
-
本文向大家介绍请你说一说Top(K)问题？相关面试题，主要包含被问及请你说一说Top(K)问题？时的应答技巧和注意事项，需要的朋友参考一下 参考回答： 1、直接全部排序（只适用于内存够的情况） 当数据量较小的情况下，内存中可以容纳所有数据。则最简单也是最容易想到的方法是将数据全部排序，然后取排序后的数据中的前K个。 这种方法对数据量比较敏感，当数据量较大的情况下，内存不能完全容纳全部数据，这种方法