算法 -- IT技术博客大学习 -- 共学习共进步！

• 面试IT业界顶尖企业所应该知道的10道题(1)

题目: 现有一个包含一千万个单词的文本文件, 每个单词占一行, 每行小于1K字节. 要求找出出现次数最多的10个单词. 如果要从一千个这样的文件中找出出现次数最多的10个单词(所有单词加起来去重后不超过一千万个), 你会怎么设计? 难度: 10K 领域: 编码, 架构, 分布式 *** 解析 *** 这道题没有任何算法上的难度, 最简单的思路就是, 一次读取一行, 计数. 先从单个文件来考虑, 首先考察面试者最基本的用计算机解决简单问题的能力.

• 面试IT业界顶尖企业所应该知道的10道题(2)

题目: 某网站的网页带有一个输入框, 该输入框可进行输入提示, 如用户输入”a”, 会提示一个下拉列表, 把以”a”开头的若干单词列出来, 词库总共有一千万个英文单词. 难度: 12K 作者: ideawu 领域: Web, 算法, 架构 *** 解析 *** 这道题不太涉及编码, 主要是考察面试者知识面广度, 架构设计能力. 面试者做的设计不能太理论化, 也不能具体到代码级别, 应该利用图, 表, 文字, 对话等方式来解. 首先考察面试者对 W...

• “火柴棍式”程序员面试题

有时候，有些面试题是很是无厘头，这不，又有一个，还记得小时候玩的的“火柴棍游戏”吗，就是移动一根火柴棍改变一个图或字的游戏。程序面试居然也可以这么玩，看看下面这个火柴棍式的程序面试题吧。下面是一个C程序，其想要输出20个减号，不过，粗心的程序员把代码写错了，你需要把下面的代码修改正确，不过，你只能增加或是修改其中的一个字符，请你给出三种答案。

• 面试题：火车运煤问题

这个可能是一个比较经典的智力题了，和以前的那个《赛马问题》很相似，其题目如下：你是山西的一个煤老板，你在矿区开采了有3000吨煤需要运送到市场上去卖，从你的矿区到市场有1000公里，你手里有一列烧煤的火车，这个火车最多只能装1000吨煤，且其能耗比较大――每一公里需要耗一吨煤。请问，作为一个懂编程的煤老板的你，你会怎么运送才能运最多的煤到集市？这道题一开始看上去好像是无解的，因为你的火车每一公里就要消耗一吨...

• Push Or Pull?

无论是消息系统，还是配置管理中心，甚至存储系统，你都要面临这样一个选择，push模型 or pull模型?是服务端主动给客户端推送数据，还是客户端去服务器拉数据，一张图表对比如下： push模型 pull模型描述服务端主动发送数据给客户端客户端主动从服务端拉取数据，通常客户端会定时拉取实时性较好，收到数据后可立即发送给客户端一般，取决于pull的间隔时间服务端状态需要保存push状态，哪些客户端已经发送成功，哪些发送失...

• 以求医为例谈搜索引擎排序算法的基础原理

我们可以根据直觉和经验，通过试错的办法，把这两个因素结合起来。但更好的办法是我们能找到一个明确的依据，最好能跟数学这样坚实的学科联系起来。说起来，依据朴素的经验，人类在古代就能建造出高楼；但要建造出高达数百米的摩天大厦，如果没有建筑力学、材料力学这样坚实的学科作为后盾，则是非常非常困难的。同理，依据朴素的经验构建的搜索引擎算法，用来处理上万的网页集合应该是没问题的；但要检索上亿的网页，则需要更为牢固的理论基础。

• 智能算法在站点质量评级体系中的应用

　　互联网的迅速发展，海量Web数据的扑面而来，给搜索引擎技术带来了严峻的挑战，但同时也带来了新的机遇。从网页抓取的角度来看，同一站点往往包含质量相似的资源，对一个优质网站进行爬取，往往可以找到更多的优质资源。因此，我们希望对网站的质量进行评级，来反映资源的质量水平，从而影响spider的调度和收录。在以往的实践中，大体思路是根据人工调研出的经验构造出规则和阈值。发现问题后逐个打补丁、调阈值，来适应变化。...

• Kolakoski序列：我们知道的还是太少

上帝创造了整数，其余的则是我们人类的事了。正因为如此，质数、完全数、Fibonacci 数之类的数列才会让数学家们如痴如醉，因为它们的存在是如此自然，没有任何人造的因素。事实上，数学家们对这些数的认识也越来越丰富，挖掘出了这些数列中越来越深刻的性质。不过，人类确实太渺小了。还有好多构造异常简单的“纯天然数列”，我们了解得实在太少。Kolakoski 数列就是最好的例子...

• Bitcoin 的基本原理

Bitcoin 为什么保值，BTC (Bitcoin 的货币简称)存在于一个庞大的 p2p 网络中。使用 Bitcoin 的群体公认了一种算法，这种算法在现今的条件下，每小时只会新产生大约 6 组新的 BTC ，目前一组是 50 个。也就是说，这个世界上，每个小时大约只会产生 300 个 BTC 。这个产量还会由网络自动调整难度来限制产量。你没办法通过修改所有人的 Client 的算法及参数(client 是开源的)来加快货币产量。伪造的货币会被网络丢弃(除非你可以控制大部分网络节点)。

• HBase二级索引与Join

二级索引与索引Join是多数业务系统要求存储引擎提供的基本特性，RDBMS早已支持，NOSQL阵营也在摸索着符合自身特点的最佳解决方案。这篇文章会以HBase做为对象来讨论如何基于Hbase构建二级索引与实现索引join。文末同时会列出目前已知的包括0.19.3版secondary index, ITHbase, Facebook方案和官方Coprocessor的介绍。理论目标在HBase中实现二级索引与索引Join需要考虑三个目标： 1，高性能的范围检索。 2，数据的低冗余（存储所...

• 趣题：老鼠与毒药问题的推广

今天的趣题来源于 IBM Ponder This 三月份的谜题。大家应该都听说过这个老题目：有 1000 个一模一样的瓶子，其中有 999 瓶是普通的水，有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在，你只有 10 只小白鼠和一星期的时间，如何检验出哪个瓶子里有毒药？这个问题的答案也堪称经典：把瓶子从 0 到 999 依次编号，然后全部转换为 10 位二进...

• 僵尸对象或 RAII

我最近在想这个问题，到底要不要在程序中使用异常？以前写的 C 代码比较多，即使写 C++，基本上也是把它当成 C with object …

• Hive-如何基于分区优化

Hive优化

• 数学之美：垂心的各种优雅的性质

三角形的奇迹首先表现在各个“心”上：三角形内部的每一组有几何意义的线条都交于一点。三条角平分线交于一点，这个点就叫做三角形的“内心”，它是三角形内切圆的圆心；三边的中垂线交于一点，这个点就叫做三角形的“外心”，它是三角形外接圆的圆心；三角形的三条中线也交于一点，这个点叫做三角形的“重心”，因为它真的就是这个三角形的重心。用力学方法可以很快推导出，它位于各中线的三等分点处。这些心将会在本文后面某个出人意料的地方再次出现。

• jvm垃圾回收

在jvm中堆空间划分为三个代：年轻代（Young Generation）、年老代（Old Generation）和永久代（Permanent Generation）。年轻代和年老代是存储动态产生的对象。永久带主要是存储的是java的类信息，包括解析得到的方法、属性、字段等等。永久带基本不参与垃圾回收。我们这里讨论的垃圾回收主要是针对年轻代和年老代。具体如下图。年轻代又分成3个部分，一个eden区和两个相同的survior区。刚开始创建的对象都是放置在eden区的。分成...

• 干嘛不去掉“I”和“Impl”？

今天早上我仔细研究TopShelf项目的源代码，想追查里面一个API的修改，突然发现TopShelf终于向新近流行的去掉接口名称上的“I”字母做法屈服了。在.NET上这还是个新事物，使用Java的人这样做了有一段时间了，但在.NET里很多都还是新事物。这些可不是从ruby偷来的。如果你对此不太熟悉，我先解释一下，传统的习惯是在接口的名称前加入一个毫无必...

• Hive源码解析-之-语法解析器

hive 源码解析

• HIVE的CTAS用法探究

最近在使用ADM系统的时候遇到一个问题，ADM在自动将HIVE QL包装成CTAS之后，由于HIVE内部缺省使用’\\N’来存储NULL，这样就会产生一个问题，因为我们处理的很多结果数据是需要导出附件来给下游客户使用的，而导出数据时很少会使用这样一个特殊的字符串来代表NULL值。这种情况下，HIVE为我们提供了重新定义NULL值存储格式的方法，使用serialization.null.format参数。一、CTAS功能探究对于已经创建成功的hive表，如果希望修改NU...

• 趣题：八等分一张圆饼最少需要多少刀？

一个有趣的智力题：将一张摊好的软面饼分成八等份，最少需要几刀？你可以任意折叠这张面饼。

• 蛋疼研究之单词等式

先给大家看两个“单词等式”： ACT + DEAL = DONE COIN + TRY = DIAL 除了意义上说得通以外，从另外一个角度来看，这两个等式也是成立的。大家能猜到是什么吗？答案是：这两个等式真的就是成立的――如果把单词看作 36 进制数的话。把 ACT 转换成 10 进制就是 13421 ，把 DEAL 转换成 10 进制就是 625053 ，而 DONE 的 10 进制正好就是 638474 ...