Question

Cisco | OA Coding Questions and Solutions | Set - 11 | 2022 | August

Answer 1

CISCO | OA| Fresher |SDE|August 2022
Coding Question
Q1. Mail Rooms for Office Buildings
Problem::
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::

 

1. A building can host only 1 mall room
2. 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.
3. A building may or may not be connected to other buildings. In such a case, it would
   need its own mail room.
4. The number of each building X is a random integer where 0<=X<= 10^4
5. Total number of buildings is P where 0<= P<=10^4
   6.Number of connections is N such that 0<=N<=1000

 

Q2. 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

 

1. If seat number is free, the customer at the head of the line gets the seat. Then, the
   customer exits the queue.
2. 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,
3. 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:

 

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

 

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

Answer 2

PROBLEM DESCRIPTION :

 

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 to be paid by this customer would be Rs.70.
   
  Constraints :

1. Total customers say N where 0 < N <= 10000.
2. Seats are assigned in increasing order.
3. 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 Explanation 1:
  There are 2 customers in the group. Customer1 gets seat #1 as the seat is unassigned. When customer2 is at the head of the queue, seat #1 is already assigned and hence, he rejoins the queue at the end with his choice being #2 (previous choice + 1). Seat #2 is available and gets assigned to customer2. Final answer is Rs.10 as Customer #2 was requeued once and hence a penalty of Rs.10.
   
  Sample Input 2:
  3
  1
  1
  1
   
  Sample Output 2 :
  40
   
  Sample Explanation 2:
  There are 3 customers in the group. Customer1 gets seat #1 as its unassigned. When customer2 is at the head of the queue, seat #1 is not available and hence he rejoins the queue at the end / re-queued. His preference is bumped up by 1 to #2. Similarly, Customer3 who also wants seat #1 which is already assigned and hence, he also rejoins the queue at the end with his choice now being #2 (previous choice + 1). Back to Customer2 whose choice of Seat#2 is available and he gets it. Customer3 however get re-queued again as seat#2 is already assigned. His choice is bumped to Seat#3. Finally, Customer3 gets Seat #3 as it is available. So total penalty of Rs.40 ( Rs.10 for 1 requeue for Customer2 and Rs.30 for 2 requeues for Customer3).

---

SOLUTION :

 

My Approach - Since Constraints were pretty low , I did a hashing plus Queue Based Implementation for this problem. My code passed 8/12 test cases. I had to change return type of the function from int to long long, otherwise it was only passing 5 test cases.

 

Here's my code in C++ :

 

long long TotalCustomerPenalties(vector<int> InitialAsk) {
    
   queue<array<long long,3>>q;
    int n = InitialAsk.size();
    vector<bool>vis(n+1,false);
    long long ans =0LL;
    
    for(int&i : InitialAsk){
        if(!vis[i])
            vis[i]= true;
            
        else {
            q.push({i+1,0,1LL});
        }
    }
    
	while(q.size()>0){
        
        auto curr = q.front();
        q.pop();
        
        if(vis[curr[0]]==false){
            vis[curr[0]]=true;
            ans+=(curr[2]*1LL);
            continue;
        }
        
        curr[0]++;
        curr[1]++;
        curr[2]+=(long long)pow(2,curr[1]);
        q.push(curr);
    }
    
    ans*=10LL;
    
    return ans;

}

Answer 3

if there are circles in the graph, NP hard. You have to try all combinations. https://en.wikipedia.org/wiki/Dominating_set

 

if there are no circles in the graph, greedy solution. start from leafs(i.e. nodes with less than 2 edges), if a leaf is not connected to a mail room, greedily add a mail room to its parent node (if no parent, add to itself) and remove the leaf. When a parent node's leafs are all removed, it becomes a new leaf, repeat the process untill we loop through all nodes

 

const int maxi=1e5+5;
vi adj[maxi];
int ans=0;
int go(int src, int par){
    unordered_set<int> st;
    int f=1;
    for(auto &x: adj[src]){
        if(x!=par){
            int hm=go(x,src);
            st.insert(hm);
            f=0;
        }
    }
    if(f==1){
        return 2;
    }
    int c=st.size();
    for(auto &x: st){
        if(x==2){
            ans++;
            return 1;
        } else if(x==0){
            c--;
        } else if(x==1){
            return 0;
        }
    }
    if(c==0){
        return 2;
    }
    return 0;
}
void solve(){
    int n;
    cin>>n;
    int m;
    cin>>m;
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    int ok=go(1,-1);
    if(ok==2){
        ans++;
    }
    cout<<ans<<endl;
}