I want to share with you all my weird experience of the
coding round by AppPerfect. I was
ready with my sleeves aced up, but who knows what was going to happen in the next
90 minutes of coding session. I was a bit nervous about question that I haven’t
seen yet, but my confidence definitely overlaid my fear at that time. Finally
after all the server set ups, I found my ball rolling down smoothly through the
question, I understood the question’s meaning along with test cases in single
go, and started coding within 15-25 minutes of getting the question.
The question at the first glance seemed to be a bit
easy and interesting, and so I just started my coding with the easiest and straight
forward approach that struck my mind. Well, let me first put the question
before you all.
AppPerfect Programming Test : Problem
1
One of the older OOPJ faculty members has a very old
computer at his house. It is so old that there is no notion of virtual memory
in the operating system. Instead it uses a simple memory allocation technique
called the 'Best Fit Algorithm'. The BFA works like this:
Whenever a request comes in for some memory space, the OS
looks for the smallest, continuous empty space, which can satisfy it, and
allocates a portion of this region to the program making the request. If such
space cannot be found, the program is terminated and all the memory used by the
program is freed. Any program can get terminated due to two reasons:
- The program exits
- Enough memory is not available to start the program or keep it
running
All memory requests that come in at the same time-instant
are processed in ascending order of process-id. If while processing, a program
is terminated for lack of memory, all memory held by it is freed before
processing any other request and no further memory requests by the terminated
program are considered. All termination is also done in order of process-id.
You have to write a program to simulate this algorithm
and print out the number of processes that were terminated due to lack of
memory.
Note:
1. No process will request
for memory before its start-time or after its end-time.
2. All memory sizes are
specified in KB.
3. The memory is linear
in nature, i.e., addresses do not wrap around. It starts at zero and goes up to
N-1 KB.
4. At a given time
unit, all processes that have reached end-time will be terminated (and memory
freed) before other memory requests are serviced.
5. The total free space
available in memory might be enough to satisfy a request, however the OS will
terminate the process if a continuous region of empty space is not found
Input specification:
- First line has an integer N (0 < N <= 1000), size of the
memory in KB.
- Second line of input will have integer P (0 <= P <= 20), the
total number of processes to be run on the system.
- Next P lines will have data for each process in the following
format:
<process-id> <start-time> <end-time> <initial-memory>
These input lines will be sorted in ascending order of the process-id.Process-id will be unique integers greater than zero. - Next line will have integer R (0<= R <= 20), which specifies
the subsequent memory requests by any process.
- Next R lines have the following format:
<process-id> <request-time> <memory-required>
Output specification:
An integer specifying the number of processes that were
terminated due to lack of memory
Sample Input and Output:
Input:
100
4
1 3 7 20
2 0 4 30
3 0 3 70
4 0 10 25
2
3 2 30
2 2 10
Output:
2
Input:
10
2
1 0 8 4
2 0 3 2
3
1 1 2
2 1 2
1 4 4
Output:
1
You may take some time to
fully understand the question and then embed all the constraints aptly to get
the test case working in your mind, and really the tough task starts here, now
you need to make your dumb laptop to do something that your mind can easily manipulate.
I started with the simplest
approach that everyone will catch, sorting the process list in accordance with
the starting time of each process. This was quite easy. Now I thought of
arranging the requests by process in the increasing order of their request time,
and for this also I used Bubble Sorting Algorithm which is no doubt a high
complexity sorting algorithm with worst case time complexity of O(n2).
But I did this without any pain as I knew that both, the number of processes and
the number of requests will not exceed 20, and so using Bubble Sort was fairly
a good choice.
During sorting I managed to get into the tricky part of
requests made by the processes. What if two processes requests memory at the same
instance of time. To which process should I give the preference? And the answer
to this question was specified in the question itself. I need to choose the
process with lower process_id first, and before completing this request I
should not move on resolving the other request. I again managed this using the
Indexed Bubble Sorting Algorithm, if the inputs were not in the sequence of ascending
process_id order.
All these were really the preliminary parts of my
problem solving strategy, the real journey begins now. Now I started looking
for requests and processes that arrive at the current time, and intuitively I started
a loop denoting the current time from the minimum arrival time for a process
till the maximum Departure time or ending time of a process. And according to
me was the tricky part for a novice to think.
In the above explained loop I just made an array
denoting the memory, and I stored 0 or 1 at each index of the array. 1 denoted that
this particular byte of the array is occupied by a currently running process
and 0 indicated that this byte is free and can be allocated to any process.
Again this was a crafty task to think for novice.
Now at each request I searched for the shortest
contiguous and sufficient memory block that I can use to allocate to a
particular process, and I was done. Now I just needed to make sure that whenever
a process terminates, it frees all the memory occupied by it, and this was
pretty simple.
I made my code in C and realized that I had a wrong
choice of language, because it became very lengthy. But it is working fine…Thank
God!!!
I was really happy that I managed this much big code,
in that intense pressure, and got something useful to learn. Before I write the
whole code here I would like you all to try this question by yourself and discover
your own bag of new tricks. I would also like to give information about some
techniques through which it can be implemented, firstly using the Comparable
interface of Java language would be of great help, secondly, designing bubble
sort with generic programming could have reduced the code size.
#include<stdio.h>
#include<stdlib.h>
struct process
{
int pid,st,et,im;
int isAlive;
};
struct request
{
int pid,rt,mr;
};
void bubbleSortForProcessArray(struct process*pArray,int numberOfProcesses)
{
int i,j;
struct process temp;
for(i=1;i<numberOfProcesses;i++)
{
for(j=0;j<numberOfProcesses-i;j++)
{
if(pArray[j].st>pArray[j+1].st)
{
temp=pArray[j];
pArray[j]=pArray[j+1];
pArray[j+1]=temp;
}
}
}
}
void bubbleSortIndexedForRequestArray(struct request*rArray,int a,int b) // sorting subArray from arr[a] to arr[b]
{
int i,j,n;
struct request temp;
n=b-a+1; // number of elements to be sorted
for(i=0;i<n-1;i++)
{
for(j=a;j<b-i;j++)
{
if(rArray[j].pid>rArray[j+1].pid)
{
temp=rArray[j];
rArray[j]=rArray[j+1];
rArray[j+1]=temp;
}
}
}
}
void bubbleSortForRequestArray(struct request*rArray,int numberOfRequests)
{
// sorting the request Array according to the request time of each request.
int i,j,ci;
struct request temp;
for(i=1;i<numberOfRequests;i++)
{
for(j=0;j<numberOfRequests-i;j++)
{
if(rArray[j].rt>rArray[j+1].rt)
{
temp=rArray[j];
rArray[j]=rArray[j+1];
rArray[j+1]=temp;
}
}
}
// now here we need to all the individual bunches of request array that have same request time
for(i=0;i<numberOfRequests;i++)
{
ci=i;
while(rArray[i].rt==rArray[i+1].rt && i+1<numberOfRequests)
i++;
if(i==numberOfRequests)
i--;
bubbleSortIndexedForRequestArray(rArray,ci,i);
i=ci;
}
}
void printProcessList(struct process*pArray,int numberOfProcesses)
{
int i;
printf("The process list is as follows : \n");
for(i=0;i<numberOfProcesses;i++)
printf("%d %d %d %d\n",pArray[i].pid,pArray[i].st,pArray[i].et,pArray[i].im);
}
void printRequestList(struct request*rArray,int numberOfProcesses)
{
int i;
printf("The request array is as follows : \n");
for(i=0;i<numberOfProcesses;i++)
printf("%d %d %d\n",rArray[i].pid,rArray[i].rt,rArray[i].mr);
}
int searchContiguousSmallest(int *memoryArray,int memory,int leastMemory) // searches contiguous smallest and sufficient.
{
int blockSize=2147483647,minBlockSize=2147483647,flag=0,minStartingIndex=-1,startingIndex,is1present=0,i,exitFlag=0;
for(i=0;i<memory;i++)
{
if(memoryArray[i])
{
is1present=1;
flag=0;
if(blockSize<minBlockSize && blockSize>=leastMemory)
{
minBlockSize=blockSize;
minStartingIndex=startingIndex;
}
exitFlag=0;
}
else
{
if(flag==0)
{
blockSize=0;
startingIndex=i;
flag=1;
}
blockSize++;
exitFlag=1;
}
}
if(exitFlag==1)
{
if(blockSize<minBlockSize && blockSize>=leastMemory)
{
minBlockSize=blockSize;
minStartingIndex=startingIndex;
}
}
if(is1present)
return minStartingIndex; // if not possible to allocate the memory return -1
else if(blockSize>=leastMemory)
return 0;
else return -1; // if not possible to allocate the memory return -1
}
void terminateProcess(int processId,int *memoryArray,int *occupyingProcess,int memory)
{
int i;
for(i=0;i<memory;i++)
{
if(occupyingProcess[i]==processId)
memoryArray[i]=0; // free
}
for(i=0;i<memory;i++)
{
if(occupyingProcess[i]==processId)
occupyingProcess[i]=-1;
}
}
int getProcessIndexByPID(int pid,struct process*pArray,int numberOfProcesses)
{
int i;
for(i=0;i<numberOfProcesses;i++)
{
if(pArray[i].pid==pid)
return i;
}
return -1; // if no such process with pid exists
}
int findAnswer(struct process*pArray,int numberOfProcesses,struct request*rArray,int numberOfRequests,int memory,int maxEndingTime,int minStartingTime)
{
int currentTime,index,blockSize,answer=0,requestIndex;
int i,j;
int *memoryArray,*occupyingProcess;
memoryArray=(int*)malloc(sizeof(int)*memory);
for(i=0;i<memory;i++)
memoryArray[i]=0; // means at the starting the memory is not occupied by any process
occupyingProcess=(int*)malloc(sizeof(int)*memory);
for(i=0;i<memory;i++)
occupyingProcess[i]=-1; // means at the starting the memory is not occupied by any process
for(currentTime=minStartingTime;currentTime<=maxEndingTime;currentTime++)
{
printf("\n\nCurrent Time = %d\n",currentTime);
for(i=0;i<numberOfProcesses;i++)
{
if(pArray[i].isAlive && pArray[i].et==currentTime) // process terminated due to ending time.
{
terminateProcess(pArray[i].pid,memoryArray,occupyingProcess,memory);
pArray[i].isAlive=0;
printf("terminating due to end of time ->> pid : %d\n",pArray[i].pid);
}
}
for(i=0;i<numberOfProcesses;i++)
{
if(pArray[i].st==currentTime)
{
pArray[i].isAlive=1;
index=searchContiguousSmallest(memoryArray,memory,pArray[i].im);
if(index==-1) // process terminates as no sufficient memory is available
{
// here the process needs to be terminated and increment answer
// for the termination of the process you need to free the resources allocated to it.
terminateProcess(pArray[i].pid,memoryArray,occupyingProcess,memory);
pArray[i].isAlive=0;
answer++;
printf("terminating by process due to lack of memory ->> pid : %d\n",pArray[i].pid);
continue;
}
printf("Request made by %d successful\n",pArray[i].pid);
for(j=index;j<index+pArray[i].im;j++)
{
memoryArray[j]=1;
occupyingProcess[j]=pArray[i].pid;
}
}
}
for(i=0;i<numberOfRequests;i++) // allcating the memory from the request Array
{
requestIndex=getProcessIndexByPID(rArray[i].pid,pArray,numberOfProcesses);
if(rArray[i].rt==currentTime && pArray[requestIndex].isAlive==1 && pArray[requestIndex].et>currentTime)
{
index=searchContiguousSmallest(memoryArray,memory,rArray[i].mr);
if(index==-1)
{
// here the process needs to be terminated and increment answer
// for the termination of the process you need to free the resources allocated to it.
terminateProcess(pArray[requestIndex].pid,memoryArray,occupyingProcess,memory);
pArray[requestIndex].isAlive=0;
printf("terminating by request due to lack of memory : %d\n",pArray[requestIndex].pid);
answer++;
continue;
}
printf("Request made by %d successful\n",pArray[requestIndex].pid);
for(j=index;j<index+rArray[i].mr;j++)
{
memoryArray[j]=1;
occupyingProcess[j]=pArray[j].pid;
}
}
}
}
return answer;
}
int main()
{
int n,i;
struct process*pArray;
struct request*rArray;
int numberOfProcesses,numberOfRequests,maxEndingTime,minStartingTime;
scanf("%d%d",&n,&numberOfProcesses);
pArray=(struct process*)malloc(sizeof(struct process)*numberOfProcesses);
maxEndingTime=0;
minStartingTime=2147483647;
for(i=0;i<numberOfProcesses;i++)
{
scanf("%d%d%d%d",&pArray[i].pid,&pArray[i].st,&pArray[i].et,&pArray[i].im);
pArray[i].isAlive=0;
if(maxEndingTime<pArray[i].et)
maxEndingTime=pArray[i].et;
if(minStartingTime>pArray[i].st)
minStartingTime=pArray[i].st;
}
scanf("%d",&numberOfRequests);
rArray=(struct request*)malloc(sizeof(struct process)*numberOfRequests);
for(i=0;i<numberOfRequests;i++)
scanf("%d%d%d",&rArray[i].pid,&rArray[i].rt,&rArray[i].mr);
bubbleSortForProcessArray(pArray,numberOfProcesses);
bubbleSortForRequestArray(rArray,numberOfRequests);
//printProcessList(pArray,numberOfProcesses);
//printRequestList(rArray,numberOfRequests);
printf("Answer = %d",findAnswer(pArray,numberOfProcesses,rArray,numberOfRequests,n,maxEndingTime,minStartingTime));
return 0;
}
No comments:
Post a Comment