Question

Linkedin | SRE | Coding OA and Solutions | Intern | Set-4 | 2022

Answer 1

1. Task Queue
Task queues, which allow for asynchronous performance, are an important part of modern processing architectures. Information about a system consisting of several batch processing queues is given.

 

Each queue has three parameters:

 

1. the maximum number of tasks it can process in a single batch.
2. the time it takes to process a single batch of tasks in that queue
3. the number of tasks the queue must process

 

Given this information. calculate the minimum time needed to process a set of tasks by the system.

 

Example
n = 2
batchSize = [4,3]
processingTime = [6,5]
numTasks = [8,8]

 

Queue 0 can process a max of 4 tasks in 6 minutes, and queue 1 can process a max of 3 tasks in 5 minutes. Each queue has 8 tasks to process. The time required to perform the assigned tasks in the minimu possible time is calculated as follows:

 

For queue 0:

 

• At time = 0, a new batch of 4 tasks is initiated
• At time = 6, the first batch of tasks is processed and a new batch of 4 tasks is initiated.
• At time = 12, the second batch of tasks is processed. There are no more tasks left to process

 

For queue 1:

 

• At time=0, a new batch of 3 tasks is initiated.
• At time = 5, the first batch of tasks is processed and a new batch of 3 tasks is initiated
• At time = 10, the second batch of tasks is processed and a new batch of 2 tasks is initiated.
  The min time to process all tasks is 15

 

Constraints:

 

• 1 <= n <= 10^5
• 1 <= batchSize[i] <= 10^9
• 1 <= processingTime[i] <= 10^5
• 1 <= numTasks[i] <= 10^9
   

 

2. Picking Tickets
Consider an array of n ticket prices, tickets. A number, m, is defined as the size of some subsequences, s, of tickets where each element covers an unbroken raneg of integers. That is to say, if you were to sort the elements in s, the absolute difference between any elements j and j+1 would be either 0 or 1. Determine the maimum length of a subsequence chosen from the tickets array

 

Example
tickets = [8, 5, 4, 8, 4]

 

Valid subsequences, sorted, are {4,4,5} and {8,8}. These subsequences have m values of 3 and 2, respectively. Return 3.

 

Constraints

 

• 1 <= n <= 10^5
• 1 <= tickets[i] <= 10^9
   

 

3. Arranging Numbers
Jayme has a list of consecutive numbers beginning with 1. Her arrangement of those numbers is called a beautiful arrangement if at least one of the following is true:

 

• The number present at the ith position is divisible by i
• i is divisible by the number present at the ith position.

 

Determine how many beautiful arrangements of her integers is possible. For example, she has n =5 integers, [1,2,3,4,5]. Using 1-based indexing, there are the following arrangements satisfying the above:

 

[1,2,3,4,5]
[2,1,3,4,5]
[3,2,1,4,5]
[4,2,3,1,5]
[5,2,3,4,1]
[4,1,3,2,5]
[1,4,3,2,5]
[3,4,1,2,5]
[2,4,3,1,5]
[5,4,3,2,1]

 

In the first row, both conditions hold for all elements: each i equals the value at index i, so each i is divisible by the element and each element is divisible by its index i. In the next row, where the first two elements have been switched, where i = 1 and value is 2, 2 is divisible by i. In the next position, index i=2 is divisible by its element value of 1. Similar logic is applied to form each of the subsequent rows.

 

Constraints

 

• 1 < n < 20

Answer 2

for second, I was thing approach like following not sure if this would work for all test cases

 

pub fn picking_tickets(mut prices: Vec<i32>) -> usize {
    
    prices.sort();
    
    let mut max_size = 0;
    let mut seq = VecDeque::new();

    for i in 0..prices.len() - 1 {
        if (prices[i] - prices[i + 1]).abs() <= 1 {
            if seq.back().is_none() {
                seq.push_back(prices[i]);
                seq.push_back(prices[i + 1]);
            } else {
                seq.push_back(prices[i + 1])
            }
        } else {
            max_size = max(seq.len(), max_size);
            seq.truncate(0);
        }
    }
    return max_size;
}

Answer 3

3rd one

 

int n,i,j;
cin>>n;
int dp[(1<<n)];
memset(dp,0,sizeof(dp));
dp[0]=1;
for(i=1;i<(1<<n);++i)
{
  int cnt=0;
  for(j=0;j<n;++j)
  {
    if((i&(1<<j))!=0)
    {
      ++cnt;
    }
  }
  for(j=0;j<n;++j)
  {
    if((i&(1<<j))!=0)
    {   if((j+1)%cnt==0 || cnt%(j+1)==0)
        dp[i]+=dp[i^(1<<j)];
    }   
  }
}
cout<<dp[(1<<n)-1];

Answer 4

1st Solution: TC = O(n)

 

int minTime(std::vector<int> batchSize, 
         std::vector<int> processingTime, 
         std::vector<int> numTasks) 
{            
     int n = batchSize.size();
     int maxTime = INT_MIN;
     for(int i=0; i<n; i++)
     {
         int t = numTasks[i]%batchSize[i];
         int temp = numTasks[i]/batchSize[i] + (t == 0 ? 0 : 1);
         maxTime = std::max(maxTime, temp*processingTime[i]);
     }    
    return maxTime;
}