ftofficer|张聪的blog

 
Splashtop a Rapid-Start Platform for Consumer PCs

不需要硬盘，不需要操作系统，直接固化在主板ROM里面的Linux、浏览器和Skype，这种机器在拥有网络连接的时候，究竟有多大的潜力？

嗯，很大。

部分翻译自 ISO C Standard Update

作者Arjun Bijanki是Visual C++编译器的test lead，而且是Microsoft在C标准委员会的代表。

C1x (0<=x<=9)将是下一个版本的C语言标准，ISO国际标准化委员会WG14，C Programming Language刚刚结束了在夏威夷的又一次半年会议，在会上委员会成员讨论了下一版本的C语言，非官方称为C1x的未来发展，参见这里。

对C程序员来说，整部文档都值得一看，但是希望在C1x当中的新的概念引起大家的注意：

12. Trust the programmer, as a goal, is outdated in respect to the security and safety programming communities. While it should not be totally disregarded as a facet of the spirit of C, the C1X version of the C Standard should take into account that programmers need the ability to check their work.
12. 信任程序员，从安全的编程角度上来说已经过时了。虽然说作为C的精神的一个重要方面这个原则并不应该被完全否定，但是C1x有责任给程序员一个检查自己工作的机会。

13. Unlike for C9X, the consensus at the London meeting was that there should be no invention, without exception. Only those features that have a history and are in common use by a commercial implementation should be considered. Also there must be care to standardize these features in a way that would make the Standard and the commercial implementation compatible.
13. 不像C9x，伦敦会议的一致意见是(在C1x当中)完全不应该有任何的新发明。只有经过历史考验和在商业实现当中得到广泛应用的特性才会被考虑。而且在标准化的时候需要注意和商业实现的兼容。

14. Migration of an existing code base is an issue. The ability to mix and match C89, C99, and C1X based code is a feature that should be considered for each proposal.
14. 对已有代码的升级是一个考虑方面。每一个提案都应该具有将基于C89, C99和C1X的代码整合的能力。

代码升级是毋庸置疑的重要 – 我甚至认为这是基本的需求。但是我发现另外两项更有意思。第12条反映了工业界在近10年来对于安全性方面的持续关注，委员会开始拥抱这个设想是非常伟大的。因此委员会在 TR 24731 (边界检查接口，包括了在VS 2005当中大多数_s系列的函数)上面的努力也就也不让人意外了。

委员会也要求编译器厂商提供它们被最广泛应用的语言扩展以便委员会考虑。在众多实现(例如Visual C++ 和 GCC)当中共享的很多特性，像扩展属性(extended attributes)和线程局部存储(thread local storage)，将被重点考察。还有一些情况，实现之前语法可能有区别，但是底层的概念是一致的。正如 #13所说，委员会会尽力去对他们保持兼容。

对于微软为什么没有在Visual C++当中完整的实现C99，Arjun Bijanki的解释是实现哪些功能是基于用户提出的需求的。根据用户的需求，Visual C++已经实现了可变长参数宏(variadic macros)，long long类型，__pragma, __FUNCTION__, 和__restrict。他希望能够听到更多来自C语言用户的需求，而且许诺会在明年4月份的下一次会议后给出关于C标准更进一步的更新。

http://code.google.com/edu/

互联网真是个好东西。

来自这里。

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进行通信？

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

http://www.news.com/8301-10784_3-9789901-7.html

Google is beefing up its outsourced e-mail offering aimed at
corporations and universities, adding security features that large
companies demand.

Three weeks after closing its acquisition of Postini, Google has
integrated the company’s security and government regulation services
into Google Apps Premier Edition. That suite includes hosted e-mail,
calendar, instant messaging, Docs & Spreadsheets and Web page
creation software.

Google的hosted application suite的确是一个非常有意思的创意。而现在其中加上了Anti-Spam和Anti-Virus的自定义，是不是看起来Google应该成为比Microsoft更大的一个安全行业的竞争对手了呢？

上面发的这个关于blog comment spam的文章被同样的人再次spam，而且正好被Ace的两个回复夹了三明治。实在让我郁闷了一把。

既然我不能对live space做什么让它不接收spam comment，那么我只能让我自己眼不见为净了。既然必须要我自己访问自己的blog的时候才会发现自己的blog是不是被spam了并且会手动删除上面的spam comment，那么我就把这个过程自动化好了。

基于GreaseMonkey好了。

先搭个架子，然后向里面填算法来判断这个comment是不是spam，目前的话，先基于关键字好了，看到那个叫做boubo的链接就删掉。

原来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真的是个复杂问题……

http://connect.microsoft.com/Phoenix

Phoenix is the code name for a
software optimization and analysis framework that is the basis for all
future Microsoft compiler technologies. The Phoenix framework is an
extensible system that can be adapted to read and write binaries and
MSIL assemblies and represent the input files in an IR, which can be
analyzed and manipulated by applications by using the Phoenix API. The
code can then be written in binary or JITable form for execution.

也许对于程序的沙盒化和程序分析有点用。

先推荐一下本月的TechNet Magzine文章：The Known DLLs Balancing Act。

请注意文章结束的地方，最后一行，关于Reymond Chen的介绍：

He has no idea what his T-shirt size is anymore.