10 weeks ago

Rohit • 610

Hyderabad

Question 1

Process Scheduler

Question 2

Purchase Optimization

Question 3

Pythagorean Triples

Question 4

Portfolio Backtesting

21 days ago

Lokesh 310

Hyderabad

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;
}

9 weeks ago

John 910

Hyderabad

Question 4

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

Solution Link here: Portfolio Backtesting

21 days ago

Lokesh 310

Hyderabad

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;
}