Hello! I recently finished interviewing with google for a SWE - Early career position, am currently on team matching stage and wanted to share the questions i've got with you guys.
Online assessment
Given a positive integer x, return any list of values whose squared and summed together produce x
I used a greedy approach, starting from the closest integer lower or equal to sqrt of x, them added all numbers below it repeating when possible, until reaching x.
follow up = find the shortest list that produces x
didn't manage to implement, but suggested finding all combinations recursively, after interview interviewer pointed i could use dp to improve performance
On-site
1-Given a list of reservations for a day, comprised of pickup and return times(from 00:00 to 23:59) assign
a car to each reservation, using as little cars as possible, and return such list
wasted a bit of time thinking it was something similar to the intervals questions, but it's fairly different,
started by sorting the intervals based on pickup time(start)
used lists of objects:
Cars{int: carNumber,
list: reservations,
int: nextTimeAvailable}
at the end noticed i could have used a min heap to keep track of the lowest minTimeAvailable.
2-Given a html formatted string and a string "comparison", find if the text contents of the html formatted
string equal the string comparison
went characther by character, kept a boolean determining when to consider the current character as text or not, and controlled that bool when i encountered ">" or "<" characters.
follow up 1 = how can we instead count the number of html tags inside the input string?
asked the interviewer if we could consider anything between "<" and ">" a valid tag, but he said that we have a "structure" of my choice, with all the valid tags and need to make sure to only consider those, so i suggested checking values found between "<" and ">", and add to a counter it was in the tags set
follow up 2 = how can we perform this comparison if the "input" string doesn't fit into memory all at once?
didn't have much time to think about it, ended up not giving an answer
3-Given chat logs of users, return N most talkative users, most talkative being those who typed more words
went line by line, creating HashMap entries based on username, and attributing number of words typed per user, added all to a maxHeap based on the number of words, them polled() from it N times
- follow up = given max words typed per user = 5000, how can we improve the efficiency of the algorithm?
we can use an array of size 5001, were each position keeps a list of users that spoke that amount of words, them look at N elements, starting from the last position, and going trough the lists. Managed to implement about 85% of this approach, them time run out