Finding duplicates in array

Question

I know how to find duplicate elements in array but recently in an interview question, I was asked to find duplicate elements in array in a single pass meaning without using nested loops and recursion. I tried but failed. The interviewer wasn't kind enough to even give me a hint. So I came here to ask, Is it possible to find duplicate elements in array without nested loops/recursion? If yes can anybody give an example code? Also Library functions are not allowed

P.S I would also like to know what impact does it have if we don't use loops or recursion. Is it related to complexity?

Should we use O(1) additional memory as well, or we have no such limitations? — Denis Kulagin, Mar 09 '16 at 11:13
Ops, right. Well, it seems to me you should have asked the interviewer for details. Can you assume the elements are integers? If yes, then you can sort using counting sort. If not, then you can use hash table and have O(n) *expected* time. Etc. etc. — blazs, Mar 09 '16 at 12:13
We don't know what the interviewer has really asked you, but as stated in your question, this is not possible. — n. m. could be an AI, Mar 09 '16 at 12:17
It *is* possible and solutions have already been given below (although horrenduously inefficient). I do, however, feel that not all constraints given in the original question have been presented above. Such questions regularly have a twist in them like "integers from 1..n with one duplicate in an array 1..(n+1)" — tofro, Mar 09 '16 at 12:36
@tofro All these solutions assume something that is not stated in the question, or violate stated requirements. If you can assume whatever you want, you can solve any problem. Why not assume that the array contains booleans and call it a day? No, wait, that's too stupid, let's use a dictionary! OK. Since library functions or nested loops or recursion are not allowed, how do you implement a dictionary? — n. m. could be an AI, Mar 09 '16 at 14:28
It seems to me this kind of interviewing question is usually a prompt to say something along the lines of "It seems like you're asking this question to weed out the grit who can't code because you've been scammed, but this question is also likely to weed out the gold. I don't do consultant work for free. Call me when you need someone to come up with **decent** interview questions." and hand them a business card... ;) — autistic, Mar 09 '16 at 14:46

score 4 · Accepted Answer · answered Mar 09 '16 at 11:18

4

You can keep a hash table/dictionary with item counts for each item value.

answered Mar 09 '16 at 11:18

Alexander Lazarov

578
5
13

@n.m. Why isn't coding your own hashtable allowed? – autistic Mar 09 '16 at 14:49
@Seb Try doing it without loops or recursion. – n. m. could be an AI Mar 09 '16 at 15:46
@n.m. Without using nested loops? Sure. Multiple loops can be merged into one using `continue`... – autistic Mar 09 '16 at 15:53
@n.m. You just changed the goalposts... First you were talking about the "loops and recursion" requirement, and now you've moved on to the other requirement. Did you realise you were wrong about that first one? That's okay, I'm happy to move on... You don't have enough information to extrapolate "find duplicate elements in array in a single pass" to "must not perform passes of other arrays". – autistic Mar 09 '16 at 16:03
@n.m. It's a loop that accesses every element precisely once, yes. Does that mean it can't loop multiple times per element access? – autistic Mar 09 '16 at 16:10
@n.m. That kind of inflammatory language is most unsuitable for this website. I no longer wish to converse with you. – autistic Mar 09 '16 at 16:13
@n.m. I'm astounded when comment etiquette is constantly violated by two members well beyond the "new to the website" status. None of these comments prompt or offer further information for this answer for future readers; in fact they should only exist as comments for the question. I fully expect someone to flag this entire thread, and every comment here will be deleted. Please consider the number of keystrokes you waste next time you comment in the wrong place. – autistic Mar 09 '16 at 16:33
@n.m. Have you tested your comment etiquette by [reading (all of) the FAQ](http://stackoverflow.com/help/privileges/comment)? Did you happen to notice that this particular FAQ page states that you shouldn't comment for "Secondary discussion or debating a controversial point"? Now, since this entire stream of comments is in violation please stop responding and leave it to be destroyed. – autistic Mar 09 '16 at 16:54

score 0 · Answer 2 · edited May 23 '17 at 12:31

0

Since you did not mention anything about the array, I'd say it isn't possible to do it in single pass. I'm not sure if counting sort is the answer you're looking for. So, the only solution to your problem is to use a dictionary. This is the most simplest implementation of a dictionary I could find in C.

Quick Way to Implement Dictionary in C

Hope this helps.

edited May 23 '17 at 12:31

Community

1
1

answered Mar 09 '16 at 12:33

ebby94

3,131
2
23
31

score 0 · Answer 3 · answered Mar 11 '16 at 16:38

Since you want to find duplicates in linear time, e.g. one pass, you must use an additional data structure to count the number of times each element appears.

Here I assume the array is of integers. This would work for any type though. I use a HashMap that uses the elements, in this case integers, as the key, and the number of occurrences as the value.

public static ArrayList<Integer> findDuplicates(int[] arr) {

   HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
   for (int i = 0; i < arr.length; i++) {
       if (!map.containsKey(arr[i]))
           map.put(arr[i], 1);
       else
           map.put(arr[i], map.get(arr[i]) + 1);
   }

   ArrayList<Integer> dups = new ArrayList<Integer>();

   for (Integer i : map.keySet())
       if (map.get(i) > 1)
            dups.add(i);

  return dups;
}

So

int arr[] = {1,2,3,4,2,1,2,3,4,5,6,7,8};
findDuplicates(arr);

would return [1, 2, 3, 4].

Vagish · Answer 4 · 2016-03-09T12:06:45.790

-1

I am assuming size of integer is 2 bytes.

#define ARRAY_SIZE 10

int array[ARRAY_SIZE] = {2,3,1,5,1,6,7,7,8,1};

int duplicate[65535] = {0};

for(char i = 0;i< ARRAY_SIZE;i++)
{
  duplicate[array[i]]++;
  if(duplicate[array[i]] > 1)
  {
     printf(" %d is duplicate in array",array[i]);
  }  
}

Now, each index of duplicate array shows number of times a value is repeated in array.

edited Mar 09 '16 at 12:06

answered Mar 09 '16 at 11:28

Vagish

2,520
19
32

(1) The assumption is not reasonable and (2) this is not an O(n) solution. See my explanation for the other bad answer as to why this is so wrong. – Tom Karzes Mar 09 '16 at 11:29
@TomKarzes I am working on 78K0R compiler where sizeof integer is 2 bytes. – Vagish Mar 09 '16 at 11:31
Doesn't matter. The values could be doubles, or structs. Even if they aren't, suppose you have an array of 10 integers ranging in value from 1 to 32767. It's hardly an O(n) solution, is it? In any case, this clearly is not the desired answer to OP's problem. – Tom Karzes Mar 09 '16 at 11:32
@TomKarzes could you please elaborate why this is not O(n) solution? – Vagish Mar 09 '16 at 11:34
Because n is the length of the array, not the number of integers the machine can represent. The run time should scale linearly with the length of the array. Most modern general purpose processors are in fact 64 bits these days, but even at 32 bits creating an array large enough to hold all of them is impractical. Further, why do you think restricting the values to very tiny integers is reasonable? It should work on doubles or other data types as well. – Tom Karzes Mar 09 '16 at 11:37
@TomKarzes please go through the question again, I have given the answer which gives O(n) solution to given question. You have down-voted my answer considering it is not practical(for your system). I am still not getting whether the answer is wrong or not? – Vagish Mar 09 '16 at 11:41
No, you have given a horribly inefficient solution that only works at all if (1) the array contains integers and (2) integers are so small that you're willing to create an array large enough to support every possible integer value as an index. Neither assumption is reasonable. I can't explain it any more clearly than this. – Tom Karzes Mar 09 '16 at 11:45
Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/105799/discussion-between-vagish-and-tom-karzes). – Vagish Mar 09 '16 at 11:46

score -1 · Answer 5 · answered Mar 09 '16 at 11:40

-1

Simple - but creative - solution: Propose the requirement the array should be sorted - Then its going to be trivial. (But that is how interview questions work)

answered Mar 09 '16 at 11:40

tofro

5,640
14
31

1

I think we can safely assume the response would be "Nice try, but it's not" – Tom Karzes Mar 09 '16 at 11:41
I don't think so - Not where I'm interviewing. I *like* to hear creative answers rather than text book answers. The hash proposed in other answers is a perfect solution given the fictuous requirement but does not lead to a perfect program. And if you had a real case of finding duplicates, you could probably improve code quality a lot when asking for a sorted array - Which could, in reality, a piece of cake to fulfil. – tofro Mar 09 '16 at 12:00
1

I just consider it too trivial to be interesting if the array is sorted. Why even ask the question if that's the case? If given the problem, I would probably confirm it with "I assume the array is unsorted?", just to let the interviewer know I had thought of it, but I'd be pretty surprised if the answer was "No, it's sorted, next question". What's the point? – Tom Karzes Mar 09 '16 at 12:11
The point is: I want the candidate to come up with the simplest solution. Even if it requires discussion and maybe re-work in other places. Because that is what I would expect from an engineer working in my team. Hashing is a nice solution to the problem given the constraints, but If you'd do that in a real team you'd probably have to be fired.... – tofro Mar 09 '16 at 12:18
If you're interviewing bright people, and the solution was "oh, sorry, I forgot to tell you the array is already sorted", they'd probably finding it insulting. I know I would. Any such condition should be part of the problem statement. It isn't something someone would fail to notice in a real problem. – Tom Karzes Mar 09 '16 at 12:22
Come to think of it: If you wouldn't ask for a sorted array, I'd probably not hire you. There you are. – tofro Mar 09 '16 at 12:27
So if I didn't ask that someone execute an O(n\*log(n)) algorithm before giving me the problem, so that I could then solve it in an additional O(n) time? Seriously? Why not go one better, and require that all the duplicates appear at the front of the array? This is a *useless* answer, it is not clever, and you aren't thinking of anything that isn't obvious to anyone who hears it. This is a very elementary interview question, and you failed to answer it. Sorry. – Tom Karzes Mar 09 '16 at 13:24

Finding duplicates in array

5 Answers5