工作学习 / 专业技术讨论 / ice (甲基苯丙胺) 贡献的一个算法问题，大家讨论 -maple2000(等待着夏天); 2006-3-3 {323} (#2817445@0)
其实都是很简单的data structure的应用。给你一个题吧 by ice (甲基苯丙胺) at 2006.3.2 00:24 [#746553@9]

one singly linked list has two heads (h1 and h2)
the linked list is structured like:
1(h1)->2->3->4->5->6.......->n
(n+1)(h2)->(n+2)->...->(n+m)->i (i<n)

given h1 and h2, return the merged node's address.

不明白.从i->n的节点算不算merged? -canadiantire(轮胎-M.I.N.K.); 2006-3-3 (#2817508@0)

返回第一个就可以了。 -ice(甲基苯丙胺); 2006-3-3 (#2817529@0)

:S -ice(甲基苯丙胺); 2006-3-3 (#2817516@0)
Forgot to mention, do it IN PLACE and don't modify the given linked list. -ice(甲基苯丙胺); 2006-3-3 (#2817520@0)
打听一下，这种类型的问题是不是面试经常会考啊？还是你们纯粹是有兴趣？ -winterbear(Hibernate); 2006-3-3 (#2818252@0)

a true interview question -ice(甲基苯丙胺); 2006-3-4 (#2818278@0)
牛人也对C有兴趣? #2818323, #2818310 -iwantcar(EnjoyStudying); 2006-3-4 (#2818354@0)

第一，这是个算法问题不是个C问题；第二，我的兴趣在于面试是不是会考这种东西，而不在这个问题本身；第三，每个人都有自己牛的领域和不牛的领域，算法领域我是低到水平面以下，大学的东西都忘光光了 -winterbear(Hibernate); 2006-3-4 (#2818393@0)

和你说笑,别往心里去. -iwantcar(EnjoyStudying); 2006-3-4 (#2818612@0)

再来一个 -maple2000(等待着夏天); 2006-3-4 {157} (#2818363@0)
Design an algorithm to print a 2 dimensional array in a spiral clockwise manner? e.g. A[3][4] = 1 2 3 4 5 6 7 8 9 10 11 12 Print : 1 2 3 4 8 12 11 10 9 5 6 7

这个题好像比较容易。 -holdon(again); 2006-3-4 {255} (#2818921@0)
B[3][4]=0,0,0,0,0,0,0,0,0,0,0,0

x=0;
y=0;
while (1)
{
print A[x][y];
b[x][y]=1;
if (y<3 && b[x][y+1] == 0 )
y++
else if ( x<2 && b[x+1][y] ==0 )
x++
else if ( y>0 && b[x][y--] ==0 )
y--
else if ( x>0 &&b[x-1][y]==0 )
x--
else
break
}

Dude, u have to assume it's a m*n matrix -maple2000(等待着夏天); 2006-3-4 (#2818969@0)

你把2，3 换成m-1,n-1不行吗？ -holdon(again); 2006-3-4 (#2818999@0)

正在消化你的算法呢。你那个中间辅助数组可能面试者不答应。另外，你最好implement一次，看是否工作。 -maple2000(等待着夏天); 2006-3-4 (#2819004@0)

你总要有个东西保存某节点是否已经走过的状态。 -holdon(again); 2006-3-4 (#2819017@0)

这个问题我其实是今天上午才整出来，可惜rolia不支持html posting 了，要不俺可以贴俺做的原码 -maple2000(等待着夏天); 2006-3-4 (#2819022@0)

可以贴html阿？贴出来交流交流。 -holdon(again); 2006-3-4 {35} (#2819170@0)
yahoo.com

a sample java implementation -maple2000(等待着夏天); 2006-3-4 {539} (#2819545@0)

This is just one solution for your reference

	public static void printMatrix(int [][] a, int row, int col){
		int minK = rowk; j--) System.out.print(a[row-1-k][j]+" ");
			for(int i=row-k-1; i>k; i--) System.out.print(a[i][k]+" ");
		}
		System.out.println();
	}

7, <pre> tag doesn't work -maple2000(等待着夏天); 2006-3-4 {430} (#2819550@0)
public static void printMatrix(int [][] a, int row, int col){
int minK = row<col?row:col;
for(int k=0; k<minK; k++){
for(int j=k; j<col-k; j++) System.out.print(a[k][j]+" ");
for(int i=k+1; i<row-k; i++) System.out.print(a[i][col-1-k]+" ");
for(int j=col-k-2; j>k; j--) System.out.print(a[row-1-k][j]+" ");
for(int i=row-k-1; i>k; i--) System.out.print(a[i][k]+" ");
}
System.out.println();
}

不错，是个好方法。 -holdon(again); 2006-3-4 (#2819690@0)

另外如果一定不让用辅助数组，一个简单方法是A[x][y]=-A[x][y]; 改条件为 A[][]>0 ; 不过看不出有什么必要。 -holdon(again); 2006-3-4 (#2819180@0)

Write code to reverse a linked list -maple2000(等待着夏天); 2006-3-4 (#2818666@0)

用不着reverse link list吧。先沿 h1走一边，把所有指针存在另一个数租里，在沿h2走，每一步都在数组里查一遍，找到的第一个就是了。 -holdon(again); 2006-3-4 (#2818927@0)

usually they will ask you to do it IN PLACE. -ice(甲基苯丙胺); 2006-3-4 (#2818936@0)

that's the point! even u have done recusive solution, then they'll ask nonrecursive solution. -maple2000(等待着夏天); 2006-3-4 (#2818943@0)
怎样才算IN PLACE呢？正确解法是什么？ -holdon(again); 2006-3-4 (#2819003@0)

for example swap number a and b in place. like prototype: void swap(int a, int b). IN PLACE means no extra memory should be used. -maple2000(等待着夏天); 2006-3-4 (#2819008@0)

照这么说这题就没法做了，不允许使用额外变量。没有临时指针，比都没法比。不过我误会你了，看来你说"reverse a linked list"是另一道题。 -holdon(again); 2006-3-4 (#2819014@0)

这样吧，你先实现swap(a,b) in place.介个比较好整一点。算法肯定有。 -maple2000(等待着夏天); 2006-3-4 (#2819020@0)

这我初中就会了. -holdon(again); 2006-3-4 (#2819157@0)

please give the algorithm -maple2000(等待着夏天); 2006-3-4 (#2819553@0)

时间太久，我忘了行吗？ -holdon(again); 2006-3-4 (#2819691@0)

It's really a good excuse to tell the interviewer. -ice(甲基苯丙胺); 2006-3-4 (#2819772@0)

:-) 我想把一些通常见到的面试算法都做出来，建一个BLOG，最好有人能反馈改进，要不就么得什么意义了 -maple2000(等待着夏天); 2006-3-4 (#2819784@0)

remember what i told you yesterday? -ice(甲基苯丙胺); 2006-3-4 (#2819789@0)

em, then how can I improve my skills？三个臭皮匠抵个诸葛亮不是？ -maple2000(等待着夏天); 2006-3-4 (#2819800@0)

完全看态度 -ice(甲基苯丙胺); 2006-3-4 (#2819831@0)

不过说实话，很多算法平时工作中根本用不上。几个大巨头的面试真的是变态！ -maple2000(等待着夏天); 2006-3-4 (#2819791@0)

其实，ms我不知道，amazon我有同学。上次去seattle一起出去喝酒，那厮整晚都在若有所思的想他的一个task。用perl处理什么东西。很多面试题都是他们实际工作中遇到的真正问题。 -ice(甲基苯丙胺); 2006-3-4 (#2819819@0)

那他们岂不是用面试来套算法了？K，这么便宜的好事。Amazon的面试比MS的更切合实际一些，Google的更好。比如叫应试者写garbage collector是他们的问题之一。不过现在他们的面试题不允许外漏了。 -maple2000(等待着夏天); 2006-3-4 (#2819833@0)

i was asked to figure out how spell checker works by amazon -ice(甲基苯丙胺); 2006-3-4 (#2819838@0)

wow! 你有好的组合算法吗？比如ABCDE里任选两个组合给打印出来？ -maple2000(等待着夏天); 2006-3-4 (#2819852@0)

what's the output? all possible two letters or you just need a random tow letters combination. -ice(甲基苯丙胺); 2006-3-5 (#2819865@0)

all two letters combinations, like ABCD => AB AC AD BC BD CD -maple2000(等待着夏天); 2006-3-5 (#2819873@0)

If need to know how many combinations ------>n! / x!*(n-x)! -simonqu(后悔); 2006-3-5 (#2819897@0)

not the number of combinations but the coms themself -maple2000(等待着夏天); 2006-3-5 (#2819908@0)

Easy way is something like bubble sort. Good way is something like merge sort. Instead of comparation, simply print them out. No difference -simonqu(后悔); 2006-3-5 (#2819945@0)

见intervirewer时说不定急中生智，就想起来了。 -holdon(again); 2006-3-4 (#2819794@0)

得，俺帮你想起来吧 -maple2000(等待着夏天); 2006-3-4 {71} (#2819804@0)
void swap (int a, int b) {
a = a^b;
b = a^b;
a = a^b;
}

还真看不懂。^什么意思？ -holdon(again); 2006-3-4 (#2819813@0)

Bitwise operators: &=AND |=OR ^=XOR ~=NOT -maple2000(等待着夏天); 2006-3-4 (#2819821@0)

高人就是喜欢故意让人不明白。a+b, a-b,a-b不就完了。 -holdon(again); 2006-3-4 (#2819826@0)

哈哈，不错，终于想起来了。a+b, a-b,a-b的做好了，他们会问：能优化算法吗？ -maple2000(等待着夏天); 2006-3-4 (#2819842@0)

靠，这才真叫变态，一个加法还要优化。 -holdon(again); 2006-3-4 (#2819846@0)

当然变态！不过他们是Rule的设计者，玩不玩由你 -maple2000(等待着夏天); 2006-3-5 (#2819856@0)

想出一个in place的解法：先h1走一遍，边走边拆，把指针都置成null,再h2走，走不动就是了。不过找完了，链表也没了。呵呵，这会不会把面试管气晕过去？ -holdon(again); 2006-3-4 (#2819811@0)

Forgot to mention, do it IN PLACE and don't modify the given linked list. -ice(甲基苯丙胺); 3.3 17:06 (#2817520@0) -ice(甲基苯丙胺); 2006-3-4 (#2819814@0)
very creative though. This problem has both recursive and non-recursive solutions -maple2000(等待着夏天); 2006-3-4 {79} (#2819817@0)
when I was asked this question I used stack to solve it. I did get some points.

i guess you are talking about reversing a linked list. he is talking the one with two heads -ice(甲基苯丙胺); 2006-3-4 (#2819825@0)
你是在说第一题吗？最笨的法子，先从h1走，一个一个跟h2比，没找到就h2走一步，再从h1一个一个比，不过这好像傻慢阿。应该有什么可以优化的地方吧。 -holdon(again); 2006-3-5 (#2819858@0)

俺搞错了，你话题接在reverse link list下面，我以为你是说第二题。第一题you are on right track. -maple2000(等待着夏天); 2006-3-5 (#2819860@0)

step1: Pcur = node0 ; Pnxt1= Pcur->next; Pnxt2 = Pnxt1->next; Prev = Pcur; step2: while(){ Pcur = Pnxt1; Pnxt1 = Pnxt2; Pnxt2 = Pnx2->next ; Pcur->next = Prev; Prev = Pcur } -simonqu(后悔); 2006-3-5 (#2819993@0)

There should have some condition check -simonqu(后悔); 2006-3-5 (#2819994@0)
The basic idea is look forward 2 positions, have one pointer for current node and a pointer to the reserve node -simonqu(后悔); 2006-3-5 (#2819995@0)

For recursive way. Break the linked list form the middle like the merge sort; Instead of merge them together, relink them in a reevise way -simonqu(后悔); 2006-3-5 (#2819999@0)

All the questions here are real interview questions. -maple2000(等待着夏天); 2006-3-4 (#2818668@0)
write code to copy a binary search tree. -maple2000(等待着夏天); 2006-3-4 (#2818670@0)

It depends on sallow or deep copy. If it's sallow copy, you only need copy the pointer. Copying a collection in both java and C++ are sollow copy. If it's a deep copy, it depends on what language you're choosing -simonqu(后悔); 2006-3-5 (#2819956@0)

think of serializing and deserializing it. so it's deep copy. -maple2000(等待着夏天); 2006-3-5 (#2819959@0)

A language using array to implement BST, you need calculate the size of the array first then copy the whole chunk of the array. If use linked list, you need do a traverse to copy the linked list -simonqu(后悔); 2006-3-5 (#2819960@0)

When I say copy the linked list, I mean copy it into an array -simonqu(后悔); 2006-3-5 (#2819964@0)

大家共同讨论，共同提高:-) -maple2000(等待着夏天); 2006-3-4 {78} (#2818677@0)
如果我们以前多做一些这种基本训练，我们很多同志就不会被微软，亚马逊，古狗折磨了
implement a function that prints all possible ordering of the chars in a string. -maple2000(等待着夏天); 2006-3-4 (#2818683@0)

similiar to merge sort or quick sort. the Big O time should be nlg(n) -simonqu(后悔); 2006-3-5 (#2819965@0)

interesting idea -maple2000(等待着夏天); 2006-3-5 (#2819969@0)

implement a function that prints all possible combinations of the chars in a string. -maple2000(等待着夏天); 2006-3-4 (#2818685@0)
注意：每个问题最长时间约一小时。有感到简单的DX，如果你还在小公司的话，应该挑战MS, Google -maple2000(等待着夏天); 2006-3-4 (#2818720@0)

These're practical problems. The real challenge is algorithm. You can always refine your design, but without talent you can't solve the algorithm problem. I personally find difficulties on algorithm -simonqu(后悔); 2006-3-5 (#2819927@0)

design a thread pool -maple2000(等待着夏天); 2006-3-4 (#2818945@0)

This one is not easy. It's a OS related problem. It really test you how to implemet how to write a Semaphor and scheduler -simonqu(后悔); 2006-3-5 (#2819899@0)

design a garbage collector -maple2000(等待着夏天); 2006-3-4 (#2818947@0)

step1: Create a deamon which gonna scan the objects on the heap and free any objects without referencing( the refernce counter is 0 ) -simonqu(后悔); 2006-3-5 (#2819877@0)
step 2 create a base class with a date member, reference counter and initially the counter will be one. -simonqu(后悔); 2006-3-5 (#2819881@0)
If you have the change seeing some sections of open source code, this is the most common way to clean the memory -simonqu(后悔); 2006-3-5 (#2819882@0)
step 3, whenever you create a new class, extends the base class we defined in step2 -simonqu(后悔); 2006-3-5 (#2819890@0)
step 4 Anytime any object is referenced, increment the counter. Anytime any object is released, decrease the counter. -simonqu(后悔); 2006-3-5 (#2819892@0)

great! new JVM uses different scheme. instead of reference counter, tracing collector is in favor -maple2000(等待着夏天); 2006-3-5 (#2819902@0)

Java make it more complicated. There's difference between soft delete and hard delete. Anyway, it just another way to manage memory -simonqu(后悔); 2006-3-5 (#2819919@0)

any good memory management articles or books to recommand? -maple2000(等待着夏天); 2006-3-5 (#2819923@0)

Sorry, I only collect thoes information piece by piece. I do learn a lot from C Programming -simonqu(后悔); 2006-3-5 (#2819935@0)

that's fine. Thanks anyway. -maple2000(等待着夏天); 2006-3-5 (#2819938@0)

It also can be implemented by event driven in Java or by call back in C++. Issue an event or triger the call back when the object finds its counter becoming zero -simonqu(后悔); 2006-3-5 (#2819906@0)

design a memory management scheme -maple2000(等待着夏天); 2006-3-4 (#2818950@0)

need more details -simonqu(后悔); 2006-3-5 (#2819900@0)

C++ way or Java way. Interviewer just want to know how you are familiar with any of them or even better all of them -maple2000(等待着夏天); 2006-3-5 (#2819928@0)

If you really want to know it, it's more easy to be understand through assembly language. Have a look how the object created on heap, how a function is called and how the parameters are passed to the function -simonqu(后悔); 2006-3-5 (#2819940@0)
After you familiar thoes problems you can do futher research on how compiler( C or C++) or interpeter(java) works -simonqu(后悔); 2006-3-5 (#2819941@0)

After that you need focus on How OS works on memory allocation, how paging work and how context switch works. Memory management is really not only related to languages -simonqu(后悔); 2006-3-5 (#2819943@0)

design a can-juice vendor machine and test it -maple2000(等待着夏天); 2006-3-4 (#2818958@0)

more details please -simonqu(后悔); 2006-3-5 (#2820000@0)

design an elevator control system and write test cases for it -maple2000(等待着夏天); 2006-3-4 (#2818963@0)

There's an exact example with UML Diagram in Deitel and Deitel. No need snoop around, simply copy it -simonqu(后悔); 2006-3-5 (#2819898@0)

URL please -maple2000(等待着夏天); 2006-3-5 (#2819904@0)

Pick a book like C++ How to program or Java How to program. They're pretty books. You need one of them on hand http://www.deitel.com/ -simonqu(后悔); 2006-3-5 (#2819912@0)

Jig saw puzzle. What are the data structures? Assume you have some method which can tell you if two pieces fit together. How would you solve the puzzle, minimizing the number of times you have to call that function? -maple2000(等待着夏天); 2006-3-5 (#2819961@0)

Where did you collect such a big number questions. It makes me fell like a final exam. The above questions are really good. -simonqu(后悔); 2006-3-5 (#2819973@0)

check ur PM -maple2000(等待着夏天); 2006-3-5 (#2819974@0)

I alway tell people we're computer scientist not a damn programmer. Don't follow the trend but do some study on algorithm and OS. They're the core of CS. Sigh!!! No body believes me -simonqu(后悔); 2006-3-5 (#2819977@0)

@Calgary

a sample java implementation

This is just one solution for your reference

Replies, comments and Discussions:

This is just one solution for your reference

More Topics