Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: Phone Interview
well.. i know O(n)=O(n* 1/2 ), cause 1/2 is a constant.. but its significantly better that n iterations.. and i dont think you could do it in O(1)
I think the question is flawed. Here is my logic.
1. If you need to find whether the string is a palindrome or not (and not guess it), you need to touch every character in the string to give the correct answer.
2. By touching every char in the string, the time complexity has to be order n where n is the length of the string.
3. it does not matter if you half the loops and touch two chars at a time. In the above comment regarding O(n*1/2), you are still touching the whole string and not half of it.
So finding whether a string is a palindrome in less than O(n) is a flawed question.
1. Maintain the current possible pivot index (for either odd or even count of current elements) - @pidx
2. With each new coming char (@ch) at index @i and as long as a pivot index is set (@pidx != -1), check
to see if it can be an element in a palindromic sequence up to now.
Check is done using the idea of whether the current element is the same
as the one equaly distant as the current one is from the pivot index.
If the two elements are the same and the first element is at index 0, then we
have a palindrome with this current char.
If the current element does not contribute to a palindromic sequence, then
reset the previous @pidx (if any set) and check whether this one can be a
new pivot index.
The time complexity of the above algorithm is O(1) sinece we compare the current
char only with its potential match coming before it.
Not true in step of new pivot. Anyone between old pivot and new char may be the new pivot. Eg. BaaaaaB
void add_char(char c) {
// pointers to keep track of odd and even-length palindromes
static int odd = 0, even = -1;
static int idx = 0; // current position in the stream
static char stream[256];
static bool same_char = true;
stream[idx] = c;
stream[idx+1] = '\0';
if(same_char && idx > 0 && c != stream[idx-1]) {
same_char = false;
}
if(same_char)
printf("palindrome: %s\n", stream);
if(odd >= 0 && stream[odd] == c) {
odd--;
if(odd < 0) {
printf("odd palindrome: %s\n", stream);
odd = idx - 1;
}
} else
odd = idx - 1;
if(even >= 0 && stream[even] == c) {
even--;
if(even < 0) {
printf("even palindrome: %s\n", stream);
even = idx;
}
} else
even = idx;
idx++;
}
int main() {
const char *s = "aaaaaabaaaaaa";
for(int i = 0; s[i] != 0; i++)
add_char(s[i]);
return 0;
}
i really failed to understand your logic could you please expline it throgh an algo or an example
logic is quite simple: in any given moment of time stream[cmp_pos] must match with the next incoming character stream[idx] to grow a current palindrome sequence. When 'cmp_pos' descends below 0, this indicates that we found a palindrome seq.
if stream[cmp_pos] does not match with stream[idx], we reset
cmp_pos either to 'idx' or 'idx-1' (ie the index of the last incoming character)
@algogeek: you are right, for that matter I use a flag 'same_char' which remains 'true' until we get the first non-repeating character from the stream. please see the modified code
This is not correct. I think this is a fundamentally flawed approach and minor code tweaks aren't going to fix it. Consider a test case like this: bcacacb. What will your algorithm do here? If I understand correctly, your algo would first start matching things on bcac. It will then expect b to complete the palindrome bcacb. When it instead gets a, it will start matching from the back again. So then there's no way it'll see that the next two characters complete the palindrome. The problem is that the algorithm was focusing on checking one possible palindrome when the second part of the real palindrome was already forming.
_
I myself cannot find an O(1) time and O(1) extra space approach that is deterministically correct, and I actually doubt that one exists. I've come up with an O(1) space, O(1) time method involving rolling hashes, but this may not be strictly speaking guaranteed to work. With O(logN) time and space I could devise a probabilistic method that guarantees correctness and the time and space bounds in the expectation (but not not determninistically). I think with just O(1) extra space we're definitely pretty crippled here. However, O(logN) space is very small. If I want, say, 10logN bytes, if you give me a constant buffer of, say, 4KB, I can handle inputs larger than the number of atoms in the universe.
Well of course no such inputs would be able to be stored or processed on any machine, I mean from the algorithmic perspective...
Use a variant of rabin karp algorithm.
Each character update is O(1).
maintain a hash for the first and second half
When a new (odd) character is added only the second part moves just like in every pattern matching algorithm.
When a new (even) character is added
a. the first and second part are added a character.
O(1) per update.
O(n) average time for entire sequence.
1)Maintain two hashes, one for upper half and other for lower half.
2)Maintain the count of characters.
3)When a new element is added, check the new count.
4)Wen the count is two,both the halfs will be having hash value of one characted each.
5)When a third element is added, check the count.
6)Since the count is odd,remove the hash value of first character in 2nd hash and make that character middle element.
7)Add the hash value of newly entered character to 2nd hash.
8)When a fourth element is added,add the hash value of middle character to first hash and add the hash value of newly entered character to 2nd hash.
Please let me know if you find any flaw in this approach.
Thanks
- Siva Krishna May 21, 2012i=0; while(i<=n/2) { if(a[i]==a[n-i]) i++; else return 0; } if(i>n/2) return 1;