Question regarding dequeues and testing

Question

Hello guys,

I am preparing for an interview and I came across these questions. Can some one please help how to solve these questions.

1. Imagine you've 2D system which is just testing whether 2 rectangles are in collision state or not, and you supposed to make a program which takes the code of this system from its developers and test it automatically to see if it's working good or not, and output the percentage of the error in the code ?

2. write out the queue and de-queue methods for a fixed length queue that is shared between two objects. Here what does objects refer to ? Thread synchronization ?

Thanks & Regards,

Mousey

Answer 1

For the first one, just plug in a known dataset and write the results. Sounds more like a coding assignment than a conceptual test.

For the second, write a circular queue. Generally, something is wrong with your job if you are writing a general data structure rather than using a library.

Unless they mention threads, I wouldn't make a big deal of it. But throwing critical sections around everything couldn't hurt.

Answer 2

For 1) You should test for overlap in the rectangles. The first test I would develop would simply start with the rectangles on top of each other and move them apart slowly until no collisions was detected. Error would most likely have to be measure either percentage of overlap or # of pixels that are overlapping. I'd do both... Who knows they may have developed the algorithm to be accurate to a pixel error or a % size of object error. ie.. more accurate for smaller objects. After this initial "quick test" I'd attempt to develop a more general case with more variation in the overlap. ie... 1 pixel in the top left corner overlapping with 1 pix in the bottom left corner of the other rectangle with varying sizes of rectangles. Testing some smart corner cases and some pseudo-random overlapping triangles seems like a good test design to me.

I always develop simple tests first to get immediate feedback then try to move to more general and thorough tests. Obviously if you put two rectangles down that are completely overlapping and there is no collisions something is wrong.

For 2) Counting semaphores comes to mind as a way to solve this problem. You want it to block when the queue is full on the input side and block when the queue is empty on the dequeue side. I'm not sure if both objects can queue and dequeue, but it really doesn't matter if you're using semaphores to keep track of the state of the queue. You also want to obtain an exclusive lock whenever you modify the queue.