যোগফল শূন্য – প্রোগ্রামিং ইন্টারভিউ সমস্যা ৬

সমস্যাঃ একটি পূর্ণসংখ্যার অ্যারেতে তিনটি করে সংখ্যা নিলে কতগুলো পৃথক ত্রয়ী পাওয়া যায়, যাদের যোগফল শূন্য (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]]

সমস্যাটি আমি আজকে সন্ধ্যায় সমাধান করেছি (আমি পাইথন ব্যবহার করেছি), কিন্তু পুরো সমাধান লিখে দিয়ে পাঠককে প্রোগ্রামিংয়ের আনন্দ থেকে বঞ্চিত করতে চাইছি না।

উল্লেখ্য যে, এই প্রশ্নটি গুগল ও ফেসবুকের ইন্টারভিউতে ইতিপূর্বে জিজ্ঞাসা করা হয়েছে।

অন্তরফল – প্রোগ্রামিং ইন্টারভিউ সমস্যা ৫

সমস্যাঃ একটি ইন্টিজার অ্যারে দেওয়া আছে যার উপাদানগুলো ছোট থেকে বড় ক্রমে সাজানো। এখন একটি অঋণাত্মক সংখ্যা দেওয়া হলে, বলতে হবে যে, অ্যারের যেকোনো দুটি পৃথক সংখ্যার অন্তরফল ওই সংখ্যাটির সমান কী না। অর্থাৎ, অ্যারে A ও একটি সংখ্যা k (>= 0) দেওয়া থাকলে এরকম i ও j পাওয়া সম্ভব কী না, যেখানে, A[j] – A[i] = k, i != j.

উদাহরণঃ A = [1, 3, 5], k = 4 হলে, i = 0, j = 2 এর জন্য A[j] – A[i] = k হয়।

সমাধানঃ এটি সমাধান করা খুবই সহজ। নেস্টেড লুপ চালালেই হয়, আর সেক্ষেত্রে কমপ্লেক্সিটি হবে O(n^2). আমি এই সমাধানের কোড দেখালাম না, কারণ, আশা করি যারা এই লেখাটি পড়ছে, তাদের সবাই এটি কোড করতে পারবে। এখন ইন্টারভিউতে প্রথমে বলতে হবে যে, কোন পদ্ধতিতে সমাধান করার পরিকল্পনা করা হয়েছে এবং তারপর ইন্টারভিউয়ার যদি সম্মতি দেন, তাহলে সেটি কোড করতে হবে। এখন এই সমস্যার ক্ষেত্রে O(n^2) সমাধানটি যদি ঠিকঠাক হয়, তাহলে ইন্টারভিউয়ার জিজ্ঞাসা করবেন, টাইম কমপ্লেক্সিটি আরো কমানো যায় কী না। তখন চিন্তাভাবনা শুরু করতে হবে।

যেহেতু অ্যারেটি সর্ট করা আছে, তাই আমরা প্রতিটি A[i]-এর জন্য অ্যারেতে A[i]+k আছে কী না, সেটি খুঁজে বের করার কাজটি O(log n) কমপ্লেক্সিটিতে করতে পারি, বাইনারি সার্চ ব্যবহার করার মাধ্যমে। এটিও কোড করতে সমস্যা হওয়ার কথা নয়, তবুও আমি কোড দিচ্ছি –

def diff_possible(A, k):
    n = len(A)
    for i in range(n-1):
        key = A[i] + k
        
        left, right = i + 1, n - 1
        found = False
        
        while left <= right:
            mid = (left + right) // 2
    
            if A[mid] == key:
                found = True
                break
            if A[mid] < key:
                left = mid + 1
            else:
                right = mid - 1
                
        if found:
            break
                
    return found

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

ধরা যাক, A = [3, 3, 4, 5, 5, 6, 6, 7, 7, 7, 9, 14], k = 5.

এখন, i = 0 ও j = 1 থেকে শুরু করি। যতক্ষণ A[j] – A[i] < k হবে, ততক্ষণ j-এর মান বাড়াই। তাহলে, একসময় i = 0, j = 10 হবে, কারণ A[9] – A[0] = 7 – 3 = 4 < k. এখন, i-এর মান এক বাড়াবো, i = 1. j-এর মান কিন্তু 2 থেকে শুরু হবে না, আগে যেই মান ছিল (অর্থাৎ 10), সেখান থেকেই শুরু হবে। কারণ A[j] – A[i] <= A[j] – A[i+1] (যেহেতু অ্যারে সর্টেড, তাই A[i] <= A[i+1]). এখন কিন্তু একটু চিন্তাভাবনা করলে ও প্রয়োজনে কাগজ-কলম ব্যবহার করে পুরো সমাধানটি বুঝে ফেলার কথা এবং কোডও করে ফেলা কোনো সমস্যা হবে না। তবুও আমি কোড দিয়ে দিচ্ছি –

def diff_possible(A, k):
    n = len(A)
    found = False
    i, j = 0, 1
    while i < n - 1:
        while j < n:
            if A[j] - A[i] == k:
                return True
            if A[j] - A[i] > k:
                break
            j += 1
        i += 1
        if i == j:
            j += 1
                   
    return found

এই কোডে নেস্টেড লুপ থাকলেও কমপ্লেক্সিটি কিন্তু O(n). কারণ দ্বিতীয় লুপ শুরুর আগে কিন্তু j-এর মান নতুন করে সেট করা হচ্ছে না। কোডটা চাইলে এভাবেও লেখা যায় –

def diff_possible(A, k):
    n = len(A)
    found = False
    i, j = 0, 1
    while i < n - 1 and j < n:
        if A[j] - A[i] == k and i != j:
            return True
        if A[j] - A[i] > k:
            i += 1
        else:
            j += 1    
                
    return found

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

কেউ চাইলে এখানে গিয়ে সমস্যাটি সমাধান করতে পারে –https://www.interviewbit.com/problems/diffk/, যদিও সমাধান ইতিমধ্যে করে দিয়েছি!   উল্লেখ্য যে, এই ওয়েবসাইটের তথ্যমতে এই প্রশ্নটি ফেসবুকে ইন্টারভিউতে জিজ্ঞাসা করা হয়েছিল।

 

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

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

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

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