Friday, December 15, 2006

Job Interview Puzzle: 3 Classic Weighing puzzles :Simple Medium and Hard



In this post I want to describe about a series of puzzles called weighing puzzles. These puzzle vary in hardness from simple to extremely mathematical involving either expertise in some fields or extreme ingenuity. Either you know it or you figure out it using extreme intelligence. So here is the chance for some people to burn your grey cells.

I am putting forward three puzzles with varying range of hardness. Sometimes you may feel the hardest one is very easy for you have already come across the theory, but I still made it the hardest for the people who will be solving it with out knowing the theory behind it, giving them an option to figure out a small part in evolution of computational history.

There is a shopkeeper who wants to weigh things who has a common balance. He must be in a position to weigh things of all possible integral weighing units from 1 to a given maximum sum. The question will be either about how many weights you will need or how will you weigh.

Problem 1: One Side Only (Simple Interview Question for Phone Screening usually)

In this version of the problem shopkeeper can only place the weights in one side of the common balance. For example if shopkeeper has weights 1 and 3 then he can measure 1,3 and 4 only. Now the question is how many minimum weights and name the weights you will need to measure all weights from 1 to 1000. This is a fairly simple problem and very easy to prove also.


Problem 2: Both Sides (Medium:5 to 10 mins onsite interview question)

This is same as the first problem with the condition of placing weights on only side of the common balance being removed. You can place weights on both side and you need to measure all weights between 1 and 1000.For example if you have weights 1 and 3,now you can measure 1,3 and 4 like earlier case, and also you can measure 2,by placing 3 on one side and 1 on the side which contain the substance to be weighed. So question again is how many minimum weights and of what denominations you need to measure all weights from 1kg to 1000kg.

Problem 3: Incremental (Hard)
This is an altogether different one in the same scenario. You have to make 125 packets of sugar with first one weighing 1 kg, second 2 kg, third 3 kg etc ...and 125th one weighing 125kg.You can only use one pan of the common balance for measurement for weighing sugar, the other pan had to be used for weights i.e. weights should be used for each weighing.
It has come into notice that moving weights into and out of the pan of the balance takes time and this time depends on the number on the number of weights that are moved. For example - If we need to measure 4 kg using weights 1 and 3 only, it will take twice as much time needed to measure 1 kg. Lets say we want to make sugar packets of weights 1,3,4 using weights 1 and 3 only. For this first we measure 1 kg, with 1 unit of time, we place 3 kg along with 1 kg and measure 4kg with again 1 unit of time, and finally we move 1kg out of pan to measure 3kg in 1 unit of time. So in 3 units of time we could measure 1,3 and 4kg using weights 1 and 3 only.

Now you have to make sugar packets of all weights from 1 to 125 in minimum time, in other words in minimum movement of weights. The question here is to find out the minimum number of weighs needed and the weight of each the weights used and the strategy to be followed for the creation of 125 packets of sugar.


Please post your solutions as comments.Solution will be posted soon in the blog.If any where its obfuscated or simple wrong pls feel free to correct.

95 comments:

Ricky Clarkson said...

"For example if shopkeeper has weights 1 and 3 then he can measure 1,3 and 4 only."

Surely he can measure 2.

Assuming he can't, I'd say 1, 2, 4, 8, 16, 32, 64, 128, 256, 512 are the required weights.

Christophe Poucet said...

Well I do not think the questions are that difficult.

In the first case, the poster is correct, it is simply the weights: 1, 2, 4, 8, 16, 32, 64, 128, 512

In the second case, we need to get subtractive logic involved as well. A quick analysis reveals that this means that we need to work in base 3 instead of 2 cause we only have three options. And for getting up to 1000 we then need the weights: map (3^) [0..6] meaning 7 weights.

In the third case it's also not so very difficult,. For some reason it reminds me of gray numbers, although in this case the bit encoding is fixed (the weights). The principle is the same, basically you want to minimize bitflips. So the maximum weight was 125, so we need 7 weights: map (2^) [0..6]. All that is required now is to traverse the space of all bits (except for the numbers 126 and 127 on, though if we include those number that's just two weight changes more cause each number can be arrived to by one weight change)
so that at each step we only flip one bit.

Reginald Braithwaite said...

With respect to the medium problem, if the unknown object has a whole number weight (1, 2, 3 ... but not 3.14 or 1.618), you do not need a one, the lightest weight should be a two.

As christophe points out, you can then work base 3 so the sequence goes { 2, 6, 18, ... } and not { 1, 3, 9, ... }

Dhananjay said...

excellent answers ....Christophe (vincenz)... :-) !!

Satheesh Rishi said...

for medium ....it is 1,3,7,23,69,207,415,831.

This goes in a pattern like prev_num*2 + 1

Satheesh Rishi said...

sorry it is sum of prev nums

Lost in Sea- The seafarer! said...

i dont think roganwald solution is correct.how can some body weight for ,1 kg,3kg for expample with the denomanation of {2,6,18,...}....

Unknown said...

I'm not computer guy, so let me talk ppure high school maths.

Basically its sum of geometric progession with first term=1 and common ratio=2.
a,ar,ar2,ar3....ar9=No of terms:10

So, sum of first 10 terms is
1023

I.e n=10

SO 10 weights are required

Yogesh said...

Rishi's solution is looking quite ok...

krithika said...

so is the final answer 125?

Unknown said...

The third one has 2 pans.. one for measuring sugar and other for weights. first use the 1kg weight to measure one kg sugar. Now use this sugar and a 3 kg on the weigh pan to measure 2 kg and so on....

The sequence is 1,3,9,27,81.... this will end up the process in min time.

Mohd Shahid said...

For easy solution is 1,2,4,8,16,32,64,128,256,512 and medium answer is 1,3,8,16,32,64,256,512

Interview Puzzles said...
This comment has been removed by the author.
Interview Puzzles said...

Check interview puzzles for more puzzle with answers like this.

mahesh said...

For Hard problem.. the solution is 1,3,9,27,81 and we will measure in a sequence ..i.e., 1,(3-1),3,3+1,.....

I think this might be the best solution

neeraj/iitr said...

for medium, the solution could be 1,3,12,33,99,297,891

hemant_finding my way said...

Hi,
For the first question..
Can you prove/disprove that the set
(1,2,4,8,16,32,64,128,256 and 512) is the only sets of 10 weights that can be used to weigh all the weights from 1 to 1000 kg?

kanhaiya sharma said...

Great Blog with very good posts .Can you please tell me that how much time you take to create this wonderful blog,although i am new on internet but your work is very good and i appreciate your work.
Aptitude test

Ashish Lahoti said...

I have been asked the same question in one of the interview - How many minimum weighs required to measure weight from 1 to 60 kg?

If use one side balance (1,2,4,8,16,32 = 6 weighs)
If use both side balance
(1,3,9,27,81 = 5 weighs)

sWebDev said...

http://iamsoftwareengineer.blogspot.com Check out software aspirants

Ashutosh Mukherjee said...

explain the third one without using gray coding scheme

Unknown said...

I'm not a genius but bear with me.
Is this correct for 3?

1x1KG weight.
Measure 1KG bag
Move 1KG bag to other side
Measure 2KG bag
Remove 1KG bag
Move 2KG bag to other side
Measure 3KG bag
Following this process till you reach 125

A loop
measure N bag against N-1 bag + 1KG weight
Remove N-1 bag and replace with N bag
Repeat until N = 125

Vibhor said...

Good collection of puzzles.

Unknown said...

Thank you for sharing such a useful information. It was so useful. Please visit
GK

viji said...

you are posting a good information for people and keep maintain and give more updates too.

seo company india

Hema said...

you are giving a very interesting post and it is usefull.
informatica training in chennai

Sindhuja Ravi said...

your post conveys a good messages and interesting things and give more updates.
digital marketing company in india

Unknown said...

Interesting blog post.This blog shows that you have a great future as a content writer.waiting for more updates...

Digital Marketing Company in India

Digital Marketing Services in India

Digital Marketing Agency in India

Digital Marketing Companies in India

Digital Marketing Company India

Digital Marketing Companies India

Unknown said...

Thank you for taking the time to provide us with your valuable information. We strive to provide our candidates with excellent care.As always, we appreciate you confidence and trust in us.


Best Training Institute in chennai

Ancy merina said...
This comment has been removed by the author.
Web Logix Infotech said...

i like this blog.Thanks for sharing post.Which is the Best Website Designing Company in Delhi NCR?

Web Logix Infotech said...

Thanks for sharing post Which is the Best SEO Company in Delhi NCR?

Saro said...

Wow it is really wonderful and awesome thus it is very much useful for me to understand many concepts and helped me a lot. it is really explainable very well and i got more information from your blog.

rpa training in chennai
rpa training in bangalore
rpa course in bangalore
best rpa training in bangalore
rpa online training

akash thakur said...

thanks for giving that type of information. ielts coaching in gurgaon

Unknown said...

It would have been the happiest moment for you,I mean if we have been waiting for something to happen and when it happens we forgot all hardwork and wait for getting that happened.
Data Science training in rajaji nagar | Data Science Training in Bangalore
Data Science with Python training in chennai
Data Science training in electronic city
Data Science training in USA
Data science training in pune

sai said...

After seeing your article I want to say that the presentation is very good and also a well-written article with some very good information which is very useful for the readers....thanks for sharing it and do share more posts like this.
python course in pune
python course in chennai
python course in Bangalore

simbu said...

This is a nice article here with some useful tips for those who are not used-to comment that frequently. Thanks for this helpful information I agree with all points you have given to us. I will follow all of them.
Java training in Bangalore | Java training in Jaya nagar

Java training in Bangalore | Java training in Electronic city

Java training in Chennai | Java training institute in Chennai | Java course in Chennai

Java training in USA

Unknown said...

Really you have done great job,There are may person searching about that now they will find enough resources by your post
Best Devops training in sholinganallur
Devops training in velachery
Devops training in annanagar
Devops training in tambaram

nivatha said...

I read this post two times, I like it so much, please try to keep posting & Let me introduce other material that may be good for our community.

Data Science course in Chennai | Best Data Science course in Chennai
Data science course in bangalore | Best Data Science course in Bangalore
Data science course in pune | Data Science Course institute in Pune
Data science online course | Online Data Science certification course-Gangboard
Data Science Interview questions and answers
Data Science Tutorial

jeeva said...

Great Article… I love to read your articles because your writing style is too good, its is very very helpful for all of us and I never get bored while reading your article because, they are becomes a more and more interesting from the starting lines until the end.

rpa training in chennai
rpa training in bangalore
rpa training in pune
rpa training in marathahalli
rpa training in btm
best rpa training in chennai

LENIN said...

Does your blog have a contact page? I’m having problems locating it but, I’d like to shoot you an email. I’ve got some recommendations for your blog you might be interested in hearing.
AWS Training in Chennai |Amazon Web Services Training in Chennai
AWS Training in Rajaji Nagar |Best Amazon Web Services Training in Rajaji Nagar
AWS Amazon Web Services Training in Chennai | AWS Training and Certification for Solution Architect in Chennai
AWS Training Institute in Bangalore | AWS Course in Bangalore

afiah b said...

Thanks Admin for sharing such a useful post, I hope it’s useful to many individuals for developing their skill to get good career.
Java training in Bangalore | Java training in Indira nagar

Java training in Bangalore | Java training in Rajaji nagar

Java training in Bangalore | Java training in Marathahalli

Java training in Bangalore | Java training in Btm layout

Unknown said...

Excellent post!!!. The strategy you have posted on this technology helped me to get into the next level and had lot of information in it.
Best Devops online Training
Online DevOps Certification Course - Gangboard

Unknown said...

Would you suggest starting with a free platform like Word Press or go for a paid option? There are so many choices out there that I’m completely confused. Any suggestions? Thanks a lot.
AWS Training in Bangalore electronic city| AWS Training in Bangalore BTM Layout
AWS Training in Pune with placements | AWS Training in Pune kharadi
AWS Training in Chennai review |Best AWS Training in Chennai tnagar
Best AWS Amazon Web Services Training in Chennai | Best AWS Training centers in Chennai
AWS Online Training in india | AWS online training cost

شركة المثالي سوبر said...

شركة عزل الاسطح بالخبر
شركة كشف تسربات المياه بعنك
شركة كشف تسربات المياه بسيهات

Unknown said...


Nice post. it is very interesting and informative. Thank you for the sharing.
Deer Hunting Tips Camping Trips Guide DEER HUNTING TIPS travel touring tips

Unknown said...


Well thanks for the information, do not forget to visit my blog too.

Still Hunting Method
Hunting psych tips Survival Tips Travel Touring Tips

Unknown said...



Thanks for sharing this quality information with us. I really enjoyed reading.
travel trekking tips
see the link Tent Camping 101 Exploring Smithriver

Chiến SEOCAM said...

ستاسو مضمون ډیر معنی دی

chó Corgi

bán chó Corgi

chó Corgi giá bao nhiêu

mua chó Corgi

svrtechnologies said...

Thanks for Sharing such an useful info...

learn data science

Never Ending Footsteps said...

data science course bangalore is the best data science course

360DigiTMG said...

Such a very useful article. Very interesting to read this article.I would like to thank you for the efforts you had made for writing this awesome article.
data analytics course
business analytics course
data science courses

offpageseo70 said...

Nice blog,I understood the topic very clearly,And want to study more like this.
Data Scientist Course

Priyanka said...

Attend The Data Analytics Courses From ExcelR. Practical Data Analytics Courses Sessions With Assured Placement Support From Experienced Faculty. ExcelR Offers The Data Analytics Courses.
ExcelR Data Analytics Courses
Data Science Interview Questions

priyash said...

wonderful article. Very interesting to read this article.I would like to thank you for the efforts you had made for writing this awesome article. This article resolved my all queries.
Data science Interview Questions
Data Science Course

hrithiksai said...

This Was An Amazing ! I Haven't Seen This Type of Blog Ever ! Thankyou For Sharing, data science training

Ben Johnson said...

Wonderful Article ...Completely impressed with your writing...

DevOps training in chennai | DevOps Certification Course in chennai BITA academy

Python training in chennai | Microsoft Azure Certification training in chennai

datasciencecourse said...

cool stuff you have and you keep overhaul every one of us

data science course

hrithiksai said...

This Was An Amazing ! I Haven't Seen This Type of Blog Ever ! Thankyou For Sharing, data sciecne course in hyderabad

hrithiksai said...

This Was An Amazing ! I Haven't Seen This Type of Blog Ever ! Thankyou For Sharing, data science training in Hyderabad

hrithiksai said...

This Was An Amazing ! I Haven't Seen This Type of Blog Ever ! Thankyou For Sharing, data science course in hyderabad with placements

datasciencecourse said...

I like viewing web sites which comprehend the price of delivering the excellent useful resource free of charge. I truly adored reading your posting. Thank you!

data science course

nisha said...

The Blog is really useful for the Learners.

Data Science Training Course In Chennai | Data Science Training Course In Anna Nagar | Data Science Training Course In OMR | Data Science Training Course In Porur | Data Science Training Course In Tambaram | Data Science Training Course In Velachery

datasciencecourse said...

This is a wonderful article, Given so much info in it, These type of articles keeps the users interest in the website, and keep on sharing more ... good luck.

Correlation vs Covariance

priyash said...

Very interesting to read this article.I would like to thank you for the efforts you had made for writing this awesome article. This article inspired me to read more. keep it up.
Correlation vs Covariance
Simple linear regression

varsha said...

I believe that your blog will surely help the readers who are really in need of this vital piece of information. Waiting for your updates
AWS training in chennai | AWS training in annanagar | AWS training in omr | AWS training in porur | AWS training in tambaram | AWS training in velachery

Ziarulunirea.ro said...

Very interesting blog. Many blogs I see these days do not really provide anything that attracts others, but believe me the way you interact is literally awesome.You can also check my articles as well.

Data Science In Banglore With Placements
Data Science Course In Bangalore
Data Science Training In Bangalore
Best Data Science Courses In Bangalore
Data Science Institute In Bangalore

Thank you..

rocky said...

Wow super. This article is very impressed.
Python Training in Chennai | Certification | Online Training Course | Python Training in Bangalore | Certification | Online Training Course | Python Training in Hyderabad | Certification | Online Training Course | Python Training in Coimbatore | Certification | Online Training Course | Python Training in Online | Python Certification Training Course





devi said...

I believe there are many more pleasurable opportunities ahead for individuals that looked at your site.
Data Science Training In Chennai | Certification | Data Science Courses in Chennai | Data Science Training In Bangalore | Certification | Data Science Courses in Bangalore | Data Science Training In Hyderabad | Certification | Data Science Courses in hyderabad | Data Science Training In Coimbatore | Certification | Data Science Courses in Coimbatore | Data Science Training | Certification | Data Science Online Training Course


Damien Grant said...

https://digitalweekday.com/
https://digitalweekday.com/
https://digitalweekday.com/
https://digitalweekday.com/
https://digitalweekday.com/
https://digitalweekday.com/
https://digitalweekday.com/
https://digitalweekday.com/

Damien Grant said...

https://digitalweekday.com/
https://digitalweekday.com/
https://digitalweekday.com/
https://digitalweekday.com/
https://digitalweekday.com/
https://digitalweekday.com/
https://digitalweekday.com/
https://digitalweekday.com/

EXCELR said...

This post is great. I reallly admire your post. Your post was awesome.
data science course in Hyderabad

priyash said...

Very interesting to read this article.I would like to thank you for the efforts you had made for writing this awesome article. This article inspired me to read more. keep it up.
Correlation vs Covariance
Simple linear regression
data science interview questions

CloudLearn ERP said...

This article is well formulated. I particularly like the way how you have delivered all the major points about the topic of the content in petite and crisp points.
Data Science training in Mumbai
Data Science course in Mumbai
SAP training in Mumbai

Priyanka said...

Attend The Data Analyst Course From ExcelR. Practical Data Analyst Course Sessions With Assured Placement Support From Experienced Faculty. ExcelR Offers The Data Analyst Course.
Data Analyst Course

priyanka said...

Amazing Article ! I would like to thank you for the efforts you had made for writing this awesome article. This article inspired me to read more. keep it up.
Correlation vs Covariance
Simple Linear Regression
data science interview questions
KNN Algorithm
Logistic Regression explained

360digitmg said...

Great post i must say and thanks for the information. Education is definitely a sticky subject. However, is still among the leading topics of our time. I appreciate your post and look forward to more.
360DigiTMG data science course in ECIL

Priyanka said...

Attend The Data Analyst Course From ExcelR. Practical Data Analyst Course Sessions With Assured Placement Support From Experienced Faculty. ExcelR Offers The Data Analyst Course.
Data Analyst Course

EXCELR said...

I enjoyed your blog Thanks for sharing such an informative post. We are also providing the best services click on below links to visit our website.data science courses

un known said...

Thanks for Sharing This Article.It is very so much valuable content. I hope these Commenting lists will help to my website
devops online training
best devops online training
top devops online training

Priyanka said...

Attend The Data Analytics Courses From ExcelR. Practical Data Analytics Courses Sessions With Assured Placement Support From Experienced Faculty. ExcelR Offers The Data Analytics Courses.
Data Analytics Courses

Excelr Tuhin said...

I've read this post and if I could I desire to suggest you some interesting things or suggestions. Perhaps you could write next articles referring to this article. I want to read more things about it!
data science course in Hyderabad

360digiTMG Training said...


Regular visits listed here are the easiest method to appreciate your energy, which is why I am going to the website everyday, searching for new, interesting info. Many, thank you!
Data Science Training

Gopinath said...

Hi! Thank you for the share this information. This is very useful information for online blog review readers. Keep it up such a nice posting like this.

Data Science Training in Chennai

Data Science Course in Chennai

Mallela said...

Thanks for posting the best information and the blog is very helpful.python course in Bangalore

data scientist said...

Terrific post thoroughly enjoyed reading the blog and more over found to be the tremendous one. In fact, educating the participants with it's amazing content. Hope you share the similar content consecutively.
Data Analytics Course in Raipur

Mallela said...

Thanks for posting the best information and the blog is very helpful.Data science course in Faridabad

Mallela said...

Thanks for posting the best information and the blog is very helpful.data science interview questions and answers

Jon Hendo said...

online events allow companies to reach their entire user base as opposed to the 5 to 10 percent that used to attend in person. event marketing and virtual gifts

Deekshitha said...

Informative blog
data science course in india

Maneesha said...

I would like to thank you for the efforts you have made in writing this article. I am hoping the same best work from you in the future as well..
data scientist training and placement in hyderabad

Data Science Course in Varanasi - 360DigiTMG said...

Truly mind blowing blog went amazed with the subject they have developed the content. These kind of posts really helpful to gain the knowledge of unknown things which surely triggers to motivate and learn the new innovative contents. Hope you deliver the similar successive contents forthcoming as well.

data science in bangalore

Maneesha said...

I wanted to thank you for this great read!! I definitely enjoying every little bit of it I have you bookmarked to check out new stuff you post.
data scientist training and placement

Mallela said...

Thanks for posting the best information and the blog is very important.digital marketing institute in hyderabad

data science said...

I was just examining through the web looking for certain information and ran over your blog.It shows how well you understand this subject. Bookmarked this page, will return for extra. data science course in vadodara