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

সমস্যাঃ একটি ইন্টিজার অ্যারে দেওয়া আছে যার উপাদানগুলো ছোট থেকে বড় ক্রমে সাজানো। এখন একটি অঋণাত্মক সংখ্যা দেওয়া হলে, বলতে হবে যে, অ্যারের যেকোনো দুটি পৃথক সংখ্যার অন্তরফল ওই সংখ্যাটির সমান কী না। অর্থাৎ, অ্যারে 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/, যদিও সমাধান ইতিমধ্যে করে দিয়েছি!   উল্লেখ্য যে, এই ওয়েবসাইটের তথ্যমতে এই প্রশ্নটি ফেসবুকে ইন্টারভিউতে জিজ্ঞাসা করা হয়েছিল।