Solved

Remove Duplicates

Posted on 2004-04-26
21
431 Views
Last Modified: 2012-06-21
Write out a function that given a sorted list of integers would return the same set of integers with out duplicates. If you could only do 10 tests for the above function what 10 would you do?

guyz thizz not a homework question but a interview screening question i would really appreciate the answer.

thnx
krithi
0
Comment
Question by:krithi
  • 5
  • 4
  • 3
  • +3
21 Comments
 
LVL 86

Expert Comment

by:jkr
Comment Utility
>>would return the same set of integers with out duplicates

That part holds the answer - use a 'std::set<int>', e.g.

#include <set>
using namespace std;

int input [] = { 1,1,2,2,2,3,4,4,5,6,7,8,8,8,9};

set<int> ns;

for ( int i = 0; i < sizeof (input); ++i) {

  ns.insert(input[i]);
}

int nSize = ns.size();
int* output = new int[nSize];

for ( set<int>::const_iterator it = ns.begin(); it != ns.end(); ++ii) {

   output[i] = *it;
}



0
 
LVL 86

Expert Comment

by:jkr
Comment Utility
Oops, the last loop should be

for ( set<int>::const_iterator it = ns.begin(); it != ns.end(); ++it) {

  output[i] = *it;
}
0
 

Author Comment

by:krithi
Comment Utility
thnx but can u just write this in simple c or c++.

thnx
krithi
0
 
LVL 86

Accepted Solution

by:
jkr earned 43 total points
Comment Utility
>>thnx but can u just write this in simple c or c++.

This is the C++ area, and the above is simple C++...
0
 

Author Comment

by:krithi
Comment Utility
I meant withou using STL
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
Comment Utility
That is simple C and shouldn't be posted here in C++:

#include <string.h>

        int input [] = { 1,1,2,2,2,3,4,4,5,6,7,8,8,8,9};

        int last = input[0];
        int siz  = sizeof(input);
        for (int i = 1; i < siz; i++)
        {
             if (input[i] == last)
             {    
                  if (i < siz-1)
                     memmove(&input[i], &input[i+1], siz-i-1);
                  input[--siz] = 0;                
             }
             last = input[i];
        }

Regards, Alex
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
Comment Utility
Should be

            }
            else
               last = input[i];

Regards, Alex
0
 
LVL 39

Assisted Solution

by:itsmeandnobodyelse
itsmeandnobodyelse earned 41 total points
Comment Utility
>>  If you could only do 10 tests for the above function what 10 would you do?

I would ask jkr, AlexFM, Axter, DanRollins, Sys_Prog, bcladd, STeH, chensu, rstavely, khkremer to check my function and wonder how i could make so many mistakes in such a little function.
0
 

Author Comment

by:krithi
Comment Utility
will this work?

void RemoveDuplicates(struct Node* pHead)
{
      //pHead - Beginning of the sorted list.
      if (pHead)
      {
            struct Node* pCurrent = pHead->pNext;
            struct Node* pPrev = pHead;
            // add pPrev->nValue to the new sorted list with no duplicates.
      }
      
      while(pCurrent)            // iterate the list till the end
      {
            if(pCurrent->nValue == pPrev->nValue)
            {
                  // move to current pointer to the next node.
                  pCurrent = pCurrent->pNext;
            }
            else
            {
                  //add pCurrent->nValue to the new sorted list with no duplicates.

                  // move the previous pointer to the current node.
                  pPrev = pCurrent;                  

                  // move to current pointer to the next node.
                  pCurrent = pCurrent->pNext;            
            }
      }
}
0
Highfive + Dolby Voice = No More Audio Complaints!

Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

 
LVL 11

Assisted Solution

by:bcladd
bcladd earned 41 total points
Comment Utility
Only problem I detect is that it won't include the first value in the result list. So the result is empty for a single valued list.

-bcl
0
 

Author Comment

by:krithi
Comment Utility
i think this will do the job

if (pHead)
     {
          struct Node* pCurrent = pHead->pNext;
          struct Node* pPrev = pHead;
          // add pPrev->nValue to the new sorted list with no duplicates.
     }
0
 
LVL 11

Expert Comment

by:bcladd
Comment Utility
Then follow that with your while loop and you are good to go.

What test cases would you use (and why)?
0
 
LVL 3

Expert Comment

by:CoolBreeze
Comment Utility
but i thought he says 10 tests?
how do you use only 10 tests for a general problem?
0
 
LVL 11

Expert Comment

by:bcladd
Comment Utility
The point of limiting you to 10 tests is two-fold:
  -- Even with automated testing, writing test cases with more than 10 different test scenarios for a routine of this length is probably a waste of effort (if the test cases are well chosen)
  -- Regardless of the number of tests, you can easily prioritize what you want to test and come up with 10 tests that will catch many bugs (off by 1 errors, null input errors, etc.)

You ask how 10 tests oculd work for a general problem. How many tests would you run? How many tests would your employer want to pay you to run? The point is that with well chosen test cases you can get good coverage (of the infinite logical input space).

-bcl
0
 
LVL 3

Expert Comment

by:EarthQuaker
Comment Utility
#include <algorithm>

int input [] = { 1, 2, 2, 3, 3, 3 };
int output[3];

copy(input, unique(input, input + sizeof(input)), output);
0
 
LVL 3

Expert Comment

by:CoolBreeze
Comment Utility
i see thanks, bcladd.
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
Comment Utility
I think it's a maximum of 4, 5 scenarios that should be run for that limited complexity:

1. An empty list and one having only one element
2. A list that had no duplicates
3. A list that has only one value
4. A list that has a few duplicates (normal case)
5. A list that has many duplicates, one at begin and one at end

Regards, Alex


0
 

Author Comment

by:krithi
Comment Utility
thnx
0

Featured Post

6 Surprising Benefits of Threat Intelligence

All sorts of threat intelligence is available on the web. Intelligence you can learn from, and use to anticipate and prepare for future attacks.

Join & Write a Comment

Suggested Solutions

IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
C++ Properties One feature missing from standard C++ that you will find in many other Object Oriented Programming languages is something called a Property (http://www.experts-exchange.com/Programming/Languages/CPP/A_3912-Object-Properties-in-C.ht…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.

763 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

14 Experts available now in Live!

Get 1:1 Help Now