Sunday, October 2, 2022
HomeJavaEasy methods to discover first recurring or duplicate character in given String?...

Easy methods to discover first recurring or duplicate character in given String? [Solved]


Good day guys, whereas browsing the Web for a few weeks again, I come to
know that this drawback was requested on Google interviews,
discover the primary recurring character in a given String. I do not know if
that is true however this appears like a quite simple coding drawback from Google’s
Interview commonplace. If it was certainly requested, then that man should have been
very fortunate. Anyway, I appreciated this coding drawback and thought to put in writing about
it, as a result of it is a good coding drawback to examine candidates’
knowledge construction and algorithms abilities
as a result of it is difficult. It is difficult as a result of it is very simple to make a mistake
assuming only one recurring character in String, which you need to
keep away from. Even when it was not requested on Google, you’ll probably discover this drawback
on numerous startups, and different IT firms like Infosys, TCS, Cognizant,
Microsoft, and perhaps
Amazon

Trying from the opposite facet of the desk, I imply as an interviewer, 
that is probably a very good coding drawback to ask on telephonic tech
interviews as a result of there are a number of options to this drawback and it additionally
demonstrates how utilizing the appropriate knowledge construction can enhance your algorithm
and efficiency.

Drawback – Given a String, discover the primary recurring or duplicate
character
? Write a program to unravel it, if there isn’t a recurring character,
simply return null.

Instance – If given String is :


“ABCDAB”
– first recurring character is A


“ABBCDA”
– first recurring or duplicate character is B


“ABCDA”
– there isn’t a recurring character, so your operate ought to return
null.

3 Methods to discover first recurring character in given String

There are a few methods to unravel this drawback, however first, let’s take a
have a look at the best resolution which does not contain any knowledge construction or
extra reminiscence.

1. Brute pressure resolution (Tough)

The brute pressure or most intuitive technique to remedy this drawback is to take one
character at a time, ranging from the
first character, after which examine
with all of the characters, if it matches, then it is the primary recurring
character. Simply return the character and you’re accomplished.
For instance, if the enter string is “ABCDAB”
then there are two duplicate characters in it however “A” is the primary recurring
character. In the event you begin with the letter “A” and examine it with “B”, “C”,
“D”, “A”, you will see that it matches with the final “A”, therefore that is the
first
recurring character.

You aren’t accomplished but, that is the place the place most programmers make errors
significantly inexperienced persons and careless programmers. This resolution will work if
there’s only one recurring character within the String however it won’t
work in case your string has a couple of recurring character
like on this case.

As an alternative of returning the character and exiting the operate, you should
retailer this letter and its matching index right into a variable, like
firstRecurringCharacter=”A”, firstRecurringIndex=”4″.

How to find first recurring character in given String

Now, you’ll begin with “B” and full the iteration, this time, you’ll
discover the recurring character at index=5. 

Now, you should examine and see if this subsequent index is decrease than the
earlier index, if sure, then
swap and will probably be the brand new first recurring character as a result of it is noticed
first within the String. When you full with all characters, you should have
your reply in variable “firstRecurringCharacter”.

This resolution would not use any extra reminiscence however the time complexity of
the answer is O(n^2) as a result of you should examine every character with
everybody else. The primary go takes n comparability, the second go takes n-1
comparability, third takes n-2, which suggests complete
N(N-1)/2 = O(n^2)

So, it really works however it’s probably not probably the most environment friendly resolution and let’s examine
if we are able to enhance it.

2. Utilizing a Map, hash desk, or Dictionary

Now, we’re utilizing an information construction referred to as Map, or hash desk, or dictionary
in Python to enhance our resolution. On this resolution, we undergo all
characters one after the other and retailer them within the
hash desk
as key and worth as 1 to point that we have now seen this character
earlier than. 
By default, the important thing and worth will probably be null for an unseen character. Whenever you
hit a recurring character, you will see that that it is already current on the
map. At that time, you may cease processing and return that character. Achieved.
The time complexity of this resolution is
O(n) as a result of we’re simply visiting
every character one time. If there’s n character in String then we’ll name
the
put() technique
N occasions. Because the time complexity of storing a key-value pair within the hash
desk is O(1), the time
complexity of our resolution can be
O(n)*
O(1) = O(n).

This implies a significantly better resolution than the earlier one. It can take
extra reminiscence of O(n) as a result of
we have to retailer every character into the hash desk however time has been
diminished quite a bit. 

It is a good instance of how utilizing an information construction can enhance efficiency
and simplify an algorithm. It’s also a very good instance of the area vs time
tradeoff as a result of we spend
O(n) area to scale back time
complexity from O(N^2) to O(n).
By the best way, in case you are new to time and area complexity, you may try
these
knowledge constructions and algorithms courses to be taught and refresh your ideas. 

3. Utilizing a Set

If you do not know Set is a particular knowledge construction that solely shops distinctive
worth. In the event you attempt to retailer a reproduction worth in Set then it should return
false. We are able to additionally use this knowledge construction to search out the primary recurring
character in a given String. In Java, we have now many implementations of set
knowledge construction and we’ll use HashSet for this resolution.
HashSet has an add() technique which
returns false if the factor is already current within the Set. Just like the
earlier resolution, we are able to undergo every character one after the other and retailer
them in
HashSet.

In the event you a personality is already current then
add() technique will return false,
that’s our first recurring character. At the moment, we are able to cease processing
and return that character.

Once more, the time and area complexity of this resolution are the identical because the
earlier one, I imply it should take
O(n) area and
O(n) time to search out the primary
recurring character in a string of N characters.

4. Java Program to search out the primary recurring character in a given String

Now, let’s examine the whole Java program to unravel this Google Interview
Query and discover the primary recurring, or duplicate, or repetitive character
within the given String. It has some unit checks to confirm that our resolution is
working effective. It additionally has three strategies for every resolution and they’re
checked in opposition to the identical unit checks
import static org.junit.Assert.assertEquals;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import org.junit.Earlier than;
import org.junit.Ignore;
import org.junit.Check;


public class GoogleTest {
    GoogleCode code;

    @Earlier than
    public void init() {
        code = new GoogleCode();
    }

    @Check
    public void testBrutForceSolution() {
        assertEquals("A", code.bruteForce("ABCDA"));
        assertEquals("A", code.bruteForce("ABCDAB"));
        assertEquals("B", code.bruteForce("ABBCDA"));
        assertEquals(null, code.bruteForce("ABCD"));
    }

    @Check
    public void testUsingMapSolution() {
        assertEquals("A", code.usingMap("ABCDA"));
        assertEquals("A", code.usingMap("ABCDAB"));
        assertEquals("B", code.usingMap("ABBCDA"));
        assertEquals(null, code.usingMap("ABCD"));
    }

    @Check
    public void testUsingSetSolution() {
        assertEquals("A", code.usingSet("ABCDA"));
        assertEquals("A", code.usingSet("ABCDAB"));
        assertEquals("B", code.usingSet("ABBCDA"));
        assertEquals(null, code.usingSet("ABCD"));
    }
}


class GoogleCode {

    public String bruteForce(String enter) {
            char[] characters = enter.toCharArray();
            String firstRecurringCharacter = null;
            int firstRecurringIndex = enter.size() - 1;

            for (int i = 0; i < characters.size; i++) {
                char ch = characters[i];

                for (int j = i + 1; j map = new HashMap < > ();
                    for (Character ch: chars) {
                        Integer rely = map.get(ch);
                        if (rely == null) {
                            map.put(ch, 1);
                        } else {
                            return "" + ch;
                        }

                    }
                    return null;
                }

                public String usingSet(String enter) {
                    char[] chars = enter.toCharArray();
                    Set setOfCharacters = new HashSet < > ();
                    for (Character ch: chars) {

                        
                        
                        
                        if (!setOfCharacters.add(ch)) {
                            return "" + ch; 
                        }
                    }
                    return null;
                }
            }


Output - All Assessments handed

The logic to check this program is written within the unit take a look at. Whenever you run the
program, you will notice all checks are passing. This system has three checks,
one for every resolution. Every take a look at checks 4 situations, if our resolution
passes for all these 4 situations then logic is appropriate.

That is all about
discover the primary recurring character in a given String. You possibly can
remedy this drawback in Java, C++, or Python, as much as you, I’ve solved it in
Java. As I mentioned, this was requested in Google so it is value practising. It is
additionally a very good coding drawback as a result of it teaches you ways intelligent use of knowledge
construction can cut back time complexity. If you’re making ready for coding
interviews and want extra such questions, I recommend you be part of this course

Extra String Coding Issues from Interviews for Apply

If you’re thinking about fixing extra String based mostly coding issues from
Google, Fb, Amazon, and different FAANG firms then right here is the listing of
hottest string questions

  • Easy methods to discover all permutations of String? (resolution)
  • Easy methods to examine if the given String is the rotation of one another? [solved]
  • Easy methods to Print duplicate characters from String? (resolution)
  • Easy methods to convert a numeric string to an integer? (resolution)
  • Easy methods to examine if two Strings are anagrams of one another? (resolution)
  • Easy methods to program to print the primary non-repeated character from String?
    (resolution)
  • Easy methods to reverse String in Java utilizing Iteration and Recursion? (resolution)
  • Easy methods to examine if a string incorporates solely digits?  (resolution)
  • Easy methods to rely the variety of vowels and consonants in a String? (resolution)
  • Easy methods to rely the incidence of a given character in String? (resolution)
  • 10 Algorithms Programs to Crack Programming Job Interviews (programs)
  • Easy methods to reverse phrases in a sentence with out utilizing a library technique? (resolution)
  • Easy methods to examine if String is Palindrome? (resolution)
  • Easy methods to return the very best occurred character in a String? (resolution)
  • Easy methods to reverse a String in place in Java? (resolution)
  • 50+ Information Construction and Algorithms Interview Questions (questions)

Thanks for studying this text thus far. In the event you like this Google coding
Interview drawback and my resolution and rationalization then please share it with
your folks and colleagues. When you have any questions or suggestions then
please drop a be aware.

P. S.- In the event you really feel your knowledge construction and algorithm abilities are rusty
and also you want a little bit of refresher then I recommend you are taking these
coding interview preparation books and programs
to shortly revise all vital ideas earlier than your interview. 



RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular

Recent Comments