Amazon Interview Question
Software Engineer / DevelopersCountry: India
When we take 128 int array, initialized as all 0, are we not increasing space complexity?
@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!
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.
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;
}
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';
}
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;
}
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)
in this solution we are using extra space for tree but in the question they are asking for space complexity of O(1).
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;
}
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.
Also, if your solution involves anything with directly manipulating bits, then you are an asshole because it is unnecessary.
1. Take 128 int array, initialized as all 0
- mag November 06, 20122. 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