Interview Question

Software Engineer Interview Migdal Ha`Emeq (Israel)

Here I will refer only to the second interview because the

  first one was really trivial. 1) You have a plate with areas, some of them must be checked and the order of the check is given. Your maching has three operations: move to the cell, aquire the image, measure the image. How can you do it as efficiently as possible

Interview Answer

1 Answer


I said that it seems classic producer-consumer problem and that move-aquire must be implemented as one thread and this thread is the producer, and the second thread or pull of threads are the measuring threads, the consumers.
I said that we need some round-buffer to keep all the jobs and each measuring thread will keep also its own local buffer with k jobs. All the partners that use the buffer must get a mutex lock for it, so there will be mutual exclusion and measuring thread lock the buffer and take k jobs at once, to reduce number of mutex invocations. Also I said that it is possible that producer makes jobs whe there is no memory, so I add semaphor isBufferFull that initially is set on n and one semaphor for measuring threads that initially is set on zero.

Here are the pseudocodes I wrote:
semafor isBufferFull = n;
semafor isBufferEmpty = 0;

For Aquisition: For Measure:
forever do{ forever do{
mv.move(); isBufferEmpty.get(k);
Img im = aquire(); buffer.copy(myBuff, k);
isBufferFull.get(1); isBufferFull.release(k);
buffer.add(im); process(myBuff);

Interview Candidate on Jan 11, 2010

Add Answers or Comments

To comment on this, Sign In or Sign Up.