Friday 5 December 2014

AppPerfect Coding Round : Best Fit Algorithm

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