Microsoft Interview Question Interns
Country: India
Interview Type: In-Person
#include<iostream>
#include<string.h>
#include<malloc.h>
using namespace std;
void remove_alternate_dup(char* str)
{
int len=strlen(str);
bool *h=(bool*)calloc(sizeof(bool),len);
int tail=0;
int i=0;
int flag_space=0;
while(i<len)
{
if((str[i]>=65&&str[i]<=90)||(str[i]>=97&&str[i]<=122))
{
if(str[i]>=65&&str[i]<=90)
{
if(h[str[i]]==0||h[str[i]+32]==0)
{
h[str[i]]=1;
h[str[i]+32]=1;
str[tail++]=str[i++];
}
else if(h[str[i]]==1||h[str[i]+32]==1)
{
h[str[i]]=0;
h[str[i]+32]=0;
i++;
}
}
else if(str[i]>=97&&str[i]<=122)
{
if(h[str[i]]==0||h[str[i]-32]==0)
{
h[str[i]]=1;
h[str[i]-32]=1;
str[tail++]=str[i++];
}
else if(h[str[i]]==1||h[str[i]-32]==1)
{
h[str[i]]=0;
h[str[i]-32]=0;
i++;
}
}
}
else
{
if(flag_space==0)
{
str[tail++]=str[i++];
flag_space=1;
}
else
{
flag_space=0;
i++;
}
}
}
str[tail]='\0';
}
int main()
{
char str[]="Today is the day";
remove_alternate_dup(str);
cout<<str<<endl;
return 0;
}
Please find below java implementation:
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class RemoveDuplicatesFromString {
public static void main(String[] args) {
String inputString = "";
String outputString = "";
Map<Character, Integer> dictionary = new HashMap<Character, Integer>();
Scanner sc = new Scanner(System.in);
System.out.println("Please Ente String:");
inputString = sc.nextLine();
for (int i = 0; i < inputString.length(); i++) {
if (!dictionary.containsKey(inputString.toLowerCase().charAt(i))) {
dictionary.put(inputString.toLowerCase().charAt(i), 1);
outputString += inputString.charAt(i);
}
}
System.out.println(outputString);
}
}
you can optimized your code if you use char [] or StringBuilder but It works.
Here are some test cases:
Base case:
1) "abcabc"
2) "abcABC"
3) "abc"
4) ""
5) NULL
6) "aaaaaaaaaa"
7) "aAaAaAaAaAaA"
8) "A very big string which length is bigger than INTEGER.MAX_VALUE ( If possible )"
9) "123123"
10) "!"#$#%&/()?=)(/&%$#"!°¡ "
11) " " (spaces)
12) Is it thread safe? HashMap is not thread Safe, so we can do something to break it maybe
13)
BY THE WAY! You implementation is wrong!
This is about deleting ALTERNATE duplicates, not all the duplicates.
So for Example:
Input: "aaAaaAAA"
Output: "aAaA"
Check my code:
void removeDuplicates(char str[],int n){
int letters [256];
int i = 0;
int index=0;
for(i=0;i<256;i++)
letters[i]=0;
for(i=0; i<n;i++){
char lowerCase = str[i];
if(str[i] >= 65 && str[i] <= 90){
lowerCase +=('a' - 'A');
}
if(letters[lowerCase] == 0){
letters[lowerCase]++;
str[index++]=str[i];
}else{
letters[lowerCase]--; // We want to Alternate
}
}
while(index < i){
str[index++]= 0;
}
}
void removeALTERNATEDuplicates(char str[],int n){
int letters [256];
int i = 0;
int index=0;
for(i=0;i<256;i++)
letters[i]=0;
for(i=0; i<n;i++){
char lowerCase = str[i];
if(str[i] >= 65 && str[i] <= 90){
lowerCase +=('a' - 'A');
}
if(letters[lowerCase] == 0){
letters[lowerCase]++;
str[index++]=str[i];
}else{
letters[lowerCase]--; // We want to Alternate
}
}
while(index < i){
str[index++]= 0;
}
}
my code is up (anonymous)
and it is modified
public String dup(String word)
{
boolean check =false; //"";
HashSet<Character>s = new HashSet<Character>();
String result = "";
for(int i = 0 ; i < word.length();++i)
{
check =s.add(word.charAt(i));
if(check==true)
{
result += word.charAt(i);
}
}
return result;
}
try it soon it will help for your micro interview
- oxymoron November 16, 2013