Good Processor — Puzzle for Interview rounds

Question :

You are on a spaceship that has a computer with n processors.

Suddenly, the spaceship gets hit with an alien laser beam, and some of the processors are damaged.

However, you know that more than half of the processors are still good.

You can ask one processor whether it thinks another processor is good or bad. A good processor will always tell the truth, but a bad one will always lie.

A ‘step’ consists of asking one processor if it thinks another processor is good or bad. Find minimum number of steps required to find at least one good processor.

Answer is a integer.

Solution :

N-2 is the correct answer.

Let the processors be numbered 1…n. Begin by asking processor 1 if processor 2 is good. If the answer is “no”, remove these two processors from the list and start over. Note that you removed one good processor and one bad processor from the list, so more than half of the remaining processors are still good.If processor 1 says processor 2 is good, continue by asking processor 2 about processor 3, 3 about 4, etc., until you get a “no” answer. Suppose it is processor j that says processor j+1 is bad. Remove both processors j and j+1 from the list (as before, more than half of the remaining processors are still good, since one of the two you removed was good and one was bad), and continue by asking processor j-1 about processor j (the processor that was after j+1 before you removed it and the original processor j).
You are creating a “chain” of processors who each think the next processor in the chain is good. So these processors are either all good or all bad. Once this chain comprises more than half of the processors in the remaining list, you know that all these processors are good. Or, if you’ve removed so many processors that only one or two remain, you know that that one or those two are good.
To show that this involves at most n-2 steps, note that every processor is asked about at most once, and the first processor is never asked about. Also, the last processor is never asked about either, since you stop once the chain is longer than half the list.

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.




Upskilling students for tech placements!

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

2021: Creating a Lexicon of Future

Extending The Python Debugger

ELK stack on a Kubernetes cluster: A hard way

For Python, Everything is an Object

#PythonTip: List Vs Set performance experiments

Length of Shortest sub-array containing ‘k’ distinct elements of another Array | Sliding Window…

Memory Isolation Violation in Deserialization Code — Certora Bug Disclosure

How to deploy a PostgreSQL Cluster on Kubernetes + OpenEBS

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store


Upskilling students for tech placements!

More from Medium

Class Quiz

“Delete and Earn” problem using Dynamic Programming

Graph Algorithms

Scattered Rice Coding Question