Twitter
Facebook
Flickr
RSS
Find missing number in 4 billinon 32 bit integers
Oct272008Problem
Given a file with 4 billion 32bit integers, how do you find an missing integer from the file? In other words, which integer didn't show up in this file? You are given only 16MB memory.( not using external sorting)
solution
Like 3 bits. Suppose my list has 0, 1, 2, 3, 4, 6, 7. (sorted for convenience of explanation, but that's not a requirement)
000
001
010
011
100
110
111
Now count the bits:
number of bits from most significant to least significant bit position:
zeros: 4 3 4
ones: 3 4 3
Since the most-significant bit position is missing a 1, the middle bit position is missing a 0, and the least-significant bit position is missing a 1, we get this number to fill in the gaps:
101, or 5 decimal.
code
#include <iostream>
#include <fstream>
using namespace std;
int main() {
unsigned int number;
int bits[2][32] = {0};
ifstream numbers_file;
numbers_file.open("numbers.txt");
int i = 0;
numbers_file >> number;
while( ! numbers_file.eof()) {
for (i =0; i<32; i++){
int shifted = number>>i;
int bit = shifted % 2;
bits[bit][i]++;
}
numbers_file >> number;
}
unsigned int missing = 0;
for (i =31; i> -1; i--){
if(bits[0][i]>bits[1][i]) missing++;
missing = (missing<<1);
}
cout << "missing number is " << missing << endl;
}
面试很热门的抛鸡蛋问题
分析
Q: 只给你二个鸡蛋，你能上100层楼，你想知道鸡蛋的硬度。鸡蛋可能很硬或很脆弱，如果鸡蛋从第m层掉下而没破裂，而从第m+1层掉下就破裂了，那么这个鸡蛋的硬度就是m。你需要找出这个m和在最坏情况下最少试验次数。(经典鸡蛋问题)
A: 计算机学生可能会首先用第一个鸡蛋做二分搜索(O(logN))再用第二个递增做线性搜索（O(N)），最后必将用线性搜索结束因为用第二个鸡蛋时你无法确定最高一层。因此，问题变为如何使用第一个鸡蛋来减少线性搜索。
于是如果第一个蛋破裂在最高点我们要扔x-1次并且我们必须从x层高扔第一个蛋。现在如果第一个蛋的第一次扔没有破裂，如果第一个蛋在第二次扔破了我们要扔x-2次第二个蛋。假如16是答案，我需要扔16次才能找到答案。来验证一下是否可以从16层开始扔，首先从16层扔如果它破裂了，我们尝试所有其下的楼层从1到15；如果没破我们还能扔15次，于是我们将从32层(16+15+1)再扔。原因是如果它在32层破裂我们能尝试其下所有楼层从17到31最坏扔第二个蛋14次（总共能扔16次了）。如果32层并没破，我们还剩下能扔13次，依此类推得：
1 + 15 16 如果它在16层破裂，从1到15层最坏扔15次第二个蛋
1 + 14 31 如果它在31层破裂，从17到30层最坏扔14次第二个蛋
1 + 13 45.....
1 + 12 58
1 + 11 70
1 + 10 81
1 + 9 91
1 + 8 100 在最后我们能轻易地做到因为我们有足够多扔的次数来完成任务
从上表我们能看到最佳的一个在最后一步将需要0次线性搜索。
能把上述规律写为: (1+p) + (1+(p-1))+ (1+(p-2)) + .........+ (1+0) >= 100.
令1+p=q上述式子变为q(q+1)/2>=100,对100解答得到q=14。
扔第一个蛋从层14，27，39，50，60，69，77，84，90，95，99，100直到它破裂，再开始扔第二个蛋。最坏情况只需14次。
代码
设计一个状态f[i][j]，表示有i层楼j个鸡蛋，最坏情况下要扔鸡蛋的次数。
由于一个鸡蛋扔下去就只有破和不破两种可能，所以状态转移就是f[i][j] = min(1+max(f[k-1][j-1], f[i-k][j]))，(1 <= k <= i)。如果要构造出一个可行解的话，稍微修改一下代码，记录下路径就应该可以了吧。
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
const int MAXN = 1001; // change it to the number you want
const int MAXM = 1001;
int n; // the number of floors
int m; // the number of eags
int f[MAXN][MAXM]; // the result
void init()
{
memset(f, 0, sizeof(f));
for (int j=1; j<MAXM; j++)
{
for (int i=1; i<MAXN; i++)
{
if (j == 1)
f[i][j] = i;
else{
for (int k=1; k<=i; k++)
{
int tmp = 1+max(f[k-1][j-1], f[i-k][j]);
if (f[i][j]==0 || f[i][j]>tmp)
f[i][j] = tmp;
}
}
}
}
}
int main()
{
init();
printf("Hey cin n, m\n");
while (scanf("%d%d", &n, &m) != EOF)
printf("%d\n", f[n][m]);
return 0;
}
Nvidia took my first Interview of life
Oct212008This is a phone interview, i really feel excited about it:-), i hope i could get a pretty offer from such an amazing company!
Understanding reference counting with Objective C
Oct192008Let's start with retain and release; autorelease is really just a special case once you understand the basic concepts.
In Cocoa, each object keeps track of how many times it is being referenced (specifically, the NSObject base class implements this). By calling retain on an object, you are telling it that you want to up its reference count by one. By calling release, you tell the object you are letting go of it, and its reference count is decremented. If, after calling release, the reference count is now zero, then that object's memory is freed by the system.
The basic way this differs from malloc and free is that any given object doesn't need to worry about other parts of the system crashing because you've freed memory they were using. Assuming everyone is playing along and retaining/releasing according to the rules, when one piece of code retains and then releases the object, any other piece of code also referencing the object will be unaffected.
What can sometimes be confusing is knowing the circumstances under which you should call retain and release. My general rule of thumb is that if I want to hang on to an object for some length of time (if it's a member variable in a class, for instance), then I need to make sure the object's reference count knows about me. As described above, an object's reference count is incremented by calling retain. By convention, it is also incremented (set to 1, really) when the object is created with an "init" method. In either of these cases, it is my responsibility to call release on the object when I'm done with it. If I don't, there will be a memory leak.
Example of object creation:
NSString* s = [[NSString alloc] init]; // Ref count is 1
[s retain]; // Ref count is 2 - silly
// to do this after init
[s release]; // Ref count is back to 1
[s release]; // Ref count is 0, object is freed
Now for autorelease. Autorelease is used as a convenient (and sometimes necessary) way to tell the system to free this object up after a little while. From a plumbing perspective, when autorelease is called, the current thread's NSAutoreleasePool is alerted of the call. The NSAutoreleasePool now knows that once it gets an opportunity (after the current iteration of the event loop), it can call release on the object. From our perspective as programmers, it takes care of calling release for us, so we don't have to (and in fact, we shouldn't).
What's important to note is that (again, by convention) all object creation class methods return an autoreleased object. For example, in the following example, the variable "s" has a reference count of 1, but after the event loop completes, it will be destroyed.
NSString* s = [NSString stringWithString:@"Hello World"];
If you want to hang onto that string, you'd need to call retain explicitly, and then explicitly release it when you're done.
Consider the following (very contrived) bit of code, and you'll see a situation where autorelease is required:
- (NSString*)createHelloWorldString
{
NSString* s = [[NSString alloc] initWithString:@"Hello World"];
// Now what? We want to return s, but we've upped its reference count.
// The caller shouldn't be responsible for releasing it, since we're the
// ones that created it. If we call release, however, the reference
// count will hit zero and bad memory will be returned to the caller.
// The answer is to call autorelease before releasing the string. By
// explicitly calling autorelease, we pass the responsibility for
// releasing the string on to the thread's NSAutoreleasePool, which will
// happen at some later. The consequence is that the returned string
// will still be valid for the caller of this function.
return [[s autorelease] release];
}
I realize all of this is a bit confusing - at some point, though, it will click. Here are a few references to get you going:
* Apple's introduction to memory management.
* Cocoa Programming for Mac OS X (3rd Edition), by Aaron Hillegas - a very well written book will lots of great examples. It reads like a tutorial.
* If you're truly diving in, you could head to Big Nerd Ranch. This is a training facility run by Aaron Hillegas - the author of the book mentioned above. I attended the Intro to Cocoa course there several years ago, and it was a great way to learn.
9 Tips for the aspiring Emacs playboy
Oct082008Introduction
I consider myself a beginning Lisper. I've been developing my software in Emacs for 8 months now. At first, I was clumsy at it. Emacs can be difficult and daunting. The terminology is different from what I'm used to, the key bindings are different, and there are just so many commands, configurations, and modes. But I've persevered and I now find myself quite nimble with key bindings and structured editing. And yet there's still more to learn.
The subject of what to learn is treated in many online tutorials and printed books. But here, now, I thought I'd share some tips I use to keep the key bindings in my head from being garbage collected.
1. Post up a cheat sheet
Create your own cheat sheet with ten key bindings you'd like to learn. No more than 10. Don't burden yourself with a gigantic list you'll have to search through. You won't be able to find them quickly enough, and you'll stop referring to the sheet.
Make it a point to use bindings from the cheat sheet while you code.
At first, your cheat sheet will have the basic commands you need to master. But it will evolve as you do . . .
2. Don't use the mouse
The mouse is a crutch for the beginner. It will keep you from learning keyboard commands. Using the keyboard will let you edit faster than the mouse ever can.
Get rid of the tool bar (tool-bar-mode -1) and the menu bar (menu-bar-mode -1).
Don't touch the mouse. If you find yourself using the mouse too much, open up emacs in a terminal instead of in X. When you find yourself reaching for the mouse, think of a way to use the keyboard to get to where you want. In no time, you'll be flying around the text like a crazy rocket-powered hamster on steroids instead of some wimpy mouse.
3. Read other people's .emacs file
Lots of people post their .emacs file for bragging/demonstration purposes. These often have great tips/insights into a configuration/mode that you didn't know about. This is like getting a look directly into the brain of an experienced Emacs user. Cut and paste and read the comments.
4. Write down any interesting commands you discover
While perusing help, reading .emacs files, loitering in the newsgroups, or surfing the web, you'll invariably find an Emacs command that you'll want to remember. You won't remember it unless you write it down. Sure, you may remember some, but not all. Keep a list of key bindings you don't want to forget. You will not be able to find it again.
5. Update your cheat sheet
Ok, so you've got a cheat sheet. Now what? After a week or two of using a single, ten item cheat sheet, go through the sheet and decide which key bindings you've graduated from.
For each item on you cheat sheet, ask yourself these questions:
Do you use it often enough not to forget it?
Do you want to forget it?
Will you remember it without the cheat sheet?
Do you remember what it does?
When you've whittled down your sheet so that it again contains only those key bindings that you want to remember but don't, add some more from the list of interesting commands you've been keeping. But don't exceed a total list size of ten!
6. Keep your key bindings standard
There are a lot of key bindings that are universally accepted as standard. When you're still learning, you won't know which those are, and you'll destroy any chance you have of fluency in another Emacs window if you change them. There's nothing worse than sitting down at a terminal and being totally lost with the commands because you're used to rebinding most of them. You might even do something awful.
It's like being parachuted into a foreign country where "Hello, I come in peace." means "Your mother is ugly but she's good in bed." But at the same time, you might use some commands so much you want to rebind them to something more useful. It's a dilemma but I suggest keeping as many of the original key bindings as possible, especially at first.
7. Use help
Online help is a great help (wow, really bad pun). Some help commands that you might find helpful (not again):
- describe-key (C-h k): Asks you to strike a keystroke and describes the command it is bound to.
- describe-bindings (C-h b): Lists all of you key bindings.
- command-apropos (C-h a): Search all of the commands in the system, and gives you a brief description of each matching command(with its key binding).
- view-order-manuals (C-h RET): View all help commands
Also, watch when you you type a command using M-x. If there is a key binding for it, it will tell it to you.
8. Experiment
In order to strengthen the human-Emacs symbiotic bond, you should experiment with different editing commands and editing modes. Most text editors only offer a couple of ways of navigating text. Here are some common ones: Arrow Keys, Home/End keys, PageUp/PageDown, and find. One of the strengths of Emacs is that you can treat the same text differently depending on what command you use. For instance, you treat it as characters with C-f and C-b. But you treat it as words with M-f and M-b. You treat it as s-exprs with C-M-f and C-M-b. Etc.
In order to know when it is best to use which command, experimentation is your best option. Try out different commands and learn their strengths and weaknesses.
9. Create keyboard macros
Keyboard macros are a great thing to learn in their own right, but they can help you learn commands like a pro. When recording your macros, you have to think: "How can I do this so that this command will work perfectly a hundred times?". The thought process you have to go through to compose those commands will reinforce all of the possible ways to perform an action.
王泛森院士-如果让我重做一次研究生.
Oct052008如果让我重做一次研究生......
在所里碰到刚从美国读完博士回来的同事，
献什么？」……
一、研究生与大学生的区别
首先跟大家说明一下研究生和大学生的区别。
造新的知识，
是恭喜你对人类的知识有所创新，因此授予你这个学位。」
新，这个创新或大或小，都是对于普遍的知识有所贡献。
究生是不同的。
（一）选择自己的问题取向，学会创新
你一旦是研究生，你就已经进入另一个阶段，
接受知识到创造知识，是身为一个研究生最大的特色，不仅如此，
己。做为研究生不再是对于各种新奇的课照单全收，
有一个关注的焦点，而不能像大学那般漫无目标。
论文，那篇论文是你个人所有武功的总集合，
（二）尝试跨领域研究，主动学习
提出一个重要的问题，跨越一个重要的领域，将决定你未来的成败。
关键，而你自己本身必须是带着问题来探究无限的学问世界，
点，来探究这些知识，产生有机的循环。
是一个主动的探索者，并学会悠游在这学术的领域。
我举一个例子，我们的中央研究院院长李远哲先生，得了诺贝尔奖。
他的故事。
不教他任何东西。可是隔壁那个教授，老师教很多，
说：「如果我知道结果，那我要你来这边念书做什么？
是他自己从这个什么都不教他，永远碰到他只问他「
但是最好的方式就是将这两个方式结合起来。
习「 self-help 」，而不能再像大学时代般，都是纯粹用听的，
域。
然而研究生另外一个重要的阶段就是 Learn how to learn ，不只是学习而已，而是学习如何学习，
要学习拿起那一根针，学会绣出一件漂亮的衣服，
读书，
而应该是要放在领域的普遍人里面。你这篇文章要有新的东西，
新。
二、一个老师怎么训练研究生
第二个，身为老师你要怎么训练研究生。
和同侪间密切的互动和学习是非常重要的，
你往后的生活应该或多或少都和这个探索有相关。
（一）善用与老师的伙伴关系，不断 Research
我常说英文 research 这个字非常有意义， search 是寻找，而 research 是再寻找，所以每个人都要 research ，不
断的一遍一遍再寻找，并进而使你的生活和学习成为一体。
条件一致者强，凡生活与战斗条件不一致者弱。」
长的，当中你所听到的每一句话，都可能带给你无限的启发。
回想当时我在美国念书的研究生生活，
等。所以能帮助解决问题的不单只是你的老师，
用毛泽东的「革命不是请客吃饭！」来跟他讲：「
（二）藉由大量阅读和老师提点，进入研究领域
怎样进入一个领域最好，我个人觉得只有两条路，
学生就会知道这个领域有些什么，
局在讲什么。藉由学生的报告，
碰到问题可以看哪些东西。就像是我在美国念书的时候，
只是不停的开书目，运用这样的方式慢慢训练，
到问题也有能力可以去查询相关的资料。
（三）循序渐进地练习论文写作
到了硕士或博士最重要的一件事，是完成一篇学位论文，
不知道教育方面的论文情况是如何，但是史学的论文都要写二、
体架构组织得通畅可读？首先，必须要从一千字、五千字、
字。这么大规模的论文谁都写得出来，问题是写得好不好，
铜钱；是一间大礼堂，而不是一间小小分割的阁楼。
因为受计算机的影响，我发现很多学生写文章能力都大幅下降。
过慢慢练习会使你的文笔跟思考产生一致的连贯性。
果有好的文笔当然更棒，但那是可遇不可求的，
的还是把内容陈述清楚，从一万字到最后十万字的东西，
我在念书的时候，有一位欧洲史、英国史的大师 Lawrence Stone ，他目前已经过世了，曾经有一本书访问十位最了不起的史学家，
访问中说了一句非常吸引人注意的话，他说他英文文笔相当好，
的地位。内容非常重要，有好的表达工具更是具有加分的作用，
三、研究生如何训练自己
（一）尝试接受挑战，勇于克服
研究生如何训练自己？就是每天、每周或每个月给自己一个挑战，
克服那个挑战，但是要努力去尝试。我在我求学的生涯中，
碰到一个很聪明的人，他就是没办法克服他给自己的挑战，
某一个期限内，无论如何一定要把这三行字改掉，
我挑战三次总会完成一次，完成一次就够了，
你，不一定能做到的事情。不过也要切记，
（二）论文的写作是个训练过程，不能苛求完成精典之作
各位要记得我以前的老师所说的一句话：「
没有办法好好的完成硕士论文，或是博士论文，
后的时间很难再有三年或六年的时间，
教授还要指导学生、上课，因此非常的忙碌，
就一点都不奇怪了。
不一定要刻意强求，要有这是一个训练过程的信念，
是要调整自己的心态，把论文的完成当成一个目标，
摊有一位非常博学多文的旧书店老板，我常常赞叹的对他说：「
文当成要写一本经典，那当然永远写不完。
士那二十几页的论文，不过切记不要把那个当作是目标，
论文，不要一开始就期待它是经典之作。如果你期待它是经典之作，
候我在找一本书，但它并没有在旧书店里面，不过他告诉我：「
个旧书店的老板精熟每一本书，可是他就是永远无法完成，
（三）论文的正式写作
1. 学习有所取舍
到了写论文的时候，要能取也要能舍，因为现在信息爆炸，
树挂相关的东西，但千万不要不断的挂不相关的东西，
这棵知识树要如何形成？第一步你必须对所关心的领域中，
2. 形成你的知识树
我昨天还请教林毓生院士，他今年已经七十几岁了，
五、六本书要读好几遍。」因为林毓生先生是海耶克，
理，虽然你不可能只读那几本重要的书，但是那五、
放一边。生也有涯，知也无涯，你不可能读遍天下所有的好书，
落得普林斯顿街上的那位旧书店的老板一般，
3. 掌握工具
在这个阶段一定要掌握语文与合适的工具。
一个语文，不管是英文、日文、法文 …… 等，一定要有一个语文能够非常流畅的阅读相关书籍，
受限制，因为语文就如同是一扇天窗，
不懂，你就不知道如何找人来帮你或是自己查相关的数据。
具学会。
4. 突破学科间的界线
应该要把跨学科的学习当作是一件很重要的事，
概念，对于本身关心的问题产生另一种不同的启发，
发生在学科交会的地方。为什么会如此？
时候，很多都带有那个时代的思想跟学术背景，比如说，
尔经济奖，这二十年来所颁的奖，
Nash 这位数学家也得诺贝尔经济奖，为什么？
的地方已经 search 太多次了，因此不一定能有很大的创新，
常常一篇硕士论文或博士论文最重要、最关键的，
着手电筒在这个小仓库里面照来照去照太久了，
位数学家为什么会得诺贝尔数学奖？
以用在经济方面来思考，而这个东西在一开始，
关系，在数学的这一个部分也没有大关系，不过两个加在一起，
5. 论文题目要有延展性
对一个硕士生或博士生来说，如果选错了题目，就是失败，
就是要花在这上面，你要不断的跟老师商量寻找一个有意义、
案，就有一万四千个袋子，就要送给一万四千个教授审查。
好，我的著作很好，所以我来申诉。」
常常被拿出来讨论的，就是这个题目不必再做了、
的。
我的学生常常选非常难的题目，我说你千万不要这样，
要挤很多东西，才能筛选出一点点内容，
我写过好几本书，我认为我对每一本书的花的心力都是一样，
好的书，是我二十几岁刚到史语所那一年所写的那本书。
且还是用我以前旧的笔记写的。大陆这些年有许多出版社，
文有错字，因为在军队营区里面随时都要出操、随时就要集合，
有力气校正。
为什么举这个例子呢？我后来想一想，那本书之所以比较好，
剑桥大学出的那一本，不过我认为我最好的书一定是用中文写的，
三分随意，那时候你才可以说对于这一个语文完全理解与精熟，
回到我刚刚讲的，其实每一本书、每一篇论文我都很想把它写好。
的所有训练跟努力才有价值。我在这里建议大家，
可能只有五年，如果你的材料太不集中，
厌数字，但却选了一个全都要靠统计的论文，那是不可能做得好。
6. 养成遵照学术格式的写作习惯
另一个最基本的训练，就是平时不管你写一万字、三万字、
究生的阶段就要培养成为你生命中的一个部份，
几百页，如果一开始弄错了，后来再重头改到尾，一定很耗时费力，
哪一个书名号该在哪里、哪一个地方要用引号、
还很封闭的时候，有一个人从美国回来就说：「
引用。」他的名字就叫 ibid 。所谓 ibid 就是同前作者，这个字是从拉丁文发展出来的，
同编的。英文有一本 The Chicago Manual of Style 就是专门说明这一些写作规范。各位要尽早学会中英文的写作规范，
习，最后随性下笔，就能写出符合规范的文章。
7. 善用图书馆
图书馆应该是研究生阶段最重要的地方，不必读每一本书，
情，就是要把书名看一看。在某些程度上知道书皮就够了，
算机就可以查到书名，可是我还是非常珍惜这种定期去 browse 新到的书的感觉，或去看看相关领域的书长成什么样子。
息教授，他告诉我他在创造力最高峰的时候，
过切记不重要的不要花时间去看，你们生活在信息泛滥的时代，
学生引用一些三流的论文，却引得津津有味，我都替他感到难过，
8. 留下时间，精致思考
还要记得给自己保留一些思考的时间。一篇论文能不能出神入化、
是提醒大家要在一般的层次再提升两三步， conceptualize 你所看到的东西。真切去了解，你所看到的东西是什么？
廓是什么？千万不要被枝节淹没，虽然枝节是你最重要的开始，
难教的东西，我记得我念书时，有位老师信誓旦旦说要开一门课，
的是，在被很多材料和枝节淹没的时候，要适时跳出来想一想，
傅斯年先生来到***以后，