SDE - Intern

So basically the question was to rearrange the linked list nodes alternatively, firstly I tried using Recursion, but later I found out I was doing something wrong, then I told the interviewer that I needed to change my approach and I thought Stack could be used to solve this, in return, he gave me hint that you should go with the stack. I was declaring two pointers that do the same thing so he asked me whether we needed to use both or we could do it with only one, I said we could use any of them and we don't need to create both of them, even one pointer would be fine.

So the problem sounded like a typical DP problem where we need to find the maximum and where we have a choice to include the current number or not, sounded like a variation of 0/1 knapsack. I just needed to track whether earlier I had 2 consecutive elements before my current elements or not, if yes then I can't take that element. But interviewer told me to optimize this as it was less efficient. I couldn't come up with another approach then he told me the problem could be done greedily and explained to me the solution.

Very less time was remaining so the interviewer gave me this question and told me he wanted an optimized solution i.e. in O(n) time and O(1) space, so basically I told him that we could get the maximum 3 numbers or 1 maximum and 2 minimum, whichever comes greater will be my answer, then he asked me about the implementation, then I told him we can have 3 variables for maximum (highest, second highest, third highest) and 2 for minimum and for every new element we can just update maximum and minimum and the below minimum/maximum (like if I get a number greater than the maximum, I need to first give my third highest the value of second highest, second highest value of highest and update the highest with the current number).

Tip 1: Be confident and don't be anxious, try to maintain a good vibe environment with healthy discussion.
Tip 2: Again good Projects are very important.
Tip 3: The previous intern project should look like you had done something earlier.