You are given the ‘N’ processes with their “burst times”, and the “arrival time” for each process is 0.
Your task is to find the “waiting time” and the “turn-around time” of each process using the ‘FCFS CPU Scheduling’ algorithm.
Note:
The process that comes first will be executed first.
Assume all the process has arrived at same time and you have to consider the process with low process id to have arrived first.
The next process starts only after the previous gets fully executed.
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the T test cases follow.
The first line of each test case contains a single positive integer, ‘N’, denoting the number of Processes.
The second line of each test case contains ‘N’ space-separated non-negative integers denoting the ‘burst’ time of each process.
For each test case, print the two lines.
The first will contain the “waiting time” of each process separated by the space in the same order in which they are input.
The second will contain the “turn-around time” of each process separated by the space in the same order in which they are input.
Output for each test case will be printed in a separate line.
You do not need to print anything. It has already been taken care of. Just implement the given function.
1 <= T <= 10
1 <= N <= 10^6
1 <= BURST[i], ARRIVAL[i]<= 1000
Where ‘T’ denotes the number of test cases, ‘N’ denotes the number of processes, ‘BURST’ represents the ‘burst time’ of each process, and ‘ARRIVAL’ represents the ‘arrival time’ of each process.
Time Limit: 1sec
1
5
4 6 7 2 1
0 4 10 17 19
4 10 17 19 20
For first test case, as per FCFS algorithm process with get completed line wise. So, 1 process get start at 0 and gets completed at 4 and similarly it goes on till last process. Thus, the waiting time of all process are [ 0, 4, 10, 17, 19] and Finishing time are [ 4, 10, 17, 19, 20].
1
1
3
0
3
For first test case, We have only one process, so it starts at time 0 and ends at time 3.
Try to build an algorithm.
Approach:
Steps:
void findWaitingTime(burstTime, waitingTime):
void findTurnAroundTime(burstTime, waitingTime, turnAroundTime):
O(N), where ‘N’ is the number of processes.
We are considering each process only once and using its values to find the values of other processes. This takes constant time for each process and thus takes O(N) time.
O(N), where ‘N’ is the number of processes.
As we are creating two extra arrays to store the ‘waiting time’ and ‘turn-around time’ of each process, which is of size ‘N’. Hence, space complexity will be O(N).
All tags
Sort by
Interview problems
C++ | EASY | JUST DO IT
#include <bits/stdc++.h>
vector<vector<int>> findScheduling(int n, vector<int> &burstTime) {
vector<int>wait;
vector<int>turn;
wait.push_back(0);
int w = 0;
for(auto i=0;i<burstTime.size();i++)
{
w +=burstTime[i];
if(i!=burstTime.size()-1) wait.push_back(w);
turn.push_back(w);
}
vector<vector<int>>ans;
ans.push_back(wait);
ans.push_back(turn);
return ans;
}Interview problems
C++ Most Easy solution ✅✅ single loop.
vector<vector<int>> findScheduling(int n, vector<int> &burstTime) {
// Write your code here.
vector<vector<int>> ans;
int sum=0;
vector<int> temp1;
vector<int> temp2;
for(int i=0;i<n;i++)
{
temp1.push_back(sum);
sum+=burstTime[i];
temp2.push_back(sum);
}
ans.push_back(temp1);
ans.push_back(temp2);
return ans;
}Interview problems
Using Java ArrayList
import java.util.* ;
import java.io.*;
import java.util.ArrayList;
public class Solution {
public static ArrayList<ArrayList<Integer>> findScheduling(int n, ArrayList<Integer> burstTime) {
ArrayList<Integer> wt=new ArrayList<>();
ArrayList<Integer> tat=new ArrayList<>();
wt.add(0);
tat.add(burstTime.get(0));
for (int i=1;i<n;i++){
int s=burstTime.get(i-1)+wt.get(i-1);
wt.add(s);
int s2=burstTime.get(i)+tat.get(i-1);
tat.add(s2);
}
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
result.add(wt);
result.add(tat);
return result;
}
}Stack soln, C++
#include <bits/stdc++.h>
vector<vector<int>> findScheduling(int n, vector<int> &burstTime) {
vector<int> tat;
vector<int> wt;
vector<vector<int>> ans;
stack<int> stack;
stack.push(burstTime[0]);
for(int i=1; i<burstTime.size(); i++)
{
stack.push(stack.top()+burstTime[i]);
}
while(!stack.empty())
{
tat.push_back(stack.top());
stack.pop();
}
reverse(tat.begin(), tat.end());
for(int i=0; i<burstTime.size(); i++)
{
wt.push_back(tat[i]-burstTime[i]);
}
ans.push_back(wt);
ans.push_back(tat);
return ans;
}
Interview problems
c++
/* Time Complexity: O(N) Space Complexity: O(N)
Where N is the number of processes. */
// This function is used to find the waiting time of each process. void findWaitingTime(int n, vector < int > & burstTime, vector < int > & waitingTime) { // The Waiting time of the first process is 0. waitingTime[0] = 0;
// Fill the waiting time of the remaining processes. for (int i = 1; i < n; i++) { /* The waiting time of a process is equal to the sum of the waiting time and burst time of the previous process. */ waitingTime[i] = burstTime[i - 1] + waitingTime[i - 1]; }
}
// This function is used to find the turn around time of each process. void findTurnAroundTime(int n, vector < int > & burstTime, vector < int > & waitingTime, vector < int > & turnAroundTime) {
// Turn around time is the summation of the waiting time and the burst time. for (int i = 0; i < n; i++) { turnAroundTime[i] = burstTime[i] + waitingTime[i]; }
}
vector < vector < int >> findScheduling(int n, vector < int > & burstTime) { // Create two new vectors for the Waiting time and the Trun Around time of each process. vector < int > waitingTime(n), turnAroundTime(n);
// Find the waiting time. findWaitingTime(n, burstTime, waitingTime); // Find the turn around time. findTurnAroundTime(n, burstTime, waitingTime, turnAroundTime);
vector < vector < int >> result; result.push_back(waitingTime); result.push_back(turnAroundTime); return result; }
Interview problems
The last test case seems to be faulty, 10/11 test cases passed
from os import *
from sys import *
from collections import *
from math import *
def findScheduling(n, burstTime):
# Write your code here.
# Arrival time for each process is 0
AT = 0
# step1: preperation of gantt chart (GT)
gt = []
currSum = 0
for ele in burstTime:
currSum += ele
gt.append(currSum)
# each element of the GT represents the completion time (CT) of a process
# step2: calculate the turn around time = CT - AT
TAT = []
for ele in gt:
TAT.append(ele - AT)
# step3: calculate the waiting time = CT - BT
WT = []
for ele1, ele2 in zip(gt, burstTime):
WT.append(ele1 - ele2)
return [WT, TAT]Interview problems
simple c++ solution
vector<vector<int>> findScheduling(int n, vector<int> &burstTime) {
int sum=0;
vector<int>wt(n);
vector<int>tat(n);
for(int i=0;i<n;i++){
sum+=burstTime[i];
tat[i]=sum;
}
for(int i=0;i<n;i++){
wt[i]=tat[i]-burstTime[i];
}
vector<vector<int>> v={{wt},{tat}};
return v;
}Interview problems
C++
vector<vector<int>> findScheduling(int n, vector<int> &burstTime) { // Write your code here. vector<int>waitingTime; vector<int>turnAroundTime; vector<vector<int>>ans; int sum=0; waitingTime.push_back(sum); for(int i=0;i<burstTime.size()-1;i++){ sum+=burstTime[i]; waitingTime.push_back(sum); } ans.push_back(waitingTime); sum=0; for(int i=0;i<burstTime.size();i++){ sum+=burstTime[i]; turnAroundTime.push_back(sum); } ans.push_back(turnAroundTime); return ans; }
// please UpVote :)
Interview problems
Discussion thread on Interview Problem | FCFS CPU Scheduling
Hey everyone, creating this thread to discuss the interview problem - FCFS CPU Scheduling.
Practise this interview question on Coding Ninjas Studio (hyperlinked with the following link): FCFS CPU Scheduling
