Yahoo Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
inplace removal. C++ code.
void inplace_remove_dupes(char *s) {
char *write = s;
char *read = s;
bool seen[256];
for (int i = 0; i < 256; i++) {
seen[i] = false;
}
while (*read != '\0') {
if (seen[*read]) {
read++;
continue;
}
seen[*read] = true;
*write = *read;
write++; read++;
}
*write = '\0';
}
void remote_duplicates(char* str) {
int tbl[256] = {0};
char* new_pos = str;
for (char* p = str; *p; p++) {
if (!tbl[*p]) {
tbl[*p] == 1;
*new_pos = *p;
new_pos++;
}
}
*new_pos = 0;
}
ruby sucks. some other import redefined split to mean something other than what you expect.
void duplicate(char *str)
{ int i,j,k=0;
int flag=1;
char *str1;
char ch;
i=0;
while(str[i]!='\0')
{
ch=str[i];
j=0;
flag=1;
if(!str1[0])
{
str1[k]=ch;
k++;
continue;
}
while(str1[j]!='\0')
{
if(str1[j]==ch)
{
flag=0;
break;
}
else if(str1[j]!=ch)
{
flag=1;
}
j++;
}
if(flag)
{
str1[k]=ch;
k++;
}
i++;
}
str1[k]='\0';
sort(str1);
}
void duplicate(char *str)
{ int i,j,k=0;
int flag=1;
char *str1;
char ch;
i=0;
while(str[i]!='\0')
{
ch=str[i];
j=0;
flag=1;
if(!str1[0])
{
str1[k]=ch;
k++;
continue;
}
while(str1[j]!='\0')
{
if(str1[j]==ch)
{
flag=0;
break;
}
else if(str1[j]!=ch)
{
flag=1;
}
j++;
}
if(flag)
{
str1[k]=ch;
k++;
}
i++;
}
str1[k]='\0';
sort(str1);
}
public class RemoveDeuplicate {
public static void main(String[] args) {
String sat = "abracadabra";
Removeduplicates(sat);
}
public static void Removeduplicates(String sat){
String input1=sat;
String output="";
for(int i=0;i<input1.length();i++){
int count=0;
for(int j=0;j<output.length();j++){
if(input1.charAt(i)==output.charAt(j)){
count++;
}
}
if(count==0){
output=output.concat(String.valueOf(input1.charAt(i)));
}
}
System.out.println(output);
}
}
If we are allowed to use additional data structure like a Hash table, we can do this easily like this:
The below is in C#...
public static string RemoveDupCharsFromString(string str)
{
if (str == null)
return null;
string newstr = "";
Hashtable ht = new Hashtable();
char[] ca = str.ToCharArray();
int i = 0;
for (i = 0; i < ca.Length; i++)
{
if (ht.ContainsKey(ca[i]))
{
continue;
}
else
{
ht.Add(ca[i], true);
newstr = newstr + ca[i];
}
}
return newstr;
}
#include <map>
#include <string>
using namespace std;
int main()
{
map<char,int> char_map;
string s;
char c;
cin>>s;
string::iterator str_iter=s.begin();
while(str_iter!=s.end())
{
c=*str_iter;
map<char,int>::iterator map_iter=char_map.find(c);
if(map_iter!=char_map.end())
{
map_iter->second++;
}
else
{
char_map[c]=1;
cout<<c;
}
str_iter++;
}
}
#include <map>
#include <string>
using namespace std;
int main()
{
map<char,int> char_map;
string s;
char c;
cin>>s;
string::iterator str_iter=s.begin();
while(str_iter!=s.end())
{
c=*str_iter;
map<char,int>::iterator map_iter=char_map.find(c);
if(map_iter!=char_map.end())
{
map_iter->second++;
}
else
{
char_map[c]=1;
cout<<c;
}
str_iter++;
}
}
#include <iostream>
#include <string>
using namespace std;
void remove(string & str, int index)
{
for(int i = index; i < str.size(); i++)
str[i] = str[i + 1];
}
string removeDeplicated(string str)
{
for(int i = 0; i < str.size(); i++)
for(int j = i + 1; j < str.size(); j++)
if(str[i] == str[j])
remove(str, j);
return str;
}
int main()
{
cout << removeDeplicated("abracadabra") << endl;
return 0;
}
import java.util.Iterator;
import java.util.LinkedHashSet;
import org.junit.Assert;
import org.junit.Test;
public class RemoveDuplicateChallenge {
@Test
public void test() {
Assert.assertTrue(removeDuplicate("aaabbb").equals("ab"));
Assert.assertTrue(removeDuplicate("abcabc").equals("abc"));
Assert.assertTrue(removeDuplicate("abracadabra").equals("abrcd"));
}
public String removeDuplicate(String str) {
LinkedHashSet<Character> set = new LinkedHashSet<Character>();
char[] array = str.toCharArray();
for(char c : array) {
set.add(c);
}
StringBuilder sb = new StringBuilder();
Iterator<Character> it = set.iterator();
while (it.hasNext()) {
sb.append(it.next());
}
return sb.toString();
}
}
Python 3 w/o using hash method
a = "abracadabra"
def removeDup(s):
if len(s) == 0 or len(s) == 1:
return s
myLs = list(s)
noDup = []
"""first element is unique until it is not"""
i = 0
noDup.append(myLs[i])
myLs.remove(myLs[i])
len_to_go = len(myLs)
while(len_to_go > 0) :
#print(myLs)
print(noDup)
len_to_go = len(myLs)
j = 0
while j < len_to_go:
if noDup[i] == myLs[j]:
print("remove: '{0}' at index '{1}'".format(myLs[j],j))
myLs.remove(myLs[j])
j += 1
len_to_go = len(myLs)
if (len(myLs) > 0):
noDup.append(myLs[0])
myLs.remove(myLs[0])
i += 1
else:
break
return ''.join(noDup)
print(removeDup(a))
{
public static string removeDuplicates( string s)
{
char[] charArray = s.ToCharArray();
int[] seen = new int[256];
int numUniquelelements = 0;
int i = 0;
string ret;
foreach ( char c in s)
{
if (seen[c] == 0)
{
seen[c] = 1;
charArray[i] = c;
i++;
numUniquelelements++;
}
}
ret = new string(charArray);
return ret.Substring(0, numUniquelelements);
}
}
def removeDuplicatesInPlace(s):
##Strings are immutable so we must use a list
l = [c for c in s]
r = i = 0
dict = {}
for el in l:
if dict.get(el) is None:
dict[el] = True
l[r] = l[i]
r = r + 1
i = i + 1
return "".join(l[:r])
if __name__ == "__main__":
s = raw_input()
print removeDuplicatesInPlace(s)
#include <iostream>
#include <map>
#include <string.h>
using namespace std;
void deleterepeatingchar(const char *);
int main()
{
const char str [] = {"abracadabra\0"};
deleterepeatingchar(str);
return 0;
}
void deleterepeatingchar(const char *str) {
string str1 = "";
map<char,int> numCount;
map<char,int>::iterator iter;
for ( int i = 0 ; i < strlen(str) - 1;i++) {
iter = numCount.find(str[i]);
if( iter != numCount.end()) {
numCount[str[i]]++;
}
else {
numCount[str[i]]++;
str1 += str[i];
}
}
cout << "Unique Character:" << str1;
}
#include <iostream>
#include <map>
#include <string.h>
using namespace std;
void deleterepeatingchar(const char *);
int main()
{
const char str [] = {"abracadabra\0"};
deleterepeatingchar(str);
return 0;
}
void deleterepeatingchar(const char *str) {
string str1 = "";
map<char,int> numCount;
map<char,int>::iterator iter;
for ( int i = 0 ; i < strlen(str) - 1;i++) {
iter = numCount.find(str[i]);
if( iter != numCount.end()) {
numCount[str[i]]++;
}
else {
numCount[str[i]]++;
str1 += str[i];
}
}
cout << "Unique Character:" << str1;
}
#include <iostream>
#include <map>
#include <string.h>
using namespace std;
void deleterepeatingchar(const char *);
int main()
{
const char str [] = {"abracadabra\0"};
deleterepeatingchar(str);
return 0;
}
void deleterepeatingchar(const char *str) {
string str1 = "";
map<char,int> numCount;
map<char,int>::iterator iter;
for ( int i = 0 ; i < strlen(str) - 1;i++) {
iter = numCount.find(str[i]);
if( iter != numCount.end()) {
numCount[str[i]]++;
}
else {
numCount[str[i]]++;
str1 += str[i];
}
}
cout << "Unique Character:" << str1;
}
public static String removeDuplicates(String input) {
//1) Doing it in O(n)
//2) Maintaining the order
//3) Takes O(n) space but then if it needs to be done in place then we need to take chararray which also takes O(n);
LinkedHashSet<Character> visited = new LinkedHashSet<Character>();
for(int i = 0; i<input.length(); i++){
if(!visited.contains(input.charAt(i))){
visited.add(input.charAt(i));
}
}
StringBuilder sb = new StringBuilder();
Iterator<Character> it = visited.iterator();
while(it.hasNext()){
sb.append(it.next());
}
return sb.toString();
}
public static String removeDuplicates(String input) {
//1) Doing it in O(n)
//2) Maintaining the order
//3) Takes O(n) space but then if it needs to be done in place then we need to take chararray which also takes O(n);
LinkedHashSet<Character> visited = new LinkedHashSet<Character>();
for(int i = 0; i<input.length(); i++){
if(!visited.contains(input.charAt(i))){
visited.add(input.charAt(i));
}
}
StringBuilder sb = new StringBuilder();
Iterator<Character> it = visited.iterator();
while(it.hasNext()){
sb.append(it.next());
}
return sb.toString();
}
public static String removeDuplicates(String input) {
//1) Doing it in O(n)
//2) Maintaining the order
//3) Takes O(n) space but then if it needs to be done in place then we need to take chararray which also takes O(n);
LinkedHashSet<Character> visited = new LinkedHashSet<Character>();
StringBuilder sb = new StringBuilder();
for(int i = 0; i<input.length(); i++){
if(!visited.contains(input.charAt(i))){
visited.add(input.charAt(i));
sb.append(input.charAt(i));
}
}
return sb.toString();
}
Updated the approach and removed the iterator
C/C++ based simple solution for in place duplicate char removal. An extra space has been used to store ASCII value of char.
void replace( char* S)
{
bool cArray[256];
for ( int index =0; index < 256 ; index++)
{
cArray[index] = false;
}
int start = 0;
char * ptr = S;
while ( *ptr != '\0')
{
if(! cArray[*ptr] )
{
cArray[*ptr] = true;
S[start] = *ptr;
start++;
}
ptr++;
}
S[start] = '\0';
cout <<"OUT:"<< S<<endl;
}
private static String removeDuplicate(String str) {
StringBuffer sb = new StringBuffer();
char[] array = str.toCharArray();
int[] letter = new int[256];
for (int i = 0; i < array.length; i++) {
int ascii = (int)array[i];
if(letter[ascii]==0){
sb.append(array[i]);
} letter[ascii] = 1;
}
return sb.toString();
}
In java:
- djmclaugh July 11, 2014