ftofficer|张聪的blog

从某处zz…

1. 程序员写出自认为没有Bug的代码。
2. 软件测试,发现了20个Bug。
3. 程序员修改了10个Bug,并告诉测试组另外10个不是Bug。
4. 测试组发现其中5个改动根本无法工作,同时又发现了15个新Bug。
5. 重复3次步骤3和步骤4。
6. 鉴于市场方面的压力,为了配合当初制定的过分乐观的发布时间表,产品终于上市了。
7. 用户发现了137个新Bug。
8. 已经领了项目奖金的程序员不知跑到哪里去了。
9. 新组建的项目组修正了差不多全部137个Bug,但又发现了456个新Bug。
10. 最初那个程序员从斐济给饱受拖欠工资之苦的测试组寄来了一张明信片。整个测
试组集体辞职。
11. 公司被竞争对手恶意收购。收购时,软件的最终版本包含783个Bug。
12. 新CEO走马上任。公司雇了一名新程序员重写该软件。
13. 程序员写出自认为没有Bug的代码。

昨天无聊在bbs上面逛，发现joke版上面的一个强帖。本来创意来自mop，是说两组数字怎么得到24：第一组：0,0,0,0；第二组：10、10、10、9。众位闲人们不负众望，充分发挥科大bbs将joke帖转变成技术帖的光荣传统，在得到阶乘这种运算是可以允许的时候，截止到昨天午夜，给出的答案如下，括号里面是我的吐槽，权且当笑话看：

[0,0,0,0]系列 (请在手边常备大学数学书和保证你能够理解二进制补码)：

• (0!+0!+0!+0!)! = 24 (0! = 1，4! = 24，忘了的去补大学数学)
• (cos0+cos0+cos0+cos0) != 24 (这个没甚创意，下面应该就是e^0了吧)
• (!0+!0+!0+!0)! = 24 (by Kamui, 别和第一个弄混了，!在这里表示0的二进制取反，好吧，权且认为这个是对的)
• (exp(0)+exp(0)+exp(0)+exp(0))! = 24 (by spadeQ，好吧，它终于出来了)
• 只要f(0)=1的函数都可以这么套 (by spadeQ，嗯，有人总结pattern了)
• delta函数也可以 (by Kamui，delta函数是阶乘运算推广到实数范围上的函数，忘记的请去查概率论)
  — update@2008-1-1 —
  鉴于数学达人ziyuang提醒，我承认我错了。delta函数的详情请ziyuang来解释一下。
  — /update —
• (-(~0+~0+~0+~0))! = 24 (by me，我也无耻一把好了，~0对于0的按位取反就是-1了)

[10,10,10,9]系列：

• (10-(9^(1/2))!)!+10-10 = 24 (by reneo, 根号无法输出，用1/2次方来表示)
• ((10+10)/10)^3*9^1/2 = 8*3 = 24 (by Dedura)
• (((10*10)^(1/2)/10)+9^(1/2))! = (10/10+3)! = 24 (by Bagwell)
• {-[-(10+10+10)/9]}! = 24 (by Bagwell, 其中"[]"为数据结构中的向下取整符号，这个都出来了 -_-b)
• 9-10的导除以10的导加10的导再阶乘 (by anusitch，不过为什么我觉得是错的~)
• 10+10＝20å’Œ10+9＝19那两年的月份数之和 (by Recnalias，抛开历法不谈，也许……，算是个创意)
• 今年第10+10+10+9天的小时数 (by Recnalias，leng~)

放之四海而皆准系列：

• (10^0+10^0+10^0+9^0)! = 24 (by saturn，不过有了多用了0之嫌，然后有了下面这个)
• {[(10)’]!+[(10)’]!+[(10)’]!+[(9)’]!}!=24 (by Bagwell, x’表示导数，C’=0当C为常数，忘记的去补大学微积分。确实没有多用数字……)
• (sgn(10)+sgn(10)+sgn(10)+sgn(9))! (zz by xii, sgn为二值函数，sgn(c)=1当c大于零，忘记的请去补信号与系统或者自动控制原理)
• 从0到24/39对(10+10+10+9)积分 (by Recnalias，这个……)
• 以(10+10)为期望（10+9）为标准差的正态分布的某次取样 (by Recnalias，好吧好吧，也许某次取样就是这个，但是能告诉我这个概率么？)
• define:return24（x1,x2,x3,x4）= 24; (by Joedanver的师弟，终极解决方案，不过我说，在代码当中硬编码magic number是不好地~)

— 2007å¹´12月20日更新 —
10+10+lg10+sqrt(9) = 24

来自这里。

1. There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1].

   Solve it without division operator and in O(n).

2. There is a linked list of numbers of length N. N is very large and you don’t know N. You have to write a function that will return k random numbers from the list. Numbers should be completely random.

   Hint:
   1. Use random function rand() (returns a number between 0 and 1) and irand() (return either 0 or 1)
   2. It should be done in O(n).

3. You are given a game of Tic Tac Toe. You have to write a function in which you pass the whole game and name of a player. The function will return whether the player has won the game or not. First you to decide which data structure you will use for the game.You need to tell the algorithm first and then need to write the code.

   Note: Some position may be blank in the game। So your data structure should consider this condition also.

4. You are given an array [a1 To an] and we have to construct another array [b1 To bn] where bi = a1*a2*…*an/ai. you are allowed to use only constant space and the time complexity is O(n). No divisions are allowed.
5. How do you put a Binary Search Tree in an array in a efficient manner.

   Hint: If the node is stored at the ith position and its children are at 2i and 2i+1(I mean level order wise)Its not the most efficient way.

6. How do you find out the fifth maximum element in an Binary Search Tree in efficient manner.

   Note: You should not use use any extra space. i.e sorting Binary Search Tree and storing the results in an array and listing out the fifth element.

7. Given a Data Structure having first n integers and next n chars. A = i1 i2 i3 … iN c1 c2 c3 … cN.Write an in-place algorithm to rearrange the elements of the array ass A = i1 c1 i2 c2 … in cn
8. Given two sequences of items, find the items whose absolute number increases or decreases the most when comparing one sequence with the other by reading the sequence only once.
9. Given That One of the strings is very very long , and the other one could be of various sizes. Windowing will result in O(N+M) solution but could it be better? May be NlogM or even better?
10. How many lines can be drawn in a 2D plane such that they are equidistant from 3 non-collinear points ?
11. Lets say you have to construct Google maps from scratch and guide a person standing on Gateway of India (Mumbai) to India Gate(Delhi).How do you do the same ?
12. Given that you have one string of length N and M small strings of length L . How do you efficiently find the occurrence of each small string in the larger one ?
13. Given a Binary Tree, Programmatically you need to Prove it is a Binary Search Tree

    Hint: Some kind of pointer handling with In Order Traversal – anybody in for writing some code

14. You are given a small sorted list of numbers, and a very very long sorted list of numbers – so long that it had to be put on a disk in different blocks. How would you find those short list numbers in the bigger one?
15. Suppose you have given N companies, and we want to eventually merge them into one big company. How many ways are theres to merge?
16. Given a file of 4 billion 32-bit integers, how to find one that appears at least twice?
17. Write a program for displaying the ten most frequent words in a file such that your programshould be efficient in all complexity measures.
18. Design a stack. We want to push, pop, and also, retrieve the minimum element in constant time.
19. Given a set of coin denominators, find the minimum number of coins to give a certain amount of change.
20. Given an array,
    i) find the longest continuous increasing subsequence.
    ii) find the longest increasing subsequence.
21. Suppose we have N companies, and we want to eventually merge them into one big company. How many ways are there to merge?
22. Write a function to find the middle node of a single link list.
23. Given two binary trees, write a compare function to check if they are equal or not. Being equal means that they have the same value and same structure.
24. Implement put/get methods of a fixed size cache with LRU replacement algorithm.
25. You are given with three sorted arrays ( in ascending order), you are required to find a triplet ( one element from each array) such that distance is minimum.

    Distance is defined like this :

    If a[i], b[j] and c[k] are three elements then distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))"

    Please give a solution in O(n) time complexity

26. Classic – Egg Problem
    You are given 2 eggs.You have access to a 100-storey building.

    Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.

    Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process.

Long Live the Command Line: access Google Calander

The latest example of new-meets-old: the gcalcli command-line interface to Google’s online calendar application. It’s an open-source utility that lets people read and update Google calendars–either their own or shared ones.

原以为是Google Calander的Web UI直接支持的command line接口，还想看看Google对于Command Line UI的支持方式——毕竟这个公司对于Web的理解应当成为一个值得借鉴的素材；仔细一看其实不是，这是Google Code上面的一个项目，用Google GData API访问Google Calander的后台并提供一个命令行接口。

有点意思，但是这种做法反而失去了Web 2.0的优势——随时随地的访问。

不过，让我们回头考虑一下，为什么这种Command Line接口的Google Calender前端会有市场——因为人们的操作习惯使然。而目前的Web软件开发还没有形成一种统一的操作习惯——虽然大多数人看到鼠标变成手形就会试图电击，但是更细致的习惯，像Unix一样认为一切皆可通过shell和管道通过文本连接的哲学，还没有形成。目前的Web开发，虽然大家让程序运行在相同的浏览器平台上面——通过HTML/XML/JavaScript/Flash来提供UI和使用HTTP进行数据的传输和命令的调用，但是这些UI并没有固定的标准和用户体验，所以人们才想出来开发一个大家习惯的用户界面，来访问Web应用程序。

也许我们除了浏览器，我们还需要一个shell，来整合这一切。这个shell是什么呢？基于feed的Google Personal Page也许是一个趋势：在Unix当中，一切皆是文本；那么在Web上面，一切皆是feed。

那么如何让feed能够更好的互操作呢？如何让用户可以方便的整合不同的应用，让他们通过feed进行通信？

这应该是个非常有趣的话题。

原来Unicode当中还有这种字符：U+0489

Ò‰

看不到的话，估计是你的浏览器或者系统对于Unicode的支持还不够好，所以这个Unicode字符看不到。

OK，然后我们看看更有趣的：

先看看这篇文章：
http://www.tipotheday.com/2007/08/26/wtf-is-this-character/

然后打开这个链接看看你的网页和标题栏：
http://www.google.com/search?hl=en&q=%E2%80%AB%E2%80%AC%E2%80%AD%E2%80%AE%E2%80%AA%E2%80%AB%E2%80%AC%E2%80%AD%E2%80%AB%E2%80%AC%E2%80%AD%E2%80%AE%E2%80%AA%E2%80%AB%E2%80%AC%E2%80%AD%E2%80%AE%D2%89language+&btnG=Search

解释在这里：
http://en.wikipedia.org/wiki/Unicode_control_characters#Bidirectional_text_control
照顾不能上wikipedia的朋友们，贴过来：

实际上在这两个例子当中，一圈逗号的字符只是一个幌子，真正起作用的是U+202B – U+202E一系列的转义字符，只是它们都是不可显示的，所以需要用一个幌子来让你可以用来拷贝。

更有趣的是，如果你在上面两个网页当中任何一个打开源代码看看，保证你会疯掉：源代码也已经反过来了……

但是，实际上，数据仍然是按照正常的顺序存在的，问题出在文本的渲染上面。

那么，如果所有的编辑器都能够follow Unicode的标准，那么我们怎么才能看到真正顺序的文本？这似乎成了一个悖论。

再感叹一下：I18N真的是个复杂问题……