## Amazon Interview Question

Country: United States

Comment hidden because of low score. Click to expand.
2
of 2 vote

are you sure time complexity is O(log n)? How you determine a character is unique without traversing the full string?

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

they just asked that can we solve it in O(logn) time .

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

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).

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

@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).

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

Stop posting fake questions.

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

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.

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

bhak aisa nhi ho sakta..bache ki jan le lo..

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

@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. :(

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

BullS** !
Trie will not give O(log(N)) !

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

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.

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

Absolutely agreed with Manan. I really can't see how there's any debate. Isn't it obvious by elementary logic?

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

How the trie will help in getting the soln ? Could u explain it ...

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

How the trie will help in getting the soln ? Could u explain it ...

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

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.

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

I think your algm wont assist in getting first unique letter. Your algm wont work for the word TWEEWWT as W will come as root element but it is repeated. Please verify.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

bitwise xor all the characters in the string.

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

Won't work. Something could be repeated 3, 5, 7, etc. times and influence the XOR.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

MapReduce algorithm.
Described nicely here in algo
The are many question on this site whose solution is MapReduce,
Eg the twitter trending topic etc..

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

Hi, could you explain your idea on your code , your code is actually doing a loop with O(n) , not a Log n way .

thanks
hongtao

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.