সমস্যাঃ একটি সিঙ্গলি লিঙ্কড লিস্ট দেওয়া আছে, যেখানে প্রতিটি নোডের ডেটা ও পরবর্তী নোডের ঠিকানা থাকবে।
class SinglyLinkedListNode:
def __init__(self, node_data):
self.data = node_data
self.next = None
এখন একটি ফাংশন লিখতে হবে –
int getNode(SinglyLinkedListNode* head, int positionFromTail)
অর্থাৎ লিঙ্কড লিস্টের শুরুর নোড (হেড নোড) দেওয়া থাকবে, আর একটা সংখ্যা দেওয়া থাকবে, ওই সংখ্যার মান যত, লিঙ্কড লিস্টের শেষ থেকে ততঘর বা ততটি নোড আগে এসে যেই নোড পাওয়া যায়, তার মান রিটার্ন করতে হবে।
এটা বেশ সহজ একটি সমস্যা। ইন্টারভিউতে এই সমস্যা দিলে ইন্টারভিউয়ার আশা করবেন যে 10-12 মিনিট বা তার চেয়ে কম সময়ে এটি সমাধান করতে হবে।
কেউ সমস্যাটি সমাধান করতে চাইলে এখানে চেষ্টা করতে পারে – https://www.hackerrank.com/challenges/get-the-value-of-the-node-at-a-specific-position-from-the-tail/problem
সমাধানঃ আমরা রিকার্শন ব্যবহার করে সহজেই সমাধান করতে পারি। ইন্টারভিউতে শুরুতেই কোড লিখে ফেলা যাবে না। প্রথমে আলোচনা করে নিতে হবে যে, কাজটি কিভাবে করা হবে। যেমন, “আমি রিকার্শন ব্যবহার করে লিঙ্কড লিস্টের শেষে চলে আসবো, তারপরে শেষ থেকে শুরু করে কাউন্ট করে যাবো।”
পাইথনে রিকার্শন দিয়ে এভাবে কোড লেখা যেতে পারে –
def getNode(head, positionFromTail):
count = 0
value = None
def traverse_ll(node):
nonlocal count
nonlocal value
if node is None:
return
traverse_ll(node.next)
if count == positionFromTail:
value = node.data
count += 1
traverse_ll(head)
return value
nonlocal-এর ব্যবহার লক্ষ করতে হবে। এ বিষয়ে আমি এখানে একটি আর্টিকেল লিখেছি।
এখন ইন্টারভিউয়ার বলতে পারেন, স্ট্যাক ব্যবহার করে সমস্যাটির সমাধান করতে। তখন সেভাবে করার চেষ্টা করতে হবে। তাহলে আমরা সবগুলো নোডের মান একটি স্ট্যাকে রেখে দেবো। তারপরে positionFromTail এর চেয়ে একবার বেশি স্ট্যাক থেকে পপ করবো। কোড বেশ সহজ হবে, এরকম –
def getNode(head, positionFromTail):
value = None
stk = []
node = head
while node:
stk.append(node.data)
node = node.next
while positionFromTail >= 0:
value = stk.pop()
positionFromTail -= 1
return value
আমরা তো দুটি পদ্ধতিতে সমস্যাটির সমাধান করলাম? দুটোর টাইম ও স্পেস কমপ্লেক্সিটির মধ্যে পার্থক্য কী?
