Meta

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,

1/ Phone screen - [reject but try again]

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 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.

$12

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.