Tag: প্রোগ্রামিং ইন্টারভিউ

সমস্যা – একটি অ্যারে দেওয়া থাকবে যার প্রতিটি উপাদান একটি ইন্টিজার এবং অ্যারের সংখ্যাগুলো ছোট থেকে বড় ক্রমে সাজানো আছে। ওই অ্যারেতে যেসব সংখ্যা একাধিকবার আছে, সেসব সংখ্যা একটি রেখে অতিরিক্তগুলো বাদ দিতে হবে। আর এজন্য অতিরিক্ত কোনো অ্যারে ব্যবহার করা যাবে না, অর্থাৎ ইনপুট অ্যারেতেই কাজ করতে হবে। যেমন, ইনপুট যদি হয় [1, 1, 1, 2, 3, 3], তাহলে ডুপ্লিকেট (duplicate)-গুলো বাদ দিলে অ্যারেটি হবে [1, 2, 3, …]. এক্ষেত্রে প্রথম তিনটি সংখ্যার পরে বাকিগুলো কী হবে, সেটি বিবেচনা করা হবে না। আর অ্যারেটি পরিবর্তন করার পরে অ্যারেতে মোট কয়টি উপাদান আছে সেটি রিটার্ন করতে হবে। অর্থাৎ এই ইনপুটের জন্য অ্যারেটি পরিবর্তন করার পরে 3 রিটার্ন করতে হবে।

সমাধান – সমস্যাটিতে যদি বলা হত অতিরিক্ত অ্যারে ব্যবহার করা যাবে, তাহলে আমরা কী করতাম? একটি নতুন অ্যারে তৈরি করে সেখানে সংখ্যাগুলো এমনভাবে রাখতাম যেন কোনো সংখ্যা একবারের বেশি না আসে।

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

def remove_duplicates(nums):
    unique_nums = []
    unique_nums.append(nums[0])
    
    n = len(nums)
    for i in range(1, n):
        if nums[i] != nums[i-1]:
            unique_nums.append(nums[i])

    return len(unique_nums)

প্রোগ্রামটি আরেকভাবে ইমপ্লিমেন্ট করা যায় –

def remove_duplicates(nums):
    unique_nums = list(set(nums))
    unique_nums.sort()
    return len(unique_nums)

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

def remove_duplicates(nums):
    n = len(nums)
    unique_nums = [0] * n
    unique_nums[0] = nums[0]
    current_index = 1
    for i in range(1, n):
        if nums[i] != nums[i-1]:
            unique_nums[current_index] = nums[i]
            current_index += 1

    return current_index

এই ফাংশনটি ভালোভাবে লক্ষ করলে বুঝে ফেলা উচিত যে, unique_nums ব্যবহার না করলেও চলে। বুঝতে না পারলে একটু চিন্তা করতে হবে, তাহলেই বুঝে ফেলা উচিত।

আর ইন্টারভিউতে কিন্তু স্পেশাল কেস ঠিকভাবে হ্যান্ডেল করতে হবে। যেমন, এই প্রোগ্রামে ইনপুট যদি ফাঁকা অ্যারে বা লিস্ট হয়, তখন প্রোগ্রামটা 0 রিটার্ন করার বদলে ক্র্যাশ করবে, এটি ঠিক করতে হবে।

আশা করি নিচের দুটি সমস্যা সমাধান করতে তেমন বেগ পেতে হবে না –

https://leetcode.com/problems/remove-duplicates-from-sorted-array/

https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/

সমস্যাঃ একটি সেট দেওয়া আছে, সেই সেটের সকল সাবসেট তৈরি করার ফাংশন লিখতে হবে।

সমাধানঃ ইন্টারভিউতে এই প্রশ্ন করা হলে শুরুতেই দুটি বিষয় পরিষ্কার হয়ে নিতে হবে। সেটি হচ্ছে, ফাঁকা সেট এবং ওই সেটটি নিজে তার সাবসেট কী না। আমাদের এই আলোচনায়, দুটি উত্তরই হচ্ছে, হ্যাঁ।

সমাধান দেখার আগে নিজে চেষ্টা করা উচিত। এখানে গিয়ে সমস্যা দেখা যাবে ও সমাধান জমা দেওয়া যাবে – https://leetcode.com/problems/subsets/

তাহলে, ইনপুট যদি হয় [1, 2, 3], আউটপুট হবে, [[], [1], [2], [3], [1, 2], [2, 3], [1, 3], [1, 2, 3]]। আউটপুট লিস্টের উপাদানগুলোর ক্রম ভিন্ন হলেও সমস্যা নেই, কিন্তু একই জিনিস দুইবার থাকতে পারবে না।

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

def subsets1(S):
    if S == []:
        return [[]]
    
    result = [[]]
    n = len(S)
    visited = [False] * n
    
    def recurse(i, n, li):
        if i == n:
            return
        
        if len(li) > 0:
            result.append([x for x in li])
        
        for j in range(i, n):
            if visited[j]:
                continue
            visited[j] = True
            li.append(S[j])
            recurse(j, n, li)
            li.pop()
            visited[j] = False
            
    recurse(0, n, [])
    return result

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

সম্পূর্ণ কোড এখানে – https://gist.github.com/tamim/87d3b79ff15d3375a98e9e0cd73b7c73

 

সমস্যাঃ একটি লিস্টে কিছু সংখ্যা থাকবে, সংখ্যাগুলোর সবগুলো বিন্যাস (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

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

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

উদাহরণঃ 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]]

সমস্যাটি আমি আজকে সন্ধ্যায় সমাধান করেছি (আমি পাইথন ব্যবহার করেছি), কিন্তু পুরো সমাধান লিখে দিয়ে পাঠককে প্রোগ্রামিংয়ের আনন্দ থেকে বঞ্চিত করতে চাইছি না।

উল্লেখ্য যে, এই প্রশ্নটি গুগল ও ফেসবুকের ইন্টারভিউতে ইতিপূর্বে জিজ্ঞাসা করা হয়েছে।