Amazon Interview Question for Software Engineer / Developers


Country: India




Comment hidden because of low score. Click to expand.
8
of 12 vote

1. Take 128 int array, initialized as all 0
2. In first pass: increment character count in array
3. In second pass: keep two pointers at first character
4. loop until j reaches end
5. keep copying characters at position j to characters at position i if char count at position j is 1
6. if char count at j is > 1 ignore this j and go ahead.
7. finally put null at i+1 position.
8. you are done.

TC: O(n) because you traversed string twice, so O(n) + O(n) = O(2n) = O(n)
SC: O(1)
because constant extra space requirements says that size of extra space should not depend upon size of input just as in our case, no matter how large your input string is going to be, you will always need 128 int's

- mag November 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

When we take 128 int array, initialized as all 0, are we not increasing space complexity?

- AP November 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@AP: as I said, if you take constant amount of storage and that size does not depend your input size, its constant extra space. so if you get string of length 100 or of length 1 million, you are always going to reserve 128 int's.

So we are not increasing time complexity. Taking 2-3 temporary variables as extra space in your code is just a myth about using constant extra space!

- mag November 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

A bit vector of size 256 will do the work!

- Psycho November 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

private static String removeDuplicateCharactersFromWord(String word) {

String result = new String("");

for (int i = 0; i < word.length(); i++) {
if (!result.contains("" + word.charAt(i))) {
result += "" + word.charAt(i);
}
}

return result;
}

- code_mystery February 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 6 vote

Is it duplicate words in a string (string is a sentence) or duplicate characters (when string is a word) ?

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

In the below algorithm, checker works similar to an array of bits. When it does an |= operation, it sets the bit of the particular number.

void retUniqueCharsINPLACE(char* &str) {
	int checker = 0, i =0;
	int c;
	int flag = 0;
	while (str[i] != '\0') {
		c = str[i] - 'a';
		if ((checker & (1 << c)) > 0) {
			str[i] = 0;
			if (flag ==0)
				flag = i;
		} else {

			checker |= (1 << c);
			if (flag != 0) {
				str[flag] = str[i];
				str[i] = 0;
				while (flag <= i && str[flag] != 0) {
					flag++;
				}
			}
		}
		i++;
	}
}

Please comment if anything you feel is wrong.
This algorithm takes O(1) space and inplace but not sure if it is O(n) as there is a loop that is used to find the blanks.

- praveen November 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I suppose it as a string(word) and if I use bitset, it could reduce more memory.
256/8=32 byte only.

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

int main( int argc, char *argv[] )
{
    unsigned char bitmap[256];
    memset( bitmap, 0, 256 );

    unsigned char *ch = (unsigned char *)argv[1];
    while( *ch != '\0' ) {
        if( bitmap[*ch] == '\0' ){
            bitmap[*ch] = 1;
            printf("%c", *ch );
        }
        ch++;
    }
    printf("\n");

    return 0;
}

- CharSyam November 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This may be another solution...I used 128 int array which is used to indicate the duplicity of characters......you can use of ur own choice to reduce wastage of memory usage
Nonetheless this is of O(1) space complexity and O(n) time complexity

void rem_dup(char* str){
	int i[128],k=0;
	for(int j=0;j<128;j++)
		i[j]=0;
	for(int p=0;str[p]!='\0';p++){
		if(i[int(str[p])]==0) {
			str[k]=str[p];
			k++;
			i[int(str[p])]=1;
		}
	}
	str[k]='\0';
}

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

String str = "thisisastring";
StringBuilder sb = new StringBuilder();
BitSet bs = new BitSet(256);
for (int i = 0; i < str.length(); i++) {
	if (!bs.get(str.charAt(i))) {
		sb.append(str.charAt(i));
		bs.set(str.charAt(i));
	}
}
System.out.println(sb.toString());

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

code for removing duplicates in just one pass assuming that input contains only
small letters of English alphabet.

Time complexity = O(n) ; space complexity = O(1).

int remove_dup(char *str)
{
        int c, i = 0;
        /* Assuming all small letters */
        char *temp = str, array[26];

for (i = 0; i < 26; i++)
                array[i] = 0;

i = 0;
        while (*temp) {
                c = *temp++;
                if (array[c - 'a'] == 0) {
                        array[c - 'a'] += 1;
                        str[i++] = c;
                }
        }
        str[i] = 0;
        /* Return new size */
        return i;
}

- arun.edarath November 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 6 vote

using binary search tree time complex. O(n)

use ASCII value of char in string

then take first char of string as root and then apply-
for(i=1;i<strlen(string;i++)
if(ASCII value of char < node)
node->left child=ASCII value of char
if(ASCII value of char >node)
node ->right child=ASCI Value of char
if(ASCII value == parent node)
delete(char from string)  O(1)

- Chandan Singh November 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

in this solution we are using extra space for tree but in the question they are asking for space complexity of O(1).

- sachin November 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

As per above code complexity is o(n) but this code won't eliminate the all duplicates..it will eliminate only first character duplicates.

- venkat November 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Sort the string with 3 way quicksort and find duplicate if the value of the current one is equal to the previous one and delete the current one

- Karthik Vvs November 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can someone tell me why the code from above blog is wrong. I am having hard time understanding it why it is wrong.

void setNthBit(char* a, int pos)
{
    /*quotient gives us the cell number in the array
    which needs to be manipulated. Remember array is zero
    based, so no need to do quotient+1.*/
    int quotient = pos/8;
    int remainder = pos % 8;
    a[quotient] |= 1 << (7 - remainder);
    return;
}

bool isNthBitSet(char* a, int pos)
{
    int quotient = pos/8;
    int remainder = pos % 8;
    /*7 - remainder does the trick and ensures that bit in question
    becomes least significant bit*/
    return ((a[quotient] >> (7 - remainder)) & (0x1));
}

void removeAllDuplicates(char* str)
{
    if (!str || !*str)
        return;
    //Initialize the array with all zeroes
    char hash[32] = {0};
    int emptySlot = -1;
    for (int i = 0; str[i] != '\0'; ++i)
    {
        if (isNthBitSet(hash, str[i]))
        {
            if (emptySlot == -1)
            {
                emptySlot = i;
            }
        }
        else
        {
            if (emptySlot != -1)
            {
                str[emptySlot++] = str[i];
            }
            setNthBit(hash, str[i]);
        }
    }
    if (emptySlot != -1)
        str[emptySlot] = '\0';
    return;
}

- Anonymous November 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If that's the code I wouldn't waste time trying to do anything with it. This problem can be solved with a simple look-up table.

- Asperger November 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Also, if your solution involves anything with directly manipulating bits, then you are an asshole because it is unnecessary.

- Asperger November 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is a look up table. Read code. It is using an array of 32 bytes to see if the character already exists in the array. Which look-up table will be shorter than 32 bytes to represent all ASCII characters. I just compiled the code and tested it. It works like a charm.

- DelMar November 07, 2012 | Flag


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