## Samsung Interview Question for Software Developers

Country: United States

Comment hidden because of low score. Click to expand.
0
of 0 vote

wont work

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def findMinQueues(arr):
cpu=
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))``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

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++)
{
}

//init packets
ArrayList<Packet> packets =  new ArrayList<>();

//Test case 1

//Test case 2

//Test case 2-revised

//Test case 3

//Not enough queues

//Not enough queues 2

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+" }";
}
}``````

Comment hidden because of low score. Click to expand.
0

You code doesn't works for test case 2.

We can finish all three packets within 10 secs using 1 CPU only.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.