1.You are given a list of n numbers from 1 to n-1, with one of the numbers repeated. Devise a method to determine which number is repeated.
The sum of the numbers 1 to n-1 is (n)(n-1)/2. Add the numbers on the list, and subtract (n)(n-1)/2. The result is the number that has been repeated.
2.Write an algorithm to detect loop in a linked list.
You are presented with a linked list, which may have a "loop" in it. That is, an element of the linked list may incorrectly point to a previously encountered element, which can cause an infinite loop when traversing the list. Devise an algorithm to detect whether a loop exists in a linked list. How does your answer change if you cannot change the structure of the list elements?
One possible answer is to add a flag to each element of the list. You could then traverse the list, starting at the head and tagging each element as you encounter it. If you ever encountered an element that was already tagged, you would know that you had already visited it and that there existed a loop in the linked list. What if you are not allowed to alter the structure of the elements of the linked list? The following algorithm will find the loop:
The important realization for this problem is that the hour hand is always moving. In other words, at 1:30, the hour hand is halfway between 1 and 2. Once you remember that, this problem is fairly straightforward. Assuming you don't care whether the function returns the shorter or larger angle, Example 4 shows a solution to this problem.
The sum of the numbers 1 to n-1 is (n)(n-1)/2. Add the numbers on the list, and subtract (n)(n-1)/2. The result is the number that has been repeated.
2.Write an algorithm to detect loop in a linked list.
You are presented with a linked list, which may have a "loop" in it. That is, an element of the linked list may incorrectly point to a previously encountered element, which can cause an infinite loop when traversing the list. Devise an algorithm to detect whether a loop exists in a linked list. How does your answer change if you cannot change the structure of the list elements?
One possible answer is to add a flag to each element of the list. You could then traverse the list, starting at the head and tagging each element as you encounter it. If you ever encountered an element that was already tagged, you would know that you had already visited it and that there existed a loop in the linked list. What if you are not allowed to alter the structure of the elements of the linked list? The following algorithm will find the loop:
- Start with two pointers ptr1 and ptr2.
- Set ptr1 and ptr2 to the head of the linked list.
- Traverse the linked list with ptr1 moving twice as fast as ptr2 (for every two elements that ptr1 advances within the list, advance ptr2 by one element).
- Stop when ptr1 reaches the end of the list, or when ptr1 = ptr2.
- If ptr1 and ptr2 are ever equal, then there must be a loop in the linked list. If the linked list has no loops, ptr1 should reach the end of the linked list ahead of ptr2.
The important realization for this problem is that the hour hand is always moving. In other words, at 1:30, the hour hand is halfway between 1 and 2. Once you remember that, this problem is fairly straightforward. Assuming you don't care whether the function returns the shorter or larger angle, Example 4 shows a solution to this problem.
No comments:
Post a Comment