Microsoft Interview Question
Software Engineer in Tests#include <string.h>
typedef char bool;
#define true 1
#define false 0
void removeDup(char * str) {
int tgt = 0, i = 0;
bool charTable[256] = {false};
if(!str) return;
for(i = 0; str[i]; i++) {
if(!charTable[str[i]]) {
charTable[str[i]] = true;
str[tgt++] = str[i];
}
}
str[tgt] = 0;
return;
}
int main() {
char * str = (char *);
strcpy(str,"hello world!");
removeDup(str);
}
void removeduplicates(char *str)
{
char *str1;
int hash[256];
int j=0,index=0;
for(i=0;i<255;i++)
hash[i]=0;
for(i=0;i<strlen(str);i++)
hash[str[i]]++;
while(str[j])
{
if(hash[str[j]]>1)
continue;
else
str1[index++]=str[j];
}
str1[index]='\0';
cout<<"the unduplicated string is "<<str1;
}
char* RemoveDuplicates(char* inputString)
{
if(!inputString)
return NULL;
int len = strlen(inputString);
int src=0;
int dest=0;
while (src<len) {
if(inputString[src] != inputString[src+1]){
inputString[dest++] = inputString[src++];
}
else {
src++;
}
}
inputString[dest] = '\0';
return inputString;
};
Here is simple solution for this..
public static void removeDup(char[] str)
{
if (str==null) return;
int len=str.lenght()l
if(len<2) return;
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[i];
++tail;
}
}
str[tail]=0;
}
}
public class RemoveDup {
public static void main(String[] args) {
String str=new String();
System.out.println("Enter the String");
Scanner s=new Scanner(System.in);
str=s.nextLine();
int[] ch=new int[256];
String str1 = new String();
for(int i=0;i<str.length();i++){
if(ch[str.charAt(i)]==0)
{
ch[str.charAt(i)]=1;
str1=str1 + str.charAt(i);
}
else{
ch[str.charAt(i)]++;
}
}
System.out.print(str1);
}
}
Logic:
Read each charecter,
Hash it to a bitmap with each character being hashed to its corresponding bit position.
assumption:
all values in lower case
Please point out if i have made any pointer mistakes
- saurabh.comps November 08, 2009