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

Comment hidden because of low score. Click to expand.
0

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

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 )

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.

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.

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

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.

Comment hidden because of low score. Click to expand.
0

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

}
}``````

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.

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.