Amazon Interview Question Software Engineer / Developers
0of 0 votesRemove duplicates in a string.
Country: United States
Interview Type: In-Person
Did you mean.. Suppose 'fool' is given as input string, you have to convert this to 'fol'
This can be solved by o(n) by taking an extra array of size 256 to count the frequency of the character.
Please find the working function below.
Input : string, length,
Output : string
char* removeDupFromString(char input[], int len)
{
char output[len];
int ASCII[256] = {0};
int i, j;
for(i=0, j=0; i<len; i++)
{
if(ASCII[input[i]] == 0)
{
output[j++] = input[i];
ASCII[input[i]] += 1;
}
else
ASCII[input[i]] += 1;
}
output[j] = '\0';
return output;
}
1) Why are you counting "+=1" when it is a boolean problem (yes/no have we seen the character before)?
2) What do you have the same "ASCII[ ]+=1" part inside if and else part? It is common to both, so move it ouside.
char* removeDupFromString(char input[], int len)
{
char output[len]; <== Created on stack
int ASCII[256] = {0};
int i, j;
for(i=0, j=0; i<len; i++)
{
if(ASCII[input[i]] == 0)
{
output[j++] = input[i];
ASCII[input[i]] += 1; <== same
}
else
ASCII[input[i]] += 1; <== same
}
output[j] = '\0'; <=Will this fit if string has no duplicates?
return output; <== Pointer to stack returned
}
What if the string has no duplicates?
@bigphatkdawg
I m counting the frequency of each word is which is not required for this problem. so we can use as this array as boolean but in 'c' we don't have this datatype so i used int.
Yest "ASCII[ ]+=1" can be put outside the if statement. Like
if(ASCII[input[i]] == 0)
output[j++] = input[i];
ASCII[input[i]] += 1;
And if string has no duplicate char then same string will be returned back.
Fixing your solution (what you meant):
if C, "typedef enum {false=0,true} bool;" before this code
char* removeDupFromString(char input[], int len)
{
char *output=malloc(len+1); <=n+1 space from HEAP
if(!output) exit(1);
bool ASCII[256] = {0};
int i, j;
for(i=0, j=0; i<len; i++)
{
if( !ASCII[input[i]] )
{
output[j++] = input[i];
ASCII[input[i]]=true;
}
}
output[j] = '\0';
return output; //better if you strcpy back to original array
}
Find the remaining bugs...
a caller will call your funciton like this in C
removeDup(string, strlen(string));
then it will seg fault here (or corrupt memory):
output[j] = '\0';
SIMPLE CONCEPT:
for(i=0;i<str[i].length();i++)
{
if(str[i]!=str[i+1])//##AVOIDING DUPLICATES INPLACE IN str[i]##
{
str[i++]=str1[i++]//copying the unique elements of str[i] into new array str1[i]
}
printf("the new array is %s",str1[i])
}
An efficient O(n) solution without using any additional data structure or buffer.
public static String removeDuplicate(String in){
StringBuilder sb = new StringBuilder();
int flag = 0;
in = in.toLower();
for(int i=0; i<in.length(); i++){
int mask = 1<<(int)in.charAt(i);
if(! flag&mask) //char not seen so far
sb.append(in.charAt(i));
flag |= mask;
}
return sb.toString();
}
public static String replaceDuplicates(String s_) {
char[] c = s_.toCharArray();
Map<Character, Boolean> v = new HashMap<>();
for (int i = 0; i < c.length; i++) {
Character a = Character.valueOf(c[i]);
if (v.containsKey(a))
v.put(a, true);
else
v.put(a, false);
}
String noDups = s_;
Character empty = '\0';
for (Character a : v.keySet()) {
if (v.get(a) == false)
continue;
noDups = noDups.replace(a.toString(), "");
}
return noDups;
}
/// O(n), without extra memory
#include <iostream>
using namespace std;
int main()
{
std::string str = "aaaabbbbcdddeee";
std::string::iterator itr1=str.begin();
std::string::iterator itr2=str.begin();
for(; itr2 != str.end(); ++itr2)
{
if(*itr1 != *itr2)
{
*(++itr1) = *itr2;
}
}
str.resize(itr1 +1 - str.begin());
cout << str;;
}
public static void removeDublicate() {
String str = "aaabbddffrrg88gcc8c";
String result = "";
int index;
boolean[] visitedIndexs = new boolean[str.length()];
result = "";
char current;
for (int i = 0; i < str.length(); i++) {
current = str.charAt(i);
index = i;
if (visitedIndexs[i] == true)
continue;
while (true) {
visitedIndexs[index] = true;
index = str.indexOf(current, index + 1);
if (index == -1)
break;
}
result = result + current;
}
System.out.println(str);
System.out.println(result);
}
C++ solution using pointers. Start from the end of the array to copy the optimized array.
#include<iostream>
using namespace std;
void copy_rest(char* index1, char* index2) {
char* temp = index1+1;
int i = 2;
while(*temp != '\0') {
*(index2 +i) = *temp++;
i++;
}
*(index2+i) = '\0';
}
int main (int argc, const char* argv[]) {
char input[] = "abbbccd";
char* index1 = input+sizeof(input)-1;
char* index2 = index1-1;
while(index2 >= input) {
if(*index2 != *index1) {
copy_rest(index1,index2);
index1 = index2--;
} else {
index2--;
}
}
if(index1 != index2) {
copy_rest(index1,index2);
}
cout<<input;
}
An efficient O(n) solution without using any additional data structure or buffer.
- zahidbuet106 December 16, 2013public static String removeDuplicate(String in) { StringBuilder sb = new StringBuilder(); int flag = 0; in = in.toLower(); for(int i=0; i<in.length(); i++) { int mask = 1<<(int)in.charAt(i); if(! flag&mask) //char not seen so far sb.append(in.charAt(i)); flag |= mask; } return sb.toString(); }