Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
2.
Puzzle Description
3.
Solution
4.
Frequently Asked Questions
4.1.
How to approach a puzzle interview problem?
4.2.
Why are puzzles asked in interviews?
4.3.
What do you mean by puzzle reasoning?
5.
Conclusion
Last Updated: Mar 27, 2024

Good Processor

Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM
Interview Puzzles

Introduction 

Puzzles are a good measure of one's analytical skills and lateral thinking. Many product-based companies ask the puzzles to help them filter candidates based on their real-world problem-solving skills to approach a problem they have not seen before.

A puzzle may have multiple solutions. The interviewer is generally interested in the candidate's approach to solving the mystery and the approach to building and thinking creatively about the answer to the puzzle.

Puzzle Description

You are on a spaceship that has a laptop with n processors. Suddenly, the spacecraft receives hit by an alien laser beam, and many of the processors are damaged. However, you realize that more than n/2 of the processors are nevertheless top. You can ask one processor whether or not it thinks every other processor is top or terrible. A top processor will usually inform the truth. However,terrible one will usually lie. A ‘step’ includes asking one processor if it thinks every other processor is top or awful. Find the minimal quantity of steps required to locate as a minimum one top processor. The answer is an integer.

Example 1: if n=8, ans=6.

Example 2: if n=12, ans=10.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Solution

N-2 is the answer.

Explanation:

Let the processors be numbered from 1 to n. Begin via way of means of asking processor one if processor 2 is top. If the solution is “no,” cast off or remove those processors from the listing and begin over. You eliminated one top processor and one terrible processor from the listing, so more than n/2 of the final processors are top. If processor 1 says processor 2 is top, move on by asking processor two about processor threethree about 4, etc., till you get a “no” answer. Suppose it's a processor j that announces processor j+1 is terrible. Remove each processor j and j+1 from the listing (as earlier thanmore than n/2 of the remaining processors are nevertheless top because two of you eliminated became top and one became terrible), and preserve via way of means of asking processor j-1 about processor j (the processor that became after j+1 earlier than you eliminated it and the authentic processor j).

You are developing a “chain” of processors who every suppose the subsequent processor within side the chain is exact. So those processors are both all the same or all horrific. Once this chain contains more than 1/2 of the processors within the final listingyou realize that every one of those processors is exact. Or, if you’ve eliminated such a lot of processors that simplest one or remain, you know that one of the ones is exact.

To display that this includes at maximum n-2 steps, notice that each processor is requested approximately at maximum as soon as, and the primary processor is in no way asked roughly. Also, the remaining processor is not asked around both because you prevent it as soon as the chain is more extended than 1/2 of the listing.

 

Ex:-  BGBGBGBGBGGG
If there are 12 processors, 7 will be top, and five will be terrible. So you come across 5 terrible processors, and you remove  5 top and 5 terrible processors like this:

Removed: - GB, GB, GB, GB, GB
Remaining:-  G , G
After this, we are sure that there are only top processors left. So it took n-2 steps for us to calculate that.

Check out this problem - 8 Queens Problem

Frequently Asked Questions

How to approach a puzzle interview problem?

  1. Thinking about problem
  2. Clarity regarding problem
  3. Use brute force first
  4. Try to make logic
  5. Get the solution

Why are puzzles asked in interviews?

To see how you will approach a real-time and tricky situation.

What do you mean by puzzle reasoning?

It simply means analyzing the data given in the puzzle and arranging data to get the correct solution.

Conclusion

In this article, we discussed the popular interview puzzle Good Processor along with its possible solution

Recommended Readings:


Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Interview Puzzles, Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

We hope that this blog has helped you enhance your knowledge regarding puzzles, and if you liked this blog, check other links. Do upvote our blog to help other ninjas grow. Happy Coding!"

Live masterclass