Bonzo
BAN USERSuppose the array has numbers ranging from 20 to 200. Declare an array of size (200 - 20) = 180 and initialize all values to 0. Let's call this array duplicates.
Suppose the array in which we have to find duplicates is named arr.
Loop through arr. For every arr[i] increment duplicates[arr[i] - 20].
After the loop is complete, duplicates[i] will hold the number of times (i + 20) occurred in arr.
1. Take two pointers, fast and slow. At each iteration, the fast pointer moves forward two nodes and the slow pointer moves forward one node. If the two pointers meet, that means there is a loop. Break out of the loop.
2. Now start a counter to find out the length of the loop. Initialize the counter to 0. Don't move the slow pointer, only move the fast pointer forward. For every iteration, increment the counter by 1. When the slow and fast pointers meet, the counter's value will give you the length of the loop.
3. Now that you have the length of the loop (loopLength), initialize both slow and fast pointers to the head of the linked list. Start a for loop and move the fast pointer forward loopLength number of times. At this point, the slow pointer points to the head and the fast pointer is loopLength nodes ahead of the slow pointer.
4. Now just move the slow and fast pointers forward till they meet. Where they meet is the beginning of the loop.
public Node getBeginingOfLoop() {
Node slowIterator = this.head; // slow pointer
Node fastIterator = this.head; // fast pointer
/*
* slow pointer moves ahead one node
* fast pointer moves ahead two nodes.
* If the two pointers meet, break out of the loop
*/
while(fastIterator.getNext().getNext() != null) {
slowIterator = slowIterator.getNext();
fastIterator = fastIterator.getNext().getNext();
if(slowIterator == fastIterator) {
break;
}
}
/*
* find out the length of the loop by keeping slow
* pointer stationary and moving the fast pointer
* forward till they meet
*/
int loopLength = 0;
while(slowIterator != fastIterator) {
fastIterator = fastIterator.getNext();
loopLength++;
}
slowIterator = this.head; // initialize pointers to head
fastIterator = this.head;
/* move the fast pointer loopLength nodes ahead */
for(int iii = 0; iii < loopLength; iii++) {
fastIterator = fastIterator.getNext();
}
/*
*now the slow pointer is at the head and fast pointer is
* loopLength nodes ahead of slow pointer.
* Start moving pointers ahead till they meet
*/
while(slowIterator != fastIterator) {
fastIterator = fastIterator.getNext();
slowIterator = slowIterator.getNext();
}
return fastIterator; // where they meet is the starting of the loop
}
This is obviously incorrect. Suppose the five groups are A, B, C, D, E. After racing each of these groups you can find out the top horse in each group. So you know the horse ranked 1 in each group (A1, B1, C1, D1, E1) and you can race these to find out the fastest horse. But it is possible that the horse that came second in Group A (A2) is faster than the horse that came first in Group B (B1). Your method doesn't take that into account.
Or as ben pointed out, if the top 3 horses out of the 25 are in the same group, then your method won't work.
This is a better solution than the "automaton" solution because you can easily change this for any number. If the question was to calculate remainder when dividing by 99, and you wanted to solve using the automaton solution, you would have to list all possible states.
- Bonzo June 26, 2012Just iterate through the elements and store them in a std::map. std::map doesn't store duplicates, so you don't need to worry about that. After you've stored the whole array, the 4 largest numbers are myMap[myMap.size()-1], myMap[myMap.size()-2], myMap[myMap.size()-3], myMap[myMap.size()-4].
This will take O(n) time.
Just iterate through the array and store the numbers in a std::map. std::map doesn't store duplicates so you don't have to worry about that. After storing, the 4 largest numbers are: myMap[myMap.size() -1], myMap[myMap.size() -2], myMap[myMap.size() -3], myMap[myMap.size() -4].
- Bonzo June 19, 2012We represent the people in the room as: a, b, c, d, ..., n
Stand these people in a line.
Ask the first person who all they know.
If the first person knows no one, then they are the celebrity.
If they know 5 people, then the celebrity is one of those 5 people.
Suppose a knows (b, c, d, e, f). Now, out of these 5 people, we only need to find the person who doesn't know anyone. The worst case complexity of this algorithm is O(n) which is when the first person we ask knows everyone. Then we have to loop through the n people to find out who doesn't know anyone. But if the first person knows only m people (such that m<= n), then our algorithm will run in O(m).
In our example, we will only need to find out who knows no one out of the 5 people that a knows.
Someone correct me if my logic is incorrect please.
Reppaulajheineman, Consultant at Bank of America
Hello, I am from Las Vegas, NV.Completed a Diploma course in Advanced Technological Developments and Staff Management. I have ...
Repsheenaamajors, System Administrator at Achieve Internet
Teach art classes to a diverse array of students of varying ages and abilities. Strong desire to incorporate a multidimensional ...
In order traversal of a tree takes O(n) time. Your approach will take approximately O(nlogn) time. The interviewer asked for a O(logn) time algo.
- Bonzo July 10, 2012