Month: May 2018

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

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

• Hackerrank – Queue using two stacks
• Leetcode – Queue using Stacks

সমস্যাঃ একটি ফাংশন তৈরি করতে হবে, যেখানে একটি বাইনারি ট্রি ইনপুট দেওয়া হলে সেটি বাইনারি সার্চ ট্রি (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

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

• Hackerrank – Is BST
• Leetcode – Validate Binary Search Tree

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

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)

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