First Recursion Problem – JAVA Coding Interview Question

Problem Statement : Given a word, find the first recurring letter.

Example 1.) 
Input : ABCD. 
Output : Null
Explanation : None of the letters repeat or recur.

Example 2.) 
Input : DERDER
Output : D
Explanation : D is the first recurring letter.

Example 3.)
Input : QWEEWQ
Output : Q
Explanation : Q is the first recurring letter.

Now there are 2 approaches.

Approach 1

  • Apply 2 loops. (i and j)
  • First loop i.e. ‘i’ will iterate through from first letter till last letter of the word.
  • Second loop i.e. ‘j’ will iterate from ‘i’ to last letter.
  • On each iteration of ‘j’ check if the ‘ith‘ letter is repeating. If yes you got your O/P.
  • This approach has O(n2) Time complexity as we are iterating through the letters of the word twice, using 2 loops.

Below is the code.

OUTPUT of Above Code

Approach 2

  • This approach is required when you are giving interviews in Tier 1 companies because they are more worried over ‘Time complexity’.
  • The approach uses single loop thus having time complexity O(n), uses less memory.
  • The approach also uses easy string manipulation.
  • So let’s look into the code below and check time complexity.
CODE
OUTPUT

5 thoughts on “First Recursion Problem – JAVA Coding Interview Question

  1. I was curious if you ever thought of changing the layout of
    your site? Its very well written; I love what youve got to say.
    But maybe you could a little more in the way of content so people could connect with it better.

    Youve got an awful lot of text for only having 1 or
    two images. Maybe you could space it out better?

  2. It’s a pity you don’t have a donate button! I’d most certainly donate to this excellent blog!
    I guess for now i’ll settle for book-marking and adding your RSS feed to my
    Google account. I look forward to fresh updates and will talk
    about this site with my Facebook group. Talk soon!

  3. Heya i’m for the primary time here. I came across this board and I find It really helpful & it helped me out a lot.

    I hope to give one thing again and aid others such
    as you helped me.

  4. Hi I am so thrilled I found your weblog, I really found you by accident, while I was browsing
    on Google for something else, Anyways I am here now and would
    just like to say cheers for a tremendous post and a all round interesting
    blog (I also love the theme/design), I don’t have time to read it all at the moment but I have bookmarked it
    and also included your RSS feeds, so when I have time
    I will be back to read a great deal more, Please do
    keep up the awesome job.

Leave a Reply to http://t.co Cancel reply

Your email address will not be published.

Verified by MonsterInsights