Amazon Interview Question
Country: United States
Looks like question itself is wrong, as first character character of any string will always be unique. I think question should be first non-repeated charater in the string, and that can not be done in less then O(n).
@Sachin: I guess the person who asked this question meant the same i.e. non-repeated character or a character unique to the whole string.
@Barney: I think I agree with anonymous on this one. It doesn't seem possible to do in o(logn).
It's of course not possible to do this in less than O(n). Consider the character the string starts with. If it is not found anywhere else, it's the answer. But there can be no way to know whether it is found anywhere else or not until you inspect every other character.
@Manan: why is this question necessarily fake? Interviewers ask stupid things every now and then.
@Manan, this is definitely not a fake question at all, i have been asked by amazon the same question on this Thursday.
Look at the question they have framed me,
Q1) Write an algorithm that when given a string, will return the first unique character in that string with the best possible runtime efficiency.
Examples:
tweet => w
tool => t
loot => l
toto => null
and for those who are wondering how this algorithm can be written with O(log n) complexity then trie is the solution i guess which i couldn't think of at the time of interview. :(
Log n is definitely not possible as you will have to go through the whole string at least once to know the character is unique.
Absolutely agreed with Manan. I really can't see how there's any debate. Isn't it obvious by elementary logic?
yes we can do it.
create a suffix tree like structure. actually builld a BST like tree using ascii value of characters as the key. read fisrt letter, insert into tree. Read second character, compare it with tree top. If equal, del that node, else depnding upon the ascii value, move it left or right. That way at the end of reading all the characters you will get tree root as the first unique character. TI will require, (n + log n ) time and space complexity would be in worst case equal to n.
are you sure time complexity is O(log n)? How you determine a character is unique without traversing the full string?
- Anonymous July 18, 2012