Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 3555
  • Last Modified:

Remove duplicate elements in a array

How to remove duplicate elements in a array using hash tables and also without using hash tables.


this was an interview question.
0
tamilthambi
Asked:
tamilthambi
  • 2
2 Solutions
 
sunnycoderCommented:
All duplicates will produce the same hash value .. simply search the  hash bucket and elminate it if it is a duplicate. A good hash function will distribute the values evenly in buckets so this should be fairly fast to perform.

Without using hash tables would depend on other constraints .. e.g. given sufficient memory you can allocate an array of range of value in that array .. simply keep marking the index value equal to data value and  consolidate the values in single scan ... This would bebad if range is huge but number of values is small ....
Or you can try sorting the array ... Or try to construct a binary search tree .. basically you need to gauge what is that interviewer is trying to have you optimize .. ask him/her questions to determine the constraints/performance they are looking for.

Cheers!
sunnycoder
0
 
fridomCommented:
without hash you can sort the array. Then you walk it and you copy all the unique elements to another array. You even can keep the same array you just have to remove the not unique elements, e.g while setting the to a known value which indicates it "not there".

The problem with hashes is that you can get the same hash for different values. That happens sooner or later, so you can not eliminate it that easy. The only way not to let happen if you can assure that no element in the field yields the same hash code.

So sunnycoder is not fully right on his first suggestion.

Regards
Friedrich
0
 
sunnycoderCommented:
Friedrich,

Perhaps I was not clear enough. I never said that two different values cannot produce same hash. What I said was duplicate values will have the same hash (unless ofcourse you are using some hash function like time()%value). That was the reason I said you need to search the hash bucket before eliminating an element.

Cheers!
sunnycoder
0

Featured Post

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now