Amazon Interview Question Software Engineer / Developers
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.
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.
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.
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.
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.
Hi,
- Manpreet February 01, 2013We 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.