Google Interview Question for Software Engineer / Developers


Country: United States




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

For precise definitions you can check books like "The Art of Multiprocessor Programming". Otherwise, "Java Concurrency in Practice" provides a pretty good idea in Chapter 15.

"non blocking" roughly means where threads are not blocked waiting to acquire some lock. Just combine that with what thread-safe means, so you have - code where threads do not wait to acquire some lock and still it works correctly with multiple threads.

Here's an attempt to do this using an AtomicBoolean flag to guard the non-threadsafe queue:

import java.util.ArrayList;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicInteger;

public class CASQueue<T> {

	private int capacity;
	private AtomicInteger size = new AtomicInteger(0);
	private ArrayList<T> queue = new ArrayList<T>();
	private AtomicBoolean inUse = new AtomicBoolean(false);

	public CASQueue(int capacity) {
		this.capacity = capacity;
	}

	public void offer(T value) {
		while (!inUse.compareAndSet(false, true)) {
			try {
				Thread.sleep(100);
			} catch (InterruptedException e) {
				System.out.println("Thread " + Thread.currentThread().getId() + " interrupted");
			}
		}
		if (size.get() == capacity) {
			inUse.set(false);
			throw new RuntimeException("Queue full!");
		}
		size.incrementAndGet();
		queue.add(value);
		System.out.println("Thread-" + Thread.currentThread().getId() + " pushed " + value + " into queue.");
		inUse.set(false);
	}

	public T take() {
		while (!inUse.compareAndSet(false, true)) {
			try {
				Thread.sleep(100);
			} catch (InterruptedException e) {
				System.out.println("Thread " + Thread.currentThread().getId() + " interrupted");
			}
		}
		if (size.get() == 0) {
			inUse.set(false);
			throw new RuntimeException("Queue empty!");
		}
		size.decrementAndGet();
		T value = queue.remove(0);
		System.out.println("Thread-" + Thread.currentThread().getId() + " retrieved " + value + " from queue.");
		inUse.set(false);

		return value;
	}

}

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

/**
 * Hello world!
 * 
 */
public class App {

	public static void main(String[] args) throws InterruptedException, ExecutionException {
		final CASQueue<Integer> queue = new CASQueue<Integer>(5);

		Callable<Integer> producer = new Callable<Integer>() {
			@Override
			public Integer call() {
				int pushCount = 0;
				for (int i = 0; i < 10; i++) {
					try {
						queue.offer(i);
						pushCount++;
					} catch (Exception e) {
						System.out.println("Thread-" + Thread.currentThread().getId() + " tried to put value into a full queue.");
					}
				}

				return pushCount;
			}
		};

		Callable<Integer> consumer = new Callable<Integer>() {
			@Override
			public Integer call() {
				int removeCount = 0;
				for (int i = 0; i < 9; i++) {
					try {
						queue.take();
						removeCount++;
					} catch (Exception e) {
						System.out.println("Thread-" + Thread.currentThread().getId() + " tried to remove value from an empty queue.");
					}
				}

				return removeCount;
			}
		};

		ExecutorService executorService = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors() + 1);
		List<Future<Integer>> pushes = new ArrayList<Future<Integer>>();
		List<Future<Integer>> removes = new ArrayList<Future<Integer>>();
		for (int i = 0; i < 10; i++) {
			if (i % 2 == 0) {
				pushes.add(executorService.submit(producer));
			} else {
				removes.add(executorService.submit(consumer));
			}
		}

		int pushCount = 0;
		for (Future<Integer> result : pushes) {
			pushCount += result.get();
		}

		int removeCount = 0;
		for (Future<Integer> result : removes) {
			removeCount += result.get();
		}

		executorService.shutdown();

		System.out.println("#successful pushes = " + pushCount);
		System.out.println("#successful removes = " + removeCount);

		// just a basic correctness test, assuming no InterruptedException comes
		// up
		int count = 0;
		try {
			System.out.println();
			while (true) {
				queue.take();
				count++;
			}
		} catch (Exception e) {
			System.out.println("\nQueue final size =" + count); // should be 5
		}
	}

}

- DevGuy January 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Are you sure about your interpretation of "non-blocking threadsafe" being "without aquring a lock"?

In your implementation you are effectively using a spinlock which is still a lock.

- Anonymous January 20, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

That's a good question.

Yes there is a spin lock in the code above. However, if you remove the sleeping part, it becomes polling the CAS variable which is what the wait-free implementations like ConcurrentLinkedQueue do as well. If you look at the code of CLQ you will see there is just the same while loop on CAS variable.

From Wikipedia page on non-blocking algorithms "In computer science, a non-blocking algorithm ensures that threads competing for a shared resource do not have their execution indefinitely postponed by mutual exclusion. A non-blocking algorithm is lock-free if there is guaranteed system-wide progress; wait-free if there is also guaranteed per-thread progress."

From chapter 7 (spin locks) of The Art of Multiprocessor Programming "Any mutual exclusion protocol poses the question: what do you do if you can- not acquire the lock? There are two alternatives. If you keep trying, the lock is called a spin lock, and repeatedly testing the lock is called spinning, or busy– waiting. The Filter and Bakery algorithms are spin locks. Spinning is sensi- ble when you expect the lock delay to be short. For obvious reasons, spinning makes sense only on multiprocessors. The alternative is to suspend yourself and ask the operating system’s scheduler to schedule another thread on your proces- sor, which is sometimes called blocking. Because switching from one thread to another is expensive, blocking makes sense only if you expect the lock delay to be long."

- DevGuy January 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

You mean 'non-blocking thread-safe /queue/s'? Is it different from blocking thread-safe /queue/s? Yes, different.

- JeffD February 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

When writing lock free, it is important to assign ownership of variables. For a Single producer, Single consumer following is guaranteed to be thread safe -

public static class LockFreeQueue<T> {
		private T[] buffer;  // Bounded buffer.
		private final int size;  // Max item = size - 1;
		private volatile int head;  // Dequeue from head. Owned by Consumer.
		private volatile int tail;  // Enqueue at tail. Owned by producer.
		
		public LockFreeQueue(T[] buffer) {
			this.size = buffer.length;
			this.buffer = buffer;
			this.head = 0;
			this.tail = 0;
		}
		public T dequeue() {
			// Check if queue is empty.
			if (tail == head) {
				return null;  // tail can only be incremented
			}
			// Fetch item. head and buffer location is owned by consumer.
			T item = buffer[head % size];
			head++;  // commit
			return item;
		}
		public boolean enqueue(T obj) {
			// Check if queue is full.
			if (tail == head + size - 1) {
				return false;
			}
			buffer[tail % size] = obj;
			tail++;  // commit
			return true;
		}
	}
	public void verify() {
		final LockFreeQueue<String> queue = new LockFreeQueue<String>(new String[2]);
		final int N = 10000000;
		System.out.println("Testing ..");
		Thread producer = new Thread(new Runnable() {
			@Override
			public void run() {
				for (int i = 0; i < N; ++i) {
					while(!queue.enqueue("" + i));
				}
			}
		});
		Thread consumer = new Thread(new Runnable() {
			@Override
			public void run() {
				for (int i = 0; i < N; ++i) {
					String item;
					while((item = queue.dequeue()) == null);
					if (Integer.parseInt(item) != i) {
						throw new RuntimeException("FIFO guarantee broken");
					}
				}
			}
		});
		producer.setDaemon(false);
		consumer.setDaemon(false);
		producer.start();
		consumer.start();
	}

Here head is owned by consumer and tail by producer. The cell at tail % size is owned by producer. Other cells with item is owned by consumer.

- Anonymous May 18, 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