Google 5/21 2nd interview

The interviewer first asked me about the difference between substring and subsequence.
Then comes the coding question.

You are given a dict of valid_word= {“” ….} and an input string S.
Find all subsequences of size 3 or more in S
And check if it’s valid or not.

I only gave the brute force solution, finding all subsequences and check whether the
size of subsequence is greater than or equal to 3. Then check whether this subsequence
Is in the valid dict or not. The interviewer said I can use itertools.combinations.
Later when I was asked the time complexity my brain was not clear so I was stuck for a long time.

from itertools import combinations
valid_dict={“aaa”, “abcd”,...}
input_word
ans=set()
for _len in range(3, len(input_word)):
    for sub in combinations(input, _len):
		cur_sub= “”.join(sub)
        if cur_sub in valid_dict:
			ans.add(cur_sub)    	
return ans	

I later find a similar problem on leetcode.
https://leetcode.com/problems/number-of-matching-subsequences/description/

Google 5/23 3rd interview (interval problem)

You are given the following input and output. Design a function that takes input and gives the following output.

Input
Name      Start   End
Abby      10      50
Ben       60      100
Carla     80      120
Donna     150     300
 
Output 
Start  end     Name 
10      50     Abby
60      80     Ben
80     100     Ben, Carla
100    120     Carla
150    300     Donna

You can decide input and output format yourself.

I format the input like the following…

[(“Abby”, 10, 50), (“Ben”, 60,100) …]

And I format the output using print.

print(“Start, End , Name”, start, end,name)

Follow up question:
What if the input have the same start and end time??
The interviewer asked me to generate an example input test case and implement the solution.
Example input:

Input
Name   Start    End
Abby    10      50
Apple   10      40
Ben     60      100
Carla   80      120
Donna  150      300

Google 5/26 4th interview

An array of length n
[4, 5, 3, 6, 7 ]
Find Index i, j that satisfy the following 3 conditions:

1. i <=j
2. array[i] ==array[j]
3. max( sum(array[i:j+1]) )
   return index i, j

Follow up :
What if the second condition was taken off?
—> a variation of max subarray
https://leetcode.com/problems/maximum-subarray/description/

An array of length n
[4, 5, 3, 6, 7 ]
Find index i, j that satisfy the following conditions:

1. i <=j
2. max( sum(array[i:j+1]) )
   return index i, j

6/3 Feedback from HR

I got feed back from HR, she said the result was mixed.

She said my second interview on 5/21 was considered not passing the bar on L3/L4 SDE roles. But I have passed my other 1st, 3rd, and 4th technical interview. (My 1st interview experience: https://leetcode.com/discuss/post/6679035/google-l3-interview-question-taipei-taiw-qd44/)

She will help me to pass my resume and interview results to other teams to see
whether I can proceed to the behavioral interview. If there are team leaders interested in me, I can proceed to the behavioral interview.

Personally, I don’t have much expectations about proceeding to the final round.
She also said if I want to re-apply SDE roles in Google, normally, I have to wait for at least 1 year. However, because of my solid performance, I can re-apply SDE roles in 6 months.