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.
You don't loop, but query it directly with a given key, in this case the char itself. Example: hashTable.has('A') // true or false if the table has that key or: hashTable.get('A') != null // true or false if the table has that key I did show 2 variations because it can vary from one language to another. The .has() method is just a helper that some implementations offer. The second example can cause problems if we actually want to store null values, but for this case works fine. A hashtable has a constant access time, O(1), so the overall time complexity does not increment.
Lol I just thought about that before resuming the video, my solution tho is using a int with size of n bits. Then I check if the bit in the place of the character is on or off. If it on return the number. If it off turn it on. As that more efficient in memory (the hash can be stored in a register). If I want to redefine the problem to result A in a ABBA case my solution is failing because I can't know the order of the characters in the input string. In such case using a table won't help ether because hash table don't keep order of inserion ether. I don't have a real good simple solution for that problem right now. As the efficient way I am thinking about is creating the hash in a way that every recurring characters are marked with a on bit. Then looking for the first 'on' character in the string. I find my solution not simple because it has those 2 steps that I need to repeat...
For "first solution" he is referring to the O(n^2) solution that scan each character and try to find a match in the remaining characters. Using that solution, the input "ABBA" would return 'A', but the correct answer should be 'B', according to the question definition.
CS Dojo Assuming the characters can only be ASCII (or any character encoding with a constant number of characters), your second solution has an O(1) runtime complexity. Not O(n) because your string can be 256000 characters long but you will see a repeated character after 256.
Classic miss direction and you fell for it, the only purpose for this video is to asses their future janitor if he can work out if he has cleaned a toilet twice during his shift.
Instead of using a HashMap, you could use a bit vector as the hash map. Set the bit of the character in the bit vector while you encounter it and if the bit is already set, thats the first recurring character.
Why? Obviously you're not going to know anything about a subject you haven't studied. :D If you've studied it extensively and you still don't understand it, _then_ you may feel dumb about it. And even then, so what? Feeling dumb simply means you just found out that you have something to learn. Feeling dumb has nothing to do with being dumb. :)
vaishnavi Our feelings are often illusions. They are emotions. And emotions aren't logical. So these feelings often give us an incorrect idea about reality. You may feel dumb even if you aren't. You may feel smart even if you aren't.
after seeing your video I made a short python script with two functions, the first using the good, the second the poor algorithm. I made a list with 10000 random, not repeating characters and at the end AA. Here are the results: good: (using a set and going through ones) 0.0789 sec bad: 9.46 seconds! Nice video, thanks for enlightening
Would hash set be better? In hash table you are storing another column count, which uses more space... In hash set, you only need to check whether the element is in the set. If it is already in the set, then you return this element right away...
CS Dojo its the same space complexity but hashset in this case is certainly a better option. I guess you can use the hash table and if interviewer asks for space optimization you can suggest a hashset with minimal code change
It hardly depends on the language. For instance, in Java HashMap is used internally in the HashSet collection thus it does not bring any memory optimization.
Actually the run time for the hashing variant is O(const) (and O(n) for small lists). We will find a double character within the first k+1 elements of the list where k is the number of valid characters. If the string is encoded in say UTF-8 our charset has 8 bit, thus we will inevitably find a repeating character after 256 elements and can ignore the remaining list. If our charset is even shorter (say only A-Z [note the capital]) as in this case, we only consider the first 27 characters. This number is independent of the lists actual size, thus it will work in constant time for long lists. The same goes for the first variant which is O(n^2), we can prune comparing against characters that are more then charset+1 away from the start and will find one within the first charset + 1 characters. This will result in a runtime of O( [charset + 1]^2 ) which is lower then O(n^2) for big lists. Which variant is faster then becomes interesting, because we might be able to further optimize via multicore processing or SIMD ...
Mhhh not necessarily. I don't think that the problems itself are unsolvable at these companies, I believe that they are more looking for how you solve it and if you can get to the uber-smart approach they are expecting (tough for me, since I mostly work after the pattern "make it work, optimize it later")
A rather simple operation with Time O(length of string) and space O (1) is using bit operations. Just define a mask 0, loop through the characters get bit of mask at location char-'A'. If 0 is gotten, set to 1. And continue looping, if 1, return char
Fundamentally, if you understand Data Structures and Algorithms you can solve this one. This is why those two classes are ALWAYS recommended (required even) before any elaborate code building. Great vid to reinforce the fundamentals
My thought was simply to iterate through the array and for each element, check the length of a set before and after adding the element to that set. If the length increases, that's the first time the element has occurred in the array. If the length stays the same, the element was already in the set and therefore it's the first recurring element.
most add functions actually return a boolean value for if the set was changed or not (at least in java). So all you would really have to do is if(!set.add(char)){ return char}
Even if we don't have any recurring characters in the first 26 characters of the string, the 27th character will be recurring, since we have only 26 alphabets (assuming the string contains only alphabets). So time complexity is O(26), which can also be written as O(1). Even if the string can contain all ASCII characters, it can still be considered O(1) according to me.
But you still have to traverse the whole thing to find the element that is recurring. And if the input is smaller than 26 you can't use the pigeonhole principle.
@@sangramjitchakraborty7845 As soon as you find the first recurring character you can exit the for loop. The first recurring character can't come after 27th position, because for it to do so all the positions before it must contain different characters, which is not possible since only 26 characters are possible. Hence 27th position or lower positions must contain at least one recurring character which will be the first recurring character.
Why do you need to use a hashtable to store an extra value of the count? Just use an arraylist. PseudoCode: Arraylist occured; for char in Given_String: if(!occurred.contains(char)){ occurred.insert(char); } else{ return char; }
The two solutions that you mentioned (O(n^2) and O(n)) produce different results for the string ABBA. Now I am confused which one is first recurring char in ABBA, A or B. If it is B then your second solution would work properly (Set would be better though). But if it is A then we can use dictionary like you did with chars as keys and respective counts as values. We need to traverse the complete string to complete the dictionary then we could start traversing the string again and for every char we would refer dictionary for its count. Once we reach a char for which count is >1, return. Time complexity - O(n). Space - O(1). Any better solution?
his brute solution is wrong; like you suggested ABBA will return A when in fact ABBA should return B. For second method, I don't think it matters whether you use hashset/map or even an array. What does matter is that the space is not O(n) but rather O(1) since there are limited number of alphabets (52 if case sensitive, 26 otherwise).
Exactly what I was going to comment! The problem is not properly defined, is the first recurring character the first one to appear twice or the first one in the sequence that repeats? His solution only works in the first case.
I agree that 2nd solution gives correct result, since in ABBA, A recuring in 4th spot, and B is recurring in 3rd. However I not quite agree we have O(n) in second solution. Sure we go only forward the string, but we iterate each table row every char. Sure, most languages are making this for us in lower level, yet still are doing.
I just started uni and got the answer right, didn't think about the naive way at all. I come up with a good enough solution and then I optimize it. If you shoot for the stars right away, you'll struggle a lot because you're gonna get stuck on the details and you won't get anything from that. My high school computer science teacher used to say "you can't build a skyscraper all at once, start with the foundations, then build your way up"
Ganesh _ the complexity of hashset and hashtable is equivalent. Here it supposed the time complexity of ‘ if e in counts ‘ is 1. If the size of counts may grow large, it needs to optimize ‘if e in counts’.
Some performance numbers in python (running the method on string.printable 10000 times): List - 1.8005362025424931 seconds Dictionary - 0.4816858277563984 seconds Set - 0.2586124478794257 seconds Looks like a set would have been the best choice.
In your assessment of the time complexity, you should add the time that it takes to actually create a hashtable and insert the values. That would have increased memory usage as well. Depending on your time and memory constraints, you have to use different approaches.
for (i from 0 to n - 1) { character = input_string[ i ] counts[character] = 1 if (counts.size() < i + 1) return character } return none This variation take advantage of the unicity of Hash keys
You don't even need a hashmap. Just use a mapping onto an array of size 2⁸ via the char number - constant read, write: char frc(char* str) { char* buf = calloc(256, 1); int i = 0; len = strlen(str); while(i < len && buf[str[i]] != str[i]) buf[str[i++]] = str[i]; return str[i]; }
You could use a bitmap to mark the seen characters and when the same character is seen the next time, you could return that character simply. This way you save space as well by not tracking the character and the count in a dictionary/hash table. For example, for 96 printable ASCII characters including special characters, you would need only 12 bytes to mark different characters that are seen as we pass each character. Since we are interested only in the first reoccurring character we don’t need more than 12 bytes. We mark each character from the string using a lookup table and set the corresponding bit in the bitmap. We can have different ranges for special characters and normal characters in the bitmap and mark appropriately. The first reoccurring character can be found when we try to set the bit which is already set. This way we don’t use a lot of space as well as the time complexity is at minimum (which is similar to the solution presented in the video).
I used Java for the solution. No need for a HashMap/HashTable. A simple ArrayList will do as we don't need to save the number of times a character appears in the string. One's we check that the next character is already in the list we stop the search, that's break out of the loop and return the value.
There's a lot of tough looking codes in the comments. Here's an easy one in Python 3 (I think): s = input("") ar = [] for i in s: if s.count(i) > 1: ar.append(i) if ar: print(ar[0]) else: print("None!")
The hash table is def more elegant and better time complexity. My first attempt in c++ was of a double for loop O(n^2), 2 array chars, & 1 basic char. One array char to hold the letters, another array char to assign & store duplicates found by a third plain char holding current indexed letter.
In Haskell (obviously can be made shorter, but hopefully very readable and is evidently efficient): --This function takes two lists and returns another. Each element of the second list is removed and put into the first list if not already present there, otherwise it remains in the second list. sift :: Eq a => [a] -> [a] -> [a] sift ts [] = [] sift ts (x:xs) | x `elem` ts = x:(sift ts xs) | otherwise = sift (x:ts) xs --This function gives list of first (and later) repeats of elements. repeats :: Eq a => [a] -> [a] repeats xs = sift [] xs --This function gives first element to repeat, or an error if no letter repeats. firstRepeat :: Eq a => [a] -> a firstRepeat xs | null (repeats xs) = error "No element repeats." | otherwise = head (repeats xs)
I am student of First Semester of B.S(CS). I literally pused it and thought a rough algorithm and I made it on my FIRST try C++ ! :) Really really happy to realize my hidden skills :-D
In python you can use string functions(built-in). If you put the letters in a list and then go with a for i in list, then you count each letter with list.count(i) and if it is >= 2 then print the letter and break!
You could also create an array of length 26 in which you insert the ascii code to int and increment the position and then when the index is equal to 2 stop and convert the index to the position getting the character
I like this and I was reaching for it in my head too, but I think to properly answer strings like "ADDA" with an 'A' you wouldn't be able to reduce this to a range/popcount problem.
Two pass method (python): def firstNONRecurringCharacter(string): dic = {} for char in string: if char not in dic: dic[char] = 1 else: dic[char]+=1 for char in string: if dic[char] == 1: return char
I'd just search backwards for each char: function focc(str) { for (var i = 1; i < str.length; i++) { if (str.substr(0, i).indexOf(str[i]) > -1) { return str[i]; } } return null; } This way no other memory would be used
If you use sets in Python then you can reduce the complexity to just o(n). here is the code: a = "ABCDA" b = set() for char in a: if char in b: print(char) else: b.add(char)
A JavaScript solution: function findRecurrence(str) { //convert string to array const arr = str.split(""); //construct new set from array and check if the size is the same if(new Set(arr).size === arr.length) return null; //loop through array and use slice method to extract elements starting at current index +1 so that the current index is not on the new array //check if this new array contains the current element, return it if so for(let i = 0; i < arr.length - 1; i++) { if(arr.slice(i+1).indexOf(arr[i]) !== -1) return arr[i]; } }
Good job. By performance purpose you can replace arr.slice() with arr.indexOf(arr[i], i + 1). Slice function creates a useless array, which turns the algorithm a bit slow I created this gist to demonstrate my tests! Check this out: gist.github.com/thiago-tallison/36b3e826a856f9ffaa1cdd09dcf95265
my solution, for those interested (written in C#): char? firstRecurring(string str) { if (str.Length - 1 == 0) return null; List temp = new List(); temp.Add(str[0]); for(int i = 1; i < str.Length - 1; i++) { if(temp.Contains(str[i])) { return str[i]; } temp.Add(str[i]); } return null; } the reason I start with 1 instead of 0 is pretty straight forward, I want to have something to check against on the first pass in case indices 0 and 1 are the 1st recurring. No need to make a complete pass if you don't need to. And in case you're curious, my first conditional is there in case of a curve ball. Say they pass in the string "A", just return null prior to even running checks as you know there'll be no recurring characters. Hope this helps someone, good luck all
I think a linear solution is possible by using map in c++. I extract each character from the string and increment the count. If I get a count greater than 1, I print that character. Then in a visited array, I set the attribute to true so that I don't print the same character again.
before watching the video what I would do is a loop that runs through a certain string and assigns checks each of the characters one by one starting at the beginning and for example “DCADAB” it would start at ‘D’ and then create a byte variable that would store that there is one d(byte d += 1;) and move on the the next and the loop ends when any of the variables = 2
I don't get it. They are already in a string, so you could just start at the 2nd level and see if its in the first position. Then continue to take the n-th letter and check it with the first n-1 letters. It uses the same amount of comparisons as his 'correct' solution.
Louis, both the solutions are correct but the second one is better than the first one as it takes much lesser comparisons. Your method uses same number of comparisons as his first method which is n(n-1)/2...
Checking if something exists in an array takes at best O(1), on average O(n/2) -> O(n), and at worst O(n) comparison. Checking something if it is in a hashmap/hashset takes at best O(1), on average O(1), at worst O(n). So adding an item into an array and then checking if it is in an array is O(n^2), which is what we want to avoid. Use a hashmap/hashset when you don't care about the order it gets added into the hashmap/hashset.
Leighton Lee, assuming there are only uppercase English letters (it seems so), you could use an array of 26 booleans and use the current char as index (its ASCII value minus that of 'A'). That way it's always O(1) for the lookup because you don't actually have to search for anything. If you're short on memory you could even use a 4byte bitmask in the same way :3
This is my solution in java 8: private static Character findFirstRecurring(String letter){ char[] l = letter.toCharArray(); Set list = new HashSet(); for (char c: l) { if (!list.add(c)) { return c; } } return null; }
We don't actually need a hashset for that. We can use simple uint32, since chars are in range 1-26 and we need a simple bool check. Simply by checking bits on int. int check = 0; for (int i = 0 ;i < chars.count; i++) { // make sure that value is in range 1-26 if (check & 1
Aren't both solutions O(n^2)? For the second solution, the programming language will have to compare char against each item in the list, won't it? That would make it O(n^2) if i'm not mistaken. Can anyone confirm/deny?
I thought so as well. But the comparison of the chars will only take a constant amount of time, because there is a finite number of possible characters
You use for loop to iterate through the string nd check the index of character other the current position if gives index >-1 then it is an recurring character, in this case the loop will go only 1 time for both question 1 and 2 which is quicker than the map and sets
Rowan Hatherley, you absolutely right. I was so much confused doing this many times and came to know that this twp solutions gives two different answers.
It's B. Basically, just look for the character you see twice first. Since you return after the first recurring character (B), the second, third, ..., recurring characters don't matter. ABCA returns A because A is the only recurring character, therefore, the first recurring character. BCABA returns B because B is the first recurring character. Given ABCBDA, it would return B since it's the first recurring character.
Hey guys Checkout this Google interview problem that's solved with 4 different approaches from scratch to code really quick at : ua-cam.com/video/ucMDHUzaH60/v-deo.html
'I recommend you pause the video and think about it for a second.' It took me an hour and a half to come up with a naive solution and get it working in code
Watch some of his or other people's videos on Big O notation. It's not as hard and intimidating as it looks. CS Dojo's explanation of it is one of the better ones.
If it's just a string of letters (A-Z aka 26 different symbols), I'd just use a 32bit value, go through the string from left to right like you did, and for each letter first check if the corresponding bit is already set (using BITAND), if yes, return this character, if not set the bit (BITOR). Such bit operations are a lot faster typically, often have hardware support and you only need 4 Bytes for the alphabet, no need to use any fancy data structures :)
Hey guys Checkout this Google interview problem that's solved with 4 different approaches from scratch to code really quick at : ua-cam.com/video/ucMDHUzaH60/v-deo.html
The first "naive" solution actually wouldn't even work in some scenarios. The string example you used was "DBCABA"... if the string was, say "DBCAAB" then the first solution would still output "B" which would be the wrong answer since A repeats before both B's.
Think about start placement in your loops. ABBA => starts with A then your sub array is (BBA) => start with B sub array (BA). That should help you understand how you get the n(n-1)
From what I see, most interview questions (specially on phone and online) are a coversion from a O(n^2) to O(n). And when you have it, hashmaps - there you go! :) Saved my ass last Friday (before I saw this video though).
The best way is to have an array of size = 26 and increment the count based on the alphabet by traversing right to left. check if the count of the respective element while traversing itself. If count>1 then it's repeating. Check till the left most element.
The answer would be different in "naive" and hash table method if the string is DBCAAB. In naive method it would return B while in other it will return A.
Either solution works, so if the requirements are as you specified then it shouldn't matter which one you use. You are making an assumption that we want to optimize on speed. If we want to optimize for memory size then the first solution you gave would be a better solution.
Timothy Fish The first solution would likely never be used regardless of optimization specifications. First, it gives the wrong answer in a situation such as ABBA (returns A, but the correct answer is B). Also, large data sets would take way too long
@@jackytaly , you're confusing the first recurring character with the first repeated character. In ABBA, A is the first recurring character because it is the first character that has a recurrence in the string, but the second B is the first repeated character. So, again, the requirements are more important to which algorithm is correct than optimization that may not be requirement at all.
Timothy Fish So in a string of say ABBCCDDEEFFGGA, you should return A as the first recurring character? No one would define “first recurring” as such. Recurring and repeating are interchangeable depending on who is defining the requirements, so it is not a matter of recurring vs. repeating. It is a matter of who is defining the problem, and no one would define it for A to be returned in this situation because it’s illogical and wouldn’t be useful in most situations
@@jackytaly, yes, I would say that A is the first recurring character. But if someone were to code it differently, I wouldn't say that they were wrong, just that the requirements weren't clearly written. But that's my point. You can't say that someone is wrong for writing code that optimizes for something other than what you think it should when you haven't specified what they should be optimizing for.
I use for loop in this case to either areive at the solution right away or create a key:pair diction to show the how many time the key appear. Def letter_and_number(variables): Counter ={} for letter in variables: If letter in counter: Counter[letter] += 1 else: Counter[letter] = 1
It's actually a very good exercise. Thank you. I think it would be something like this in Java (though my first approach was the naive solution, I agree with using a Map instead) import java.util.HashMap; import java.util.Iterator; import java.util.Map; public class MainApp { public static void main(String[] args) { //the subject String String someString = "ABCDEFGAD"; //split subject String to an array String[] someStringCharArray = someString.split(""); //the Map to fill in with individual character and count per character Map map = new HashMap(); //start looping through comparing and counting for(int i=0; i 1){ System.out.println(o); } } } }
Ive got extremely minimal coding experience and knowledge BUT. I would take every charavter in the array and store it as a variable (INT) named itself. As the array is counted by the program, the variable adds +1 to whatever it sees. First one to get to 2 stops the program and outputs x variable.
If you can use JavaScript couldn't you run through your array once and compare indexOf with lastIndexOf and return the first value where they are not the same?
@@TheFreakinProgrammer with this it does: function findRecurrence(str) { for(let i = 0; i < str.length - 1; i++) { let char = str.charAt(i); if(str.indexOf(char) !== str.lastIndexOf(char)) return char; } return null; }
don't need any data structure other than an array - my intuitive solution is to iterate over the chars in the string, push each char to the array as you go, and then each time check if it's already in the chars array. Here's a simple version of it in ruby! def first_recurring_string(str) encountered_chars = [] str.chars.each do |char| return char if encountered_chars.include?(char) encountered_chars
In the second method, wouldn't the O-notation not be O(n) since in addition to checking the String you are also checking the created set for every character?
Less processing but more memory. Guess it depends on what hardware you want to utilize. But usually small if the string is anticipate to be small, then processing is valued over memory I assume. But the instruction won't be repeated, I think that's what the O is about, not overall complexity, but instruction repetition. Oh, just noticed your comment is 3 years ago. Well, cheers.
@@MoJo01 well im glad you mentioned that, i had that thought as well so I am glad you left a reply. Ill have to look into it more, but now i no where to start so cheers to you!
In the case of an alphabet with 26 defined characters. Create a 26d array with values set to 0. preprocess your string to a list of ints. Go through list one by one, changing the index of the corresponding number in the array of 0’s to be 1. Then when the index is 1 already stop. Convert back to string. Arrays are faster than using hashes.
Well, no, because the table is just an array with the int value of the character as the index. We don't have to search the table, but we do have to have memory to hold the table, which is not a given if we are developing embedded software.
If we're only guaranteed to analyze ASCII characters between 0x41 - 0x5A, the even more performant solution that consumes only 5 bytes of memory would be to use a the first 26 bits of a uint32_t initialized to 0 to keep track of the first occurrence of each character. The current bit index would be tracked by a uint8_t. When checking the next character sequentially, if the bit corresponding to that character is already 1, then return (char)(0x41 + m_flagIndex). m_flagIndex can be calculated by taking the current character and subtracting 0x41. This solution could also be expanded to 9 bytes of required storage if we need to handle both lower and uppercase characters.
It took me three months of a CS degree education to understand and fully comprehend everything said in this video. Starting from someone with no knowledge of coding. Its really not to difficult once you understand the jargon. Discrete mathematics and a data structures class will make this a breeze.
Same solution can be made with lists, which may or may not be simpler; def first_recurring(given_string): letters = [] for char in given_string: if char in letters: return char else: letters.append(char) Return null
A hash set would suffice, e.g. (Java): char findFirstRepeat(String s) { Set set = new HashSet(); for(char c : s.toCharArray()) { if(!set.add(c)) return c; } return 0; }
The second solution is much more optimal in terms of time complexity. The first solution is the basic, "brute-force" method," and often the one that comes more naturally to beginner programmers. In that sense, it is more naive than the second.
for i:=1 to length(s) do inc(count[s[i]]); for j:=‘a’ to ‘z’ do m:=max(m,count[j]); for j:=‘a’ to ‘z’ do if count(j)=m then begin writeln(j); halt; end;
Both solutions are not of the same complexity. The first is O(n^2), second one is actually O(n log(n)). Map lookup uses loops, but the loops doesn't go though all n element, only through log(n) elements.
raptor eagles Any general purpose hash map implementation will be more than O(n). An array based implementation for example needs to extend the array and reorder items after adding some amount of entries (or deal with lots of collisions). In our example however, dealing with ascii characters as a key, we can use a static 256 bit array to mark characters. This will be O(n). But actually O(1), because we will never process more than 257 characters for input of any length.
Boris Brodski yeah that's right. but we have to implement that logic ourselves. default set/map implementations don't do that. might be bitset will help but it has its own limitations.
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.
You don't loop, but query it directly with a given key, in this case the char itself.
Example: hashTable.has('A') // true or false if the table has that key
or: hashTable.get('A') != null // true or false if the table has that key
I did show 2 variations because it can vary from one language to another. The .has() method is just a helper that some implementations offer. The second example can cause problems if we actually want to store null values, but for this case works fine.
A hashtable has a constant access time, O(1), so the overall time complexity does not increment.
too late over half a million ppl watched lmaooo
Lol I just thought about that before resuming the video, my solution tho is using a int with size of n bits. Then I check if the bit in the place of the character is on or off. If it on return the number. If it off turn it on. As that more efficient in memory (the hash can be stored in a register). If I want to redefine the problem to result A in a ABBA case my solution is failing because I can't know the order of the characters in the input string. In such case using a table won't help ether because hash table don't keep order of inserion ether. I don't have a real good simple solution for that problem right now. As the efficient way I am thinking about is creating the hash in a way that every recurring characters are marked with a on bit. Then looking for the first 'on' character in the string. I find my solution not simple because it has those 2 steps that I need to repeat...
For "first solution" he is referring to the O(n^2) solution that scan each character and try to find a match in the remaining characters. Using that solution, the input "ABBA" would return 'A', but the correct answer should be 'B', according to the question definition.
CS Dojo Assuming the characters can only be ASCII (or any character encoding with a constant number of characters), your second solution has an O(1) runtime complexity. Not O(n) because your string can be 256000 characters long but you will see a repeated character after 256.
What if I just wanna sweep the floor and clean the toilets?
lmao
For that, u dont need to fuck around a Coding Video.
Plot twist: floor sweepers and toilet cleaners at Google are robots programmed by these coders. Our job prospects just got lowered! 🤪
Classic miss direction and you fell for it, the only purpose for this video is to asses their future
janitor if he can work out if he has cleaned a toilet twice during his shift.
Watch a toilet cleaning tutorial.that will help u more than a coding video.
"we're going to use pseudo code to explain this code"
> uses python
LOL
I was thinking the same😁
Probably it was a subtle trolling 😉
LOL
isn't Python just a runnable pseudo code?
@@play005517 no its real code, Reddit works on Python. It's just weird
I'm an IT graduate (computer networks) but this comment section makes me reconsider my life decisions
why ?
Modi Rasheed why?😂
Cuz coding is more fun than IT. I’ve done both. Just my opinion :p.
Same here
Same here bro
Instead of using a HashMap, you could use a bit vector as the hash map. Set the bit of the character in the bit vector while you encounter it and if the bit is already set, thats the first recurring character.
Came into the comments section not knowing anything about this subject and now I feel dumb
Marco M lol! then why this video came into your feeds in the first place?
Marco M sameeee
Why? Obviously you're not going to know anything about a subject you haven't studied. :D
If you've studied it extensively and you still don't understand it, _then_ you may feel dumb about it.
And even then, so what? Feeling dumb simply means you just found out that you have something to learn. Feeling dumb has nothing to do with being dumb. :)
Dalendrion u know the last line of ur cmnt is like inception ending scene for me.
what i mean is i didnt get it
vaishnavi Our feelings are often illusions. They are emotions. And emotions aren't logical.
So these feelings often give us an incorrect idea about reality.
You may feel dumb even if you aren't. You may feel smart even if you aren't.
after seeing your video I made a short python script with two functions, the first using the good, the second the poor algorithm. I made a list with 10000 random, not repeating characters and at the end AA. Here are the results:
good: (using a set and going through ones) 0.0789 sec
bad: 9.46 seconds!
Nice video, thanks for enlightening
Would hash set be better? In hash table you are storing another column count, which uses more space... In hash set, you only need to check whether the element is in the set. If it is already in the set, then you return this element right away...
Yeah using hash set would be another option. Same space complexity though.
CS Dojo its the same space complexity but hashset in this case is certainly a better option. I guess you can use the hash table and if interviewer asks for space optimization you can suggest a hashset with minimal code change
It hardly depends on the language. For instance, in Java HashMap is used internally in the HashSet collection thus it does not bring any memory optimization.
Agree , HashSet is better in my opinion too!. Thanks for your suggestion , Wendy!
what's the complexity of a look up in your hash table?
Actually the run time for the hashing variant is O(const) (and O(n) for small lists). We will find a double character within the first k+1 elements of the list where k is the number of valid characters.
If the string is encoded in say UTF-8 our charset has 8 bit, thus we will inevitably find a repeating character after 256 elements and can ignore the remaining list.
If our charset is even shorter (say only A-Z [note the capital]) as in this case, we only consider the first 27 characters. This number is independent of the lists actual size, thus it will work in constant time for long lists.
The same goes for the first variant which is O(n^2), we can prune comparing against characters that are more then charset+1 away from the start and will find one within the first charset + 1 characters. This will result in a runtime of O( [charset + 1]^2 ) which is lower then O(n^2) for big lists.
Which variant is faster then becomes interesting, because we might be able to further optimize via multicore processing or SIMD ...
This is too easy for a google question i feel
dota noob probably a warm-up question. I was told that their interviewer might ask a couple of simple questions before getting for a hard one.
If I were a google interviewer, I would ask after that: "Can you solve it with O(1) space?". Not so easy anymore?))
@@kharinskiyalexey7409 Without checking n characters we can't conclude so they can't ask like that
@@Abdulmajeed-sy1usof course you have to check you, go on :) but with O(1) space
Mhhh not necessarily. I don't think that the problems itself are unsolvable at these companies, I believe that they are more looking for how you solve it and if you can get to the uber-smart approach they are expecting (tough for me, since I mostly work after the pattern "make it work, optimize it later")
I have gone through google phone interview twice before and to be honest it's never as easy of this.
Interviewer asks question:
*Me* : Ummm can I go to the toilet and does it have wifi?
Go home and get your shine boxes jumped poor village training Lord37899 Henry
@@agnesmortey7266 Agnes Morty has issued an insult Lord Vyron 12937 Mark ii; the shoes are shined and feet are in the boxes
A rather simple operation with Time O(length of string) and space O (1) is using bit operations. Just define a mask 0, loop through the characters get bit of mask at location char-'A'. If 0 is gotten, set to 1. And continue looping, if 1, return char
Fundamentally, if you understand Data Structures and Algorithms you can solve this one. This is why those two classes are ALWAYS recommended (required even) before any elaborate code building. Great vid to reinforce the fundamentals
My thought was simply to iterate through the array and for each element, check the length of a set before and after adding the element to that set. If the length increases, that's the first time the element has occurred in the array. If the length stays the same, the element was already in the set and therefore it's the first recurring element.
most add functions actually return a boolean value for if the set was changed or not (at least in java). So all you would really have to do is if(!set.add(char)){ return char}
@@grantmartin2002 Interesting! Unfortunately, it doesn't work that way in python- it just returns "None". But I didn't know that about java!
I got the exact same question in my college exams.. and I wrote the first solution.
Guess what - I got the FULL marks😐😂😂😋😋
in real work environment, it will be like:
1. google 'find first recurring character'
2. click into stackoverflow, copy, done
🤣🤣🤣
accurate!!!! lol
Even if we don't have any recurring characters in the first 26 characters of the string, the 27th character will be recurring, since we have only 26 alphabets (assuming the string contains only alphabets). So time complexity is O(26), which can also be written as O(1).
Even if the string can contain all ASCII characters, it can still be considered O(1) according to me.
That's a deeper understanding of the problem, nice
But you still have to traverse the whole thing to find the element that is recurring. And if the input is smaller than 26 you can't use the pigeonhole principle.
@@sangramjitchakraborty7845 As soon as you find the first recurring character you can exit the for loop. The first recurring character can't come after 27th position, because for it to do so all the positions before it must contain different characters, which is not possible since only 26 characters are possible. Hence 27th position or lower positions must contain at least one recurring character which will be the first recurring character.
@@tornes Thank you
Ahh. I see what you mean. Thats a great approach.
Why do you need to use a hashtable to store an extra value of the count? Just use an arraylist.
PseudoCode:
Arraylist occured;
for char in Given_String:
if(!occurred.contains(char)){
occurred.insert(char);
}
else{
return char;
}
The two solutions that you mentioned (O(n^2) and O(n)) produce different results for the string ABBA. Now I am confused which one is first recurring char in ABBA, A or B. If it is B then your second solution would work properly (Set would be better though). But if it is A then we can use dictionary like you did with chars as keys and respective counts as values. We need to traverse the complete string to complete the dictionary then we could start traversing the string again and for every char we would refer dictionary for its count. Once we reach a char for which count is >1, return. Time complexity - O(n). Space - O(1). Any better solution?
I think the second solution is wrong.
his brute solution is wrong; like you suggested ABBA will return A when in fact ABBA should return B. For second method, I don't think it matters whether you use hashset/map or even an array. What does matter is that the space is not O(n) but rather O(1) since there are limited number of alphabets (52 if case sensitive, 26 otherwise).
Exactly what I was going to comment! The problem is not properly defined, is the first recurring character the first one to appear twice or the first one in the sequence that repeats? His solution only works in the first case.
exactly what I was confused about
I agree that 2nd solution gives correct result, since in ABBA, A recuring in 4th spot, and B is recurring in 3rd. However I not quite agree we have O(n) in second solution. Sure we go only forward the string, but we iterate each table row every char. Sure, most languages are making this for us in lower level, yet still are doing.
I just started uni and got the answer right, didn't think about the naive way at all. I come up with a good enough solution and then I optimize it. If you shoot for the stars right away, you'll struggle a lot because you're gonna get stuck on the details and you won't get anything from that. My high school computer science teacher used to say "you can't build a skyscraper all at once, start with the foundations, then build your way up"
The counts of the character is of no use, so why not use a Set (like hashset) instead.
Ganesh _ the complexity of hashset and hashtable is equivalent. Here it supposed the time complexity of ‘ if e in counts ‘ is 1. If the size of counts may grow large, it needs to optimize ‘if e in counts’.
Agree. Better optimized memory.
Some performance numbers in python (running the method on string.printable 10000 times):
List - 1.8005362025424931 seconds
Dictionary - 0.4816858277563984 seconds
Set - 0.2586124478794257 seconds
Looks like a set would have been the best choice.
Using hashset is still the same memory complexity. They are the same. You can use an array instead if you worry about the nonexistent memory overhead
It is useful for the problem he mentioned at the end.
In your assessment of the time complexity, you should add the time that it takes to actually create a hashtable and insert the values. That would have increased memory usage as well. Depending on your time and memory constraints, you have to use different approaches.
for (i from 0 to n - 1) {
character = input_string[ i ]
counts[character] = 1
if (counts.size() < i + 1)
return character
}
return none
This variation take advantage of the unicity of Hash keys
Ayoub Gacem this is a great solution that is actually O(n)
You don't even need a hashmap. Just use a mapping onto an array of size 2⁸ via the char number - constant read, write:
char frc(char* str) {
char* buf = calloc(256, 1);
int i = 0; len = strlen(str);
while(i < len && buf[str[i]] != str[i])
buf[str[i++]] = str[i];
return str[i];
}
him : asking him a very simple ques me: apply dfs on array of trees
You could use a bitmap to mark the seen characters and when the same character is seen the next time, you could return that character simply.
This way you save space as well by not tracking the character and the count in a dictionary/hash table.
For example, for 96 printable ASCII characters including special characters, you would need only 12 bytes to mark different characters that are seen as we pass each character.
Since we are interested only in the first reoccurring character we don’t need more than 12 bytes. We mark each character from the string using a lookup table and set the corresponding bit in the bitmap. We can have different ranges for special characters and normal characters in the bitmap and mark appropriately.
The first reoccurring character can be found when we try to set the bit which is already set.
This way we don’t use a lot of space as well as the time complexity is at minimum (which is similar to the solution presented in the video).
Well that was easy, using a hash table was literally the first thing that popped into my mind
I used Java for the solution. No need for a HashMap/HashTable. A simple ArrayList will do as we don't need to save the number of times a character appears in the string. One's we check that the next character is already in the list we stop the search, that's break out of the loop and return the value.
There's a lot of tough looking codes in the comments. Here's an easy one in Python 3 (I think):
s = input("")
ar = []
for i in s:
if s.count(i) > 1:
ar.append(i)
if ar:
print(ar[0])
else:
print("None!")
This is why I love python. Easy to understand.
It's better to use dictionaries than list, are more fast
The hash table is def more elegant and better time complexity. My first attempt in c++ was of a double for loop O(n^2), 2 array chars, & 1 basic char. One array char to hold the letters, another array char to assign & store duplicates found by a third plain char holding current indexed letter.
I'm so proud I solved it by my own
Me too :)
xd
In Haskell (obviously can be made shorter, but hopefully very readable and is evidently efficient):
--This function takes two lists and returns another. Each element of the second list is removed and put into the first list if not already present there, otherwise it remains in the second list.
sift :: Eq a => [a] -> [a] -> [a]
sift ts [] = []
sift ts (x:xs)
| x `elem` ts = x:(sift ts xs)
| otherwise = sift (x:ts) xs
--This function gives list of first (and later) repeats of elements.
repeats :: Eq a => [a] -> [a]
repeats xs = sift [] xs
--This function gives first element to repeat, or an error if no letter repeats.
firstRepeat :: Eq a => [a] -> a
firstRepeat xs
| null (repeats xs) = error "No element repeats."
| otherwise = head (repeats xs)
For first non-recurring character easy given above; just remove "repeats xs" from xs and take first element of the list.
I am student of First Semester of B.S(CS). I literally pused it and thought a rough algorithm and I made it on my FIRST try C++ ! :)
Really really happy to realize my hidden skills :-D
In python you can use string functions(built-in). If you put the letters in a list and then go with a for i in list, then you count each letter with list.count(i) and if it is >= 2 then print the letter and break!
Can't break if there are 2 recurring characters
We can actually terminate it just when the count of any of the characters become 2 since we are concerned about only the first recurring character.
You could also create an array of length 26 in which you insert the ascii code to int and increment the position and then when the index is equal to 2 stop and convert the index to the position getting the character
A simple hashing to 26 bits should work to avoid using extra space as well.
I like this and I was reaching for it in my head too, but I think to properly answer strings like "ADDA" with an 'A' you wouldn't be able to reduce this to a range/popcount problem.
Two pass method (python):
def firstNONRecurringCharacter(string):
dic = {}
for char in string:
if char not in dic:
dic[char] = 1
else:
dic[char]+=1
for char in string:
if dic[char] == 1:
return char
return False
print(firstNONRecurringCharacter(input()))
UNIX solved all of this over 40 years ago. You can man sort, sed, awk, grep et al.
I'd just search backwards for each char:
function focc(str) {
for (var i = 1; i < str.length; i++) {
if (str.substr(0, i).indexOf(str[i]) > -1) {
return str[i];
}
}
return null;
}
This way no other memory would be used
I guess it would not be much harder for me to crack their interview if they ask such questions
If you use sets in Python then you can reduce the complexity to just o(n). here is the code:
a = "ABCDA"
b = set()
for char in a:
if char in b:
print(char)
else:
b.add(char)
The complexity is still O(n) either way, the only difference is you save an extra 4 bytes per character using a set instead of a dictionary
A JavaScript solution:
function findRecurrence(str) {
//convert string to array
const arr = str.split("");
//construct new set from array and check if the size is the same
if(new Set(arr).size === arr.length) return null;
//loop through array and use slice method to extract elements starting at current index +1 so that the current index is not on the new array
//check if this new array contains the current element, return it if so
for(let i = 0; i < arr.length - 1; i++) {
if(arr.slice(i+1).indexOf(arr[i]) !== -1) return arr[i];
}
}
Good job. By performance purpose you can replace arr.slice() with arr.indexOf(arr[i], i + 1). Slice function creates a useless array, which turns the algorithm a bit slow
I created this gist to demonstrate my tests! Check this out: gist.github.com/thiago-tallison/36b3e826a856f9ffaa1cdd09dcf95265
IndexOf makes this solution n^2 which is just as bad as checking every pair.
my solution, for those interested (written in C#):
char? firstRecurring(string str)
{
if (str.Length - 1 == 0) return null;
List temp = new List();
temp.Add(str[0]);
for(int i = 1; i < str.Length - 1; i++)
{
if(temp.Contains(str[i]))
{
return str[i];
}
temp.Add(str[i]);
}
return null;
}
the reason I start with 1 instead of 0 is pretty straight forward, I want to have something to check against on the first pass in case indices 0 and 1 are the 1st recurring. No need to make a complete pass if you don't need to. And in case you're curious, my first conditional is there in case of a curve ball. Say they pass in the string "A", just return null prior to even running checks as you know there'll be no recurring characters. Hope this helps someone, good luck all
Thank you! It was pretty simple to solve. Wait for the harder ones :)
I think a linear solution is possible by using map in c++. I extract each character from the string and increment the count. If I get a count greater than 1, I print that character. Then in a visited array, I set the attribute to true so that I don't print the same character again.
I just started to learn programming at university and I think it`s too early for this kind of videos for me. lol
before watching the video what I would do is a loop that runs through a certain string and assigns checks each of the characters one by one starting at the beginning and for example “DCADAB” it would start at ‘D’ and then create a byte variable that would store that there is one d(byte d += 1;) and move on the the next and the loop ends when any of the variables = 2
Hey I've answered that right, so I'm now I Google employee? Nice! :D
Pretty simple but good to nail this down as it could be a building block to harder problems.
I was just thinking about adding them to an array and checking if they were in it....
I don't get it. They are already in a string, so you could just start at the 2nd level and see if its in the first position. Then continue to take the n-th letter and check it with the first n-1 letters. It uses the same amount of comparisons as his 'correct' solution.
Louis, both the solutions are correct but the second one is better than the first one as it takes much lesser comparisons. Your method uses same number of comparisons as his first method which is n(n-1)/2...
Checking if something exists in an array takes at best O(1), on average O(n/2) -> O(n), and at worst O(n) comparison. Checking something if it is in a hashmap/hashset takes at best O(1), on average O(1), at worst O(n). So adding an item into an array and then checking if it is in an array is O(n^2), which is what we want to avoid. Use a hashmap/hashset when you don't care about the order it gets added into the hashmap/hashset.
Leighton Lee Thanks, I get it now.
Leighton Lee, assuming there are only uppercase English letters (it seems so), you could use an array of 26 booleans and use the current char as index (its ASCII value minus that of 'A'). That way it's always O(1) for the lookup because you don't actually have to search for anything. If you're short on memory you could even use a 4byte bitmask in the same way :3
Congratulations, You took clear water and muddied it.
I would design a neural network to figure it out while I ate a snack
jydk37 wtf? hahaha
Lol
xD
You're selected
~google interviewer
Trying random solutions until you get the answer is bad. But if you do it fast enough it's called machine learning.
This *simple* problem can be a foundation to solve some appearingly complex problems. Thanks
This is my solution in java 8:
private static Character findFirstRecurring(String letter){
char[] l = letter.toCharArray();
Set list = new HashSet();
for (char c: l) {
if (!list.add(c)) {
return c;
}
}
return null;
}
Congrats, We're hiring you as Security Guard.
Tsetsen Mendsaikhan omg i am dying 😂😂
Lmao!
very nice bro
We don't actually need a hashset for that.
We can use simple uint32, since chars are in range 1-26 and we need a simple bool check.
Simply by checking bits on int.
int check = 0;
for (int i = 0 ;i < chars.count; i++) {
// make sure that value is in range 1-26
if (check & 1
Aren't both solutions O(n^2)? For the second solution, the programming language will have to compare char against each item in the list, won't it? That would make it O(n^2) if i'm not mistaken. Can anyone confirm/deny?
I thought so as well. But the comparison of the chars will only take a constant amount of time, because there is a finite number of possible characters
the 'key' is that unlike arrays hash tables have O(1) lookup time
You use for loop to iterate through the string nd check the index of character other the current position if gives index >-1 then it is an recurring character, in this case the loop will go only 1 time for both question 1 and 2 which is quicker than the map and sets
Don't these two solutions do different things?
Given the string "ABCBDA", solution 1 would return "A", whereas solution 2 would return "B", right?
Rowan Hatherley You are right
Rowan Hatherley, you absolutely right. I was so much confused doing this many times and came to know that this twp solutions gives two different answers.
Correct! I think he needs to clarify what is first recurring char. In a string ABBA, the first recurring char is A or B?
It's B. Basically, just look for the character you see twice first. Since you return after the first recurring character (B), the second, third, ..., recurring characters don't matter. ABCA returns A because A is the only recurring character, therefore, the first recurring character. BCABA returns B because B is the first recurring character. Given ABCBDA, it would return B since it's the first recurring character.
Hey guys Checkout this Google interview problem that's solved with 4 different approaches from scratch to code really quick at : ua-cam.com/video/ucMDHUzaH60/v-deo.html
'I recommend you pause the video and think about it for a second.'
It took me an hour and a half to come up with a naive solution and get it working in code
Me before 2:19
"Oh, hey, maybe I can understand coding.
Me after 2:19
"Nope"
Seanbo88 I wouldn't worry, the guy in the video doesn't understand coding either.
Watch some of his or other people's videos on Big O notation. It's not as hard and intimidating as it looks. CS Dojo's explanation of it is one of the better ones.
If it's just a string of letters (A-Z aka 26 different symbols), I'd just use a 32bit value, go through the string from left to right like you did, and for each letter first check if the corresponding bit is already set (using BITAND), if yes, return this character, if not set the bit (BITOR).
Such bit operations are a lot faster typically, often have hardware support and you only need 4 Bytes for the alphabet, no need to use any fancy data structures :)
Your naïve solution returns a different answer than your final solution for the case "abba." Therefore one of your solutions isn't a solution at all.
idk for abba we should return a or b?
b . Its the first recurring character
public String findFirstRecurring(char[] array) {
String answer = null;
for(int i=array.length - 1; i>0; i--) {
for(int j=i-1; j>0; j--) {
if(array[i] == array[j]) {
answer = "" + array[j];
}
}
}
return answer;
}
Thats the naïve solution I guess.
So there is no naive solution for this problem, basically.
Hey guys Checkout this Google interview problem that's solved with 4 different approaches from scratch to code really quick at : ua-cam.com/video/ucMDHUzaH60/v-deo.html
The first "naive" solution actually wouldn't even work in some scenarios. The string example you used was "DBCABA"... if the string was, say "DBCAAB" then the first solution would still output "B" which would be the wrong answer since A repeats before both B's.
Yeah you would need to keep an index of the rightest element when a pair is found, and then after brute forcing everything return the lowest index
If this is seriously the interview question, I might really throw my resume there right away
🤣🤣🤣🤣🤣
Whay is it n(n -1)/2 ? Especially why there's the division between 2?
Think about start placement in your loops. ABBA => starts with A then your sub array is (BBA) => start with B sub array (BA). That should help you understand how you get the n(n-1)
From what I see, most interview questions (specially on phone and online) are a coversion from a O(n^2) to O(n). And when you have it, hashmaps - there you go! :)
Saved my ass last Friday (before I saw this video though).
The best way is to have an array of size = 26 and increment the count based on the alphabet by traversing right to left. check if the count of the respective element while traversing itself. If count>1 then it's repeating. Check till the left most element.
how the fuck did I end up here?!
The answer would be different in "naive" and hash table method if the string is DBCAAB. In naive method it would return B while in other it will return A.
Either solution works, so if the requirements are as you specified then it shouldn't matter which one you use. You are making an assumption that we want to optimize on speed. If we want to optimize for memory size then the first solution you gave would be a better solution.
Timothy Fish The first solution would likely never be used regardless of optimization specifications. First, it gives the wrong answer in a situation such as ABBA (returns A, but the correct answer is B). Also, large data sets would take way too long
@@jackytaly , you're confusing the first recurring character with the first repeated character. In ABBA, A is the first recurring character because it is the first character that has a recurrence in the string, but the second B is the first repeated character. So, again, the requirements are more important to which algorithm is correct than optimization that may not be requirement at all.
Timothy Fish So in a string of say ABBCCDDEEFFGGA, you should return A as the first recurring character? No one would define “first recurring” as such. Recurring and repeating are interchangeable depending on who is defining the requirements, so it is not a matter of recurring vs. repeating. It is a matter of who is defining the problem, and no one would define it for A to be returned in this situation because it’s illogical and wouldn’t be useful in most situations
@@jackytaly, yes, I would say that A is the first recurring character. But if someone were to code it differently, I wouldn't say that they were wrong, just that the requirements weren't clearly written. But that's my point. You can't say that someone is wrong for writing code that optimizes for something other than what you think it should when you haven't specified what they should be optimizing for.
I use for loop in this case to either areive at the solution right away or create a key:pair diction to show the how many time the key appear.
Def letter_and_number(variables):
Counter ={}
for letter in variables:
If letter in counter:
Counter[letter] += 1
else:
Counter[letter] = 1
It's actually a very good exercise. Thank you.
I think it would be something like this in Java (though my first approach was the naive solution, I agree with using a Map instead)
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
public class MainApp {
public static void main(String[] args) {
//the subject String
String someString = "ABCDEFGAD";
//split subject String to an array
String[] someStringCharArray = someString.split("");
//the Map to fill in with individual character and count per character
Map map = new HashMap();
//start looping through comparing and counting
for(int i=0; i 1){
System.out.println(o);
}
}
}
}
this is the only google coding interview question that I can solve on my own lol
First question I ask on an interview... What sound does an owl make?
If you've heard one in flight, they're actually pretty quiet. Like a gentle "whoosh" sound.
A better use of a hashmap would be if we have to return a character that recurs 3 times or more. This will allow us to use the count column.
Ive got extremely minimal coding experience and knowledge BUT. I would take every charavter in the array and store it as a variable (INT) named itself. As the array is counted by the program, the variable adds +1 to whatever it sees. First one to get to 2 stops the program and outputs x variable.
"write some pseudo code"
*writes python*
XD classic
Hey bro...i am from india
My dream is to work in google as software engineer
Your channel is encouraging me
I am in std 10
Thank you so much cs dojo
first study hard and crack iit jee..then dream for google..stop wasting your time watching thses videos..in iit you will definitely get the knowledge
@@lipifying_life savage :v
@@lipifying_life you can get into Google even without IIT jee. Just need to have analytical mind.
If you can use JavaScript couldn't you run through your array once and compare indexOf with lastIndexOf and return the first value where they are not the same?
It would have to parse the array every time you use indexOf and lastindexOf. Not the most efficient solution.
It is not very efficient to make people read long names either
And it is also not very efficient to make people read unpronounceable names either.
...Lets start the bashing. :P
Juz kiddin though. Happy coding. :)
Will that work for string "ABBA"?
No
@@TheFreakinProgrammer with this it does:
function findRecurrence(str) {
for(let i = 0; i < str.length - 1; i++) {
let char = str.charAt(i);
if(str.indexOf(char) !== str.lastIndexOf(char)) return char;
}
return null;
}
don't need any data structure other than an array - my intuitive solution is to iterate over the chars in the string, push each char to the array as you go, and then each time check if it's already in the chars array. Here's a simple version of it in ruby!
def first_recurring_string(str)
encountered_chars = []
str.chars.each do |char|
return char if encountered_chars.include?(char)
encountered_chars
the idea of an array is perfect
In the second method, wouldn't the O-notation not be O(n) since in addition to checking the String you are also checking the created set for every character?
Less processing but more memory. Guess it depends on what hardware you want to utilize. But usually small if the string is anticipate to be small, then processing is valued over memory I assume. But the instruction won't be repeated, I think that's what the O is about, not overall complexity, but instruction repetition.
Oh, just noticed your comment is 3 years ago. Well, cheers.
@@MoJo01 well im glad you mentioned that, i had that thought as well so I am glad you left a reply. Ill have to look into it more, but now i no where to start so cheers to you!
In the case of an alphabet with 26 defined characters. Create a 26d array with values set to 0. preprocess your string to a list of ints. Go through list one by one, changing the index of the corresponding number in the array of 0’s to be 1. Then when the index is 1 already stop. Convert back to string. Arrays are faster than using hashes.
actually it is the same algorithm. hash tables using more space and time also.
Well, no, because the table is just an array with the int value of the character as the index. We don't have to search the table, but we do have to have memory to hold the table, which is not a given if we are developing embedded software.
If we're only guaranteed to analyze ASCII characters between 0x41 - 0x5A, the even more performant solution that consumes only 5 bytes of memory would be to use a the first 26 bits of a uint32_t initialized to 0 to keep track of the first occurrence of each character. The current bit index would be tracked by a uint8_t. When checking the next character sequentially, if the bit corresponding to that character is already 1, then return (char)(0x41 + m_flagIndex). m_flagIndex can be calculated by taking the current character and subtracting 0x41. This solution could also be expanded to 9 bytes of required storage if we need to handle both lower and uppercase characters.
As a beginner looking at this makes me realy doubt if i want to learn more about coding 😨
if this is enough to deter you then probably not
It took me three months of a CS degree education to understand and fully comprehend everything said in this video. Starting from someone with no knowledge of coding. Its really not to difficult once you understand the jargon. Discrete mathematics and a data structures class will make this a breeze.
@@MonsterhunterFTWWTF wtf 3 months? u can fricking understand this in 2 days.
Same solution can be made with lists, which may or may not be simpler;
def first_recurring(given_string):
letters = []
for char in given_string:
if char in letters:
return char
else:
letters.append(char)
Return null
This guy looks from macdanuru drive thru.
A hash set would suffice, e.g. (Java):
char findFirstRepeat(String s) {
Set set = new HashSet();
for(char c : s.toCharArray()) {
if(!set.add(c)) return c;
}
return 0;
}
Substituting one loop for another doesn't make your solution less naive.
The second solution is much more optimal in terms of time complexity. The first solution is the basic, "brute-force" method," and often the one that comes more naturally to beginner programmers. In that sense, it is more naive than the second.
for i:=1 to length(s) do inc(count[s[i]]);
for j:=‘a’ to ‘z’ do m:=max(m,count[j]);
for j:=‘a’ to ‘z’ do if count(j)=m then begin writeln(j); halt; end;
hey ,its very easy man.
Instead of storing the characters, we can use substring in java and we can find the character in o(n) without extra space complexity..
the second solution is incorrect and is also of O(n2) complexity as fetching data from a map also involves loop...
that's what i thought too...
if you have string "abcdefghijkmlopqrstuvwy zz"
you'd go O(n2) right?
Both solutions are not of the same complexity. The first is O(n^2), second one is actually O(n log(n)). Map lookup uses loops, but the loops doesn't go though all n element, only through log(n) elements.
Boris Brodski Depends on implantation of set/map. If it is a binary tree then O(log n). But of it is implemented using array internally then O(n).
raptor eagles Any general purpose hash map implementation will be more than O(n). An array based implementation for example needs to extend the array and reorder items after adding some amount of entries (or deal with lots of collisions).
In our example however, dealing with ascii characters as a key, we can use a static 256 bit array to mark characters. This will be O(n). But actually O(1), because we will never process more than 257 characters for input of any length.
Boris Brodski yeah that's right. but we have to implement that logic ourselves. default set/map implementations don't do that. might be bitset will help but it has its own limitations.
I’d use a Set. Over the loop if set.has(str[i]) then return it. Else set.add(str[i]).
Console.writeline("pls hire me senpai");
Ruby:
def recur(string)
repeats = []
string.length.times do |i|
repeats 1
end
return repeats.uniq!
end
Should add .first to return statement, repeats.uniq!.first
for i in string:
if string.count(i)>1:
return i
return "no recurring character found"
Err: Used return outside function