১->০, ০->১ – প্রোগ্রামিং ইন্টারভিউ সমস্যা ৮

সমস্যাঃ সম্প্রতি আমি একটা ইন্টারভিউতে এই সমস্যাটি দেখেছি – একটা ফাংশন লিখতে হবে, যেখানে ইনপুট 0 হলে আউটপুট হবে 1 আর ইনপুট 1 হলে আউটপুট হবে 0। ফাংশনটা বিভিন্নভাবে লিখতে হবে। ফাংশনের ইনপুট কেবল 0 আর 1 হবে, অন্য কোনো সংখ্যা নয়।

সমাধানঃ আমার সমাধান দেখার আগে নিজে নিজে চেষ্টা করা উচিত।

এটা আসলে ঠিক কতভাবে করা যায়, আমার জানা নেই। তবুও পাইথন ব্যবহার করে আমি বেশ কয়েকভাবে ফাংশনটি লিখতে পারি।

প্রথমে অবশ্যই if-else ব্যবহার করে –

def fnc1(n):
    if n == 1:
        return 0
    else:
        return 1

ওপরের প্রোগ্রামটা পাইথনে আরেকটু সুন্দরভাবে লেখা যায় –

def fnc2(n):
    return 0 if n == 1 else 1

এবারে কিছু গাণিতিক বুদ্ধিশুদ্ধি ব্যবহার করি –

def fnc3(n):
    return (n + 1) % 2

এবারে লিস্ট ডেটা স্ট্রাকচার ব্যবহার করি –

def fnc4(n):
    li = [1, 0]
    return li[n]

একইভাবে চাইলে টাপলও ব্যবহার করা যায়। ডিকশনারি ব্যবহার করেও করা যায় –

def fnc5(n):
    dt = {1: 0, 0: 1}
    return dt[n]

এবারে বিট লেভেলে চিন্তা করা যাক।  আমরা যদি 1 এর সঙ্গে 0-কে এক্সর (XOR) করি, তাহলে 1 পাবো, আর 1-কে এক্সর করলে 0 পাবো –

def fnc6(n):
    return 1 ^ n

আমার মাথায় এগুলোই এসেছে। আর কোনোভাবে ফাংশনটি লেখা যায়?

স্ট্রিং-এর ভেতর স্ট্রিং (সাবস্ট্রিং) – প্রোগ্রামিং ইন্টারভিউ সমস্যা ৭

সমস্যাঃ দুটি স্ট্রিং দেওয়া আছে – A ও s. একটি ফাংশন লিখতে হবে, যার কাজ হচ্ছে, s যদি A-এর সাবস্ট্রিং হয়, তাহলে A-এর যেই ইনডেক্স থেকে s শুরু হয়েছে, সেই ইনডেক্স রিটার্ন করতে হবে। আর s যদি A-তে না থাকে, তাহলে -1 রিটার্ন করতে হবে।

সমাধানঃ প্রশ্নটা খুবই সহজ, তাই অনেকেই সরাসরি কোড লেখা শুরু করে দিবে। ইন্টারভিউতে এমন করলে কিন্তু হবে না। কারণ রিকোয়ারমেন্ট আরো পরিষ্কার করে নিতে হবে। যেমন, s যদি খালি স্ট্রিং হয়, তখন কী হবে? s যদি A-তে একাধিকবার থাকে, তখন কী হবে? – এসব প্রশ্নের উত্তর কোড লেখার আগেই জেনে নিতে হবে।

যারা পাইথন ব্যবহার করে অভ্যস্ত, তারা সহজেই কোড লিখে ফেলতে পারবে –

def string_search(A, s):
  if s in A:
    return A.index(s)
  else:
    return -1

খুবই সহজ কোড। তবে কেউ যদি বলে যে সে পাইথনে অভিজ্ঞ, তাহলে হয়ত তাকে ইন্টারভিউয়ার বলবেন যে, ফাংশনের ভেতরে এক লাইনে কোড লিখে ফেলতে। তখন কোড হবে এরকম –

def string_search(A, s):
  return A.index(s) if s in A else -1

এরপর ইন্টারভিউয়ার হয়ত বলবেন যে, index ফাংশন ব্যবহার করা যাবে না, আমি আসলে দেখতে চাইছি, আপনি এই ফাংশনটা নিজে তৈরি করতে পারেন কী না। তখন একটু চিন্তাভাবনা করে কোড লিখে ফেলতে হবে। আমার ধারণা আমার ব্লগের ৮০% পাঠকেরই এটা লিখতে দশ মিনিটের কম সময় লাগবে। আমি কোড লিখে দিচ্ছি –

if s == "" or A == "" or len(s) > len(A):
  return -1

lenA, lenS = len(A), len(s)

for i in range(lenA):
  if A[i] == s[0]:
    j, k = i, 0
    
    while j < lenA and k < lenS and A[j] == s[k]:
      j += 1
      k += 1

    if k == lenS:
      return i
    
return -1

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

বি.দ্র. ইউনিট টেস্ট নিয়ে আমি আগে একটি আর্টিকেল লিখেছি।

নোটঃ কোনো কোনো ইন্টারভিউয়ার এই প্রশ্নের উত্তরে আরো ইফিশিয়েন্ট অ্যালগরিদম ব্যবহার করতে পরামর্শ দেবেন। সেক্ষেত্রে রবিন-কার্প স্ট্রিং ম্যাচিং, অথবা কেএমপি (নুথ-মরিস-প্র্যাট) অ্যালগরিদম ব্যবহার করতে হবে।

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

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

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

সমস্যাঃ স্ট্যাক (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-তে নিয়ে আসবো (তখন দ্বিতীয় স্ট্যাকে সেগুলো প্রথম স্ট্যাকের বিপরীত ক্রমে থাকবে)। তারপরে দ্বিতীয় স্ট্যাক থেকে পপ করবো।

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

বাইনারি সার্চ ট্রি – প্রোগ্রামিং ইন্টারভিউ সমস্যা ২

সমস্যাঃ একটি ফাংশন তৈরি করতে হবে, যেখানে একটি বাইনারি ট্রি ইনপুট দেওয়া হলে সেটি বাইনারি সার্চ ট্রি (BST) কী না, তা বের করতে হবে।

সমাধানঃ কোনো বাইনারি ট্রি-কে বাইনারি সার্চ ট্রি হতে হলে ওই ট্রি-এর যেকোনো নোডের বামদিকের চাইল্ড ও নাতি-পুতি নোডগুলো ওই নোডের চেয়ে ছোট এবং ডানদিকের চাইল্ড ও নাতি-পুতি নোডগুলো ওই নোডের চেয়ে বড় হতে হবে। যেমন নিচের ট্রি-টি একটি বাইনারি সার্চ ট্রি –

             6
          /     \
         3       12
       /   \    /   \
      1     4  9     13

কিন্তু নিচের বাইনারি ট্রি-টি বাইনারি সার্চ ট্রি নয় (কেন?)

             6
          /     \
         3       12
       /   \    /   \
      1     7  9     13

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

এখন আমরা যদি প্রতিটি নোডের বামদিকের নোডটি সেই নোডের চেয়ে ছোট কী না এবং ডানদিকের নোডটি সেই নোডের চেয়ে বড় কী না, সেটি পরীক্ষা করি, তাহলে কিন্তু সমাধান সঠিক হবে না। কেন সঠিক হবে না, সেটি না বুঝলে ওপরে যেই দুটি উদাহরণ দিয়েছি, তা ভালোমতো বুঝতে হবে। তাহলে সমাধান কী? প্রতিটি নোডের বামদিকে যতগুলো নোড আছে, সেগুলো ওই নোডের চেয়ে ছোট কী না এবং তার ডানদিকে যতগুলো নোড আছে, সেগুলো ওই নোডের চেয়ে বড় কী না, তা পরীক্ষা করতে হবে। তাহলে আমরা পাইথনে কোড লিখে ফেলি –

class node:
  def __init__(self, data):
      self.data = data
      self.left = None
      self.right = None


def find_max(root):
    max_v = root.data
    if root.left:
        left_max = find_max(root.left)
        if left_max > max_v:
            max_v = left_max
    if root.right:
        right_max = find_max(root.right)
        if right_max > max_v:
            max_v = right_max
    return max_v


def check_binary_search_tree(root):
    if root is None:
        return True
        
    # find the largest number on the left sub-tree and check if it's smaller/equal to the root
    if root.left:
        max_value = find_max(root.left)
        if max_value >= root.data:
            return False
    
    # find the smallest number on the right sub-tree and check if it's larger than the root
    if root.right:
        min_value = find_min(root.right)
        if min_value <= root.data:
            return False
    
    # now do the same for the sub-trees
    valid_left = check_binary_search_tree(root.left)
    valid_right = check_binary_search_tree(root.right)
        
    return valid_left and valid_right

ওপরে find_min ফাংশনটি আমি ইমপ্লিমেন্ট করলাম না, find_max কীভাবে কাজ করে বুঝলে find_min তৈরি করতে সমস্যা হবে না। এখন প্রশ্ন হচ্ছে, ওপরের ফাংশনটির কমপ্লেক্সিটি কত? ফাংশনটির টাইম কমপ্লেক্সিটি হচ্ছে O(n^2). কীভাবে সেটি বুঝতে না পারলে একটি বাইনারি ট্রি, যেটি কী না বাইনারি সার্চ ট্রি, সেটি নিয়ে অ্যানালাইসিস করলে বুঝতে পারা যাবে (এই লেখার প্রথম উদাহরণের ট্রি-এর মতো)।

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

def check_binary_search_tree_(root):
    nodes = []
    
    def inorder(root):
        if root is None:
            return
        inorder(root.left)    
        nodes.append(root.data)
        inorder(root.right)
            
    inorder(root)
    
    for i in range(len(nodes)-1):
        if nodes[i] >= nodes[i+1]:
            return False
        
    return True

আমরা কিন্তু সময় বাঁচাতে গিয়ে একটু বেশি জায়গা খরচ করে ফেলেছি। কারণ এখানে আমরা একটি অতিরিক্ত লিস্ট ব্যবহার করেছি। এখন, আমরা যদি একটু চিন্তা করি কিংবা চেষ্টা করি, তাহলে এই অতিরিক্ত জায়গা ব্যবহার না করেও কিন্তু সমস্যাটির সমাধান করা যায়। আমি কোড লিখে দিচ্ছি, তবে আমার কোড দেখার আগে নিজে নিজে কাজটি করার চেষ্টা করা উচিত। আর সমাধান সঠিক হলো কী না, তা যাচাই করা যাবে নিচের যেকোনো একটি লিঙ্কে গেলে –

ওপরের লিঙ্কগুলোতে পাইথন ছাড়াও অন্য ভাষা ব্যবহার করা যাবে।

def check_binary_search_tree(root):
    
    def inorder(root):
        nonlocal last_node
        
        if root is None: 
            return True
        
        left_valid = inorder(root.left)    
        if left_valid is False:
            return False
        
        if root.data <= last_node: 
            return False
        
        last_node = root.data
        
        return inorder(root.right)  
    
    last_node = -1 #assuming all nodes are non-negative
    return inorder(root)

লেখাটি যাদের কাজে আসতে পারে, তাদের সঙ্গে শেয়ার করার অনুরোধ রইলো। ধন্যবাদ।
 

pow(a, n) – প্রোগ্রামিং ইন্টারভিউ সমস্যা ১

সমস্যাঃ একটি ফাংশন তৈরি করতে হবে, যেখানে দুটি ইন্টিজার (a, n) ইনপুট দেওয়া থাকলে ফাংশনটি a^n রিটার্ন করবে। ফাংশনটির রানটাইম হতে হবে O(log n)।

সমাধানঃ আমাদেরকে যেটি করতে হবে, সেটি হচ্ছে pow() ফাংশনটি ইমপ্লিমেন্ট করতে হবে। কিন্তু এতে ঘাবড়াবার কিছু নেই। আমরা পাইথনে খুব সহজে এটি ইমপ্লিমেন্ট করতে পারি।

def pow(a, n):
   result = 1.0
   for _ in range(n):
      result = result * a
   return result

ওপরে যেই ফাংশনটি লিখলাম, সেটির কমপ্লেক্সিটি কত? টাইম কমপ্লেক্সিটি হচ্ছে O(n)। কিন্তু আমাদেরকে বলা হয়েছে O(log n) কমপ্লেক্সিটিতে ইমপ্লিমেন্ট করতে। যদি এটি বলা না থাকতো, তাহলে কিন্তু ওপরের কোড লিখে দিলেই হতো।
আমরা ডিভাইড এন্ড কনকোয়ার পদ্ধতিতে সমস্যাটির সমাধান করতে পারি। সেজন্য আমাদেরকে একটি বিষয় উপলব্ধি করতে হবে। a^n-কে আমরা লিখতে পারি, (a^n/2) * (a^n/2). যেমন, 5^4 হচ্ছে 625. কিন্তু আমরা 5^4-কে লিখতে পারি, (5^2) * (5^2)। এভাবে লিখে লাভ কী হলো? লাভ হচ্ছে, 5^2 এর মান আমাদের দুবার বের করতে হবে না, একবার বের করলেই হবে। কিংবা ধরা যাক, আমাদেরকে 2^32-এর মান বের করতে বলা হলো।

2^32 = (2^16) * (2^16)
2^16 = (2^8) * (2^8)
2^8 = (2^4) * (2^4)
2^4 = (2^2) * (2^2)
2^2 = (2^1) * (2^1)

এখন আমরা জানি, a^0 হচ্ছে 1 আর a^1 হচ্ছে a. তাই রিকার্শন ব্যবহার করে সমস্যাটির সমাধান বের করতে কিন্তু আমাদের তেমন বেগ পেতে হবে না। আর n যদি জোড় সংখ্যা না হয়ে বিজোড় সংখ্যা হতো, তখন আমাদের কী করতে হবে? তখন a^n-কে আমরা লিখতে পারি a^(n-1) * a. n যেহেতু বিজোড় সংখ্যা, n-1 অবশ্যই জোড় সংখ্যা। তাই আমরা আবার আগের মতো আগাতে পারি।

এখন আমি প্রোগ্রাম লিখে ফেলি –

def pow(a, n):
   if n == 0: return 1
   if n == 1: return a 

   if n % 2 == 1:
      return a * pow(a, n-1) 
   else:
      p = pow(a, n/2)
      return p * p

ওপরের pow() ফাংশনটির কমপ্লেক্সিটি হচ্ছে O(log n)। কেন সেটি আর এখানে বিস্তারিত ব্যাখ্যা করলাম না, তবে যারা বাইনারি সার্চের কমপ্লেক্সিটি বোঝে, তাদের এটি বুঝতে কোনো সমস্যা হবে না।

সমস্যাটির সমাধান কিন্তু পুরোপুরি হয় নি। কারণ n যদি ঋণাত্মক হয় তখন কিন্তু প্রোগ্রামটি কাজ করবে না। এটি ঠিকঠাক করার জন্য আমাদেরকে কী করতে হবে?

পাইথন-এ ডেটা অ্যানালাইটিক্স

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

পাইথন এর প্রাথমিক ব্যাপারগুলো নিয়ে কিছু বলার আর তেমন দরকার আছে বলে আমার মনে হয় না। কারো প্রয়োজন হলে বিস্তারিত দেখে নেয়া যাবে এখান থেকে –

১। পাইথন পরিচিতি   

২। প্রাথমিক ধারনা  

আমার এই লিখাটা মূলত তিনটি বা চারটি পর্বে ভাগ করার ইচ্ছে। এই পর্বে আলোচনা করব NumPy এর একেবারের শুরুর কিছু ব্যাপার। সামনের পর্ব গুলোতে  থাকবে NumPy আর Pandas নিয়ে বিস্তারিত কিছু যা মূলত ডাটা এনালাইটিকস এর কাজে ব্যাবহৃত হয়।

তার আগে কিন্তু আমাদের পাইথন এর বেসিক কিছু ডাটা স্ট্রাকচার নিয়ে হাতেকলমে কাজ করে আসতে হবে ,যেমন list, dict, tuples, sets, strings । আমি নিশ্চিত তোমরা এই জিনিসগুলো পড়েই ডাটা এনালাইটিক্স এর কাজে হাত দিবে –
চটপট একটা পুরনো পড়া পড়ে ফেলতে পারি আমরা –
List এ  append আর  extend এর পার্থক্য কি ?

NumPy (সচরাচর উচ্চারন “নামপাই”) একটি লাইব্রেরি এবং শব্দটা এসেছে Numerical Python থেকে । এই লাইব্রেরি এন-ডাইমেনশনাল Array , বিভিন্ন জটিল গাণিতিক ফাংশন এর কাজ ( যেমন  Fourier transforms )-সহ আরো অনেক ধরনের গাণিতিক কাজ করার ক্ষেত্রে ওস্তাদ ।

ঢাকায় এখন বিভিন্ন এপভিত্তিক পরিবহন খুব জনপ্রিয় – আমরা সবাই উবার, পাঠাও, মুভ বা স্যাম নামে এইসব সেবা ব্যাবহার করছি আর সেইরকম একটি সার্ভিস-এর তিনজন ব্যবহারকারীর কিছু ডেটা আছে, সেইরকম তিনটা ফাইল নিয়ে আমরা কাজ শুরু করতে পারি।
আমরা সেখান থেকে তিনটা জিনিস বের করতে চাইব :
১। অফিস থেকে কে কখন রাইড নিয়ে বের হয়ে গিয়েছে ?
২। তাদের ভাড়ার Standard Deviation দেখতে কেমন ?
আর
৩। চেষ্টা করব বের করতে এই তিনজনের মাঝে কোন বাইক ড্রাইভার কমন ছিলেন কিনা, সম্ভব হলে সেটা গ্রাফে দেখা (যদিও গ্রাফে দেখার ব্যাপারটা এর সাথে তেমন একটা সম্পর্কিত না – কিন্তু দেখতে সুন্দর লাগে)।

এখান থেকে ফাইলগুলো নামিয়ে নেয়া যাবে (আপাতত আমি একটা ফাইল রেখেছি …পরবর্তী পর্বে বাকীগুলো পাওয়া যাবে)। 

প্রথমেই RidersData1 ফাইলটি পড়ে নিয়ে পাইথন-এ এর ডাটা দেখে নেই – 

import csv
with open("C:\Users\Asus\Desktop\RidersData1.csv", 'r') as f:
riders_data = list(csv.reader(f, delimiter=","))
print(riders_data[:2])

দেখে নেই যাত্রীর ভাড়ার পরিমান কত ছিল তার ভ্রমণের দিনগুলোতে

fare = [item[10] for item in riders_data[1:]]
print(fare)

তার মোট পরিমান কত ছিল ?

fare = [int(item[10]) for item in riders_data[1:]]
print(sum(fare))

>> ৫১৮৫ টাকা

এবার আমরা Numpy ইন্সটল করে কাজটা শুরু করি-
( Numpy ইন্সটল করার ধাপগুলো সুন্দর করে বলে দেয়া আছে এখানে

import numpy as np
riders_data = np.genfromtxt("D:\RidersData1.csv", delimiter=",", skip_header=1)

 

fare = [int(item[10]) for item in riders_data[0:]]
print(sum(fare))

এখন যদি Numpy ব্যাবহার করে Array তৈরী করি যা আসলে Array এর Array তৈরী করবে ।

riders_data_array = np.array(riders_data[1:], dtype=np.int)

এখানে dtype=np.int  আসলে নিশ্চিত করবে যেন ডাটা গুলোকে  String থেকে int এ রুপান্তর(convert) করে নেয়।

এখন আমরা যদি Array টা দেখতে চাই?

ইনপুট
 print(riders_data_array)
আউটপুট
 [[4445115     143    3180   15536       5]
  [4341383     167    3067   15704       5]
  [4153972     163    2383   15692       5]
  [4052253     167    3055   15703       5]
  [3935184     191    1520   12760       5]
  [3896665     202    2251   13224       5]
  [3807622     141    2611   15722       5]
  [3723194     236    2063   16165       5]
  [3650954     233    2411   15695       5]
  [3592384     262    5845   15721       5]
  [3538266     204    4802   11583       5]
  [3496106     242    3462   15698       5]
  [3455465     235    2588   15695       5]
  [3361305     229    1883   15724       5]
  [3353856     230    2173   15574       5]
  [3342150     234    2483   15700       5]
  [3302407     217    2461   15716       5]
  [3263818     163    2393   15688       5]
  [3227817     163    2270   15691       5]
  [3189625     166    2976   15635       5]
  [3118401     244    3155   16076       5]
  [3056517     245    3161   12712       5]
  [2966371     191    1882   12546       5]
  [2904590     242    2844   16122       5]
  [2872271     135    2652   15900       5]]

আমরা এখন যেকোন রকমের Array তৈরি করতে পারি

ইনপুট
 any_array = np.ones((5,6))
 print(any_array)
আউটপুট
 [[ 1.  1.  1.  1.  1.  1.]
  [ 1.  1.  1.  1.  1.  1.]
  [ 1.  1.  1.  1.  1.  1.]
  [ 1.  1.  1.  1.  1.  1.]
  [ 1.  1.  1.  1.  1.  1.]]

এখানে np.ones((5,6)) তে 5 এবং 6  যথাক্রমে row আর column বুঝাচ্ছে ।ঠিক একই রকম ভাবে একটা array তৈরি করতে পারি যেটার সবগুলো ভ্যালু হবে zero।

ইনপুট
 any_array = np.zeros((5,6))
 print(any_array)
আউটপুট
 [[ 0.  0.  0.  0.  0.  0.]
  [ 0.  0.  0.  0.  0.  0.]
  [ 0.  0.  0.  0.  0.  0.]
  [ 0.  0.  0.  0.  0.  0.]
  [ 0.  0.  0.  0.  0.  0.]]

আর এখন যদি চিন্তা করি একটা array তৈরি করব যার ভ্যালুগুলো হবে যে কোন নাম্বার বা Random ।

ইনপুট
 any_array = np.random.rand(2,3)
 print(any_array)
আউটপুট
 [[ 0.58870582  0.75596673  0.48148491]
  [ 0.39392526  0.16046594  0.34446376]]

এই পর্যায়ে এসে আমি দুটো বাড়ির কাজ দিতে চাই – 

১। Random নাম্বারের একটা array তৈরি করতে হবে যেখানে সংখ্যাগুলো হবে পূর্ণমান বা integer
২। any_array = np.eye(4)  – এই কোডটি run করলে যেই আউটপুট আসল তার মানে কি ?

স্লাইসিং (Slicing) :

শব্দটা শুনেই বুঝা যাচ্ছে – যে কোন বড় কোন Array থেকে কিছু অংশ কেটে নেয়াই slicing । যেমন আমাদের মূল ডাটা এর array ( riders_data_array)  যা দেখতে এমন

[[4445115     143    3180   15536       5]
  [4341383     167    3067   15704       5]
  [4153972     163    2383   15692       5]
  [4052253     167    3055   15703       5]
  [3935184     191    1520   12760       5]
  [3896665     202    2251   13224       5]
  [3807622     141    2611   15722       5]
  [3723194     236    2063   16165       5]
  [3650954     233    2411   15695       5]
  [3592384     262    5845   15721       5]
  [3538266     204    4802   11583       5]
  [3496106     242    3462   15698       5]
  [3455465     235    2588   15695       5]
  [3361305     229    1883   15724       5]
  [3353856     230    2173   15574       5]
  [3342150     234    2483   15700       5]
  [3302407     217    2461   15716       5]
  [3263818     163    2393   15688       5]
  [3227817     163    2270   15691       5]
  [3189625     166    2976   15635       5]
  [3118401     244    3155   16076       5]
  [3056517     245    3161   12712       5]
  [2966371     191    1882   12546       5]
  [2904590     242    2844   16122       5]
  [2872271     135    2652   15900       5]]

আমি যদি এখন এখান থেকে ২য় কলাম এর প্রথম ৫ টা ডাটা দেখতে চাই –

ইনপুট
 print(riders_data_array[0:5,1])
আউটপুট
 [143  167   163   167   191]

এখানে [0:5,1] অংশ টা বুঝাচ্ছে – প্রথম ৫ টি row এর ডাটা এবং তা ২য় column এর। এখানে যদি 0 এর পরিবর্তে আমি 1 লিখি – তারমানে তখন প্রথম row বাদ দিয়ে চারটি ডাটা নিবে এবং আউটপুট হবে এরকম

[167   163    167     191]

NumPy নিয়ে পরবর্তী পর্বটি কিছুদিন পর প্রকাশিত হবে। ধন্যবাদ।

 

 

 

 

গড়, মধ্যক ও প্রচুরক

গড় শব্দটির সঙ্গে তোমরা যারা স্কুলে বিষয়টি পড়ে ফেলেছ, তারা যেমন পরিচিত, তেমনি যারা ক্রিকেট খেলা দেখো, তারাও পরিচিত। এই বইটি যখন লেখা হচ্ছে, তখন তামিম ইকবালের টেস্ট ক্রিকেটে ব্যাটিং গড় হচ্ছ 40.34 আর সাকিব আল হাসানের 40.93। এই গড় কিভাবে হিসেব করা হলো আর এর মানেই বা কী?

আমাকে যদি দুটি সংখ্যা দিয়ে এদের গড় বের করতে বলা হয়, তখন আমি সংখ্যা দুটি যোগ করে দুই দিয়ে ভাগ করবো। যেমন : 5 ও 6, এই দুটি সংখ্যার গড় হচ্ছে (5 + 6) / 2 বা 11 / 2 বা 5.5। তিনটি সংখ্যা 6, 7, 8-এর গড় হচ্ছে (6 + 7 + 8) / 3 বা 21 / 3 বা 7। তাহলে আমাকে যদি n সংখ্যক সংখ্যা দেওয়া হয়, তাহলে তাদের গড় বের করতে হলে সবগুলো সংখ্যা যোগ করে n দিয়ে ভাগ করবো। তাহলেই হয়ে গেলো।

এখন আমরা পাইথন ব্যবহার করে একটি প্রোগ্রাম লিখবো, যার কাজ হচ্ছে অনেকগুলো সংখ্যার গড় বের করা।

def average(li):
   s = sum(li)
   n = len(li)
   return s / n

li = [1, 2, 3]
print("Average:", average(li))
li = [10, 20, 30, 40, 50, 60, 70, 80]
print("Average:", average(li))
li = [-1, 0, 1]
print("Average:", average(li))

প্রোগ্রামটি রান করলে আমরা আউটপুট পাবো এরকম :

Average: 2.0
Average: 45.0
Average: 0.0

ক্রিকেট খেলায় ব্যাটিং গড় কিভাবে বের করে? মোট রানকে ইনিংস দিয়ে ভাগ করতে হয়। তবে একটি মজার বিষয় হচ্ছে, কোনো ইনিংসে অপরাজিত থাকলে, অর্থাৎ, আউট না হলে, সেই ইনিংসকে ভাগ করার সময় গণনা করা হয় না। ধরা যাক, কোনো ব্যাটসম্যান প্রথম খেলায় করলো 50 রান, দ্বিতীয় খেলায় 100 রান (অপরাজিত), তৃতীয় খেলায় আবারো 50 রান করে আউট হলো। তাহলে তার ব্যাটিং গড় হবে, (50 + 100 + 50) / 2, বা 200 / 2 বা 100। এখানে 3 এর বদলে 2 দিয়ে ভাগ করার কারণ হচ্ছে, দ্বিতীয় খেলায় সে অপরাজিত ছিল।

এখন গড় আমাদের কী কাজে লাগে? ধরা যাক, আন্তর্জাতিক ক্রিকেট খেলায় নতুন একটি দেশের আগমন ঘটলো এবং বাংলাদেশের সঙ্গে ওই দলের খেলা। টসে হেরে ওই দল প্রথমে ব্যাটিং পেল। এখন ওদের যেই দুজন ব্যাটসম্যান ইনিংস ওপেন করতে এসেছে, ঘরোয়া লিগে একজনের ব্যাটিং গড় হচ্ছে 26 আরেকজনের হচ্ছে 41। এই তথ্য থেকে তুমি দুজন ব্যাটসম্যানের মধ্যে তুলনা করতে পারো যে, কে তুলনামূলক ভালো ব্যাটসম্যান। তবে আজকের ম্যাচে কে কত রান করবে, এটি কিন্তু ব্যাটিং গড়ের ওপর নির্ভর করে না। কারও ব্যাটিং গড় 26 মানে এই নয় যে, সে প্রতি ইনিংসে 26 রান করে। তাহলে গড় হচ্ছে কোনো কিছুর মান সম্পর্কে ধারনা করার জন্য একটি টুল মাত্র। ইংরেজিতে একে average বলে, তবে গণিতের ক্ষেত্রে mean শব্দটিই বেশি ব্যবহার করা হয়।

এখন আরেকটি উদাহরণ দেই। কোনো দেশের মানুষ কেমন ধনী বা গরিব, তা বোঝার জন্য অনেকসময় মাথাপিছু আয় ব্যবহার করা হয়। মাথাপিছু আয় মানে হচ্ছে গড় আয়। সেটি ব্যবহার করে সেই দেশের মানুষের অর্থনৈতিক অবস্থা সম্পর্কে ধারণা পাওয়া যায়। কিন্তু সেখানে যদি মানুষের আয়ের মধ্যে বৈষম্য অনেক বেশি হয়, তাহলে কিন্তু গড় ব্যবহার করে প্রকৃত ধারণা পাওয়া যাবে না। একটি উদহারণ দিয়ে বোঝাই। ধরা যাক, কোনো দেশে 10 জন মানুষ আছে। তাদের মধ্যে 2 জন প্রতি মাসে 10 হাজার টাকা আয় করে। 5 জন প্রতিমাসে 20 হাজার টাকা আয় করে। আর একজন আয় করে প্রতিমাসে 30 হাজার টাকা। বাকী দুইজন প্রতি মাসে 5 লক্ষ টাকা আয় করে। তাহলে প্রতিমাসে তাদের গড় আয় কত?

গড় আয় = (10000 + 10000 + 20000 + 20000 + 20000 + 20000 + 20000 + 30000 + 500000 + 500000) / 10 = 115000।
তার মানে গড় আয় এক লক্ষ পনের হাজার টাকা! তাহলে শুধু গড় আয় জানলে যেকেউ সেই দেশের মানুষকে ধনী ভাববে। তাই গড় ব্যবহার করে সবসময় প্রকৃত চিত্র পাওয়া যায় না। তবে এতে হতাশ হওয়ার কিছু নেই, কারণ আমাদের হাতে রয়েছে মধ্যক ও প্রচুরক।

মধ্যক

এখন ধরা যাক, তুমি কোনো ক্রিকেট দলের ম্যানেজার। তোমার দল তৈরির সময় দুই জন ব্যাটসম্যান – রবিন ও সমিত-এর মধ্যে একজনকে বেছে নিতে হবে। দুজনের মধ্যে যার ব্যাটিং গড় বেশি, তুমি তাকে দলে নিতে পারো। কিন্তু তুমি যদি আরেকটু সচেতন হও, তখন হয়ত তুমি জানতে চাইতে পারো যে, কে কতগুলো ম্যাচ খেলেছে। ধরা যাক, রবিন 50 টি ম্যাচ খেলেছে এবং তার ব্যাটিং গড় 30। আর সমিত খেলেছে 5টি ম্যাচ এবং তার ব্যাটিং গড় 38। তুমি কিন্তু বেশিরভাগ ক্ষেত্রেই রবিনকে দলে নেবে, যেহেতু সে সমিতের তুলনায় অনেক বেশি অভিজ্ঞ। কিন্তু দুইজন যদি সমান সংখ্যক ম্যাচ খেলে, তখন কি কেবল গড় হিসেব করবে? তুমি চাইলে তখন আরেক ধরনের টুল ব্যবহার করতে পারো, যার নাম মধ্যক (ইংরেজিতে বলে median)। ধরা যাক, রবিন ও সমিত – দুজনেই 10টি করে ম্যাচ খেলেছে। 10টি ম্যাচে রবিনের রান হচ্ছে 95, 88, 47, 0, 10, 1, 5, 12, 0, 3। আর সমিতের রান হচ্ছে 10, 40, 20, 37, 0, 1, 25, 35, 30, 33। রবিনের গড় রান সমিতের গড় রানের চেয়ে বেশি। তবে এখানে আমরা দেখতে পাচ্ছি, রবিন মাঝে-মধ্যে অনেক বেশি রান করে, তবে বেশিরভাগ সময়ই সে খুব একটা ভালো খেলে না। আর সমিত দুয়েকটা বাদের বাকি খেলাগুলোয় মোটামুটি রান করতে পারে। তাই শুধু গড়ের ওপর ভরসা করা আমাদের ঠিক হবে না। আমরা মধ্যক বের করবো। প্রথমে আমরা তাদের প্রতি ম্যাচের রান ছোট থেকে বড় ক্রমানুসারে সাজাবো। তাহলে রবিনের রান হবে 0, 0, 1, 3, 5, 10, 12, 47, 88, 95 আর সমিতের রান হবে 0, 1, 10, 20, 25, 30, 33, 35, 37, 40। মধ্যক বের করতে গেলে আমাদেরকে তালিকার মাঝামাঝি সংখ্যাটি নিতে হবে। মোট সংখ্যা যদি বিজোড় হয়, তাহলে মাঝামাঝি সংখ্যা হবে একটি। যেমন 11-এর ক্ষেত্রে 6 নম্বর সংখ্যাটি হচ্ছে মাঝামাঝি সংখ্যা। কারণ ওই সংখ্যার চেয়ে ছোট 5টি সংখ্যা আছে। আবার বড় সংখ্যাও আছে 5টি। কিন্তু জোড় সংখ্যার বেলায় একটি মাঝামাঝি সংখ্যা বের করা যায় না। যেমন 10টি সংখ্যার ক্ষেত্রে আমরা যদি 5 নম্বর সংখ্যাটিকে মাঝামাঝি সংখ্যা ধরি, তাহলে তার ছোটি 4টি আর তার বড় 5টি সংখ্যা থাকবে। আবার 6 নম্বর সংখ্যাকে মাঝামাঝি সংখ্যা ধরলে, তার ছোট 5টি আর বড় 4টি সংখ্যা থাকবে।

যেহেতু আমাদের 10 টি সংখ্যা, তাই আমরা 5 ও 6 নম্বর সংখ্যা দুটি নিয়ে তাদের গড় বের করবো, মানে সংখ্যা দুটি যোগ করে দুই দিয়ে ভাগ করবো। তাহলে রবিনের রানের মিডিয়ান হবে 7.5 আর সমিতের রানের মিডিয়ান হবে 27.5। এখানে আমরা মিডিয়ান ব্যবহার করে সিদ্ধান্ত নিতে পারি যে কাকে দলে নেব। কাজটি তোমরা খাতা কলমে করে ফেল, তবে আমি পাইথন ব্যবহার করে একটি প্রোগ্রাম লিখে দেখাবো।

def median(li):
   li.sort()
   count = len(li)
   if count == 0:
      return None
   if count % 2 == 1:
      mid = count // 2
      return li[mid]
   else:
      mid2 = count // 2
      mid1 = mid2 - 1
      return (li[mid1]+li[mid2])/2

robin_run = [95, 88, 47, 0, 10, 1, 5, 12, 0, 3]
shomit_run = [10, 40, 20, 37, 0, 1, 25, 35, 30, 33]

median_robin = median(robin_run)
median_shomit = median(shomit_run)

print("Median run for Robin", median_robin)
print("Median run for Shomit", median_shomit)

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

প্রচুরক

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

একটি ওয়ানডে ম্যাচে একজন বোলারের পক্ষে সর্বোচ্চ ও সর্বনিম্ন কয়টি উইকেট পাওয়া সম্ভব? উত্তর হবে, যথাক্রমে 10টি ও 0টি। 0-এর চেয়ে কম কিংবা 10-এর চেয়ে বেশি উইকেট পাওয়া সম্ভব নয়। এখন ধরা যাক, মোস্তাফিজ এখন পর্যন্ত 20টি ওয়ানডে ম্যাচে বোলিং করেছে। সেই খেলাগুলোতে সে প্রতি খেলায় যতগুলো উইকেট পেয়েছে, তা হচ্ছে : 6, 5, 6, 4, 3, 1, 3, 2, 1, 0, 5, 3, 3, 2, 2, 1, 3, 4, 3, 3। এখন আমি একটি তালিকা তৈরি করবো, যে মোস্তাফিজ 0 উইকেট পেয়েছে কতবার, 1 উইকেট পেয়েছে কতবার … এরকম।

উইকেট ম্যাচের সংখ্যা
0 1
1 3
2 3
3 7
4 2
5 2
6 2
7 0
8 0
9 0
10 0

তাহলে আমরা দেখতে পাচ্ছি, মোস্তাফিজ সবচেয়ে বেশি পেয়েছে 3 উইকেট। 20টি খেলার মধ্যে 7 টি খেলাতেই সে 3 উইকেট করে পেয়েছে। তাহলে তুমি ধরে নিতে পারো যে, আজকের খেলাতে মোস্তাফিজের 3 উইকেট পাওয়ার সম্ভাবনাই সবচেয়ে বেশি। এখানে প্রচুরক হচ্ছে 3। কারণ উইকেটের লিস্টে 3 সবচেয়ে বেশি বার আছে। আমরা এখন ওপরের হিসেবটা একটি পাইথন প্রোগ্রাম লিখে করবো।

wkts_list = [6, 5, 6, 4, 3, 1, 3, 2, 1, 0, 5, 3, 3, 2, 2, 1, 3, 4, 3, 3]

for item in range(11):
   print("Wicket:", item, "Count:", wkts_list.count(item))

প্রোগ্রামটি রান করলে আউটপুট আসবে এরকম :

Wicket: 0 Count: 1
Wicket: 1 Count: 3
Wicket: 2 Count: 3
Wicket: 3 Count: 7
Wicket: 4 Count: 2
Wicket: 5 Count: 2
Wicket: 6 Count: 2
Wicket: 7 Count: 0
Wicket: 8 Count: 0
Wicket: 9 Count: 0
Wicket: 10 Count: 0

যে ঘটনাটি সবচেয়ে বেশি সংখ্যক বার ঘটে, সেটিই হচ্ছে প্রচুরক। বিভিন্ন রকম মতামত জরিপ করতে প্রচুরক ব্যবহার করা হয়। যেমন ধরো, তুমি একটি নতুন মোবাইল ফোন কিনতে চাও। কিন্তু কোন ব্র্যান্ডের ফোন ভালো সেটা বুঝতে পারছ না। তখন তুমি তোমার বন্ধুদের জিজ্ঞাসা করতে পারো এবং সবচেয়ে বেশি সংখ্যক বন্ধু যেই ব্র্যান্ডের মোবাইল ফোন ব্যবহার করে বা ভালো বলে, সেই ব্র্যান্ডের ফোন কিনতে পারো।

গড়, মধ্যক ও প্রচুরক হচ্ছে পরিসংখ্যানের একেবারে মৌলিক জিনিস। এগুলো ছাড়াও আরো অনেক ধরনের টুল আছে, যেগুলো ব্যবহার করে বিভিন্ন তথ্য-উপাত্ত বিশ্লেষণ করা যায়। এগুলো তোমরা ভবিষ্যতে পরিসংখ্যান পড়লে জানতে পারবে।

এই লেখাটি সহ গণিতের আরো কিছু মৌলিক বিষয় নিয়ে প্রকাশিত হয়েছে গণিত করবো জয়