Expedia Coding Interview

Round 2(Coding and Data Structures Round)
Held on Bluejeans video call and code in http://collabedit.com/

Question : What is Binary Search Tree(BST)? (Answer: Specify the conditions)

Question:Why this example is not a BST ?(Answer: 3 cannot be in the right side of root node 5)
5

3 7

2 4 38

Question:What are some applications of BST? (Answer: Application related to searching as time complexity is O(logn), the inorder traversal gives a sorted order (so can store values to be in sorted order)

Question: Give Order Traversals of a tree

Pre: root,left,right
In: left,root,right
Post: left,right,root

def preorder(root):
if(root==None):
return
print(root.val)
self.preorder(root.left)
self.preorder(root.right)

def inorder(root):
if(root==None):
return
self.inorder(root.left)
print(root.val)
self.inorder(root.right)

def postorder(root):
if(root==None):
return
self.postorder(root.left)
self.postorder(root.right)
print(root.val)

Question : Give an array having numbers from 1 to n , where 2 numbers are missing. Find the two missing numbers.
Answer:
Sorted: Apply linear search or binary serach
Not sorted : Try applying average and sum formula

Snippet for the equations:

a:1 to n
ideal_sum=n*(n+1)/2
curr_sum=sum(a)
diff=ideal_sum-curr_sum
x+y=diff
1<=x,y<=n

ideal_sum-x-y/n=(n+1)/2-x/n-y/n

Question : Given a linked list with duplicate elements , sum up the duplicates and return the end result (do not use extra space like map to store frequency)

1->2->2->3->3->3->9->None
1->4->9->9->Null
1->4->18->NULL

Snippet of Code:

new_val=0
while(ptr.next!=None):

if(ptr.next.val==ptr.val):
new_val+=ptr->next.val

else:
if(new_val!=0):
intial_pos.val=new_val
intial_pos.next=ptr.next
new_val=ptr.next.val

new_val=0
ptr=ptr.next