Monday, July 03, 2006
Some thought-provoking algorithmic questions.
Some interesting questions I've been asked recently along with my responses. Try to determine a fast and efficient way to provide the result of each situation.
Middle element of a singly linked list
Suppose you have a singly linked list of objects. How would you determine the object in the middle of the list using a single pass? One way: create 2 pointers. The first pointer traverses the list using the next pointer for each element. Every other time through the list the 2nd pointer is moved to the next element. When the 1st pointer reaches the end, the 2nd pointer is the middle.
Considerations: What if the list changes during the search and elements are added or removed?
Nth element from end of a singly linked list
Suppose you have the same list. How would you determine the 5th object from the end of the list? One way: Similar to the above except the 2nd pointer doesn't begin traversing until the 1st pointer gets to the 5th element. Then both pointers move until the 1st pointer again reaches the end. The 2nd pointer will point at the 5th element from the end.
Considerations: Same.
Sorting a file of integers
Suppose you have a file of integers. The size of the file is unknown. Each integer is in the range of 0 to 1000. How would you print the integers in sorted order? One way: create a 1000-element array. As each integer is read, use it as an index into the array and increment that element by 1. The array will hold a count of occurrences of each integer. At EOF, iterate over the 1000-element array and print the index of each non-zero cell using the value of the cell to tell how many times to print the index.
Considerations: file access security, buffers size, integer values within range
Find the start of a list
Suppose you have a array of integers. The array is sorted into ascending order except the starting point of the element is unknown. Find the 0-based index of lowest valued element in the array. For example, (20,30,5,10,15) returns 2. The array is a fixed, unlimited size. One way: Split the list in half. Compare the value of the left most element to the value midpoint element and compare the value of the midpoint element to the right most element. This comparison yields which half of the list contains the point where the numbers recycle. Update the left or right pointer to the mid point, reset to the new middle point. Repeat until left and right are adjacent. Compare the 2 values and return the index of the lower.
Considerations: locking the list from change, assuming list is sorted per specification, duplicates
Find a duplicate value
Suppose you have an array of integers. The size of the array is unlimited. Each cell in the array contains a value between 1 and the number of elements in the array. Find the value of any element that occurs more than once in the list. For example, (1,2,3,2,3) returns 2 or 3 but not 1. The list must remain intact when the function completes. One way: iterate through the list. Using the value of each cell as an index, negate the element (vals[Math.abs(vals[index])]) *= -1. If the element is already negative, it is a duplicate. Save the value. Revert all negatives values to positive.
Considerations: write access to target from called routine, locking list from change whilst executing.
Add an index to a very large data base table
You have a very high availability data base with a very large table that has a high frequency of inserts (10 per second). There are >400M rows in the table. You need to create a new index on the table with little to no downtime on the table. You cannot use create index because locking would stall access until it was able to complete. One way: Create a new table with the new index. Copy over all rows from the base table. Upon completion of the copy, rename the tables. Copy any rows that appeared between the end of your copy operation and the rename operation. Only a slight number of rows would receive an error. The application would be smart enough to wait a few seconds and retry.
The fox, the hen and the bag of corn.
A farmer has to cross a stream in a canoe. He has a fox, a hen and a bag of corn. He can only carry one item at a time with him across the stream in the canoe. If he leaves the fox alone with the chicken, the fox will eat the chicken. If he leaves the chicken alone with the corn, the chicken will eat the corn. How can he get everything across the stream in the least number of trips?
One way: Take the chicken across. Go back and get the fox. Leave the fox and take the chicken back to the original side. Leave the chicken on the original side and take the corn across. Go back and get the chicken.
Middle element of a singly linked list
Suppose you have a singly linked list of objects. How would you determine the object in the middle of the list using a single pass? One way: create 2 pointers. The first pointer traverses the list using the next pointer for each element. Every other time through the list the 2nd pointer is moved to the next element. When the 1st pointer reaches the end, the 2nd pointer is the middle.
Considerations: What if the list changes during the search and elements are added or removed?
Nth element from end of a singly linked list
Suppose you have the same list. How would you determine the 5th object from the end of the list? One way: Similar to the above except the 2nd pointer doesn't begin traversing until the 1st pointer gets to the 5th element. Then both pointers move until the 1st pointer again reaches the end. The 2nd pointer will point at the 5th element from the end.
Considerations: Same.
Sorting a file of integers
Suppose you have a file of integers. The size of the file is unknown. Each integer is in the range of 0 to 1000. How would you print the integers in sorted order? One way: create a 1000-element array. As each integer is read, use it as an index into the array and increment that element by 1. The array will hold a count of occurrences of each integer. At EOF, iterate over the 1000-element array and print the index of each non-zero cell using the value of the cell to tell how many times to print the index.
Considerations: file access security, buffers size, integer values within range
Find the start of a list
Suppose you have a array of integers. The array is sorted into ascending order except the starting point of the element is unknown. Find the 0-based index of lowest valued element in the array. For example, (20,30,5,10,15) returns 2. The array is a fixed, unlimited size. One way: Split the list in half. Compare the value of the left most element to the value midpoint element and compare the value of the midpoint element to the right most element. This comparison yields which half of the list contains the point where the numbers recycle. Update the left or right pointer to the mid point, reset to the new middle point. Repeat until left and right are adjacent. Compare the 2 values and return the index of the lower.
Considerations: locking the list from change, assuming list is sorted per specification, duplicates
Find a duplicate value
Suppose you have an array of integers. The size of the array is unlimited. Each cell in the array contains a value between 1 and the number of elements in the array. Find the value of any element that occurs more than once in the list. For example, (1,2,3,2,3) returns 2 or 3 but not 1. The list must remain intact when the function completes. One way: iterate through the list. Using the value of each cell as an index, negate the element (vals[Math.abs(vals[index])]) *= -1. If the element is already negative, it is a duplicate. Save the value. Revert all negatives values to positive.
Considerations: write access to target from called routine, locking list from change whilst executing.
Add an index to a very large data base table
You have a very high availability data base with a very large table that has a high frequency of inserts (10 per second). There are >400M rows in the table. You need to create a new index on the table with little to no downtime on the table. You cannot use create index because locking would stall access until it was able to complete. One way: Create a new table with the new index. Copy over all rows from the base table. Upon completion of the copy, rename the tables. Copy any rows that appeared between the end of your copy operation and the rename operation. Only a slight number of rows would receive an error. The application would be smart enough to wait a few seconds and retry.
The fox, the hen and the bag of corn.
A farmer has to cross a stream in a canoe. He has a fox, a hen and a bag of corn. He can only carry one item at a time with him across the stream in the canoe. If he leaves the fox alone with the chicken, the fox will eat the chicken. If he leaves the chicken alone with the corn, the chicken will eat the corn. How can he get everything across the stream in the least number of trips?
One way: Take the chicken across. Go back and get the fox. Leave the fox and take the chicken back to the original side. Leave the chicken on the original side and take the corn across. Go back and get the chicken.
