As always after a day of mock interviews I feel destroyed. Mentally destroyed. The fact that yesterday I played poker until 4am might helped, lol.
My problems were:
- given an array what is the longest non-contiguous increasing subsequence of elements?
- determine if a linked list is a palindrome
The first was a terrible pain and coulnd't unstuck myself using my regular tacticts.
The second was a fun and thought provoking journey into a few tricks to respect the O(n) time and O(1) space complexity. I
particularly liked how the O(1) forces you to have two pointers.
Basically this is the way I solved it, after a hint 3/4 into the interview where I couldn't move past O(n^2):
- do one first pass of the linked list, getting the size of it
- create two pointers P1 P2
- P1 will remain at the start
- P2 will move till the middle of the string (considering the chance of an odd linked list)
- P2 will now continue its path towards the end, but now it will invert all the
nextpointers, pointing them backwards, to the previous node, instead of forwards, as they are usually - when P2 reaches the end then P1 and P2 move towards the center, comparing items
Really really fun. I almost got it myself when I tried one of the tricks to unstuck myself, which is to simplify the problem, I thought "what about having a double linked list?" but then the mental leap to inverting the direction of the links between nodes was still a bit too far away.
But all considered I am very happy with how things are going.