American Express Hiring Challenge

,
23

Yes, Did it. Nice observation.

24

Actually that was find the inversion in an array,
If you do brute force , then you will get 34/100,
thus you have to use Merge sort for this.
(:smile:

25

Graph problem can be solved using bfs.

First we maintain an array, whose i th index tells the nearest node (which will be our answer)
and also second array, which can maintain level of the node at i th index of first array (read further you will understand).
Now, question is how to fill that array. For that we can bfs with source 1 (as it is given graph is rooted at 1), for that we can use queue of pair<node, level>, where node is simple node number and level is level of that node (level of node 1 is 1). Now, every time we get some node, we can easily find the number of divisors (fc) of the value corresponds to that node, Now start fill the array from fc + 1 to 250 (this 250 is the size of array, which i have taken), with the following conditionā€¦
let first array is arr, and second array brr

  1. if arr[i] == 0 (that means we havenā€™t ye filled) then arr[i] = node, brr[i] = level;
  2. else if (arr[i] != 0 && brr[i] == level && arr[i] > node) arr[i] = node;

Now you doneā€¦
for each query x, just check if arr[x] == 0 then print -1; else print arr[x]

for finding the number of divisors efficiently, you can use this ->

int div[100006];

for (int i = 1; i < 1000006; i++) {
for (int j = i; j < 1000006; j += i) div[j]++;
}

1 Like
26

@py_js Thanks for your reply. Do you have idea about any sorted hash set function which gives the number of elements less than a particular value. I know the method using lower bound and distance function(C++ STL). Apparently distance function itself takes O(N) time. So, any other idea (Other than implementing the Balanced BST by myself).

27

or we can use fenwick tree

28

thank you for such a nice explanation.
I also did it using bfs ans got only 40 marks.

29

My second question was candy loveā€¦

30

Candy Love was a basic DP question.

int cost(vector<int> B) {
    dp[0][0] = 0;
    dp[0][1] = 0;
    for(int i = 1; i < B.size(); ++i) {
        dp[i][0] = max(dp[i-1][1] + B[i-1] - 1,dp[i-1][0]);
        dp[i][1] = max(dp[i-1][0] + B[i]-1, dp[i-1][1] + abs(B[i] - B[i-1]));
    }
    return max(dp[B.size()-1][0],dp[B.size()-1][1]);
}
2 Likes