-1

I was asked the following question in a 30-minute interview:

Given an array of integers, remove the duplicates without using any STL containers. For e.g.: For the input array [1,2,3,4,5,3,3,5,4] the output should be: [1,2,3,4,5];

Note that the first 3, 4 and 5 have been included, but the subsequent ones have been removed since we have already included them once in the output array. How do we do without using an extra STL container?

In the interview, I assumed that we only have positive integers and suggested using a bit array to mark off every element present in the input (assume every element in the input array as an index of the bit array and update it to 1). Finally, we could iterate over this bit vector, populating (or displaying) the unique elements. However, he was not satisfied with this approach. Any other methods that I could have used?

Thanks.

  • Wow.. Why `-1`? –  Jun 22 '18 at 19:27
  • Bit on the broad side. What do you mean by bit vector? You are trying to pull a fast one by pointing out that `std::vector` isn't really the same as the old STL vector, are you? – user4581301 Jun 22 '18 at 19:29
  • 1
    If there are no time complexity requirements, then you just iterate iterate over the output array to see if you already have a value. –  Jun 22 '18 at 19:29
  • @user4581301, apologies. I meant to say a binary array with just `1`s at those indices where that index appears in the input array. Sorry for using the word `vector`. –  Jun 22 '18 at 19:31
  • There are many ways, sort it first, then algo is trivial, or do it brute force and so on. – Slava Jun 22 '18 at 19:31
  • The first question I would ask is how do they want the duplicates removed from the array since it is a fixed size. – NathanOliver Jun 22 '18 at 19:31
  • 1
    Pretty much any function from `` would work with C-style arrays. Personally, I'd choose standard solution over any other, even if it was more efficient just for the sake of understandable code. – Yksisarvinen Jun 22 '18 at 19:32
  • It wasn't me, but I'm guessing the -1 was because this question has been asked by others before you. For example, here's one approach: https://stackoverflow.com/a/1533109/69998 – Void - Othman Jun 22 '18 at 19:32
  • Is limitation for STL containers only? – Slava Jun 22 '18 at 19:33
  • @Slava, yes, that's right. –  Jun 22 '18 at 19:34
  • Would be a good dupe, but the question is about different language. – Yksisarvinen Jun 22 '18 at 19:34
  • 4
    @RakeshKarandikar then just use `std::sort` and `std::unique` end of story – Slava Jun 22 '18 at 19:36
  • Nothing to apologize for. Thank you for the clarification. @Yksisarvinen when people say no STL, a lot of the time they mean "I want a C program." – user4581301 Jun 22 '18 at 19:37
  • @Yksisarvinen, the accepted answer in the proposed dupe is valid C++ as well. – Void - Othman Jun 22 '18 at 19:37
  • @RakeshKarandikar sorting first is horrible if they are testing for efficiency. – Christopher Pisz Jun 22 '18 at 19:41
  • 2
    @user4581301 OP did not say no STL, he said no STL containers – Slava Jun 22 '18 at 19:43

3 Answers3

3

Just use std::sort() and std::unique():

int arr[] = { 1,2,3,4,5,3,3,5,4 };
std::sort( std::begin(arr), std::end(arr) );
auto end = std::unique( std::begin(arr), std::end(arr) );

Live example

Slava
  • 43,454
  • 1
  • 47
  • 90
  • I agree this works (and will accept it since my question was _only this_). But out of curiosity, how do you modify it to ensure it works well for an array of `string` or `user-defined objects`? I am just curious. I agree my current question does not mention this anyway... I am just looking for a robust method. For one, I know I will have to use templates... –  Jun 22 '18 at 19:53
  • @Rakesh Templates have nothing to do with this. –  Jun 22 '18 at 19:54
  • @NeilButterworth, could you please elaborate _this_? How do I make a method that is robust to accept anything - an array of integers, or strings or user-defined objects as an input? –  Jun 22 '18 at 19:55
  • @Rakesh Sorry, I was refering to your original question, I didn't see your earlier comment. But you would be mad to write your own templated solution to this solved problem, and I'm sure it's not what the interviewer was after. –  Jun 22 '18 at 19:57
  • 1
    Lots of assumptions about what the interviewer was after. Just give them everything. Sort for them, hash for them, implement templates for them, dance a jig for them, but then ask them for 180k/year. More is always better than less. Ask what they are after. Offer up everything you can. – Christopher Pisz Jun 22 '18 at 19:59
  • @NeilButterworth, yeah, I agree - with the later part though (not the initial part where you say I would be mad). –  Jun 22 '18 at 20:00
  • @RakeshKarandikar you need to learn standard library, `std::sort` and `std::unique` work with `std::string` as it is. For user defined object you need to provide either `operator<` and `operator==` or use predicates. – Slava Jun 22 '18 at 20:00
  • 4
    @ChristopherPisz if interviewer cares about efficiency he/she should remove stupid restrictions. And it is definitely not worse that brute force O(n^2) – Slava Jun 22 '18 at 20:06
  • @Slava I'm not the interviewer. I'm just telling you whats out there in the real world, and telling the OP what he needs to know. What he should or shouldn't do is left up to those whom already have jobs and their own interviews to conduct. If there is a more efficient answer then one you gave, the other candidate will get the position and you'll get "sorry we're gonna have to pass" According to HackerRank, this question's most efficient answer is to hash. – Christopher Pisz Jun 22 '18 at 20:15
  • "If there is a more efficient answer then one you gave, the other candidate will get the position and you'll get "sorry we're gonna have to pass"" this is at least questionable. This program will work, manually implemented in 30 minutes hash will be buggy for sure. It does not matter how fast is incorrect program. – Slava Jun 23 '18 at 00:52
  • I think that you've made a false assumption that we are all going to fail at implementing something they teach college freshman. You are also assuming that code "that works" is all it takes to get people jobs. Bad assumptions. I honestly cannot fathom what you have against a more efficient solution. Exponentially more efficient, at that. The only reason you've given thus far is that it's too hard. – Christopher Pisz Jun 25 '18 at 18:50
1

We can first sort the array then check if the next element is equal to the previous one and finally give the answer with the help of another array of size 2 larger than the previous one like this.

Initialize the second array with a value that first array will not take (any number larger/smaller than the limit given) ,suppose 0 for simplicity then 

int arr1[] = { 1,2,3,4,5,3,3,5,4 };
int arr2[] = { 0,0,0,0,0,0,0,0,0,0,0 }; 
std::sort( std::begin(arr1), std::end(arr1) );
int position=1;
arr2[0] = arr1[0];
for(int* i=begin(arr1)+1;i!=end(arr1);i++){
     if((*i)!=(*(i-1))){
         arr2[position] = (*i);
         position++;
     }
}
int size = 0;
for(int* i=begin(arr2);i!=end(arr2);i++){
    if((*i)!=(*(i+1))){
        size++;
    }
    else{
        break;
    }
}
int ans[size];
for(int i=0;i<size;i++){
    ans[i]=arr2[i];
}
Chaman Agrawal
  • 86
  • 2
  • 11
-2

Easy algorithm in O(n^2):

void remove_duplicates(Vec& v) {
    // range end
    auto it_end = end(v);

    for (auto it = begin(v); it != it_end; ++it) {
        // remove elements matching *it
        it_end = remove(it+1, it_end, *it);
    }
    // erase now-unused elements
    v.erase(it_end, end(v));
}

See also erase-remove idiom

Edit: This is assuming you get a std::vector in, but it would work with C-style arrays too, you would just have to implement the erasure yourself.

rlbond
  • 65,341
  • 56
  • 178
  • 228
  • 2
    What is a `Vec`? –  Jun 22 '18 at 19:34
  • `v.erase(it_end, end(v));` works with c style arrays? Also the OP said they can't use standard containers so they won't be getting or using a `std::vector`. – NathanOliver Jun 22 '18 at 19:40
  • @NathanOliver I said they will need to implement the erasure themselves. What does OP want, a newly allocated C-array? – rlbond Jun 22 '18 at 19:42
  • @NeilButterworth `Vec` is a typedef for a `vector`. If you can't use a vector, the algorithm is still sound. Iterate over the original array and remove any duplicates. – rlbond Jun 22 '18 at 19:43
  • The algorithm is still sound for anything that implements major parts of the Standard Library the interface of a vector i.e. it is vector, which was excluded in the OP's question. –  Jun 22 '18 at 19:47