Archive for 七月, 2005

Algorithm

Posted: 2005/07/30 in 杂货铺

1.What’s the difference between a linked list and an array?

 

2.Implement a linked list. Why did you pick the method you did?

 

3.Implement an algorithm to sort a linked list. Why did you pick the method you did? Now do it in O(n) time.

 

3.Describe advantages and disadvantages of the various stock sorting algorithms.

 

4.Implement an algorithm to reverse a linked list. Now do it without recursion.

 

5.Implement an algorithm to insert a node into a circular linked list without traversing it.

 

6.Implement an algorithm to sort an array. Why did you pick the method you did?

 

7.Implement an algorithm to do wild card string matching.

 

8.Implement strstr() (or some other string library function).

 

9.Reverse a string. Optimize for speed. Optimize for space.

 

10.Reverse the words in a sentence, i.e. "My name is Chris" becomes "Chris is name My." Optimize for speed. Optimize for space.

 

11.Find a substring. Optimize for speed. Optimize for space.

 

12.Compare two strings using O(n) time with constant space.

 

13.Suppose you have an array of 1001 integers. The integers are in random order, but you know each of the integers is between 1 and 1000 (inclusive). In addition, each number appears only once in the array,except for one number, which occurs twice. Assume that you can access each element of the array only once. Describe an algorithm to find the repeated number. If you used auxiliary storage in your algorithm, can you find an algorithm that does not require it?

 

14.Count the number of set bits in a number. Now optimize for speed. Now optimize for size.

 

15.Multiple by 8 without using multiplication or addition. Now do the same with 7. Add numbers in base n (not any of the popular ones like 10, 16, 8 or 2 — I hear that Charles Simonyi, the inventor of Hungarian Notation,favors -2 when asking this question).

 

16.Write routines to read and write a bounded buffer.

 

17.Write routines to manage a heap using an existing array.

 

18.Implement an algorithm to take an array and return one with only unique elements in it.

 

19.Implement an algorithm that takes two strings as input, and returns the intersection of the two, with each letter represented at most once. Now speed it up. Now test it.

 

20.Implement an algorithm to print out all files below a given root node. Given that you are receiving samples from an instrument at a constant rate, and you have constant storage space, how would you design a storage algorithm that would allow me to get a representative readout of data, no matter when I looked at it? In other words, representative of the behavior of the system to date.

 

21.How would you find a cycle in a linked list?

 

22.Give me an algorithm to shuffle a deck of cards, given that the cards are stored in an array of ints.

 

23.Imagine this scenario:

I/O completion ports are communictaions ports which take handles to files, sockets, or any other I/O. When a Read or Write is submitted to them, they cache the data (if necessary), and attempt to take the request to completion. Upon error or completion, they call a user-supplied function to let the users application know that particular request has completed. They work asynchronously, and can process an unlimited number of simultaneous requests. Design the implementation and thread models for I/O completion ports.Remember to take into account multi-processor machines.

 

24.Write a function that takes in a string parameter and checks to see whether or not it is an integer, and if it is then return the integer value.

 

25.Write a function to print all of the permutations of a string.

 

26.Implement malloc.

 

27.Write a function to print the Fibonacci numbers.

 

28.Write a function to copy two strings, A and B. The last few bytes of string A overlap the first few bytes of string B.

 

29.How would you write qsort?

 

30.How would you print out the data in a binary tree, level by level, starting at the top?

 

31.The following asm block performs a common math function, what is it?

cwd xor ax, dx

sub ax, dx

 

Advertisements

淡如水

Posted: 2005/07/21 in 杂货铺
小时候觉得自己的将来会有无数的可能性,而现在觉得每天的不同就是晚上下班时是在外面吃饭还是回家自己做饭吃.
胡胡现在每天一回到家就霸占我的电脑看那些无聊的怪异小说,上周她考试的成绩出来了,查分前就开始了许愿,如果这次过了.就请我们干锅居的咪西咪西.看在干锅居的份上,我亲自操刀上网.结果分数查出来了.一门57,一门58.胡胡傻眼了,干锅居是没指望了.我开始声讨胡胡的七宗罪,从她复习前晚上不知死活每天熬夜看韩剧.同时为了欺骗自己还把一大堆复习的资料都堆在床头上.周未阿呆和她妹妹来玩,她妹妹一看到胡胡的床头堆满了复习的书大为敬佩.狂批阿呆要她好好学习胡胡"啧啧,你看看人家,连晚上睡觉都不忘记复习".而我记得胡胡最让我叹为观止的是她竟然能够在同一时刻在做帐,看连续剧,与饭桶聊天三个任务而互不影响.
不知道这种淡得如水的日子还要过多久.生活不应该是这样平淡的阿
                              
 

这二天看UMUHS借给我的Band of Brothers,抛开对与错的立场,日尔曼民族的确非常优秀, 如果不是希特勒最后在攻打莫斯科上犯下的致命错误,那么二战的结果也许就要完全改写.而作为德国军队闪电战术的灵魂-装甲部队,德国党卫军第一装甲师的歌曲.从音乐角度欣赏,也是一首气势磅礴,节奏强劲的好歌曲。
 
    

作者:Era
歌曲:The Mas/弥撒

The Mas/弥撒
  空气布满紧张的气氛,大战即将来临,
  泪水划过母亲的脸庞,祖国就在身后,
  远方传来敌军的脚步声,大地在颤抖,
  是捍卫正义的时候了,热血早已澎湃,
  干枯树枝上最后一片树叶被寒风打落,
  闪电撕破了远处承重的黑幕,看,是SS部队在前进.

  
  

全体指挥官的合影(正中为该师首任师长约瑟夫·迪特里希)  
  

党卫军第一装甲师/1st SS Panzer Division
  该师的前身是1933年3月17日组建的“柏林警备队”,当时希特勒从慕尼黑的卫队中亲自挑选出120名士兵,作为个人的贴身警卫。同年9月的慕尼黑大会中,正式改称“阿道夫-希特勒”党卫队。由迪特里希任首领。1939年发展到3700人。在闪击波兰的战役中,它从南部发起进攻,势如破竹,于9月底攻入华沙。
  1940年德军进攻西欧,由于机械化程度高,该师6小时便攻入荷兰境内80公里,荷兰投降后,受命向南转进,协助在法国边境的德军作战。当6月24日法国投降时,它已攻至圣爱田地区,是进展最快速的德军部队.

   

党卫军第一装甲师的士兵在法国战役时小憩为准备对苏作战,它于1941年被调到东线,并在南欧作战中以闪电般的速度穿过南斯拉夫及保加利亚,攻入希腊,在希腊投降的3天前,俘虏了16个师的希腊部队。此役结束后,该部扩编为机械化步兵师团,共有10796名官兵。其后,在侵苏作战中被编入南方集团军,1941年6月22日攻入苏联,并和“维京”师团通力合作,协助第11和第17军团在乌曼包围苏军3个军团,会战结果有10万多名苏军官兵被俘。乌曼会战后不久该师改编成装甲掷弹兵师团。
  斯大林格勒之役后,德军在哈尔可夫引诱苏军发动攻势,然后投入SS第一装甲师(即阿道夫-希特勒师团)进行作战,结果苏军损失52个师级和旅级部队,造成2万多名士兵阵亡,损失了600多辆坦克。该战役是希特勒在斯大林格勒大败后的首次胜利,为此希特勒大喜:“武装党卫队装甲军团足可抵得上20个意大利师!

1943年春季哈尔科夫战役后,古德里安将军视察第1SS师直属第4重坦克连的老虎,站在车上穿黑制服的是连长-科林SS上尉
  
  

库尔斯克战役中,第1SS师直属第13重坦克连的老虎“1313”号(看炮塔上)接下来武装党卫队各装甲师开始大量换装新研制的“虎”式及“黑豹”式坦克,并参加了库尔斯克作战,后在南乌克兰地区遭苏军包围,元气大伤。
1944年6月6日,盟军大举登陆诺曼底,该师虽然受命阻击盟军,却由于盟军激烈的空中攻击而再次蒙受惨重的损失。
  

  

该师最著名的坦克王牌——米歇尔·魏特曼
  
  诺曼底之战后,阿道夫-希特勒师从比利时撤到安亨(即:阿纳姆)地区,并在那里参加了著名的安亨之役(即:市场—花园战役),结果重创英军空降部队。随后,该师又于1944年12月16日参加了争夺西线主动权的阿登战役。此战结束后,希特勒火速将遭受重创的武装党卫队各师团加以整编,并派到匈牙利境内以解救布达佩斯的德军守备队。这次作战成为阿

道夫-希特勒师团的最后一战。在苏军强大的压力下德军已是筋疲力尽,几经惨败后不得不撤退。希特勒为此非常震怒,认为他最心爱的武装党卫队已经背叛他,于是在1945年3月底下令取消他们的袖标,正式宣告希特勒与武装党卫队的决裂。其后阿道夫-希特勒师团和其他的武装党卫队一起退到奥地利,终于在史泰尔地区向美军投降,部分后卫部队被苏军俘虏.

 

雨巷

Posted: 2005/07/02 in 杂货铺

独自撑着雨伞
徘徊在悠长的雨巷
多希望遇见一个
结着愁怨的姑娘
她有丁香一样的颜色
她有丁香一样的芬芳
她象我一样撑着油纸伞
彷徨在雨巷

 

忽然一位姑娘
出现在寂寥的雨巷
梦一般凄婉迷茫
有着太息的眼光
她有丁香一样的颜色
她有丁香一样的芬芳
我身旁飘过独自的女郎
走到那竹篱墙

这女郎象梦一样
冷漠凄清又惆怅
我多希望送她一枝丁香花
消散那眼光里面迷茫的忧伤

独自撑着雨伞
徘徊在悠长的雨巷
多希望遇见一个
结着愁怨的姑娘。
她有丁香一样的颜色
她有丁香一样的芬芳
她象我一样撑着油纸伞
彷徨在雨巷
这女郎象梦一样
冷漠凄清又惆怅
我多希望送她一枝丁香花
消散那眼光里面迷茫的忧伤

这女郎象枝丁香
寂寞美丽又芬芳
我多希望送她一枝丁香花
交换那眼光里面哀怨的惆怅
丁香一样的姑娘
消隐在悠长的雨巷
多希望再次相逢
在这寂寥的雨巷
她有丁香一样的颜色
她有丁香一样的芬芳
她象梦一样撑着油纸伞
飘过了雨巷