This is the second part of the series on online assessments that I witnessed during the season of 2024. The first part can be found here.

• Zomato
• PACE Stock Broking
• HiLabs Technologies
• InMobi
• Dream 11
• Netradyne
• Microsoft
• Google
• Plutus Research

Zomato

Other Campuses Questions

1. You are given the edges that form a tree with the root as $0$. A traversal of the tree is generated in the following manner:

   • An empty queue $q$ is initialized and the node $0$ is pushed into it.
   • While the queue is not empty, the front element is popped and all its children are pushed into the queue in any arbitary order.
   • The popped element is added to the traversal.

   You are given multiple traversals of the tree, and you need to find which of the traversals provided can be a valid BFS order traversal of the same.

   Solution

   We can use the provided traversal to order the nodes of the tree in the particular order. We can then generate the BFS traversal of the tree and compare it with the provided traversal.

   Time Complexity: $O(Q * N \log N)$

   1
   bool checkTraversal(int n, vector<set<int>> &g, vector<int> &traversal) {
   2
       if (traversal.size() != n)
   3
           return false;
   4
   
   5
       vector<int> idx(n, -1);
   6
       for (int i = 0; i < n; i++)
   7
           idx[traversal[i]] = i;
   8
       for (int i = 0; i < n; i++)
   9
           if (idx[i] == -1)
   10
               return false;
   11
   
   12
       for (auto &ch: g) sort(ch.begin(), ch.end(), [&](int a, int b) { return idx[a] < idx[b]; });
   13
   
   14
       queue<int> q;
   15
       q.push(0);
   16
       vector<int> tr;
   17
       while (!q.empty()) {
   18
           int u = q.front();
   19
           q.pop();
   20
           tr.push_back(u);
   21
           for (auto &v: g[u])
   22
               q.push(v);
   23
       }
   24
   
   25
       return tr == traversal;
   26
   }
   27
   
   28
   vector<bool> show(vector<vector<int>> edges, vector<vector<int>> traversals) {
   29
       int n = edges.size() + 1;
   30
   
   31
       vector<vector<int>> g(n);
   32
       for (auto &e : edges) {
   33
           g[e[0]].push_back(e[1]);
   34
           g[e[1]].push_back(e[0]);
   35
       }
   36
   
   37
       vector<bool> ans;
   38
       for (auto &tr : traversals)
   39
           ans.push_back(checkTraversal(n, g, tr));
   40
   
   41
       return ans;
   42
   }

2. You are given an string $s$. You are also given two strings $t$ and $u$ which are both initially empty. You can perform either of the two operations in a turn:

   • Append the first character of $s$ to the end of $t$.
   • Append the last character of $t$ to the end of $u$.

   You need to apply these operations such that all the end all the characters from $s$ are shifted to $u$, and the generated string $u$ is the lexicographically smallest possible. Return the lexicographically smallest string $u$ that can be generated.

   Solution

   This question can be solved with the help of stack and using a greedy approach. In the stack, we try to maintain all the elements that we can processed till now (it acts like our string $t$). We greedily process the characters from $a$ to $z$, always travelling to their rightmost occurence and trying to add them to the string $u$. Before processing any character, we also check our stack to see it has some smaller character than the current one, and if it does, we pop it out and add it to the string $u$.

   Time Complexity: $O(N)$ where $N$ is the length of the string $s$.

   1
   string solve(string s)
   2
   {
   3
       int n = s.size();
   4
   
   5
       vector<int> lastOccur(26, -1);
   6
       for (int i = 0; i < n; i++)
   7
           lastOccur[s[i] - 'a'] = i;
   8
   
   9
       stack<char> st;
   10
       string ans = "";
   11
   
   12
       int lastIdx = -1;
   13
       for (char cur = 'a'; cur <= 'z'; cur++)
   14
       {
   15
           if (lastOccur[cur - 'a'] == -1 || lastOccur[cur - 'a'] <= lastIdx)
   16
               continue;
   17
   
   18
           while (!st.empty() && st.top() <= cur)
   19
           {
   20
               ans += st.top();
   21
               st.pop();
   22
           }
   23
   
   24
           while (lastIdx < lastOccur[cur - 'a'])
   25
           {
   26
               lastIdx++;
   27
               if (s[lastIdx] == cur)
   28
                   ans += cur;
   29
               else
   30
                   st.push(s[lastIdx]);
   31
           }
   32
       }
   33
   
   34
       while (!st.empty())
   35
       {
   36
           ans += st.top();
   37
           st.pop();
   38
       }
   39
   
   40
       return ans;
   41
   }

3. You are given a string $s$ that has lowercase English characters. You are also given an integer $n$. You need to generate a string $x$ of length $n$ such that:

   • All of characters present in $s$ must be present in the string.
   • We will then make a string of length $t$ by repeatedly adding the string $x$ to it untill the string $t$ can be re-arranged to have the string $s$ as a substring.
   • The generated string $t$ should be of the minimum possible length. If there are multiple possible $t$ with the same length, it should be so that the generated string $t$ is lexicographically smallest.

   Return the string $x$ that would generate the string $t$.

   Solution

   It is clear that we need to minimse the number of copies of the string $x$ that we need to add to the string $t$. We can binary search on this value of copies needed, and then generate the string $x$ greedily by adding the minimum number of characters needed to fullfill condition $2$, and pad the rest of the spaces with the character $a$.

   Time Complexity: $O(N + 26 \log N)$ where $N$ is the length of the string $s$.

   1
   bool canGenerate(int copies, int n, vector<int> &cnt)
   2
   {
   3
       int total = 0;
   4
       for (int i = 0; i < 26; i++)
   5
           total += (cnt[i] + copies - 1) / copies;
   6
       return total <= n;
   7
   }
   8
   
   9
   string generate(int n, string s)
   10
   {
   11
       vector<int> neededCnt(26, 0);
   12
       for (char ch : s)
   13
           neededCnt[ch - 'a']++;
   14
   
   15
       int l = 0, r = s.size();
   16
       int minCopies = -1;
   17
       while (l <= r)
   18
       {
   19
           int mid = (l + r) / 2;
   20
           if (canGenerate(mid, n, neededCnt))
   21
           {
   22
               minCopies = mid;
   23
               r = mid - 1;
   24
           }
   25
           else
   26
               l = mid + 1;
   27
       }
   28
   
   29
       if (minCopies == -1)
   30
           return "";
   31
   
   32
       int usedSpaces = 0;
   33
       vector<int> usedCnt(26, 0);
   34
       for (int i = 0; i < 26; i++)
   35
       {
   36
           usedCnt[i] = (neededCnt[i] + minCopies - 1) / minCopies;
   37
           usedSpaces += usedCnt[i];
   38
       }
   39
       usedCnt[0] += n - usedSpaces;
   40
   
   41
       string ans = "";
   42
       for (int i = 0; i < 26; i++)
   43
           ans += string(usedCnt[i], 'a' + i);
   44
   
   45
       return ans;
   46
   }

PACE Stock Broking

Other Campus Questions

1. There are $n$ employees in a company, out of which there are $k$ special employees who have data network and share their mobile hotspots with other employees. There are employee edges connections already made between the employees, where the / connection connects the employees $from[i]$ and $to[i]$, such that either of the employees, $from[i]$ and $to[i]$ can share a mobile hotspot.

   Two employees $x$ and $y$ are connected if there is a path between them. All the employees connected to a special employee $x$ will use the mobile hotspot of the special employee $x$.

   Up to now, to restrict data usage, any employee was connected to at most one special employee. As data consumption has increased, any employee can be connected to at most $m$ number of special employees. Find the maximum number of edges that can be added to the graph such that any employee is connected to at most $m$ special employees.

   Solution

   It can be proven that it is optimal to greedily make a component as large as possible. To do the same, we will perform the following steps:

   • Perform a BFS on the graph to find the connected components.
   • For each connected component that has no special employee, connect it to the largest connected component that has a special employee.
   • Sort all the connected components in decreasing order of their size.
   • If the components are $c_1, c_2, \ldots, c_k$, then connect the first $m$ components (i.e. $c_1, c_2, \ldots, c_m$), then the next $m$ components (i.e. $c_{m + 1}, c_{m + 2}, \ldots, c_{2m}$), and so on.

   Now each component with size $s$ contribute $\frac{s \cdot (s + 1)}{2} - x$ to the answer, where $x$ is the number of edges present originally in that component. The time complexity of the solution is $O(n + m)$.

2. A simple variation of Minimum Path Sum

3. A simple variation of the Job Scheduling Problem

4. Find the number of ways to colour a $3 \times n$ grid using $3$ colours such that no row and column has all the colours the same. Print the answer modulo $10^9 + 7$.

   Solution

   Refer to this blog post.

5. The floor of your house is created by $n$ tiles, which are either empty (.), dirty (D) or have food (F). Your task is to group the food into a single consecuive group while following the following rules:

   • You can move the food to the left or right by one tile at cost $x$.
   • Food can’t be moved to a tile that is dirty.
   • The cost to clean a dirty tile is $y$.

   Given $q$ queries, each all of the form $(x, y)$ and a string representing the floor, find the minimum cost to group all the food together for each query.

   Solution

   This is an application of the standard problem trying to group people together, along with the realization of the fact that all the dirty spots between the leftmost food point and the righmost food point must be cleaned. The complexity of the solution is $O(n + q)$.

   1
   int main()
   2
   {
   3
       int n;
   4
       string s;
   5
       cin >> n >> s;
   6
   
   7
       int firstFood = -1, lastFood = -1;
   8
       for (int i = 0; i < n; i++)
   9
           if (s[i] == 'F')
   10
           {
   11
               if (firstFood == -1)
   12
                   firstFood = i;
   13
               lastFood = i;
   14
           }
   15
   
   16
       int countDirty = 0, countFood = 0;
   17
       for (int i = firstFood; i <= lastFood; i++)
   18
           if (s[i] == 'D')
   19
           {
   20
               countDirty++;
   21
               s[i] = '.';
   22
           }
   23
           else if (s[i] == 'F')
   24
               countFood++;
   25
   
   26
       int minMoves = 0;
   27
       int seenLeft = 0;
   28
       for (int i = firstFood; i <= lastFood; i++)
   29
       {
   30
           if (s[i] == '.')
   31
               minMoves += min(seenLeft, countFood - seenLeft);
   32
           else
   33
               seenLeft++;
   34
       }
   35
   
   36
       int q;
   37
       cin >> q;
   38
       while (q--)
   39
       {
   40
           long long x, y;
   41
           cin >> x >> y;
   42
           cout << x * minMoves + y * countDirty << endl;
   43
       }
   44
   }

6. There are infinite seats in a bus. There are $n$ people in a queue waiting to board the bus, and each wants to board and sit as seat $arr[i]$. It is givent that the seat desired by each person is between $1$ and $n$. The allotment is done in the following manner:

   • If the seat desired by the person in the front of the queue is empty, they are allotted that seat and removed from the queue.
   • If the seat desired by the person in the front of the queue is occupied, the seat number desired by them is incremented by $1$ and they are pushed to the end of the queue.

   Find the final seat number allotted to each person in the queue. There are atmost $10^5$ people in the queue.

   Solution

   We will first store all the people who have not been alloted a seat in a stack to simulate their priority. We can also see that at max seats till index $2 \cdot n$ will be occupied. The rest can be seen from the implementation. The time complexity of the solution is $O(n)$.

   1
   int main() {
   2
       int n;
   3
       cin >> n;
   4
   
   5
       vector<int> arr(n);
   6
       for (int i = 0; i < n; i++)
   7
           cin >> arr[i];
   8
   
   9
       vector<vector<int>> people(2 * n + 1);
   10
       for (int i = 0; i < n; i++)
   11
           people[arr[i]].push_back(i);
   12
   
   13
       vector<int> ans(n);
   14
       stack<int> st;
   15
       for (int seat = 1; seat <= 2 * n; seat++) {
   16
           if (!people[seat].empty()) {
   17
               // Allot seat to first person, and push rest to stack for later allotment
   18
               // in reverse order
   19
               auto p = people[seat];
   20
               ans[p[0]] = seat;
   21
               for (int i = p.size() - 1; i >= 0; i--)
   22
                   st.push(p[i]);
   23
           } else {
   24
               if (!st.empty()) {
   25
                   ans[st.top()] = seat;
   26
                   st.pop();
   27
               }
   28
           }
   29
       }
   30
   
   31
       for (int i = 0; i < n; i++)
   32
           cout << ans[i] << " ";
   33
   }

7. You are running a restaurant and are expecting $n$ customers. The customers are represented by a vector of $N \times 3$ where the $i^{th}$ customer is represented by $(arrival_i, departure_i, numberDishes_i)$. The $i^{th}$ customer arrives at time $arrival_i$ and will stay till time $departure_i$. The $i^{th}$ customer will order $numberDishes_i$ dishes. What is the minimum number of chefs you need to hire so that all the customers can be served?

   • Assume that any chef can prepare any dish in $1$ unit of time.
   • A customer takes no time to eat the dishes after they are served, and they order all the dishes at once as soon as they come.
   Solution

   We will binary search on the number of chefs required. We can then simulate the process of serving the customers and check if the number of chefs required is less than or equal to the number of chefs we have. So simulate the process, we can use the greedy strategy of trying to serve the customer who is leaving the earliest first. Careful implementation is needed to ensure that you do not process the dishes of the customer before they arrive! I have used a priority queue to store the dishes to simulate the same. The time complexity of the solution is $O(n \log n \cdot \log A)$ where $A$ is the maximum number of chefs that can be needed.

   1
   using pq_type = priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>>;
   2
   
   3
   void processOrders(int curTime, int lastFreeTime, int chefCnt, pq_type &toProcess, vector<int> &served)
   4
   {
   5
       int canProcess = (curTime - lastFreeTime) * chefCnt;
   6
       while (!toProcess.empty() && canProcess)
   7
       {
   8
           auto p = toProcess.top();
   9
           toProcess.pop();
   10
           int leaveTime = p[0], quantity = p[1], idx = p[2];
   11
   
   12
           int process = min(canProcess, quantity);
   13
           canProcess -= process;
   14
           quantity -= process;
   15
   
   16
           if (quantity)
   17
               toProcess.push({leaveTime, quantity, idx});
   18
           else
   19
               served[idx] = 1;
   20
       }
   21
   }
   22
   
   23
   bool check(int chefCnt, vector<vector<int>> &customers)
   24
   {
   25
       int n = customers.size();
   26
       vector<int> served(n, 0);
   27
   
   28
       // pq -> stores [time, 0 / 1, idx]
   29
       // toProcess -> stores [leaveTime, quantity, idx]
   30
       pq_type pq, toProcess;
   31
       for (int i = 0; i < n; i++)
   32
       {
   33
           pq.push({customers[i][0], 0, i});
   34
           pq.push({customers[i][1], 1, i});
   35
       }
   36
   
   37
       int lastFreeTime = -1;
   38
       while (!pq.empty())
   39
       {
   40
           auto t = pq.top();
   41
           pq.pop();
   42
           int custIdx = t[2], type = t[1], curTime = t[0];
   43
   
   44
           if (type == 0)
   45
           {
   46
               toProcess.push({customers[custIdx][1], customers[custIdx][2], custIdx});
   47
               if (lastFreeTime == -1)
   48
                   lastFreeTime = curTime;
   49
               processOrders(curTime, lastFreeTime, chefCnt, toProcess, served);
   50
           }
   51
           else
   52
           {
   53
               processOrders(curTime, lastFreeTime, chefCnt, toProcess, served);
   54
               if (!served[custIdx])
   55
                   return 0;
   56
           }
   57
           lastFreeTime = curTime;
   58
       }
   59
   
   60
       return 1;
   61
   }
   62
   
   63
   int solve(vector<vector<int>> &customers)
   64
   {
   65
       int low = 1, high = 1e9, ans = -1;
   66
       while (low <= high)
   67
       {
   68
           int mid = (low + high) / 2;
   69
           if (check(mid, customers))
   70
           {
   71
               ans = mid;
   72
               high = mid - 1;
   73
           }
   74
           else
   75
               low = mid + 1;
   76
       }
   77
   
   78
       return ans;
   79
   }

8. You are given a string $s$ whose length can be more than $10^9$. You are given an array $arr$ and a string $p$ showing the count of the characters (for example, if $arr = [1, 2]$ and $p$ is ab, then the string $s$ is abb). Count the number of sequences modulo $10^9 + 7$ such that every subsequence contains all the vowels atleast once.

   Constraints:

   • $1 \leq n \leq 10^5$
   • $1 \leq arr[i] \leq 10^5$
   Solution

   We will make use of DP to solve this problem. We will maintain $idx$ as the current index in the compressed string that we are processing, and a $mask$ to represent the vowels that have occured atleast once in the current subsequence upto the index $idx$. The time complexity of the solution is $O(n \cdot 2^5 \cdot \log max(arr[i]))$. The extra factor of $\log max(arr[i])$ comes from the fact that we are using the binary exponentiation to calculate the powers of $2$, which can be removed with the help of precomputation.

   1
   long long mod = 1e9 + 7;
   2
   
   3
   long long binPower(long long a, long long b)
   4
   {
   5
       long long res = 1;
   6
       while (b)
   7
       {
   8
           if (b & 1)
   9
               res = (res * a) % mod;
   10
           a = (a * a) % mod;
   11
           b >>= 1;
   12
       }
   13
       return res;
   14
   }
   15
   
   16
   int getVowelIdx(char c)
   17
   {
   18
       if (c == 'a')
   19
           return 0;
   20
       if (c == 'e')
   21
           return 1;
   22
       if (c == 'i')
   23
           return 2;
   24
       if (c == 'o')
   25
           return 3;
   26
       if (c == 'u')
   27
           return 4;
   28
       return -1;
   29
   }
   30
   
   31
   long long solve(int idx, int mask, string &p, vector<int> &arr, vector<vector<long long>> &dp)
   32
   {
   33
       if (idx == p.size())
   34
           return mask == 31;
   35
   
   36
       if (dp[idx][mask] != -1)
   37
           return dp[idx][mask];
   38
   
   39
       long long ans = 0;
   40
       int vowelIdx = getVowelIdx(p[idx]);
   41
   
   42
       if (vowelIdx == -1 || (mask & (1 << vowelIdx)))
   43
       {
   44
           // Not a vowel or already present, thus can take any number of occurences
   45
           // from 0 to arr[idx]
   46
           ans += solve(idx + 1, mask, p, arr, dp) * binPower(2, arr[idx]);
   47
           ans %= mod;
   48
       }
   49
       else
   50
       {
   51
           // Do not take the vowel
   52
           ans += solve(idx + 1, mask, p, arr, dp);
   53
           ans %= mod;
   54
           // Take atleast one occurence of the vowel
   55
           ans += solve(idx + 1, mask | (1 << vowelIdx), p, arr, dp) * (binPower(2, arr[idx] - 1));
   56
           ans %= mod;
   57
       }
   58
   
   59
       return dp[idx][mask] = ans;
   60
   }
   61
   
   62
   int countSubsequences(string p, vector<int> arr)
   63
   {
   64
       vector<vector<long long>> dp(p.size(), vector<long long>(32, -1));
   65
       return solve(0, 0, p, arr, dp);
   66
   }

9. You are given three arrays $a$, $b$ and $c$ of length $n$ each. In one operation, you can choose any one element from any one of the arrays and move it to any other array. After you have performed all the operations, we would sort each of the arrays indidually, and then concatenate them. What is the minimum number of operations that you must perform so that the final resulting array formed is also sorted?

   Constraints:

   • $1 \leq n \leq 10^5$
   • $1 \leq a[i], b[i], c[i] \leq 10^9$
   Solution

   We can use an approach similar to merging sorted arrays in this question. Let us first sort all the three arrays, and now try to form the new array. If we are able to add the element from the first array, then that is analogous to no operation being required for the sorting to be performed. On the other hand, it the current minimum is either from the second or the third array, then atleast one operation would be needed to put the same to it’s correct position. This can be simulated easily with the help of pointers or we can use priority queues for easier implementation. The time complexity of the solution is $O(n \log n)$.

   1
   int main()
   2
   {
   3
       int n;
   4
       cin >> n;
   5
   
   6
       vector<int> a(n), b(n), c(n);
   7
   
   8
       priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
   9
       for (int i = 0; i < n; i++)
   10
       {
   11
           cin >> a[i];
   12
           pq.push({a[i], 0});
   13
       }
   14
       for (int i = 0; i < n; i++)
   15
       {
   16
           cin >> b[i];
   17
           pq.push({b[i], 1});
   18
       }
   19
       for (int i = 0; i < n; i++)
   20
       {
   21
           cin >> c[i];
   22
           pq.push({c[i], 2});
   23
       }
   24
   
   25
       int cntA = 0, cntB = 0, cntC = 0, ops = 0;
   26
       while (cntA + cntB + cntC != 3 * n)
   27
       {
   28
           auto [_, idx] = pq.top();
   29
           pq.pop();
   30
   
   31
           if (idx == 0)
   32
               cntA++;
   33
           else if (idx == 1)
   34
           {
   35
               cntB++;
   36
               if (cntA != n)
   37
                   ops++;
   38
           }
   39
           else
   40
           {
   41
               cntC++;
   42
               if (cntA != n || cntB != n)
   43
                   ops++;
   44
           }
   45
       }
   46
   
   47
       cout << ops << endl;
   48
   }

10. You are given an array $arr$ on length $n$. In one operation you can choose any two distinct indexes $i$ and $j$, remove both the elements from the array, and then add their sum back to the array at any position of your choice. What is the minimum number of operations required to make the array sorted in non-decreasing order?

    Constraints:

    • $1 \leq n \leq 10^5$
    • $1 \leq arr[i] \leq 10^9$
    Solution

    Let us fix the elements that we would not change in the array, that is the longest non-decreasing subsequence in the array. We can then see that the elements that are not part of the longest non-decreasing subsequence must be removed and added back to the array. When adding back, we can always pair two elements together, and add them in the appropiate position in the sorted array. The time complexity of the solution is $O(n \log n)$.

    1
    int main() {
    2
        int n;
    3
        cin >> n;
    4
    
    5
        vector<int> arr(n);
    6
        for (int i = 0; i < n; i++)
    7
            cin >> arr[i];
    8
    
    9
        vector<int> lis;
    10
        for (int i = 0; i < n; i++) {
    11
            int idx = lower_bound(lis.begin(), lis.end(), arr[i] + 1) - lis.begin();
    12
            if (idx == lis.size())
    13
                lis.push_back(arr[i]);
    14
            else
    15
                lis[idx] = arr[i];
    16
        }
    17
    
    18
        cout << (n - lis.size() + 1)/2 << "\n";
    19
    }

11. There are $n$ bacteria samples which are arranged in a row in a lab, from $1$ to $n$. There are $m$ number of pairs of bacteria, where $a[i]$ bacteria is poisonous to the bacteria $b[i]$. Determine the number of intervals of samples that can coexist.

    Constraints:

    • $1 \leq n \leq 10^5$
    • $1 \leq m \leq 10^5$
    • $1 \leq a[i], b[i] \leq n$
    Solution

    1
    int main() {
    2
        int n, m;
    3
        cin >> n >> m;
    4
    
    5
        vector<int> a(m), b(m);
    6
        for (int i = 0; i < m; i++)
    7
            cin >> a[i];
    8
        for (int i = 0; i < m; i++)
    9
            cin >> b[i];
    10
    
    11
        // Denotes the minimum index till which I can include
    12
        // in the subarray ending at me and still be safe
    13
        vector<int> d(n + 1, -1);
    14
    
    15
        for (int i = 0; i < m; i++) {
    16
            int u = a[i], v = b[i];
    17
            if (u > v)
    18
                swap(u, v);
    19
            d[v] = max(d[v], u);
    20
        }
    21
    
    22
        // All those in my range need to be safe too
    23
        for (int i = 1; i <= n; i++)
    24
            d[i] = max(d[i], d[i - 1]);
    25
    
    26
        long long ans = 0;
    27
        for (int i = 1; i <= n; i++) {
    28
            if (d[i] == -1)
    29
                ans += i;
    30
            else
    31
                ans += i - d[i];
    32
        }
    33
    
    34
        cout << ans << endl;
    35
    }

12. Number of Ways

13. For some array $arr$, the score of the array is defined as $len(arr) * max(arr)$. Given an array $arr$, find the sum of the scores of all the non-empty subarrays of the array. Return the same modulo $10^9 + 7$.

    Solution

    For each index $i$, let us calculate the number of subarrays that have the maximum element as that index, and add the contribution of all those arrays to the answer. This can be done with the help of some maths and stacks. Remember to handle the equality of the elements in exactly one the computations of either the previous greater or the next greater and calculate the contribution of the lengths accordingly. The time complexity of the solution is $O(n)$.

    1
    long long mod = 1e9 + 7;
    2
    
    3
    long long getCnt(long long x, long long y)
    4
    {
    5
        if (x > y)
    6
            swap(x, y);
    7
    
    8
        long long ans = x * (x + 1) / 2LL;
    9
        ans %= mod;
    10
        ans *= (x + y);
    11
        ans %= mod;
    12
    
    13
        long long ans2 = (y - x - 1) * x;
    14
        ans2 %= mod;
    15
        ans2 *= x;
    16
        ans2 %= mod;
    17
    
    18
        ans = (ans + ans2 + 2LL * mod) % mod;
    19
        return ans;
    20
    }
    21
    
    22
    int main()
    23
    {
    24
        int n;
    25
        cin >> n;
    26
    
    27
        vector<int> arr(n);
    28
        for (int i = 0; i < n; i++)
    29
            cin >> arr[i];
    30
    
    31
        stack<int> st;
    32
        vector<int> nxtGreater(n, n);
    33
        for (int i = 0; i < n; i++)
    34
        {
    35
            while (!st.empty() && arr[i] > arr[st.top()])
    36
            {
    37
                nxtGreater[st.top()] = i;
    38
                st.pop();
    39
            }
    40
            st.push(i);
    41
        }
    42
        while (!st.empty())
    43
            st.pop();
    44
    
    45
        vector<int> prevGreater(n, -1);
    46
        for (int i = n - 1; i >= 0; i--)
    47
        {
    48
            while (!st.empty() && arr[i] >= arr[st.top()])
    49
            {
    50
                prevGreater[st.top()] = i;
    51
                st.pop();
    52
            }
    53
            st.push(i);
    54
        }
    55
    
    56
        long long ans = 0;
    57
        for (int i = 0; i < n; i++)
    58
        {
    59
            arr[i] %= mod;
    60
            ans += getCnt(i - prevGreater[i], nxtGreater[i] - i) * arr[i];
    61
            ans %= mod;
    62
        }
    63
    
    64
        cout << ans << endl;
    65
    }

Online Assessment Questions

1. Make Fence Great Again

   Solution

   The key realization to solve the problem is that you will never need to increment one number (or fence) by more than $2$ times in the optimal solution. Using the same we can write a simple DP solution with the time complexity of $O(n \cdot 3 \cdot 3)$.

   1
   #include <bits/stdc++.h>
   2
   using namespace std;
   3
   
   4
   #define IOS                       \
   5
       ios_base::sync_with_stdio(0); \
   6
       cin.tie(0);                   \
   7
       cout.tie(0)
   8
   
   9
   #define ll long long int
   10
   #define vvll vector<vector<long long int>>
   11
   #define vpll vector<pair<long long int, long long int>>
   12
   #define range(x, s, n) for (int x = s; x < n; ++x)
   13
   
   14
   void solution();
   15
   
   16
   const int MOD = 1e9 + 7;
   17
   
   18
   int main()
   19
   {
   20
       IOS;
   21
       int TEST_CASES;
   22
       TEST_CASES = 1;
   23
       cin >> TEST_CASES;
   24
       while (TEST_CASES--)
   25
           solution();
   26
       return 0;
   27
   }
   28
   
   29
   ll solve(int idx, int lastIncr, vpll &arr, vvll &dp)
   30
   {
   31
       if (idx == arr.size())
   32
           return 0;
   33
   
   34
       if (dp[idx][lastIncr] != -1)
   35
           return dp[idx][lastIncr];
   36
   
   37
       ll cost = 1e18;
   38
       int lastEle = arr[idx - 1].first + lastIncr;
   39
       for (ll incr = 0; incr <= 2; incr++)
   40
       {
   41
           if (lastEle == arr[idx].first + incr)
   42
               continue;
   43
           cost = min(cost, incr * arr[idx].second + solve(idx + 1, incr, arr, dp));
   44
       }
   45
       return dp[idx][lastIncr] = cost;
   46
   }
   47
   
   48
   void solution()
   49
   {
   50
       int n;
   51
       cin >> n;
   52
   
   53
       vpll arr(n);
   54
       range(i, 0, n) cin >> arr[i].first >> arr[i].second;
   55
   
   56
       vvll dp(n, vll(3, -1));
   57
       ll ans = 1e18;
   58
       for (ll incr = 0; incr <= 2; incr++)
   59
           ans = min(ans, incr * arr[0].second + solve(1, incr, arr, dp));
   60
   
   61
       cout << ans << endl;
   62
   }

2. You are given a tree with $n$ nodes, and each node has a value $arr[i]$. You are given $q$ queries, and for each query you need to count the number of nodes with a prime value in the subtree of the query $q[i]$. The tree is rooted at $1$.

   Constraints:

   • $1 \leq n, q \leq 10^5$
   • $1 \leq arr[i] \leq 10^5$

3. You are given an even integer $n$. You need to count the number of ways to colour a $1 \times n$ grid using $3$ colours such that no two adjacent cells have the same colour and the cells equidistant from the beginning and the end also do not have the same colour. Print the answer modulo $10^9 + 7$.

   Constraints:

   • $1 \leq n \leq 10^5$
   • $n$ is even

4. You are even a grid of size $n \times m$. Each cell of the grid is either:

   1. $0$ -> Meaning that it is free to move
   2. $1$ -> Meaning that it is blocked
   3. $2$ -> Meaning that it is a has a gold coin

   You need to begin at the point $(0,0)$ and end at the point $(t_x, t_y)$ and need to collect all the gold coins on the way. You can only move within the grid, and can move in any of the $4$ directions. Find the minimum number of moves required to collect all the gold coins. You are allowed to visit multiple cells multiple times.

   Constraints:

   • $1 \leq n, m \leq 100$
   • Count of gold coins $\leq 10$
   • $0 \leq t_x < n$
   • $0 \leq t_y < m$

HiLabs Technologies

The company repeated the coding questions across campuses, even if the gap between the OA dates was more than $3$ days. MCQs questions were also partially repeated across campuses, both for the SDE and DS roles.

Other Campus Questions

1. You are given a graph with $n$ nodes and $m$ edges. The graph is undirected and unweighted. A bridge is an edge that, if removed, will increase the number of connected components in the graph. Find the number of pairs of nodes $(u, v)$ in the graph such that $u \leq v$ and any path between $u$ and $v$ contains exactly one bridge.

   Constraints:

   • $1 \leq n, m \leq 10^5$
   Solution

   You can use Tarjan’s algorithm to find the bridges in the graph. Then, you can condense all the nodes in the graph that have no bridge between them into a single node. This technique is known as the bridge tree. Then the given condition converts to chosing two nodes in the bridge tree such that the path between them contains exactly one edge. The time complexity of the solution is $O(n + m)$.

   1
   int main()
   2
   {
   3
       int n, m;
   4
       cin >> n >> m;
   5
   
   6
       vector<vector<int>> g(n);
   7
       for (int i = 0; i < m; i++)
   8
       {
   9
           int u, v;
   10
           cin >> u >> v;
   11
           u--, v--;
   12
           g[u].push_back(v);
   13
           g[v].push_back(u);
   14
       }
   15
   
   16
       vector<int> vis(n, 0), tin(n), low(n);
   17
       int timer = 0;
   18
       set<pair<int, int>> bridges;
   19
   
   20
       function<void(int, int)> dfs = [&](int u, int p) -> void
   21
       {
   22
           vis[u] = 1;
   23
           tin[u] = low[u] = timer++;
   24
   
   25
           for (int v : g[u])
   26
           {
   27
               if (v == p)
   28
                   continue;
   29
               if (!vis[v])
   30
               {
   31
                   dfs(v, u);
   32
                   low[u] = min(low[u], low[v]);
   33
                   if (low[v] > tin[u])
   34
                   {
   35
                       bridges.insert({u, v});
   36
                       bridges.insert({v, u});
   37
                   }
   38
               }
   39
               else
   40
                   low[u] = min(low[u], low[v]);
   41
           }
   42
       };
   43
       dfs(0, -1);
   44
   
   45
       vector<int> compId(n, -1);
   46
       function<void(int, int, int)> bridgeDfs = [&](int u, int p, int comp) -> void
   47
       {
   48
           compId[u] = comp;
   49
           for (int v : g[u])
   50
           {
   51
               if (v == p || compId[v] != -1)
   52
                   continue;
   53
   
   54
               if (bridges.find({u, v}) == bridges.end())
   55
                   bridgeDfs(v, u, comp);
   56
           }
   57
       };
   58
   
   59
       int comp = 0;
   60
       for (int i = 0; i < n; i++)
   61
           if (compId[i] == -1)
   62
               bridgeDfs(i, -1, comp++);
   63
   
   64
       vector<int> compSize(comp + 1, 0);
   65
       for (int i = 0; i < n; i++)
   66
           compSize[compId[i]]++;
   67
   
   68
       long long ans = 0;
   69
       for (auto &[u, v] : bridges)
   70
       {
   71
           long long a = compId[u];
   72
           long long b = compId[v];
   73
           ans += compSize[a] * compSize[b];
   74
       }
   75
   
   76
       ans /= 2;
   77
       cout << ans << endl;
   78
   }

2. You are given an array $arr$ of length $n - 1$. What is the maximum GCD that you can obtain by selecting exactly $n - 1$ elements from the array?

   Constraints:

   • $1 \leq n \leq 10^5$
   • $1 \leq arr[i] \leq 10^9$
   Solution

   We will try to exclude every element from the array and calculate the GCD of the remaining elements. The maximum GCD that we can obtain is the maximum of all the GCDs that we calculate. This calculation can be done in $O(n)$ time by using prefix and suffix GCD arrays. The time complexity of the solution is $O(n \log A_{max})$.

   1
   int main()
   2
   {
   3
       int n;
   4
       cin >> n;
   5
   
   6
       vector<int> arr(n);
   7
       for (int i = 0; i < n - 1; i++)
   8
           cin >> arr[i];
   9
   
   10
       vector<int> prefix(n), suffix(n);
   11
       prefix[0] = arr[0];
   12
       for (int i = 1; i < n - 1; i++)
   13
           prefix[i] = __gcd(prefix[i - 1], arr[i]);
   14
   
   15
       suffix[n - 1] = arr[n - 1];
   16
       for (int i = n - 2; i >= 0; i--)
   17
           suffix[i] = __gcd(suffix[i + 1], arr[i]);
   18
   
   19
       int ans = 0;
   20
       for (int i = 0; i < n; i++)
   21
       {
   22
           int curGCD = i == 0 ? suffix[1] : (i == n - 1 ? prefix[n - 2] : __gcd(prefix[i - 1], suffix[i + 1]));
   23
           ans = max(ans, curGCD);
   24
       }
   25
   
   26
       cout << ans << endl;
   27
   }

3. A compnay has $n$ servers, labelled from $1$ to $n$, all of which initally have no workload. $m$ requests are sent to the company’s API, where the requests are distributed evenly between the servers. An even distribution ensures that the busiest server has the least possible load. Print which server would handle the request for each API request.

   • $1 \leq n \leq 10^5$
   • $1 \leq m \leq 10^5$
   • $1 \leq requests[i] \leq 10^9$
   Solution

   Use a priority queue to store the servers and their loads. The time complexity of the solution is $O(m \log n)$.

   1
   int main()
   2
   {
   3
       int n, m;
   4
       cin >> n >> m;
   5
   
   6
       priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
   7
       for (int i = 1; i <= n; i++)
   8
           pq.push({0, i});
   9
   
   10
       for (int i = 0; i < m; i++)
   11
       {
   12
           cin >> load;
   13
           auto [curLoad, server] = pq.top();
   14
           pq.pop();
   15
           cout << server << " ";
   16
           pq.push({curLoad + load, server});
   17
       }
   18
   }

4. You are given an array $arr$ of length $n$. You need to find the number of ways to divide the array into subarrays such that each subarray has exactly one $1$ present in it. The length of the array is up to $10^6$. The answer can be large, so print the answer modulo $10^9 + 7$.

   Solution

   We can simply store the indices of all the $1$s in the array and then perform a cut at each of the position between two consecutive $1$s. The time complexity of the solution is $O(n)$.

   1
   int solve(vector<int> arr) {
   2
       int n = arr.size();
   3
   
   4
       vector<int> oneIdx;
   5
       for (int i = 0; i < n; i++) {
   6
           if (arr[i] == 1) {
   7
               oneIdx.push_back(i);
   8
           }
   9
       }
   10
   
   11
       if (oneIdx.size() <= 1) return oneIdx.size();
   12
   
   13
       long long ways = 1, MOD = 1e9 + 7;
   14
       for (int i = 1; i < oneIdx.size(); i++) {
   15
           ways = (ways * (oneIdx[i] - oneIdx[i - 1])) % MOD;
   16
       }
   17
   
   18
       return ways;
   19
   }

5. A consisent sequence is a binary string where all the adjacent elements are different. You are given an integer $n$. Find the number of consistent subsequences of a consistent sequence of length $n$ starting with the character $0$. Return the number of subsequences modulo $10^9 + 7$.

   • $1 \leq n \leq 10^5$
   Solution

   The sequence given to us is nothing but $010101\ldots$ and we need to find the alternating sequence of $0$s and $1$s. We can use a simple DP to solve this problem. The time complexity of the solution is $O(n)$.

   long long MOD = 1e9 + 7;
   
   long long solve(int idx, int need, int n, vector<vector<long long>> &dp)
   {
       if (idx == n)
           return 1;
       if (dp[idx][need] != -1)
           return dp[idx][need];
   
       dp[idx][need] = solve(idx + 1, need, n, dp);
       if (idx % 2 == need)
       {
           dp[idx][need] += solve(idx + 1, !need, n, dp);
           dp[idx][need] %= MOD;
       }
   
       return dp[idx][need];
   }
   
   int consistentSubsequence(int n)
   {
       vector<vector<long long>> dp(n, vector<long long>(2, -1));
       // -1 to remove empty subsequence
       long long ans = solve(0, 0, n, dp) - 1;
       ans += solve(0, 1, n, dp) - 1;
       ans = (ans + 2 * MOD) % MOD;
   
       return ans;
   }

6. The beauty of an subarray between $(i, j)$ of array $arr$ is defined as $\sum_{k = i}^{k = j} (arr[k]) + c \cdot (j - i)$. Print the maximum value of the beauty across all the possible distinct indexes $(u, v)$ in the array.

   Solution

   We maintain the largest value of beauty in the subarray. Then at any index either we can start a new subarray or extend the current subarray by adding the element and one unit of $c$. The time complexity of the solution is $O(n)$.

   long long maximumQuirkness(vector<int> &arr, long long cost)
   {
       long long sufMax = arr.back();
       long long ans = -1e18;
   
       for (int i = arr.size() - 2; i >= 0; i--)
       {
           ans = max(ans, sufMax + arr[i] + cost);
           sufMax = max(arr[i] + cost + sufMax, (long long)arr[i]);
       }
   
       return ans;
   
   }

7. The beauty of an subarray between $(i, j)$ of array $arr$ is defined as $\sum_{k = i}^{k = j} (arr[k] + c \cdot (j - i)) + 2 \cdot i \cdot j$. Print the maximum value of the beauty across all the possible distinct indexes $(u, v)$ in the array. The array is $1$ indexed.

8. You have $n$ coins with values from $0$ to $n - 1$. Find the number of ways of choosing exactly $k$ coins such that the sum of the coins is divisible by $m$. Return the number of ways modulo $1e9 + 7$.

   Constraints:

   • $1 \leq n \leq 10^3$
   • $1 \leq k \leq min(n, 10^2)$
   • $1 \leq m \leq 10^3$
   Solution

   We can use a take or not-take approach to solve this problem. The state of the DP can be represented as $(i, j, k)$ where $i$ is the coin that we are considering right now, $j$ is the number of coins taken that we can take in the next moves, and $k$ is the sum of the coins that must be taken in the next moves modulo $m$. The time complexity of the solution is $O(n \cdot k \cdot m)$ as each state can be reached in $O(1)$ time.

   int main()
   {
       int n, k, m;
       cin >> n >> k >> m;
   
       using ll = long long;
       using vll = vector<ll>;
       vector<vector<vll>> dp(n + 1, vector<vll>(k + 1, vll(m + 1, 0)));
   
       dp[n][0][0] = 1;
       ll MOD = 1e9 + 7;
   
       for (int i = n - 1; i >= 0; i--)
           for (int j = 0; j <= k; j++)
               for (int l = 0; l <= m; l++)
               {
                   dp[i][j][l] = dp[i + 1][j][l];
                   if (j > 0)
                   {
                       int reqMod = l - i;
                       reqMod = ((reqMod % m) + m) % m;
                       dp[i][j][l] += dp[i + 1][j - 1][reqMod];
                   }
                   dp[i][j][l] %= MOD;
               }
   
       cout << dp[0][k][0] << endl;
   }

   This might give TLE in a $1$ time limit or MLE in strict constraints, so we can space optimise the same and make use of arrays instead of vectors to improve the performance.

   Space Optimised Solution

   1
   const int MAXK = 100, MAXM = 1000;
   2
   long long cur[MAXK + 1][MAXM + 1], nxt[MAXK + 1][MAXM + 1];
   3
   
   4
   int main()
   5
   {
   6
       int n, k, m;
   7
       cin >> n >> k >> m;
   8
   
   9
       memset(nxt, 0, sizeof(nxt));
   10
       nxt[0][0] = 1;
   11
   
   12
       long long MOD = 1e9 + 7;
   13
   
   14
       for (int i = n - 1; i >= 0; i--)
   15
       {
   16
           memset(cur, 0, sizeof(cur));
   17
   
   18
           for (int j = 0; j <= k; j++)
   19
               for (int l = 0; l <= m; l++)
   20
               {
   21
                   cur[j][l] = nxt[j][l];
   22
                   if (j > 0)
   23
                   {
   24
                       int reqMod = l - i;
   25
                       reqMod = ((reqMod % m) + m) % m;
   26
                       cur[j][l] += nxt[j - 1][reqMod];
   27
                   }
   28
                   cur[j][l] %= MOD;
   29
               }
   30
   
   31
           memcpy(nxt, cur, sizeof(cur));
   32
       }
   33
   
   34
       cout << nxt[k][0] << endl;
   35
   }

9. You are standing at position $k$. You can move to any position which is the product of any two elements of the array $arr$ from the current position. Find the maximum distance you can move in one jump.

   Constraints:

   • $1 \leq n \leq 10^5$
   • $-10^9 \leq arr[i] \leq 10^9$
   • $-10^9 \leq k \leq 10^9$
   Solution

   You will make the jump to either the most positive position possible or the most negative position possible. The time complexity of the solution is $O(n \log n)$ due to the sorting.

   1
   int main()
   2
   {
   3
       long long n, k;
   4
       cin >> n >> k;
   5
   
   6
       vector<long long> arr(n);
   7
       for (int i = 0; i < n; i++)
   8
           cin >> arr[i];
   9
   
   10
       sort(arr.begin(), arr.end());
   11
   
   12
       long long maxPos1 = arr[n - 1] * arr[n - 2];
   13
       long long maxPos2 = arr[0] * arr[1];
   14
       long long maxPos3 = arr[0] * arr[n - 1];
   15
   
   16
       long long d = max({abs(maxPos1 - k),
   17
                       abs(maxPos2 - k),
   18
                       abs(maxPos3 - k)});
   19
   
   20
       cout << d << endl;
   21
   }

10. You are given an array of distinct elements $arr[i]$. You elements $a$ and $b$ can be connected by an edge if $lcm(a, b) \leq 10^6$. Find the minimum number of connected components possible in from the given array.

    Constraints:

    • $1 \leq n \leq 10^5$
    • $1 \leq arr[i] \leq 10^9$
    Solution

    It is obvious that elements greater than $10^9$ when paired with any other element would have a $lcm$ greater than $10^6$. So we can ignore all the elements greater than $10^6$. Now let us fix the $gcd$ as $g$. We can push all the elements that are divisible by $g$ into an array. Now it is certain that all the elements in this array with have a $gcd$ of atleadt $g$. We can use a two pointer approach to connect all the elements in the array that have $a * b \leq 10^6 \cdot g$. We will use a DSU to connect all the elements in the array. The time complexity of the solution is $O(n + A \log A)$ where $A$ is $10^6$.

    1
    class DSU
    2
    {
    3
    public:
    4
        vector<int> parent, size;
    5
    
    6
        DSU(int n)
    7
        {
    8
            parent.resize(n);
    9
            size.resize(n, 1);
    10
            for (int i = 0; i < n; i++)
    11
                parent[i] = i;
    12
        }
    13
    
    14
        int find(int x)
    15
        {
    16
            if (parent[x] == x)
    17
                return x;
    18
            return parent[x] = find(parent[x]);
    19
        }
    20
    
    21
        void unite(int x, int y)
    22
        {
    23
            x = find(x);
    24
            y = find(y);
    25
            if (x != y)
    26
            {
    27
                if (size[x] < size[y])
    28
                    swap(x, y);
    29
                parent[y] = x;
    30
                size[x] += size[y];
    31
            }
    32
        }
    33
    };
    34
    
    35
    int solve(vector<int> &arr)
    36
    {
    37
        int n = arr.size();
    38
    
    39
        const int LIMIT = 1e6;
    40
        DSU dsu(LIMIT + 1);
    41
    
    42
        int compCnt = 0;
    43
        vector<int> pre(LIMIT + 1, 0);
    44
        for (int i = 0; i < n; i++)
    45
        {
    46
            if (arr[i] > LIMIT)
    47
                compCnt++;
    48
            else
    49
                pre[arr[i]] = 1;
    50
        }
    51
    
    52
        for (int gcd = 1; gcd <= LIMIT; gcd++)
    53
        {
    54
            vector<long long> ele;
    55
            for (int j = gcd; j <= LIMIT; j += gcd)
    56
                if (pre[j])
    57
                    ele.push_back(j);
    58
    
    59
            long long maxProduct = (long long)1e6 * gcd;
    60
            int n = ele.size();
    61
    
    62
            int j = 0;
    63
            for (int i = 0; i < n; i++)
    64
            {
    65
                if (j < i)
    66
                    j = i;
    67
                dsu.unite(ele[i], ele[j]);
    68
                while (j + 1 < n && ele[i] * ele[j + 1] <= maxProduct)
    69
                {
    70
                    dsu.unite(ele[i], ele[j + 1]);
    71
                    j++;
    72
                }
    73
            }
    74
        }
    75
    
    76
        set<int> par;
    77
        for (int x : arr)
    78
            if (x <= LIMIT)
    79
                par.insert(dsu.find(x));
    80
    
    81
        return par.size() + compCnt;
    82
    }

11. Candle Problem

12. You are given a tree with $n$ nodes with one node intially marked as black, and the rest marked as white. In one operation, you can colour any of the nodes black only if atleast one the neighbours of the node is black. Count the possible number of colourings of the tree. Return the answer modulo $10^9 + 7$.

    Solution

    We can use simple DFS to solve this problem. Let the $dfs$ function return the number of ways of colouring the subtree of $u$ (when the whole tree is rooted at $root$) and the node $u$ is coloured black. Then for every child node, we can either leave it white, resulting in $1$ way of colouring, or colour it black which can be calculated recursively by multiplying with the result of the $dfs$ function. All the ways for all the children are multiplied together to get the final result. The complexity of the solution is $O(n)$.

    1
    long long mod = 1e9 + 7;
    2
    
    3
    long long dfs(int u, int p, vector<vector<int>> &g)
    4
    {
    5
        long long ans = 1;
    6
        for (int v : g[u])
    7
        {
    8
            if (v == p)
    9
                continue;
    10
            ans *= (1 + dfs(v, u, g));
    11
            ans %= mod;
    12
        }
    13
        return ans;
    14
    }
    15
    
    16
    int main()
    17
    {
    18
        int n;
    19
        cin >> n;
    20
    
    21
        vector<vector<int>> g(n);
    22
        for (int i = 0; i < n - 1; i++)
    23
        {
    24
            int u, v;
    25
            cin >> u >> v;
    26
            u--, v--;
    27
            g[u].push_back(v);
    28
            g[v].push_back(u);
    29
        }
    30
    
    31
        int root;
    32
        cin >> root;
    33
        root--;
    34
    
    35
        cout << dfs(root, -1, g) << endl;
    36
    
    37
    }

13. When comparing two numbers, you need to first compare the sum of digits of the two numbers, and only if they are the same, then you need to compare the actual values of the numbers themselves. Given an array $arr$, for each index, find the index of the closest number to the right that is bigger than the number at the given index according to the comparision scheme specified above. If no such number exists, print $-1$.

    Constraints:

    • $1 \leq n \leq 10^5$
    • $1 \leq arr[i] \leq 10^9$

14. You are given array $A$ of size $N$. You can make atmost $K$ operations on the same, where in each operation you can increase or decrease an element in array by $1$. Now, the beauty of array is frequency of most frequent element in the array. Output the maximum beauty that can be achieved in $K$ operations.

    Constraints:

    • $1 \leq n \leq 10^5$
    • $1 \leq k \leq 10^{18}$
    • $-10^9 \leq arr[i] \leq 10^9$
    Solution

    Let us first sort the array and try to binary search on the answer. It is clear that when we are checking the validity for an answer $x$, we would want some subarray of the sorted array to become all equal to $x$. Thus we can maintain a sliding window, and calculate the required number of operations for each window. It is a well known fact that given a sorted array, the median of the array is the point from where the number of operations required to make the array all equal by increments and decrements is minimum. We can use prefix sums to calculate the number of operations required to make the array all equal to $x$ in $O(1)$ time for any subarray. Thus the overall complexity of the solution is $O(n \log n)$.

    1
    int main()
    2
    {
    3
        int n;
    4
        long long k;
    5
        cin >> n >> k;
    6
    
    7
        vector<int> arr(n);
    8
        for (int i = 0; i < n; i++)
    9
            cin >> arr[i];
    10
        sort(arr.begin(), arr.end());
    11
    
    12
        vector<long long> pre(n);
    13
        pre[0] = arr[0];
    14
        for (int i = 1; i < n; i++)
    15
            pre[i] = pre[i - 1] + arr[i];
    16
    
    17
        auto getRangeSum = [&](int l, int r) -> long long
    18
        {
    19
            if (l > r)
    20
                return 0;
    21
            return pre[r] - (l == 0 ? 0 : pre[l - 1]);
    22
        };
    23
    
    24
        auto getMinOpsAtIdx = [&](int l, int r, int m) -> long long
    25
        {
    26
            long long sum1 = getRangeSum(l, m - 1);
    27
            sum1 = (long long)(m - l) * arr[m] - sum1;
    28
    
    29
            long long sum2 = getRangeSum(m, r);
    30
            sum2 = sum2 - (long long)(r - m + 1) * arr[m];
    31
    
    32
            return sum1 + sum2;
    33
        };
    34
    
    35
        auto getMinOps = [&](int l, int r) -> long long
    36
        {
    37
            int len = r - l + 1;
    38
            if (len % 2 == 1)
    39
                return getMinOpsAtIdx(l, r, l + len / 2);
    40
            else
    41
            {
    42
                long long m1 = l + len / 2 - 1, m2 = l + len / 2;
    43
                return min(getMinOpsAtIdx(l, r, m1), getMinOpsAtIdx(l, r, m2));
    44
            }
    45
        };
    46
    
    47
        auto checkLength = [&](int l) -> bool
    48
        {
    49
            for (int i = 0; i <= n - l; i++)
    50
                if (getMinOps(i, i + l - 1) <= k)
    51
                    return true;
    52
            return false;
    53
        };
    54
    
    55
        int ans = 0;
    56
        int l = 1, r = n;
    57
    
    58
        while (l <= r)
    59
        {
    60
            int m = (l + r) / 2;
    61
            if (checkLength(m))
    62
            {
    63
                ans = m;
    64
                l = m + 1;
    65
            }
    66
            else
    67
                r = m - 1;
    68
        }
    69
    
    70
        cout << ans << endl;
    71
    }

15. You are given a tree with $n$ nodes and each node has the value $0$ initially. The tree is rooted at $1$. You need to perform $q$ queries on the same of the following types:

    • 1 X Y: Increase the value of all the nodes in the subtree of node $X$ by $Y$.
    • 2 X Y: Increase the value of all nodes by $Y$ except the nodes in the subtree of node $X$.

    Print the final values of all the nodes in the tree.

    Constraints:

    • $1 \leq n, q \leq 10^5$
    • $1 \leq X \leq n$
    • $-10^9 \leq Y \leq 10^9$
    Solution

    1
    int main()
    2
    {
    3
        int n;
    4
        cin >> n;
    5
    
    6
        vector<vector<int>> g(n);
    7
        for (int i = 0; i < n - 1; i++)
    8
        {
    9
            int u, v;
    10
            cin >> u >> v;
    11
            u--, v--;
    12
            g[u].push_back(v);
    13
            g[v].push_back(u);
    14
        }
    15
    
    16
        int timer = 0;
    17
        vector<int> tin(n), tout(n);
    18
    
    19
        function<void(int, int)> dfs = [&](int u, int p) -> void
    20
        {
    21
            tin[u] = timer++;
    22
            for (int v : g[u])
    23
            {
    24
                if (v == p)
    25
                    continue;
    26
                dfs(v, u);
    27
            }
    28
            tout[u] = timer++;
    29
        };
    30
        dfs(0, -1);
    31
    
    32
        vector<long long> dif(2 * n + 1);
    33
    
    34
        int q;
    35
        cin >> q;
    36
        while (q--)
    37
        {
    38
            int ty, x, y;
    39
            cin >> ty >> x >> y;
    40
            x--;
    41
    
    42
            if (ty == 1)
    43
            {
    44
                dif[tin[x]] += y;
    45
                dif[tout[x] + 1] -= y;
    46
            }
    47
            else
    48
            {
    49
                dif[tin[0]] += y;
    50
                dif[tout[0] + 1] -= y;
    51
    
    52
                dif[tin[x]] -= y;
    53
                dif[tout[x] + 1] += y;
    54
            }
    55
        }
    56
    
    57
        for (int i = 1; i <= 2 * n; i++)
    58
            dif[i] += dif[i - 1];
    59
    
    60
        for (int i = 0; i < n; i++)
    61
            cout << dif[tin[i]] << " ";
    62
    }

16. This question was asked in the Software Developer role, and a workspace was provided to work on the same. You are required to design a simple HTML page that accepts from the user the number of rows and columns, and then makes a table of the specified dimensions. There is bonus marking for CSS styling.

    HTML Code

    <!doctype html>
    <html>
      <head>
        <title>Test</title>
        <style>
          body {
            font-family: Arial, Helvetica, sans-serif;
            padding: 5px;
          }
    
          input {
            margin-left: 5px;
            margin-right: 5px;
          }
    
          table {
            text-align: center;
          }
    
          tr:nth-child(even) {
            background-color: lightgrey;
          }
    
          tr:hover {
            background-color: lightcyan;
          }
    
          td {
            border: 1px solid black;
            margin: 0;
            padding: 1px;
          }
        </style>
      </head>
    
      <body>
        <center>
          <form name="input-form">
            <label for="rows" tabindex="1">Rows</label>
            <input
              type="number"
              name="rows"
              required
              min="1"
              max="10"
              id="rows"
            />
            <label for="cols" tabindex="2">Columns</label>
            <input
              type="number"
              name="cols"
              required
              min="1"
              max="10"
              id="cols"
            />
            <button type="submit" tabindex="3">Submit</button>
            <button type="reset" tabindex="4">Reset</button>
          </form>
    
          <h2>Generated Table</h2>
          <table id="main-table"></table>
        </center>
      </body>
    
      <script>
        const tableDiv = document.getElementById("main-table");
        const form = document.forms["input-form"];
    
        const resetValues = () => {
          form["rows"].value = "";
          form["cols"].value = "";
        };
    
        const handleSubmit = (event) => {
          event.preventDefault();
          const rows = +form["rows"].value,
            cols = +form["cols"].value;
          if (Number.isNaN(rows) || Number.isNaN(cols)) {
            alert("Please enter valid value of rows and columns");
            resetValues();
            return;
          }
    
          if (rows == 0 || cols == 0) {
            alert("Rows and columns can't be zero");
            resetValues();
            return;
          }
          plotTable(rows, cols);
        };
    
        const plotTable = (rows, cols) => {
          tableDiv.innerHTML = "";
          for (let r = 0; r < rows; r++) {
            const rowEle = document.createElement("tr");
            for (let c = 0; c < cols; c++) {
              const colEle = document.createElement("td");
              colEle.innerHTML = `Row ${r + 1} Col ${c + 1}`;
              rowEle.appendChild(colEle);
            }
            tableDiv.appendChild(rowEle);
          }
        };
    
        form.addEventListener("submit", handleSubmit);
      </script>
    </html>