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

# Question 1

Process Scheduler

# Question 4

## Portfolio Backtesting

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&lt;=i&lt;=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 &lt;data_type, vector&lt;data_type&gt;, greater&lt;data_type&gt;&gt; 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&lt;int&gt; start, vector&lt;int&gt; end)
{
vector&lt;pair&lt;int, int&gt;&gt; p;
for (int i = 0; i &lt; start.size(); i++)
{
p.push_back({start[i], end[i]});
}
sort(p.begin(), p.end());
int count = 0;
int ans = 0;
priority_queue&lt;pair&lt;int, int&gt;, vector&lt;pair&lt;int, int&gt;&gt;, greater&lt;pair&lt;int, int&gt;&gt;&gt; q;
for (int i = 0; i &lt; p.size(); i++)
{

q.push({p[i].second, p[i].first});
count++;
while (!q.empty() &amp;&amp; q.top().first &lt; p[i].first)
{
q.pop();
count--;
}
ans = max(ans, count);
}
return ans;
}
``````
1
Entering edit mode

## Question 4

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

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&lt;vector&lt;int&gt;&gt; &amp;adj, vector&lt;vector&lt;int&gt;&gt; &amp;dist, vector&lt;bool&gt; &amp;vis, int u, int dfsnumber)
{
vis[u] = true;
if (!vis[v])
{
dist[v].push_back(dist[u][dfsnumber] + 1);
}
}
int countPythogoreanTriplets(int treenodes, vector&lt;int&gt; tree_from, vector&lt;int&gt; tree_to, int x, int y, int z)
{
vector&lt;vector&lt;int&gt;&gt; dist(treenodes);
vector&lt;bool&gt; vis(treenodes, false);
for (int i = 0; i &lt; treenodes - 1; i++)
{
}

dist[x].push_back(0);
for (int i = 0; i &lt; treenodes; i++)
vis[i] = false;
dist[y].push_back(0);
for (int i = 0; i &lt; treenodes; i++)
vis[i] = false;
dist[z].push_back(0);

int ans = 0;
for (int i = 0; i &lt; treenodes; i++)
if (i != x &amp;&amp; i != y &amp;&amp; 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;
}
``````