So, today I had the 1st round of interview, it was about 45 mins, and I was given these two problems.
1. """
Given an array, for each element find the value of the nearest element to the
right which is having a frequency greater than as that of the current element.
If there does not exist an answer for a position, then make the value ‘-1’.
Input : a[] = [1, 1, 2, 3, 4, 2, 1]
1 = 3
2 = 2
3 = 1
4 = 1
Output : [-1, -1, 1, 2, 2, 1, -1]
"""
2. given a binary tree find the distance between two nodes of the tree.about 15/20 mins the interviewer was telling me what he does for the job, and then gave me the 1st problem, I wanted to solve in hashmap but somehow he wanted o(n) solution, I didnt have much time with it, as he quickly pointed out that about 10 mins are remaining, and wanted to jump to the 2nd problem, I solved the second using dfs technique but the interviewer seems like not understand how it works ! I asked him, how he could have solved the 1st one in o(n) he told me that there are solutions in google !
anywasys my answer to the. 2nd problem is below:
class Node():
def __init__(self, val):
self.val = val
self.left = None
self.right = None
points = [1, 4]
result = []
def dfs(node, left_distance, right_distance, tag):
if node == None:
return
if node.val in points:
if tag == -1:
result.append(left_distance)
else:
result.append(right_distance)
return
if len(result) == 2:
return
dfs(node.left, left_distance + 1, right_distance, -1)
if node.right:
dfs(node.right, left_distance, right_distance + 1, 1)
if len(result) == 2:
result.append(-1*left_distance)
node = Node(5)
node.left = Node(3)
node.right = Node(6)
node.left.left = Node(2)
node.left.right = Node(4)
node.left.left.left = Node(1)
node.right.right = Node(7)
node.right.right.right = Node(8)
dfs(node, 0, 0, 0)
print(sum(result)) If anyone can help me with the 1st problem in o(n) time, it would be great.
Comments (10)