দুটি মাইক্রোসফট্ ইন্টারভিউ প্রশ্ন

View previous topic View next topic Go down

দুটি মাইক্রোসফট্ ইন্টারভিউ প্রশ্ন

Post by BIT0112-Rokon on Tue Jun 14, 2011 8:24 am

সমস্যাঃ ১

আপনার সামনে দশটি স্বচ্ছ প্লাস্টিকের বাক্স লাইন করে সাজানো আছে। প্রতিটি বাক্সে আছে ছোট ছোট অনেকগুলি কয়েন। প্রতিটি কয়েনের ওজন দশ গ্রাম করে। দশটি বাক্সের মধ্যে কেবলমাত্র একটি বাক্স আছে, যেখানকার কয়েনগুলোতে সমস্যা আছে। দশ গ্রামের বদলে সেখানকার প্রতিটি কয়েনের ওজন এগারো গ্রাম করে। কিন্তু সেটা দেখে বুঝবার কোনো উপায় নেই, একমাত্র ওজন করেই বুঝা সম্ভব। এখন ওজন মাপবার জন্য আপনাকে একটা মেশিন দেয়া হলো। সেই ওজন মাপবার মেশিনে আপনি যাই ওজন করতে চান না কেন, একবার ওজন করতে পারবেন। একবার কোনো কিছু ওজন করে ফেললে, মেশিনটা আপনার কাছ থেকে সরিয়ে নেয়া হবে। আপনি যে-কোনো বাক্স থেকে যতখুশি কয়েন নিতে পারেন, যা খুশি ওজন করতে পারেন। এখন সমস্যাটা হচ্ছে, যা খুশি ওজন করুন না কেন, একবারমাত্র ওজন করে আপনাকে বলতে হবে, ঠিক কোন বাক্সের কয়েনগুলিতে সমস্যা আছে। কিভাবে আপনি সমাধান করবেন?


সমস্যাঃ ২

৩০টি ক্যান্ড ফুড।
১টিতে বিষ আছে।
ইঁদুর দিয়ে পরীক্ষা করতে হবে। খাওয়ার ১৪ ঘন্টা পরে ইঁদুর মারা যাবে।
২৪ ঘন্টায় পরীক্ষা শেষ করে বলতে হবে কোন ক্যনে বিষ ছিল।

প্রশ্নঃ সর্বনিম্ন কয়টি ইঁদুর লাগবে?

বলে রাখি এই প্রশ্ন দুটি মুক্তমনা থেকে নেওয়া। আমাদের রাজু স্যার এর ব্লগ থেকে কপি করে দিলাম। সমস্যা দুটি আমার পছন্দ হয়েছে। সফট্ওয়্যার ইঞ্জিনিয়ারিং কিংবা কম্পিউটার প্রোগ্রামিং করার ক্ষেত্রে সমস্যা সমাধান(বিশেষ করে গাণিতিক) করার ক্ষমতা, পুরোপুরি সমাধান না হলেও সমাধানের জন্য চিন্তা করতে পারার ক্ষমতাকে একটি গুরুত্বপূর্ণ যোগ্যতা হিসেবে দেখা হয়। সুতরাং কেও চেষ্টা করে দেখতে পারে।

_________________________________________________________________


Code Explosion Blog | Code Explosion Wiki | The Rokonoid | নির্ঝরিণী

BIT0112-Rokon
Programmer
Programmer

Course(s) :
  • BIT

Blood Group : O+
Posts : 673
Points : 1269

View user profile http://blog.codexplo.org

Back to top Go down

Re: দুটি মাইক্রোসফট্ ইন্টারভিউ প্রশ্ন

Post by BIT0130-Shakkhor on Tue Jun 14, 2011 9:24 pm

Problem 2ta face korsi er age. 2nd tar akta generalized solution dei.

let's assume the following prototype of this method log(base, exp).

Now, number of rats required will be ceiling(log(2*n, number_of_bottles)),
where n=floor(hours_available_in_total/hours_for_one_rat_to_die).

For this case, the answer is 5. Jodi 1ta rat morte 14hr er jaygay 12hr lagto, then answer hobe 3.

UVa te similar akta problem ase. The solution is here:

Code:
#include <stdio.h>

int getPowerOfTwo(long long n)
{
   long long result=1;
   int power=0;
   if(n<=1) return 0;
   do
   {
      result=result<<1;
      power++;
   }
   while(n>result);
   return power;
}

int main()
{
   int cases;
   long long input;
   scanf("%d ",&cases);
   for(int i=0;i<cases;i++)
   {
      scanf("%lld",&input);
      printf("Case %d: %d\n",i+1,getPowerOfTwo(input+1));
   }
}

_________________________________________________________________
I'm not a driver with drinking problem.
I'm an alcoholic with driving problem.

Blog | বাংলা ব্লগ

BIT0130-Shakkhor
Programmer
Programmer

Course(s) :
  • BIT

Blood Group : B+
Posts : 209
Points : 328

View user profile

Back to top Go down

Re: দুটি মাইক্রোসফট্ ইন্টারভিউ প্রশ্ন

Post by BIT0130-Shakkhor on Wed Jun 15, 2011 3:17 am

There is another soluiton. This one was proposed by Amit.

1 min por por 1ta idur re 1ta kore can theke food dite hobe, then time er track rakhte hobe. nth can ta poisoned hoile 14hr nth minute idur ta mara jabe.

For the given problem, this is a more elegant solution.

_________________________________________________________________
I'm not a driver with drinking problem.
I'm an alcoholic with driving problem.

Blog | বাংলা ব্লগ

BIT0130-Shakkhor
Programmer
Programmer

Course(s) :
  • BIT

Blood Group : B+
Posts : 209
Points : 328

View user profile

Back to top Go down

Re: দুটি মাইক্রোসফট্ ইন্টারভিউ প্রশ্ন

Post by BIT0122-Amit on Wed Jun 15, 2011 3:24 am

BTW, I won't say I gave it. Because I happen to read the same blog Rokon did :S Razz


_________________________________________________________________
Adminship / Moderatorship is not about power, it is about Responsibility.

|About me|My Blog|

BIT0122-Amit
Founder
Founder

Course(s) :
  • BIT

Blood Group : O+
Posts : 4187
Points : 6605

View user profile http://iitdu.forumsmotion.com

Back to top Go down

Re: দুটি মাইক্রোসফট্ ইন্টারভিউ প্রশ্ন

Post by BIT0112-Rokon on Wed Jun 15, 2011 11:35 pm

Most of the people agree with Amit's solution.SmileSmile

_________________________________________________________________


Code Explosion Blog | Code Explosion Wiki | The Rokonoid | নির্ঝরিণী

BIT0112-Rokon
Programmer
Programmer

Course(s) :
  • BIT

Blood Group : O+
Posts : 673
Points : 1269

View user profile http://blog.codexplo.org

Back to top Go down

Re: দুটি মাইক্রোসফট্ ইন্টারভিউ প্রশ্ন

Post by BIT0130-Shakkhor on Fri Jun 17, 2011 11:46 pm

Yes, but it's imperfect too. The solution holds if and only if you're given a stopwatch. For a mathematical problem, that's a lot to assume. Shocked

_________________________________________________________________
I'm not a driver with drinking problem.
I'm an alcoholic with driving problem.

Blog | বাংলা ব্লগ

BIT0130-Shakkhor
Programmer
Programmer

Course(s) :
  • BIT

Blood Group : B+
Posts : 209
Points : 328

View user profile

Back to top Go down

Re: দুটি মাইক্রোসফট্ ইন্টারভিউ প্রশ্ন

Post by BIT0220-Iftekhar on Sat Jun 18, 2011 12:14 am

Shakkhor ভায়া wrote:There is another soluiton. This one was proposed by Amit.

1 min por por 1ta idur re 1ta kore can theke food dite hobe, then time er track rakhte hobe. nth can ta poisoned hoile 14hr nth minute idur ta mara jabe.

For the given problem, this is a more elegant solution.
কিন্তু এতে সর্বনিম্ন কয়টা ইঁদুর লাগবে কিভাবে জানা যাবে?

এই নিয়মানুযায়ী আমার হিসাবে সর্বনিম্ন ইঁদুর র সংখ্যা দাঁড়াচ্ছে ৩০। কারণ সবগুলো ইঁদুর কে খাওয়াতে সময় লাগবে ৩০ মিনিট। এর মধ্যে কোনটাই মারা যাবে না। তাই ৩০ টা ইদুর-ই লাগবে।

BIT0220-Iftekhar
Administrator-RC

Course(s) :
  • BIT

Blood Group : B+
Posts : 434
Points : 630

View user profile http://iftekharunplugged.blogspot.com

Back to top Go down

Re: দুটি মাইক্রোসফট্ ইন্টারভিউ প্রশ্ন

Post by BIT0122-Amit on Sat Jun 18, 2011 2:03 am

লাগবে ১টাই।

সাক্ষর। সমস্যাটাই তো Imperfect. দুনিয়ার সব ইন্দুর জাত লিঙ্গ নির্বিশেষে ঠিক ১৪ ঘন্টায় মারা যাবে, এইটা কেমন কথা?

প্রশ্নটার উদ্দেশ্য mathematical বা programming skills খুঁজাখুঁজি করা না, বাক্সের বাইরে চিন্তা করতে পারে নাকি সেটা দেখা। Very Happy

_________________________________________________________________
Adminship / Moderatorship is not about power, it is about Responsibility.

|About me|My Blog|

BIT0122-Amit
Founder
Founder

Course(s) :
  • BIT

Blood Group : O+
Posts : 4187
Points : 6605

View user profile http://iitdu.forumsmotion.com

Back to top Go down

Re: দুটি মাইক্রোসফট্ ইন্টারভিউ প্রশ্ন

Post by BIT0220-Iftekhar on Sat Jun 18, 2011 3:19 am

BIT0122-Amit wrote:লাগবে ১টাই।
ধইন্যবাদ Very Happy
এতক্ষণে ধরতে পারলাম যে ১ মিনিট পর পর একই ইঁদুরকে খাওয়ানো হবে। Neutral

BIT0220-Iftekhar
Administrator-RC

Course(s) :
  • BIT

Blood Group : B+
Posts : 434
Points : 630

View user profile http://iftekharunplugged.blogspot.com

Back to top Go down

Re: দুটি মাইক্রোসফট্ ইন্টারভিউ প্রশ্ন

Post by BIT0122-Amit on Sat Jun 18, 2011 4:56 am

আচ্ছা, বরররে কেউ কিছু ধন্যবাদটাইপ কিছু দিলো না কেন?

গরর। আমিই দিলাম। rep++

_________________________________________________________________
Adminship / Moderatorship is not about power, it is about Responsibility.

|About me|My Blog|

BIT0122-Amit
Founder
Founder

Course(s) :
  • BIT

Blood Group : O+
Posts : 4187
Points : 6605

View user profile http://iitdu.forumsmotion.com

Back to top Go down

Re: দুটি মাইক্রোসফট্ ইন্টারভিউ প্রশ্ন

Post by Sponsored content Today at 11:23 pm


Sponsored content


Back to top Go down

View previous topic View next topic Back to top


 
Permissions in this forum:
You cannot reply to topics in this forum