Status: 10+ exp mostly C/C++ engineering fields, education - PhD (Engineering, not CS)
Position: Not sure, E4/E5 I think
Location: London
Date:Feb 8, 2022

1/ Phone screen - [reject but try again]

it looks like mine was very similar to another that interviewed on the same day.
This is my second phone screen, I applied last year and completely clammed up in the screen, I don't think I got an answer in at all. I remember writing code whilst saying I knew it wouldn't work, it was a nightmare!

First qn was Range Sum of BST. We talked about it before coding, I had a tablet set up so I could draw on the coderpad draw interface - this was new since last year and really good to have. And worth practising with if you're anything like me. I tried to draw out each leetcode problem while I was practising.

I said I'd do an in order DFS of the whole tree first, and add in early exit conditions on the range afterwards, as this sort of brute force then optimise approach was something I've seen recommended. Coded and found a stupid bug after prompting (an or instead of an and), think we agreed the full tree traversal was ok (I mean it was pretty simple to be fair). Then added my early exit conditions and adjusted the time complexity. My early exit conditions were wrong, and we spoke about the correction without actually coding it.

I then asked if we could move to the next qn as there wasn't long left.

Qn 2 was printing a BST as a grid, i.e. column by column with the values in depth order. Interviewer said we won't have time to code but we'll talk through it. I said my gut was to traverse it breadth first, but I would have gaps in the rows (or something, I can't recall!) so I'd do a recursive DF traversal, incrementing/decrementing a column counter as I moved left or right, storing values in a map which would keep the columns in order (the map containing a vector for each column).

We talked about this approach and the interviewer pointed out that my depth order would be incorrect. I realised I could use an iterative BF traversal and keep track of the left/right data as I would the depth level in the normal queue used for iterative BF traversal.
Again no code, so if this is a requirement I am toast. But we spoke about space and time complexity and after I remembered the map I was using, got the time complexity correct. And I was drawing the tree and map on the screen, it might have helped.

We then came back to the space complexity of the first Qn, I had to be prompted to add the depth of the recursive tree, and said it would depend on how balanced the tree was - if unbalanced it would be N, if balanced I stupidly said N/2, I said that was a guess, I think the time running out on Qn2 just got to me. He said then that it divides by 2 each level so "it's Log N" we both said at the same time.

I'm still waiting to hear back, it's been 3+ working days now. I am semi-hopeful. Feel free to correct me :-D

Update: interviewer suggested I get a re-do, second qn let me down

Phone Screen #2 [reject]:
So I took just under 2 weeks before my follow up phone screen. Exactly the same format.
Qn 1: Valid palindrome after removing one character.
I'd looked at this fairly recently and knew the outline solution, told the interviewer this. I coded after a short discussion on approach, We walked through an example and I had to correct my logic on testing the result of each branch of recursion, but I think interviewer was happy. We moved on to the next question with time to spare (an improvement on the last one for starters!)
Time and space complexity here are both just O(N)

Qn 2: Subarry sum = k. I had practised this one a few times and told the recruiter I had seen it before. I described the algorithm pretty perfectly I think and he didn't want me to code it, but to move on to something I hadn't seen before. I was gutted I didn't get to code it as I had literally practised it the night before. I hope this counts for something, or I am done with trying at this place!
Wasn't asked time or space complexity.

Qn3: 2 Parts:a) Encode a vector with repeating values to be memory efficient, b) Dot product 2 such vectors.
Hadn't seen this before (well I hadn't solved it before..). Vector structure is basic, I used a vector of structs to make life a bit simpler when it came to coding. However I needed prompting that I knew the index of a value implicitly, I was going down the path of storing start positions of each set of repeating values.
Then outlined an approach for dot producting the vectors, I basically just said I'd track two pointers, iterate over my vector of structs of the first vector, track the position in the second vector, and that I knew there would be some mess around updating the struct for the second pointer within the loop, probably best figured out while coding. This interviewer was definitely not pro drawing things out and was happy to go to code.
So coded up, did a lot more working out on the fly than I expected, e.g. realising I had nested my loops incorrectly as I was coding, but I think that was a fairly organic approach to take. Stepping through an example again I was using the draw pad to draw out the step-through, and the interviewer commented afterwards that was probably not the best move as it was slower than typing.
Anyway during that step-through realised I had the bounds on my loops off by one, otherwise seemed good.
Wasn't asked time or space complexity for these.

I feel hopeful, last qn I suppose could have been perfect but I felt like I got a coded solution down in time and had described the 2nd one as well as possible.

Status: Reject! well that surprises me quite a bit. The third question I suppose I could have got to the solution more directly? I know the answer I ended up at was correct, so what gives? "Not enough to move forward with" is the feedback.
Recruiter offered me another different screen, must be for direct management or maybe e6. I am done with this process.