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
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.
took 5 seconds to do it !!!A typical hashmap problem…
def seen(str):
d = {}
for eke in str:
if ele not in d:
d[ele] = 1
else:
return ele
return -1
you don't need a hashtable when you can use a hashset, smaller memory for same effect
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
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)
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
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
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
ABCCDBD, will your solution in Python work for this string?
This simple problem can be a foundation to solve some appearingly complex problems. Thanks
Good job
this is the only google coding interview question that I can solve on my own lol
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)
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
def findCharacter(string):
char = None
temp = ''
for ch in string:
if ch not in temp:
temp += ch
else:
char = ch
break
return char
ster = input("enter your string")
for i in ster:
if ster.count(i)>1:
print(i)
exit()
is this good?
Became your subscriber. Your sessions are awesome dude
why the first way was O(n2)? Didn't get that well :/.
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 …
My god this was easy
I think use hashmap with open addressing should be good ?
<?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?
* */
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.
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
The first solution would output B if the string was "DCBAAB", so besides the time complexity, it's just wrong
This is amazing series of Interview Questions .Kindly make more videos on Famous Interview Questions . It will be beneficial for all of us .pleaseeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee.
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..
Why did you not just append those items to a list and return them if they are already in the list?
Your solution has a bug. If you string is CBAAB your code will return A when the correct answer is B.
could we just use an array instead of a hash table?
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();
}
}
}
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;
}
why the hell is that microphone that large?, liturally where did you find one of those?
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");
}
}
// 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)
def recurredChar(a):
output = ""
for i in a:
if i in output:
return i
output += i
It is true, too
Nice video. But when we check the hash table for existing item that's doing the same step of the first solution.
But why there's god level questions being asked in clement's interview ?🙁
This is comparatively easy one
K=0
for element in str1[:len(str1)-2] :
If element in str1[k+1:]
Return element
K+=1
in the first algorithm, why is it n*(n-1) / 2? (why the /2?
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;
}
There's no actual way google really asks these simple questions
U can use a hashset instate of hashmap and chey if the element exist
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 ' ';
}
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)