Google Interview Question Software Engineer in Tests


Country: United States
Interview Type: Written Test


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

public class CircularQueue {
    private int size;
    private int head;
    private int tail;
    private int q[];
    public CircularQueue(int s) {
        size = s;
        q = new int[s+1];
        head = 0;
        tail = 0;
    }
    public synchronized void initialize() {
        head = 0;
        tail = 0;
    }
    public synchronized boolean enqueue(int v) {
        int tmp = (tail+1) % size;
        if (tmp == head) return false;
        q[tail] = v;
        tail = tmp;
        return true;
    }
    public synchronized int dequeue() throws Exception{
        if (head == tail) throw new Exception("queue underflow!");
        int tmp = q[head];
        head = (head + 1) % size;
        return tmp;
    }
}

- sqw on June 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

One small bug: the queue only accommodates s-1 integers, not s integers.

You could consider using tmp = (tail+1 == size) ? 0: tail + 1; to avoid the expensive modulo operation.

- eugene.yarovoi on June 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

nice thinking to remove the modulo.. but i think adding an if condition will also be somewhat expensive.. it ll have to flush and re fetch instruction pipeline when 'if' fails.. (if is also expensive).. i cant tell which one ll be more.. but something to think upon for performance sensitive contexts..

- 289abhi on August 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Since the if condition will almost always be false, the branch predictor should be able to pick up on that, guess false all the time, and make this common situation cheap. The branch will only be mispredicted when the condition is true, which will likely be once in a rare while.

Furthermore, it's likely that the compiler will eliminate the if statement altogether, replacing it with a special conditional set instruction available on many modern architectures, an instruction that either does nothing or sets a register to a value, depending on a condition flag. If this happens, there will be no need to have the possibility of an instruction jump. The code could look like (in pseudo-assembly):
[temp, size, tail are placeholders for the registers that hold these values, let's say]

add tmp, tail, 1 // tmp = tail + 1
cmp tmp, size  //sets the "Equal" condition flag to 1 iff tail+1 == size
csete tmp, 0 // Conditional SET if Equal. If "Equal" condition flag is 1, set register tmp to 0.

In hardware, these sorts of conditional instructions work simply by having some AND and OR logic gates to apply a bitmask based off the condition flag.

In fact, the operation could even have been written in software (not that I recommend such code):

tmp = tail + 1;
//right arithmetic shift. If temp = size, it evaluates to a mask of all 0s; if temp < size, all 1s. INTEGER_BIT_WIDTH is 32 for 32-bit integers, 64 for 64-bit integers, etc.
conditionMask = (tmp - size) >> (INTEGER_BIT_WIDTH - 1);
// apply the mask to tmp, either clearing tmp or not changing it
tmp &= conditionMask;

- eugene.yarovoi on August 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Shouldn't your synchronize be on the queue instead of at method level? The current implementation does not take thread safety across methods into account.

- Anonymous on September 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

1- thread safety is broken (read/write blocks should be mutually exclusive)
2- queue should allow "overwrite" case which requires a tweak. constructor might take a parameter for that. this is important since
circular queue makes sense in most of the scenarios (audio/streaming) where overwriting is behaviour by design.

- yemre_ankara on September 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Anonymous, yemre_ankara: in Java, marking an instance method as synchronized obtains a lock on the instance itself upon entry and releases it on exit.

- eugene.yarovoi on September 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

I think you should do modulo with size + 1 instead of size.

- Sai Manoj Kumar on October 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

class MyQueue {
	static int[] queue;
	int front;
	int end;
	int count;

	void initialise(int queueSize) {
		queue = new int[queueSize];
		front = end = 0;
	}

	void enqueue(int element) {

		synchronized(queue) {
			if(count == queue.length - 1)
				System.out.println("Queue is Full"+count);
			else{
				if(front == 0) {
					front = 1;
				}
				end = (end % (queue.length-1)) + 1;
				queue[end] = element;
				System.out.println("Element entered:\t"+ end + "\t" + element);
				count++;
			}	
		}		
	}

	void dequeue() {
		synchronized(queue) {
			if(count == 0)
				System.out.println("Queue is Empty");
			else{
				System.out.println("Element Deleted:\t" + front + "\t" + queue[front]);
				front = (front % (queue.length-1)) + 1;
				count--;
			}	
		}
	}

	void display()
	{
		int temp = end;
		System.out.println("\nElements in the Queue:");
		int c = count;
		while(c > 0)
		{
			System.out.println(temp + "\t" + queue[temp]);
			temp = (temp % (queue.length-1)) - 1;
			c = c -1 ;
		}
		System.out.println("Front:\t" + queue[front] + "\tEnd:\t" + queue[end] + "\n");
	}
}

- Amruta on July 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class CircularQueue {
	private final int SIZE = 10;
	private int[] arr = new int[SIZE];
	private int head = -1;
	private int tail = 0;
	public void enqueue(int n){
		if(head == tail){
			System.out.println("Queue is Full");
		} else {
			synchronized (this){
				if(head == -1) head = 0;
				arr[tail] = n;
				tail=(tail+1)%SIZE;
			}
		}
	}
	public int dequeue() throws Exception{
		if(head == -1){
			throw new Exception("Queue is Empty");
		} else {
			int n;
			synchronized (this) {
				n = arr[head];
				head=(head+1)%SIZE;
				if(head == tail){
					head = -1;
					tail = 0;
				}
			}
			return n;
		}
	}
}

- ashwanilabs on July 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What is Written test for Google? Is it for On Campus selections?

- Andy2000 on September 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

can some one please give the final code ??

- Kamatchi on January 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Queue {

	int array[];
	int size = 0;
	int head, tail;
	static int counter = 0;

	synchronized public void initialize(int sizeofArray) {
		size = sizeofArray;
		array = new int[sizeofArray];
		head = -1;
		tail = 0;
	}

	void enqueue(Integer value) {
		System.out.println("enqueue Called....");
		if (head == tail) {
			System.out.println("Queue is filled");
			return;
		}
		synchronized (this) {

			{
				if (head == -1)
					head = 0;
				if(tail==size && head != 0)
				{
					tail=0;
				}
				array[tail] = value;
				tail++;
				counter++;
			}
		}
	}

	void dequeue() {
		System.out.println("dequeue Called....");
		if (head == -1) {
			System.out.println("Queue is empty");
			return;
		}
		synchronized (this) {
			{
				head++;
				counter--;
				if(head == tail){
					head = -1;
					tail = 0;
				}
			}
		}
	}

	public void getQueue() {
		System.out.println("GetQueue Called....");
		int temp = head;
		int temp2 = 0;
		for(int i = 0; i < counter; i++)
		{
			if(head < tail)
			 {
				System.out.println(array[temp]+"\n");
				temp++;
				if(temp==tail)
					break;
			 }
			if(head > tail || head == tail)
			{
				if(temp != size){
					System.out.println(array[temp]+"\n");
					temp++;}
				if(temp2<tail && temp == size){ 
					System.out.println(array[temp2]+"\n");
					temp2++;}
			}		
			
	}
		
}
}

public class queueOfArray {

	public static void main(String[] args) {
		Queue ob1 = new Queue();
		ob1.initialize(10);
		for (int i = 0 ; i < 10; i++)
		ob1.enqueue(i);
		
		ob1.getQueue();
		
		for (int i = 0 ; i < 7; i++)
		ob1.dequeue();
		
		ob1.getQueue();
		
		ob1.enqueue(16);
		ob1.getQueue();
		
	}

}

- Sandesh Sharma on February 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class CircularQueue {
    private int size;
    private int head;
    private int tail;
    private int array[];
    public CircularQueue(int initialCapacity) {
        size = initialCapacity;
        array = new int[initialCapacity];
        initialize();
    }
    public synchronized void initialize() {
        head = 0;
        tail = 0;
    }
    public synchronized void enqueue(int v) throws Exception {
        int tmp = (tail+1) % size;
        if (tmp == head) {
        	resizeQueue();
            array[tail] = v;
            
        }else{
            array[tail] = v;
            tail = tmp;
        }
    }
    public synchronized int dequeue() throws Exception{
        if (head == tail) throw new Exception("Empty Queue!");
        int tmp = array[head];
        array[head] = 0;  // Zero is just an arbitrary value, Just to simulate a clean up of the current slot
        head = (head + 1) % size;
        return tmp;
    }
    public void resizeQueue()throws Exception{
    	
    	size = size*2;
    	int tmp []= new int[size];
    	int index = 0;
    	
    	while(head != tail){
    		tmp[index++] = dequeue();
    	}
    	head = 0;
    	tail = index;
    	array = tmp;
    }
    public void printQueue(){
    	if( tail == head){
    		System.out.println("Empty Queue!");
    	}
    	for(int i = 0 ; i < array.length ; i++){
    	if(i == tail)
    			System.out.print("Tail->[" +array[i] +"],");
    		else if(i == head)
    			System.out.print("head->[" +array[i] +"],");
    		else
    			System.out.print("["+array[i]+"],");
    	}
    
    }
    
    public static void main(String [] args) throws Exception{
    	CircularQueue myQueue = new CircularQueue(5);
    	myQueue.enqueue(1);
    	myQueue.enqueue(2);
    	myQueue.enqueue(3);
    	myQueue.enqueue(4);
    	myQueue.enqueue(5);
    	myQueue.enqueue(6);
    	myQueue.dequeue();
    	myQueue.dequeue();
    	myQueue.dequeue();
    	myQueue.dequeue();
    	

        myQueue.printQueue();
    }
}

- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> on January 16, 2014 | Flag Reply


Add a Comment
Name:

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

Books

is a comprehensive book walking you through 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