100 Replies to “Amazon Coding Interview Question – firstNonRepeatingCharacter”

  1. Def es1(string):
    Answer = [ ]
    Check = set()
    For i in string:
    | If i in Answer:
    | Check.add(i)
    | Answer.remove(i)
    | If i not in Check:
    | Answer.append(i)
    | Else:
    | continue
    If Answer != [ ]:
    return Answer[0]
    return "_"

    Would this Algorithm also do the trick?
    Or is it slower?

  2. Proposed solution=
    create empty seenArray
    for each letter, determine if it is already in seenArray,
    if it doesn't already exist, push letter onto [end of] seenArray,
    if if does exist already, remove existing letter from seenArray (don't add current letter to seenArray)
    proceed to next letter for sample.length-1 times
    once end of sample is reached, return seenArray[0]
    Note: I just discovered your channel and I like the content so far. Great job! My software development experience is limited to a few projects and the first few sections of freecodecamp. I haven't covered data structures yet but I've seen a few videos touching on the topic. I still immediately think of stacking with arrays. I could be wrong here but this method seems worth mentioning as I think it should be O(n) with limited space. I'd love it if someone schooled me if I'm misunderstood here. Looking forward to the rest of your content, Nick! keep it coming.

  3. You could use 2 arrays of 26. One to keep count and the other for the first occurrence of a particular character. Initialize each entry of the second one to -1 so that you know if it has been seen if its positive. Then after parsing you can actually sort the second array in constant bcoz its of fixed length. Then you know the order of the first occurrence of every letter in the string.
    Then you just parse it linearly comparing the letter in the second array to the count in the first one. Should be more efficient on average I think for long sequences.

  4. Hi New to coding,
    can someone please tell me whats wrong with this way..
    Create a set of the elements in the string, then use the count() inbuilt function for a sub string within a string ,with a condition if ==1 to return that element..

    The time is O(n) not even O(2n) if im not wrong..
    Could someone please explain as this seems simpler to me thanks..

  5. I would use a hashmap<char, int> where I store the index it occurred at. I would pass over the n values adding elements to the map if a value is already within the map I would set the index to – 1. Then if another element comes up I would know it has already been duplicated. Thus there would be three states; not within, within at index, duplicated. Then I would iterate over the map and find the minimum index and return the character. This would be n time complexity and technically constant space complexity of sizeof(char)*sizeof(int).

  6. "non-repeating" here seems fairly misrepresentative of what you're actually doing given the rules explained. At best, it's super vague. I would prefer the word "unique", myself. I could MAYBE consider "non-repeated"; but "repeating" implies that the letter is the same in the order given. Not really YOUR problem, I guess; and as long as the rules are there it doesn't matter too much. Just seemed weird.

  7. Another way to bring O to n from 2*n is to pushBack all chars with occurrence of 1 in a list and when their occurrence becomes 2 you tell the list to remove object which will have complexity of max(26) for the remove and linear for the integer array. Then you just popFront from the list.

  8. My first thought was to sort the string alphabetically, then you'd know on the first pass if a character occurred only once since they'd be consecutive if it did. It would break strings where the first instances weren't in alphabetical order, but none of the examples

  9. I believe you can achieve O(n)

    For char in char_array:
    If not char_set.get(char):
    Char_set.add(char)
    Else:
    Return char
    Return ‘_’

    Retrieving the char from the char_array would be constant time using a set.

  10. I believe this can be done properly in O(n) or rather O(n + 26) time space and O(26) space complexity. Not sure how accurate I am on the notation there. But using 2 by 26 length arrays, one of count, and one of char. However whether this is a better solution would depend on the string length that you are working with. If it is like in the video, then your solution is likely better but as the string gets longer, the second (worst case) iteration will kill you.

    That being said beyond the theoretical complexity, in hardware, I am not sure how the operations in order to do my solution (comparison branches ect) would play out between the two. Though I think my solution is far better as the strings get much longer. However for short ones, your solution is probably
    better if for no other reason than being simpler to get ones head around.

    Implemented in c++
    :

    char firstNonRepeat(std::string str) {
    char order[26] = {0};
    int count[26] = {0};
    int p = 0;
    for (int i = 0; i < str.length(); i++)
    if(count[str[i] – 0x61]++ == 0) order[p++] = str[i];
    for (int i = 0; i < 26; i++)
    if (count[order[i] – 0x61] == 1) return order[i];
    return '_';
    }

    Note: I am not sure but it feels like I might have left a bit on the table, with respect to having to have 2 arrays rather than one. But given the second both a fixed length and only 26bytes total, I think it'd leave it there as it just gets more difficult to read and know what is going on and the saving of a CONSTANT few bytes, (not n) is eh..

  11. Nicely explained!!! I can only thought of the solution with HashMap but you have given few more as well……nice one!!!

  12. You don't actually need a hashmap. Just create a bit vector associated with the character's ascii value. You don't care how many times it happens, just update a single bit. It will be almost constant time/space since you only need 56 bits to represent the entire a-zA-Z alphabet.

  13. Do they seriously give problems that are this simple? Anyone with a degree in cs can solve this O(n) in 5 minutes right?

  14. All of these solutions are sub-optimal. All you need to do is use a regular map – not a hashmap as the characters are unique so you should not be wasting cpu cycles hashing them (and you should not create a 26-element array because there may not be exactly 26 letters) – and as you make your one single pass through the string you store a list of non-repeating characters. That is an O(n) solution, instead of O(2n).

  15. What about this solution (only loops once):

    string = list('abacabad')

    not_repeating = []

    visited = []

    for i in string:

    if i not in visited:

    not_repeating.append(i)

    visited.append(i)

    else:

    if i in not_repeating:

    not_repeating.remove(i)

    if not not_repeating: # if not_repeating is empty

    print('_')

    else:

    print(not_repeating[0])

    >>> c

  16. I dont know if only Python has count method? In python i would do like this: for loop (for char in string) then if string.count(char) == 1: return char, else string.replace(char,'')

  17. Using a stack operation we can tackle this problem like if the pointer of the pervious char is same it will not push into stack if it's not same it will push into stack and then pop the elements out and print them according to lifo. I guess my logic does also apply.

  18. I don't like the final solution. It really doesn't scale. Just because you have a function called indexOf and lastIndexOf doesn't mean you don't have a loop inside that function. If you have 100,000 long string beginning with "aabbccdd(etc..)xxzzzzzzzz…(to the end)" checking the lastIndexOf(a-x) characters will loop almost the whole string each time – while the hashmap methods loop once in total and then a smaller loop of 26 chars collecting the result.

    But with this solution you really should split the if-check on line 4 into two checks. If indexOf isn't equal to "i", then you can skip looping and find lastIndexOf same character. This is a beginner misstake of optimizing code. I've seen plenty of errors in C where beginners think strlen() is a cheap function.

  19. How about this @Nick.. 🙂

    leastCharacter = (str) => {
    const obj = {};
    let least = 2;
    let leastChar = '';

    for (char of str) {
    if (!obj[char]) {
    obj[char] = 1;
    } else {
    obj[char]++;
    }
    }
    for (char in obj) {
    if (obj[char] < least) {
    least = obj[char];
    leastChar = char;
    }
    }
    return leastChar;
    }

    console.log(leastCharacter('aaabcccdeeef'));

  20. def first_non_duplicate(s):

    d={}

    for i in s:

    if i not in d:

    d[i]=1

    else:

    d[i]+=1

    l = [k for k,v in d.items() if v==1]

    try:

    print(l[0])

    except IndexError:

    print("Nothing")

    first_non_duplicate("aaabcccdeeef")

  21. def fn(s):

    order = []

    counts = {}

    for x in s:

    if x in counts:

    counts[x] += 1

    else:

    counts[x] = 1

    order.append(x)

    for x in order:

    if counts[x] == 1:

    return x

    return None

  22. im 100% new to python, so this was my solution: dict = {}
    char = 'aaabcccdeeef'
    char = list(char)
    for char in char:
    #print(char)
    if char not in dict:
    dict[char] = 1
    else:
    dict [char] += 1
    for char in dict:
    if dict [char] == 1:
    print(char)
    break

  23. Struct that compares the newest value to the stored value, each comparison that's true increments the counter if a new value is found when the counter is 0 then break the loop and return the value within the struct otherwise it will adopt the new value and reset the counter.

    Since the challenge doesnt care about any values after the first non-repeating character we can exit on the first non repeating character and ignore the remaining string.

    Would this work?

  24. You could make the last solution ”0(26)”. That would be nice for big strings but I’m guessing that the indexof functions and lastindex are linear searches so its still slow…

  25. I like the last one. My solution was to take each letter in sequence, and then compare the string length, to the string length with that letter removed. If the result is 1 then you have the first non repeating letter, if not, use the string that has that letter stripped as the new input, and repeat until you get 1 as the difference in string lengths.

  26. create a map of linked lists/arrays for 26 characters, every time we read one char add its index to the corresponding array. O(n) time. then go through the map and for each character check if the corresponding list is of size one, compare the value with the current minimum, and update as needed minimum index. again, O(n). return the resulting string[min index]. Also, we do t need to add every character to the linked list/array, only the first two occurences to keep the time O(n)

  27. Since we are looking for the first character instance only, we can use a regular variable to store that character. It reduces the memory used.

  28. Anyone can come up with a Hashmap, I think that's not what they want as they take space complexity, Check my solution out.
    I have a O(n)+O(26) and better space complexity than a hashmap,

    That is creating an array of size 26 with empty cells, Next go through the entire string using the for loop . And at every element fetch it's ascii value and do modulos operation with the number 65. This will give you a number from 0 to 26 and we use this number as a index of the array we created.

    Now take the value of forloop 'i' which is nothing but the index of that specific character in that string and store it in the array.
    Now if that specific index is already filled with some number instead of empty space then insert -1 indicating it is a duplicate.
    after completing the forloop our complexity is now O(n), Now once again check the array for the smallest number in that array which is nothing but the index of the first non repeating character.

  29. Could we just split every char from string and place them in array and then see how many the same character are in array ?

  30. The most simple and straight forward explanation you could find for this question,
    Can you provide the code for all 4 approaches using C.

  31. I wanted to ask bc my friend told me about it when interviewing, btw this did help me understand what companies want from someone, anyway my friend told me that if they give u a question u already seen and solved that u should tell them, is that a good idea or no??

  32. I think I would just use a hashmap. Each time a letter is found add it to the map and give it an increment. If it is found again increment again. Once the loop is finished check the map for the first entry with only one increment.

  33. Can we use Kmp string matching algorithm to find out patterns then just exclude them to find the 1st non repeating character?

  34. Brute force it with mullti-threading, over engineered 😉
    Could be more elegant with a thread pool in an Executor or something.I didnt compile it, so it is likelly bugged.

    Class main{

    char[] found = new char[122];
    //the index in this array is the ascii decimal int of each char we want to find.
    string searching;
    //to store the string for our threads in the subclass

    public char firstnonrepeating(string s){

    searching = s;

    //prepare 3 threads, ascii 97 to 122 is a-z
    , you can scale it to 1 thread per ascii char if you want.
    Searcher s1 = new Searcher(97,103);

    Searcher s2 = new Searcher(104,111);

    Searcher s3 = new Searcher(112,122);

    //start threads

    Thread t1 = new Thread(s1).start();

    Thread t2 = new Thread(s2).start();

    Thread t3 = new Thread(s3).start();

    ///wait for completion

    t1.wait();

    t2.wait();

    t3.wait();

    //the array will contain counts, find first one with 1

    for (int i = 97; i<=122; i++;)

    if(found[i] == 1)

    return (char) i;

    return '_';

    }

    Class Searcher implements Runnable{

    public int low;

    public int high;

    public Searcher(int llow, int hhigh){

    low=llow;

    high=hhigh;

    }

    public void run() {

    for (int i = low; i<=high; i++;)

    for(int j = 0; j < searching.length(); j++)

    if(i == searching.charAt(j)) //i = ascii code of char we are searching

    found[i]++; //increase count of this char by 1

    }

    }

    }

  35. Bro, i have seen many videos for competitive programming and none of them explained the solutions or even the questions this way. Keep up the good work. Your videos really helped me a lot. 😊

  36. how much time are we given to do this in an interview. Managed to do it in c in about 20 minuts but im a just a first year in computer science

  37. How about a hashmap with a list-like properties where when you encounter each character in the string pass you add it to the hashmap if it doesnt exist, otherwise you say Map.At('e')+=1 (or somesuch) and then you iterated directly on the hashmap contents and stop at the first 1 you meet? This could be marginally quicker, right?

  38. What about LinkedHashMap? They are sorted the way in which you are entering the key-value pair, so we can go with a for-loop in the end just to find the first key that has value 1.

  39. How can I know if the question is asking the first nonrepeating char in alphabetical order or in the string order? eg. if the string is bacc, then is the solution a or b? If I am the only one misunderstanding the question, what am I missing? Thanks in advance.

  40. from the thumbnail i thought this was a trick question as they asked you which character is the first non repeating character and the first a is because there were no a's before that a

  41. Couldn't you just do a for loop with bounds (i = 1; i < string.length() – 1)
    And then return whatever character isnt matching charAt(i + 1) or charAt(i – 1)
    Then have an if statement at beginning to avoid out of bounds errors

  42. If that is a string, you could also split the string while looping through the character. If the splitted result length is 2 then it only appears once and you can immediately return the value without looping through the characters.

  43. I find myself tempted to use recursion here:

    // Find the first non-repeating character in a string

    // Returns null for empty strings and strings with no unique chars

    function findFirstNonRepeatingChar(str) {

    // Get the first character of the string

    let char = str.charAt(0)

    if(!char) return null;

    // Replace all instances of that character

    let repl = str.split(char).join('')

    // Recurse if you replaced more than one character

    if(str.length – repl.length > 1) {

    return findFirstNonRepeatingChar(repl)

    } else return char

    }

  44. The third example with the 26 character array wouldn't work. It would return the lowest character in the alphabet non repeating, not the first.

  45. Rather than traversing it twice O(2N)

    Why can't we first make hashmap through the first loop which would take O(N) and then traverse through hashmap which would be 27.
    So it would be O(N+27)
    Correct me if I'm wrong.

  46. Im going to university right now and study Computer Science however ill drop out and Go to another School where ill get a Bachelor in Software Engineering. Wish me luck

  47. my c# soulution (if i understood the question correctly):

    static void Main(string[] args)

    {

    string source = Console.ReadLine();

    Console.WriteLine(GetFirstNonRepeatedChar(source));

    Console.ReadKey();

    }

    static char GetFirstNonRepeatedChar(string source) => GetNonRepeatedChars(source)[0];

    static char[] GetNonRepeatedChars(string source)

    {

    char[] chars = source.ToCharArray();

    List<char> NonRepeatedChars = new List<char>();

    for (int x = 0; x < chars.Length; x++)

    {

    if (!IsRepeated(chars[x], source))

    NonRepeatedChars.Add(chars[x]);

    }

    return (NonRepeatedChars.Count == 0) ? new char[] { '_' } : NonRepeatedChars.ToArray();

    }

    static bool IsRepeated(char c, string source)

    {

    char[] chars = source.ToCharArray();

    int AmountFound = 0;

    for(int x = 0; x < chars.Length; x++)

    {

    if (chars[x] == c)

    AmountFound++;

    }

    return AmountFound > 1;

    }

  48. I thought of something else. For each letter put you find it has a duplicate put it in an array and precheck each character if it exists in the array then proceed on. If all goes well it will return the requested character. But ik your way is way more effective since arrays take a lot of space in memory and the process will be slower cuz you'll have to precheck everything with an extra for loop. I need to be more comfortable with using boolean lol

  49. Someone please help me understand this. Wouldn't the break statement in the first example (5:21) make it so that if it finds one recurring char it breaks from both loops and returns "_" ?

  50. The last solution isn't good. Please don't recalculate that condition for each character. You should still store what characters you've encountered and only make that check if it's a new character that hasn't been encountered. Otherwise recalculating first and last index again would be inefficient.

  51. Define a array[a…z] . Use for loop and loop through the array. Compare the value of loop and string. In loop use if value in loop appears more than the particular string and loop again if it doesn't appear it gives output.

  52. Won't indexOf() function take some extra time to evaluate the indexes? Or at core it tracks every character in array as soon as it is declared/initialized? If it doesn't, then man interviews are seriously unfair and illogical af

  53. I think array of 26 size is better to use than hash maps, because of internal complexities. Not talking from interview perspective but just real life thing. At least in C, where char's can be taken up swiftly subtracted to get absolute value by AND-ing them, it would be quick. Does interview peeps care about things like this?

  54. I like to waste time… so…

    public static String firstNonRepeatingCharacter(String input) {

    if (input == null || input.isEmpty()) {
    return DEFAULT_VALUE;
    }

    Map<Character, AtomicInteger> cache = new LinkedHashMap<>();
    Set<Character> discarded = new HashSet<>();
    for (Character c : input.toCharArray()) {

    if (discarded.contains(c)) {
    continue;
    }

    int count = cache.computeIfAbsent(c, k -> new AtomicInteger())
    .incrementAndGet();

    if (count > 1) {
    cache.remove(c);
    discarded.add(c);
    }
    }

    if (!cache.isEmpty()) {
    Map.Entry<Character, AtomicInteger> e = cache.entrySet().iterator().next();
    return e.getKey().toString();
    }

    return DEFAULT_VALUE;
    }

  55. The last solution, Using IndexOf and LastIndexOf be an additional 2 traversals for each character ? resulting in a O(n^3) ?

  56. Can somebody tell me what the O(n) is for this Python solution?
    repeating = []

    nonRepeating = []

    for l in string:

    if l in repeating:

    continue

    if l not in nonRepeating:

    nonRepeating.append(l)

    else:

    nonRepeating.remove(l)

    if l not in repeating:

    repeating.append(l)

    if len(nonRepeating) > 0:

    return nonRepeating[0]

    else:

    return "_"

  57. def first_non_repeating_character(string):
    last = ''
    for char in string:
    if string.count(char) == 1:
    return char
    else:
    return '_'

  58. def second(string):

    alpha = "abcdefghijklmnopqrstuvwxyz"

    values = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

    for i in range(len(string)):

    values[alpha.find(string[i])] += 1

    for i in range(len(string)):

    if values[alpha.find(string[i])] == 1:

    return string[i]

    if _name_ == "__main__":

    print(second(str(input("Enter string: "))))

    Before watching, this was my attempt in python. I'm only 17 so I don't expect to be getting a job interview anytime soon but what sort of time limit is given? This took me six minutes is that good?
    Is there a better way to initialize my list?

  59. Amateur coder so I may be WAY off, but it seems to me that this would be the best solution, because you would only have to loop through a single time. The pseudocode:

    Create two empty strings, DUPES and SINGLES
    Loop through the target string character by character. For each character:
    >Does it exist in DUPES? Then skip to next character loop.
    >Does it exist in SINGLES? Then remove it from SINGLES but add it to DUPES, and skip to the next character loop.
    >Append the current character to the right END of the SINGLES string. Loop to the next character.

    Now the leftmost character in SINGLES is your answer. If SINGLES is empty, return the underscore.

    Wouldn't that be the fastest? An O of N, perhaps?

  60. I personally think my solution is far cleaner. https://ideone.com/3ZeYUx. If you use two arrays, one can keep track of the order in which you found the characters

  61. What is the complexity if we use an OrderedDict() , it saves the position on which the key was stored, so maybe it could be done in a worse case time of O(n+26)

  62. Hey @NickWhite
    One quick ques… Doesn't these built-in methods too use some kind of loops which can increase time complexity of this code..?

  63. #include <stdlib.h>
    #include <stdio.h>

    int main(int argc, char* argv[]){
    // find all repeated chars in O(n+26) time complexity and O(1) space
    // complexity, where n is the length of the input string.
    // It can be trivially modified to also output the first
    // repeated char. If the goal is to find only the first repeated char
    // the code is even simpler and the second loop is useless, left as an
    // exercise to the reader. Hint: bit_array should be only 4 bytes long.

    // 52/8 -> 6.5 so get 7*8 bits (actually 64 because of mem alignment)
    u_int8_t bit_array[7]={0};
    u_int8_t c_idx, c_offset; // we'll never go above 26
    char c;
    if (argc == 1){
    printf("Usage: %s string_to_parsen", argv[0]);
    return 0;
    }
    while (c = *argv[1]++){
    // C being C a bit of input sanitizing is a must
    if (c < 'a' || c > 'z')
    continue;
    // c/4 because we want 2*c/8
    c_idx = (c – 'a') / 4;
    c_offset = 2 * ((c – 'a') % 4);
    if (!(bit_array[c_idx] & (2 << c_offset))){
    bit_array[c_idx] |= (bit_array[c_idx] & (1 << c_offset)) << 1;
    bit_array[c_idx] |= 1 << c_offset;
    }
    }
    for (u_int8_t idx=0; idx < 26; idx++){
    c_idx = idx / 4;
    c_offset = 2 * (idx % 4);
    if (bit_array[c_idx] & (2 << c_offset)){
    printf("%c is a repeated charn", idx + 'a');
    }

    }
    return 0;
    }

  64. fuck this noise,ken thompson applied for a job at google and was asked to do an aptitude test!!! the creator of UNIX!

  65. The amount of people that use multiple returns in a single function is quite annoying. Use breaks instead, and only use return at the very end of your code, improves readibility, and improves debugging.

  66. Before watching the video I'd do something like (edit: see reply for errata, I have a small bug in this code and I'm not willing to edit my comment — just show possible bugs, you have to show that you don't panic when bugs like this occur and that you can just fix them):

    char findFirstNonRepeatingCharacter(char *str) {
    char counters[26] = {};
    char found[27] = {};
    int found_count = 0;

    while (*str) {
    counters[*str]++;
    if (counters[*str] == 1)
    found[found_count++] = *str;
    if (counters[*str] > 2)
    counters[*str] = 2; // I don't care if I get more than 2 characters of each kind
    str++;
    }

    // reuse str pointer to iterate through array
    str = found;
    while (*str) {
    if (counters[*str] == 1)
    return *str;
    str++;
    }
    // Nothing found
    return '_';
    }

    When asked about performance, I'd argue linear time, constant space and that it's an online algorithm (I could replace str with an unlimited size character stream and it's just fine, I won't need to actually hold all of the string in the memory; I only take one character, process then forget it).

  67. I have another solution https://stackoverflow.com/are
    /60116476/9654183. Profile same anurag sharma answered below

  68. I'm in 11th grade,but would the answer just using 2 vectors,one to store how many times a character has appeared in the string (in a while loop,till there are elements in the string) and another to remember the order of appearance of the characters and then see which character/characters are non-repeating and then which one of those appeared first?(I'm at min 2.25)

Leave a Reply

Your email address will not be published. Required fields are marked *