海量数据处理的 Top K算法(问题) 小顶堆实现

海量数据处理的 Top K算法(问题) 小顶堆实现

笔试面试 5年前 (2012-09-25) 浏览: 21

问题描述:有N(N>>10000)个整数,求出其中的前K个最大的数。(称作Top k或者Top 10) 问题分析:由于(1)输入的大量数据;(2)只要前K个,对整个输入数据的保存和排序是相当的不可取的。 可以利用数据结构的最小堆来处理该问题。 最小堆如图所示,对于每个非叶子节点的数值,一定不大于孩子节点的数值。这样可用含有K个节点的最小堆来保存K个目前的最大值(当然根节点是其中的最小数

面试题集锦

面试题集锦

笔试面试 5年前 (2012-09-25) 浏览: 9

1、实现一个函数,对一个正整数n,算得到1需要的最少操作次数。 操作规则为:如果n为偶数,将其除以2;如果n为奇数,可以加1或减1;一直处理下去。 例子: func(7) = 4,可以证明最少需要4次运算 n = 7 n-1 6 n/2 3 n-1 2 n/2 1 要求:实现函数(实现尽可能高效) int func(unsign int n);n为输入,返回最小的运算次数。给出思路(文字描述),完

Top K问题

Top K问题

算法/数据结构 5年前 (2012-09-25) 浏览: 15

问题描述:(百度面试题)搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为0-255字节。假设目前有1000万个记录,除去重复后,不超过300万个。一个查询串的重复度越高,说明查询它的用户越多,也就是越热门,请你统计最热门的10个查询串,要求内存不能超过1G。 问题解析: 【分析】:要统计最热门查询,首先就是要统计每个query出现的次数,然后根据统计结果,找出To

进程与线程的区别

进程与线程的区别

系统原理 5年前 (2012-09-25) 浏览: 6

一 程序是存放在磁盘上的一系列代码和数据的看执行映像,是一个静止的实体,   二 进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动,是系统进行资源分配和调度的一个独立单位, 是一个执行中的程序,它是动态的实体;   三 线程是进程的一个实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位.线程自己基本上不拥有系统资源,只拥有一点在运行中必不可少的资源(如程序计数器,

线程安全和线程可重入

线程安全和线程可重入

Linux 5年前 (2012-09-24) 浏览: 16

线程安全:概念比较直观。一般说来,一个函数被称为线程安全的,当且仅当被多个并发线程反复调用时,它会一直产生正确的结果。 可重入:概念基本没有比较正式的完整解释,但是它比线程安全要求更严格。根据经验,所谓“重入”,常见的情况是,程序执行到某个函数foo()时,收到信号,于是暂停目前正在执行的函数,转到信号处理函数,而这个信号处理函数的执行过程中,又恰恰也会进入到刚刚执行的函数foo(),这样便发生了

经典智力问题收集

经典智力问题收集

笔试面试 5年前 (2012-09-24) 浏览: 6

第一部分题目开始: 1、有两根不均匀分布的香,香烧完的时间是一个小时,你能用什么方法来确定一段15分钟的时间? 2、一个经理有三个女儿,三个女儿的年龄加起来等于13,三个女儿的年龄乘起来等于经理自己的年龄,有一个下属已知道经理的年龄,但仍不能确定经理三个女儿的年龄,这时经理说只有一个女儿的头发是黑的,然后这个下属就知道了经理三个女儿的年龄。请问三个女儿的年龄分别是多少?为什么? 3、有三个人去住旅

信号量与互斥锁的区别

信号量与互斥锁的区别

Linux 5年前 (2012-09-24) 浏览: 17

信号量用在多线程多任务同步的,一个线程完成了某一个动作就通过信号量告诉别的线程,别的线程再进行某些动作(大家都在sem_wait的时候,就阻塞在那里)。而互斥锁是用在多线程多任务互斥的,一个线程占用了某一个资源,那么别的线程就无法访问,直到这个线程unlock,其他的线程才开始可以利用这个资源。比如对全局变量的访问,有时要加锁,操作完了,在解锁。有的时候锁和信号量会同时使用的. 也就是说,信号量不

TCP连接的建立与断开

TCP连接的建立与断开

网络 5年前 (2012-09-24) 浏览: 25

1.为什么建立连接协议是三次握手,而关闭连接却是四次握手呢? 这是因为服务端的LISTEN状态下的SOCKET当收到SYN报文的建连请求后,它可以把ACK和SYN(ACK起应答作用,而SYN起同步作用)放在一个报文里来发送。但关闭连接时,当收到对方的FIN报文通知时,它仅仅表示对方没有数据发送给你了;但未必你所有的数据都全部发送给对方了,所以你可以未必会马上会关闭SOCKET,也即你可能还需要发送

切换注册

登录

忘记密码 ?

切换登录

注册

扫一扫二维码分享