Thursday, May 05, 2005

 

Some notes on Puzzle Questions - 1

1.
发信人: robustzgy (浪迹天涯), 信区: JobHunting
标 题: Re: 面试时被问到的有趣问题。
发信站: Unknown Space - 未名空间 (Wed May 4 19:10:27 2005), 转信

can use induction.
n=1,2,3,.....
F(n)=a*(F(n-1)+1)+b*F(n-1)
where a+b=1
a=n/{2n choose 2}=1/2n-1;
F(n)=F(n-1)+1/2n-1;

【 在 fiby (I+Know) 的大作中提到: 】
: 有n条绳子放在地上,每次从地上抽两个绳头,如果是同一个绳子的,将其打成一个环,
: 如果不是,也将两个绳头打结,做成一条新绳子。继续这样的操作,直到地上没有两个绳
: 头为止,请问平均的绳环的数量?
--
※ 来源:.Unknown Space - 未名空间 mitbbs.com.[FROM: 128.113.]

2.
发信人: antelope (虽碎岁随), 信区: JobHunting
标 题: Re: A programming interview question
发信站: Unknown Space - 未名空间 (Tue May 3 11:41:13 2005), 转信

Use Zobrist hashing (google if you don't know what it is).

【 在 syrsyr (syrsyr) 的大作中提到: 】
: Given a document, how to find pairs of words with same charactors but
: different order?
: This is my thinking: Use stringtokenizer to get every word. Then calculate the
: sum of unicode values of all characters in a word. Campare the sum value of
: different words. If same, then they are possible pairs. But this is only
: sufficient condition.
: Any thought?
--
爱琴海 -- Aegean Sea
※ 来源:.Unknown Space - 未名空间 mitbbs.com.[FROM: 68.149.]

3.
发信人: maxlu (南瓜饼), 信区: Programming
标 题: intervew question
发信站: BBS 未名空间站 (Wed Jun 29 01:23:51 2005), 转信

Suppose you have a single linked list, but you don't have the head pointer.
Given random pointer to a node in the list, delete this node from the list.

I have some basic ideas. But I am thinking about the solution if the random
pointer point to the last node.

Any ideas?

--

※ 来源:·BBS 未名空间站 mitbbs.com·[FROM: 128.194.]

发信人: maxlu (南瓜饼), 信区: Programming
标 题: Re: intervew question
发信站: BBS 未名空间站 (Wed Jun 29 18:38:12 2005), 转信

summarize:

1) If ther given pointer p is the address of next pointer of previos node
(Node**) or address of head (&head), the prblem is very easy to solve. Just

Node* temp = *p;
*p = (*p)->next;
delete temp;

2) But the problem is the given pointer is just an address to a random
node. (Node*).

The idea is to copy valude of next node to provious node one by one.
Then delete the last node. However, it cannot solve the problem when
the given pointer is just the address of last node. You cannot
get the address of previous node's next; then you cannot modify it
to null.

I think it depends on how we define the linked list. We can append
a dumy node at the end of the linked list so that there's no such
a problem. It is only a workaround.

※ 来源:·BBS 未名空间站 mitbbs.com·[FROM: 128.194.]

4.
发信人: topgun (有一说一), 信区: JobHunting
标 题: Google Labs Aptitude Test ( 10)
发信站: Unknown Space - 未名空间 (Fri Oct 15 04:50:38 2004)
On an infinite, two-dimensional, rectangular lattice of 1-ohm resistors,
what's the resistance between two nodes that a knight's move away?

--
**************************************
**************************************
http://home.91i.net/zhouyuxuan/Images/gs.gif
http://pop.pcpop.com/upimg/10669855982003731891733683.gif
http://218.9.252.30/1/bbs2.gif

来源:.Unknown Space - 未名空间 mitbbs.com.[FROM: 208.180.]

Answer can be found in

Electric currents in infinite networks
From http://math.dartmouth.edu/~doyle/docs/net/net/net.html

5.
发信人: procrustes (sunday), 信区: Programming
标 题: 做题做题
发信站: Unknown Space - 未名空间 (Fri May 7 14:12:30 2004) WWW-POST

朋友去Interview时的问题,想了一下没想出来..
给你N对括号“()”来排列,如果对排列出来的
式子(只有括号)从左向右数,不管你停在式子中
的哪个位置,“(”的数目都必须大于等于“)”的
数目,这样的排列结果才是一个Valid的结果,问
N对括号有多少个Valid的排列结果。
举例:
N=2: 2个, ()(), 和 (())
N=3: 5个。

--
※ 来源:.Unknown Space - 未名空间 mitbbs.com.[FROM: 128.211.]

发信人: entourage (无远弗届), 信区: Programming
标 题: Re: 做题做题
发信站: Unknown Space - 未名空间 (Fri May 7 18:29:14 2004) WWW-POST


f(n) = \sum_{i = 0}^{n - 1} f(i)f(n - 1 - i)
with f(0) = 1

f(n) = (2n)! / n! / (n+1)!

发信人: gunxu (Gang), 信区: Programming
标 题: Re: 做题做题
发信站: Unknown Space - 未名空间 (Sat May 8 15:39:07 2004) WWW-POST

right,

f(n) = C_{2n}^n - C_{2n}_^{n-1}

this is a special case of infamous voting problem. first term is the total
permutation number, the second term is the permutation number where bracket
don't match. It is so because the Mexwell reflection principle.

6.
发信人: gloomyturkey (一只郁闷的火鸡), 信区: Programming
标 题: Classic Interview question
发信站: Unknown Space - 未名空间 (Tue Apr 27 09:37:02 2004) WWW-POST

A special case of subset-sum problem:

Given an array of integer a[n] and fixed number N, what's the complexity to
decide whether there is a pair: ai+aj = N?

Interviewee claimed that it is a O(n) problem.

I searched the JHQ, there is a O(nlogn) solution. So: can anyone give a O(n)
solution or prove it is impossible to solve in O(n)?

thx for your insights.

发信人: xxxyyyzzz (2005 找到好工作), 信区: Programming
标 题: Re: Classic Interview question
发信站: Unknown Space - 未名空间 (Wed Feb 16 02:11:23 2005), 转信


Maybe Hash is not the interviewer desired
Another algorithm is provided below

First set up a array A into all zeros

A[1] A[2] A[3] ... A[N]

Then set up a array B into all zeros

B[N] B[N-1] B[N-2] ... B[1]

read a integr from a[n] then put

A[a[n]]=B[N-a[n]]=1

Loop for a[n]

Finally Add up A and B as

A[1]+B[N], A[2]+B[N-1], ...

if there is a sum output as 2 then we found a pair, otherwise ...

Obviously it is linear time cost of max(N,n)

【 在 gloomyturkey (一只郁闷的火鸡) 的大作中提到: 】
: A special case of subset-sum problem:
: Given an array of integer a[n] and fixed number N, what's the complexity to
: decide whether there is a pair: ai+aj = N?
: Interviewee claimed that it is a O(n) problem.
: I searched the JHQ, there is a O(nlogn) solution. So: can anyone give a O(n)
: solution or prove it is impossible to solve in O(n)?
: thx for your insights.

7.
There are 25 horses, each runs at different speed. You can race a maximum
of 5 horses each time. What is the minimum number of races needed to determine
the three fastest horses? (You need to determine which is No.1, which is No.2
and which is No.3).

With a clock you need only 5 times.
Without a clock, you need 7 times.

This one had been discussed b4 either here or on programming board,
let me try:
1) 5 races to get a winner from 5 different groups.
2) 1 race for winners of the 5 groups. #1 is the fastest. let b and c be #2 and #3 of this race
3) 1 race for b, c, the #2 & #3 from the #1 group and #2 from b group.

The first 2 of the last race are the next two fastest. total is 7.

8.
From http://www.cnblogs.com/Michael_z/archive/2005/09/24/243341.html

经典问题:有12个球,外观一模一样,重量也应该是一模一样,但偏偏其中有一个球不那么老实,与其他球不同,现提供天平一个,请问最少要多少次能够把那个同的球找出来。

# re: 12个球的烦恼 回复
刚好前不久我看到过这道题

编号为1、2、...、12
取1、2、3、4;5、6、7、8 称
若相同,则称9;10
若相同,则称1;11
若相同,则12为所求
否则11为所求
否则,称1;9
若相同,则10为所求
否则9为所求
否则,记现在天平状态为“+”(另一非平状态为“-”)
称1、6、7、8;5、10、11、12
若相同,则称2;3
若相同,则4为所求
若为“+”,则2为所求
若为“-”,则3为所求
若为“+”,则称1;12
若相同,则5为所求
否则1为所求
若为“-”,则称6;7
若相同,则8为所求
若为“+”,则6为所求
若为“-”,则7为所求

2005-09-24 19:07 地狱门神

# re: 12个球的烦恼 回复
问题是这样的:有12个球,外观一模一样,重量也应该是一模一样,但偏偏其中有一个球不那么老实,与其他球不同,现提供天平一个,请问最少要多少次能够把那个不同的球找出来。
----------------------------------------------------------------------

楼主的题目中只是要求把那个不同的球(姑且称其为坏球)找出来,并没有要求回答坏球是轻或重了,那么即使有13个球,用天平称3次也可以找出坏球的。当然,如果只有12个球,还可以顺便判断出坏球的轻重来。

解法:

设这13个球的编号为: 1-8, A-E,

R1 = CMP(1234, 5678);
switch (R1)
{
case '<': // 1-4轻或5-8重 R2 = CMP(1235, 4ABC); switch (R2) { case '<': // 1-3轻 R3 = CMP(1, 2); switch (R3) { case '<': Output(1轻); break; case '=': Output(3轻); break; case '>': Output(2轻); break;
}
break;
case '=': // 6-8重
R3 = CMP(6, 7);
switch (R3)
{
case '<': Output(7重); break; case '=': Output(8重); break; case '>': Output(6重); break;
}
break;
case '>': // 4轻或5重
R3 = CMP(4, A);
switch (R3)
{
case '<': Output(4轻); break; case '=': Output(5重); break; } break; } break; case '=': // A-E坏, 不知轻重 R2 = CMP(AB, C1); switch (R2) { case '<': // AB轻或C重 R3 = CMP(A, B); switch (R3) { case '<': Output(A轻); break; case '=': Output(C重); break; case '>': Output(B轻); break;
}
break;
case '=': // DE坏, 不知轻重
R3 = CMP(D, 1);
switch (R3)
{
case '<': Output(D轻); break; case '=': Output(E ); break; //仅当有13个球时 case '>': Output(D重); break;
}
break;
case '>': // AB重或C轻
R3 = CMP(A, B);
switch (R3)
{
case '<': Output(B重); break; case '=': Output(C轻); break; case '>': Output(A重); break;
}
break;
}
break;

case '>': // 1-4重或5-8轻
R2 = CMP(1235, 4ABC);
switch (R2)
{
case '>': // 1-3重
R3 = CMP(1, 2);
switch (R3)
{
case '<': Output(2重); break; case '=': Output(3重); break; case '>': Output(1重); break;
}
break;
case '=': // 6-8轻
R3 = CMP(6, 7);
switch (R3)
{
case '<': Output(6轻); break; case '=': Output(8轻); break; case '>': Output(7轻); break;
}
break;
case '<': // 4重或5轻 R3 = CMP(4, A); switch (R3) { case '=': Output(5轻); break; case '>': Output(4重); break;
}
break;
}
break;
}

2005-09-25 15:04 空军

9.
from http://wangcong.org/articles/puzzle.html

解读求pi的怪异代码
Cong Wang
25th November,2005


Institute of Post and Telecommunications, Xi'an, P.R.China
Network Engineering Dep.


引言
网上流传着一个怪异的求pi程序,虽然只有三行却能求出pi值连小数点前共800位。这个程序如下:

/*某年Obfuscated C Contest佳作选录:*/
#include < stdio.h>
long a=10000, b, c=2800, d, e, f[2801], g;
main(){
for(;b-c;)f[b++]=a/5;
for(;d=0,g=c*2;c-=14,printf("%.4d",e+d/a),e=d%a)
for(b=c;d+=f[b]*a,f[b]=d%--g,d/=g--,--b;d*=b);
}

/* (本程式可算出pi值连小数点前共800位)
(本程式录自sci.math FAQ,原作者未详)*/

咋一看,这程序还挺吓人的。别慌,下面就告诉你它是如何做到的,并且告诉你写怪异C程序的一些技巧。^_^

展开化简
我们知道,在C语言中,for循环和while循环可以互相代替。

for(statement1;statement2;statement3){
statements;
}

上面的for语句可以用下面的while语句来代替:

statement1;
while(statement2){
statements;
statement3;
}

而且要写怪异的C程序,逗号运算符无疑是一个好的助手,它的作用是:
从左到右依次计算各个表达式的值,并且返回最右边表达式的值。
把它嵌入for循环中是写怪异代码的常用技巧之一。所以,上面的程序可以展开为:
#include < stdio.h> /*1*/
/*2*/
long a=10000, b, c=2800, d, e, f[2801], g; /*3*/
main(){ /*4*/
while(b-c!=0){ /*5*/
f[b]=a/5; /*6*/
b++; /*7*/
} /*8*/
d=0; /*9*/
g=c*2; /*10*/
while(g!=0){ /*11*/
b=c; /*12*/
d+=f[b]*a; /*13*/
f[b]=d%--g; /*14*/
d=d/g--; /*15*/
--b; /*16*/
while(b!=0){ /*17*/
d=d*b+f[b]*a; /*18*/
f[b]=d%--g; /*19*/
d=d/g--; /*20*/
--b; /*21*/
} /*22*/
c-=14; /*23*/
printf("%.4d",e+d/a); /*24*/
e=d%a; /*25*/
d=0; /*26*/
g=c*2; /*27*/
} /*28*/
} /*29*/

现在是不是好看一点了?

进一步化简
你应该能注意到a的值始终是10000,所以我们可以把a都换成10000。再就是,仔细观察g,在外层循环中,每次循环用它做除法或取余时,它总是等于2*c-1,而b总是初始化为c。在内层循环中,b每次减少1,g每次减少2。你这时会想到了吧?用2*b-1代替g!代进去试试,没错!另外,我们还能做一点化简,第26行的d=0是多余的,我们把它合并到第13行中去,第13行可改写为: d=f[b]*a; 。所以程序可以改为:
#include < stdio.h>

long b, c=2800, d, e, f[2801];
main(){
while(b-c!=0){
f[b]=2000;
b++;
}

while(c!=0){
b=c;
d=f[b]*10000;
f[b]=d%(b*2-1);
d=d/(b*2-1);
--b;
while(b!=0){
d=d*b+f[b]*10000;
f[b]=d%(b*2-1);
d=d/(b*2-1);
--b;
}
c-=14;
printf("%.4d",e+d/10000);
e=d%10000;
}
}

少了两个变量了!

深入分析
好了,马上进入实质性的分析了。一定的数学知识是非常有必要的。首先,必须知道下面的公式可以用来求pi:
pi/2=1+1!/3!!+2!/5!!+3!/7!!+...+k!/(2*k+1)!!+...
只要项数足够多,pi就有足够的精度。至于为什么,我们留给数学家们来解决。
写过高精度除法程序的人都知道如何用整数数组来进行除法用法,而避免小数。其实很简单,回想一下你是如何徒手做除法的。用除数除以被除数,把得数放入结果中,余数乘以10后继续做下一步除法,直到余数是零或达到了要求的位数。
原程序使用的数学知识就那么多,之所以复杂难懂是因为它把算法非常巧妙地放到循环中去了。我们开始具体来分析程序。首先,我们从数学公式开始下手。我们求的是pi,而公式给出的是pi/2。所以,我们把公式两边同时乘以2得:

pi=2*1+2*1!/3!!+2*2!/5!!+2*3!/7!!+...+2*k!/(2*k+1)!!+...

接着,我们把它改写成另一种形式,并展开:

pi=2*1+2*1!/3!!+2*2!/5!!+2*3!/7!!+...+2*n!/(2*n+1)!!

=2*(n-1)/(2*n-1)*(n-2)/(2*n-3)*(n-3)/(2*n-5)*...*3/7*2/5*1/3
+2*(n-2)/(2*n-3)*(n-3)/(2*n-5)*...*3/7*2/5*1/3
+2*(n-3)/(2*n-5)*...*3/7*2/5*1/3
+2*3/7*2/5*1/3
+2*2/5*1/3
+2*1/3
+2*1

对着公式看看程序,可以看出,b对应公式中的n,2*b-1对应2*n-1。b是从2800开始的,也就是说n=2800。(至于为什么n=2800时,能保证pi的前800位准确不在此讨论范围。)看程序中的相应部分:
d=d*b+f[b]*10000;
f[b]=d%(b*2-1);
d=d/(b*2-1);

d用来存放除法结果的整数部分,它是累加的,所以最后的d将是我们要的整数部分。而f[b]用来存放计算到b为止的余数部分。
到这里你可能还不明白。一是,为什么数组有2801个元素?很简单,因为作者想利用f[1]~f[2800],而C语言的数组下标又是从0开始的,f[0]是用不到的。二是,为什么要把数组元素除了f[2800]都初始化为2000?10000有什么作用?这倒很有意思。因为从printf("%.4d",e+d/10000); 看出d/10000是取d的第4位以前的数字,而e=d%10000; ,e是d的后4位数字。而且,e和d差着一次循环。所以打印的结果恰好就是我们想要的pi的相应的某4位!开始时之所以把数组元素初始化为2000,是因为把pi放大1000倍才能保证整数部分有4位,而那个2就是我们公式中两边乘的2!所以是2000!注意,余数也要相应乘以10000而不是10!f[2800]之所以要为0是因为第一次乘的是n-1也就是2799而不是2800!每计算出4位,c都要相应减去 14,也就保证了一共能够打印出4*2800/14=800位。但是,这竟然不会影响结果的准确度!本人数学功底不高,无法给出确切答案。(要是哪位达人知道,请发email到xiyou.wangcong@gmail.com告诉我哦。)

偶然在网上见到一个根据上面的程序改写的“准确”(这个准确是指没有漏掉f[]数组中的的任何一个元素。)打印2800位的程序,如下:
long b,c=2800,d,e,f[2801],g;
int main(int argc,char* argv[])
{
for(b=0;b f[b] = 2;
e=0;
while(c > 0)
{
d=0;
for(b=c;b>0;b--)
{
d*=b;
d+=f[b]*10;
f[b]=d%(b*2-1);
d/=(b*2-1);
}
c-=1;
printf("%d",(e+d/10)%10);
e=d%10;
}
return 0;
}

不妨试试把上面的程序压缩成3行。

结论
以Knuth图灵演讲中的一句话结束全文:
We have seen that computer programming is an art, because it applies accumulated knowledge to the world, because it requires skill and ingenuity, and especially because it produces objects of beauty. A programmer who subconsciously views himself as an artist will enjoy what he does and will do it better.
与大家共勉!^_^



<< Home

This page is powered by Blogger. Isn't yours?