Samsung Interview Question
Software DevelopersCountry: United States
def findMinQueues(arr):
cpu=[0]
for aTime,pTime in arr:
minCpu=min(cpu)
if max(0,minCpu-aTime)+pTime<10:
cpu.remove(minCpu)
cpu.append(max(minCpu,aTime)+pTime)
else:
if len(cpu)==5:
return -1
else:
cpu.append(aTime+pTime)
return len(cpu)
if __name__ == '__main__':
N= int(input())
arr=[]
for _ in range(N):
aTime,pTime=list(map(int,input().strip().split()))
arr.append((aTime,pTime))
print(findMinQueues(arr))
#include <stdio.h>
vector<int> q; //vector of available queues;
vector<vector<int>> q1; //contains packets in waiting for each queue(q1[0] is a vector whch contains info about the time for the packets to be processed in this queue to be procesed)
m //map of all the rod entry time;
t=0;
int main() {
while(t<100000)
{
for(int i=0;i<q.size();i++)
{
if(q[i]>0)
{
q[i]--;
}
else
{
if(q1.size()>0)
{
q[i]=*q1.begin();
q1.erase(q1.begin());
}
}
}
if(m.find(t)!=m.end())
{
if(q.size()==0)
{
q.push_back(m[t]);
}
else
{
bool flag=0;
int minind=-1;
int mini=INT_MAX;
for(int i=0;i<q.size();i++)
{
if(q[i]+m[t]+)>=10)
{
flag=1;
continue;
}
flag=0;
if(mini>q[i]+m[t]+sum(q1[i].begin(),q1[i].end())
{
mini=q[i]+m[t]+sum(q1[i].begin(),q1[i].end());
mini=i;
}
}
q1[minind].push_back(m[t]);
if(flag==1)
{ if(q.size()>=5)
{
cout<<"-1"<<endl;
break;
}
else
q.push_back(m[t]);
}
}
}
}
return 0;
}
Here's my shot.
The hardest part for me is modelling the problem. The coding itself is very easy and does not require any advanced data-structure.
One way to look at this: at each instant (or time unit) we have the queues which can contain one or more packages to consume. At each instant, the status of the queues changes. A brute force implementation can iterate over the time and upgrade the status of the queues, and return the output value based on the queues status.
Another line of thought: let's consider a _single_ queue. *Let's call T the processing time available by that queue*. At time=0, T=10 as no packet is being allocated yet. After time=3 secs, T=7 because 2 secs have been wasted waiting for packets and doing nothing. If a packet of length 3 arrives at time=4 secs, the queue would be busy until time=7 and T=3.
|----|===|---|
So T is really how much processing the queue can still take on, considering all the allocated packets.
While considering one queue, we can define
[P1..Pn] the packets to receive. Note each P has _receiveTime_ and _length_ properties.
T* = process(T, [P1..Pn])
as the function returning (T*) the available processing time _after_ processing [P1..Pn].
Now we have that
T* = process(T, [P1..Pn]) = process(T**, [P2..Pn])
T** = T - process(T,[P1])
The available time after processing [P1..Pn] from the initial time T, will be the same as the processing of all the packets but the first, from the initial time reduced by the time needed to process the first packet.
We can use this idea to do a recursive implementation of the process function.
But we have multiple queues! We can change the signature of the process function to have multiple times, but the same logic still applies.
[T1..T5]* = process([T1..T5], [P1..Pn])
[T1..T5]* = process([T1..T5], [P1..Pn]) = process([T1..T5]**, [P2..Pn])
[T1..T5]** = [T1..T5] - process([T1..T5],[P1])
One important difference between one and multiple queues is the way we calculate the time after the processing of P1. In a single queue the resulting time is simply
T - (P1.receiveTime + P1.length)
When we move to multiple queues, we apply the same subtraction but *only of one of the times, as we allocate to one specific queue*. So we need to choose which queue to allocate to!
As the problem requests the minimum number of the required queues, we are trying to *optimize the number of queues*.
When a new packet arrives should we send it to an empty queue or a non-empty queue? We should always prefer a non-empty queue, actually *that with the least processing time.* Ideally we'd stick every packet in one queue.
Below is the code. the process function is implemented by the method calculateRemainingProcessingTime()
Please note the function is recursive as the definition. But it's trivial to make it iterative, as all the parameters are mutable.
PS: test case 2 has output 2, not 1!
---------
import java.util.*;
public class QueuesOptimization{
public List<Integer> calculateRemainingProcessingTime( List<Integer> queueProcessingTimes, List<Packet> packets )
{
//case 0, no packets
if(packets.isEmpty())
{
return queueProcessingTimes;
}
Packet nextPacket = packets.remove(0);
int queue = determineQueueWithLeastProcessingTime(queueProcessingTimes, nextPacket.requiredProcessingTime);
//process this packet!
queueProcessingTimes.set(queue, queueProcessingTimes.get(queue) - nextPacket.requiredProcessingTime);
return calculateRemainingProcessingTime(queueProcessingTimes, packets);
}
/**
* @param queueProcessingTimes must not be null.
*/
private int determineQueueWithLeastProcessingTime(List<Integer> queueProcessingTimes, int requiredTime)
{
int res = -1;
if(queueProcessingTimes.size() > 1 )
{
for(int i=0; i < queueProcessingTimes.size(); i++)
{
if(queueProcessingTimes.get(i) < requiredTime )
{
continue;
}
if( res < 0 || (queueProcessingTimes.get(res) > queueProcessingTimes.get(i) ) )
{
res = i;
}
}
}
if(res == -1)
{
throw new RuntimeException("Not enough queues");
}
return res;
}
public static void main(String [] args)
{
final int QUEUES = 5;
final int MAX_PROC_TIME = 10;
//init available time
ArrayList<Integer> queueTimes = new ArrayList<>(QUEUES);
for(int i=0; i<QUEUES;i++)
{
queueTimes.add(MAX_PROC_TIME);
}
//init packets
ArrayList<Packet> packets = new ArrayList<>();
//Test case 1
//packets.add(new Packet(2,7));
//packets.add(new Packet(5,8));
//Test case 2
//packets.add(new Packet(1,3));
//packets.add(new Packet(2,3));
//packets.add(new Packet(3,5));
//Test case 2-revised
//packets.add(new Packet(1,3));
//packets.add(new Packet(2,3));
//packets.add(new Packet(3,4));
//Test case 3
packets.add(new Packet(1,5));
packets.add(new Packet(2,4));
packets.add(new Packet(3,8));
//Not enough queues
//packets.add(new Packet(1,11));
//Not enough queues 2
//packets.add(new Packet(1,5));
//packets.add(new Packet(2,4));
//packets.add(new Packet(3,8));
//packets.add(new Packet(1,5));
//packets.add(new Packet(2,4));
//packets.add(new Packet(3,8));
//packets.add(new Packet(2,4));
//packets.add(new Packet(3,8));
//packets.add(new Packet(2,4));
//packets.add(new Packet(3,8));
System.out.println("Packets: "+packets);
Collections.sort(packets);
QueuesOptimization qo = new QueuesOptimization();
qo.calculateRemainingProcessingTime(queueTimes, packets);
int usedQueues = (int) queueTimes.stream().filter( time -> time < MAX_PROC_TIME ).count();
System.out.println("Used queues: "+usedQueues);
System.out.println("Queues after execution: "+queueTimes);
}
}
class Packet implements Comparable<Packet>
{
public Packet(int arrivalTime, int requiredProcessingTime)
{
this.arrivalTime = arrivalTime;
this.requiredProcessingTime = requiredProcessingTime;
}
public int arrivalTime;
public int requiredProcessingTime;
//Sort by arrivalTime and decremental processing time
public int compareTo(Packet other)
{
int res = this.arrivalTime - other.arrivalTime;
if(res == 0)
{
res = other.requiredProcessingTime - this.requiredProcessingTime;
}
return res;
}
public String toString()
{
return "{ Time: "+ arrivalTime+", Len: " +requiredProcessingTime+" }";
}
}
wont work
- Anonymous June 07, 2018