up vote 0 down vote favorite

I have one question to ask on Algorithms. I have been asked to write the algorithm on this: Not asking you to write the algo for me, but just let me know the efficient process what I need to do:

There is an array of n elements like the book or contents of Bible, and Suppose you have inserted a input string "Gaurav Agarwal" in that. What you want to do you need to fetch unique elements that are present in the array for that String. Just an algorithm how you will proceed further (unsorted)

If you did not understand then let me know and I will try to help on this.

share|improve this question
up vote 1 down vote

One good way to find duplicates in an unsorted array is to sort it based on the string elements, therefore the algorithm for your homework question would be:

  1. Sort the array
  2. check your array for existence of "Gaurav Agarwal". Since it is sorted, neighboring elements would be the same string, and what you need to do then is to keep a counter and increment it until you find the first array element that is not equal to the string you're looking for
share|improve this answer
  • There was 100000 elements in an array already defined .and you need to find the input string unique elements from that array if those are present in the big array , – gaurav Jul 4 '11 at 6:18
up vote 1 down vote

it will take some time to sort the string array and then to parse it. I would recommend just to parse the array of string and verify if length of your string is the same as the length of the string from the current position of the array. If the length is the same, compare the 2 strings

share|improve this answer
up vote 0 down vote

I dont think sorting and searching is the most efficient solution to your problem.

Sorting itself has nlogn complexity.

Just doing a bruteforce search of array is more efficient(has a complexity of n)

This is the case if you are finding unique elements for one string or a few strings. If you are trying to find unique elements for a lot of input strings instead of one only then sorting makes sense.

share|improve this answer
up vote 0 down vote

I would proceed in the following steps:

  1. I would use a hash table with chaining, using a hash function that works well for strings.
  2. find the hash of the new string and search the linked list of the slot corresponding that hash for duplicates.
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.