CareerCup

String removeDuplicate(string str)
{
int len=str.Length;
if(len<2) return str;
int tail=1;
for(int i=1;i<len,i++)
{
for(int j=0;j<tail;j++)
{
if(str[i]==str[j])
break;
if(j==tail)
{
str[tail]=str[j];
++tail;
}
}
}
str[tail]='/0';
}

@kumar palike...
were u interviewed in India?which collg are u from?is microsoft hiring in India?

std::string removeDuplicate(char s[])
{ for (int i=0; i< strlen(s) ; i++)
{
for (int j=i+1; j< strlen(s) ; j++)
{
if(s[i] == s[j]){
int count=j;
while(s[count]!=0)
{
s[count] = s[count+1];
count++;
}
}
}
}

std::cout<<s;
return s;

}

Complexity is n^2 for the one that Vipul did , but this can be done using hashtable in O(n)

use 256 bit map to track which character has been occurred. so your hash table wont take that much space, you can do this with 16 byte extra space. and O(n)

void print(string s)
{
    int i; 
    bool V[256];
     
     memset(V,false,sizeof(V));
     
    for(i=0;i<s.size();i++)
      V[(int)s[i]]=true;
      
    for(i=0;i<s.size();i++)
     {
        if( V[(int)s[i]] )
         {
          cout<<s[i];
          V[(int)s[i]]=false;
          
          }
          
          }
          
    return;
    
}
T.C=O(n) & S.C=O(1) as we need 256 booleans for ASCII strings independent of the size of string .

generally they extend this question to the case of unicode characters after u use an "array method"

How to approach it then ?

In case of unicode chars, we can convert them to int using library functions. Can somebody confirm if this is the best approach?

Use HashSet of <char>,get the result in 0(n)

i guess Hashset is one of the methods...guys any other method?

I'll just use std::map.

string s = "This is a test, let's see.";
map<char, int> m;
int index = 0;
for(int i=0;i<s.length();++i)
{
char c = s[i];
if(m[c] == 0)
{
m[c] = 1;
s[index] = c;
++index;
}
}

for(int i=index;i<s.length();++i)
s[i] = ' ';

Use hashing key as char , and value as count, if count more than 1 discard the char

1 #include <stdio.h>
2 #include <string.h>
3
4 void delete_repeated_chars(char * s)
5 {
6 int n = strlen(s);
7 int repeated[128];
8 int i;
9 for(i=0; i<128; i++)
10 repeated[i] = 0;
11 int readpos = 0;
12 int writepos = 0;
13 for(; readpos<=n; readpos++)
14 {
15 if(!repeated[s[readpos]]&&writepos!=readpos)
16 {
17 repeated[s[readpos]] = 1;
18 s[writepos++] = s[readpos];
19 }
20 }
21 s[writepos] = '\0';
22
23 }
24

#include<stdio.h>
#include<string.h>
void rev(char *);
int main()
{
char str[100];
printf("Enter a string\n");
gets(str);
printf("Original string\n");
printf("%s\n",str);
rev(str);
return 0;
}

void rev(char * str)
{
int len;
len=strlen(str);
char hash[256];
int j;
for(j=0;j<256;++j)
hash[j]=0;
char *nstr=(char *)malloc(sizeof(char)*len);
int i;
j=0;
for(i=0;i<len;++i)
{
if(hash[((int)str[i])]==0)
{
hash[((int)str[i])]=1;
nstr[j++]=str[i];
}
}
printf("\n%s\n",nstr);
}

#include<stdio.h>
#include<string.h>
void rev(char *);
int main()
{
char str[100];
printf("Enter a string\n");
gets(str);
printf("Original string\n");
printf("%s\n",str);
rev(str);
return 0;
}

void rev(char * str)
{
int len;
len=strlen(str);
char hash[256];
int j;
for(j=0;j<256;++j)
hash[j]=0;
char *nstr=(char *)malloc(sizeof(char)*len);
int i;
j=0;
for(i=0;i<len;++i)
{
if(hash[((int)str[i])]==0)
{
hash[((int)str[i])]=1;
nstr[j++]=str[i];
}
}
printf("\n%s\n",nstr);
}

char a[20], ch;
int i, j, len = 0;

puts("Enter a string");
while(1)
{
scanf("%c", &ch);
if(ch == 10)
break;
else
{
a[len] = ch;
len++;
}
}
a[len] = '\0';

for(i = 0;i < len; i++)
{
for(j = i - 1; j>= 0; j--)
{
if(a[i] == a[j])
break;
}
if(j < 0)
printf("%c", a[i]);
}

:) it's established that coding the favorite activity amongst most visitors.
A very vital part of the excercise though is test cases for the method.

here are some :

aaaaa
aaaabbbbb
abcd - all unique
abababab - alternating to check if sequence is maintained along with uniqueness
aaaaab aaaa
null

any other suggestions ??

Public Class Helper{
Public Static string removedup(string sentence)
{
return new string(sentence.ToCharArray().Distinct().ToString())
}
}

Main routine to call the function, write in the main :->
{
Console.WriteLine(Helper.removedup("This is a String"));
}
O/p= This a trng

This is using Linq Approach in C#