ত্রিভুজ গণনা – প্রোগ্রামিং ইন্টারভিউ সমস্যা ৪

সমস্যাঃ একটি ইন্টিজার অ্যারে দেওয়া আছে, যার সবগুলো সংখ্যাই ধনাত্মক। ওই অ্যারে থেকে তিনটি করে উপাদান নিয়ে মোট কয়টি ত্রিভুজ বানানো যায়, সেটি গণনা করতে হবে।

সমাধানঃ সমস্যাটি নিয়ে চিন্তা করার শুরুতেই একটি বিষয় মাথায় চলে আসবে, “ত্রিভুজের যেকোনো দুই বাহুর সমষ্টি তৃতীয় বাহু অপেক্ষা বৃহত্তর।” এই বিষয়টি কাজে লাগিয়ে আমরা সমস্যাটির সমাধান করতে পারি। আমাদের মূল কোড হবে নিচের মতো –

count = 0
for i in range(0, n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            if A[i] + A[j] > A[k]:
                count += 1

ইন্টারভিউতে অবশ্য একটি ফাংশন তৈরি করে তার ভেতরে মূল কোড লেখা উচিত, আমি সেটি আর দেখালাম না। এখন প্রশ্ন হচ্ছে, এই সমাধানের কমপ্লেক্সিটি কত? O(n^3)। এখন ইন্টারভিউয়ার জানতে চাইবেন, এর চেয়ে ভালোভাবে সমাধান করা সম্ভব কী না, এবং সম্ভব হলে চেষ্টা করতে।

ধরা যাক, মূল অ্যারেতে দেওয়া আছে 1, 1, 2, 3, 4। এখানে প্রতিবার তিনটি করে সংখ্যা নিলে আমরা পাই –

1, 1, 2
1, 1, 3
1, 1, 4
1, 2, 3
1, 2, 4
1, 3, 4
1, 2, 3
1, 2, 4
1, 3, 4
2, 3, 4

এগুলোর মধ্যে, কেবল 2, 3, 4 যখন একটি ত্রিভুজের বাহুর দৈর্ঘ্য হবে, তখন একটি ত্রিভুজ তৈরি করা যাবে। কারণ, 2 + 3  > 4। বাকীগুলোর জন্য a + b > c সত্য নয় (এখানে a, b, c হচ্ছে যথাক্রমে ত্রিভুজের প্রথম, দ্বিতীয় ও তৃতীয় বাহু)। আর সংখ্যাগুলো যেহেতু ছোট থেকে বড় ক্রমে সাজানো, তাই a + b > c পরীক্ষা করলেই হবে, b + c > a, c + a > b এগুলো পরীক্ষা করার দরকার নেই।

এখন প্রশ্ন হচ্ছে, আমাদেরকে যেই অ্যারে দেওয়া আছে, সেটিতো ছোট থেকে বড় ক্রমে সাজানো নেই। তাই প্রথমে আমরা সেটি সর্ট করে নেবো। এই কাজটি করার কমপ্লেক্সিটি হচ্ছে O(n log n), যা O(n^3)-এর চেয়ে অনেক ছোটো। তাহলে প্রথমে আমরা অ্যারেটি সর্ট করে নেবো।

ধরা যাক, অ্যারে A-তে আছে দশটি সংখ্যা – 10, 11, 12, 13, 14, 15, 16, 20, 21, 22। এখন, i-এর মান 0, j-এর মান 1 হলে, k-এর মান 2 থেকে 7 পর্যন্ত প্রতিটির জন্যই A[i] + A[j] > A[k] শর্তটি সত্য হবে, অর্থাৎ A[i], A[j], A[k] ত্রিভুজের তিনটি বাহু হিসেবে ব্যবহার করা যাবে। আর মোট ত্রিভুজ কয়টি হবে? 7 – 1 বা 6টি।

এখন, i-এর মান 0, j-এর মান 2 এর জন্য কিন্তু আর k-এর মান 2 থেকে পরীক্ষা করার দরকার নেই, কারণ k-এর মান 7 পর্যন্ত অবশ্যই A[i] + A[j] > A[k] সত্য হবে, কারণ A[0] + A[1] এর মান অবশ্যই A[0] + A[2] এর মানের  চেয়ে ছোট বা সমান। তাই আমরা k-এর মান আগের চেয়ে এক এক করে বাড়িয়ে পরীক্ষা করবো।

তাহলে, i-এর যেকোনো মানের জন্য, j-এর মান i+1 এবং k-এর মান i+2 থেকে আমরা লুপ শুরু করবো। আর j-এর মান যখন বাড়বে, তখন কিন্তু আবার k-এর মান i+2 থেকে শুরু করবো না, বরং আগে k-এর মান যা ছিল, সেখান থেকেই শুরু হবে।

count = 0
for i in range(n - 2):
    k = i + 2
    for j in range(i + 1, n - 1):
        while k < n and A[i] + A[j] > A[k]:
            k += 1
        count = count + k - j - 1

ওপরের কোড-এর কমপ্লেক্সিটি কত? যারা একটু কম চিন্তা করবে, তারা হুট করে বলে দিবে O(n^3), কারণ তিনটি নেস্টেড লুপ আছে। কিন্তু একটু ভালোভাবে লক্ষ করলে দেখা যাবে যে, j-এর লুপের জন্য ভেতরের লুপটি আর নতুন করে শুরু হচ্ছে না, k-এর আগের মান থেকেই শুরু হচ্ছে। না বুঝলে খাতা কলম নিয়ে বসতে হবে। তাই সবচেয়ে বাইরের লুপ (i-এর লুপ)-এর জন্য ভেতরে j ও k-এর লুপ প্রতিটি সর্বোচ্চ n সংখ্যকবার চলবে (মোট, n + n = 2n)। তাই কমপ্লেক্সিটি হচ্ছে, n * 2n, বা 2 * n^2, বা, O(n^2).

কেউ চাইলে নিচের যেকোনো একটি সমস্যা সমাধানের চেষ্টা করতে পারে

1) https://leetcode.com/problems/valid-triangle-number/

2) https://www.interviewbit.com/problems/counting-triangles

স্ট্যাক দিয়ে কিউ তৈরি – প্রোগ্রামিং ইন্টারভিউ সমস্যা ৩

সমস্যাঃ স্ট্যাক (Stack) ব্যবহার করে কিউ (Queue) তৈরি করতে হবে, অর্থাৎ কিউ এর এনকিউ (enqueue) ও ডিকিউ (dequeue) ফাংশন তৈরি করতে হবে।

সমাধানঃ প্রথমে একটু চিন্তা করলেই আমরা বুঝতে পারবো যে একটি স্ট্যাক দিয়ে আসলে একটি কিউ তৈরি করা সম্ভব নয়। যদি সম্ভব হতো, তাহলে এই দুটি আলাদা ডেটা স্ট্রাকচার হতো না। কিন্তু যেহেতু সমস্যা দেওয়া হয়েছে, সমাধান নিশ্চয়ই আছে। সমাধান হচ্ছে, দুটি স্ট্যাক ব্যবহার করা।

নোটঃ স্ট্যাক ও কিউ নিয়ে আমি বিস্তারিত আলোচনা করেছি, কম্পিউটার প্রোগ্রামিং ৩য় খণ্ড – ডেটা স্ট্রাকচার ও অ্যালগরিদম পরিচিতি এবং পাইথন দিয়ে প্রোগ্রামিং শেখা ৩য় খণ্ড – ডেটা স্ট্রাকচার ও অ্যালগরিদম পরিচিতি বইতে। এছাড়া ইউটিউবেও এ বিষয়ে আলোচনা  করেছি ডেটা স্ট্রাকচার ও অ্যালগরিদম প্লেলিস্টে

ধরা যাক, কিউতে প্রথমে আমি পাঁচটি সংখ্যা রাখতে চাই, অর্থাৎ enqueue অপারেশন হবে পাঁচবার এবং সংখ্যাগুলো হচ্ছে – 1, 2, 3, 4, 5. আমি এগুলো প্রথম স্ট্যাকে পুশ (push) করব।

এখন আমি চাই, কিউ থেকে প্রথম তিনটি সংখ্যা সরিয়ে ফেলতে, অর্থাৎ তিনবার dequeue অপারেশন হবে। তাহলে কিউ থেকে যথাক্রমে 1, 2, 3 – এই তিনটি সংখ্যা চলে যাবে। কিন্তু স্ট্যাক থেকে তো কেবল ওপরের সংখ্যাটি সরানো যায়। তাহলে, আমি প্রথম স্ট্যাকের সবগুলো সংখ্যা দ্বিতীয় স্ট্যাকে নিয়ে আসব। তখন স্ট্যাকগুলোর অবস্থা হবে নিচের ছবির মতো –

এখন আমি দ্বিতীয় স্ট্যাকে তিনবার পপ (pop) অপারেশন চালালে 1, 2, 3 স্ট্যাক থেকে চলে যাবে। তখন স্ট্যাকদুটির অবস্থা হবে নিচের ছবির মতো –

এখন আমি কিউতে 6 ও 7 ক্রমানুসারে রাখতে চাই। আমি সেগুলো প্রথম স্ট্যাকে পুশ করবো।

এখন কিউ-এর অবস্থা হচ্ছে এমন: 4, 5, 6, 7. আমি যদি কিউ থেকে তিনটি সংখ্যা সরিয়ে নিই (অর্থাৎ তিনবার ডিকিউ করি), সেগুলো হবে, যথাক্রমে 4, 5, 6। ডিকিউ করার জন্য আমি প্রথমে দেখবো যে দ্বিতীয় স্ট্যাকে কিছু আছে কী না। যদি থাকে, সেই স্ট্যাক থেকে পপ করবো। আর যদি stack2 খালি থাকে, তাহলে Stack1-এর সব কিছু Stack2-তে নিয়ে আসবো (তখন দ্বিতীয় স্ট্যাকে সেগুলো প্রথম স্ট্যাকের বিপরীত ক্রমে থাকবে)। তারপরে দ্বিতীয় স্ট্যাক থেকে পপ করবো।

আশা করি, সমাধানটি নিজের পছন্দমতো প্রোগ্রামিং ভাষায় ইমপ্লিমেন্ট করতে সমস্যা হবে না। সমাধান সঠিক হলো কী না, তা যাচাই করার জন্য নিচের যেকোনো একটি লিঙ্কে গিয়ে সমাধান জমা দিলেই হবে –