সমস্যাঃ একটি পূর্ণসংখ্যার অ্যারেতে তিনটি করে সংখ্যা নিলে কতগুলো পৃথক ত্রয়ী পাওয়া যায়, যাদের যোগফল শূন্য (0) হবে?
যেমন, A = [-1, 0, 1, 2, -1, -4], দেওয়া থাকলে, সমাধান হচ্ছে, (-1, 0, 1) ও (-1, -1, 2). প্রতিটি ত্রয়ীর সংখ্যাগুলো ছোট থেকে বড় ক্রমে লিখতে হবে, মানে -1, 2, -1 লিখা যাবে না, বরং -1, -1, 2 লিখতে হবে।
সমাধানঃ সমস্যাটি খুব সহজেই তিনটি নেস্টেড লুপ ব্যবহার করে সমাধান করা যায়, সেক্ষেত্রে সমাধানের কমপ্লেক্সিট হয় O(n^3). ইন্টারভিউতে এই সমস্যা দিলে প্রথমেই এই কোড লেখা যাব না, বরং ইন্টারভিউয়ারকে জিজ্ঞাসা করতে হবে এবং আমার দৃঢ় বিশ্বাস, ইন্টারভিউয়ার এই সমাধানের কোড লিখে সময় নষ্ট করতে উৎসাহিত করবেন না, বরং কমপ্লেক্সিটি আরো কমাতে বলবেন।
আমরা যদি অ্যারেটি শুরুতেই সর্ট করে নিই, তাহলে সবচেয়ে ভেতরের লুপের বদলে বাইনারি সার্চ ব্যবহার করা যায়, এবং সেক্ষেত্রে কমপ্লেক্সিটি হয়, O(n^2 log n), যা O(n^3)-এর চেয়ে ভালো। কিন্তু সমস্যাটি O(n^2) কমপ্লেক্সিটিতেই সমাধান করা সম্ভব। আমি প্রথমেই বলব, পাঠককে একটু নিজে চেষ্টা করার জন্য। নিজে চেষ্টা করে নিচের যেকোনো একটি লিঙ্কে সমাধান করে যাচাই করা যাবে –
https://www.interviewbit.com/problems/3-sum-zero/
https://leetcode.com/problems/3sum/description/
আমি একটি নমুনা ইনপুট ও আউটপুট দিয়ে দিচ্ছি –
ইনপুট – A = [ 1, -4, 0, 0, 5, -5, 1, 0, -2, 4, -4, 1, -1, -4, 3, 4, -1, -1, -3]
আউটপুট – [[-5, 0, 5], [-5, 1, 4], [-4, -1, 5], [-4, 0, 4], [-4, 1, 3], [-3, -2, 5], [-3, -1, 4], [-3, 0, 3], [-2, -1, 3], [-2, 1, 1], [-1, 0, 1], [0, 0, 0]]
সমস্যাটি আমি আজকে সন্ধ্যায় সমাধান করেছি (আমি পাইথন ব্যবহার করেছি), কিন্তু পুরো সমাধান লিখে দিয়ে পাঠককে প্রোগ্রামিংয়ের আনন্দ থেকে বঞ্চিত করতে চাইছি না।
উল্লেখ্য যে, এই প্রশ্নটি গুগল ও ফেসবুকের ইন্টারভিউতে ইতিপূর্বে জিজ্ঞাসা করা হয়েছে।
