Computer Algorithms Data structures

0. What's the difference between a linked list and an array?

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

2. 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 an algorithm to do wild card string matching.

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

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

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

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

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

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

15. 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?

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

17. Multiple by 8 without using multiplication or addition. Now do the same with 7.

18. 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).

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