Google Interview Question Software Engineer in Tests
0of 0 votesImplement a circular queue of integers of user-specified size using a simple array. Provide routines to initialize(), enqueue() and dequeue() the queue. Make it thread safe.
Country: United States
Interview Type: Written Test
Also, I'd recommend the use of tmp = (tail+1 == size) ? 0: tail + 1;
to avoid the expensive modulo operation, if you wanted to optimize this. Circular queues are often used in performance-sensitive contexts.
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..
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 add instruction (a special instruction that either does nothing or adds a number, depending on a condition flag). 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 zero condition flag to 1 iff tail+1== size
sub free_register, 0, tmp // free_register = -tmp
cincz tmp, free_register // Conditional INCrement if Zero condition flag. tmp is reduced to 0 if condition was met.
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.
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.
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");
}
}
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;
}
}
}
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();
}
}
- sqw on June 28, 2012 Edit | Flag Replypublic 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; } }