9 weeks ago

John 910

Hyderabad

Avg CTC: 19lpa

Job Role: Software Engineer

Job Link: SE Bangalore link

Question 1

Mail Rooms for Office Buildings

Company ABC has corporate campus with multiple buildings. These buildings may or may not be Connected to one other.

Goal

Please help Alisa determine the least number of mail rooms to be setup so that all buildings are serviced with the following considerations.

Constraints

• A building can host only 1 mall room
• A building having a mail room will also service buildings directly connected to it. Hence those directly connected buildings may not host a mail room unless required otherwise.
• A building may or may not be connected to other buildings. In such a case, it would need its own mail room.
• The number of each building X is a random integer where 0 <= X <= 10^4
• Total number of buildings is P where 0 <= P <= 10^4
• Number of connections is N such that 0 <= N <= 1000

Inputs

First line contains integer P i.e. total number of buildings in Campus.

Second line contains integer N i.e. numbers of connections. Here each connection is represented as 'X Y' eg '10 20' ie link between Bldg 10 and Bldg 20

Next N lines contain the first building connected by the link i.e. 10. The other endpoint would be at index of current line + N. Next N lines contain the second building connected by the link i.e. 20

Output

Number indicating minimum number of mail rooms needed.

Example 1

Input

6
5
1
2
2
4
5
2
3
5
5
6

Output

2

Question 2

Travel Booking Penalties

Sherlock Airlines have come up with a novel way to handle group of travelers who do not plan ahead and end up trying to book similar seat numbers at the travel desk. In the process, they waste everyone's time since only one person can sit at a seat. Assume all seats are arranged in a straight line & members of the group line up in a queue with their preferred seat number. Agents of Sherlock Airlines allocate seats with this logic

• If seat number is free, the customer at the head of the line gets the seat. Then, the customer exits the queue.
• If seat is not free, the customer goes back to the end of the line and his preferred seat, Is bumped up by 1. Also the customer incurs a penalty for the delay caused
• Every time a customer goes back to the end of the line due to a conflict, the penalty doubles and accumulates. I.e if customer A has to go back his/her 1st time, he/she carries a penalty of Rs. 10. If the next time the customer gets to the front of the line and again has a conflict, the penalty doubles. So new penalty is Rs. 20 ( 2nd time) and total penalty is Rs.30. The next penalty would be Rs.40 and total penalty paid by this customer would be Rs. 70.

Constraints:

• Total customers say N where 0 < N <= 10000
• seats are assigned in increasing order,no need to fill prior gaps.
• No need to fill prior gaps.

Input :

First line contains the total number of passengers N.

Next N lines contain the first choice of the N passengers

Output :

Return the total number of times customers of the group have been re-queued.

Sample Input 1 :

2
1
1

Sample Output 1 :

10

Sample Input 2:

3
1
1
1

Sample Output 2 :

40

23 months ago

Ganesh Aggarwal 60

Question 1: Mail Rooms for Office Buildings

Assumption: All the buildings which are connected will always form a tree because incase it forms a graph and not a tree, then it will be a NP hard problem.

Approach: Dynamic Programming on trees will be used to solve the problem optimally.

First let us find out how to solve the problem for a single tree and then we will look at the case when we have forest structure (disjoint trees)

Root the tree at some node, let us assume at R.

Every node will have 3 states s0, s1 and s2.

s0: The entire subtree of the node is served except the node itself and hence it does not has a mailing room.

s1: The entire subtree of the node including the node itself is served but this node does not has a mailing room.

s2: The entire subtree of the node including the node itself is served and this node also has a mailing room.

Now, let

• dp[v][0] be the minimum number of mailing rooms required when node v is in state s0.
• dp[v][1] be the minimum number of mailing rooms required when node v is in state s1.
• dp[v][2] be the minimum number of mailing rooms required when node v is in state s2.

Initialize the entire dp array to INF.

Base case: When the tree has only one node, v

• dp[v][0]=0
• dp[v][1]=INF, because this case is not possible
• dp[v][2]=1

The transition is as follows:

Let v1,v2,v3,.....,vk be the children of node v

• dp[v][2]: sum of min(dp[vi][1],dp[vi][2]) for all i:{1,2,3...,k}.
• dp[v][0]: sum of dp[vi][1] for all i:{1,2,3,...,k}, if none of them is INF <br/>, else dp[v][0]=INF. <br/> Note: This is because for node to be unserved, none of the children can be in state s2. Also, since the subtree should be served, only possible case is when all children are in state s1.
• dp[v][1]: Let s denote the sum of min(dp[vi][1],dp[vi][2]) for all i:{1,2,3,..,k} <br/> Now find the value of "s-min(dp[vi][1],dp[vi][2])+dp[vi][2]" for every i:{1,2,3,...,k}. Let xi denote this value for every i. <br/> dp[v][1] = min(x1,x2,....,xk) <br/> Note: This is because we want to find a arrangement such that atleast one the children is in state s2 so that it can serve the current node (parent node).

So, the approach will be as follows:

Apply DFS, and while applying DFS, solve the problem bottom up. <br/>First, recursively call DFS for all the children to find the values for their different states. Then use these values to compute the values for the current node. The answer for a particular tree will be the min(dp[r][1],dp[r][2]) where r is the chosen root for this particular tree.

General Approach: In case of forest structure (disjoint trees)

Keep a visited array for all the nodes. Also keep a ans variable initialized as 0. <br/>Traverse from 1 to n over the visited array. Whenever an unvisited node is encountered, DFS is called with this node as the root. <br/> Let the encountered node be r. All the nodes which are part of the subtree of this node including itself are marked as visited. <br/> The min(dp[r][1],dp[r][2]) is added to the ans variable.

After all the nodes have been visited, ans variable has the final answer to the problem.

Time Complexity

• O(P+N), where P is the number of buildings and N is the number of connections between buildings

Pseudocode

int n,m;
vector<vector<int> > v;
vector<vector<int> > cnt;

void dfs(int st, int par, int vis[])
{

    vis[st]=1;
    int sum1 = 0;
    for(auto x:v[st])
    {
        if(vis[x]==1)
            continue;
        dfs(x,st, vis);
        sum1+=min(cnt[x][1],cnt[x][2]);
    }
    int sum0 =0, flag=0;
    for(auto x:v[st])
    {
        if(x==par)
            continue;
        if(cnt[x][1]==INF)
        {
            flag=1;
            sum0=INF;
            break;
        }
        sum0+=cnt[x][1];
    }
    int sum2 = 0;
    for(auto x:v[st])
    {
        if(x==par)
            continue;
        sum2+=min3(cnt[x][0],cnt[x][1],cnt[x][2]);
    }
    int flag1 = 0;
    int ans1 = INF;
    for(auto x:v[st])
    {
        if(x==par)
            continue;
        if(cnt[x][2]!=INF)
        {
            flag1=1;
            ans1 = min(ans1, sum1-min(cnt[x][1],cnt[x][2])+cnt[x][2]);
        }
    }
    cnt[st][0]=sum0;
    cnt[st][1]=ans1;
    cnt[st][2]=sum2+1;

}

int solve()
{
        int vis[n+1]={};
        int ans = 0;
        for(int i=1; i<=n; i++)
        {
            if(vis[i]==0)
            {
                dfs(i,-1,vis);

                ans+=min(cnt[i][1],cnt[i][2]);
            }
        }
        return ans;

}

5 months ago

Manas • 20

Mumbai

Travel Booking Penalties

int n;
cin >> n;
int a[n];
for(int i=0; i<n; i++)
    cin >> a[i];

sort(a, a + n);

int last_filled = 0;
long long ans = 0;

for(int i=0; i<n; i++){
    // Since the array was sorted, all the seats from a[i] to last_filled must be filled
    if(a[i] <= last_filled)
        ans += 10*(pow(2, last_filled - a[i] + 1) - 1);

    // Update last_filled seat
    last_filled = max(a[i], last_filled + 1);
}

cout << ans;

2.1 years ago

Shivam • 0

include<bits/stdc++.h>

using namespace std;

define pp pair< int , int >

define ll long long

ll gp(ll a , ll r , ll n) { return (a * (pow(r,n) - 1))/(r-1); }

define ll long long

int main() { ll n; cin>>n;

queue< pp > q;

for(int i=0;i<n;i++) { int v; cin>>v; q.push({v,0}); }

int val=1;

ll res=0;

while(!q.empty()) { auto x = q.front(); q.pop();

  if(x.first!=val)
  {
      q.push({x.first+1 , x.second+1});
  }
  else
  {
      res+=gp(10 , 2 , x.second );
      val++;
  }

}

cout<

2.1 years ago

Shivam • 0

`#include<bits/stdc++.h> using namespace std;

define pp pair< int , int >

define ll long long

ll gp(ll a , ll r , ll n) { return (a * (pow(r,n) - 1))/(r-1); }

define ll long long

int main() { ll n; cin>>n;

queue< pp > q;

for(int i=0;i<n;i++) { int v; cin>>v; q.push({v,0}); }

int val=1;

ll res=0;

while(!q.empty()) { auto x = q.front(); q.pop();

  if(x.first!=val)
  {
      q.push({x.first+1 , x.second+1});
  }
  else
  {
      res+=gp(10 , 2 , x.second );
      val++;
  }

}

cout<