## Amazon Interview Question for Software Engineer / Developers

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

Hi,
We can make use of HashMap for getting the first non repeating character in a string.

We can traverse a string in O(n) time to put entries in our hash map, by storing index of the character in the string as a value and the character as keys.
By taking extra care, Like If there is a duplicate character in the string then just make the value of that character as negative of the previous store index value.

Once iterate the whole string, Now you have to see in the hash map with the least positive value. That will be the index value of the character.

Hope this will help.

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

If the string is of type ascii, then you can have an array of ints of size 128 characters (initialise it to 0). In the first pass of the string, you go through each character and increment the value at the position of the character in the array of ints, for example, for 'b' do a['b'] += 1. In the second pass, for each character see if the entry in the corresponding position of the character is 1. If it is 1 then return that character, else go through the whole string to find such a character.

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

In fact two bits per character would also be enough because we want to just know if it is present once or more than once.

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

Take every character in the string and make an entry in a linkedHashMap with the character as key and number of occurrences as the value. The first with the value 1 is the required character.

or

Traverse the string character wise and have a pointer to denoting a recurrence. Stop when a non-reccurring character in the string is found.

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

we can do it by taking an extra space of 32 byte only, using hashing Tecnique....

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

Am I misunderstanding the problem here? Why are all the solutions presented assuming you have to iterate over the full length of the string? Why can't you just start at element one, and from then on, "if element i != element i+1, then i+1 is the first non-repeating character.

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

The repeating characters need not necessarily be next to each other.

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

Ram, I agree that repeating characters need not necessarily be next to each other but we can sort all the characters according to their ascii value and then compare each character with the next one.

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

Hello Anonymous,

if you solve the problem as you said it's complexity would be worst compared to other's solutions.You have to sort the given stream before you want to do side by side character comparison.To sort stream itself
takes O(nlogn) complexity and after that again you have to go through the complete stream of characters(in the worst case) for which complexity is O(n).So total complexity is O(nlogn)+O(n) i.e O(nlogn) which is obviously not a better idea over other ideas whose complexities are O(2n) i.e O(n).Please correct me if I am heading towards wrong explanation.

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.