Amazon Interview Question


Country: India




Comment hidden because of low score. Click to expand.
4
of 4 vote

O(n) approach:

1.) 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).

- Anonymous December 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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());

- vikk December 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

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();
}

- Anonymous December 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

#include<stdio.h>
#include<string.h>

void compact(char* str){
    int len = strlen(str);
    printf("%d",len);
    int a[26],i;
    char temp[len];

    for(i=0;i<len;i++){
        int t = (int)str[i] - 65;
        if(a[t]!=1){
            printf("%c",str[i]);
        }
        a[t] = 1;
    }
}

void main(){
    compact("BANANAS");
}

- Vijay November 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

here is a good solution for O(n^2)...

puddleofriddles.blogspot.com/2011/04/remove-duplicates-in-string.html

- Anonymous January 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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..

- probs December 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

the hashing approach can take n time (O(1) for searching in hash table)

- Anonymous December 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

Construct a BST from the word,  do pre_order traversal

- Anonymous December 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Are you sure that BST can be constructed with duplicate values?

- rajeshkumar.a December 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

When constructing BST we can ignore the dups.
This again takes nlogn time, I guess.

- Anonymous December 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

<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>

- Anonymous December 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//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;
		
	}

- nmc December 29, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

StringBuilder sb = new StringBuilder();
foreach (var myChar in param)
{
if (!(sb.ToString().Contains(myChar.ToString())))
sb.Append(myChar.ToString());
}

Console.WriteLine(sb.ToString());

- Mohasin January 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Amit January 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void uniq(char *s)
{
    uint32_t t[8] = {0};
    char *d = s;
    while (*s) {
        char c = *s++;
        int i = c >> 5;
        int m = 1 << (c & 31);
        if (!(t[i] & m)) {
            *d++ = c;
            t[i] |= m;
        }
    }
    *d = 0;
}

- psykotic February 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n^2) solution to go along with my bitmap-based O(n) solution:

void uniq(char *s)
{
    for (; *s; s++) {
        char *d = s+1;
        for (char *p = d; *p; p++)
            if (*p != *s)
                *d++ = *p;
        *d = 0;
    }
}

- psykotic February 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void removeDup(char* str)
{
	if(!str)
	return;

	bitset<256> hash;

	int i = 0, j = 0;
	while(str[j])
	{
		if(!hash.test(str[j]))
		{
			str[i++] = str[j];
			hash.set(str[j]);
		}
		j++;
	}
	str[i] = '\0';
}

- Sunny_Boy February 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{
{
{

#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++;
}


}
}
}


}

- Sagar Zaveri September 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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();
}

- Prabu January 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void remove_duplicates(char* str)
{
	hash_set<char> chars;
	int skipcount = 0;
	int i;
	for(i = 0; str[i] != '\0'; ++i)
	{
		if(chars.find(str[i]) != chars.end())
		{
			++skipcount;
		}
		else
		{
			str[i - skipcount] = str[i];
		}
	}

	str[i - skipcount] = '\0';
}

- Anonymous July 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

There's a very easy way to do this:

int x[100];
For (int i=0;i<str.length;i++){
if(x[ str.charAt(i) ]!=-1){
system.out.print(str.charAt(i));
x[str.charAt(i)]=-1;
}

}

- Sasanka September 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- Anonymous November 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- Anand Kumar Singh November 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//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;
}

- Ankur Chaudhary December 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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));
    }
    
}

- Anonymous March 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Approach 1> O(n) and O(1) complexity
Maintain a 26 element array with each element representing a character
Read from start increment the count of each character in the array, if the element count <> 0, dont print

- Gaurav April 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- kinshuk.ram April 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

- Mehdi August 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

4453563rt5t54et 4e 665

- Anonymous September 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

trtrfgfy565465

- 6t546t4e6 September 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- mourya.gudladona September 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- mourya.gudladona September 11, 2016 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More