CODEWITHSUNDEEP
array-algorithms
gaurav
gaurav

Reputation: 3126

Array Algorithms

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.

Upvotes: 0

Views: 379

Answers (4)

Wael H. Al Saeed
Wael H. Al Saeed

Reputation: 1

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.

Upvotes: 0

user7120361
user7120361

Reputation:

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

Upvotes: 1

chetan.c chandrashekar
chetan.c chandrashekar

Reputation: 1

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.

Upvotes: 0

Benny Tjia
Benny Tjia

Reputation: 4883

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

Upvotes: 1

Related Questions