Question: BNY Mellon, Recently Asked Questions in IIT-KGP on 6th November, 2022
0
Entering edit mode

Question 1

Process Scheduler

Click here to Practice

BNY1.1BNY1.2BNY1.3

Question 2

Purchase Optimization

BNY2.1BNY2.2BNY2.3BNY2.4

Question 3

Click here to Practice

Pythagorean Triples

BNY3.1BNY3.2BNY3.3BNY3.4BNY3.5BNY3.6

Question 4

Portfolio Backtesting

Click here to Practice

BNY4.1BNY4.2

ADD COMMENTlink 21 days ago Rohit • 190 • updated 15 days ago Lokesh 230
3
Entering edit mode

Question 1

Overview:

  • In a CPU, for a given core, only one process can run at a time.
  • Given N Process with start time and end time, find a minimum number of cores needed so that all processes have a core available for them to run in its [start, end] time interval.

Approach:

  • The minimum number of cores needed is equal to the maximum number of processes running at a given time.
  • min no of cores = max(no of process running at time i) , for all 1<=i<=1e9
  • Create pairs of {Start,end}
  • We know that the of process running can increase only when a new process is started, so sort the process according to the start time.
  • Have a priority_queue which has {end,start} , and has minimum end time in top.
    • priority_queue <data_type, vector<data_type>, greater<data_type>> variable_name;
  • Iterate through the sorted pairs {Start_i,end_i}.
    • Add 1 to the number of currently running processes.
    • Add the current pair to the priority_queue , in the form of {end_i,start_i}
    • Now check the top of the priority queue for whether the top elements' first value is less than the current pair's start_i.
      - If yes, pop and reduce the number of currently running processes by `1`.
      - If no break
      
    • ans = max(ans, number of currently running process)`

Complexity:

  • O(NLOGN), where is N is a number of processes.

Pseudocode:

int getMinCores(vector<int> start, vector<int> end)
{
    vector<pair<int, int>> p;
    for (int i = 0; i < start.size(); i++)
    {
        p.push_back({start[i], end[i]});
    }
    sort(p.begin(), p.end());
    int count = 0;
    int ans = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    for (int i = 0; i < p.size(); i++)
    {

        q.push({p[i].second, p[i].first});
        count++;
        while (!q.empty() && q.top().first < p[i].first)
        {
            q.pop();
            count--;
        }
        ans = max(ans, count);
    }
    return ans;
}
ADD COMMENTlink 19 days ago Lokesh 230
1
Entering edit mode

Question 4

Portfolio Backtesting is a repeated question. Previously asked for Standard Chartered. Checkout the solution below.

Solution Link here: Portfolio Backtesting

ADD COMMENTlink 21 days ago John 450
0
Entering edit mode

Question 3

Overview

  • Given a tree, and three nodes x,y,z, find the number of nodes i whose distances from x,y,z sorted in ascending order form a Pythagorean triplet
  • given( x!=y,x!=z, y!=z), we also take (i!=x!, i!=y, i!=z)

approach:

  • For all nodes distance from z,y,z using a DFS
  • Now go to each node i(i!=x!, i!=y, i!=z) and sort those distances from z,y,z and check whether they for a Pythagorean triplet

Complexity

  • O(N) N is the number of Nodes
    • Complexity of DFS is O(N+M), but for a tree M=N-1, so DFS complexity is O(N)

Pseudocode

void dfs(vector<vector<int>> &adj, vector<vector<int>> &dist, vector<bool> &vis, int u, int dfsnumber)
{
    vis[u] = true;
    for (auto v : adj[u])
        if (!vis[v])
        {
            dist[v].push_back(dist[u][dfsnumber] + 1);
            dfs(adj, dist, vis, v, dfsnumber);
        }
}
int countPythogoreanTriplets(int treenodes, vector<int> tree_from, vector<int> tree_to, int x, int y, int z)
{
    vector<vector<int>> adj(treenodes);
    vector<vector<int>> dist(treenodes);
    vector<bool> vis(treenodes, false);
    for (int i = 0; i < treenodes - 1; i++)
    {
        adj[tree_from[i]].push_back(tree_to[i]);
        adj[tree_to[i]].push_back(tree_from[i]);
    }

    dist[x].push_back(0);
    dfs(adj, dist, vis, x, 0);
    for (int i = 0; i < treenodes; i++)
        vis[i] = false;
    dist[y].push_back(0);
    dfs(adj, dist, vis, y, 1);
    for (int i = 0; i < treenodes; i++)
        vis[i] = false;
    dist[z].push_back(0);
    dfs(adj, dist, vis, z, 2);

    int ans = 0;
    for (int i = 0; i < treenodes; i++)
        if (i != x && i != y && i != z)
        {
            sort(dist[i].begin(), dist[i].end());
            if ((dist[i][0] * dist[i][0] + dist[i][1] * dist[i][1]) == dist[i][2] * dist[i][2])
                ans++;
        }
    return ans;
}
ADD COMMENTlink 16 days ago Lokesh 230

Login before adding your answer.

Similar Posts
Loading Similar Posts