屋顶上的木帷幕

Coding Problems

(C/C++) Find the common ancestor of two nodes in a tree

(C/C++) Partially revert a linked list

(C/C++) Exchange the odd and even nodes in a linked list

(SQL) Delete the post and the whole sub tree

posted on 2005-10-13 17:47:00 by mvm  评论(0) 阅读(384)

Exchange Nodes

Problem: Exchange the odd and even nodes in a linked list.

Given a "head" pointer to a linked list. You are asked to write a C/C++ function to exchange the odd and even nodes in the linked list. For example:

Please follow the type and function definitions below:

typedef struct _Node
...{
    int value;
    struct _Node* next;
}Node;

void ExchangeNodes(Node** phead) //note: phead is of Node** type
...{
    //your code here.
}

[The End]

posted on 2005-10-13 17:37:00 by mvm  评论(0) 阅读(1953)

Find Common Ancestor

Problem: find the common ancestor of two nodes in a tree

Given a "tree" pointer pointing to the root node of a tree and the other two pointers to two nodes in the tree. You are expected to write a C++ subroutine to find the common ancestor of the two nodes. In any unexpected condition, your code should return null pointer and avoid crashing.

For example, if the tree is like below, B is the common ancestor of E and G; A is the common ancestor of H and F; D is the common ancestor of D and G.

You are allowed to use recursion but as few as possible. You are NOT allowed to use STL. Please follow the type definitions shown below:

//tree node type
typedef struct _Node
...{
    char value;
    struct _Node* left;
    struct _Node* right;
}Node;

class CommonNodeFinder
...{
    //add any auxiliary code here as you wish.
public:
    inline Node* FindCommonAncestor(Node* tree, Node* node_1, Node* node_2)
    ...{
        //your code here.
    }
}

[The End]

posted on 2005-10-13 16:01:00 by mvm  评论(0) 阅读(2662)

Google热会降温的

上个月，微软推出了Microsoft Gadgets，立即在苹果社区里面遭到mac fans的大肆嘲笑：“雷蒙德的软件巨人将再次打开他的复印机，这次的对像是Dashborad Widgets”，尽管Apple的Dashboard其实也不过就是从Konfabulator抄袭来的——这一点人尽皆知。而且，在其他方面，Apple也不是那么干净的。Apple引以为豪的iPod播放器同时触犯了Microsoft和Creative的各一项专利：微软的Auto playlist generation with multiple seed songs (20030221541)，创新的Automatic hierarchical categorization of music by metadata (6,928,433)。

微软一直给人以“抄袭者”的印象，而且批评者总是可以列出长长一串微软收购来的产品的清单：PowerPoint (1987年), Visual SourceSafe (1994年), Frontpage (1996年), Hotmail (1997年), WebTV (1997年), Visio (1999年), Age of Empires (2001年), Virtual PC (2003年), ...。但在这个行业里，哪个大公司不收购，哪个公司不买别人的技术？Cisco和GE就不用说了；IBM的五大产品线DB2、Websphere、Lotus、Tivoli和Rational里，Rational和Lotus都是收购来的；Google收购Pisca，Adobe收购了Macromedia，eBay收购Skype，等等。但唯独Microsoft背上了“复印机”的恶名。

我们读书的时候，每个班上通常都有这么一个同学，功课很好，人也很善良，也愿意和大家一起打球吃饭，但总是成为大家嘲笑和开玩笑的对象。很多年来微软好像就一直扮演了这么一个形象——干得很好、干得很认真、做的东西也很好，却总是背着一些坏名声，例如：靠抄袭和收购开发产品，靠垄断获得利润，靠捆绑赢得竞争，产品落后且漏洞百出。

事实是，微软是一家积极创新的公司。不用列举一堆实例，且看Boston Consulting Group今年的Innovation 2005调查报告，BCG向全球68个国家各主要行业的940名高级管理管理人员（都是CEO、COO、President等级别的）发放了调查问卷，调查结果显示，“Executives ranked Apple, 3M, GE, Microsoft, and Sony as the most innovative companies”。

调查结果中，Google比去年上升15位，排在第八。Google正处于和公众关系的蜜月期中，头上顶着耀眼的光环，在公众的眼里，Google是和Apple一样富有创新精神的公司，很多人对Google顶礼膜拜（当然顺便也用鄙视的目光看了一眼微软）。

昨天CSDN转载了王建硕的《微软的过去和Google的宿命》，下面的评论中有人这么说：“Google每推出一个产品，几乎都是代表了当今最优秀的的技术，Google的每一个产品，都力求做到最好”。我觉得，Google的能力被夸大了。事实上，Google也并没有在每个产品上做到最好。例如：

• Google Talk：远远不如MSN Messenger、Yahoo! Messenger和Apple iChat。不支持WebCam，不支持Emotion，对话窗口不能用Ctrl+Space呼出系统菜单。对中文的支持还特别差，当输入满一行文字时，如果下一行第一个字是中文字，例如“文(wen)”，"w"是输入不进去的。Google Talk简直就是一个半成品。
• Google Reader：太简单的界面，用了一些客户端脚本的效果，除此以外实在没感觉Google Reader有什么过人之处。我仍然继续用NewsGator Web Edition来读朋友们的Blog，用My Yahoo来读各个新闻和专业网站的RSS Feed。

就算Google出了Google OS，难道Google OS能够做的比Linux、Mac OS X和Windows Vista都要好？就算Google出了传言中的Google Media Player，又能如何。Apple有QuickTime，Real有Real Player，ZDNet上还有各种形形色色的播放器，难道Google真的就能做的比这些所有的都要好？我不相信。

Google热会降温的。

--

The posts on this weblog are provided "AS IS" with no warranties, and confer no rights. The opinions expressed herein are my own personal opinions and do not represent my employer's view in any way.

posted on 2005-10-13 11:05:00 by mvm  评论(60) 阅读(8787)