Amazon Interview Question
SDE1sTeam: IDC
Country: India
Interview Type: In-Person
Can you please explain the set_hash function... I am java skilled and have no idea about bit manipulation...
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 )
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.
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.
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++;
}
}
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
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]);
}
}
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.
- Cerberuz April 11, 2013