Google Coding Interview Question and Answer #1: First Recurring Character



Find the first recurring character in the given string!

A variation of this problem: find the first NON-recurring character. This variation problem and many others are covered in my Udemy course, 11 Essential Coding Interview Questions: https://www.udemy.com/11-essential-coding-interview-questions/?couponCode=GOOGLE1

(You’ll get a discount through the above link.)

source

Avatar of CS Dojo

By CS Dojo

46 thoughts on “Google Coding Interview Question and Answer #1: First Recurring Character”
  1. Hi guys! I actually made a mistake in my first solution.. sorry. The first recurring character in ABBA should be B, and not A. Also, I should've used a set in my second solution. The time complexity is the same either way, though.

  2. Completely new to programming but can someone explain why this isn't efficient?
    def recurrence(x):

    empty_list = []

    for letter in x:

    if not letter in empty_list:

    empty_list.append(letter)

    else:

    return letter

  3. My weapon of choice is Python and this is what I came up with… Copy and paste and try it out.
    string1 = 'ABCA'

    string2 = 'BCABA'

    string3 = 'ABC'

    def first_duplicate_generator(group):

    duplicate = []

    singles = []

    for letter in group:

    if letter not in singles:

    singles.append(letter)

    elif letter in singles:

    duplicate.append(letter)

    if duplicate:

    first_duplicate = duplicate[0]

    print(first_duplicate)

    else:

    print('There are no duplicates in this string.')

    first_duplicate_generator(string1)

    first_duplicate_generator(string2)

    first_duplicate_generator(string3)

  4. For anyone who has done technical interviews I have a question now obviously this question is checking to see if you can find a duplicate value which since you're only looking for a minimum of one duplicate you can use a set and you don't have to worry about storing an additional key and I get that. However during an interview it seems like since we went to talk about flexibility and scalability and other concepts from a system hearing perspective you might want to consider a hash map instead of a hash set just so that you can consider flexibility or scalability in the future because in the future you might want to know the actual number of frequencies for each duplicate so if I solved this question using a hash map without approach would that look good or bad? It doesn't add anything to time complexity and yes there is a trade-off by adding additional space complexity but it does allow for more flexibility

  5. Why do you have to scan the string from the first character when you are passed it, for example if you are in the third position then directly check it with fourth position, you need not to go from first and second positions because you already checked the occurrency of first and second earlier, though the time complexity will be changed accordingly

  6. the solution i came up with is creating an empty list then looping through each character of the word once if the character is not in the list then you append it into it if it is then you return it.
    this is the code:
    string = "DBCABA"

    def get_recurring_char(word):

    letters = []

    for x in word:

    if x not in letters:

    letters.append(x)

    else:

    return x

    print(get_recurring_char(string))

    edit: just realized this is the solution in the video i didnt finish it when writing the comment

  7. can we use this instead:

    def solution(strs):

    for st in strs:
    if strs.count(st) >= 2:
    return st
    else:
    return "Null"

    string = 'ABC'
    result = solution(string)
    print(result)

  8. D00, you gotta explain sheet. Make a step by step video for fuck tards. I already knew n squared time complexity. Didn't know basic statistcs n choose 2 or why you did n * n – 2 / 2. Had to Google

  9. def findCharacter(string):
    char = None
    temp = ''
    for ch in string:
    if ch not in temp:
    temp += ch
    else:
    char = ch
    break
    return char

  10. ster = input("enter your string")

    for i in ster:

    if ster.count(i)>1:

    print(i)

    exit()
    is this good?

  11. In a worst case we may find the recurring character at the end of the string. How about using a forward looking regex to get the recurring character.

    Will it solve the same problem in less time….

    Thoughts please …

  12. <?php
    $str = "ABCDXYZPDAC";
    $myarr = array();

    for($i = 0; $i < strlen($str); $i++) {
    if(!isset($myarr[$str[$i]])) {
    $myarr[$str[$i]] = 1;
    }else {
    break;
    }
    }

    echo "found : ". $str[$i]."n";

    /** can we use PHP??
    * if so, then, what do you think about that?
    * */

  13. We can take every char from the string and insert it in set and check its length. The character which does not increase the length of set is the first recurring character.

  14. This can be solved without any other data structure.
    Just iterate through the elements chech if that element is their in the remaining charater array except the iterable one.
    If it is their then just return index of that element by using an if else block

  15. The first solution would output B if the string was "DCBAAB", so besides the time complexity, it's just wrong

  16. This is amazing series of Interview Questions .Kindly make more videos on Famous Interview Questions . It will be beneficial for all of us .pleaseeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee.

  17. There is also this other approach where you first use merge or quicksort to sort the string character wise, and the ln simply iterate through the array and compare arr[I] and arr[I+1] , if they are equal just return it .

    Complexity is O(nlogn), but dosent take any extra memory..

  18. Why did you not just append those items to a list and return them if they are already in the list?

  19. Your solution has a bug. If you string is CBAAB your code will return A when the correct answer is B.

  20. Here is my solution but i dont think that google will give me a jop.
    namespace Reccuring

    {

    class Rec

    {

    public char TheChar { get; set; }

    public int TheCounter { get; set; }

    public Rec(char x, List<Rec> r)

    {

    TheChar = x;

    TheCounter = 1;

    bool add = true;

    foreach (Rec item in r)

    {

    if (item.TheChar==TheChar)

    {

    add = false;

    item.TheCounter++;

    break;

    }

    }

    if (add)

    {

    r.Add(this);

    }

    }

    public void Checking(char x)

    {

    if (x==TheChar)

    {

    TheCounter++;

    }

    }

    }

    class Program

    {

    static void Main(string[] args)

    {

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

    List<Rec> questionString = new List<Rec>();

    Console.WriteLine("Give the string");

    string question=Console.ReadLine();

    char[] charArry = question.ToCharArray();

    foreach (char item in charArry)

    {

    Rec newRec = new Rec(item, questionString);

    }

    foreach (Rec item in questionString)

    {

    if (item.TheCounter>1)

    {

    result.Add(item.TheChar);

    }

    }

    string theResult = "";

    foreach (char item in result)

    {

    theResult += item;

    }

    Console.WriteLine(theResult);

    Console.ReadLine();

    }

    }

    }

  21. C++ Code using a Hash map with time complexity O(n) and space complexity O(n)

    #include<iostream>

    #include<unordered_map>

    using namespace std;

    int main(){

    string s;

    cin>>s;

    unordered_map<char,int>umap;

    for(int i=0;i<s.length();i++){

    if(umap[s[i]]!=0){

    cout<<s[i]<<" is the first recurring character"<<endl;

    return 0;

    }

    umap[s[i]]=1;

    }

    cout<<"No"<<endl;

    return 0;

    }

  22. import java.util.Scanner;
    class google
    {
    void main()
    {
    Scanner sc= new Scanner(System.in);
    String str;int f= 0;
    System.out.println("enter the string: ");
    str= sc.nextLine();
    int len= str.length();
    for(int i=0;i<len;i++)
    {
    char ch= str.charAt(i);
    for(int j=i; j<len; j++)
    {
    if(ch== str.charAt(j))
    {
    f= 1;
    char result= ch;
    break;
    }
    }
    }
    if(f== 1)
    System.out.println("first recurring: "+ result);
    else
    System.out.println("not");
    }
    }

  23. // in javaScript

    let letters = "CFBDBAD"

    let duplicatedLetter = solve(letters)

    function solve(str) {

    for (let i = 0;i < str.length;i++) {

    let current = str[i]

    for (let j = i + 1;j < str.length;j++) {

    if (current == str[j]) {

    return current

    }else if (i == str.length && j == str.length){

    return undefined

    }

    }

    }

    }

    console.log(duplicatedLetter)

  24. def recurredChar(a):

    output = ""

    for i in a:

    if i in output:

    return i

    output += i

    It is true, too

  25. Nice video. But when we check the hash table for existing item that's doing the same step of the first solution.

  26. But why there's god level questions being asked in clement's interview ?🙁
    This is comparatively easy one

  27. C++ code:

    #include <iostream>
    #include <string>
    #include <map>
    using namespace std;

    int main()
    {
    string s = "ABCB";
    map<char,int> mp;

    for(int i=0; i<s.length(); i++)
    {
    if(mp.find(s[i]) == mp.end())
    {
    mp.insert({s[i], 1});
    }
    else
    {
    cout<<s[i];
    }
    mp.insert({s[i], 1});
    }

    return 0;
    }

  28. Using Java

    private static char getFirstCharacter(String str) {

    Map<Character,Integer> map = new LinkedHashMap<Character, Integer>();

    for(int i = 0; i < str.length(); i++) {

    char ch = str.charAt(i);

    if(map.containsKey(ch)) {

    map.put(ch, map.get(ch)+1);

    if(map.get(ch)>=2) {

    return ch;

    }

    }

    else {

    map.put(ch, 1);

    }

    }

    return '';

    }

  29. For looking inside the set you are also doing a search. Which can slowly increase as the size of dictionary increases. If not sorted each search can go upto O(1)+O(2)+O(3)….O(n) approx O(n**2)

Leave a Reply

Your email address will not be published.

Captcha loading...