Use two pointers, one 5 elements ahead of the other. Now move both
pointers ahead together by one element until the first one hits the
end, the second pointer will point to the fifth element from the last.
In my algo, this O(N) space restriction is not violated. Each computer
uses O(N) space only. But overall, all the N computers use O(N^2) space.
I agree with Dhyanesh. This "counting" sort routine prescribed by Adak
fails when the numbers can be random.
Dhyanesh, I searched for "element uniqueness" and that problem is more
generic. It says to find if all the numbers are unique. But in my
problem it is known that exactly one number is dupli
Btw how would your algo work if the numbers were
{ 1, 4, 5, 10^100 , 45, 5 }
I dont believe you can create an array of size 10^100.
This problem cannot be solved in better than O(nlgn).
-Dhyanesh
On 12/2/05, adak <[EMAIL PROTECTED]> wrote:
Hi pramod,I'm not sure what the "right" name for th
Would it be possible to do your calculations on the data as your worked
your way through the data using an array of structs?
Even if you only could load 5,000 or 10,000 structs at a time into the
array, that could provide a fast way to do the work, and then just
reload the array with the next 5,0
Hi pramod,
I'm not sure what the "right" name for this is, if anybody knows I hope
they jump in with that info for us.
In the original problem, the set of numbers contained just ONE
duplicate value. So let's say the set is { 3, 9, 6, 4, 4}
The array that is built up by the loop would then be ha
Well, Even if its O(n) , one way to reduce the steps required for finding the length of the list(which is required here) is two use the Hare and Tortoise method where there are two pointers (Hare and the Tortoise) . The Hare moves two steps for each step the tortoise takes. The tortoise would t
Hi pramod,
Just read your method. The only problem is this: "Ultimately we'll be
left with one person in T." I think this cannot be ensured. You may be
left with a few people who know each other.
one of the restriction is that a computer can only hold O(N) integers.
In a link list the search is always going to be O(n) unless you
customize/modify it.
-Abhishikt
If you want to use the fact that the data are sorted, you can just read
the file once in order to build an array of integers that are the
character offsets of the start of each line. (If all the lines are the
same length, you don't even need to do this!) Then use file seek
(direct access) and bin
you will need to implement data structure = hash table + linked list
In Java there is one available called LinkedHashSet (assuming that your timestamps are all different, otherwise you can't use set).
Hash table and linked list implementation of the Set interface, with predictable iteration ord
I need to get all data between two timestamps. So suppose I use
hashtable, I can easily find the starting timestamp. Then how do I look
for all timestamps between the starting timestamp and ending timestamp
in the hashtable.
Can someone answer to this :
http://www.algogeeks.com/fastest_way_to_find_arbitary_element_in_linked_list
but I am not making any use of the fact that the data is sorted
This sounds like unnecessary consideration. Once you have data in hashtable, based on hashtable implementation you can even have sorted data available through iterator.
On 12/2/05, Jay <[EMAIL PROTECTED]> wrote:
I have to rea
I have to read a large file where every line is timestamped and the
file is sorted by timestamp. I need to store all that data in some good
data structure so that later on I can easily do calculations on data
between two timestamps meaning I will have to search based on date-time
later.
If I u
Hi
If the numbers are arbitrary then you can not do better than O ( n log
(n ) ) ... this is a proven lower bound. Google for "Element
Uniqueness" and you will find links to these proofs.
-DhyaneshOn 12/2/05, pramod <[EMAIL PROTECTED]> wrote:
I am sorry I did not get your solution.So if the giv
/ and Stacks
On 12/2/05, vive <[EMAIL PROTECTED]> wrote:
hi i have to do followingdecimal to binary conversioncan antone help me please
hi i have to do following
decimal to binary conversion
can antone help me please
I am sorry I did not get your solution.
So if the given array is say { 5, 1, 8, 100 }
all are > 1, how will your algo work?
Or you had counting sort in mind? for my problem, counting sort is
ruled out.
If it's possible for the array to encompass by subscript, the entire
range of the numbers, then this is VERY fast.
for each n, {
array[n] += 1
if(array[n] > 1) /* you have found the duplicate n */
break;
}
I call this "doing a distribution count", but I'm sure there's a better
term
21 matches
Mail list logo
