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

সমস্যাঃ দুটি স্ট্রিং দেওয়া আছে – 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

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

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

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

Facebook Comments

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

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

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

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

Facebook Comments

অন্তরফল – প্রোগ্রামিং ইন্টারভিউ সমস্যা ৫

সমস্যাঃ একটি ইন্টিজার অ্যারে দেওয়া আছে যার উপাদানগুলো ছোট থেকে বড় ক্রমে সাজানো। এখন একটি অঋণাত্মক সংখ্যা দেওয়া হলে, বলতে হবে যে, অ্যারের যেকোনো দুটি পৃথক সংখ্যার অন্তরফল ওই সংখ্যাটির সমান কী না। অর্থাৎ, অ্যারে 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/, যদিও সমাধান ইতিমধ্যে করে দিয়েছি!   উল্লেখ্য যে, এই ওয়েবসাইটের তথ্যমতে এই প্রশ্নটি ফেসবুকে ইন্টারভিউতে জিজ্ঞাসা করা হয়েছিল।

 

Facebook Comments

ত্রিভুজ গণনা – প্রোগ্রামিং ইন্টারভিউ সমস্যা ৪

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

সমাধানঃ সমস্যাটি নিয়ে চিন্তা করার শুরুতেই একটি বিষয় মাথায় চলে আসবে, “ত্রিভুজের যেকোনো দুই বাহুর সমষ্টি তৃতীয় বাহু অপেক্ষা বৃহত্তর।” এই বিষয়টি কাজে লাগিয়ে আমরা সমস্যাটির সমাধান করতে পারি। আমাদের মূল কোড হবে নিচের মতো –

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

Facebook Comments

তথ্যপ্রযুক্তিতে নারী – ২০১৮ সালের সেরা দশ

অন্যান্য পেশার মত প্রযুক্তি অঙ্গনে নারীদের অংশগ্রহণ কম থাকা সত্ত্বেও, পৃথিবীর কিছু নারী প্রকৌশলীর রয়েছে তথ্যপ্রযুক্তি জগতে বর্নাঢ্য পদচারণা। নিজেদের পেশাজীবন সফল করার পাশাপাশি তাঁরা প্রতিনিয়ত তথ্যপ্রযুক্তিকে নিয়ে যাচ্ছেন কোটি কোটি সাধারণ মানুষের কাছে। সেইসব নারীদের বিশ্বে পরিচয় করিয়ে দেয়ার জন্য প্রতিবছর “বিজনেস ইনসাইডার” পত্রিকা তাঁদের তালিকা প্রকাশ করে। তাহলে দেখে নেয়া যাক ২০১৮ সালে কারা স্থান করে নিয়েছেন সেই তালিকায়ঃ
১. গোয়েন শটওয়েলঃ
শ্রেষ্ঠ নারী প্রকৌশলীর তালিকার প্রথমে জায়গা করে নিয়েছেন স্পেসএক্সের প্রেসিডেন্ট এবং COO গোয়েন শটওয়েল। ২০০২ সালে স্পেসএক্স যাত্রা শুরুর সময় থেকেই তিনি এই প্রতিষ্ঠানের সাথে কর্মরত। ২০০৮ সালে তিনি এই কোম্পানির প্রেসিডেন্টের দায়িত্ব পান। ২০১২ সালের মধ্যে শটওয়েলের সহযোগিতায় স্পেসএক্স প্রথম বেসরকারি অর্থায়নে ইন্টারন্যাশনাল স্পেস ষ্টেশনে মহাকাশযান প্রেরণের মাধ্যমে একটি মাইলফলকের সূচনা করে। তাঁরই নেতৃত্বে স্পেসএক্স প্রথমবারের মত একটি স্যাটেলাইট (বঙ্গবন্ধু-১) পাঠাতে সক্ষম হয়।
গোয়েন শটওয়েল প্রকৌশলীর হওয়ার প্রেরণা পান “সোসাইটি অফ ওম্যান ইঞ্জিনিয়ারস্‌”- এর একটি অনুষ্ঠানে পোশাক-আশাকে সুসজ্জিত একজন মেক্যানিকাল ইঞ্জিনিয়ারের বক্তৃতা শুনে। তখন তাঁর মাত্র ১৫ বছর বয়স। এই সম্পর্কে তিনি বলেন, “তখন আমার মাত্র ১৫ বছর বয়স। অনুষ্ঠানে তাঁর বক্তৃতা শুনে আমি যতটা না মুগ্ধ হই, তারচেয়ে বেশি পছন্দ করি তাঁর স্যুটটিকে। যদিও আমি এই ব্যাপারে কথা বলতে গেলে খুব লজ্জা পাই, তারপরেও বলতে পছন্দ করি এই কারনে যে, এই ঘটনাটির কারণেই আজকে আমি একজন সফল প্রকৌশলী হতে পেরেছি।”
২. প্রিয়া বালাসুব্রামানিয়ামঃ
অ্যাপলের আইফোন অপারেশন্স বিভাগের ভাইস প্রেসিডেন্ট প্রিয়া বালাসুব্রামানিয়াম আছেন তালিকার  চতুর্থ অবস্থানে। তিনি আইফোন উৎপাদনের জন্য Supply Chain তত্ত্বাবধানের পাশাপাশি আইফোনের মূল যন্ত্রাংশগুলোর গুণগতমান এবং ত্রুটি সংশোধনের কাজ পরিচালনা করে থাকেন। ২০০১ সাল থেকে অ্যাপলে কর্মরত এই প্রকৌশলী ২০১৭ সালেও এই তালিকায় ছিলেন।
গত বছর, ২০১৭ সালে তিনি মিশিগান স্টেট ইউনিভার্সিটি থেকে সম্মানসূচক ডক্টরেট ডিগ্রী লাভ করেন, যেখান থেকে প্রিয়া ২০০১ সালে Supply Chain Management এর উপর এমবিএ ডিগ্রী অর্জন করেন। সেখানকার উদ্বোধনি বক্তৃতায় তিনি ক্যারিয়ার শুরুর দিকে তাঁর সংগ্রামের কথা বলেন। একবার এক কোম্পানিতে ইন্টারভিউ দেয়ার সময় তাকে ম্যানাজার বলেছিল, “একটি ফ্যাক্টারি চালানো কোন মেয়ে মানুষের কর্ম নয়। মেয়েরা যা করতে পারে একটি ফ্যাক্টারি চালানো সেসব থেকে অনেক বেশিকিছু”। ভাগ্যিস! প্রিয়া সেইসব নিন্দুকদের কথা শোনেননি।
৩. ডায়ান ব্রায়ান্টঃ 
গুগল ক্লাউডের চিফ অপারেটিং অফিসার (COO) হিসেবে ডায়ান ব্রায়ান্ট যোগাদান করেন ২০১৭ সালের নভেম্বর মাসে। তিনি এর আগে ৩০ বছরেরও বেশি সময় ধরে আরেক টেকজায়ান্ট কোম্পানি ইনটেলের ডাটা সেন্টার গ্রুপে কর্মরত ছিলেন। ইনটেল ছেড়ে গুগলে যাবেন কী না, এই চিন্তা করার জন্য তিনি বেশ কিছুদিন ইনটেল থেকে ছুটি নিয়েছিলেন।
গুগলে তিনি এটিকে সর্ববৃহৎ ক্লাউড কম্পিউটিং সাইট হিসেবে প্রতিষ্ঠিত করার জন্য এবং Amazon এবং Microsoft এর উপরে স্থান দেয়ার জন্য কাজ করে যাচ্ছেন। গৃহহীন কিশোরি থেকে ইঞ্জিনিয়ারিং কলেজে পড়া এবং সেখান থেকে নিজেকে প্রতিষ্ঠিত করার এক অন্যন্য উদাহরণ ডায়ান ব্রায়ান্ট।
৪. ডেনিশ ডুমাসঃ
ডেনিশ ডুমাস “রেড হ্যাট” এর অপারেটিং সিস্টেম প্ল্যাটফর্মের ভাইস প্রেসিডেন্ট হিসেবে কর্মরত। রেড হ্যাট এন্টারপ্রাইজ লিনাক্স, লিনাক্সের সবচেয়ে সফল বাণিজ্যিক সংস্করণ হিসেবে বাজারে প্রচলিত। ডুমাসের টিম এই রেড হ্যাটের বর্তমান সংস্করণগুলোর হালনাগাদ এবং নতুন সংস্করণ তৈরির কাজ করে থাকে। একই সাথে সেই সংস্করণগুলো রেড হ্যাট কোম্পানি এবং কোম্পানির বাইরে ঠিকমত কাজ করছে কিনা সেটি নিশ্চিত করে থাকে।
ডেনিশ ডুমাস অনুপ্রেরণা পান একজন কর্মীকে নতুন কোন পরীক্ষামূলক কাজে সাহায্য করে এবং সেখান থেকে দ্রুত কোন আইডিয়া নিয়ে সেটিকে কাজে লাগানোর মাধ্যমে। অবসর সময়ে তিনি বাগান করতে খুব ভালবাসেন এবং নিজেকে “পাগলা মালী” হিসেবে পরিচয় দিতে পছন্দ করেন।
৫. আঞ্জুল ভামভ্রিঃ
এডোবের ক্লাউড প্ল্যাটফর্ম ইঞ্জিনিয়ারিং বিভাগের ভাইস প্রেসিডেন্ট হিসেবে কাজ করে যাচ্ছেন আঞ্জুল ভামভ্রি। ৩০০ জনের একটি টিমের টিম লীডার হিসেবে তিনি  এডোবের ক্রেতাদের ক্লাউডে ডাটা রাখার মাধ্যমে তাদের ব্যবসায় সহায়তা করে থাকেন। এছাড়াও আঞ্জুলের টিম পরবর্তী প্রজন্মের প্রযুক্তি যেমনঃ কৃত্রিম বুদ্ধিমত্তা এবং মেশিন লার্নিং নিয়ে কাজ করে।
নিজের কাজকে ভালবাসার পাশাপাশি আঞ্জুল কুকুর অনেক পছন্দ করেন। পোজো নামের তাঁর একটি পোষা ল্যাব্রাডর কুকুর আছে। পোজোর সাথে খেলাধুলা এবং হাঁটাহাঁটি করার মধ্য দিয়ে তিনি প্রতিদিন নতুন করে কাজ করা প্রেরণা পান।
৬. জয় চিকঃ 
মাইক্রসফটের ক্লাউড এবং এন্টারপ্রাইজ গ্রুপের কর্পোরেট ভাইস প্রেসিডেন্ট হিসেবে কর্মরত জয় চিক জায়গা করে নিয়েছেন এই তালিকায়। তাঁর নেতৃত্বে মাইক্রসফটে তাঁর টিম অফিস ৩৬৫, এক্সবক্স, এজুরে, উইনডোজ এবং সারফেস-এ এর ব্যবহারকারীদের ডাটার নিরাপত্তার জন্য কাজ করে থাকে। ১৯৯৮ সালে সফটওয়্যার ইঞ্জিনিয়ার হিসেবে মাইক্রসফটে তিনি পা রাখেন। এরপর সেখান থেকে ধীরে ধীরে মাইক্রসফটের উন্নয়ন বিভাগের পরিচালক, ইঞ্জিনিয়ারিং বিভাগের পরিচালক এবং পরবর্তীতে কর্পোরেট ভাইস প্রেসিডেন্টের দায়িত্ব পান।
ভ্রমণপ্রিয় জয় চিক কাজের ফাঁকে ফাঁকে ঘুরে বেড়াতে পছন্দ করেন। তিনি এন্টার্টিকা মহাদেশ ছাড়া বাকি ৬টি মহাদেশের মোট ৬০ টি দেশে ভ্রমণ করেছেন।
৭. ক্যাথি উইন্টারঃ 
 ইনটেলের অটোমেটেড ড্রাইভিং সল্যুশন ডিভিশনের জেনারেল ম্যানেজার এবং ভাইস প্রেসিডেন্ট ক্যাথি উইন্টার দখল করেছেন এই তালিকার ১৭ নম্বর স্থান। ক্যাথি উইন্টার ২০১৬ সালের শেষের দিকে ইনটেলের অটোমেটেড সল্যুশন বিভাগের জেনারেল ম্যানেজার হিসেবে যোগদান করেন। তখন তিনি স্বয়ংক্রিয় গাড়ির বিভিন্ন যন্ত্রাংশের চিপ তৈরির কাজে যুক্ত ছিলেন। এর আগে ডেলফিতে তিনি এই নতুন ধরণের কাজটির সাথে যুক্ত ছিলেন, যেখানে ক্যাথেরিন এবং তাঁর টিম স্বয়ংক্রিয় অর্থাৎ চালকবিহীন গাড়িতে চড়ে ক্যালিফোর্নিয়া থেকে নিউইয়র্কে ৯ দিনের একটি ট্রিপ সম্পন্ন করেন।
ইনটেলে ক্যাথি এ্যাডভান্স ভেহিকেল ল্যাবের কাজ তত্ত্বাবধান করেন। এছাড়াও স্বয়ংক্রিয় গাড়ির পরীক্ষামূলক চালনার কাজ তিনি পরিচালনা করে থাকেন। ক্যাথি বলেন, “আমি ড্রাইভিং এর সময় নিরাপত্তাকে অনেক বেশি প্রাধান্য দিয়ে থাকি। একটি স্বয়ংক্রিয় গাড়ির সুবিধা হলো, এটি চলার সময় বিভ্রান্ত হয় না, কাউকে টেক্সট মেসেজ পাঠায় না এবং উচ্চশব্দে গানও শুনতে পারে না।”
৮. আঁচল গুপ্তাঃ
ফেসবুকের সাইবার সিকিউরিটি বিভাগের পরিচালকের দায়িত্বে আছেন আঁচল গুপ্তা, যেখানে তিনি একাধিক টিমের টিম লীডার হিসেবে ফেসবুককে সুরক্ষিত রাখার কাজ তদারক করেন। এছাড়াও তিনি ফেসবুকের কর্পোরেট অবকাঠামো সুশৃঙ্খল রাখার কাজও করে থাকেন।
আঁচলের সাইবার সিকিউরিটির উপর রয়েছে প্রায় দুই দশকের অভিজ্ঞতা। ফেসবুকে যোগদান করার আগে তিনি স্কাইপের সাইবার সিকিউরিটি বিভাগের চিফ ইনফরমেশন অফিসার হিসেবে কর্মরত ছিলেন। কাজের পাশাপাশি তিনি বৃহত্তর ইকো সিস্টেম সিকিউরিটি এবং গ্রেস হোপার রিভিউ কমিটির সক্রিয় সদস্য।
আঁচল গুপ্তা তাঁর টিমের নারীদের বিভিন্ন সভা সেমিনারে অংশগ্রহণ করা, বক্তৃতা দেয়া এবং নিজেরদের গল্প অন্যদের শোনানোর ব্যাপারে উৎসাহ দিয়ে থাকেন। তিনি মনে করেন , এসব থেকে অন্য মেয়েরাও ভাল কিছু করার অনুপ্রেরণা পায়।
৯. সোফিয়া ভেলাস্টেগুইঃ 
মাইক্রসফটের কৃত্রিম বুদ্ধিমত্তাসম্পন্ন পণ্য বিভাগের জেনারেল ম্যানেজার সোফিয়া ভেলাস্টেগুই জায়গা করে নিয়েছেন এই তালিকায়। দক্ষিন কোরিয়ান নাগরিক সোফিয়ার রয়েছে জর্জিয়া টেক কলেজ অফ ইঞ্জিনিয়ারিং এ একাধিক পেটেন্ট এবং আসন। তিনি ২০১৭ সালে মাইক্রসফটে যোগদান করেন এবং সেখানে কৃত্রিম বুদ্ধিমত্তাসম্পন্ন বিভিন্ন ধরণের পণ্য তৈরি এবং উন্নয়নের কাজ করে থাকেন।
মাইক্রসফটের কৃত্রিম বুদ্ধিমত্তাসম্পন্ন পণ্যের মধ্যে মাইক্রসফট ট্রান্সলেটর এবং মাইক্রসফট কর্টানা ডিজিটাল এ্যাসিস্ট্যান্ট অন্যতম। মাইক্রসফটে যোগদান ক্রয়ার আগে সোফিয়া স্মার্ট হেডফোন কোম্পানি ডপলার ল্যাব, নেস্ট, এ্যালফাবেট স্মার্ট হোম কোম্পানি এবং অ্যাপলে কর্মরত ছিলেন। তিনি মনে করেন, ক্যারিয়ার গড়ার জন্য বিভিন্ন প্রকল্পে কাজ করার পাশাপাশি একই পেশার অন্যান্য মানুষদের সাথে নেটওয়ার্কিং অত্যন্ত গুরুত্বপূর্ণ।
১০. ইয়েল গার্টেনঃ 
অ্যাপলের সিরি ডাটা সায়েন্স এবং এ্যানালাইটিকের পরিচালক ইয়েল গার্টেন, যিনি অ্যাপলের ভয়েস এসিস্ট্যান্ট সিরির ডাটা প্রসেস করে সিদ্ধান্ত প্রদানে সাহায্য করে। ইয়েল এবং তাঁর টিম ডাটা ব্যবহার করে কিভাবে “সিরি”-এর উন্নয়ন এবং কিভাবে এই প্রোগ্রামটিতে আরো নতুন বৈশিষ্ট্য যুক্ত করা যায় সেই কাজ করে থাকেন। ডাটা সায়েন্স নিয়ে কাজ করার ক্ষেত্রে তাঁকে একজন বিশেষজ্ঞ মনে করা হয়।
২০১৭ সালের আগস্ট মাসে অ্যাপলে যোগদান করার আগে গার্টেন লিংকডইনের ডাটা সায়েন্স বিভাগের পরিচালক হিসেবে কর্মরত ছিলেন। সেখানে তিনি ২০১১ সাল থেকে ডাটা সায়েন্স নিয়ে কাজ করে গেছেন। নিজের কাজের মাধ্যমে সাধারণ মানুষের কাছে খুব সহজেই টেকনোলজি পৌঁছে দিতে পারাকেই নিজের সাফল্য হিসেবে বিবেচনা করেন ইয়েল গার্টেন।
লেখকঃ তামান্না নিশাত রিনি।
Facebook Comments

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

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

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

Facebook Comments

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

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

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

Facebook Comments

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 যদি ঋণাত্মক হয় তখন কিন্তু প্রোগ্রামটি কাজ করবে না। এটি ঠিকঠাক করার জন্য আমাদেরকে কী করতে হবে?

Facebook Comments

কেন মাল্টিথ্রেডিং শেখা উচিত

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

কেনো থ্রেড প্রোগ্রামিং সম্পর্কে ধারণা রাখা উচিৎ?

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

এই একাধিক প্রসসের বা সিপিইউয়ের সুবিধাটুকু আমরা তখনই নিতে পারি, যখন এগুলোকে একই সঙ্গে বিভিন্ন কাজে ব্যবহার করতে পারি। যদি সেই সুযোগটা নিতে না পারি, তাহলে আমাদের কম্পিউটারে যে অতিরিক্ত রিসোর্স রাখা আছে, তার অপচয়ই করা হবে বটে।

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

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

আমরা যারা জাভা প্রোগ্রামিং পারি, তারা সহজেই এই মাল্টি থ্রেড প্রোগ্রামিংয়ের সুবিধাটুকু নিতে পারি, যদি একটু কষ্ট করে এর মূলনীতি এবং কীভাবে ব্যবহার করতে হয় তা জেনে নেই।

লেখকঃ আ ন ম বজলুর রহমান, সফটওয়্যার প্রকৌশলী ও লেখক (জাভা প্রোগ্রামিং, জাভা থ্রেড প্রোগ্রামিং)।

Facebook Comments

জাভা থ্রেড প্রোগ্রামিং

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

নিজের লেখা বই হাতে বইমেলায় দ্বিমিক প্রকাশনীর স্টলে লেখক বজলুর রহমান।

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

বজলুরের জাভা প্রোগ্রামিং বইয়ের পাঠকদের কমন প্রশ্ন হলো, বইতে মাল্টিথ্রেডিং নিয়ে আলোচনা করা হয় নি কেন? এরকম প্রশ্ন করার কারণ হচ্ছে, আমাদের দেশের বিশ্ববিদ্যালয়গুলোতে যখন জাভা প্রোগ্রামিং কোর্স করানো হয়, সেখানে মাল্টিথ্রেডিং পড়ানো হয়। যদিও আমি এই কাজটির কোনো যৌক্তিকতা খুঁজে পাই না। ওই কোর্সটির উদ্দেশ্য হচ্ছে অবজেক্ট ওরিয়েন্টেড প্রোগ্রামিং শেখানো, সেখানে মাল্টিথ্রেডিংয়ের মতো অগ্রসর ও জটিল বিষয়ের অবতারণা কেন? তো বজলুরও এই বিষয়ে আমার সঙ্গে একমত আর তাই সে নিজেও এই বিষয়টি জাভা প্রোগ্রামিং বইতে দেওয়ার প্রয়োজনীয়তা অনুভব করে নি। বরং শিক্ষার্থীদের জ্ঞান পিপাসা মেটাতে কেবল থ্রেডিং (বা মাল্টিথ্রেডিং) নিয়ে পুরোদস্তুর একটি বই লিখে ফেলেছে!

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

গত কয়েক বছর ধরে দ্বিমিক কম্পিউটিং ও দ্বিমিক প্রকাশনীর ছত্রছায়ায় আমরা কয়েকজন বাংলা ভাষায় তথ্যপ্রযুক্তির জ্ঞানভান্ডার উন্নয়নে কাজ করছি। যেহেতু বাংলাভাষায় প্রোগ্রামিং ও কম্পিউটার বিজ্ঞানের বিষয়ে তেমন কোনো মানসম্পন্ন কাজ হয় নি, তাই আমি ও অন্য কয়েকজন একেবারে মৌলিক জিনিসপত্র নিয়ে বই লিখে যাচ্ছি। তবে এসব বইয়ের মাঝেও মোঃ মাহবুবুল হাসান (শান্ত)-এর “প্রোগ্রামিং কনটেস্টঃ ডেটা স্ট্রাকচার ও অ্যালগরিদম” এবং শাফায়েত আশরাফের “গ্রাফ অ্যালগরিদম” বইয়ের মতো অপেক্ষাকৃত উচ্চতর বিষয় নিয়ে বই প্রকাশ করেছে দ্বিমিক প্রকাশনী। সেই তালিকায় বজলুরের “জাভা থ্রেড প্রোগ্রামিং” বইটিও একটি গুরুত্বপূর্ণ সংযোজন। এরকম উচ্চ পর্যায়ের টেকনিক্যাল বই আমাদের আরো দরকার।

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

বইটির সর্বোচ্চ বিক্রয়মূল্য ৩২০ টাকা। কিছু কিছু শিক্ষার্থীর কাছে এটি একটু বেশি ঠেকতে পারে, কারণ আমরা পৃষ্ঠা সংখ্যা দিয়ে বইয়ের দাম বিবেচনা করে অভ্যস্ত। কিন্তু আমি বলব যে, এরকম একটি বই লিখতে লেখকের যেই পরিশ্রম হয় তার তুলনায় বইয়ের দাম কিছুই না। আর আমরা বার্গার খেতে গেলে ডবল চিজ (অতিরিক্ত চিজ বা পনিরের স্তর) দিতে বললে বার্গারের দাম যতটুকু বেড়ে যায়, এটি ততটুকুই। তুলনাটি একটু স্থূল হয়ে গেলেও আশা করি সবাই বিষয়টিতে একমত হবে।

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

 

 

 

Facebook Comments