Want to give it a shot?? Sign up with us to make sure your upcoming interviews are the best they can be by practicing with our experienced engineers. interviewing.io/signup?.com&
Really good interview overall. Easy problem in the beginning but quite challenging under a set time limit by the end. The ending is awkward though and I love it! "Good luck with all your interviewing!" "Thanks! You.. you as well." sounds like something I would do haha
@@SimonsTechShow I don't agree 😕. If you prepare before the interview, you can become good at solving this specific kind of questions and it does not make you a better developer or engineer. It makes you better at this specific type of interviews just like playing chess doesn't make you suddenly good at maths or game theory. Even worse, I think it's possible to be a quite bad engineer, train hard on this sort of exercices and succeed. Conversely, you can be a quite good engineer and just completely fail. It's so far away from the problems you encounter on a daily basis IMO, it doesn't tell anything about how competent you are for the job. At least, if I were the interviewer, I wouldn't have had any clue on whether the interviewee is able or willing to follow the changes in the industry, is able to solve real-world problems with proper tooling (and why he would use that tool instead of some other), knows how to test his code and why, how he behaves in front of an open problem (can he find heuristics to simplify it?), does he have a profound knowledge of what he does/uses or is he just a superficial person… If you really want to evaluate problem solving skills, I think a Google Hashcode style open-problem is a better fit. The interviewee doesn't have to code live which causes some other issues and bias. You don't even need to look for a particular unique answer (which doesn't exist in real life anyways). You can just discuss with him of his answer, see if he knows the limitations, implications, evolutivity, if he has ideas on how to improve it. Talking of converting an n.log(n) algorithm to n, when 99.999% of the time it won't matter and will just make your code far less readable for the next person or yourself is ridiculous. And when on top of that your stack is mostly in a scripted language.
For anyone learning - there is actually a bug in the final solution of ins_del_compare() (with tolereance = 1). For strings with edit distance > 1, but length difference = 1 (e.g. "abdeX" and "abCdeF" function will throw StopIteration instead of returning false.
@@sanshinron Iterating through the string itself will not do since he needs elements from both strings. The pythonic thing to do in that case is probably to use zip to iterate both in parallel. Python2's zip has the same problem as range though, so you would have to use itertools.izip in that case to get the lazy version.
When they introduced the tolerance ... the solution i had was just a improvement of his first solution Something like : do you see any edge case i didnt think about ? def case_insensitive_compare(s1, s2): err_margin = 3 l_s1, l_s2 = len(s1), len(s2) index, err_counter = 0, 0 while index < max(l_s1, l_s2) and err_counter
I dislike how the interviewer went RIGHT into the question. No greetings, no introduction... The guy said “it’s my first one of these” and the dude literally didn’t answer lol
Philgob yeah that’s disappointing, the same happened to me yesterday, I thought maybe I did something wrong and they’re not talking to me, but it’s pretty standard!
I had an 45min coding interview where I had a long conversation with the interviewer, turns out later that the time spend on discussion was part of the coding challenge. I could not complete my challenge in less than 30 min. Of course I failed, I do not recommend wasting time during the coding task, keep all the talk for after.
Don't worry, they are all BS programming exercises they found in a book. Head over to Stackexchange and you'll find the solution posted to one of the other 10,000 people that have gotten the same question.
Yeah your daily job wont use much if any of this. I personally learned on my own through MIT freeware courses and projecteuler.net problems. The project eulers are actually kind of fun and you'll make break throughs if you really work on them but you need to have gotten through your first comp sci course or have equivalent experience to solve them. Some of them are extremely difficult specifically the ones for me anyways involving geometry and stuff.
I believe Google allows you to access the internet if you want. I saw it in one of such interviews where the interviewee asks the interviewer if he can quickly check something on the internet.
Mind you interviewer notices it all, and can "grade" you down, in his report or whatever they make, for that. I mean, you don't even know what they're searching, and pretty often these algos are the ones commonly asked, or atleast some component of it is.
Welcome to programming. Most of your time will be spent on stack overflow... Being a good programmer is also about being able to quickly find what is the source of the said problem and therefore find a solution quickly and effectively. Now chances are someone else before you ran into that problem which is why we also require to be able to browse forums & documentation in a way to minimize time spent looking for the solution and be apply to apply it in regards to our code.
There is an error with the code at 30:00. Let's take the input "AA" "BAB", in that case the length check passes, but the checks will go like "(A)A" "(B)AB" not a match, skip in longer to get "(A)A" "B(A)B" which matches "A(A)" "BA(B)" not a match, skipping the longer string raises a StopIteration (and the program crashes)
Exactly, a counter variable which counts the number of times one of the strings had to be advanced once more would have worked better for once because of scalability, and he should have caught these exceptions.
A different approach to the second part with the tolerance! def str_comp_dist2(str1,str2,tolerance):
list1 = max(list(str1.lower()),list(str2.lower())) list2 = min(list(str1.lower()),list(str2.lower())) len_missing = len([True for i in list1 if i not in list2]) + len([True for i in list2 if i not in list1]) if len_missing
i did this for the second part of the problem: def compare(str1,str2): err=0 order = sorted([str1,str2],key=lambda x: len(x), reverse=True) if len(order[0]) - len(order[1]) > 1: return False for i in order[0]: if i.upper() not in order[1].upper(): err +=1 if err > 1: return False return True
This is painful for me because I approach so many problems with future-proofing in mind. I started mapping a solve out in my head and I immediately assumed the difference tolerance should be optional and settable to any integer. That would make this problem particularly difficult for me because I'd be distracted the whole trying to make such a narrow solution.
For 8:31, if you're trying this stuff, please, please, use Python 3. There's no point in using Python 2 nowadays. It's soon ending support (January of 2020 if I remember correctly) and Python 3 provides quite a few nice abstractions to deal with the pain of strings and encoding. Also not to hate, but that solution is atrocious, a much better solution, which nice Python 3 abstractions would have been: ----- def case_insensitive_compare(s1, s2): if len(s1) != len(s2): return False if s1 is s2: return True return all(a.casefold() == b.casefold() for a, b in zip(s1, s2)) --- This makes use of a few tricks. First it checks if s1 and s2 are the same object in memory with is. Python (or CPython anyway) is quite smart and will try to optimise by storing a string in memory, and if another variable with the same string is created it will simply point to the same memory address (you can test this by creating two variables with the same string characters, and doing id(string) on each) Second, all() with the generator comprehensions and zip(). zip() returns a tuple of the iterators you pass it, in this case s1 and s2. It stops when one of the iterators is consumed. all() takes an iterator of True and False values, and if all are True it returns True (or False at the first False value). By using a generator comprehension, we can make it short circuit (so end early) at the first False value. Third, casefold(). This is Python's 3 attempt, with Unicode, to do case insensitive comparisons. Plenty of languages have special characters, with special case rules. casefold() provides the base lower string to use for comparison.
Well since he did the first function really well, I think a simple counter would do just fine. When they have the lengths different by 1 for instance, you can book a key,value pair for each character and their counts. First string will create the hash and second will add on to it. In the case 'ABC' and 'ABCD' for example the hash would look like: ,,,. If there are more than one '1' in the value list, it will return false. When user is asked for the edit distance, you do the same with one difference and that is you will not check the false statement for 'more than one 1 in the value list' but more than 1 in the value list'. I haven't tried this just typing while watching but I think this works and the code will look a lot cleaner and easier.
The guy knows some python (2 though) for sure, but he's never taken an algorithm course, Levenshtein distance and dynamic programming are so standard he would have at least remembered when he heard "edit distance". It's pretty clear he's reading about it at some point. From my point of view that's a long way from the technical level a Google engineer should have!
But he did mention it at the end of this video. So I am pretty sure he knows it. So your assumption that he doenst know it is at least wrong. Either that or he quickly googled it lmao.
Tried to follow along, this was my java solution. Tips appreciated! public static boolean caseInsensitiveCompare(String a, String b){ int editDistance = 0; int editLimit = 1; int smallLength = a.length() > b.length() ? b.length() : a.length(); int diff = Math.abs(a.length() - b.length()); if(diff > editLimit){ return false; } else { editDistance += diff; } for(int i = 0; i < smallLength; i++){ if(editDistance > editLimit){return false;}
if(Character.toUpperCase(a.charAt(i)) != Character.toUpperCase(b.charAt(i))){ editDistance++; } } return true; } I could also stick the tolerance as a method parameter and replace editLimit with the tolerance value
def compare(s1,s2,tolerance): its1 = iter(s1) its2 = iter(s2) miss = 0 for _ in range(max(len(s1),len(s2))): if next(its1,'none').upper() != next(its2,'none').upper(): miss = miss + 1 if miss > tolerance: return False return True print(compare('AB','abcde',2))
Even in the best case, final code around 12.25 will have time complexity of O(n) since he is checking length of both the strings. And len() function has linear complexity.
The len() function is not linear time, it is constant time. A list maintains a size variable that is O(1) time to access. The size is updated on each insertion / deletion of the list. Thus, when you need the len() it just returns that member variable under the hood. It doesn't count all the elements each time
I followed the questions and got to this code: def case_insensitive_compare(strA,strB, tolerance): str1, str2 = sorted([strA, strB], key=len) if len(str2)-len(str1) > tolerance: return False flag = 0 for char in range(len(str1)+(len(str2)-len(str1))): if char+flag == len(str1): return True if str1[char+flag].upper() != str2[char].upper(): flag -= 1 if flag < -tolerance: return False return True
len(str1)+(len(str2)-len(str1)) == len(str2) also in some usecases (ie. case_insensitive_compare('AbCdE', 'acdef', 2), strings are equal length, same number of insertions and deletions) your code will give a false negative. But good approach!
In my opinion, in a real interview, the candidate would have been rejected. Reasons: 1. Too many hints. 2. Sub-optimal solution. 3. Time / Space Complexity calculations were not sure either. Given these many flaws and considering the no. of candidates companies get, am sure its a reject. Sorry, no on-site.
Order is fixable by mantaining an index of letter in word in the map. But memory O(1) is indeed lost. Then we need to move two indices if they are equal and move only one if they are not and say the difference is 1, if that happens again - return false. This is probably what he is doing. This Python code is so unreadable I'm not sure but it has to be it. Thanks for pointing out about memory complexity.
def string_diff(str1, str2): short, long = sorted([str1, str2], key=lambda s: len(s)) diff=0 for i in range(len(long)): if i > len(short)-1: diff+=1 continue if short[i].lower() != long[i].lower(): diff+=1 return diff
This does not work. string_diff('abc', 'dabc' ) should give a difference of 1, but this gives 4. You need to modify the index you're comparing after a found difference. I've posted a solution below.
@@VivekYadav-ds8oz There is no reason to create an iterator, strings are iterable, there is no reason to call range as we don't need the index (use izip). Smaller other things: use all (/any) in these case, using python2 instead of python3 for an interview is strange. Finally you can even use map as the loop does more or less nothing interesting here (if you use all/any). In the end you could have (python3): def comp(x, y): def letter_eq(chars): a, b = chars return a.upper() == b.upper() return len(x) == len(y) and all(map(letter_eq, zip(x, y))) It does the exact same thing, but it looks like python code (if you prefer you could still split the last test in two lines, if you find it more readable).
looks like a tool made specifically for these interviews where there is a set of problems and you select your language. the style of the editor looks like sublime. ps if you arent on neovim you should be.
def edit_distance_str(s1,s2,tolerance=0): short_str, long_str = sorted((s1,s2),key=len) edit_distance=len(long_str)-len(short_str) if edit_distance > tolerance: return False else: for i in range(0,len(short_str)): if short_str[i].lower() not in long_str.lower(): edit_distance = edit_distance + 1 if edit_distance > tolerance: return False return True
As a function of the length of the string, L, how long will the program take on the highest order, and how much space will it take. Answers would be something like Linear or Big O of L, quadratic or Big O of L^2. Usually this is under Big O notation, which has a wikipedia for more information.
I hate to say it, but I would fail this guy. Weird iterator code, incorrect line #20, incorrect running times, taking forever to answer the basic questions, and escaping the last question by saying you had to leave.
He could've used the first function, remove the first if statement. take in tolerance as a parameter, set a counter "differences = 0" then change the if not statement to increment the differences counter. then add an if differences == tolerance return False. anyone see an issue with this?
/* C++ version solution of case insensitive strings. */ int isEqual(string a, string b) { a = allLowerCase(a); b = allLowerCase(b); if(a == b){ return 1; }else{ return 0; } } string allLowerCase(string a) { for(int i = 0; i < a.length(); i++){ if(a[i] >= 65 && a[i]
Once more... They are complicating the python code for a simple algorithms... Doesn't he just want confirmation that they strings will be the same - but not easily confused with another string? for example, by only having the length of the code and upper as parameters for being the same word, the both strings could have been confused as being the same although they were not.. by another word that was equally long as the other. Instead of confusing himself - he could have just done this simple code to make sure that you knew what to do with these strings if they are different or the same: def function(s1, s2): s1 = s1.lower() s2 = s2.lower() s_one_len = len(s1) s_two_len = len(s2) if s_one_len == s_two_len: print('ITS TRUE') if s1 == s2: print('Its double TRUE') if s1[::1] == s2[::1]: print('Its tripple true') else: print('ITS false') function('abc12','ABC12')
It's interviewing.io, you get to interview with real tech company engineers for practice. You are granted only 2 or 3 interviews. If you do well on any, then you can decide to share your info with the interviewer and if they liked you they could actually ask you to interview for real with them. But if the interview didn't go well you can stay anonymous. It's good practice and good if you're job hunting, big tech companies really do use it.
Funny how it becomes "This is a recording of a mock interview..." when the title states "Technical interview with a Google engineer:..." Classical clickbait. Never knew the product but first point is negative cuz of the deception you're trying to use. Shall I report?
def compare(s1,s2,tolerance): its1 = iter(s1) its2 = iter(s2) miss = 0 for _ in range(max(len(s1),len(s2))): if next(its1,'none').upper() != next(its2,'none').upper(): miss = miss + 1 if miss > tolerance: return False return True print(compare('AB','abcde',2))
@@ijazahmad722 Well no, it won't work, just take the example of 'bc' and 'abc' with tolerance 1, that will return False with your algorithm, while the answer is True.
this is so easy though.. sizeVar=math.abs(str1.len-str2.len) if sizeVar>tolerance : return false numMistakes=sizeVar iterate index through one stringSize if char i of either string is nonexistent (i==len of one of the strings) return true if char i.upper of str1 != char i.upper of str2 numMistakes++ if(numMistakes>tolerance) return false after iterate return true
Razer420 this wouldnt work i dont think. your check for equality requires the same char at the same index, if there was a deletion, youd add a mistake but then every character after that, would also be considered a mistake since youre not accounting for the deletion when indexing. a fix i think would be to keep track of mistakes, and then figure out which string has the deleted one probably the shorter string and always have the index check by i - mistakes (i - #deleted) but then im still not fully sure this would fix everything.
@@omarhabra6689 It said it at the beginning, and they freaking wrote it the whole time.. if someone was wondering.. why is he even watching this video when he doesn't know anything about coding
Google has huge amount of computing resources and top notch researchers, can't they develope an AI to interview candidates? It would save a ton of costly man hours spent on interviewing...
def string_diff(str1, str2): short, long = sorted([str1, str2], key=lambda s: len(s)) diff=0 for i in range(len(long)): if i > len(short)-1: diff+=1 continue if short[i].lower() != long[i].lower(): diff+=1 return diff
Want to give it a shot?? Sign up with us to make sure your upcoming interviews are the best they can be by practicing with our experienced engineers. interviewing.io/signup?.com&
"let me think this through"
*goes on stackoverflow for 5 minutes*
high key
bruh why does my heart rate go up when watching these
Really good interview overall. Easy problem in the beginning but quite challenging under a set time limit by the end.
The ending is awkward though and I love it! "Good luck with all your interviewing!" "Thanks! You.. you as well." sounds like something I would do haha
Simon Kay well the interviewer is also "interviewing" other candidates lol
You call this a good interview? Don't think this helps finding good engineers.
@@Madinko12 What's wrong with it? Shows problem solving skills
@@SimonsTechShow I don't agree 😕. If you prepare before the interview, you can become good at solving this specific kind of questions and it does not make you a better developer or engineer. It makes you better at this specific type of interviews just like playing chess doesn't make you suddenly good at maths or game theory. Even worse, I think it's possible to be a quite bad engineer, train hard on this sort of exercices and succeed. Conversely, you can be a quite good engineer and just completely fail. It's so far away from the problems you encounter on a daily basis IMO, it doesn't tell anything about how competent you are for the job. At least, if I were the interviewer, I wouldn't have had any clue on whether the interviewee is able or willing to follow the changes in the industry, is able to solve real-world problems with proper tooling (and why he would use that tool instead of some other), knows how to test his code and why, how he behaves in front of an open problem (can he find heuristics to simplify it?), does he have a profound knowledge of what he does/uses or is he just a superficial person…
If you really want to evaluate problem solving skills, I think a Google Hashcode style open-problem is a better fit. The interviewee doesn't have to code live which causes some other issues and bias. You don't even need to look for a particular unique answer (which doesn't exist in real life anyways). You can just discuss with him of his answer, see if he knows the limitations, implications, evolutivity, if he has ideas on how to improve it. Talking of converting an n.log(n) algorithm to n, when 99.999% of the time it won't matter and will just make your code far less readable for the next person or yourself is ridiculous. And when on top of that your stack is mostly in a scripted language.
the interviewer is autistic af
For anyone learning - there is actually a bug in the final solution of ins_del_compare() (with tolereance = 1). For strings with edit distance > 1, but length difference = 1 (e.g. "abdeX" and "abCdeF" function will throw StopIteration instead of returning false.
Which he could have caught, but his solution was just not scalable (in terms of longer edit distance) from the start.
13:30 Minor nitpick. The space complexity of that code is O(n) just because range is used rather than xrange. In python2 range generates a list.
No need for range at all, he could just iterate the string itself.
@@sanshinron Iterating through the string itself will not do since he needs elements from both strings. The pythonic thing to do in that case is probably to use zip to iterate both in parallel. Python2's zip has the same problem as range though, so you would have to use itertools.izip in that case to get the lazy version.
So the question is, why is he using python2 :p
@@alcesmir iterating through the string just for counting, not for using the elements, just as he is iterating through the range for counting only.
@@osquigene so he can write print instead of print()
When they introduced the tolerance ... the solution i had was just a improvement of his first solution
Something like :
do you see any edge case i didnt think about ?
def case_insensitive_compare(s1, s2):
err_margin = 3
l_s1, l_s2 = len(s1), len(s2)
index, err_counter = 0, 0
while index < max(l_s1, l_s2) and err_counter
I dislike how the interviewer went RIGHT into the question. No greetings, no introduction... The guy said “it’s my first one of these” and the dude literally didn’t answer lol
Philgob yeah that’s disappointing, the same happened to me yesterday, I thought maybe I did something wrong and they’re not talking to me, but it’s pretty standard!
I had an 45min coding interview where I had a long conversation with the interviewer, turns out later that the time spend on discussion was part of the coding challenge. I could not complete my challenge in less than 30 min. Of course I failed, I do not recommend wasting time during the coding task, keep all the talk for after.
#clickbait I wanted to see a Mighty Eel vs. an Intergalactic Avenger. This isn't even a SciFi channel movie.
I'm majoring in Comp Sci. and seeing interview questions like these get me scared cuz I like have zero confidence in my abilities.
With time and hard work comes confidence in your abilities. Everyone was afraid at first.
Don't worry, they are all BS programming exercises they found in a book. Head over to Stackexchange and you'll find the solution posted to one of the other 10,000 people that have gotten the same question.
Yeah your daily job wont use much if any of this. I personally learned on my own through MIT freeware courses and projecteuler.net problems. The project eulers are actually kind of fun and you'll make break throughs if you really work on them but you need to have gotten through your first comp sci course or have equivalent experience to solve them. Some of them are extremely difficult specifically the ones for me anyways involving geometry and stuff.
95% of these interviews are useless. They happen because no one knows a better way to assess and compare candidates.
Surprisingly insecurity is most likely among the ones who start programming through school.
i'm pretty sure the interviewiee was searching the internet, you can hear clicks and typing during the long silences
I believe Google allows you to access the internet if you want. I saw it in one of such interviews where the interviewee asks the interviewer if he can quickly check something on the internet.
Mind you interviewer notices it all, and can "grade" you down, in his report or whatever they make, for that. I mean, you don't even know what they're searching, and pretty often these algos are the ones commonly asked, or atleast some component of it is.
Welcome to programming. Most of your time will be spent on stack overflow... Being a good programmer is also about being able to quickly find what is the source of the said problem and therefore find a solution quickly and effectively. Now chances are someone else before you ran into that problem which is why we also require to be able to browse forums & documentation in a way to minimize time spent looking for the solution and be apply to apply it in regards to our code.
If a company expects you to memorize every single detail of a language and it's libraries, they are idiots.
There is an error with the code at 30:00. Let's take the input "AA" "BAB", in that case the length check passes, but the checks will go like
"(A)A" "(B)AB" not a match, skip in longer to get "(A)A" "B(A)B" which matches
"A(A)" "BA(B)" not a match, skipping the longer string raises a StopIteration (and the program crashes)
Exactly, a counter variable which counts the number of times one of the strings had to be advanced once more would have worked better for once because of scalability, and he should have caught these exceptions.
A different approach to the second part with the tolerance!
def str_comp_dist2(str1,str2,tolerance):
list1 = max(list(str1.lower()),list(str2.lower()))
list2 = min(list(str1.lower()),list(str2.lower()))
len_missing = len([True for i in list1 if i not in list2]) + len([True for i in list2 if i not in list1])
if len_missing
i did this for the second part of the problem:
def compare(str1,str2):
err=0
order = sorted([str1,str2],key=lambda x: len(x), reverse=True)
if len(order[0]) - len(order[1]) > 1:
return False
for i in order[0]:
if i.upper() not in order[1].upper():
err +=1
if err > 1:
return False
return True
This is painful for me because I approach so many problems with future-proofing in mind. I started mapping a solve out in my head and I immediately assumed the difference tolerance should be optional and settable to any integer. That would make this problem particularly difficult for me because I'd be distracted the whole trying to make such a narrow solution.
I think that's a sign of more planning needed before solving
For 8:31, if you're trying this stuff, please, please, use Python 3. There's no point in using Python 2 nowadays. It's soon ending support (January of 2020 if I remember correctly) and Python 3 provides quite a few nice abstractions to deal with the pain of strings and encoding. Also not to hate, but that solution is atrocious, a much better solution, which nice Python 3 abstractions would have been:
-----
def case_insensitive_compare(s1, s2):
if len(s1) != len(s2):
return False
if s1 is s2:
return True
return all(a.casefold() == b.casefold() for a, b in zip(s1, s2))
---
This makes use of a few tricks. First it checks if s1 and s2 are the same object in memory with is. Python (or CPython anyway) is quite smart and will try to optimise by storing a string in memory, and if another variable with the same string is created it will simply point to the same memory address (you can test this by creating two variables with the same string characters, and doing id(string) on each)
Second, all() with the generator comprehensions and zip(). zip() returns a tuple of the iterators you pass it, in this case s1 and s2. It stops when one of the iterators is consumed. all() takes an iterator of True and False values, and if all are True it returns True (or False at the first False value). By using a generator comprehension, we can make it short circuit (so end early) at the first False value.
Third, casefold(). This is Python's 3 attempt, with Unicode, to do case insensitive comparisons. Plenty of languages have special characters, with special case rules. casefold() provides the base lower string to use for comparison.
Well since he did the first function really well, I think a simple counter would do just fine. When they have the lengths different by 1 for instance, you can book a key,value pair for each character and their counts. First string will create the hash and second will add on to it. In the case 'ABC' and 'ABCD' for example the hash would look like: ,,,. If there are more than one '1' in the value list, it will return false. When user is asked for the edit distance, you do the same with one difference and that is you will not check the false statement for 'more than one 1 in the value list' but more than 1 in the value list'. I haven't tried this just typing while watching but I think this works and the code will look a lot cleaner and easier.
Would not work in case of ABC and ABDD in case tolerance for edit distance is 1...
The guy knows some python (2 though) for sure, but he's never taken an algorithm course, Levenshtein distance and dynamic programming are so standard he would have at least remembered when he heard "edit distance". It's pretty clear he's reading about it at some point. From my point of view that's a long way from the technical level a Google engineer should have!
/r/iamverysmart
@@TheMaxofSpades ^^
If he didn't know, or just forgot, then it's pretty impossible to figure it out in a couple of minutes.
pretty sure he google searched that part off-screen..
But he did mention it at the end of this video. So I am pretty sure he knows it. So your assumption that he doenst know it is at least wrong. Either that or he quickly googled it lmao.
8:20 that damn Macbook click
hahaha
Tried to follow along, this was my java solution. Tips appreciated!
public static boolean caseInsensitiveCompare(String a, String b){
int editDistance = 0;
int editLimit = 1;
int smallLength = a.length() > b.length() ? b.length() : a.length();
int diff = Math.abs(a.length() - b.length());
if(diff > editLimit){
return false;
} else {
editDistance += diff;
}
for(int i = 0; i < smallLength; i++){
if(editDistance > editLimit){return false;}
if(Character.toUpperCase(a.charAt(i)) != Character.toUpperCase(b.charAt(i))){
editDistance++;
}
}
return true;
}
I could also stick the tolerance as a method parameter and replace editLimit with the tolerance value
def compare(s1,s2,tolerance):
its1 = iter(s1)
its2 = iter(s2)
miss = 0
for _ in range(max(len(s1),len(s2))):
if next(its1,'none').upper() != next(its2,'none').upper():
miss = miss + 1
if miss > tolerance:
return False
return True
print(compare('AB','abcde',2))
As I've commented a bit earlier that would not work.
I'm pretty sure that's Joma's voice xD
I was thinking more Kumar from Harold and Kumar the whole time lol
def compare(s1, s2, dis):
if dis < abs(len(s1) - len(s2)):
return False
for i in range(min(len(s1), len(s2))):
if s1[i].upper() != s2[i].upper():
return compare(s1[i+1:], s2[i:], dis-1) or compare(s1[i:], s2[i+1:], dis-1)
return True
public boolean compareCaseInsensitive(String str1,String str2){
return(str1.equalsIgnoreCase(str2));
}
//unless we're asked to define equalsIgnoreCase() itself
first i would check string length then see if first and last letter are the same then execute
25:00 "aw shit"
Even in the best case, final code around 12.25 will have time complexity of O(n) since he is checking length of both the strings. And len() function has linear complexity.
The len() function is not linear time, it is constant time. A list maintains a size variable that is O(1) time to access. The size is updated on each insertion / deletion of the list. Thus, when you need the len() it just returns that member variable under the hood. It doesn't count all the elements each time
@@davidgaster
Thanks. Didn't know that.
I followed the questions and got to this code:
def case_insensitive_compare(strA,strB, tolerance):
str1, str2 = sorted([strA, strB], key=len)
if len(str2)-len(str1) > tolerance:
return False
flag = 0
for char in range(len(str1)+(len(str2)-len(str1))):
if char+flag == len(str1):
return True
if str1[char+flag].upper() != str2[char].upper():
flag -= 1
if flag < -tolerance:
return False
return True
len(str1)+(len(str2)-len(str1)) == len(str2) also in some usecases (ie. case_insensitive_compare('AbCdE', 'acdef', 2), strings are equal length, same number of insertions and deletions) your code will give a false negative. But good approach!
In my opinion, in a real interview, the candidate would have been rejected. Reasons:
1. Too many hints.
2. Sub-optimal solution.
3. Time / Space Complexity calculations were not sure either.
Given these many flaws and considering the no. of candidates companies get, am sure its a reject. Sorry, no on-site.
This seems to be mocked up interview ! Google uses Google Docs :) !!
Will a comparison between the ID(variable) function and if they are == then it is true and if not false work?
why not to use a map of upper case letters and increment each one if there is one in the s1 and s2 and then see if all of them are 2 except 1?
wont be O(1) memory anymore
Not only you assume that every letter is only used once but you also lose order: abcdef != fedcba
Order is fixable by mantaining an index of letter in word in the map. But memory O(1) is indeed lost. Then we need to move two indices if they are equal and move only one if they are not and say the difference is 1, if that happens again - return false. This is probably what he is doing. This Python code is so unreadable I'm not sure but it has to be it. Thanks for pointing out about memory complexity.
def string_diff(str1, str2):
short, long = sorted([str1, str2], key=lambda s: len(s))
diff=0
for i in range(len(long)):
if i > len(short)-1:
diff+=1
continue
if short[i].lower() != long[i].lower():
diff+=1
return diff
This does not work. string_diff('abc', 'dabc' ) should give a difference of 1, but this gives 4. You need to modify the index you're comparing after a found difference. I've posted a solution below.
@@dirklaren7266 You're right, my solution does not cover many cases
@@dirklaren7266 You're right, my solution does not cover many cases
The Mighty El is pausing with that silence that comes with looking up shit on StackOverflow
I'm confused, is the interviewer the Google engineer or the interviewee?
@Winston Mcgee oh I see
def edit_distance_compare(s1, s2, tolerance=2):
# O(max(s1, s2)) time; O(1) space
# Not expecting equality very often
if abs(len(s1) - len(s2)) > tolerance:
return False
# s2 is never shorter
if len(s1) > len(s2):
s1, s2 = s2, s1
offset = 0
for i, c1 in enumerate(s1):
c1 = c1.lower()
while True:
c2 = s2[i + offset].lower()
if c1 == c2:
break
else:
offset += 1
if offset > tolerance:
return False
return offset
s1_iter = iter(s1) killed me xD
Why?
@@VivekYadav-ds8oz There is no reason to create an iterator, strings are iterable, there is no reason to call range as we don't need the index (use izip). Smaller other things: use all (/any) in these case, using python2 instead of python3 for an interview is strange. Finally you can even use map as the loop does more or less nothing interesting here (if you use all/any).
In the end you could have (python3):
def comp(x, y):
def letter_eq(chars):
a, b = chars
return a.upper() == b.upper()
return len(x) == len(y) and all(map(letter_eq, zip(x, y)))
It does the exact same thing, but it looks like python code (if you prefer you could still split the last test in two lines, if you find it more readable).
@@dorrelmatad160 at that time even 3.4 was released
osquigene are you a senior eng
Which Ide or software they are using ?
Amit Joshi Sublime Text I’m guessing
It's easy they are using just vim
looks like a tool made specifically for these interviews where there is a set of problems and you select your language. the style of the editor looks like sublime. ps if you arent on neovim you should be.
The guy was googling, and reading haha
def edit_distance_str(s1,s2,tolerance=0):
short_str, long_str = sorted((s1,s2),key=len)
edit_distance=len(long_str)-len(short_str)
if edit_distance > tolerance:
return False
else:
for i in range(0,len(short_str)):
if short_str[i].lower() not in long_str.lower():
edit_distance = edit_distance + 1
if edit_distance > tolerance:
return False
return True
what do they mean by the time and space complexity?
As a function of the length of the string, L, how long will the program take on the highest order, and how much space will it take. Answers would be something like Linear or Big O of L, quadratic or Big O of L^2.
Usually this is under Big O notation, which has a wikipedia for more information.
Thank you
don't know how to answer any of the questions from 5:23 and onwards. gg
arkoraa don’t know how to answer any of the questions from 0:00
i could answer most this in c++ or C# but not in python
I hate to say it, but I would fail this guy. Weird iterator code, incorrect line #20, incorrect running times, taking forever to answer the basic questions, and escaping the last question by saying you had to leave.
He could've used the first function, remove the first if statement. take in tolerance as a parameter, set a counter "differences = 0" then change the if not statement to increment the differences counter. then add an if differences == tolerance return False. anyone see an issue with this?
Yes. You only have insertions and deletions, not modifications, so the distance between 'abc' and 'adc' is 2, not 1.
Second case would've been fixed if he used lower instead of upper, no extra credit.
Testing for the nitty gritty details of a language, and their ability to prematurely optimize, seems like a really shitty way to evaluate somebody.
/* C++ version solution of case insensitive strings.
*/
int isEqual(string a, string b)
{
a = allLowerCase(a);
b = allLowerCase(b);
if(a == b){
return 1;
}else{
return 0;
}
}
string allLowerCase(string a)
{
for(int i = 0; i < a.length(); i++){
if(a[i] >= 65 && a[i]
Once more... They are complicating the python code for a simple algorithms...
Doesn't he just want confirmation that they strings will be the same - but not easily confused with another string?
for example, by only having the length of the code and upper as parameters for being the same word, the both strings could have been confused as being the same although they were not.. by another word that was equally long as the other.
Instead of confusing himself - he could have just done this simple code to make sure that you knew what to do with these strings if they are different or the same:
def function(s1, s2):
s1 = s1.lower()
s2 = s2.lower()
s_one_len = len(s1)
s_two_len = len(s2)
if s_one_len == s_two_len:
print('ITS TRUE')
if s1 == s2:
print('Its double TRUE')
if s1[::1] == s2[::1]:
print('Its tripple true')
else:
print('ITS false')
function('abc12','ABC12')
the ammount of "likes" and "uhm" kills me man
I tested on the python shell: a = 'ábc' b = 'ÁBC' and then a.upper() == b.upper() and was returned True.
I'm calling bs, because Google starts interviews by explaining the process first. Second, they use Google docs to do the interview.
Read the second paragraph of the video description…
@@spesterwecial so not really an interview.
This is most certainly a mock interview. If you disagree, you are wrong lol
It's interviewing.io, you get to interview with real tech company engineers for practice. You are granted only 2 or 3 interviews. If you do well on any, then you can decide to share your info with the interviewer and if they liked you they could actually ask you to interview for real with them. But if the interview didn't go well you can stay anonymous. It's good practice and good if you're job hunting, big tech companies really do use it.
Funny how it becomes "This is a recording of a mock interview..." when the title states "Technical interview with a Google engineer:..." Classical clickbait. Never knew the product but first point is negative cuz of the deception you're trying to use. Shall I report?
Gosh.. just keep a counter of the edit distance.. way simpler..
I just wrote a stupid solution , its working , I'm not sure if there are some cases it won't work , I just posted in comments here
def compare(s1,s2,tolerance):
its1 = iter(s1)
its2 = iter(s2)
miss = 0
for _ in range(max(len(s1),len(s2))):
if next(its1,'none').upper() != next(its2,'none').upper():
miss = miss + 1
if miss > tolerance:
return False
return True
print(compare('AB','abcde',2))
@@ijazahmad722 Well no, it won't work, just take the example of 'bc' and 'abc' with tolerance 1, that will return False with your algorithm, while the answer is True.
tough...
Uh uh uh uh uh uh uh IM SHITTING MY PANTS!!! Uh! Uh uh!
this is so easy though..
sizeVar=math.abs(str1.len-str2.len)
if sizeVar>tolerance :
return false
numMistakes=sizeVar
iterate index through one stringSize
if char i of either string is nonexistent (i==len of one of the strings)
return true
if char i.upper of str1 != char i.upper of str2
numMistakes++
if(numMistakes>tolerance)
return false
after iterate
return true
Razer420 this wouldnt work i dont think. your check for equality requires the same char at the same index, if there was a deletion, youd add a mistake but then every character after that, would also be considered a mistake since youre not accounting for the deletion when indexing. a fix i think would be to keep track of mistakes, and then figure out which string has the deleted one probably the shorter string and always have the index check by i - mistakes (i - #deleted) but then im still not fully sure this would fix everything.
Not even close :)
This guy kinda sucks at being interviewed. Speak up chap.
Python 2...ew
xD
Python... ewww
Y no c++
This dude is not ready for a real interview
Python Interview for those who are wondering
No one was wondering 😂
@@omarhabra6689 It said it at the beginning, and they freaking wrote it the whole time.. if someone was wondering.. why is he even watching this video when he doesn't know anything about coding
@@omarhabra6689 And just because it has likes doesnt mean that they needed the information..
Lmao
Google has huge amount of computing resources and top notch researchers, can't they develope an AI to interview candidates? It would save a ton of costly man hours spent on interviewing...
No they can't. I think you are watching too much AI hype videos. It's not even close to that at THIS point. Maybe someday.
If they develop an AI that can take interviews of this level then there is no need to hire software engineers... AI can do that job better
Hurry up and take your site out of beta ffs
I wouldn’t hire this guy just because of how many times he say “uhh, umm”... very annoying!
Damn, I wouldn't hire you because you are a human and human needs to be maintained
Dat Dude LOL
And i wouldn't hire you because you seems like a prick to others.
I wouldn't hire you coz you use too many dots "..." 😂
You're a BAD programmer
def string_diff(str1, str2):
short, long = sorted([str1, str2], key=lambda s: len(s))
diff=0
for i in range(len(long)):
if i > len(short)-1:
diff+=1
continue
if short[i].lower() != long[i].lower():
diff+=1
return diff