Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
Solved

# Remove Duplicates

Posted on 2004-04-26
Medium Priority
441 Views
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
Question by:krithi
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• Learn & ask questions
• 5
• 4
• 3
• +3

LVL 86

Expert Comment

ID: 10921696
>>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

ID: 10921703
Oops, the last loop should be

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

output[i] = *it;
}
0

Author Comment

ID: 10921965
thnx but can u just write this in simple c or c++.

thnx
krithi
0

LVL 86

Accepted Solution

jkr earned 129 total points
ID: 10922091
>>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

ID: 10922221
I meant withou using STL
0

LVL 39

Expert Comment

ID: 10922259
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

ID: 10922280
Should be

}
else
last = input[i];

Regards, Alex
0

LVL 39

Assisted Solution

itsmeandnobodyelse earned 123 total points
ID: 10922323
>>  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

ID: 10922406
will this work?

void RemoveDuplicates(struct Node* pHead)
{
//pHead - Beginning of the sorted list.
{
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

LVL 11

Assisted Solution

bcladd earned 123 total points
ID: 10922581
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

ID: 10922938
i think this will do the job

{
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

ID: 10923923
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

ID: 10925990
but i thought he says 10 tests?
how do you use only 10 tests for a general problem?
0

LVL 11

Expert Comment

ID: 10927436
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

ID: 10927932
#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

ID: 10927966
i see thanks, bcladd.
0

LVL 39

Expert Comment

ID: 10928075
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

ID: 10934121
thnx
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generatâ€¦
This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why tâ€¦
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relatâ€¦
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
###### Suggested Courses
Course of the Month7 days, 22 hours left to enroll

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

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