Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
[RC Diary] Mock interviews (-60)

[RC Diary] Mock interviews (-60)

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 next pointers, 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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment