দৈনিক কোডিং সমস্যা 24  অন্য সমস্যা সমাধানের সাথে আবার স্বাগতম! আজ, আমরা এই সত্যিই চমৎকার সমস্যাটির সাথে ছাদ থেকে পড়ে যাওয়া ডিম নিয়ে কাজ করছি, যার দুটি সম্ভাব্য সমাধান জড়িত থাকবে: একটি সুন্দর সরল এবং আরেকটি চতুর। এই শেষটি আমাদের একটি বেশ বিখ্যাত অ্যালগরিদম সম্পর্কে কথা বলার সুযোগ দেবে।  বরাবরের মতো, আজকের সমস্যাটি চমৎকার নিউজলেটার দ্বারা সরবরাহ করা হয়েছে  , যা আপনি আপনার দৈনিক কোডিং চ্যালেঞ্জ পেতে বিনামূল্যে সদস্যতা নিতে পারেন। এটি পরীক্ষা করে দেখুন, এবং আপনার সমস্যাগুলিও সমাধান করার চেষ্টা করুন!   দৈনিক কোডিং সমস্যা  তখন কথা বলা যথেষ্ট; এর সমস্যা দেখা যাক!  সমস্যাটি  এই সমস্যাটি একটি চাকরির সাক্ষাত্কারে গোল্ডম্যান শ্যাক্স দ্বারা জিজ্ঞাসা করা হয়েছিল। চলুন সমস্যা দেখা যাক.      অভিন্ন ডিম দেওয়া হয়েছে এবং   মেঝে সহ একটি বিল্ডিংয়ে প্রবেশাধিকার দেওয়া হয়েছে। আপনার কাজ হল সবচেয়ে নীচের তলটি খুঁজে বের করা যা একটি ডিম ভেঙ্গে ফেলবে, যদি সেই তল থেকে পড়ে যায়। ডিম একবার ভেঙ্গে গেলে আর ফেলা যায় না।   তলা থেকে নামলে ডিম ভেঙ্গে গেলে,   এর চেয়ে বড় যে কোনো ফ্লোর থেকে নামলে ডিম ভেঙ্গে যাবে বলে ধরে নিতে পারেন। আপনাকে N k xth x   একটি অ্যালগরিদম লিখুন যা ন্যূনতম সংখ্যক ট্রায়াল ড্রপ খুঁজে বের করে, সবচেয়ে খারাপ ক্ষেত্রে, এই ফ্লোরটি সনাক্ত করতে।      এবং   হয়, তাহলে আমাদের প্রতিটি তলায় ডিমটি ফেলে দেওয়ার চেষ্টা করতে হবে, প্রথম থেকে শুরু করে, যতক্ষণ না আমরা পঞ্চম তলায় পৌঁছাই, তাই আমাদের সমাধান হবে   । উদাহরণস্বরূপ, যদি N = 1 k = 5 5  সুতরাং, একটি বিল্ডিংয়ের বিভিন্ন তলা থেকে আমাদের কিছু ডিম নিক্ষেপ করা হয়। আমরা দুঃখিত যে একটি নির্দিষ্ট ফ্লোর থেকে (যাকে আমরা   বলব), ফেলে দেওয়া ডিম মাটিতে পড়ে গেলে ভেঙে যায় না। targetFloor  সেই মেঝে থেকে নীচের প্রতিটি তলায়, জানালা থেকে ফেলে দিলে ডিম ভাঙবে না। আমাদের যা করতে বলা হয়েছে তা হল   খুঁজে বের করার জন্য একটি কার্যকর পদ্ধতি খুঁজে বের করা। targetFloor  প্রত্যাশিত হিসাবে, আমরা এটি সমাধান করার জন্য দুটি পদ্ধতি দেখতে পাব: একটি সত্যিই সহজ, যা সমাধানটিকে জবরদস্ত করবে, কিন্তু এটি কার্যকর হবে না। দ্বিতীয়টি অনেক বেশি দক্ষ হবে এবং সর্বনিম্ন সংখ্যক ধাপ ভেঙে সমস্যা সমাধানের চেষ্টা করবে।  এটি আমাদের একটি সত্যিই বিখ্যাত এবং গুরুত্বপূর্ণ অ্যালগরিদম সম্পর্কে কথা বলার সুযোগ দেবে; যেগুলির মধ্যে একটি আপনাকে করতে জানতে হবে … মূলত কিছু!  পরিবেশ স্থাপন করা  শুরু করার জন্য, আমাদের বিল্ডিং এবং   নামক পরিবেশের একটি বিট সেট আপ করতে হবে। বিল্ডিং তৈরি করার জন্য, আমরা কেবল মেঝের সংখ্যা সম্বলিত একটি অ্যারে তৈরি করি, নিচতলা থেকে nᵗʰ ফ্লোর পর্যন্ত। তারপরে, আমরা একটি র্যান্ডম সংখ্যা তৈরি করি যা হবে আমাদের   । targetFloor targetFloor  আমরা গো-তে এই সমস্যাটি আবার লিখব: পঠনযোগ্য হওয়ার জন্য যথেষ্ট সহজ, কিন্তু অভ্যন্তরীণ মেকানিক্স বোঝার জন্য যথেষ্ট জটিল।   https://gist.github.com/NicolaM94/85ae34f01e7de8cd00264276b385e137?embedable=true#file-main-go  আমরা প্রথমে অ্যারে তৈরি করি যা আমাদের বিল্ডিং হিসাবে কাজ করবে: আমরা এটিকে আমাদের ইচ্ছামত আকার দিতে পারি, আকার যত বড় হবে, বিল্ডিং তত বেশি হবে। এর পরে, আমরা Go-তে নির্মিত   মডিউল ব্যবহার করে   একটি উদাহরণ তৈরি করি। math/rand targetFlor  মূলত, আমরা বর্তমান সময়কে উৎস হিসেবে ব্যবহার করে 0 এবং বিল্ডিংয়ের উচ্চতা (... অ্যারের দৈর্ঘ্য :D) এর মধ্যে একটি নতুন র্যান্ডম পূর্ণসংখ্যা তৈরি করি।  ব্রুট ফোর্স সলিউশন  অবশ্যই, সবচেয়ে সহজ সমাধান হতে পারে প্রতিটি ডিম প্রতিটি তলায় ফেলে দেওয়া, যাতে ডিমগুলি কোন তলায় ভাঙতে শুরু করে তা দেখতে। যেহেতু আমাদের কাছে সেই তথ্য সম্বলিত একটি ভেরিয়েবল আছে, তাই সমস্যাটি সমাধানের জন্য কেউ কেবল একটি লুপ করতে পারে:   https://gist.github.com/NicolaM94/dd49b3b44a8938c40d0539512fd613cb?embedable=true#file-main-go  যদিও এটি সবচেয়ে সহজ সমাধান, এটি দুর্ভাগ্যবশত অত্যন্ত অদক্ষ। কল্পনা করুন যদি ডান তলটি উপরেরটি হয়: সমস্যা সমাধানের জন্য একজনকে অবশ্যই 100.000 ডিম ভাঙতে হবে: এটি একটি বিশাল অমলেট তবে বেশ অপচয় হবে!  সাধারণভাবে বলতে গেলে, এই সমাধানটিতে O(n) এর একটি সময় জটিলতা রয়েছে কারণ সমাধানের জটিলতা ইনপুট সমস্যার জটিলতার সাথে রৈখিকভাবে বৃদ্ধি পায়। যদিও আমরা ভাবতে পারি এটি সবচেয়ে কার্যকরী সমাধান নয়।  একটি দক্ষ সমাধান  আসুন তাহলে একটি কার্যকর সমাধান সম্পর্কে চিন্তা করা যাক। প্রতিটি ফ্লোরে প্রতিটি ডিম ভেঙে মেঝেতে হাঁটার পরিবর্তে, আমরা একটি অনুমান নিতে পারি এবং সেই অনুমানের ফলাফলের উপর ভিত্তি করে পরবর্তী অনুমানটি সামঞ্জস্য করতে পারি।  এখানে একটি উদাহরণ: ধরুন আমাদের 10 তলা বিশিষ্ট একটি বিল্ডিং আছে, এবং   হল 7 তলা (আমরা তা জানি না, অবশ্যই)। আমরা নিম্নলিখিত অনুমান নিতে পারি:  targetFloor  মূলত, আমরা অনুমান করি যে   হল বিল্ডিংয়ের মাঝখানের ফ্লোর। আমরা সেখান থেকে ডিম নিক্ষেপ করি এবং সম্ভাব্য ফলাফল দুটি: targetFloor  ডিম ভেঙ্গে যায়, যার মানে আমরা খুব বেশি। আমরা এর থেকে উঁচু মেঝেটি বাদ দিতে পারি, অন্তর্ভুক্ত করে, এবং আমাদের অনুমান ধরে চালিয়ে যেতে পারি।  ডিম ভাঙ্গে না, মানে আমরা খুব কম বা সঠিক মেঝেতে আছি। আমরা এই একের চেয়ে নীচের প্রতিটি তল বাতিল করি, অন্তর্ভুক্ত, এবং  এর পরিপ্রেক্ষিতে, আমরা এখন মধ্যম তল বা "বাকি" বিল্ডিং সম্পর্কে আরেকটি শিক্ষিত অনুমান করি এবং উপরে দেখা একই কৌশল প্রয়োগ করি। আমরা এই পদ্ধতির সাথে যেতে পারি যতক্ষণ না আমাদের এক তলা বাকি থাকে।  আপনি যদি এই পদ্ধতিটি চিনতে পারেন তবে আপনি পুরোপুরি সঠিক: এটি একটি "বাস্তব বিশ্বের" সমস্যায় প্রয়োগ করা একটি   । বাইনারি সার্চ হল একটি সহজ এবং পরিষ্কার   অ্যালগরিদম, যার অর্থ হল প্রতিটি ধাপে সমস্যার আকার অর্ধেক হয়ে যায় যতক্ষণ না আমরা সমাধান খুঁজে পাচ্ছি। বাইনারি অনুসন্ধান ডিভাইড-এন্ড-কনকার  এর মানে হল এই অ্যালগরিদম, আগের একের তুলনায়, দ্রুততর। চলুন কোড দেখি!   https://gist.github.com/NicolaM94/79d625ecef07cb26a7a8d9bcdb6143fd?embedable=true#file-main-go  এর একটি গভীর কটাক্ষপাত করা যাক. বাইনারি অনুসন্ধান ফাংশন 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)  এর মানে হল এই অ্যালগরিদমের সময় জটিলতা হল   । রৈখিক সমাধান এবং এই শেষের মধ্যে কিছু তুলনা করার জন্য, যদি বিল্ডিংটিতে 100টি ফ্লোর থাকে, তবে লিনিয়ার অ্যালগরিদম সবচেয়ে খারাপ ক্ষেত্রে 100টি পুনরাবৃত্তি নেয়, যখন বাইনারি অনুসন্ধান অ্যালগরিদম log₂100 = 6.64 নেয়, তাই 7টি পুনরাবৃত্তি। O(log(n))  এছাড়াও, এই শেষটি রৈখিকটির চেয়ে ক্রমবর্ধমান বেশি দক্ষ কারণ বিল্ডিং যত বেশি বৃদ্ধি পাবে, বাইনারি অনুসন্ধান তত বেশি কার্যকর হবে। 1.000.000.000 তলা বিশিষ্ট একটি বিল্ডিংয়ের জন্য, রৈখিকটি 1.000.000.000 পদক্ষেপ নেয়, যখন বাইনারিটি log₂1.000.000.000 = 29.9, তাই 30টি পদক্ষেপ নেয়৷ একটি বিশাল উন্নতি!   উপসংহার  এই হল! আমি আশা করি আপনি নিবন্ধটি উপভোগ করেছেন যতটা আমি চ্যালেঞ্জ সমাধান করার চেষ্টা করে মজা পেয়েছি! যদি তাই হয়, দয়া করে একটি বা দুটি হাততালি ছেড়ে দিন, এটি একটি দুর্দান্ত সমর্থন হবে! আপনি যদি এই ধরনের নিবন্ধ পছন্দ করেন এবং আরও দেখতে চান, পৃষ্ঠাটি অনুসরণ করুন কারণ আমি যতবার পারি এই ধরনের সামগ্রী প্রকাশ করি।  পরিশেষে, আপনি যদি এই নিবন্ধটিকে আকর্ষণীয় বা সহায়ক বলে মনে করেন এবং একটি কফি অফার করে অবদান রাখতে চান, তাহলে নির্দ্বিধায় তা করতে পারেন আমার  পাতা!   কো-ফাই  এবং, সবসময় হিসাবে, পড়ার জন্য ধন্যবাদ!   নিকোলা   এছাড়াও   প্রকাশিত এখানে

Read My Stories

গল্পের মূল ভাষায় এই অডিও তৈরি!

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

About Author

মন্তব্য

আসে ট্যাগ

এই নিবন্ধটি উপস্থাপন করা হয়েছে

Related Stories

কিভাবে 10X দ্বারা আপনার কর্মপ্রবাহ উন্নত করবেন: 17টি প্রয়োজনীয় অ্যাপ

ফোরাম থেকে ফিড পর্যন্ত: কীভাবে সোশ্যাল মিডিয়া অ্যালগরিদম ডিজিটাল ইন্টারঅ্যাকশনকে আকার দেয়

বোল্টজম্যান ব্রেন থিওরির একটি সংক্ষিপ্ত ভূমিকা

সফল ক্লাউড মাইগ্রেশনের সম্পূর্ণ নির্দেশিকা: কৌশল এবং সর্বোত্তম অনুশীলন

কিভাবে 10X দ্বারা আপনার কর্মপ্রবাহ উন্নত করবেন: 17টি প্রয়োজনীয় অ্যাপ

ফোরাম থেকে ফিড পর্যন্ত: কীভাবে সোশ্যাল মিডিয়া অ্যালগরিদম ডিজিটাল ইন্টারঅ্যাকশনকে আকার দেয়

বোল্টজম্যান ব্রেন থিওরির একটি সংক্ষিপ্ত ভূমিকা

সফল ক্লাউড মাইগ্রেশনের সম্পূর্ণ নির্দেশিকা: কৌশল এবং সর্বোত্তম অনুশীলন

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps