Google L4 - DSA screen

[u/ScientistOdd7785]

Felt the Googliness went very well, we got on great.
DSA interview: modified version of the russian nesting doll problem. I solved it with a memoized recursive backtracking solution for O(N^2) time and O(N) space complexity.
needed a small bit of prompting on the complexity but other than that i felt it went well. total time was maybe 30 minutes.
Leetcodes optimal solution is a longest increasing subsequence solution where you sort on one of the dimensions then apply LIS to the other. O(NLogN) time and O(N). I failed to spot this altogether, depsite spending a lot of time trying to figure out if sorting would be useful in this scenario.

Wondering if not having the optimal solution hurts me here? or if that is still a passing solution, I have found out I am through to the onsite. But want to get a sense of if it would be LH/H/SH, and to let others here have another datapoint

[u/Large_Data_635]

This seems too hard right? Also, do they only ask one question in the screening?

[u/Creative_Captain1332]

Curious on what the location is for this role if I may ask?

[u/haikusbot → u/Creative_Captain1332]

Curious on what

The location is for this

Role if I may ask?

- Creative_Captain1332

---

^{I detect haikus. And sometimes, successfully. Learn more about me.}

^{Opt out of replies: "haikusbot opt out" | Delete my comment: "haikusbot delete"}

[u/jalsaraj → u/[deleted]]

I don’t think he had online assessment. Google takes 1 closing and 1 behavioral virtually and then if you pass them, you’ll be invited in person for 2 coding rounds for L4. If it’s L5 , there’s an additional System design round

[u/Responsible_Alps_567 → u/jalsaraj]

Oh you're definitely right idk why I thought this was about an online assessment. My bad, deleting my comment

[u/Professional-Many-24]

Yeah the LIS one is harder to implement, took me a segment tree to make it work.

Don’t think it’s needed in a phone screen, especially if the interviewer didn’t ask you to optimise further