0. Implement Insert and Delete for
singly-linked linked list
sorted linked list
circular linked list
int Insert(node** head, int data)
int Delete(node** head, int deleteMe)
1. Split a linked list given a pivot value
void Split(node* head, int pivot, node** lt, node** gt)
2. Find if a linked list has a cycle in it. Now do it without marking nodes.
3. Find the middle of a linked list. Now do it while only going through the list once. (same solution as finding cycles)
4. Reverse words in a string (words are separated by one or more spaces). Now do it in-place.
5. Reverse a string
6. Strip whitespace from a string in-place
void StripWhitespace(char* szStr)
7. Remove duplicate chars from a string ("AAA BBB" -> "A B")
int RemoveDups(char* szStr)
8. Find the first non-repeating character in a string:("ABCA" -> B )
int FindFirstUnique(char* szStr)
9. You may be asked about using Unicode strings. What the interviewer is usually looking for is:
each character will be two bytes (so, for example, char lookup table you may have allocated needs to be expanded from 256 to 256 * 256 = 65536 elements)
that you would need to use wide char types (wchar_t instead of char)
that you would need to use wide string functions (like wprintf instead of printf)
10. Guarding against being passed invalid string pointers or non nul-terminated strings (using walking through a string and catching memory exceptions
11. Implement the following functions for a binary tree:
Insert
PrintInOrder
PrintPreOrder
PrintPostOrder
12. Implement a non-recursive PrintInOrder
13. You are given an array with integers between 1 and 1,000,000. One integer is in the array twice. How can you determine which one? Can you think of a way to do it using little extra memory.
14. You are given an array with integers between 1 and 1,000,000. One integer is missing. How can you determine which one? Can you think of a way to do it while iterating through the array only once. Is overflow a problem in the solution? Why not?
15. Returns the largest sum of contiguous integers in the array
Example: if the input is (-10, 2, 3, -2, 0, 5, -15), the largest sum is 8
int GetLargestContiguousSum(int* anData, int len)
16. Implement Shuffle given an array containing a deck of cards and the number of cards. Now make it O(n).
17. Return the sum two largest integers in an array
int SumTwoLargest(int* anData, int size)
18. Sum n largest integers in an array of integers where every integer is between 0 and 9
int SumNLargest(int* anData, int size, int n)
19. Implement a Queue class in C++ (which data structure to use internally? why? how to notify of errors?)
