permutation – প্রোগ্রামিং ইন্টারভিউ সমস্যা ১৩

সমস্যাঃ একটি লিস্টে কিছু সংখ্যা থাকবে, সংখ্যাগুলোর সবগুলো বিন্যাস (permutation) বের করতে হবে।

উদাহরণ: লিস্টে যদি [1, 2, 3] থাকে, তাহলে বিন্যাসগুলো হবে –

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 2, 1]
[3, 1, 2]

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

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

আমি পাইথন কোড দিচ্ছি –

def permute(i, n):
	if i == n:
		print(r)
		return
	
	for j in range(n):
		if visited[j]:
			continue
		visited[j] = True
		r[i] = a[j]
		permute(i+1, n)
		visited[j] = False

if __name__ == "__main__":
	a = [1, 2, 3, 4]
	r = [0] * len(a)
	n = len(a)
	visited = [False] * n
	permute(0, n)

এখন, এখানে আমি অতিরিক্ত একটি অ্যারে বা লিস্ট ব্যবহার করেছি। যদি সেটি করতে না চাই, তাহলে আরেকভাবে সমস্যাটির সমাধান করা যায়। সেক্ষেত্রে প্রতিটি অবস্থানের জন্য বাকী অবস্থানে যেসব সংখ্যা আছে, তাদের মধ্যে অদল-বদল করতে হবে। কোড হবে এরকম –

def permute2(l, r):
	if l == r:
		print(a)
		return
	
	for i in range(l, r+1):
		a[l], a[i] = a[i], a[l]
		permute2(l+1, r)
		a[l], a[i] = a[i], a[l]

if __name__ == "__main__":
	a = [1, 2, 3, 4]
	r = [0] * len(a)
	n = len(a)
	visited = [False] * n
	permute2(0, n-1)

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

def permute3(i, n):
	if i == n:
		tpl = tuple(r)
		if tpl in s:
			return
		s.add(tpl)
		print(r)
		return
	
	for j in range(n):
		if visited[j]:
			continue
		visited[j] = True
		r[i] = a[j]
		permute3(i+1, n)
		visited[j] = False

if __name__ == "__main__":
	a = [1, 2, 3, 1]
	n = len(a)
	r = [0] * n	
	visited = [False] * n
	s = set()
	permute3(0, n)

এখন আমরা যদি সেট ব্যবহার করতে না চাই, তাহলে দ্বিতীয় প্রোগ্রামের কোড একটু পরিবর্তন করে কাজটি করা যায় –

def permute4(l, r):
	if l == r:
		print(a)
		return
	
	for i in range(l, r+1):
		if a[i] in a[l:i]:
			continue
		a[l], a[i] = a[i], a[l]
		permute4(l+1, r)
		a[l], a[i] = a[i], a[l]


if __name__ == "__main__":
	a = [1, 2, 3, 1]
	n = len(a)
	r = [0] * n	
	visited = [False] * n

ওপরের প্রোগ্রামটি কীভাবে কাজ করে, সেটি বুঝতে হলে একটু খাতাকলম নিয়ে বসতে হবে। পরিশ্রম ছাড়া এমনি এমনি প্রোগ্রামিং শেখা যায় না।

LCS-Zero – প্রোগ্রামিং ইন্টারভিউ সমস্যা ১২

সমস্যাঃ একটা ইন্টিজারের অ্যারে দেওয়া আছে। সেখানে যদি পরপর কতগুলো সংখ্যা পাওয়া যায়, যাদের সমষ্টি শূন্য, সেই সংখ্যাগুলোর মধ্যে সবচেয়ে বেশিসংখ্যক ক্রমিক (অ্যারেতে ক্রমানুসারে সাজানো) সংখ্যাগুলো বের করতে হবে।

উদাহরণঃ 1, 2, -2, 4, -4 – এই সংখ্যাগুলোর মধ্যে, 2, -2 -এর যোগফল 0; 4, -4 – এর যোগফল 0; আবার 2, -2, 4, -4 সংখ্যাগুলোর যোগফলও 0। এখন সবচেয়ে বেশি সংখ্যক ক্রমিক সংখ্যা হচ্ছে 2, -2, 4, -4। তাই আমাদের উত্তর হবে 2, -2, 4, -4.

সমস্যাটি কেউ নিজে সমাধান করতে চাইলে এখানে চেষ্টা করতে হবে – https://www.interviewbit.com/problems/largest-continuous-sequence-zero-sum/

সমাধানঃ আমরা প্রথমে সবচেয়ে সহজ বুদ্ধি প্রয়োগ করতে পারি। অ্যারেতে যদি n সংখ্যক উপাদান থাকে, তাহলে সবগুলো উপাদানের সমষ্টি 0 কী না, সেটি পরীক্ষা করি। তারপরে n-1 সংখ্যক ক্রমিক সংখ্যার সমষ্টি 0 কী না পরীক্ষা করি। তারপর n-2 সংখ্যক ক্রমিক সংখ্যার সমষ্টি পরীক্ষা করি… এভাবে যতক্ষণ না আমরা সমষ্টি 0 পাচ্ছি, ততক্ষণ পরীক্ষা করবো আর n-এর মান এক কমাতে থাকবো 1 পর্যন্ত। যেমন, আমাদের যদি 1, 2, 3, -4, 5 – এই পাঁচটি সংখ্যা দেওয়া হয়, তাহলে প্রথমে পরীক্ষা করবো –

1 + 2 + 3 + -4 + 5 = 7

তারপরে চারটি করে ক্রমিক সংখ্যা নেব –
1 + 2 + 3 + -4 = 2
2 + 3 + -4 + 5 = 6

এবারে তিনটি করে ক্রমিক সংখ্যা –
1 + 2 + 3 = 6
2 + 3 + -4 = 1
3 + -4 + 5 = 4

এখন দুটি করে ক্রমিক সংখ্যা নেই –
1 + 2 = 3
2 + 3 = 5
3 + -4 = -1
-4 + 5 = 1

এখন একটি করে সংখ্যা নিয়ে দেখবো তাদের সমষ্টি (অর্থাৎ সেই সংখ্যাটির মান) 0 কী না। এই উদাহরণে এরকম সংখ্যা নাই।

যাই হোক, আশা করি, আমি কী করতে চাচ্ছি, তা বুঝাতে পেরেছি। এখন নিজে কোড লেখার চেষ্টা করতে হবে।

আমরা এরকম কোড লিখতে পারি –

def lszero1(A):
    n = len(A)
    
    for window_size in range(n, 0, -1):
        for start in range(0, n):
            if start+window_size > n:
                    break
            if 0 == sum(A[start:start+window_size]):
                return A[start:start+window_size]
                
    return []

এই কোডের কমপ্লেক্সিটি কত? sum() ফাংশনের কমপ্লেক্সিটি হচ্ছে O(n)। তাহলে আমাদের ফাংশনের কমপ্লেক্সিটি হবে O(n^3). প্রতিবার কিন্তু আসলে sum() ফাংশন ব্যবহার না করলেও চলে। আমরা যদি জানি, 1 + 2 + 3 = 6, তাহলে 2 + 3 + 4 হবে, আগের যোগফল থেকে 1 বিয়োগ ও 4 যোগ। বিষয়টি একটু ঠান্ডা মাথায় চিন্তা করলেই বুঝে ফেলার কথা। এই কাজটি ঠিকভাবে করতে পারলে আমরা আমাদের কোডের কমপ্লেক্সিটি O(n^2)-এ নামিয়ে আনতে পারবো।

for window_size in range(n, 0, -1):
    w_sum = sum(A[0:window_size])
    if w_sum == 0:
        return A[0:window_size]
    for start in range(1, n):
        if start + window_size > n:
            break    
        w_sum = w_sum - A[start-1] + A[start+window_size-1]
        if w_sum == 0:
            return A[start:start+window_size]                

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

A = [1, 2, -2, 4, -4], এর শুরু থেকে ক্রমিক সংখ্যাগুলোর যোগফল 1, 3 (1+2), 1 (1+2+-2), 5 , (1+2+-2+4), 1 (1+2+-2+4+-4)। এগুলো একটি অ্যারেতে রাখি –
S = [1, 3, 1, 5, 1]. এখন এই ক্ষেত্রে, প্রথম সংখ্যাটি 1, আবার পঞ্চম সংখ্যাটিও 1। অর্থাৎ প্রথম সংখ্যার পরে পরপর চারটি সংখ্যা যোগ করে যোগফলের কোনো পরিবর্তন হলো না। এতে আমরা কী বুঝলাম?

লিঙ্কড লিস্ট ১ – প্রোগ্রামিং ইন্টারভিউ সমস্যা ১১

সমস্যাঃ একটি সিঙ্গলি লিঙ্কড লিস্ট দেওয়া আছে, যেখানে প্রতিটি নোডের ডেটা ও পরবর্তী নোডের ঠিকানা থাকবে।

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

আমরা তো দুটি পদ্ধতিতে সমস্যাটির সমাধান করলাম? দুটোর টাইম ও স্পেস কমপ্লেক্সিটির মধ্যে পার্থক্য কী?

 

রানিং মিডিয়ান – প্রোগ্রামিং ইন্টারভিউ সমস্যা ১০

সমস্যাঃ একটি অ্যারেতে বা লিস্টে শুরুতে কোনো সংখ্যা নেই। অ্যারেতে ক্রমান্বয়ে n সংখ্যক সংখ্যা যুক্ত হবে, আর প্রতিটি সংখ্যা যুক্ত হওয়ার পরে ওই অ্যারের বর্তমান সংখ্যাগুলোর মিডিয়ান বের করতে হবে।

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

উদাহরণঃ ধরা যাক, অ্যারেতে ক্রমান্বয়ে 1, 2, 3, 4-এই চারটি সংখ্যা যুক্ত করতে হবে। শুরুতে অ্যারেটি খালি। তারপর 1 যোগ করি, তাহলে অ্যারের অবস্থা দাঁড়াবে এমন – [1]। এখন মিডিয়ান হচ্ছে 1। তারপর 2 যোগ করি – [1, 2]। এখন মিডিয়ান হচ্ছে 1.5 ((1 + 2) / 2)। তারপর 3 যোগ করি – [1, 2, 3]। এখন মিডিয়ান হচ্ছে 2। তারপর 4 যোগ করি – [1, 2, 3, 4]। এখন মিডিয়ান হবে 2.5 (2 ও 3-এর গড়)।

সমাধানঃ সমস্যাটির সহজ একটি সমাধান হচ্ছে ইনসার্শন সর্ট (insertion sort)। আমরা প্রতিবার একটি করে সংখ্যা নিয়ে অ্যারেটি সর্ট করে ফেলবো, আর যেহেতু নতুন সংখ্যা আসার পূর্ব পর্যন্ত অ্যারেটি সর্ট করা আছে, তাই ইনসার্শন সর্ট এক্ষেত্রে একটি কার্যকর পদ্ধতি। ইন্টারভিউয়ারের সঙ্গে আলোচনা করার পরে উনি বলবেন যে, এই পদ্ধতির কমপ্লেক্সিটি কত সেটা বের করতে, কিংবা হয়ত এটি ইমপ্লিমেন্ট করতেও বলতে পারেন। এই পদ্ধতির ওয়ার্স্ট কেস টাইম কমপ্লেক্সিটি হচ্ছে O(n^2), বেস্ট কেস হচ্ছে O(n)। আর কোড করতেও 5-6 মিনিটের বেশি সময় লাগা উচিত নয়। এখন প্রশ্ন হচ্ছে, আমরা কিভাবে আরো ভালো পদ্ধতিতে সমাধান করতে পারি?

কেউ সমস্যাটি সমাধান করতে চাইলে এখানে করতে পারে – https://www.hackerrank.com/challenges/find-the-running-median/

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

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

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

এখন কথা হচ্ছে হিপ কি আমরা শুরু থেকে ইমপ্লিমেন্ট করবো নাকি কোনো লাইব্রেরি (পাইথনে যেমন heapq) ব্যবহার করবো? এটি ইন্টারভিউয়ারকে জিজ্ঞাসা করতে হবে। হিপ নিজে ইমপ্লিমেন্ট করার অভ্যাস থাকতে হবে কারণ অনেক ইন্টারভিউয়ার সেটাও দেখতে চাইবেন। আমি এখানে কোড লিখে রেখেছি – https://gist.github.com/tamim/4dd1e7fede8e5d76f0b4c4e397e3538c

বিটের পার্থক্যের সমষ্টি – প্রোগ্রামিং ইন্টারভিউ সমস্যা ৯

সমস্যাঃ একটা অ্যারেতে কতগুলো অঋণাত্মক সংখ্যা আছে। ওই সংখ্যাগুলোর মাঝে যতগুলো জোড়া (pair) আছে, তাদের মধ্যে বিটের পার্থক্যের যোগফল বের করতে হবে। অর্থাৎ, কোনো একটি অ্যারেতে তিনটি সংখ্যা n1, n2, n3 থাকলে বের করতে হবে : n1 ও n2-এর মধ্যে বিটের পার্থক্য + n1 ও n3-এর মধ্যে বিটের পার্থক্য + n2 ও n3-এর মধ্যে বিটের পার্থক্য + n2 ও n1-এর মধ্যে বিটের পার্থক্য + n3 ও n1-এর মধ্যে বিটের পার্থক্য + n3 ও n2-এর মধ্যে বিটের পার্থক্য।

n1 ও n2-এর বিটের পার্থক্য হচ্ছে, সংখ্যা দুটিকে বাইনারিতে প্রকাশ করলে, যতগুলো পজিশনে তাদের বিটগুলো ভিন্ন হয়। যেমন, 7-কে বাইনারিতে প্রকাশ করলে আমরা পাই 111। আর 2-কে বাইনারিতে প্রকাশ করলে পাই 010। তাহলে 7 ও 2-এর মধ্যে প্রথম ও তৃতীয় বিট আলাদা, অর্থাৎ তাদের বিটের পার্থক্য 2।

উদাহরণঃ একটি অ্যারেতে যদি থাকে – [2, 4, 6], তাহলে তাদের সব জোড়ার বিটের পার্থক্য হবে –

f(2, 4) + f(2, 6) + 
f(4, 2) + f(4, 6) +
f(6, 2) + f(6, 4)  = 

2 + 1
2 + 1
1 + 1  = 8

সমস্যাটির সমাধান করতে হলে বিট অপারেশন সম্পর্কে পরিষ্কার ধারণা থাকতে হবে। সমস্যাটি এখানে সমাধান করে যাচাই করা যাবে – https://www.interviewbit.com/problems/sum-of-pairwise-hamming-distance/

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

সমস্যাটি O(n) কমপ্লেক্সিটিতেও সমাধান করা যায়। সেক্ষেত্রে আমাদেরকে জানতে হবে একটি সংখ্যা সর্বোচ্চ কত বিটের হবে। ইন্টারভিউয়ারকে সেটি প্রশ্ন করে জেনে নিতে হবে। ধরা যাক, সংখ্যাগুলো 32 বিটের। তখন বিটের প্রতিটি অবস্থানের জন্য (অর্থাৎ ১ম বিট, ২য় বিট, ৩য় বিট … ) কতগুলো সংখ্যায় ওই বিটে 1 আছে (একে বলা হয় সেট বিট) সেটি বের করতে হবে। ধরা যাক, এর মান হচ্ছে count। আর অ্যারেতে মোট সংখ্যা হচ্ছে nটি। তাহলে n – count সংখ্যায় ওই অবস্থানের বিটটি হচ্ছে 0। তাহলে ওই অবস্থানের জন্য বিটের মোট পার্থক্য হবে count * (n – count) * 2। দুই দিয়ে গুণ করার কারণ হচ্ছে, n1, n2 ও n2, n1 আলাদা জোড়া।

হিন্টসঃ একটি সংখ্যা n-এর i-তম (ডান দিক থেকে) বিট 1 কী না, সেটি বেরা যায় n & (1 << i) -এর মাধ্যমে।

 

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

সমস্যাঃ সম্প্রতি আমি একটা ইন্টারভিউতে এই সমস্যাটি দেখেছি – একটা ফাংশন লিখতে হবে, যেখানে ইনপুট 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