by **JC**, published: 2011-05-17 06:25 viewed: 9444 times

想了解更多的美国生活窍门？请订阅: **JC写的剑知北美生活快报。**

While looking for computer jobs, doing thorough preparation for the interview questions is key. The following is a set of computer science interview questions that I got when I interviewed with Microsoft, Google, Yahoo and Amazon. Also, some interview questions are from smaller software companies. I listed them here to help the computer science/software development interviewers to prepare before the interview. Hope it will help them find a job successfully.

1. How to implement the linux pipe feature in java?

2. How to implement a queue using two stacks?

3. Given a file of URLs, how to find the top 10 most popular domains? If the file is really large (containing tens of millions of URLs), and we don't want to know the exact top 10 most popular domains, what is the quickest way to find the approximate top 10 most popular domains?

4. How do you efficiently right-shift an array with the least memory usage? For example, the original array could be 2 3 4 5 6, after right-shift 2 positions, it should be 5 6 2 3 4. The function prototype is shift_right(int arr, int shiftCount).

5. How to efficiently store a billion URLs?

6. Given an array of integers, say 3,2,4,6,5,7,20,1, efficiently find all the pairs of integers that add up to 8?

7. Given an array of a million integers, how to find the top ten largest integers efficiently?

8. Given the expression 5*( ( (6+8) * (9+2))*2 ), transform it to postfix format, and then use a stack to evaluate it.

9. Write a program to parse the expression 5*( ( (6+8) * (9+2))*2 ) into a tree and evaluate it. Hint: recursive descent parsing and implicit tree

10. Given two very large list of numbers, write a program to perform the union operation of the two lists, i.e., merge the two lists together into one.

11. Write a function that returns the 5th element from the end in a singly linked list of integers. The function has one argument: a pointer to the head node of the linked list.

12. Write a function to remove the duplicate items in-place, return the new size of the array.

1) int RemoveDuplicates(char rg);

2) int RemoveDuplicates(short rg);

3) int RemoveDuplicates(int rgNum);

13. Write a program to efficiently find the number of 1s in a very large bitset (say with size of 1 million)

14. Given an array of 1’s and 0’s – can you tell me how I can get all the 0’s to the left side of the array and all the 1’s to the right?

15. Given a dictionary of words, find all the anagrams for a particular word efficiently. For example, my dictionary contains the following words: pot", "opt", "top", "tall", "app", "pap", the anagram for the word "pot" should be "opt", "top".

16. Write a program to efficiently calculate n^m. The function prototype is: long pow(int n, int m).

17. How google might implement the "Did you mean" feature? (i.e., the user typo would result in a "Did you mean" suggestion.)

18. How could computers generate random numbers when all programs are written by human being?

19. Given an array that contains both positive and negative integers, find the sub-array with the largest sum. For example: -5, 20, -4, 10, -18, The solution is the subset [20, -4, 10] which its sum is 26.

20. Given an array of size N in which every number is between 1 and N, determine if there are any duplicates in it.

21. Given an array of characters which form a sentence of words, given an efficient algorithm to reverse the order of the words (not characters) in it.

22. Reverse a linked list.

23. Insert in a sorted list.

24. In a X's and 0's game (i.e. TIC TAC TOE) if you write a program for this give a fast way to generate the moves by the computer. This should be the fastest way possible.

25. Give a fast way to multiply a number by 7.

26. Write a small lexical analyzer - interviewer gave tokens. expressions like "a*b" etc.

27. Assuming that locks are the only reason due to which deadlocks can occur in a system. What would be a foolproof method of avoiding deadlocks in the system.

28. Ways of optimizing symbol table storage in compilers.

29. How is the readers-writers problem solved?

30. Write an efficient algorithm and C code to shuffle a pack of cards.. this one was a feedback process until we came up with one with no extra storage.

31. Given an array of characters. How would you reverse it? How would you reverse it without using indexing in the array.

32. Do a breadth first traversal of a tree.

33. Write efficient code for extracting unique elements from a sorted list of array. e.g. (1, 1, 3, 3, 3, 5, 5, 5, 9, 9, 9, 9) -> (1, 3, 5, 9).

34. Sort an array of size n containing integers between 1 and K, given a temporary scratch integer array of size K.

35. An array of size k contains integers between 1 and n. You are given an additional scratch array of size n. Compress the original array by removing duplicates in it. What if k << n?

36. An array of integers of size n. Generate a random permutation of the array, given a function rand_n() that returns an integer between 1 and n, both inclusive, with equal probability. What is the expected time of your algorithm?

37. An array of pointers to (very long) strings. Find pointers to the (lexicographically) smallest and largest strings.

38. Write a program to remove duplicates from a sorted array.

39. C++ ( what is virtual function ? what happens if an error occurs in constructor or destructor. Discussion on error handling, templates, unique features of C++. What is different in C++ ( compare with unix).

40. Given a list of numbers ( fixed list) Now given any other list, how can you efficiently find out if there is any element in the second list that is an element of the first list (fixed list).

41. Describe the file system layout in the Linux OS

42. In UNIX, are the files allocated contiguous blocks of data? If not, how is the fragmented data kept track of?

43. Write an efficient C code for 'tr' program. 'tr' has two command line arguments. They both are strings of same length. tr reads an input file, replaces each character in the first string with the corresponding character in the second string. eg. 'tr abc xyz' replaces all 'a's by 'x's, 'b's by 'y's and so on.

44. What is the scope of a static function in C?

45. What is the difference between "malloc" and "calloc"?

46. Given a singly linked list, determine whether it contains a loop or not.

47. Given a singly linked list, print out its contents in reverse order. Can you do it without using any extra space?

48. Reverse a singly linked list recursively.

49. Given a singly linked list, find the middle of the list.

50. Given an array of 100 integers, each array element stores a unique integer in the range of [1-101]. Find which integer in 1-101 is missing in the array.

51. given a sorted array of n integers, find the integer k in the array.

52. Given a binary tree, print out the binary tree level by level.

53. Reverse the bits of an unsigned integer.

54. How do we test most simply if an unsigned integer is a power of two?

55. Exchange two integer variables without a temporary variable? (hint: use XOR, for example, A^B^B=A)

56. Set the highest significant bit of an unsigned integer to zero.

57. Given a pattern [ba*b], how to find out if a string matches this pattern? (for example, aaabccc)

58. Given a char array, some chars are one byte, some chars are two bytes. How to reverse the chars?

To brush up your interview skill set, in particular, the data structure/algorithm ability, see this page for my recommendations - Best Books For Preparing Computer Science Interviews

1. How to implement the linux pipe feature in java?

2. How to implement a queue using two stacks?

3. Given a file of URLs, how to find the top 10 most popular domains? If the file is really large (containing tens of millions of URLs), and we don't want to know the exact top 10 most popular domains, what is the quickest way to find the approximate top 10 most popular domains?

4. How do you efficiently right-shift an array with the least memory usage? For example, the original array could be 2 3 4 5 6, after right-shift 2 positions, it should be 5 6 2 3 4. The function prototype is shift_right(int arr, int shiftCount).

5. How to efficiently store a billion URLs?

6. Given an array of integers, say 3,2,4,6,5,7,20,1, efficiently find all the pairs of integers that add up to 8?

7. Given an array of a million integers, how to find the top ten largest integers efficiently?

8. Given the expression 5*( ( (6+8) * (9+2))*2 ), transform it to postfix format, and then use a stack to evaluate it.

9. Write a program to parse the expression 5*( ( (6+8) * (9+2))*2 ) into a tree and evaluate it. Hint: recursive descent parsing and implicit tree

10. Given two very large list of numbers, write a program to perform the union operation of the two lists, i.e., merge the two lists together into one.

11. Write a function that returns the 5th element from the end in a singly linked list of integers. The function has one argument: a pointer to the head node of the linked list.

12. Write a function to remove the duplicate items in-place, return the new size of the array.

1) int RemoveDuplicates(char rg);

2) int RemoveDuplicates(short rg);

3) int RemoveDuplicates(int rgNum);

13. Write a program to efficiently find the number of 1s in a very large bitset (say with size of 1 million)

14. Given an array of 1’s and 0’s – can you tell me how I can get all the 0’s to the left side of the array and all the 1’s to the right?

15. Given a dictionary of words, find all the anagrams for a particular word efficiently. For example, my dictionary contains the following words: pot", "opt", "top", "tall", "app", "pap", the anagram for the word "pot" should be "opt", "top".

16. Write a program to efficiently calculate n^m. The function prototype is: long pow(int n, int m).

17. How google might implement the "Did you mean" feature? (i.e., the user typo would result in a "Did you mean" suggestion.)

18. How could computers generate random numbers when all programs are written by human being?

19. Given an array that contains both positive and negative integers, find the sub-array with the largest sum. For example: -5, 20, -4, 10, -18, The solution is the subset [20, -4, 10] which its sum is 26.

20. Given an array of size N in which every number is between 1 and N, determine if there are any duplicates in it.

21. Given an array of characters which form a sentence of words, given an efficient algorithm to reverse the order of the words (not characters) in it.

22. Reverse a linked list.

23. Insert in a sorted list.

24. In a X's and 0's game (i.e. TIC TAC TOE) if you write a program for this give a fast way to generate the moves by the computer. This should be the fastest way possible.

25. Give a fast way to multiply a number by 7.

26. Write a small lexical analyzer - interviewer gave tokens. expressions like "a*b" etc.

27. Assuming that locks are the only reason due to which deadlocks can occur in a system. What would be a foolproof method of avoiding deadlocks in the system.

28. Ways of optimizing symbol table storage in compilers.

29. How is the readers-writers problem solved?

30. Write an efficient algorithm and C code to shuffle a pack of cards.. this one was a feedback process until we came up with one with no extra storage.

31. Given an array of characters. How would you reverse it? How would you reverse it without using indexing in the array.

32. Do a breadth first traversal of a tree.

33. Write efficient code for extracting unique elements from a sorted list of array. e.g. (1, 1, 3, 3, 3, 5, 5, 5, 9, 9, 9, 9) -> (1, 3, 5, 9).

34. Sort an array of size n containing integers between 1 and K, given a temporary scratch integer array of size K.

35. An array of size k contains integers between 1 and n. You are given an additional scratch array of size n. Compress the original array by removing duplicates in it. What if k << n?

36. An array of integers of size n. Generate a random permutation of the array, given a function rand_n() that returns an integer between 1 and n, both inclusive, with equal probability. What is the expected time of your algorithm?

37. An array of pointers to (very long) strings. Find pointers to the (lexicographically) smallest and largest strings.

38. Write a program to remove duplicates from a sorted array.

39. C++ ( what is virtual function ? what happens if an error occurs in constructor or destructor. Discussion on error handling, templates, unique features of C++. What is different in C++ ( compare with unix).

40. Given a list of numbers ( fixed list) Now given any other list, how can you efficiently find out if there is any element in the second list that is an element of the first list (fixed list).

41. Describe the file system layout in the Linux OS

42. In UNIX, are the files allocated contiguous blocks of data? If not, how is the fragmented data kept track of?

43. Write an efficient C code for 'tr' program. 'tr' has two command line arguments. They both are strings of same length. tr reads an input file, replaces each character in the first string with the corresponding character in the second string. eg. 'tr abc xyz' replaces all 'a's by 'x's, 'b's by 'y's and so on.

44. What is the scope of a static function in C?

45. What is the difference between "malloc" and "calloc"?

46. Given a singly linked list, determine whether it contains a loop or not.

47. Given a singly linked list, print out its contents in reverse order. Can you do it without using any extra space?

48. Reverse a singly linked list recursively.

49. Given a singly linked list, find the middle of the list.

50. Given an array of 100 integers, each array element stores a unique integer in the range of [1-101]. Find which integer in 1-101 is missing in the array.

51. given a sorted array of n integers, find the integer k in the array.

52. Given a binary tree, print out the binary tree level by level.

53. Reverse the bits of an unsigned integer.

54. How do we test most simply if an unsigned integer is a power of two?

55. Exchange two integer variables without a temporary variable? (hint: use XOR, for example, A^B^B=A)

56. Set the highest significant bit of an unsigned integer to zero.

57. Given a pattern [ba*b], how to find out if a string matches this pattern? (for example, aaabccc)

58. Given a char array, some chars are one byte, some chars are two bytes. How to reverse the chars?

To brush up your interview skill set, in particular, the data structure/algorithm ability, see this page for my recommendations - Best Books For Preparing Computer Science Interviews

1. visitor 2011-05-16 17:28

I am called Nelson Adeson , I am in Cameroon - Douala , I have admission into Dallas Baptist University to study Bachelor Degree in Computer Science Fall Semester 2011 , I had my admission without Toef , what are my chancing of getting a Visa , Dallas Baptist University is a Christian University and i wish to know how i can answer the Visa Officer if i am been ask the below question :1..Why do you choose a Christian University .

2..Why do you choose to study Computer Science .

3..Why do you choose Dallas Baptist University .

4..Why did you not take Toef .

-Is they a disadvantages of session universities Visa obtaining at the Embassy

- Is computer Science really a bad major to take to the embassy

.

Thanks ,

2. JC 2011-05-17 06:25

Computer Science is perfect to pursue in USA. As long as you have good English, I don't see why TOEFL is required. Good luck!
本文版权属于美国剑知信息网。如需转载，请先同我们联系。