GNote.Net | 记笔记

昨天同学去google笔试，我好奇的问了问笔试题目。
有一道题是这样的：
两个相同长度的整型数组A、B，长度为n。现从两个数组中，各抽出S个数，形成两个新的数组C、D。
实现一个算法，保证数组CD的内积最大，并分析时间和空间复杂度。

我说了一个解法，被同学指出复杂度高，于是又验证了同学的解法，确实更快。
我的解法如下：
先考虑一下，当CD两个数组确定后，如何排列里面的元素可以使内积最大。
假设数组中只有两个元素C1C2和D1D2，并且C1 > C2 && D1 > D2，则可以证明 C1*D1 > C2*D2
如此推广开，就是大的乘大的，小的乘小的，可以保证内积最大。

第二步，如何从两个数组中取出S个数。
考虑到整数的正负符号问题，负负得正，所以我先用绝对值从大到小排序，得到两个数组A’和B’（这个复杂度是nlgn）
然后从大到小遍历A’，每访问到一个数a，就从B’中找一个数可以和a相乘得到最大值。
如此继续2*S次，然后从结果中选出值最大的S对就是答案了（这一步的复杂度为n^2）。

同学的想法是：
直接将两个数组按大小排序，然后从数组两头向中间各取S个数，相同下标的相乘，从结果中选出值最大的S对就是答案。整个过程的复杂度都在nlgn这个量级上。

相关文章:
《告诫blogger:别动不动跟我谈逻辑》

我在我的blog上说我的观点，又没去你的地盘上JJYY，用不着你告诫。
blogging领域算个屁，整天一副blogger领军人物的架势，告诫这个告诫那个。

我就说你没逻辑了，你也可以在你blog上说我是放屁。
想让我放弃我的想法，或者让我闭嘴，办不到。
今天看哪篇文章不顺眼了，我就写逻辑错误；明天看那篇文章不顺眼了，我就写语句不通。
想点名点名，想引用引用。要是看不顺眼啊，对不住了，您别看就是了。

－－－－－－－－－－－
附一篇文章
韩寒：《文坛算个屁，谁都别装逼》

早上在抓虾热文上看到了曹增辉的文章《杀手Google和迷茫的抓虾》，我对文中的几个结论很怀疑。

作者说“Google的这个订阅数价值要远大于抓虾”，并说“原因很简单，Google的订阅用户是纯粹吸引过来对我的post感兴趣的读者；而抓虾不同，抓虾有社区化功能，帮他吸引了大量可能不应该属于我的读者的订户。”
这个判断有点想当然了。第一：Google的订阅数中有多少是活跃的有人看的订阅？有多少被当作是feed列表的备份只是导进去保留着的？有多少用户同时使用抓虾和Google Reader？有多少人是在抓虾看到了文章然后转去用GReader订阅的呢？干掉这些人数，又有多少是真正的用GReader发现并订阅了你的博客呢？
第二：抓虾的订阅数同样存在这样的疑问，另外再加上一个，有多少订阅是抓虾的社区化帮着吸引来的？真正吸引人订阅的，是你的文章质量。抓虾社区提供了一个平台，使blogger的文章能够得到充分的展示，优秀的feed会脱颖而出，增加订阅。
没有考虑这些因素对订阅数的影响就得出“毫无疑问，Google的这个订阅数价值要远大于抓虾”的结论，这个结论是疑问重重。

改版前的热文算法，马太效应严重，得票高的文章一整天垄断热文第一页，而因为展示的时间长，第一页的得票文章得票普遍很高，而之后几页的文章，票数就很少了，使得得票少的优秀的文章肯本没有机会得到展示。
改版后的热文，充分的考虑到了小频道的问题，允许只有很少票数的文章就进入最新热文，大大增加了订阅数少的优秀频道展示的机会，让用户有机会接触更多优秀的频道，让优秀的频道更容易的脱颖而出。
有没有如曹增辉所说“分散了用户的注意，推荐数字减少了、话题被分散了，结果就是价值降低了”呢？拿数据来说话，用“改版后的最热文章排行”和“改版前的热文”比较，据我统计，前三页的文章平均票数上涨了5票左右。任何时间查看“24小时最热”，都有接近和超过100票的文章，这说明每天都有推荐达到百票左右的文章，这在以前的热文中也是没有出现过的，所以说“推荐数减少”这个结论是站不住的。
再说“话题被分散了，结果就是价值降低了”？由话题分散推出价值降低？我没有找到这其中的因果联系。如果是在一个IT专业论坛，讨论饮食和股票我们可能说话题分散导致价值降低，但对于一个Digg类产品来说，由话题分散推出价值降低就显得过于草率了。要想论证这个问题，我想至少要在以下两点达成共识：1，话题分散如何确定，以及度量标准；2，如何定义价值（有用？喜欢看？消磨时间？），以及度量标准（订阅数？浏览数？收藏数？还是其他什么值）。然后才来判定话题分散和价值升降的关系。在我个人看来，Digg类网站话题分散是好事情，这使得让任何人都能在其中找到自己感兴趣的内容。

曹在原文中开始就提到“我应该也会坚持Google，因为它更高效的解决了我的阅读需求，这个是第一位的，然后才是发现和交流”，而在文章最后又用加粗字体强调“我只关心，我怎么能看到我喜欢的文章，找到我感兴趣的feed”。到底是发现是第一位还是阅读是第一位？恐怕作者自己也搞不清了。其实抓虾热文就是一个发现的平台，帮助发现好看的feed。看看朋友看了什么，收藏了什么，这也是一个发现的渠道。阅读社区会发展成什么样，还得继续探索。

坐在公交车上，地铁上，经常会看到带着耳机听音乐的人。如果再仔细观察，发现这些人中有一半是用手机听，一半用MP3。

用手机听音乐最大的障碍是什么？音效、电池的续航能力。
用手机听音乐最大的好处是什么？手机是随身携带的必备品，MP3不是，iPod也不是。用手机听音乐可以少带一样电子设备，加上附属配件如充电器，数据线啥的。

音效不是问题，音乐解码芯片的技术很成熟，再配上好耳机即可。
电池的续航能力也在不断加强，电池技术还会继续发展。
MP3的路快走到头了。
苹果也在造iPhone啊。

Google Reader中文版会对抓虾造成冲击吗？我认为不会。
中午的时候，晨钟暮鼓报道说，Google Reader中文版上线了，随后又有好几个
人报告Google Reader中文版上线，并提到可能会对抓虾造成压力。

Google Reader中文版上线，肯定会有部分用户从各个阅读器搬家过去。Google
Reader作为一个纯粹的Reader，还只是一个工具。而抓虾的核心竞争力，已经不仅
仅是阅读器了，他还是一个阅读社区。

阅读的来源是受人影响的，别人看什么，关注什么很大程度上都会影响到一个人选
择阅读什么。而阅读后呢，需要分享，分享观点并且与别人交流，希望观点得到认
同。这些都需要一个平台和社区，而抓虾正在渐渐扮演这一角色。

别人去读互联网，我们来读别人。我现在经常看我的抓虾页面，看看我的朋友都看
了啥，推荐了啥，收藏了啥，这些文章都是被人肉过滤过的，质量可靠，我也经常
从中发现好的文章。抓虾应该用个人页面替换掉好看那个标签，加快社区化的进度。

还有更大的人肉过滤，抓虾热文。每天关注blog圈里最热的文章，看别人读了什
么，不会错过互联网上最热门的新闻和事件。如果自己看feed呢，或多或少的
总会错过什么，或者延迟一段时间才会知道。

社会化阅读，可以让文章拥有更多的读者，从而获得更大的影响力。如果你已经闻
达于网络，那写写blog发挥你的影响力是不难的。但对一个小blogger来说，需要
一个平台来展示他们优秀的文章，酒好也怕巷子深。抓虾热文就是一个blogger展
示自己的平台，只要有稳定的读者，只要保证帖子质量，两三个月获得几千个订阅
也是有的。

抓虾已经形成了一定规模的社区，现在需要在社区化上作更多的尝试。

前些天收集了一些流媒体(stream media)的资料。现整理如下

流媒体是指用一个视频传送服务器把节目当成数据包发出，传送到网络上。用户通过解压设备对这些数据进行解压后，节目就会像发送前那样显示出来。这个过程的一系列相关的包称为“流”。流媒体最大的好处是用户可以不用下载完整个文件，就可以开始播放音频视频文件。

按照传输协议，流媒体传输可以使用HTTP、RTSP、RTP、PNM、MMS、MMST等。
根据协议的不同，选用的服务器也会不同：
使用HTTP协议的流媒体传输，当前最红的格式是FLV，当今的视频网站如youtube，土豆网等都是使用这种文件格式。FLV的全名是Flash Video，特点为文件体积小、跨平台（不依赖于操作系统和浏览器），占用资源小，所以成为了网络最流行的视频格式。
因为使用HTTP协议，传输FLV所用的服务器的选择有很多：
(1)Lighttpd，youtube所使用的服务器
(2)Nginx，由俄罗斯的Igor Sysoev开发的性能优越的轻量级web server
(3)red5，一个java开源FLV服务器
(4)apache
(5)FlashMediaServer，adobe的FLV服务器，收费的。

其它常用的流格式按照厂商和平台的不同可以分为三个类别：
(1)Helix server
real公司的产品，支持RTSP,RTP,PNM等协议，主用用于rm,rmvb,mp3等格式的流传输
可以在Windows和linux平台下架设，开源。
(2)Windows Media Services
微软开发的windows平台下的流媒体服务器，支持mms协议，用于wmv、asf等格式的流传输。
(3)Darwin
Apple公司的流媒体服务器，开源，可部署在linux平台，用于mov和各种mpeg4格式的流传输，如3gp等。

手机上看流媒体怎么样？
手机流媒体和PC的流媒体没有大的区别，主要就是终端的不同，即手机终端自身的特点，内存小，带宽低等。在服务器端，需要做一些特殊的配置和优化以适应这些特点。
手机看流媒体还受到手机带宽，屏幕大小，音效和视觉效果，电池续航能力，资费等因素的影响，要想普及还是不容易的。

一个产品赢得用户的关键是什么？
是体验？功能？细节？
是口碑？品牌？价格？
也许这是都是关键，也许都不是。
讨论这个问题，我们有很多标准的答案，比如说功能之基础，体验是重点，细节不可忽略等等。还可以就此展开长篇大论，讲座论坛，聊的不亦乐乎。然后上升到理论如“满足用户的需求”，“以用户为中心的设计”等等。这些话都对，但都没有用，我们不能用这几句话就做出好的产品。

到底是什么打动了用户，成为一个产品的核心竞争力？每一个产品都不一样，可以说成功的产品都一样，不成功的各有各的不足。我不知道答案，我也在找答案。所以本文只有问题，没有答案。

gmail为什么成功？百度贴吧为什么成功？ipod为什么成功？淘宝为什么成功？

今天下午有人问：你会选择用手机听音乐吗？
答：我不用手机听，以后多半也不会用手机听音乐。
问：为什么？
答：我用ipod听音乐，手机我用来打电话，发短信，当闹表。
问：那如果ipod能打电话，你还用手机不？
答：那不就是iphone吗，我会选择用iphone，不用手机了。
以上对话可以引出一个问题：问什么我（可能还有很多人和我一样）会选择一个可以打电话的ipod，而不选择一个可以听歌的电话？

还有一件事。以前，我曾经为所有媒体格式选择了一个播放器，wimnap，real player，WMP，QuickTime，divx等等。虽然也层出现过一些通吃的播放器，可以播放几乎所有的媒体格式，但我都拒绝使用。这一行为保持了很长时间，直到暴风影音的出现，我彻底放弃了除暴风影音外的其他播放器。
暴风影音好在哪？

这些具体问题的答案不重要，重要的是怎样找到一个可执行的方案，通过这个方案找到产品的核心竞争力。

网民的创造力是无穷的！
经常在网上看到这个字符串组合“orz”，一直不知道是个啥意思。今天终于忍不住问同事，他也不知道。于是百度一下，感谢伟大的百度百科。

“orz” 学名：失意体前屈。
从百度百科摘抄一段：原本指的是网络上流行的表情符号：＿|￣|○ ，它看起来像是一个人跪倒在地上，低著头，一副“天啊，你为何这样对我”的动作，虽然简单却很传神。
在初期，并没有人对这个符号起个名字，“失意体前屈”这个名字也是后来才出现的。据说是某个餐厅的座垫上绣著这五个字，至于在这之前又是谁想到的，目前尚未厘清真相。 后来，又有人发现，用简单的三个英文字也可以表现这个动作，于是orz就开始流行了。接下来，更有 orz 的日志软件、日志网站相继出现。在2004年后，于日本、中国大陆、香港与台湾俨然已经成为一种新兴的网络文化。

更NB的是“orz”的各种变体，以下拷贝几个，完全版请看百度百科。当然，读者也可以自己创造几个。
全角：
＿|￣|○ ← 右向
○|￣|＿ ← 左向
半角：
STO ← 右向
OTZ ← 左向
迷你形：
no ← 右向
on ← 左向
高级变体：
囧gg
有趣变体：
orz 这是小孩
OTZ 这是大人
OTL 这是完全失落
or2 这是屁股特别翘的
or2=3 这是放了个屁的
Or2 这是头大身体小的翘屁股
Or? 这也是头大身体小的翘屁股
orZ 这是下半身肥大
OTz 这是举重选手吧
○rz 这是大头
On 这是婴儿
crz 这是机车骑士
prz ← 长发垂地的
orz 崮rz 这是囧国国王
莔rz 这是囧国皇后
srQ ← 换一边并舔地板的orz
:◎:rz ←这是张大嘴巴嚎啕大哭的失意体前屈
oΩ: ←背部隆起的
更多请参看百度百科…
网络的语言是无敌的，好比最近出现的知音体和很久以前的梨花体
orz

这几天看抓虾热文，发现又出现一个作弊的小高潮，出现了几篇明显的作弊文章。
作为一个digg类网站，反作弊(anti-spam)应该是一个常抓不懈的工作，否则将出现破窗效应，越是放任作弊，作弊的就越多。所以对作弊行为，应该发现一起，严肃处理一起，决不能手软。即使是优质频道，也可以处理几个，达到杀一儆百的效果。
具体的anti-spam的手段就多样化了

可以针对用户，判断是否是有效的用户；
针对行为，判断是否是有效的操作；
针对数据，判断数据是否有特征；
人肉判断也可以，什么奇技淫巧都可以，有效就好。

顺便收集一下国内的digg类网站，欢迎补充

我常看的有
抓虾
草根
板砖
奇客

其他网站，有很多已经关站甚至页面无法打开了
顶啊　　http://www.dingr.com
窝窝网 http://www.mywowo.com
新聚网 http://www.tagriver.com
教育掘客 http://www.edudig.net
中国掘客 http://www.cndigg.com
投吧网 http://www.vooote.com
中国掘客 http://www.digg.cn/
掘客网 http://www.cndig.com
挨踢英雄榜 http://hero.itqun.com/
17dig.com
比客窝 http://www.pkooo.com
diggfox.com
livedigg.com
www.new21.cn/
http://tuidao.com
www.diggbuzz.com

2007年8月29号，Nokia发布互联网战略。将是另一个iPod + iTunes 这种 硬件 + 服务 的模式吗？也许会的。
Nokia手机在全球有8亿用户，如此庞大的用户群是可以有很多东西可以挖掘的。随着3G网络的普及，手机上的多媒体应用也将越来越多，因为传统的移动业务如电话、短信等不足以消耗3G网络的带宽，要想达到充分利用3G网络的效果，音频视频或者流媒体(stream media)等业务的发展势在必行。这一趋势可能会孕育出新的互联网巨头，结果充满想象。
先来说说Nokia进军互联网对我的影响，Nokia发布了其进军互联网的门户网站ovi(www.ovi.com ，预计四季度发布)，围绕ovi这个名字，可以挖掘出一些有意义的域名，如cnovi,ovicn,chinaovi,ovichina等，一旦ovi发达了，这些域名也可能获得机会。赶快去注册吧！
有这样想法的人太多了，所以，这些域名都已经在8月底、9月初被注册光了，我也慢了一步，扼腕叹息啊。翻找了半天，注册了 oovii.com 这个域名，沾点小边，呵呵。一韬和我说过，成功的网站域名里有两个o，呵呵， oovii 里面也有两个o，有意思。