Google Interview Question Software Engineer in Tests
Country: United States
Interview Type: Written Test
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.
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 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;
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.
@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.
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();
}
}
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();
}
}
class CircularQueue<T>
{
int cap;
int count = 0;
int front = 0;
int rear = 0;
T[] arr;
public CircularQueue(int cap)
{
this.cap = cap;
arr = new T[cap];
}
public bool Enqueue(T item)
{
if (count == cap)
return false;
arr[rear] = item;
rear = (rear + 1) % cap;
++count;
return true;
}
public T Dequeue()
{
if (count == 0)
return default(T);
T ret = arr[front];
front = (front + 1) % cap;
--count;
return ret;
}
}
- sqw June 28, 2012public 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; } }