Amazon Interview Question for SDE1s


Team: IDC
Country: India
Interview Type: In-Person




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

Assuming characters are in ascii range : [0,127], we can use a 64bit unsigned integer with each of its bit representing the flag for ascii character. So instead of using a boolean array of size 128 we can use two 64 bit unsigned integers.

For each character in string, if its corresponding hash-bit is not set -> character has not been seen yet and is unique till that point, so set that hash-bit( mark the character as seen ).

For each character, if its corresponding hash-bit is set -> its a duplicate, set the character as null.

Finally return the string considering only non-null characters.

unsigned long long set_hash( char *ch, int base, unsigned long long hash ) {
	if( ( hash & ( 1ULL << (*ch-base) ) ) == 0 ) {
		hash |= ( 1ULL << (*ch-base) );
	} else {
		*ch = 0;
	}
	
	return hash;
}

char * func( char *s, int len ) {
	unsigned long long hash1 = 0;
	unsigned long long hash2 = 0;
	int i;
	
	for( i = 0; i < len; i++ ) {
		if( s[i] >= 0 && s[i] <= 63 ) {
			hash1 = set_hash( &s[i], 0, hash1 );
		} else if( s[i] >= 64 && s[i] <= 127 ) {
			hash2 = set_hash( &s[i], 64, hash2 );
		}
	}
	
	int new_len = 0;
	
	for( i = 0; i < len; i++ ) {
		if( s[i] != 0 ) {
			s[new_len++] = s[i];
		}
	}
	
      s[new_len] = '\0';

	return s;
}

- Cerberuz April 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you please explain the set_hash function... I am java skilled and have no idea about bit manipulation...

- selva.vedamanickam April 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Java has bitwise operators.
As already stated set_hash() function just set the flag ( which is a bit ) to true if a character has been seen in the string.
Suppose *ch = 'a', ascii value is 97 so base = 64 and hash = hash2
=> *ch-base = 'a'-64 = 97-64 = 43
=> we need to check/set the 43rd bit from right in hash2 variable to true
=> 1ULL << (*ch-base) = 1ULL << 43 that is multiple 1 by 2^43, as this will overflow normal 32 bit integer so we take 1ULL instead of simple 1.
=> hash2 & ( 1ULL << 43 ) will take bitwise AND of the two values and will be true only if 43rd bit from right in hash2 is 1 as 43rd bit from right in ( 1ULL<<43 ) is already 1.
=> If the bit is not 1, set it to be 1 using hash2 = hash2 | ( 1ULL << 43 )

- Cerberuz April 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n^2) solution:
Sort the string using bubble sort and go through the array deleting the character that is same as the previous character in the sorted string. Deleting, in place, a character at position "i" can be achieved by moving right in the string and finding a character that is not the same character being deleted and moving it to the ith place and repeating the process.

O(n) solution:
Use boolean array of length equal to the size of the character set -- O(1) memory
For every character in the string, set the corresponding index in the boolean array to true. -- O(n)
Traverse the given string and delete the character if the boolean value for it is FALSE else set the boolean value to FALSE and move on to next character. This process will preserve the order of characters in the string as we de-dupe it.

O(1) solution:
Not possible as we have to look at each character of the given string before we can conclude it is a duplicate one.

- Karthik April 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

you can do using hashing. Lets assume you have only a...z characters.
Generate 26 prime numbers and keep in an array.

char[ ] nonDuplicateArray;

for(every character C in string ){
if(hash % prime[C-'a'] == 0){
// This means character's prime already multiplied earlier
continue;
}

hash <- hash * prime[C-'a'] ; // This will keep multiplying prime numbers
Add this character to non duplicate array.
}

This exactly O(n) time complexity.

- Digi Digi April 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void removedup(char *str)
{
	char *s = str;
	int last = strlen(str) - 1;

	while (*s) {
		char *q = s+1;
		while (*q) {
			//printf("*s = %c, *q = %c\n", *s, *q);
			if (*q == *s) {
				*q = str[last];
				str[last--] = '\0';
			}
			else 
				q++;
		}
		s++;
	}
}

- Sangeet Kumar April 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi Kumar,
Your code copies characters from last. This changes the string.
I think you should use a temporary string and copy characters from the point where the character is repeating till end.

Nandan

- Nandan Shantharaj June 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

copying to temporary variable is not required. move all characters one position closer, whenever a repeating character is found.

- Anonymous June 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can do it by Ex-Or of all the characters in a string.

- Durgesh April 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

That's interesting, can you please explain your approach ?

- Cerberuz April 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;
class RemoveDup 
{
	public static void main(String[] args) 
	{
		String S="aabbcd";
		char arr[]=S.toCharArray();
		int tail = 1;
		int j;
		for (int i = 1;i<arr.length;i++)
			{
			
			for(j =0;j<tail;j++)
				{
				
				if (arr[j] == arr[i])	
					break;
				}
			if(j==tail)
				{
				
				arr[tail]= arr[i];
				tail++;
			     }			
	     	}
			for(int i=tail;i<arr.length;i++)
		{
		arr[i]=0;
		}
		for (int i=0;i<arr.length;i++)
			System.out.print(arr[i]);

	}
}

- Vaibhav Agarwal July 30, 2013 | 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