যখন আপনাকে ছাদ থেকে ডিম ছুঁড়তে হবে: দৈনিক কোডিং সমস্যা

দৈনিক কোডিং সমস্যা 24

অন্য সমস্যা সমাধানের সাথে আবার স্বাগতম! আজ, আমরা এই সত্যিই চমৎকার সমস্যাটির সাথে ছাদ থেকে পড়ে যাওয়া ডিম নিয়ে কাজ করছি, যার দুটি সম্ভাব্য সমাধান জড়িত থাকবে: একটি সুন্দর সরল এবং আরেকটি চতুর। এই শেষটি আমাদের একটি বেশ বিখ্যাত অ্যালগরিদম সম্পর্কে কথা বলার সুযোগ দেবে।

বরাবরের মতো, আজকের সমস্যাটি চমৎকার নিউজলেটার দ্বারা সরবরাহ করা হয়েছে দৈনিক কোডিং সমস্যা , যা আপনি আপনার দৈনিক কোডিং চ্যালেঞ্জ পেতে বিনামূল্যে সদস্যতা নিতে পারেন। এটি পরীক্ষা করে দেখুন, এবং আপনার সমস্যাগুলিও সমাধান করার চেষ্টা করুন!

তখন কথা বলা যথেষ্ট; এর সমস্যা দেখা যাক!

সমস্যাটি

এই সমস্যাটি একটি চাকরির সাক্ষাত্কারে গোল্ডম্যান শ্যাক্স দ্বারা জিজ্ঞাসা করা হয়েছিল। চলুন সমস্যা দেখা যাক.

আপনাকে N অভিন্ন ডিম দেওয়া হয়েছে এবং k মেঝে সহ একটি বিল্ডিংয়ে প্রবেশাধিকার দেওয়া হয়েছে। আপনার কাজ হল সবচেয়ে নীচের তলটি খুঁজে বের করা যা একটি ডিম ভেঙ্গে ফেলবে, যদি সেই তল থেকে পড়ে যায়। ডিম একবার ভেঙ্গে গেলে আর ফেলা যায় না। xth তলা থেকে নামলে ডিম ভেঙ্গে গেলে, x এর চেয়ে বড় যে কোনো ফ্লোর থেকে নামলে ডিম ভেঙ্গে যাবে বলে ধরে নিতে পারেন।

একটি অ্যালগরিদম লিখুন যা ন্যূনতম সংখ্যক ট্রায়াল ড্রপ খুঁজে বের করে, সবচেয়ে খারাপ ক্ষেত্রে, এই ফ্লোরটি সনাক্ত করতে।

উদাহরণস্বরূপ, যদি N = 1 এবং k = 5 হয়, তাহলে আমাদের প্রতিটি তলায় ডিমটি ফেলে দেওয়ার চেষ্টা করতে হবে, প্রথম থেকে শুরু করে, যতক্ষণ না আমরা পঞ্চম তলায় পৌঁছাই, তাই আমাদের সমাধান হবে 5 ।

সুতরাং, একটি বিল্ডিংয়ের বিভিন্ন তলা থেকে আমাদের কিছু ডিম নিক্ষেপ করা হয়। আমরা দুঃখিত যে একটি নির্দিষ্ট ফ্লোর থেকে (যাকে আমরা targetFloor বলব), ফেলে দেওয়া ডিম মাটিতে পড়ে গেলে ভেঙে যায় না।

সেই মেঝে থেকে নীচের প্রতিটি তলায়, জানালা থেকে ফেলে দিলে ডিম ভাঙবে না। আমাদের যা করতে বলা হয়েছে তা হল targetFloor খুঁজে বের করার জন্য একটি কার্যকর পদ্ধতি খুঁজে বের করা।

প্রত্যাশিত হিসাবে, আমরা এটি সমাধান করার জন্য দুটি পদ্ধতি দেখতে পাব: একটি সত্যিই সহজ, যা সমাধানটিকে জবরদস্ত করবে, কিন্তু এটি কার্যকর হবে না। দ্বিতীয়টি অনেক বেশি দক্ষ হবে এবং সর্বনিম্ন সংখ্যক ধাপ ভেঙে সমস্যা সমাধানের চেষ্টা করবে।

এটি আমাদের একটি সত্যিই বিখ্যাত এবং গুরুত্বপূর্ণ অ্যালগরিদম সম্পর্কে কথা বলার সুযোগ দেবে; যেগুলির মধ্যে একটি আপনাকে করতে জানতে হবে … মূলত কিছু!

পরিবেশ স্থাপন করা

শুরু করার জন্য, আমাদের বিল্ডিং এবং targetFloor নামক পরিবেশের একটি বিট সেট আপ করতে হবে। বিল্ডিং তৈরি করার জন্য, আমরা কেবল মেঝের সংখ্যা সম্বলিত একটি অ্যারে তৈরি করি, নিচতলা থেকে nᵗʰ ফ্লোর পর্যন্ত। তারপরে, আমরা একটি র্যান্ডম সংখ্যা তৈরি করি যা হবে আমাদের targetFloor ।

আমরা গো-তে এই সমস্যাটি আবার লিখব: পঠনযোগ্য হওয়ার জন্য যথেষ্ট সহজ, কিন্তু অভ্যন্তরীণ মেকানিক্স বোঝার জন্য যথেষ্ট জটিল।

আমরা প্রথমে অ্যারে তৈরি করি যা আমাদের বিল্ডিং হিসাবে কাজ করবে: আমরা এটিকে আমাদের ইচ্ছামত আকার দিতে পারি, আকার যত বড় হবে, বিল্ডিং তত বেশি হবে। এর পরে, আমরা Go-তে নির্মিত math/rand মডিউল ব্যবহার করে targetFlor একটি উদাহরণ তৈরি করি।

মূলত, আমরা বর্তমান সময়কে উৎস হিসেবে ব্যবহার করে 0 এবং বিল্ডিংয়ের উচ্চতা (... অ্যারের দৈর্ঘ্য :D) এর মধ্যে একটি নতুন র্যান্ডম পূর্ণসংখ্যা তৈরি করি।

ব্রুট ফোর্স সলিউশন

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

যদিও এটি সবচেয়ে সহজ সমাধান, এটি দুর্ভাগ্যবশত অত্যন্ত অদক্ষ। কল্পনা করুন যদি ডান তলটি উপরেরটি হয়: সমস্যা সমাধানের জন্য একজনকে অবশ্যই 100.000 ডিম ভাঙতে হবে: এটি একটি বিশাল অমলেট তবে বেশ অপচয় হবে!

সাধারণভাবে বলতে গেলে, এই সমাধানটিতে O(n) এর একটি সময় জটিলতা রয়েছে কারণ সমাধানের জটিলতা ইনপুট সমস্যার জটিলতার সাথে রৈখিকভাবে বৃদ্ধি পায়। যদিও আমরা ভাবতে পারি এটি সবচেয়ে কার্যকরী সমাধান নয়।

একটি দক্ষ সমাধান

আসুন তাহলে একটি কার্যকর সমাধান সম্পর্কে চিন্তা করা যাক। প্রতিটি ফ্লোরে প্রতিটি ডিম ভেঙে মেঝেতে হাঁটার পরিবর্তে, আমরা একটি অনুমান নিতে পারি এবং সেই অনুমানের ফলাফলের উপর ভিত্তি করে পরবর্তী অনুমানটি সামঞ্জস্য করতে পারি।

এখানে একটি উদাহরণ: ধরুন আমাদের 10 তলা বিশিষ্ট একটি বিল্ডিং আছে, এবং targetFloor হল 7 তলা (আমরা তা জানি না, অবশ্যই)। আমরা নিম্নলিখিত অনুমান নিতে পারি:

মূলত, আমরা অনুমান করি যে targetFloor হল বিল্ডিংয়ের মাঝখানের ফ্লোর। আমরা সেখান থেকে ডিম নিক্ষেপ করি এবং সম্ভাব্য ফলাফল দুটি:

• ডিম ভেঙ্গে যায়, যার মানে আমরা খুব বেশি। আমরা এর থেকে উঁচু মেঝেটি বাদ দিতে পারি, অন্তর্ভুক্ত করে, এবং আমাদের অনুমান ধরে চালিয়ে যেতে পারি।

• ডিম ভাঙ্গে না, মানে আমরা খুব কম বা সঠিক মেঝেতে আছি। আমরা এই একের চেয়ে নীচের প্রতিটি তল বাতিল করি, অন্তর্ভুক্ত, এবং

এর পরিপ্রেক্ষিতে, আমরা এখন মধ্যম তল বা "বাকি" বিল্ডিং সম্পর্কে আরেকটি শিক্ষিত অনুমান করি এবং উপরে দেখা একই কৌশল প্রয়োগ করি। আমরা এই পদ্ধতির সাথে যেতে পারি যতক্ষণ না আমাদের এক তলা বাকি থাকে।

আপনি যদি এই পদ্ধতিটি চিনতে পারেন তবে আপনি পুরোপুরি সঠিক: এটি একটি "বাস্তব বিশ্বের" সমস্যায় প্রয়োগ করা একটি বাইনারি অনুসন্ধান । বাইনারি সার্চ হল একটি সহজ এবং পরিষ্কার ডিভাইড-এন্ড-কনকার অ্যালগরিদম, যার অর্থ হল প্রতিটি ধাপে সমস্যার আকার অর্ধেক হয়ে যায় যতক্ষণ না আমরা সমাধান খুঁজে পাচ্ছি।

এর মানে হল এই অ্যালগরিদম, আগের একের তুলনায়, দ্রুততর। চলুন কোড দেখি!

এর একটি গভীর কটাক্ষপাত করা যাক. বাইনারি অনুসন্ধান ফাংশন 4 টি আর্গুমেন্ট নেয়:

• overArray , পূর্ণসংখ্যার একটি অ্যারে, যা আমরা যে বিল্ডিংটি লুপ করছি;

• bottom , বিল্ডিংয়ের নীচের সূচক;

• top , বিল্ডিং এর উপরের তলার সূচক;

• breakFloor , ভ্যারিয়েবল হোল্ডিং targetFloor আমরা বিল্ডিং এ খুঁজে পেতে পারি কিনা তা পরীক্ষা করতে।

এর পরে, আমরা বিল্ডিংয়ের উপর লুপ করি যখন bottom top থেকে নীচে থাকে: বাইনারি অনুসন্ধানে, যখন দুটি অবস্থানগত আর্গুমেন্ট ইন্টারলেস এবং অদলবদল করে, এর মানে অনুসন্ধান করা উপাদানটি পাওয়া যায়নি।

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

আমরা middlePoint এলিমেন্টটিকে bottom এবং top মধ্যে মেঝে হিসাবে গণনা করি এবং আমরা middlePoint == breakFloor কিনা তা পরীক্ষা করি। যদি এটি হয়, আমরা ফলাফল হিসাবে middlePoint ফিরিয়ে দিই।

যদি তা না হয়, আমরা সেই অনুযায়ী bottom বা top সামঞ্জস্য করি: যদি middlePoint breakFloor চেয়ে বড় হয়, তাহলে এর মানে হল আমরা বিল্ডিংয়ে খুব বেশি তাই আমরা top সম্ভাব্য ফ্লোরটিকে middlePoint — 1 এ সেট করে আমাদের পূর্বাভাস কমিয়ে দিই।

middlePoint breakFloor চেয়ে ছোট হলে, আমরা middlePoint+1 হিসাবে সেট করে আমাদের bottom সামঞ্জস্য করি।

এখন সবকিছু পরীক্ষা করার জন্য, main ফাংশনে, আমরা আগের মতো পরিবেশ তৈরি করি এবং bsFloor নামে একটি নতুন ভেরিয়েবল তৈরি করি যা আমাদের ফলাফল ধরে রাখবে।

আমাদের অ্যালগরিদম আমাদের সঠিক ফলাফলে নিয়ে এসেছে তা নিশ্চিত করতে, আমরা bsFloor এবং targetFloor উভয়ই প্রিন্ট আউট করি, যা আগে এলোমেলোভাবে তৈরি করা হয়েছিল।

সময় জটিলতা

আমরা আগে প্রত্যাশিত হিসাবে, এই অ্যালগরিদম রৈখিক এক তুলনায় উপায় দ্রুত. যেহেতু আমরা প্রতিটি ধাপে বিল্ডিংকে অর্ধেক করে ফেলি, তাই আমরা log₂(n) এ সঠিক মেঝে খুঁজে পেতে পারি যেখানে n len(building) এর সমান।

এর মানে হল এই অ্যালগরিদমের সময় জটিলতা হল O(log(n)) । রৈখিক সমাধান এবং এই শেষের মধ্যে কিছু তুলনা করার জন্য, যদি বিল্ডিংটিতে 100টি ফ্লোর থাকে, তবে লিনিয়ার অ্যালগরিদম সবচেয়ে খারাপ ক্ষেত্রে 100টি পুনরাবৃত্তি নেয়, যখন বাইনারি অনুসন্ধান অ্যালগরিদম log₂100 = 6.64 নেয়, তাই 7টি পুনরাবৃত্তি।

এছাড়াও, এই শেষটি রৈখিকটির চেয়ে ক্রমবর্ধমান বেশি দক্ষ কারণ বিল্ডিং যত বেশি বৃদ্ধি পাবে, বাইনারি অনুসন্ধান তত বেশি কার্যকর হবে। 1.000.000.000 তলা বিশিষ্ট একটি বিল্ডিংয়ের জন্য, রৈখিকটি 1.000.000.000 পদক্ষেপ নেয়, যখন বাইনারিটি log₂1.000.000.000 = 29.9, তাই 30টি পদক্ষেপ নেয়৷ একটি বিশাল উন্নতি!

উপসংহার

এই হল! আমি আশা করি আপনি নিবন্ধটি উপভোগ করেছেন যতটা আমি চ্যালেঞ্জ সমাধান করার চেষ্টা করে মজা পেয়েছি! যদি তাই হয়, দয়া করে একটি বা দুটি হাততালি ছেড়ে দিন, এটি একটি দুর্দান্ত সমর্থন হবে! আপনি যদি এই ধরনের নিবন্ধ পছন্দ করেন এবং আরও দেখতে চান, পৃষ্ঠাটি অনুসরণ করুন কারণ আমি যতবার পারি এই ধরনের সামগ্রী প্রকাশ করি।

পরিশেষে, আপনি যদি এই নিবন্ধটিকে আকর্ষণীয় বা সহায়ক বলে মনে করেন এবং একটি কফি অফার করে অবদান রাখতে চান, তাহলে নির্দ্বিধায় তা করতে পারেন আমার কো-ফাই পাতা!

এবং, সবসময় হিসাবে, পড়ার জন্য ধন্যবাদ!

নিকোলা

এছাড়াও এখানে প্রকাশিত