Let’s see how to reach the goal by LINQ. -deep_blue(BLUE) @佛州华人论坛:佛州枫下论坛 The Rolia Forum of Florida

工作学习 / 学科技术讨论 / 求助，十年C++程序员，找了份C#的工作，被老婆鄙视工资低，极度郁闷中。现在征求一切C++，STL，BOOST，SQL，Linux BSHELL， Design Patterns，算法数据结构的面题。准备好好努力。同时，如果有公司需要C++高级程序员的，给个机会。 -oscargee(oscargee); 2010-6-23 (#6142231@0)

如果有人在C++上面有任何难题，需要帮助，我也愿意竭力相助。 -oscargee(oscargee); 2010-6-23 (#6142255@0)

Windows or Unix? Any VC? -thornthorn(Holy Moly); 2010-6-23 (#6142905@0)

no matter。我更希望做linux服务器上的编程。但是WINDOWS下的活我一样做。 -oscargee(oscargee); 2010-6-23 (#6142939@0)

Good 全活儿 -thornthorn(Holy Moly); 2010-6-23 (#6142978@0)

ＭＦＣ绝对不做。那是真正的垃圾。 -oscargee(oscargee); 2010-6-23 (#6143292@0)

呵呵，加拿大垃圾工收入不错。 -firetrain(火车头); 2010-6-23 (#6143352@0)
傻冒， MFC养活了好多人。 -tonyhao(tonyhao); 2010-7-10 (#6169548@0)

fire your LP first. -guanshui88(约定); 2010-6-23 (#6142304@0)

his lp push him up, what s wrong with it? he might start thinking fire her after his lp become satisfied. -c1xwy(洪兴罩俺去战斗); 2010-6-23 (#6142316@0)

请不要讨论这个问题。这里是事业板块。我只需要题目。 -oscargee(oscargee); 2010-6-23 (#6142325@0)

没人理我，我自己先贴一个征求答案，抛砖引玉。 -oscargee(oscargee); 2010-6-23 {410} (#6142388@0)
public class A
{
virtual void print( int a = 0)
{
cout << a << endl;
}
}
public class B : public A
{
virtual void print (int a = 1)
{
cout << a << endl;
}
}

int main( int argc, char* argv)
{
B* pb = new B();
A* pa = dynamic_cast<A>(pb);
pa->print();
}

这个题目大概大部分人都没有见过，难点在于缺省值在内存中的存储位置。谁能讲清楚？

Is this c++ code? I have to make a few changes to make it compile. -oceanwater(灌水日月长); 2010-6-23 (#6142545@0)

我随手写的，没有编译过，很显然第一行就应该加上#include<iostream>。只是一个意思，你熟悉C++的话应该能看懂。 -oscargee(oscargee); 2010-6-23 (#6142663@0)

完整编译版 -oscargee(oscargee); 2010-6-23 {341} (#6142681@0)
#include <iostream>

using namespace std;

class A
{
public:
virtual void print( int a = 0)
{
cout << a << endl;
}
};

class B : public A
{
public:
virtual void print (int a = 1)
{
cout << a << endl;
}
};

int main( int argc, char* argv)
{
B* pb = new B();
A* pa = dynamic_cast<A*>(pb);
pa->print();
}
嗯，我的完整编译版还不完整。 -oscargee(oscargee); 2010-6-23 {299} (#6142794@0)
应该在最后一行加上exit(0);

_exit 和 exit之间的区别是，_exit不做进程退出的收尾工作，属于从核心直接退出。而exit会回收进程资源。

如果你用atexit( Func); 定义一个退出函数的话，可以看到使用exit 退出时，该函数会被call，而使用_exit退出的话，这个函数不会被call。

擦把汗，还有细节要抠的话，请尽管来。

俺看不懂这些弯弯绕，不过怎么觉得像在讨论茴字的第五种写法。 -golfwood(Golf); 2010-6-23 (#6142859@0)

C++程序员就是要抠底层细节，因为我们的任务是写出最快的程序。我自己觉得自己只差直接写汇编了。这个和Java的特点不一样。但是，我认为C++有前途。因为现在的方向是云计算。当一万个用户联机进来的时候，JAVA很可能直接趴窝。 -oscargee(oscargee); 2010-6-23 (#6142885@0)
这些不是弯弯绕。打个可能不恰当的比方就是围棋里的骗招，平时最好不用，一旦遇上了也要知道如何对付。熟悉楼主提到的那些智能指针的代码才是正招，要认真学习。然后试着回答楼主的问题： -fang_yi2000(Tom); 2010-6-23 {280} (#6143366@0)
调用有缺省参数的函数代码是在编译时完成的（这也正是为什么缺省参数值必须在编译时可见）。虚拟函数的调用是在运行是完成的。所以pa->print();实际上可看成是像 B::print（A::0); 不知我说的对不对。因为我不能理解“难点在于缺省值在内存中的存储位置”，我感觉缺省参数类似于常量。这点请楼主指教。
在mac 上验证了一下，结果是0。虽然是OO, 但是代码和数据是分开的。编译器实际上在编译过程中指定用Class A 的 print，即使是在运行时动态 cast Class B 给A。实际上是Class A 的代码， Class B 的数据。实际效果和楼下“笨笨和旦旦”的写法一样。 -zzhang(zz); 2010-6-23 (#6143793@0)

exit(0)应该不用加。main()退出的时候会自动执行的。 -moonhalf(走啊走); 2010-6-23 (#6143774@0)

你说得很对，但是我觉得加的话，是一个很好的习惯。 -oscargee(oscargee); 2010-6-24 (#6143985@0)

For Windows programs, it is very bad. -liquid(豆泡松果之松果豆泡); 2010-6-24 (#6144119@0)

继续抠细节 -oscargee(oscargee); 2010-6-23 {803} (#6142862@0)
很显然，程序中没有释放掉指针。因为是单进程小程序，HEAP资源随进程退出而被回收，所以不是问题。
刚才在前面发现有人问，如何保证指针被释放？
答用内存池的话，我认为不完整。内存池的管理照样是麻烦，如果你不主动释放指针，内存池如何知道何时回收指针。

这个问题基本上还是针对Smart pointer。在STL中有一个auto_ptr，auto_ptr的特点是不能在拷贝后拥有指针。这是为了防止指针被递归引用。如果一个auto_ptr把自己带的指针复制给另外一个auto_ptr指针的话，那么这个auto_ptr就不指向任何对象。这个特点决定了auto_ptr不应该用于任何STL容器。因为STL容器的内部存在着对指针的复制。
boost::scoped_ptr 则正好相反，它的特点是不可以赋值。
boost::shared_ptr是个好东西，它可以被复制。所以它可以用于STL容器中。为了防止递归引用，它需要和boost::weak_ptr一起使用。weak_ptr是一个观察者，它不增加shared_ptr的引用计数。

还有其他的智能指针吗？
I am not sure what this is about. When I ran this code, it print out zero, which is expected, as A::print is a virtual function. What's the point here? -oceanwater(灌水日月长); 2010-6-23 (#6142874@0)

你不觉得它好像应该打印2吗？A的指针是从B cast出来的。它难道不应该执行B的override的函数吗？那好，如果我们不cast，直接用pb->print();打印的结果是什么？同一个指针啊。 -oscargee(oscargee); 2010-6-23 (#6142896@0)

I would say this is just the basic Polymorphism. If your questions is how Polymorphism implemented in c++, I would not spent time on it. -oceanwater(灌水日月长); 2010-6-23 (#6143093@0)

当然，这种题目看起来很变态。可是我向你保证，这是我所经历过的真题，薪水目标13万美元。我只不过是没有通过那次的面试。 -oscargee(oscargee); 2010-6-23 (#6143258@0)

我猜缺省值在代码里写死了，跟你Cast来Cast去无关。不信自己跟踪汇编看看。 -firetrain(火车头); 2010-6-23 (#6142876@0)

和CAST绝对有关。不信你把程序里的pa->print();改为pb->print();再运行一下，得到的就是不同的结果。 -oscargee(oscargee); 2010-6-23 (#6142980@0)

不知道为什么不能回，楼下，结果也是0。隐性CAST -oscargee(oscargee); 2010-6-23 (#6143232@0)

我试了pb->print()结果是1 -firetrain(火车头); 2010-6-23 (#6143315@0)

有时候不同的编译器得出的结果不同，你们应该统一平台 -binghongcha76(一只大猫); 2010-6-23 (#6143403@0)

嗯. 我用微软的不标准.... -firetrain(火车头); 2010-6-23 (#6143470@0)

猜猜这个的结果是什么？ -collapsar(笨笨和旦旦+Emma); 2010-6-23 {32} (#6143126@0)
A* pb2 = new B();
pb2->print();

0? -firetrain(火车头); 2010-6-23 (#6143287@0)

right -oscargee(oscargee); 2010-6-23 (#6143308@0)

这个compiler决定的。default parameters是compile-time决定的，virtual function是runtime决定的。 -baalinca(12.24_60.1); 2010-6-23 {127} (#6143321@0)
所以你调用pa->print，default parameters就是从A里来的；调用pb->print就是从B里来的。虚函数是runtime决定的，跟调用的形式没有关系。
It should be 1 -bugkiller(Driver Coding); 2010-6-27 (#6149921@0)
说句不中听的话，就冲“难点在于缺省值在内存中的存储位置”，您对C++的理解也就中等偏下水准 -manniangpai(慢两拍); 2010-10-6 (#6309903@0)

前阵有招CLI的，自己搜搜吧。纯玩C++真过时了。开发周期越来越短。。。 -firetrain(火车头); 2010-6-23 (#6142827@0)

C++可以做什么？ -oscargee(oscargee); 2010-6-23 {1406} (#6143080@0)
本文发表在 rolia.net 枫下论坛太多了。举一些简单的例子。比如我有一个股票，每天都有开盘收盘最高最低四个价格。写一个程序，分析二十年内该股票处于上升通道的区间和处于下跌通道的区间。两分钟内必须运算完成。交易员等着要数据。这个JAVA，C#基本上都是要趴窝的。再比如国内的天涯论坛，每天几十万个帖子，几万个用户同时在线。运算倒是不复杂，就是看贴回贴。这种运用也是可以用c++做的。用arpache肯定是不合算的啦。
再比如《阿凡达》，全实时光影计算，用java和c#是不可想象的。还有股票交易，每一秒钟几千个订单信息，必须在0.1秒内处理完毕，错过时机，损失算谁的？云备份，几万个用户上传文件，都是用c的。搜索引擎，不说了，百分之百的C/C++。手机服务器，同时为几万个手机用户提供天气预报。网络游戏，魔兽争霸光中国就有300多万玩家，每一个人发出的魔法都要被附近的玩家的电脑接受。所有的命令都要实时同步。每一个玩家的移动都要被计算，同步广播。用JAVA基本上也是MISSION IMPOSSIBLE。

当然，更不用说在嵌入式领域C语言的巨大运用了。比如IPHONE的XCODE，你用C的概念去学就比较快。比如CISCO设备，VXWORKS上面的编程。当然，这些还需要其他的专业知识，也比较难。

比较专业的软件，比如游戏引擎，比如PHOTOSHOP，比如腾讯QQ，比如医疗上的影像系统，比如好多好多你生活中要用到的软件，都是用C++开发的。

所以我对我的专业前景还是非常有信心的。随着云计算的推进，JAVA的弱点必定会逐渐暴露，巨大的系统开销，缓慢的运算速度，开源社区的逐渐远去。当然，JAVA也在进步，JAVA 也有前途。但是我相信C++的前景也是非常灿烂的。

我的梦想是在刀片机上做大规模并行计算。Dream啊。现实和梦想总还是有距离的。呵呵。更多精彩文章及讨论，请光临枫下论坛 rolia.net

这些能做，还找工作干啥，自己开公司挣大钱去，别的不说，做个成人阿凡达卖卖，那可大发啦。 -tjhong(啊哈); 2010-6-23 (#6143101@0)
FYI. The stock exchange throughput requirement is above 10K TPS, and round trip latency is at millisecond level instead of 0.1 sec. And there is a Java-based exchange running in Toronto, complied Java is not slower than C++. -york_region(york_region); 2010-6-23 {86} (#6143156@0)
But I don't think C# .Net can handle big systems. Microsoft platform is a limitation.

小小纠正一下：.NET 跟 Windows 无关。 -collapsar(笨笨和旦旦+Emma); 2010-6-23 (#6143161@0)

Only theoretically correct. Please give me some real example of .Net on other platform. -york_region(york_region); 2010-6-23 (#6143179@0)

MONO project started from 2004 putting .NET & silverlight on linux/Mac -goodtogo(journey); 2010-6-23 (#6143454@0)

Are most trading applications C/C++ based or JAVA base? -thornthorn(Holy Moly); 2010-6-23 (#6143168@0)

C/C++ based normally. -york_region(york_region); 2010-6-23 (#6143180@0)

I thought "am I wrong on that? " -thornthorn(Holy Moly); 2010-6-23 (#6143201@0)

What I meant was that Java is not slow and can do it. -york_region(york_region); 2010-6-23 (#6143212@0)

To certain extend. -thornthorn(Holy Moly); 2010-6-23 (#6143233@0)
+1, complied Java is not slower than C++, (with good OO) -ariso(ariso); 2010-8-23 (#6241932@0)

很抱歉我没有真地做过ＴＲＡＤＩＮＧ　ＳＹＳＴＥＭ。我大概说说：Linux下可能使用EPOOL+SOCKET来做连接的读写，或者用ＲＴＥＶＥＮＴ，不过这些都差不多级别。不见得太快，真要是考我，我就用VxWorks操作系统，全实时，还有更快的，来找我吧，我认输。 -oscargee(oscargee); 2010-6-23 (#6143266@0)

C#的JIT听说是很强劲。可是我并不相信。我曾经看到我同事初始化一个大数组，是往里面一个一个写数字。我不大相信你的编译器聪明到知道把这个东西变成块写。对于Ｃ＋＋程序员，写Ｃ恐怕是不花力气的吧。我们都是从Ｃ开始学编程的。 -oscargee(oscargee); 2010-6-23 (#6143270@0)

都说了不要比性能了。C#是用Lazy loading 初始化的。真需要用大数组说明算法本身有问题。 -firetrain(火车头); 2010-6-23 (#6143332@0)

性能方面当然是C++优先。可是现如今这行情谁还肯养着你慢慢优化性能？人还怕你Bug多没人接手呢。 -firetrain(火车头); 2010-6-23 (#6143323@0)

兄弟，这只是行业的不同。某些行业就是要性能的啊。抛开这个不谈，我比较自豪的是扎实的C++功底对我确实有帮助。 -oscargee(oscargee); 2010-6-23 {1055} (#6143362@0)
本文发表在 rolia.net 枫下论坛我记得有一段时间我公司缺人手，找我去帮忙维护他们的JAVASCRIPT网页，我看了半天，我就发火了。我实在忍不住啊，那写的叫什么啊？后来我自己写，写了大概有两个月吧。调来一个新的web developer，他接手以后，过了几个礼拜，跑过来说，你Javascript写的很好啊。我苦笑，从来没有写过。混的。

我这么说可能有点骄傲。不过真的，我没有怕过任何语言。其实我用过的语言，要都列出来，估计是一长串了。FOXPRO，i4gl，VB，VBA，powerbuilder，JAVA，C#，Javascript，Python，Objective C，SQL。当然，这些我都不会朝简历上写的。需要的时候抓过来写就是了。我也喜欢读哪些语言。比如JAVA，我的确读了SCJP的真题集。还是有所得。我在运用的时候也是集成的，比如我不喜欢MFC，常常抓了C#，三下五除二，干完UI，然后就用控件连C++了。这才叫高效。写引擎也是，上面用PYTHON，下面才用C++，商务逻辑，容易变的部分，当然是用高级语言划算。如果说，一个C++程序员，他居然写不了JAVA，那是天大的笑话。不过话说回来，Framework, 行业知识，设计习惯，这是另一个方面的问题了，在这个方面，我得向老JAVA程序员们学习。但是C++是功底，是我值得骄傲的部分，这个我也不隐瞒。我的简历上永远就是C++，我不会提我懂Javascript。因为那个不需要提。更多精彩文章及讨论，请光临枫下论坛 rolia.net

唉, 时代不同了. 就象机枪发明以后武功高手就只剩表演的份了...火云邪神能擒住子弹, 那是特例... -firetrain(火车头); 2010-6-23 (#6143491@0)

没有机关枪的时候，一个普通人手上的弩也能干掉武功高手；有机关枪的时候，女子防身术也有用武之地。当追求速度的时候，C++就自然用上了。 -moonhalf(走啊走); 2010-6-23 (#6143786@0)

既然这么牛X，你咋就找不到C++的工作呢？ -tonyhao(tonyhao); 2010-7-10 (#6169560@0)

相信你的C++水平一定很高, 不过你对高层技术比较外行. 事实上是世界上顶尖的网战象银行什么的, 都是J2EE系统, 当然它们是建立在MIDDLEWARE之上, 后者应该是C/C++做的. 还有股票分析的活, 现在我知道都是用DATAWAREHOUSE做的, 我不懂, 只知道不用写程序. -springtime(家住湖畔); 2010-6-25 (#6147063@0)

看看alexa流量前三的网站：google, facebook和youtube，你说它们后台是啥写的？ -moonhalf(走啊走); 2010-7-26 (#6198045@0)

看得我这个崇拜啊，不过，程序编的再好，不也就是一个编程序的吗？？ -jacky2001(beyond); 2010-7-27 (#6198131@0)

国内的面试题也很有意思。假设有10万条记录，请你找出重复次数最多的十条记录，5分钟内运行完成。算法题。 -oscargee(oscargee); 2010-6-23 (#6143004@0)

懒得算了，用LINQ吧，(10万条记录).GroupBy(s=>s).OrderByDesc(s=>s.Count()).Take(10) -binghongcha76(一只大猫); 2010-6-23 (#6143188@0)

呵呵，一台ＰＣ就能搞定的事情，您建议用数据库ＳＥＲＶＥＲ？ -oscargee(oscargee); 2010-6-23 (#6143206@0)

不好意思，态度不好，该打。这道题如果用到数据库的话，我觉得可能是： select top 10 from (select title, count(*) from records group by title order by count(*)) 楼下的mm，我觉得设计当然很重要。我回答在正文里面了。 -oscargee(oscargee); 2010-6-23 {254} (#6143250@0)
其实如果我今天是一个JAVA程序员的话，我绝对不会说自己语言掌握得多好。身为一个JAVA程序员，最重要的不是编程，而是行业知识。

我的悲哀在于我没有一个很好的行业知识，所以我需要选择一个行业，进去以后继续发展。

同时，我欢迎一切有关设计的题目，比如设计模式。

Why is "最重要的不是编程，而是行业知识" only applicable to Java programmers? -cca(不归的如来佛); 2010-6-25 (#6145857@0)

LOL -deep_blue(BLUE); 2010-6-23 (#6143439@0)

性能。。。 -firetrain(火车头); 2010-6-23 (#6143336@0)

性能不知道，不过再怎么用C++优化，很难说会比我这个速度提高5%？。但是有点小错误，应该是 (10万条记录).GroupBy(s=>s).OrderByDesc(s=>s.Count()).Take(10).Select(s=>s.Key) -binghongcha76(一只大猫); 2010-6-23 (#6143399@0)

一点浅见。这道题，如果用c++优化的话，速度可不是5％的提高，可能是50％，500％都不稀奇。 -oscargee(oscargee); 2010-6-23 {206} (#6143591@0)
你要知道，我只需要查询最多频率的10条，此外的无需排序。而一旦你用了order by，你就是在做全表排序。不要迷信数据库，有很多专用算法可以解决专门的问题。比如，这道题可以考虑堆排序。当然，我目前在设想更高速的排序。
OrderByDesc慢了点...我一直担心LINQ未曾优化, 否则别人搞数据库的咋挣钱... -firetrain(火车头); 2010-6-23 (#6143596@0)
我们原来没事瞎编程序玩 -baalinca(12.24_60.1); 2010-6-25 {272} (#6146056@0)
开平方的程序，因为要涉及到大数运算（可能有好几百位），一个用C和一般链表实现的，一个用的是C＋＋的运算符重载这些东西，速度差得非常之多，同一个数用C＋＋要等几秒钟，用C的就感觉没有等待的时间，如果用JAVA写，呵呵。高级语言维护起来方便些，但是一定会有额外的时间和资源上的开支的。

这只能说明你们的C++写得太差了。估计一堆copy constructor被调用 -moonhalf(走啊走); 2010-7-26 (#6198047@0)

qsort()然后再数一遍，时间复杂度NlogN+ cN. ？ -firetrain(火车头); 2010-6-23 (#6143346@0)
用perl一两行代码就能搞定，简单的hash -iambigcat(cat); 2010-6-25 (#6145739@0)

Another"一只大猫"! :-) Can you post your "two-liner"? -cca(不归的如来佛); 2010-6-25 (#6145858@0)

实际做个测试吧，保留生成随即字符串的代码，改写剩下的代码，看看谁能比我的这个写法更快？ -binghongcha76(一只大猫); 2010-6-25 {1286} (#6146250@0)
本文发表在 rolia.net 枫下论坛废话不多说，花了30秒，写了如下的程序，作为测试

static void Lab22()
{
string[] rawStrings = new string[] {"ww","oo","pp","sd","wertr","sddf"};
Random random = new Random();
// 生成10万条随机的string纪录，存到randomList中
var randomList =Enumerable.Range(1,100000).Select(s=>string.Format("{0}-{1}-{2}-{3}-{4}-{5}"
,rawStrings[random.Next(5)]
,rawStrings[random.Next(5)]
,rawStrings[random.Next(5)]
,rawStrings[random.Next(5)]
,rawStrings[random.Next(5)]
,rawStrings[random.Next(5)])).ToArray();

System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
sw.Start();
// 改写这一部分代码
var result = randomList.GroupBy(s => s).OrderByDescending(s => s.Count()).Take(10).Select(s => string.Format("{0},{1}",s.Key,s.Count())).ToArray();
sw.Stop();
Console.WriteLine(result);
// 显示运行消耗时间
Console.WriteLine(sw.Elapsed.TotalMilliseconds);
}

我的机器运行时间105毫秒，这还是我没有开启.net并行运算，我不太明在即使再优化还能怎么快？再快估计时间会倒流了，呵呵更多精彩文章及讨论，请光临枫下论坛 rolia.net

你把字串写成个文件，传上来，然后大家用各种语言写出来程序比结果，应该很有意思。有一点肯定的，用C／C＋＋30秒钟绝对写不出来的，30分钟也够呛。 -baalinca(12.24_60.1); 2010-6-25 (#6146301@0)

大猫说的是运行时间３０秒吧，快和慢是结构（architecture)上的因素,应该用同样的算法同样的机器，看看用.NET和C＋＋库，到底块多少？ -tjhong(啊哈); 2010-6-25 (#6146847@0)

“花了30秒，写了如下的程序”。 -baalinca(12.24_60.1); 2010-6-25 {393} (#6146893@0)
我刚刚准备用c写个试试，for loop里面套个for loop空转十万次，什么都没作已经快二十秒了，不知道他那个怎么实现的，是不是时间函数不对？

t1 = clock();
for( register int i = 0; i < 99999; i++ )
for( register int j = i; j < 100000; j++ )；
t2=clock();

cout<<(t2-t1)/CLOCKS_PER_SEC<<endl;

输出是19秒，而且随机产生的字串每次都是不同的，基本上每两个字串都要比至少一次，不太可能是毫秒级的时间。

你这不叫算法，叫死做。 -tjhong(啊哈); 2010-6-25 (#6146931@0)

这是最差的情况好不好？下周我有时间写个玩玩。 -baalinca(12.24_60.1); 2010-6-25 (#6146950@0)

既然是算法，肯定要做预先处理分类的，比如把第一个字符相同的分为一类，第一个字符都相同就拿第２个字符分...，你说的最差情况是我们有１０万个不同字符，每个字符长度为１０万，这就分不出类了。 -tjhong(啊哈); 2010-6-25 (#6147003@0)
我写了一个，在我机器上要花46秒。谁再写个看看。 -baalinca(12.24_60.1); 2010-6-25 {5512} (#6147123@0)
本文发表在 rolia.net 枫下论坛#include <iostream.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

typedef struct _RANDOM_STR_
{
int count;
union{
char str[12];
int number[3];
};
}RandomStr;

#define MAX_COUNT 100000
#define MAX_STR_LEN 12
#define INVALID_STR (-1)
#define TOP_TEN 10

RandomStr* pTop[TOP_TEN];

void addtotop( RandomStr* pTempStr, int start = -1, int end = -1 )
{
if( pTop[TOP_TEN-1] == NULL)
{
// first 10 times
for(int i = 0; i < TOP_TEN; i++)
{
if(pTop[i] != NULL && pTop[i]->count < pTempStr->count)
{
RandomStr* pTemp1 = pTop[i];
pTop[i] = pTempStr;
pTempStr = pTemp1;
} else if( pTop[i] == NULL )
{
pTop[i] = pTempStr;
break;
}
}
}
else if( start == -1 )
{
// 11th
if( pTop[TOP_TEN-1]->count < pTempStr->count )
{
addtotop(pTempStr, 0, TOP_TEN-1);
}
}
else
{
int i = (start + end) / 2;
if( 1 == end - start )
{
if( pTempStr->count > pTop[start]->count )
{
i = start;
}
else
i = end;

for( int j = TOP_TEN-1; j > i; j--)
{
pTop[j] = pTop[j-1];
}
pTop[i] = pTempStr;
}
else
{
if( pTempStr->count > pTop[i]->count )
{
addtotop(pTempStr, start, i);
}
else
{
addtotop(pTempStr, i, end);
}
}
}
}

char getarandomchar()
{
int i = ((double)rand() / (RAND_MAX+1) ) * 61;
char achar;
if( i >= 0 && i <= 9 )
{
achar = '0'+i;
}
else if( i >= 10 && i <= 35 )
{
achar = 'A' + i - 10;
}
else
{
achar = 'a' + i - 36;
}
return achar;
}

void createRandomString(char* pStr)
{
int iStrlen = (double)rand() / (RAND_MAX+1) * 7 + 5;
int i;

for( i = 0; i <= iStrlen; i++)
{
*pStr++ = getarandomchar();
}

for( ; i < MAX_STR_LEN; i++) *pStr++ = '\0';
}

void main(void)
{
RandomStr* pStr = new RandomStr[MAX_COUNT];
RandomStr* pTempStr = pStr;
RandomStr* pTempStr2;
clock_t t1, t2;
register int i, j;

srand( (unsigned)time( NULL ) );

for(i = 0; i<MAX_COUNT; i++)
{
pTempStr->count = 1;
createRandomString(pTempStr->str);
pTempStr++;
}

for( j = 0; j < 10; j++)
{
pTop[j] = NULL;
}

memset(pStr+10000, 0 ,sizeof(RandomStr)*10);
(pStr+10000)->count = 1;
strcpy((pStr+10000)->str, "test10th");
strcpy((pStr+10001)->str, "test10th");
strcpy((pStr+10002)->str, "test10th");
strcpy((pStr+10003)->str, "test10th");
strcpy((pStr+10004)->str, "test10th");
strcpy((pStr+10005)->str, "test10th");
strcpy((pStr+10006)->str, "test10th");
strcpy((pStr+10007)->str, "test10th");
strcpy((pStr+10008)->str, "test10th");
strcpy((pStr+10009)->str, "test10th");

memset(pStr+20000, 0 ,sizeof(RandomStr)*9);
(pStr+20000)->count = 1;
strcpy((pStr+20000)->str, "test9th");
strcpy((pStr+20001)->str, "test9th");
strcpy((pStr+20002)->str, "test9th");
strcpy((pStr+20003)->str, "test9th");
strcpy((pStr+20004)->str, "test9th");
strcpy((pStr+20005)->str, "test9th");
strcpy((pStr+20006)->str, "test9th");
strcpy((pStr+20007)->str, "test9th");
strcpy((pStr+20008)->str, "test9th");

memset(pStr+30000, 0 ,sizeof(RandomStr)*8);
(pStr+30000)->count = 1;
strcpy((pStr+30000)->str, "test8th");
strcpy((pStr+30001)->str, "test8th");
strcpy((pStr+30002)->str, "test8th");
strcpy((pStr+30003)->str, "test8th");
strcpy((pStr+30004)->str, "test8th");
strcpy((pStr+30005)->str, "test8th");
strcpy((pStr+30006)->str, "test8th");
strcpy((pStr+30007)->str, "test8th");

t1 = clock();
pTempStr = pStr;

for(i = 0; i<MAX_COUNT-1; i++)
{
if(pTempStr->count != INVALID_STR)
{
pTempStr2 = pTempStr+1;
for(j = i+1; j < MAX_COUNT; j++)
{
if( pTempStr2->count != INVALID_STR)
{
if( pTempStr->number[0] == pTempStr2->number[0]
&& pTempStr->number[1] == pTempStr2->number[1]
&& pTempStr->number[2] == pTempStr2->number[2] )
{
pTempStr->count++;
pTempStr2->count = INVALID_STR;
}
}
pTempStr2++;
}
}
pTempStr++;
}

pTempStr = pStr;
for( i = 0; i < MAX_COUNT; i++)
{
if( pTempStr->count != INVALID_STR)
{
addtotop(pTempStr);
}
pTempStr++;
}

for( i = 0; i < TOP_TEN; i++)
{
cout<<pTop[i]->count<<":"<<pTop[i]->str<<endl;
}

t2 = clock();

cout<<t2<<":"<<t1<<":"<<CLOCKS_PER_SEC<<":"<<(t2-t1)/CLOCKS_PER_SEC<<endl;

delete [] pStr;
}更多精彩文章及讨论，请光临枫下论坛 rolia.net

我如果把比较两个字串换成C标准函数strcmp，就要70多秒才完成。 -baalinca(12.24_60.1); 2010-6-25 {201} (#6147138@0)
if( pTempStr->number[0] == pTempStr2->number[0]
&& pTempStr->number[1] == pTempStr2->number[1]
&& pTempStr->number[2] == pTempStr2->number[2] )

换成

if （!strcmp(pTempStr->str, pTempStr2->str))
这样没法比较，所以我们要统一输入参数。我建议你用我的那段生成随机字符串的程序生成10万个字符串存入磁盘，再用你的C++程序做处理计算时间，这样才能比较优劣 -binghongcha76(一只大猫); 2010-6-25 (#6147155@0)

随机生成字串那段时间是没算在内的。 -baalinca(12.24_60.1); 2010-6-25 (#6147169@0)
家里没有环境，等我星期一写成文件，再比。我怀疑你排序之前已经有预处理了，预处理时间没算在内。 -baalinca(12.24_60.1); 2010-6-25 (#6147183@0)

排序算法的速度，普通的是O(N＊N)，如冒泡法，最快的排序法是O(N ＊ Log N)，如快速排序法. 你的例子类似冒泡法，大猫利用了.Net framework 提供的排序法，19 秒 vs 105毫秒是可能的。 -zzhang(zz); 2010-6-25 {171} (#6147320@0)
实际速度是 19 / 0.105 ~= 200 倍,

理论上是 100000* 100000 /(100000 * log 100000) ~=6000 倍, 但加上.net frame work 的消耗，机器速度的差别，6000倍降低到 200倍是完全可能。

没有排序，我只是统计了每个字串出现的频率，复杂度最差的情况是99999+99998+...+1，然后再挑出来重复最高的前10个，用的也是快速排序，但是要移动字串，这里可以改进成内存块拷贝或者链表。 -baalinca(12.24_60.1); 2010-6-25 {104} (#6147421@0)
而且我那个只是空循环，什么操作都没有做，就用了19秒。我怀疑.net是插入数据的时候已经排好了序或者预处理了。

你的是两重循环，工作量和冒泡法相当。大猫的例子中没加Index, 排序在order by 时进行，例子是正确的。 -zzhang(zz); 2010-6-25 (#6147591@0)

我礼拜天抽空写了一个算法 -oscargee(oscargee); 2010-6-26 {537} (#6147951@0)
但是没有办法和大猫的比较。因为我发先.net读文件是有cache的。第一次读和第二次不同。操作系统内部的事情，不管他。他groupby+orderby在我的测试文件中花费39毫秒。我的order by 是1毫秒。剩下38毫秒不知道能不能及时group by，因为暂时找不到合适的hash库。用stl的需要480毫秒，那个是红黑树做的。

group by 的优化我暂时只想到hash，没有特别好的主意。 order by的优化很简单，做一个链表，只比十次，如果count值比10个排在最前面的值都小，就扔掉，比下一个。否则，则插入。

最坏情况下是O(10＊n)次比较，要比qsort在一般情况下的O(log 2 n) 快。最坏情况下当然更快。

没有，写程序的时间30秒，运行时间105毫秒，真的是很快 -binghongcha76(一只大猫); 2010-6-25 (#6147152@0)

Great typist! You likely have broken the world record of typing speed.:-) -cca(不归的如来佛); 2010-6-25 {90} (#6147510@0)
With the same exaggeration, you could probably achieve the fastest sorting -- by hand. :-)

VS 中的编程提示很有效，加上是快手，再用上 Ctrl-C 和Ctrl-V,是完全有可能的， -zzhang(zz); 2010-6-25 (#6147604@0)

我想通了怎么回事了，你这个程序是有6个子串随机排列组合成一个大字符串，一共有720个组合。用C写个跟你一模一样功能的程序，1）预定义720个串，每个串有一个对应的计数，2）随机从中挑选一个串同时增加该串的计数，3）重复210万次， -baalinca(12.24_60.1); 2010-6-28 {251} (#6150306@0)
4）这个720预定义串按照计数排序并打印前十个。这样做根本没有字串的比较，最后对计数排序也只有720个元素，一定会比你的快的。我前面那个程序是10万个完全随机的字串，没有一点投机取巧的余地，所以是完全不同的东西。我因为不懂C#，所以一开始没明白你的程序什么意思。

Somebody woke up finally :) -liquid(豆泡松果之松果豆泡); 2010-6-28 (#6150422@0)

这个问题我早看出来了，所以我自己搞了一个测试文件。不过就算是全部用真实的URL填充，C#仍然挺快，这个不得不承认。十万条记录的量还不足以暴露C#的问题。十亿条大概才行。呵呵。 -oscargee(oscargee); 2010-6-28 (#6150439@0)

老大，我那不是6!，是6的6次方种组合，应该是46656种组合方式 -binghongcha76(一只大猫); 2010-6-28 (#6150465@0)

即使这样，不到5万个和十万个不同字串排序有很大差别的，我把我上面的程序改成只生成46656个字串，只需要9秒了。而且我可以更进一步优化，用index0-5来代替你这几个子串，只需要4bits，用一个DWORD就足够了，我不需要存储字符串，排序的时候也按照DWORD来排，只要比较一次， -baalinca(12.24_60.1); 2010-6-28 {352} (#6150615@0)
再改成快速排序，我相信最后时间会更短。

C＃再聪明它是按照字串处理的，你的字串长度是12－24，用标准字串比较函数，一次比较4个字符，至少要比较3次，最多要6次，而且如果字串长度不是4的整数倍，还要更多。程序不是变魔术，没有可能快的。

BTW你有没有在你的机器上运行一下我那个程序，看看有多少秒？我的机器挺老的，咱们的结果是在两台机器上运行，本身也没有可比性。
我试了试是挺快的，还在想是怎么回事。 -baalinca(12.24_60.1); 2010-7-2 (#6157355@0)

如果是算法考题的话，要看记录的类型，如果是记录都是数值型的，可以开一个数组统计，只要遍历一边10万条记录就行了。如果是记录是字符串，应该用hash表来统计，相当于遍历一边10万条记录的字符总长度总和。 -szbeginner(Beginner); 2010-6-29 (#6153295@0)
大家讨论得很热烈。不过大家好像没注意10万条记录的大小。题目中可没说their size is less than memory size. 如果10万条记录的大小是100G甚至于1000G呢？同学，ext sort可不是好玩的。要不用LINQ试试？我有点怀疑LINQ 能不能做ext sort。 -ejbeqhouse(ejbEqHouse); 2010-10-8 (#6312352@0)

小女子一点浅见，请勿见笑。 -jasmine8gu(Jasmine); 2010-6-23 {430} (#6143160@0)
初学编程，语言的细节掌握得越深入越好。随着经验的增加，就应该转到系统设计，逻辑设计上面去了。我们都知道各种计算机的语言，要素基本都差不多，数据类型，结构，运算优先级，分支，判断，等等，还有就是这种语言的库函数，支持object概念的各种实现。写程序尤其不要用某种语言的很特殊的feature，因为平台移植性不好。我曾将openoffice移植到iphone手机上，未经大的改动，从application层以下，基本都能运行，其平台兼容性令人大为叹服。

就冲你移植oo到iphone，你的技术能力比这里夸夸其谈的大老爷们强太多了 -goodtogo(journey); 2010-6-23 {76} (#6143446@0)
大部分coder是做buesiness applicatoin的，手低眼低，处于食物链的底层而不自知。

过奖过奖。 -jasmine8gu(Jasmine); 2010-6-23 {191} (#6143502@0)
可惜做完了之后发现启动速度太慢， openoffice本身的启动速度之慢是众所周知的，估计投到市场上面反响不会太好，所以没有发布出去。不知道哪位有什么想法可以起死回生，不然投入的时间和精力太可惜了。

发布给app store与其charge 1.99$不如做好文档，开个blog,把效果录下来放youtube上 -goodtogo(journey); 2010-6-23 {139} (#6143560@0)
，主动说明效果性能不佳，但是approach会让很多人感兴趣。

这样可以扬名立万，有人或机构对你这个package感兴趣，做training,收取consulting fee.

非常感谢你的建议, 听起来挺可行的. -jasmine8gu(Jasmine); 2010-6-24 (#6145188@0)

Agree. 以后程序都会转给民工去做。想提高就该转移重点了。 -newid123(昵称); 2010-6-25 (#6146941@0)

There should be some C++ job opportunities in capital market area. Try to contact some big job agents. -york_region(york_region); 2010-6-23 (#6143164@0)

谢谢，我希望能多做题目。然后有把握拿工作。 -oscargee(oscargee); 2010-6-23 (#6143208@0)

check PM pls -york_region(york_region); 2010-6-23 (#6143281@0)

with T as ( select distinct id, count(id) over (patition by id,...) as rows from mytable ) select top 10 id from T order by rows -spj(spj); 2010-6-23 (#6143476@0)
I have one: what is "operator new" and "new operator"? How can you write a class to make its objects can be instantiated at given addresses? -liquid(豆泡松果之松果豆泡); 2010-6-23 (#6143734@0)

new是一个操作符号，可以被重载。这大概就是你的问题吧。重载new我不常用，但是new在指定的地址上很常用new(address value) Class(); 如果你用内存池，同时存储的是对象的话，就会用到。 -oscargee(oscargee); 2010-6-24 (#6143992@0)

My note 1: many C++ questions posted here are exactly the reason many people prefer C over C++: C compiler will not generate hidden code like C++ compiler does, C is kind of a WYSIWYG language. -liquid(豆泡松果之松果豆泡); 2010-6-23 (#6143778@0)

c is not, after you start playing function pointers -moonhalf(走啊走); 2010-6-23 (#6143789@0)
这个问题不是这么看的。我解释在正文里。 -oscargee(oscargee); 2010-6-24 {642} (#6144018@0)
如果说速度，C当然要比C++快。用纯C的地方也很多，嵌入式，操作系统很多都是用C写的。但是C++是重要的，那就是因为OO。学习C++是一个学习OO的过程。我说句实话，我当年的转型很痛苦，从面向过程的C，转到面向对象的C++，我大概花了一年多。一开始就是不习惯，不习惯用OO的观点来看世界。后来转过来了，豁然开朗。

现在我再看JAVA, PYTHON，C#，基本上再没有困难了。这些语言一边读，一边我就能想到他们的底层实现。唯一C做不到而JAVA能够做到的东西就是reflect，这个和他们的运行机有关。当然，其实C也不是真的做不到，只不过没有现成的方式而已。当然，C#和JAVA实现了很多的设计模式，比如Delegate, Decorate, Iterator等等等等。这很好。不过C++的库也很不少。如果想用的话，也是有的。

After you use C++ for another several years, you may ask yourself: do I really need those features provided by C++? Does it worth it compared with the potential risks? OO is a concept, not a feature of C++, same to iterator, delegate etc. -liquid(豆泡松果之松果豆泡); 2010-6-24 (#6144126@0)

写一个曾经失败的面试过程 -oscargee(oscargee); 2010-6-24 {737} (#6144051@0)
曾经去面试过一家公司，先上来做网上考试，我记得我得了90分。然后就出了一道编程题目，就是实现内存池。要求以最快速度实现内存的存取。我做的时候，特意写了一封信去问他们，是否需要实现自动内存扩展。他们回信说，我们对这个没有限制，只需要完成我们要的功能。OK，我就写了一个固定大小的内存池去了。结果FAIL，回信说我没有实现内存的可扩展。这大概是我这辈子经历过的最郁闷的一场面试吧。

其实内存池是一个非常需要特定场景的设计。固定大小也绝不是不可接受，自动扩展，每一次扩大一半？翻倍？难道那就一定合理吗？数据库的库文件也有同样的问题，SYBASE好像每次不够了就翻倍。那只不过是人家假设可以翻倍。如果硬盘不够呢？如果根本不需要那么大呢？

所以找工作，一半是水平，一半是运气，碰到一个面试官不负责任，相信一个十年C++程序员会不懂得自动扩展内存池的，无话可说。

俺觉着，你 fail 绝不是这个原因。 -wincity(toad 会英文的红卫兵); 2010-6-24 (#6144064@0)

Anyway，过去了。这是个EMAIL面试，原因都说得很清楚，我不相信是因为我的着装，谈吐，根本连面都没有见过。就是碰到鬼了。 -oscargee(oscargee); 2010-6-24 (#6144075@0)

看到你天天抠这些算法等小节。。。咳。。。 -guanshui88(约定); 2010-6-24 (#6144073@0)

欢迎大节的面试题。 -oscargee(oscargee); 2010-6-24 (#6144080@0)

面试就是面试，你出的考题是考试（考初入门者的），这种题考试本身就是小看被面试者，一般刚毕业的大学生可能要比工作十年的人算法好多了。。。我现在就会IF语句和加一减一的算法。。。 -guanshui88(约定); 2010-6-24 (#6144089@0)

三年前我和你想得一样，奈何人家就是喜欢出这种题。这些题目都不是我出的，都是我经历过的面试中的。你有什么办法？是我们去适应市场还是市场来适应我们？ -oscargee(oscargee); 2010-6-24 (#6144096@0)

面试的时候提这种问题的都是编程序的weirdo，可能平时同事也觉得他厉害，他也自大惯了，很得意自己的技术，其实他自己也是搞了很久才搞明白怎么回事，呵呵。如果你“不经意的”答对了，是很加分的。 -baalinca(12.24_60.1); 2010-6-24 (#6144213@0)

How do you manage complexity? -wincity(toad 会英文的红卫兵); 2010-6-24 (#6144196@0)

谢谢，这题目我这里很少见，我试着回答，请指教。 -oscargee(oscargee); 2010-6-24 {927} (#6144275@0)
Yes, complexity is a big problem in business. Normally we manage it by design and by developement methodology. By design means we try to seperate business logic and low level module as possible. And we also try to abstruct io logic to prepare platform changes. We wrote business logic with high level languages like Java or C#, so that it can be changed as soon as possible. I also used existing framework and tools as possible to prevent unnecessary developement.

We are using Agile method to develope our software. Which means we release software very oftenly. So user can see the progress and they can try to use them. Once they find problem, they notify our product manager and he will arrange change schedule very quickly. Testing and developing are running together, bugs will be found in very short time. Developers have scrum meeting everyday and they can know what needs to be changed or new ideas from the meeting.

你说了这些，老实说，还不如老佛爷的三个字。你没有给point，却给了一大堆细节。不少细节似乎跟主题无关，如SCRUM，or most of your 2nd paragraph. -wincity(toad 会英文的红卫兵); 2010-6-24 (#6144480@0)

That's why I need to post this topic. I have no idea where to learn these. Divid and conquer is simple, but I could failed in this pointer. I do appreciate your help. It can open a door for me. -oscargee(oscargee); 2010-6-24 (#6144501@0)

面试时，对大节问题，要先给point，后给details。面试的人要的，往往只是points。我在写一些有关communication的文章，见链接。#4 and #5 就是讲的这个问题。 -wincity(toad 会英文的红卫兵); 2010-6-24 (#6144559@0)

This is absolutly right. The point is what if I had no point? That's why I need to learn and read. I have read many books but not including "Divide and conquer" stuff. Where do you get it? -oscargee(oscargee); 2010-6-24 (#6144589@0)

Any software engineering book would discuss it? One great book which I read many years ago and which still jumps into my mind frequently is called "Large-Scale C++ Software Design" by John Lakos. -wincity(toad 会英文的红卫兵); 2010-6-24 (#6144607@0)

Thanks a lot. I downloaded the PDF -oscargee(oscargee); 2010-6-24 (#6144615@0)
640页，估计要看两个星期了。呵呵。老大，再给点书单吧。看得出你搞的东西和我要找的方向完全一致。 -oscargee(oscargee); 2010-6-24 (#6144644@0)

Can you send the pdf file to me? I can only download the 10 pages related to content. Thanks. My email is shuibo08@yahoo.com -shuibo08(shui); 2010-8-8 (#6217260@0)

Divide and conquer. -cca(不归的如来佛); 2010-6-24 (#6144423@0)

Thank you, it is an important way. -oscargee(oscargee); 2010-6-24 (#6144434@0)
还是老佛爷厉害。 -wincity(toad 会英文的红卫兵); 2010-6-24 (#6144460@0)

如果是招senior，还靠考这样的题目来决定结果，那这种公司不去也罢。刚毕业的除外。 -xiaojinshu(小金鼠); 2010-6-24 (#6144122@0)

如果是应聘编程的职位，答错了楼主说的缺省参数的这个C语言的问题，说明对C／C＋＋了解不全面，其实实际中完全可以不用缺省参数的，或者干脆去应聘manager，architect或者是跟customer打交道的职位等等等等，说不定挣得还更多一些。 -baalinca(12.24_60.1); 2010-6-24 (#6144178@0)

Coding是软件工程中最没技术含量的工作。 -szs11(Hedge); 2010-6-24 (#6144144@0)
真有本事自己找就行了（指技术+communication skills）；写的东西让人看了很不舒服，更不用说给你机会了。 -qq234(QQ); 2010-6-24 (#6144193@0)

请多指教，如果你真的觉得我不好，我可以删贴。我只是想求一点面试题目，结果很多人就来批评我的题目。如果有好的题目的话，不管哪方面的，我都欢迎啊。 -oscargee(oscargee); 2010-6-24 (#6144215@0)

One suggestion for you, change your mind to English, no "内存池" "回收指针" ...then you will get a better job -vicky2005(孩子她爹); 2010-6-24 (#6144286@0)

Good suggestion. Thank you. I will use English in interview. -oscargee(oscargee); 2010-6-24 (#6144292@0)

Not only in interview! Get used to think in English for all those terms, instead of thinking in Chinese and translating them when speaking -vicky2005(孩子她爹); 2010-6-24 (#6144359@0)

Sure no problem. So now I am speaking memory pool, resource collection, pointer .... -oscargee(oscargee); 2010-6-24 (#6144394@0)

Very good point. -wincity(toad 会英文的红卫兵); 2010-6-24 (#6144483@0)
这个要求很扯淡。 -szs11(Hedge); 2010-6-24 (#6144576@0)

有一个新题目，非常有意思，题目很简单。Declare a method that accept one file name and try to find path of the file. 只需要写一行字，就是方法的定义。 -oscargee(oscargee); 2010-6-24 (#6144722@0)

有多个path 咋办？这得整个目录路经里循环递归去找。 -tjhong(啊哈); 2010-6-24 (#6144771@0)

牛，上来就发现问题了。这道题目老少皆宜，但是绝对不好做。基本上属于接口设计。不要求具体实现，只要求接口定义。因为要写完整的程序很麻烦也没有必要，面试的时候只考你一行。 -oscargee(oscargee); 2010-6-24 (#6144780@0)

Print all possible subsets of a set. (10 minutes) -lionel(Lionel); 2010-6-25 (#6147347@0)

思路是： Select s , count(*) into table2 from table1 group by s, 再 select s from table 2. 用 LINQ 实现。大猫可以在一分钟内用 .net 把它写出来。 -zzhang(zz); 2010-6-25 (#6147361@0)

这是一个算法问题，没有数据库。 -lionel(Lionel); 2010-6-25 (#6147389@0)

.net 有data table, 在内存里，LINQ 可将SQL 实现。你可以看一下大猫在上面的贴的例子。 -zzhang(zz); 2010-6-25 (#6147406@0)

俺不懂.net，不知道用SQL可以打印出subset来。用c/c++, java之类的解决这个问题不难。这是我曾遇到过的一道面试考题(地点在finch west)，从题量上来看，大约10分钟解题比较合适。从你说的s,count(*)看来就不像是正确的结果。假如set是{a,b,c}，那么需要打印出： -lionel(Lionel); 2010-6-25 {47} (#6147434@0)
{}
{a}
{b}
{c}
{a,b}
{a,c}
{b,c}
{a,b,c}

无任打印在屏幕上还是别的打印，打印多慢啊。 -tjhong(啊哈); 2010-6-25 (#6147467@0)

打印在内存里，程序能看见也行 -zzhang(zz); 2010-6-25 (#6147479@0)
没办法，这是面试题，人家就是考算法。忘记那家公司的名字了，他们主要用C/C++。偶在第二轮面试被刷了。 -lionel(Lionel); 2010-6-25 (#6147482@0)

相当于时间都耗在路上了。 -tjhong(啊哈); 2010-6-25 (#6147491@0)
如果是限定在C/C++, 除非前几天刚做过类似的题，或是内线给通风报信，一般十分种内很难给出好的答案。 -zzhang(zz); 2010-6-25 (#6147496@0)

换了我直接放弃 -oscargee(oscargee); 2010-6-26 {40} (#6148104@0)
十分钟，打字大该都来不及。这个题不好想。

这道面题不难的。C/C++语言本身的重要性远不如数据结构以及算法的。正如前面有人提到的：不要去抠编程语言上的某些特性。现在我面试别人的时候，一般也就是问问数据结构和算法方面的问题。 -lionel(Lionel); 2010-6-26 (#6148641@0)

算法当然是很重要的，上面说divide & conquer 其实就是qsort的核心思想。推而广之，可以用在很多场合。不过这道题我之前没有见过。当场想的话，要想对很难。有时间当然好，没有时间先放弃的就是这个题目了。 -oscargee(oscargee); 2010-6-27 (#6148770@0)

There was no performance requirement though. -cca(不归的如来佛); 2010-6-25 (#6147562@0)

因为前面刚讨论了10万个字串的那道题，加上你第一次的题目没限定语言和集合的类型，Select s,count(*) 应该是一种解。 -zzhang(zz); 2010-6-25 (#6147519@0)

如果是十万张照片呢？ -oscargee(oscargee); 2010-6-26 (#6147962@0)

Easy. -cca(不归的如来佛); 2010-6-25 {365} (#6147558@0)
Assume the member count is n.

Each subset can be represented by the binary form of a number between 0 - 2^n.

Each member can be represent by the binary form of one of these numbers: 2^0, 2^1, ..., 2^(n-1).

Loop through the "subset" numbers, "binary AND" with each "member" number to determine whether that member is part of the subset.

That's it.

如果有十万个member, 你不就惨了吗？ -zzhang(zz); 2010-6-25 (#6147574@0)

Why? Are you OK?:-) -cca(不归的如来佛); 2010-6-25 (#6147576@0)

why not? -zzhang(zz); 2010-6-25 (#6147579@0)

那时候恐怕宇宙都沉寂了。 -lionel(Lionel); 2010-6-25 (#6147582@0)

先看一下，这道题的应用价值是什么？ -zzhang(zz); 2010-6-25 (#6147616@0)

Possibly land you the job.:-) -cca(不归的如来佛); 2010-6-25 (#6147617@0)

如果是这样的话，那个job 只需要初级C/C++ 程序员。一定还有更实际的应用。 -zzhang(zz); 2010-6-25 (#6147625@0)

:-) -cca(不归的如来佛); 2010-6-25 {134} (#6147640@0)
如果是限定在C/C++, 除非前几天刚做过类似的题，或是内线给通风报信，一般十分种内很难给出好的答案。 -zzhang(zz); 22:29 (#6147496@0) reply
卡，这种题目，没见过的，给半个钟头你也未必能想到。见过的，一钱不值。所以要多做题。题海战术依然有效。没办法，这就是社会需求。 -oscargee(oscargee); 2010-6-26 (#6148116@0)

"题海战术"? How many more "ten years" do you have? Poor aptitude is curable; poor attitude is fatal. Sorry for sounding too harsh. -cca(不归的如来佛); 2010-6-26 (#6148126@0)

So what's your suggestion? -oscargee(oscargee); 2010-6-26 (#6148152@0)

You are so cute. :-) -cca(不归的如来佛); 2010-6-25 (#6147585@0)

sick -zzhang(zz); 2010-6-25 (#6147605@0)

Take care then.:-) -cca(不归的如来佛); 2010-6-25 (#6147613@0)

I'm not OK. code please. The loop is not easy. -oscargee(oscargee); 2010-6-26 (#6148106@0)

Haven't written code for ages -- I typically design/program by email:-), and sorry can't bother my team for this. There is nothing special on the loop -- not worth chewing any more, really. -cca(不归的如来佛); 2010-6-26 (#6148114@0)

Got it. You did it by yourself? If you did, please accept my respect. I will need more questions. -oscargee(oscargee); 2010-6-26 (#6148115@0)

这也是我解题的思路 -lionel(Lionel); 2010-6-25 {51} (#6147592@0)
我觉得他们主要的考点就在于理解subset并灵活使用bit。

如果是这样的话，应该是 2的n 次方才对。从0 开始到 2＊＊n －1 的二进制显示。处理10 万个member的程序的也应该能写出来，至于能不能执行完毕那是另外一回事。 -zzhang(zz); 2010-6-25 (#6147644@0)

写程序要考虑实际的。当时我用了unsigned long，n>32就完蛋了。如果用java，long可以处理到63位，基本上就足够了。 -lionel(Lionel); 2010-6-26 (#6147970@0)

As I read, the question was not about capacity nor performance. Over-interpretation of requirement introduces "feature creep" that would hurt you instead of help you in the interview.:-) -cca(不归的如来佛); 2010-6-26 {275} (#6148087@0)
Since the size of the set was never specified, you can never tell how much is enough -- regardless what.

A gentlement above challenge me with a size of 100K -- I would say he could go further and give 10 billion and laugh, but it's just not relevant at all.

Have fun.

这道题更象是数学题，集合论。和C++ 更不相干。如果和performance 无关，为什么要和C++ 搅合在一齐。出这道题的目的，出题者应该解释一下。 -zzhang(zz); 2010-6-26 (#6148366@0)

"....算法数据结构的面题。准备好好努力。"#6142231@0 -lionel(Lionel); 2010-6-26 (#6148625@0)
数据结构和算法的C++实现。想用数据库、SQL，不是不对，而是和出这种题的公司不匹配了。 -moonhalf(走啊走); 2010-7-26 (#6198041@0)

这道题很有趣，忘了我前面说的。 -zzhang(zz); 2010-6-25 (#6147578@0)

Never remembered any ways. :-) -cca(不归的如来佛); 2010-6-25 (#6147581@0)

递归调用，要考虑堆栈溢出问题，64甚至128级应该没有问题。 -baalinca(12.24_60.1); 2010-6-28 (#6150655@0)

大概这样。 -baalinca(12.24_60.1); 2010-6-28 {567} (#6150703@0)
#define MAX_SET 8
＃define MAX_LENGTH 1024

void subsets(char* prefix = "", int start = 0; int end = MAX_SET)
{
char *pTemp = new char[MAX_LENGTH];
if(pTemp != NULL )
{
for(int i = start+1; i<MAX_SET; i++)
{
if(start!=0)sprintf(pTemp, "%s,%d", prefix, sets[i]);
else sprintf(pTemp, "%s%d", prefix, sets[i]);
cout<<pTemp<<endl;
subsets(pTemp, i, MAX_SET);
}
｝
delete [] pTemp;
}

void main(void)
{
for(int i =0; i< MAX_SET;i++) sets[i]=0;
subsets();
}

＃define的后面漏了一行int sets[MAX_SET]; 我设成256级让它跑，一顿饭吃完了到现在还在打印，lol -baalinca(12.24_60.1); 2010-6-28 (#6150772@0)

再看看又发现几个错误和可以改进的地方。现在写程序准确性不好，以前没有计算机用，都是先在纸上写好，就没有这么多错。 -baalinca(12.24_60.1); 2010-6-30 {587} (#6154859@0)
#define MAX_SET 8
＃define MAX_LENGTH 1024
int sets[MAX_SET];

void subsets(char* prefix = "", int start = 0)
{
char *pTemp = new char[MAX_LENGTH];
if(pTemp != NULL )
{
for(;start<MAX_SET; start++)
{
if(start!=0) sprintf(pTemp, "%s,%d", prefix, sets[start]);
else sprintf(pTemp, "%d", sets[start]);
cout<<"{"<<pTemp<<"}"<<endl;
subsets(pTemp, start＋1);
}
delete [] pTemp;
}
}

void main(void)
{
for(int i =0; i< MAX_SET;i++) sets[i]=i;
subsets();
}

英文不好，这道题翻译成汉语是什么意思？ -binghongcha76(一只大猫); 2010-6-28 (#6150781@0)

就是一个集合，打出来所有可能的组合。比方说｛1，2｝结果是｛1｝，｛1，2｝，｛2｝，以此类推。 -baalinca(12.24_60.1); 2010-6-28 (#6150790@0)

感觉这个题目应该没有特别的时间空间要求，就是递归或者回溯法解决。10分钟写出程序来是难点。类似的写程序题在微软和google的面试一般是要求30分钟，在白板上书写，一边写一边说思路，要尽量没有语法错。 -szbeginner(Beginner); 2010-6-29 (#6153285@0)
Let’s see how to reach the goal by LINQ. -deep_blue(BLUE); 2010-6-30 {1311} (#6154092@0)
本文发表在 rolia.net 枫下论坛List<List<int>> Subset(List<int> OrignalSet)
{
IEnumerable<List<int>> basicSet = new List<List<int>>(OrignalSet.Distinct().Select(i => new List<int>() { i })); // Fiter out dups and create a basic set
List<List<int>> result = basicSet.ToList();
List<List<int>> tempSet;

List<string> keys = result.Select(i => i.ToString()).ToList();

List<int> temp;
basicSet = basicSet.ToList();

for (int j = 1; j < basicSet.Count(); j++ )
{
tempSet = new List<List<int>>();
foreach (List<int> item in result.Where(i => i.Count().Equals(j)) )
{
foreach (List<int> basicItem in basicSet)
{
if (!item.Contains(basicItem.First()))
{
temp = item.Union(basicItem).OrderBy(i =>i).ToList();
if (!result.Contains(temp) && !tempSet.Select(l => l.Select(i => i.ToString()).Aggregate((f, s) => f+s)).Contains(temp.Select(i => i.ToString()).Aggregate((f,s) => f+s)))
{
tempSet.Add(temp);
}
}
}
}
if (tempSet.Count > 0)
{
result.AddRange(tempSet.Distinct());
}
}
result.Add(new List<int>()); // Add an empty item
return result;
}更多精彩文章及讨论，请光临枫下论坛 rolia.net

不懂c#没大看懂，效率怎样？用递归函数处理16个subsets要600多毫秒（只在内存中生成，不打印到屏幕），32个就要很长时间了。 -baalinca(12.24_60.1); 2010-6-30 (#6154886@0)

It only takes 197 ~ 218 milliseconds in 16 elements loop. -deep_blue(BLUE); 2010-7-2 {1170} (#6156831@0)
本文发表在 rolia.net 枫下论坛Using previous method, it’s rather time consuming. After changing it to new one, It only takes 197 ~ 218 milliseconds in 16 elements loop.

However, Stack overflow happens in 32 elements loop.

New one:
List<List<int>> Subset(List<int> OrignalSet)
{
IEnumerable<List<int>> basicSet = new List<List<int>>(OrignalSet.Distinct().OrderBy(i => i).Select(i => new List<int>() { i }));
List<List<int>> result = basicSet.ToList();
List<List<int>> tempSet, tempSet1;
List<int> temp;
basicSet = basicSet.ToList();
tempSet1 = result;
for (int j = 1; j < basicSet.Count(); j++)
{
tempSet = new List<List<int>>();
foreach (List<int> item in tempSet1)
{
foreach (List<int> basicItem in basicSet.Where(i => !item.Contains(i.First()) && i.First() > item.Max()))
{
temp = item.Union(basicItem).OrderBy(i => i).ToList();
tempSet.Add(temp);
}
}
if (tempSet.Count > 0)
{
result.AddRange(tempSet);
}
tempSet1 = tempSet;
}
result.Add(new List<int>()); // Add an empty item
return result;
}更多精彩文章及讨论，请光临枫下论坛 rolia.net

我装了个C＃，在我烂机器上要花1026ms左右。 -baalinca(12.24_60.1); 2010-7-2 (#6157353@0)

Wow, you are real genius, can learn .NET in just one day. -deep_blue(BLUE); 2010-7-5 {1203} (#6159793@0)
本文发表在 rolia.net 枫下论坛Since you have .NET environment, you can try my new code. It is two time faster than previous one.

List<List<int>> Subset(List<int> OrignalSet)
{
List<int> basicList = OrignalSet.Distinct().OrderBy(i => i).ToList();
List<List<int>> basicSet = new List<List<int>>(basicList.Select(i => new List<int>() { i }));
List<List<int>> result = basicSet;
List<List<int>> tempSet, tempSet1;
int count = basicList.Count;
tempSet1 = result;
for (int j = 1; j < count; j++)
{
tempSet = new List<List<int>>();
foreach (List<int> item in tempSet1)
{
for (int l = basicList.FindIndex(m => m.Equals(item.Last())) + 1; l < count; l++)
{
tempSet.Add(item.Union(basicSet[l]).ToList());
}
}
result.AddRange(tempSet);
tempSet1 = tempSet;
}
result.Add(new List<int>());
return result;
}

BTW, to run the code, at least, you need following name spaces
System.Linq
System.Collections.Generic

You may also need manualy to set reference System.Data.DataSetExtensions更多精彩文章及讨论，请光临枫下论坛 rolia.net

哪里就会了。我只是copy&paste一下，发现debug的环境甚至热键都是一样的。 -baalinca(12.24_60.1); 2010-7-7 (#6164148@0)

试着解答 -bobo123(bobo123); 2010-7-2 {824} (#6156592@0)
算法一：
n 是集合的个数
它的子集个数是
Cn(0) + Cn(1) + .. + Cn(n-1) + Cn（n） = 2的n次方

其中上面的cn(i) 表示从n个元素当中选取i个 (i = 0, 1, 2, --- n-1, n), 同时Cn(i) = cn(n-i), 在得到从你n个元素中i个元素的结果，同时也可以得到选择n-i元素的结果
这样做一循环
for (i = 0; i <= n/2; i++)
{
// 打印从n里选取i 和 n-i 个元素
print_subset(n, i)
}

print_subset(n, i) 算法不再细述，大致是用一个一唯数组和几个变量进行堆栈的操作，可以完成。

算法二:
需要磁盘空间，除非n 很小可以把结果放在内存里，算法很简单。
n = 2, 假设它的集合是{1, 2}
那么它的子集是{}, {1}, {2}, {1,2}
把这个结果打印并以文件形式存放在磁盘上

当n = 3时, 集合是{1, 2, 3} ，它的子集将是n=2每个子集里添上3 + n=2 的所有子集。但打印时只需把新的子集打印出来，并把新的子集结果存放在磁盘

n = 4 同理类推

具体的程序在10分钟里很难实现。
google "Print all possible subsets of a set. (10 minutes) ", in 10 minutes, found this -interview(intervieweree); 2010-8-23 (#6242291@0)

？ -tonyhao(tonyhao); 2010-6-26 (#6147926@0)
说说你工资到底有多底？别告诉我们12W ：）））））））） -tonyhao(tonyhao); 2010-6-26 (#6147931@0)

很低，不好意思说。 -oscargee(oscargee); 2010-6-26 (#6148108@0)

打个比方，你脑袋里C++的就象是一把刀，磨的再快，但你不会耍，白费功夫。要么懂linux kernel，要么懂bussiness logic，哪怕是背一背tcpip illustrated, 也比在这摆忽C++挣得多 -obd2(obd2); 2010-6-26 (#6148122@0)

说得好啊，我就是想找一个行业，去搞搞business logic. -oscargee(oscargee); 2010-6-26 (#6148129@0)

说说你有多郁闷，还有能力和老婆同房吗？ -tonyhao(tonyhao); 2010-6-26 (#6148133@0)

做人要厚道。 -fang_yi2000(Tom); 2010-6-28 (#6150353@0)

明摆着是个显摆贴儿，你还跟着彭臭脚，可悲啊。 -tonyhao(tonyhao); 2010-6-29 (#6152091@0)

我搞不懂你们这些人，真的。请问我到底是显摆我的收入了，我的职位了，还是我的房子了？显摆？倒是有东西可以给我显摆。 -tonyhao(tonyhao); 2010-7-10 (#6169565@0)

看完贴，严重鄙视你老婆！说说你老婆工资有多高？ -superc(超级C); 2010-6-28 (#6150384@0)

失业 -tonyhao(tonyhao); 2010-7-10 (#6169561@0)

you are really good from your skill set. -newdog2(oo); 2010-6-29 (#6152946@0)
工作中技术是一方面，但更重要的是与人沟通的能力和personality。如果一个人老觉得自己比别人强，那么要么去特牛的公司或自己开公司，要么就是找到工作就不错了。 -haoxia74(winter is fun); 2010-6-29 (#6153564@0)

楼主就是一个干活的技术人员。啥细致工作都要做的。 -jacky2001(beyond); 2010-7-27 (#6198132@0)

楼主问我，他显摆什么了？我告诉你，你在显摆你的头脑和意识。 -tonyhao(tonyhao); 2010-7-10 (#6169568@0)

我不同意你这种说法。前面的技术问题我没有全部看完，因为这些技术细节对我有些生疏了。但是我能理解的是，人的大脑有不同类型的思维趋向，没有十全十美面面俱到的趋向，所以在讨论时要注意理解他人的特质。 -mayer(难得糊涂); 2010-7-26 {200} (#6197995@0)
有些人就是热衷于技术上的细致，有些人善于把握结构，有些人容易理解陌生行业的作业流程，不同类型的人有不同的位置需要，不能以一种趋向来驳另一种趋向，你可以提示他向其它方向延展，但是否能做得到就不是强求的。

Test: char *cp; explain the precessing sequence: *cp++; why? -healthy321(Keep Fit); 2010-10-8 (#6312412@0)
好久没有上rolia，今天看到贴子，不得不给你几个主义。 -dababa(1212); 2010-11-28 {1335} (#6386872@0)
本文发表在 rolia.net 枫下论坛看起来你的技术水平不错，但是太拘泥与技术本身了。一切技术，哪怕再先进，都是要为解决问题而存在的。离开了应用，技术本身什么都不是。
关于你所贴的这些问题都是一些小trick，说实话，没有贬低你的意思，我根本看不上。 C++中，using default argument is not good, if some one wrioe this way in interview, I woulnt't hire him.

我也是从C++开始，MFC， standard c++, STL, ATL, boost, rougewave 都很熟悉。后来是 .net，java。.Net 我个人来看比较适合于写desktop application, but not suitable for server application. Java is the opposite, not good for desktop app (SWT is better though).

这些技术上的细节你背的再多也不能帮助你找到好工作，关键是你做过什么类型的项目，是如何解决实际问题的。

至于性能，C++和JAVA这个话题估计永远也谈不完。各有各的说法。我的看法是在特定应用下compiled java比c++快，因为java为你管理如何分配与释放内存。C++如果不用memory pool，性能不如JAVA。在纯数学计算上，两者不相伯仲。IO C++要比JAVA快。
这些都是次要的，在大部分情况下，程序运行慢是因为developer没有进行适当的优化或者使用了错误的data structure。

关于面试，我所做过的题目都是非常简单的，初级程序员都能够做，半个小时就搞定。大部分时候都是聊天。

写了这么多，我对你的建议是

1。English
2。掌握一定的business knowledge
3。忘掉技术细节，提高自己对项目的总体设计能力
4。提高和人沟通的能力

最后祝你好运找到好工作。如果你能做到以上几点的话，12W在多伦多不是问题。更多精彩文章及讨论，请光临枫下论坛 rolia.net

@Florida

Let’s see how to reach the goal by LINQ.

Replies, comments and Discussions:

More Topics