Fourkites - Online test

Date of visit: 25.7.2018
Criteria: CGPA 7 above (there was no restriction reg. current arrears)
Platform: Hackerearth 
Duration: 2.30 hrs

Objective 10 questions: ( with varying weightage of 6 to 4 points)

The questions were based on data structures and algorithms.

Que 1: Given an expression like this "*+pq-rs", you have to write the postfix version of the expression.

Ans: pq+rs-* (explanation)
-------------------------
Que 2: For a given set of integers, where N is no. of elements in the set, choose a data structure with O(logN) to find the minimum element in the set and to insert a new element in the set which is not already present.

Options : (min-heap, binary search tree, binary tree..)

Ans: AVL-Tree (Solution)
-------------------------
Que 3: For a given postorder traversal of a tree (10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29), find the inorder traversal for the given.

Ans: <try to solve it, and if done just update the answer.>
-------------------------
Que 4: For a given preorder "abdecfg" and inorder "dbeafcg", find the postorder traversal of this.

Options : ("debfgca", "edbgfca", "edbfgca", "defgbca")

Ans: debfgca (Solution)
-------------------------
Que 5: Find the complexity of the given function.
            function(int n){
                  if(n == 1) return;
                  for(i=1;i<=n;i++){
                        for(j=1;i<=n;j++){
                                printf("*");
                        }
                  }
                  function(n-1); 
            }

Options : (O(n^2), O(n^3), O(nlogn), O(n^2logn))

Ans: <try to solve it, and if done just update the answer.>
-------------------------
Que 6: Find the tightest upper bound  that represents time complexity of  inserting an object in a binary search tree of n nodes.

Options : (O(1), O(logn), O(n), O(nlogn))

Ans: O(n) (Solution)
-------------------------
Que 7: A priority queue is implemented as max-heap and initially it has 5 elements. The level order traversal is (10, 8, 5, 3, 2), two elements "1" and "7" are inserted in this order. Find the level order traversal of this heap after the insertion of new elements.

Options : (10, 8, 7, 3, 2, 1, 5), (10, 8, 7, 1, 2, 3, 5), (10, 8, 7, 2, 3, 1, 5), (10, 8, 7, 5, 3, 2, 1)

Ans: <try to solve it, and if done just update the answer.>
-------------------------


Programming 2 question (each 100 points)

Que 1: A tree with root R and relations are represented (N-1) edges.(Note the tree is N-ary ). Each node has a value associated with it Val_i. Construct the tree and perform two operations:

Sum i ( should return the sum of the ith node and its children).
Update i , k  ( should update the node with value i by i+k )

Input
1st line : N  R
2nd line: N spaced integers (Example: if N is 5, you have to get 5 integers separated by a space)
N-1 line: U  V (i.e., There exist an edge between U & V)
Next line: Q
Next Q line: Query type.

Constraints
1<= N <= 10^5
1<= R <= N
1<= K <= 10^6
1<= Q <= 10^5
-----------------------------------------------------------
Que 2: There are N friends who have M friendships between them. They have rules: Friendship betwee two is (U, V). If U, V are friends and V, W are friends then U, W are friends. Each person have some money represented by coin value C_i. Given a sum of money find whether a person can borrow that amount from his friends. Print "YES" if he can borrow or "NO" if he cannot.

X - is the person borrowing money.
Y - is the amount that the person wants to borrow.

Input
1st line: N
2nd line: N spaced integers (Example: if N is 5, you have to get 5 integers separated by a space)
3rd line: M (No. of friendships)
M line: (U, V)
Next line: Q
Next Q line: X, Y