Microsoft Interview Question Interns
Country: India
Well, we need to make sure we are just dealing with letters, if so, then I agree. but not big harm to use 256 at all. In case we are dealing with unicode, then we just need to change the size of the array and the rest should be ok.
string inputString = "Today is the tough day".ToLower();
int i = 0;
int length = inputString.Length;
while (i != length)
{
for (int j = i + 1; j <= inputString.Length - 1; j++)
{
if (inputString[i] == inputString[j])
{
inputString = inputString.Remove(j, 1);
break;
}
}
length = inputString.Length;
i++;
}
Console.WriteLine(inputString);
}
Very important for micro intern and sde interviews so please try it soon for your benefits.
string inputString = "Today is the tough day".ToLower();
int i = 0;
int length = inputString.Length;
while (i != length)
{
for (int j = i + 1; j <= inputString.Length - 1; j++)
{
if (inputString[i] == inputString[j])
{
inputString = inputString.Remove(j, 1);
break;
}
}
length = inputString.Length;
i++;
}
Console.WriteLine(inputString);
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);
}
}
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;
}
}
int main(){
char str[]="aAaBbBcCcdefgFGZzzzO";
removeDuplicates(str,20);
printf("%s\n",str );
return 0;
}
Output:
mafafito@mafafito-Aspire-4752:~/programming$ gcc microsoft.c -o micro
mafafito@mafafito-Aspire-4752:~/programming$ ./micro
aaBBccdefgZzO
public static String removeDup(String txt){
boolean [] dp=new boolean [26];
char []chs=txt.toCharArray();
int j=0;
int dif=0;
for (int i=0;i<chs.length;++i){
if (chs[i]>='a'&&chs[i]<='z'){
dif=chs[i]-'a';
} else if (chs[i]>='A'&&chs[i]<='Z'){
dif=chs[i]-'A';
}
if (!dp [dif]||chs[i]==' '){
chs[j++]=chs[i];
dp [dif]=true;
}
}
return new String(chs,0,j);
}
def remove_duplicate_chars(st):
seen_chars = set()
actual_len = 0
for s in st:
s_lc = s.lower()
if s_lc not in seen_chars:
seen_chars.add(s_lc)
# replace current character with non-duplicate character
st[actual_len] = s
actual_len += 1
# clean up the extra space caused due to duplicates
# Note the reverse order below
for s in range(actual_len, len(st))[::-1]:
del st[s]
return st
Driver program
print remove_duplicate_chars(list("Today is the day"))
['T', 'o', 'd', 'a', 'y', ' ', 'i', 's', ' ', 't', 'h', 'e', ' ', 'd', 'a', 'y']
['T', 'o', 'd', 'a', 'y', ' ', 'i', 's', 'h', 'e']
public class RemoveAlternativeDuplicate {
public static String removeAlternateDuplicates(String str) {
StringBuffer sb = new StringBuffer();
int charachters[] = new int[256];
char c;
for (int i = 0; i < str.length(); i++) {
c = str.charAt(i);
if (c >= 65 && c <= 90) {
c += ('a' - 'A');
}
if (charachters[c] == 0) {
charachters[c]++;
sb.append(str.charAt(i));
} else {
charachters[c]--;
}
}
return sb.toString();
}
public static void main(String[] args) {
String str = "Today is the day, yet another day";
System.out.println(removeAlternateDuplicates(str));
}
}
import java.util.*;
public class remove_alternate_duplicates{
public static void removeAlternateDuplicates(String str)
{
String output="";
HashSet<Character> hs = new HashSet<Character>();
Character c;
for(int i=0;i<str.length();i++)
{
c = Character.toLowerCase(str.charAt(i));
if(hs.contains(c))
{
hs.remove(c);
}
else
{
hs.add(c);
output=output+str.charAt(i);
}
}
System.out.println(output);
}
public static void main(String [] args)
{
System.out.println("Enter the String");
String str = new Scanner(System.in).nextLine();
removeAlternateDuplicates(str);
}
}
public char[] removeAlternateDuplicates(String str) {
char temp [] = new char [str.length()];
temp[0] = str.charAt(0);
Bool remove = false;
for(int i = 1; i < str.length(); i++)
{
for(int j = 0; j < temp.length(); j++)
{
if(str.charAt(i) == temp.charAt(j))
{
remove = true;
}
}
if(!remove)
{
temp[i] = str.charAt(i);
}
}
return temp;
}
package test;
public class RemoveDuplicates {
/**
* @param args
*/
public static void main(String[] args) {
String s = "Today is the day";
System.out.println(removeDuplicates(s.toLowerCase()));
}
private static char [] removeDuplicates(String s){
char c [] = s.toCharArray();
int [] arr = new int[256];
int i = 0;
while(i<c.length){
if(arr[c[i]]>0){
arraySqueeze(c, i);
}
else{
arr[s.charAt(i)]++;
i++;
}
}
return c;
}
private static void arraySqueeze(char[]c, int i){
for(int j = i+1;j<c.length;j++){
c[j-1]= c[j];
}
c[c.length -1] = '\t';
}
}
public static void main(String[] args) {
String str = "Today is the day";
List<String> modStr = new ArrayList<String>();
StringBuilder sb = new StringBuilder();
for(int i=0; i < str.length(); i++) {
if(i == 0) {
modStr.add(String.valueOf(str.charAt(i)));
sb.append(str.charAt(i));
} else {
if(!modStr.contains(String.valueOf(str.charAt(i)))) {
modStr.add(String.valueOf(str.charAt(i)));
sb.append(str.charAt(i));
}
}
}
if(modStr.size() > 0) {
System.out.println(sb.toString());
}
}
map<char,bool> setmap(){
map<char,bool>mp;
mp[' ']=false;
for(int i=0;i<=25;i++){
mp['A'+i]=false;
// int j=i+32;
mp['a'+i]=false;
}
return mp;
}
string mic1(string& s){
map<char,bool>mp;
mp=setmap();
int pos=-1;
for(size_t i=0;i<s.size();i++){
pos++;
if(!mp[s[i]]){
mp[s[i]]=true;
mp[s[i]+32]=true;
s[pos]=s[i];
}
else{
pos--;
mp[s[i]]=false;
mp[s[i]+32]=false;
}
}
return s.substr(0,pos+1);
}
"mic1.cpp" 54L, 617C
map<char,bool> setmap(){
map<char,bool>mp;
mp[' ']=false;
for(int i=0;i<=25;i++){
mp['A'+i]=false;
// int j=i+32;
mp['a'+i]=false;
}
return mp;
}
string mic1(string& s){
map<char,bool>mp;
mp=setmap();
int pos=-1;
for(size_t i=0;i<s.size();i++){
pos++;
if(!mp[s[i]]){
mp[s[i]]=true;
mp[s[i]+32]=true;
s[pos]=s[i];
}
else{
pos--;
mp[s[i]]=false;
mp[s[i]+32]=false;
}
}
return s.substr(0,pos+1);
map<char,bool> setmap(){
map<char,bool>mp;
mp[' ']=false;
for(int i=0;i<=25;i++){
mp['A'+i]=false;
// int j=i+32;
mp['a'+i]=false;
}
return mp;
}
string mic1(string& s){
map<char,bool>mp;
mp=setmap();
int pos=-1;
for(size_t i=0;i<s.size();i++){
pos++;
if(!mp[s[i]]){
mp[s[i]]=true;
mp[s[i]+32]=true;
s[pos]=s[i];
}
else{
pos--;
mp[s[i]]=false;
mp[s[i]+32]=false;
}
}
return s.substr(0,pos+1);
}
Java Code
Verified
import java.util.ArrayList;
import java.util.List;
public class Dummy2 {
public static void main(String[] args) {
// TODO Auto-generated method stub
//For eg. "Today is the day" -> "Today ishe ". Also give test cases.
String string = "Today is the day";
alterString(string);
}
private static void alterString(String string) {
int length = string.length(),i=0;
List<Character> list = new ArrayList<Character>();
char c,orig;
while(i<length){
c = string.toLowerCase().charAt(i);
orig = string.charAt(i);
if(!list.contains(c)){
list.add(c);
System.out.print(orig);
}
else
list.remove(Object.class.cast(c));
i++;
}
}
}
public static void removeAlternateDupChar(String str){
StringBuilder sb = new StringBuilder();
byte[] flag = new byte[128];
for(int i = 0; i < str.length(); i ++){
if(flag[str.charAt(i)] == 0){
flag[Character.toUpperCase(str.charAt(i))] = (byte)1;
flag[Character.toLowerCase(str.charAt(i))] = (byte)1;
sb.append(str.charAt(i));
}else{
flag[Character.toUpperCase(str.charAt(i))] = (byte)0;
flag[Character.toLowerCase(str.charAt(i))] = (byte)0;
}
}
System.out.println(sb.toString());
}
static string RemoveDuplicateChars(string sourceString)
{
// Store encountered letters in this string.
string resultString = string.Empty;
// Loop over each character.
foreach (char value in sourceString)
{
// See if character is in the table.
if (resultString.IndexOf(value) == -1)
{
// Append to the table and the result.
resultString += value;
}
}
return resultString;
}
static string RemoveDuplicateChars(string sourceString)
{
// Store encountered letters in this string.
string resultString = string.Empty;
// Loop over each character.
foreach (char value in sourceString)
{
// See if character is in the table.
if (resultString.IndexOf(value) == -1)
{
// Append to the table and the result.
resultString += value;
}
}
return resultString;
}
// for O(n)
private static String removeDups( String str ) {
StringBuilder strB = new StringBuilder();
boolean[] charSet = new boolean[128];
for ( int i = 0; i < str.length(); i++ ) {
char c = str.charAt( i );
if ( !charSet[c] ) {
strB.append( c );
charSet[c] = true;
}
}
return strB.toString();
}
Console.WriteLine("Alternating letters string: ");
string input = Console.ReadLine();
var occurences = new Dictionary<int, int>();
var splitInChars = input.ToCharArray();
var output = string.Empty;
splitInChars.ToList().ForEach(x =>
{
int val;
if(occurences.TryGetValue(((int)x), out val))
{
if(occurences[(int)x] == 0)
output += x;
occurences[(int)x]++;
}
else
{
occurences.Add((int)x, 1);
output += x;
}
});
Console.WriteLine("Result: {0}", output);
Console.ReadLine();
java code
public static 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(word.charAt(i)>='a'&&word.charAt(i)<='z')
{
char ch = (char)((char)word.charAt(i)-'a'+'A');
check =s.add(ch);
if(check==true)
{
result += word.charAt(i);
}
}
else if(word.charAt(i)>='A'&&word.charAt(i)<='Z')
{
char ch = (char)((char)word.charAt(i)-'A'+'a');
check =s.add(ch);
if(check==true)
{
result += word.charAt(i);
}
}
else
{
if(check==true)
{
result += word.charAt(i);
}
}
}
return result;
public static 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(word.charAt(i)>='a'&&word.charAt(i)<='z')
{
char ch = (char)((char)word.charAt(i)-'a'+'A');
check =s.add(ch);
if(check==true)
{
result += word.charAt(i);
}
}
else if(word.charAt(i)>='A'&&word.charAt(i)<='Z')
{
char ch = (char)((char)word.charAt(i)-'A'+'a');
check =s.add(ch);
if(check==true)
{
result += word.charAt(i);
}
}
else
{
if(check==true)
{
result += word.charAt(i);
}
}
}
return result;
}
#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;
}
1. Use a hashmap.
2. Scan linearly through given string.
3. For each character check if it is present in hashmap. If it is, then just remove the char from hashmap. Else, add it to hashmap and append it to new string.
4. Return new string.
Java version:
import java.util.HashSet;
import java.util.Set;
public class Main {
public static String removeAlternateDupChars(String str) {
Set<Character> characterSet = new HashSet<>();
char chars[] = str.toCharArray();
int j = 0;
for (int i = 0; i < chars.length; i++) {
if (!characterSet.contains(Character.toLowerCase(chars[i]))) {
chars[j++] = chars[i];
characterSet.add(Character.toLowerCase(chars[i]));
}
}
return new String(chars, 0, j);
}
/*
Write code to remove alternate duplicate characters (case insensitive) from a string in place.
For eg. "Today is the day" -> "Today ishe ". Also give test cases.
*/
public static void main(String[] args) {
System.out.println(removeAlternateDupChars("Today is the day"));
}
}
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) different encoding perhabs?
You missed out 1 simple check, your code remove all the duplicate characters instead of alternative characters !!!! for example below
input : "Today is the day, yet another day"
output : Today ishe,nr ---> this is wrong,
correct output shoud be : Today ishe ,yt anerd
Modify your if condition in for loop like below
if (!characterSet.contains(Character.toLowerCase(chars[i]))) {
chars[j++] = chars[i];
characterSet.add(Character.toLowerCase(chars[i]));
}
else{
characterSet.remove(Character.toLowerCase(chars[i]));
}
public class remove_alternate_duplicates{
public static void main(String args[])
{
String s = "today is the day";
boolean b[] = new boolean[127];
String output="";
for(int i=0;i<s.length();i++)
{
char c = s.charAt(i);
if(b[c])
b[c] = false;
else
{
output=output+c;
b[c] = true;
}
}
System.out.println(output);
}
}
IN C#
public static String RemoveAlterNameChar(String p)
{
if (String.IsNullOrEmpty(p))
{
return null;
}
ArrayList t = new ArrayList();
foreach (char c in p)
{
if (!t.Contains(c))
{
t.Add(c);
}
}
return String.Join("", t.ToArray());
}
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; } } int main(){ char str[]="aAaBbBcCcdefgFGZzzzO"; removeAlternateDuplicates(str,20); printf("%s\n",str ); return 0; }Output:
- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> November 16, 2013mafafito@mafafito-Aspire-4752:~/programming$ gcc microsoft.c -o micro
mafafito@mafafito-Aspire-4752:~/programming$ ./micro
aaBBccdefgZzO