Paragonlight
BAN USERAs the question said, "in this BST we can have leftnode<=rootnode<=rightnode.". It implies that one node in this BST may have nodes of same value in its right child node or left child node or both.
So, I use post-order traversal for this BST.
In each steps in recursion, we first count the most frequently value of nodes in left child nodes and right child nodes of current node. Also, count the node which has the same value of current node. After that, comparing the counts of most frequently values in both left and right child nodes with the counts of current node value.
After comparison, this node return an array to his parent node which contains three elements:
result=[counts of value in parent node, count of most frequently value in this sub BST, count of most frequently value in this sub BST]
class Element(object):
def __init__(self, value, lChild,rChild):
self.value = value
self.lChild = lChild
self.rChild = rChild
def findMostFrequentlyElement(node,parentValue):
value = node.value
count = 1
#assume 0 is not in array. If not, use other element instead.
subLResult = [0,0,0]
subRResult = [0,0,0]
if(node.lChild == None and node.rChild == None):
if(parentValue == node.value):
return [1,0,0]
else:
return [0,1,node.value]
if(node.lChild != None):
subLResult = findMostFrequentlyElement(node.lChild,node.value)
if(node.rChild != None):
subRResult = findMostFrequentlyElement(node.rChild,node.value)
result=[subLResult[0] + count + subRResult[0], subLResult[1],subLResult[2], subRResult[1], subRResult[2]]
parentValueCount = 0
if(parentValue == node.value):
parentValueCount = result[0]
if(result[1] >= result[3]):
return [parentValueCount, result[1],result[2]]
else:
return [parentValueCount, result[3],result[4]]
elif(parentValue == result[2]):
parentValueCount == result[1]
if(result[0] >= result[3]):
return [parentValueCount, result[0],node.value]
else:
return [parentValueCount, result[3], result[4]]
elif(parentValue == result[4]):
parentValueCount == result[3]
if(result[1] >= result[0]):
return [parentValueCount, result[1],result[2]]
else:
return [parentValueCount, result[0], node.value]
else:
if(result[0] >= result[1]):
if(result[0] >= result[3]):
return [0, result[0],node.value]
else:
return [0, result[3],result[4]]
else:
if(result[1] >= result[3]):
return [0, result[1],result[2]]
else:
return [0, result[3],result[4]]
An answer below this question uses two pointers which has the distance k. Move them simultaneously. When the first pointer catch the last one, the second pointer reach to kth element from the tail.
There is a trick, this method have to move 2 * length in the whole. So there is an more efficient method.
Just as the answer mentioned above, we have:
first pointer
second pointer
second pointer points to the head, while first pointer points to kth element in the linked list
You can simply move first pointer k(sometimes less than k times, because maybe list has not enough elements to traverse) times every single loop, remember the times to T, after every k times movement, check whether first pointer reach the end. If not, let second pointer point to the position which first pointer points when this loop begins, and go on. If so, move second pointer T times and this is the kth element from the tail in the linked list.
Now i just use k to be the number of moves for first pointer every single loop. When k is much smaller than the linked list length, this method seems not more efficient than traditional one. So how to makes this method most efficient? With my glance, I think we could choose the number of moves every single loop dynamically. The best number is related to k and length of linked list.
class Node(object):
def __init__(self, value, node):
self.value = value
self.node = node
root = Node(0,None)
previousNode = root
for i in range(1, 50):
node = Node(i, None)
previousNode.node = node
previousNode = node
node = root
for i in range(50):
print node.value
node = node.node
def kthElementFromTail(k):
p = root
kthFromTail = 0
q = p;
for i in range(k):
if(q.node != None):
q = q.node
else:
print "k is out of range of linkedList"
return
while q.node != None:
temp = q
position = 0
for i in range(0,k):
if(q.node != None):
position += 1
q = q.node
else:
break
if(position < k):
for i in range(position):
p = p.node
return p
else:
kthFromTail += position
p = temp
return None
k = kthElementFromTail(3)
print k.value
I have passed this question in Facebook Programming Puzzle.
Code is attached below:
- Paragonlight April 09, 2013