Microsoft Interview Question for Software Engineer / Developers


Team: Azure
Country: United States
Interview Type: In-Person




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

Code of Queue itself and tester (we basically allow only one read and only one write, but read and write can be at the same time). I'd also ask if interviewer wants to implement producer/consumer model - means, read will wait until queue has needed count of bytes and write will wait until needed bytes will be freed. Code below doesn't implement producer/consumer though.

using System;
using System.Collections;
using System.Threading;

namespace ThreadSafeCirqularQueue
{
    class CirqularQueue
    {
        private byte[] queue = null;
        private uint size = 0;
        private int head;
        private int tail;
        private static object criticalSection = new object();
        private Semaphore writeLock;

        public CirqularQueue(uint queueSize)
        {
            size = queueSize;
            queue = new byte[size];
            head = tail = -1;
            writeLock = new Semaphore(1, 1);
        }

        public void Write(byte[] array)
        {
            bool validWrite = true;

            lock(criticalSection)
            {
                writeLock.WaitOne();
                if (head == -1 && tail == -1 && array.Length > size)
                {
                    Console.WriteLine("ERROR: Queue size is too small");
                    validWrite = false;
                }
                else
                {
                    if (head > tail && head - tail - 1 < array.Length ||
                        head < tail && size - (tail - head + 1) < array.Length)
                    {
                        Console.WriteLine("ERROR: Queue is full");
                        lock(criticalSection)
                        {
                            validWrite = false;
                        }
                    }
                }
                writeLock.Release();

                if (validWrite == true)
                {
                    writeLock.WaitOne();
                    for (int i = 0; i < array.Length; i++)
                    {
                        if (head == -1)
                        {
                            head = 0;
                        }

                        tail++;
                        if (tail == size)
                        {
                            tail = 0;
                        }
                        queue[tail] = array[i];
                    }
                    writeLock.Release();
                }
            }
        }

        public byte[] Read(uint N)
        {
            byte[] result = null;
            bool validRead = true;

            lock(criticalSection)
            {
                writeLock.WaitOne();
                if (head == -1 && tail == -1)
                {
                    Console.WriteLine("ERROR: Queue is empty");
                    validRead = false;
                }
                else
                {
                    if (tail > head && tail - head + 1 < N || tail < head && size - head + tail + 1 < N)
                    {
                        Console.WriteLine("ERROR: Byte count to read is bigger than number of bytes queue contains");
                        validRead = false;
                    }
                }
                writeLock.Release();

                if (validRead == true)
                {
                    writeLock.WaitOne();
                    result = new byte[N];
                    for (int i = 0; i < N; i++)
                    {
                        result[i] = queue[head];
                        head++;
                        if (head == size)
                        {
                            head = 0;
                        }
                    }

                    if (head == tail)
                    {
                        head = tail = -1;
                    }
                    writeLock.Release();
                }
            }

            return result;
        }
    }

    class ThreadSafeCirqularQueue
    {
        static CirqularQueue queue = new CirqularQueue(7);

        static void ReadThreadBig ()
        {
            byte[] array = null;

            while (true)
            {
                Thread.Sleep(750);
                array = queue.Read(4);
                if (array != null)
                {
                    Console.Write("Array:");
                    for (int i = 0; i < array.Length; i++)
                    {
                        Console.Write(" {0}", array[i].ToString());
                    }
                    Console.WriteLine();
                }
            }
        }

        static void ReadThreadSmall()
        {
            byte[] array = null;

            while (true)
            {
                Thread.Sleep(250);
                array = queue.Read(1);
                if (array != null)
                {
                    Console.Write("Array:");
                    for (int i = 0; i < array.Length; i++)
                    {
                        Console.Write(" {0}", array[i].ToString());
                    }
                    Console.WriteLine();
                }
            }
        }

        static void WriteThreadBig()
        {
            byte[] array = new byte[] { 8, 9, 10 };

            while (true)
            {
                Thread.Sleep(1000);
                queue.Write(array);
            }
        }

        static void WriteThreadSmall()
        {
            byte[] array = new byte[] { 11 };

            while (true)
            {
                Thread.Sleep(500);
                queue.Write(array);
            }
        }

        static void Main(string[] args)
        {
            byte[] array = { 1, 2, 3, 4, 5, 6, 7 };
            queue.Write(array);

            Thread readThreadSmall = new Thread(ReadThreadSmall);
            readThreadSmall.Start();

            Thread writeThreadBig = new Thread(WriteThreadBig);
            writeThreadBig.Start();

            Thread readThreadBig = new Thread(ReadThreadBig);
            readThreadBig.Start();

            Thread writeThreadSmall = new Thread(WriteThreadSmall);
            writeThreadSmall.Start();
        }
    }
}

- AK October 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

why would you need to lock read?shouldn't it be valid for multiple readers to access and read from the same node in the queue?

- anon October 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

tested implementation of it. it takes int instead of byte array. its for C++ 11

#include "stdafx.h"
#include<iostream>
#include<thread>
#include<mutex>
#define defaultSize 50   
using namespace std;

class CircullarArray{
private:
	int *myQueue;
	int top;
	int tail;
	int max;
	mutex myMutex;

public:	
	void init(int size){
		if (size < 0)             
			size = defaultSize;
		myQueue = new int[size];
		top = -1;
		tail = -1;
		max = size;
	}

	bool isFull(){
		return ((tail == 0 && top == max - 1) || (tail == top + 1)) ? 1 : 0;
	}
	

	bool isEmpty(){
		return (tail == -1) ? 1 : 0;
	}

	void push(int value){
		myMutex.lock();
		if (isFull())
			cout << "Queue is Full!" << endl;  
		else{
			top = (top + 1) % max;
			myQueue[top] = value;
		}
		if (tail == -1)
			tail = 0;
		myMutex.unlock();
	}

	void pop(){
		myMutex.lock();                          
		int data;
		if (isEmpty()){
			cout<<"Queus is empty"<<endl; 
			myMutex.unlock();                    
			return;
		}
		data = myQueue[tail];
		if (tail == top){
			top = -1;
			tail = -1;
		}
		else
			tail = (tail + 1) % max;
		cout << data << endl;
		myMutex.unlock();                       
	}
};

int _tmain(int argc, _TCHAR* argv[])
{
	CircullarArray *circullarArray = new CircullarArray();
// do staff here

	thread thread1(&CircullarArray::pop, circullarArray);
	thread thread2(&CircullarArray::pop, circullarArray);

	// wait untill the threads finish their task in case the main thread finish early.
	thread1.join();
	thread2.join();
}

- solxget April 25, 2015 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More