Google Coding Interview with an ex-Microsoft Software Engineer

Hope this was fun to watch as we simulated a real world Interview over Google Hangouts.
"Going Greedy does result in minimization but it comes at a cost, and that cost is Wrong Answer".

Part II and other links are in the description.

i was out when 793 ist one of your favorite numbers, "but 793 is not necessarily occouring" even when 793 was in the input number.
but also im an dumb average guy ..

Trie

why not just create a function to look through the given values of pi for text matches

We can do it in better complexity by using aho corasick algorithm. This will give time complexity of O(n + m).

Why not just use regex

Why do my interviewers run after small mistakes like forgetting to set value of dp[pos] before returning from check() or at the line where it returns early on finding ans is EQUAL to UNDEFINED?
I could never get away with those 🥲

Regarding the fun intro to the interview, it hasn't been proven whether or not pi has the property that any finite string of digits occurs in the decimal representation as was described by Clement. It is only conjectured that it does.

Thing I learned from this video is to make an interactive interview session, Interviewer should be that much supportive. Please bring such topics which really gives feeling of giving interview with sense of thinking that needs to be followed by candidate while giving interviews.

I swear this seems so similar to word break on leetcode.

If this was an actual interview its a guaranteed fail as the answer was not clear in code and the dp addition feels forced. Also, the solution is heavily reliant on global variables which is almost never the case in a real production environment.

I don't know who is host and who is guest !!!!

He is an ex_Microsoft Software Engineer and uses a MacBook. Do you know the reason why doesn't he work there?

I can use trie

Anjali :why you cancelled my order?

They have explained the easy problem in a hard way just to promote their algo expert.... This is simple word break problem......and simple approach is start taking character from starting and when u find any match in favorite arr you have two choices either you split or continue with next charater...try both ways . And find min spaces.....add some memoization to optimize

Iterate over favArray instead of pi in the check function. Although the time complexity seems higher, the average best-case scenario would probably be better (say if length(favArray) is smaller and/or length of each value in favArray are longer). Is my assumption correct?

I understand the problem and how to do it in no time but the thing is my Implementation sucks... Well, I just completed C data structures...

These days interviewers think like every candidate is a Damn & hardcore CODER,,,,

i've never done a coding interview but i'm wondering, why is the code written on a text file? isn't it supposed to be run? or the code isn't actually run in tech/coding interviews?

Thanks dude. your way of thinking helped me learn a lot !!

Law of large numbers

def minSpaces(target, wordBank):
targetLength = len(target)
table = [-1 for _ in range(targetLength + 1)]

for i in range(targetLength + 1):
if table[i] != -1 or i == 0:
for word in wordBank:
wordLength = len(word)
if (wordLength + i <= targetLength) and (target[i: (i + wordLength)] == word):
newMinSpace = table[i] + 1
if table[i + wordLength] == -1 or newMinSpace < table[i + wordLength]:
table[i + wordLength] = newMinSpace
return table[targetLength]

I'm not pro at algos but off the top of my head I'll use a sliding window to check through the string and get minimal substrings found in the array. It'll be o (n) too

This is basically backtracking to try everything, but caching best result makes it a DP...

Was it neccesary to show macbook and cover half of the screen. Its not a luxury nowdays ;)

Pie = 3.14blablabla
thanks for the info, I can use this in tomorrows math test. I am sure that I will get A+ grade. Thanks once again.

Ex Google Software Engineer using Apple Airpods Pro and Ex Microsoft Software Engineer using a Macbook. Whats this ;-;

this video is so helpful I can sleep faster now 😂

Work hard until your name will be added to algoexpert for discount 😀

Bfs

Can this be solved using a trie instead? just add the fav array in there, and then check the main string. ?

Can someone tell me which language they are using to make code

Hi, 2 questions:
1) where are u assigning the values to dp[] during memoization,
2) Also the statement should be: if ans!=UNDEFINED then return ans

We can insert all the favourtie strings into a "Trie" data structure. And then while we pass thru the large string, we can check if that partial string exists in trie. If it exists, break it up.

ex-Google: I'm gonna interview you.
ex-Microsoft: ok
[A few moments later]
ex-Microsoft: I'm afraid you didn't pass this interview ex-Google buddy. You can try applying again next year.

I was asked the exact same question in the final round for SDE-2 role at Amazon. No price for guessing I was rejected ;)

This is exponential algo, will this suffice for interviews? Optimal I suppose could be done using DP @rachit

Created my own solution to this video and I think my answer runs in O(n^2) time. Could be wrong though.

def numbersInPi(pi, numbers):
numbersTable = {}
origNumbersTable = {}
for i in range(len(numbers)):
origNumbersTable[numbers[i]] = True

for i in range(len(pi)):
for j in range(i + 1, len(pi) + 1):
if pi[i:j] in origNumbersTable:
if i == 0:
numbersTable[pi[i:j]] = 0
continue

if pi[:i] not in numbersTable:
continue

if pi[:j] in numbersTable:
numbersTable[pi[:j]] = min(numbersTable[pi[:j]], numbersTable[pi[:i]] + 1)
else:
numbersTable[pi[:j]] = numbersTable[pi[:i]] + 1
if pi in numbersTable:
return numbersTable[pi]
return -1

Hey anyone plzz tell and get me out ofit,
How he can check 314,once he get rid of 3 from string and get one space between 3 and 14.... once get away from one position how he can go back to the beginning of string to find the min spaces, Thank you !!!

The decimals of pi are not random

Why not sort the list of Clements favourite numbers and split the first string into an array?

how long will it take to give an interview in DS&Algo if em a beginner.!?
and maybe em so late, this code "rachit" seems expired😎

Bhai iski bandi se binary tree inversion sikhna hai

How this would solve real production issues ? 😂 I would never prefer to have this in my production server. - "and you had to show that Apple logo yeah it's obvious 😂

man now i am also becoming pro in python, i have successfully done hello world

Since the question is asking for minimum number of spaces which is a minimization problem, we could maximize the substrings resulted by introducing spaces to given input string. Sort fav numbers array in decreasing length, check if largest number is a substring of input string. if yes, increment spacesTaken by 1 and now check if 2nd largest number is present in the input string. if yes, introduce space, else continue; .. if entire input string got split into substrings (base case where i reaches n-1) by greedy method of picking largest substring at each iteration , then in this way we could guarantee that spacesTaken will guaranteed to be minimum out of all possible answers. We could use rabin-karp style substring matching for efficient checks. I hope @Rachit/Clement would notice this comment and reply if my algo would work.

Always yep

Clement should be interviewee sometimes too. It would be a lot of fun.🤗

I feel like when you call tech support this guy answers