I tried out this website Pramp which conducts live code-pair interviews.
I got stuck while implementing a recursive approach... in Python (because we can't pass value by reference in Python)!
So, I have to return the
k distance from the end.
Sounds easy, right? Keep recurring till you hit the end of the
LL and pass back incrementing the count by
1. When this count is
k, you are at the right spot.
But you can't return this value to the uppermost function call stack?
Maybe like this?
def kthfromLast(node,k, current_depth = 0): if node == None: return null ans = kthfromLast(node.next,k) current_depth +=1 if current_depth == k: return node return ans
But I knew, this wouldn't work. Since each function call would have its default
current_depth = 0.
Changing it at any one of the function call won't change the value of it in the upper function stack.
If only we could pass
current_depth as a pointer. (Not allowed in
But, can we use
ans as both? The count of the
current_depth and also the
ans (instance of
Yes we can!
def kth_form_last(node,k`): if node == None: return 0 temp = kth_form_last(node.next,k) if type(temp) is int: ans = 1 + kth_form_last(node.next,k) if ans == k : return node else: return temp
So the idea is, we use
ans as the depth of the end of the link list. Just as we hit the depth of
k from the end, we return the
Node, instead of returning current depth.
For the upper function stack, we see if the value returned from the lower function stack is
If its int, we haven't found the item as yet(so we keep calculating depth).
If its not an int, we have returned an object (which is the answer), so the upper function stack just keeps returning the return value it got from the lower function stack.
I hope that made sense.
And BDW, pramp is awesome!
If you want some free pramp credits, use this link : https://www.pramp.com/invt/5xLdx6pG0zu2b64vAwVN