Amazon Interview Question
Country: India
String string = "aabbccdefatafaz";
char[] chars = string.toCharArray();
Set<Character> charSet = new LinkedHashSet<Character>();
for (char c : chars) {
charSet.add(c);
}
StringBuilder sb = new StringBuilder();
for (Character character : charSet) {
sb.append(character);
}
System.out.println(sb.toString());
public String removeDuplicates(String string) {
string = string.toLowerCase();
BitSet bitset = new BitSet(26);
StringBuilder result = new StringBuilder();
for (int i=0;i<string.length();i++) {
char ch = string.charAt(i);
int pos = ch - 'a';
if (!bitset.get(pos)) {
bitset.set(pos);
result.append(ch);
}
}
return result.toString();
}
u can apply counting sort approach, take array of 26 elements, holding the counts of a to z characters, if the counting is zero for that element, add that element to the output, otherwise ignore it...
the hashing approach can take nlogn time (log n for searching in hash table) if I am not wrong..
<pre lang="" line="1" title="CodeMonkey27865" class="run-this">
#include <stdio.h>
#include <stdlib.h>
void removeDups(char* inStr, int len)
{
int strLen = sizeof(inStr)/sizeof(char);
strLen = len;
short* count = (short*)calloc(strLen,sizeof(short));
char res[strLen];
int i=0, j=0;
for(i=0; i<strLen;i++)
{
if(count[inStr[i]]==1)
continue;
else
{
count[inStr[i]] = 1;
res[j++] = inStr[i];
}
}
printf("Given String: %s \n Processed String: %s", inStr, res);
}
int main(void) {
removeDups("HelloWorld", 10);
return EXIT_SUCCESS;
}
</pre><pre title="CodeMonkey27865" input="yes">
</pre>
//O(n)
static String removeDupChars(String val){
int bit[]=new int [256];
String res = "";
for (int i = 0; i < val.length(); i++) {
if(bit[val.charAt(i)]==0){
res+=(""+val.charAt(i));
bit[val.charAt(i)]=1;
}
}
return res;
}
//O(n2)
static String removeDupChars1(String val){
String res = "";
for (int i = 0; i < val.length(); i++) {
int j=i-1;
boolean f =true;
while(j>=0){
if(val.charAt(j--) == val.charAt(i)){
f=false;break;
}
}
if(f)
res+=val.charAt(i);
}
return res;
}
char* RemDup (char* str)
{
char* tmp=new char[10];
bool match = false;
int pos = 0;
while(*str !=0 )
{
int x=0;
while(x != pos)
{
if(*(tmp+x) == *str)
{
match=true;
break;
}
else
{
match=false;
}
x++;
}
if(match == false)
{
*(tmp+pos) = *str;
pos++;
}
str++;
}
*(tmp+pos) ='\0';
return tmp;
}
{
{
{
#include <stdio.h>
#include <stdlib.h>
typedef struct _hash
{
char data;
}hash;
static hash *my_hash;
main()
{
char string[10] = "bananas";
char output[10] = "";
char *ptr = &string;
int idx;
my_hash = malloc(sizeof(hash) * 26);
while(*ptr != '\0')
{
idx = (int)*ptr % 26;
if(my_hash[idx].data != *ptr)
{
my_hash[idx].data = *ptr;
printf("%c\n",*ptr);
}
ptr++;
}
}
}
}
}
#include<stdio.h>
#include<conio.h>
#include<string.h>
void main()
{
char str[20];
char hash[26];
int len, i,t;
clrscr();
printf("Enter the string : ");
scanf("%s", str);
len = strlen(str);
for (i=0;i<len;i++)
{
t = (int)str[i] - 65;
if (str[t] != 1)
printf("%c", str[i]);
str[t] = 1;
}
getch();
}
#define MAX_CHARS 256
char * remove_duplicates(char *s){
int hash[MAX_CHARS],i;
char *source, *destination;
if(s == NULL) return NULL;
source = s;
destination = s;
/* Initialize hash
for(i=0;i<MAX_CHARS; i++) hash[i]=0;
while(*source != '\0'){
/* If this is first time character is encountered */
if(hash[*source] == 0){
hash[*source]++;
*destination = *source;
destination++;
source++;
}
/* We have already processed this character. */
else{
source++;
}
}
/*Imp : Terminate the string */
*destination = '\0';
return s;
}
#include "stdafx.h"
#include <iostream>
#include <string>
using namespace std;
#define MAX_CHARS 256
int search( char* arr, char item );
char* removeDup(char* input)
{
if(input == NULL)
return NULL;
char *res = new char[MAX_CHARS];
// Initialize res
for(int i=0; i<MAX_CHARS; i++)
res[i]=0;
int i = 0, j = 0;
while(input[i] != '\0')
{
if (search(res,input[i]) == 0)
{
res[j++] = input[i];
}
i++;
}
// Imp : Terminate the string
res[j] = '\0';
return res;
}
int search( char* arr, char item )
{
for(int i = 0 ; i < strlen(arr) ; i++)
if(item == arr[i] || item == ' ')
return 1;
return 0;
}
int _tmain(int argc, _TCHAR* argv[])
{
//char* input = "AAA bb CCC";
char input[] = "geeksforgeeks";
cout<<"Output: "<<removeDup(input)<<endl;
return 0;
}
//Remove Duplicate Complexity O(n^2)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main(){
int i,j,flag=0;
char str[]="ABCDESABC";
for(i=0;i<strlen(str);i++){
for(j=0;j<i;j++){
if(str[i]==str[j]){
flag=1;
break;
}
/*else{
printf("%c",str[i]);
}*/
}
if(flag==0){
printf("%c",str[i]);
}
}
return 0;
}
package demo;
/**
*
* @author Ankur
*/
import java.util.Arrays;
public class c1_03 {
private static String str="ABCAAAD";
public static String compact(String str){
String res="";
boolean []arr = new boolean[256];
Arrays.fill(arr, false);
for(int i=0;i<str.length();i++){
int x=str.charAt(i);
System.out.println(x);
if(arr[x]==false){
res+=str.charAt(i);
arr[x]=true;
}
}
return res;
}
public static void main(String args[]){
System.out.println(""+compact(str));
}
}
if characters lies in the range a...z, then we can use following O(n) method without using extra space :
public static void removeDuplicates(char[] str) {
int map = 0;
for (int i = 0; i < str.length; i++) {
if ((map & (1 << (str[i] - 'a'))) > 0) // duplicate detected
str[i] = 0;
else // add unique char as a bit '1' to the map
map |= 1 << (str[i] - 'a');
}
}
(borrowed from k2code.blogspot.in/2014/01/remove-duplicate-characters-in-string.html)
How about this
public static void main(String[] args) {
System.out.println(removeDups("PqQpaabbBBaaAAzzKzUyz11235KKIIppP!QpP".toCharArray()));
}
public static String removeDups(char []input){
long ocr=0l;
int index=0;
for(int i=0;i<input.length;i++){
int val=Math.abs(input[i]-'a');
if((ocr& (1l<<val))==0){
input[index]=input[i];
index++;
}
ocr|=(1l<<val);
}
return new String(input,0,index);
}
O(n) solution with 4 additional variables :
#include<stdio.h>
#include<string.h>
void removeDuplicates(char *);
void removeDuplicates(char *inp)
{
int i=0, j=0, REPEAT_STARTED=0, repeat_count=0;
while(inp[i]!='\0')
{
if(REPEAT_STARTED ==1)
{
inp[i-repeat]=inp[i];
}
if(j==(j | 1<<(inp[i]-'\0')))
{
repeat_count ++;
REPEAT_STARTED =1;
}
j= j | 1<<(inp[i]-'\0');
i++;
}
inp[i-repeat]='\0';
}
int main()
{
char inp[100] = "bananas";
/***** TEST CASES************
//char inp[100] = "abAABBcdbefdghicccc";
//char inp[100] = "ccccc";
//char inp[100] = "\0";
/**********************************
printf (" INPUT STRING : %s\n", inp);
removeDuplicates(inp);
printf (" OUTPUT STRING : %s:\n", inp);
return 1;
}
O(n) solution using bit-manipulation:
#include<stdio.h>
#include<string.h>
void removeDuplicates(char *);
void removeDuplicates(char *inp)
{
int i=0, j=0, REPEAT_STARTED=0, repeat_count=0;
while(inp[i]!='\0')
{
if(REPEAT_STARTED ==1)
{
inp[i-repeat_count]=inp[i];
}
if(j==(j | 1<<(inp[i]-'\0')))
{
repeat_count ++;
REPEAT_STARTED =1;
}
j= j | 1<<(inp[i]-'\0');
i++;
}
inp[i-repeat_count]='\0';
}
int main()
{
char inp[100] = "bananas";
/***** TEST CASES************
//char inp[100] = "abAABBcdbefdghicccc";
//char inp[100] = "ccccc";
//char inp[100] = "\0";
/**********************************
printf (" INPUT STRING : %s\n", inp);
removeDuplicates(inp);
printf (" OUTPUT STRING : %s:\n", inp);
return 1;
}
O(n) approach:
- Anonymous December 17, 20111.) Create empty hashtable
2.) for each letter in word, if letter not contained in hashtable, add letter to output, add to hashtable - otherwise ignore letter
3.) return output
On(n2) approach:
1.) For each letter: go backwards to previous letters in words to see if letter occurred earlier (O(n)), if so ignore, otherwise add to output - this takes n*O(n) = O(n2).