গ্রাফ পরিচিতি

খুব সংক্ষেপে গ্রাফের সংজ্ঞা দিতে গেলে আমরা বলতে পারি, গ্রাফ হচ্ছে একটি non-linear data structure. এখন আমাদের মনে প্রশ্ন আসতে পারে যে non-linear data structure বলতে আমরা কি বুঝি। প্রথমত, data structure হল একই data type এর এক বা একাধিক data element এর সমষ্টি। যেমনঃ array, stack, queue etc. এখন linear বা non-linear data structure কি - এই ব্যাপারটিতে আসা যাক। Linear data structure বলতে আমরা সেই সকল data structure কে বুঝি, যাদের element গুলোকে আমরা কোন linear order এ traverse বা access করতে পারি। যেমন, কোন array এর element গুলোকে আমরা index 0 থেকে শুরু করে পরপর শেষ পর্যন্ত traverse করতে পারি। তাই এটি একটি linear data structure. আবার stack এর ক্ষেত্রে আমরা এর top থেকে element গুলো একটির পর একটি access করতে পারি। তাই এটিও একটি linear data structure. বিপরীতভাবে, যেসকল data structure এর element গুলো আমরা কোন linear order এ access করতে পারি না তাদেরকে non-linear data structure বলে। এদের data element গুলোকে access করার জন্য বিভিন্ন রকমের traversal algorithm আছে। যেমন, গ্রাফ traversal algorithm হিসেবে আছে BFS (Breadth First Search), DFS (Depth First Search) ইত্যাদি। 

এখন আসা যাক গ্রাফে data element গুলো কিভাবে সাজানো থাকে - সে বিষয়ে। গ্রাফের দুটি প্রধান বৈশিষ্ট্য হচ্ছে node এবং edge. প্রয়োজনমত আমরা node এবং edge উভয়ের মধ্যেই data রাখতে পারি। সাধারণত আমরা node কে বৃত্ত এবং edge কে রেখাংশ দিয়ে উপস্থাপন করে থাকি। 

সহজে চিহ্নিত করার জন্য কোন গ্রাফের node গুলোকে আমরা 1,2,3,…,n ক্রমিক সংখ্যাগুলো দিয়ে সূচিত করতে পারি। দুটি node এর মধ্যে edge থাকার অর্থ হচ্ছে আমরা একটি node থেকে অপরটিতে যেতে পারি। এভাবে একটি মাত্র edge ব্যবহার করে যদি আমরা একটি node থেকে অপরটিতে যেতে পারি, তবে এরা পরস্পরের adjacent node হবে। অবশ্য যদি edge এ direction দেওয়া থাকে তবে আমরা destination node কে source node এর adjacent node বলবো। উদাহরণস্বরূপ, চিত্র-১ এ আমরা দুটি গ্রাফ দেখতে পাচ্ছি। গ্রাফ-১ এ node-1 এর adjacent node ২টি - node-2 এবং node-3. আবার গ্রাফ-২ এ node-1 এর adjacent node ১টি - শুধু node-2.

               গ্রাফ- ১               গ্রাফ-২

            চিত্র-১

Path: যদি কোন source node থেকে কয়েকটি edge ব্যবহার করে কোন destination node এ যেতে হয়, তবে যাওয়ার সময় visited node গুলোর sequence কে path বলে। যেমন, চিত্র-১ এর গ্রাফ-১ এ node-2 থেকে node-3 যাওয়ার path হচ্ছে 2,1,3. আবার চিত্র-১ এর গ্রাফ-১ এ node-2 থেকে node-3 যাওয়ার কোন path নেই। গ্রাফে দুটি node এর মধ্যে একাধিক path ও থাকতে পারে। উদাহরণস্বরুপ চিত্র-২ এর গ্রাফ-১ এ node-2 থেকে একটি edge ব্যবহার করে node-3 তে যাওয়া যায়, আবার দুটি edge ব্যবহার করে node-1 হয়েও যাওয়া যায়। 

           গ্রাফ- ১                 গ্রাফ-২

        চিত্র-২

Cycle: গ্রাফে cycle হচ্ছে এমন একটি path যেখানে প্রথম এবং শেষ node টি একই হবে, আর বাকি node গুলো একবার করে থাকে। যেমন চিত্র-২ এর গ্রাফ-১ এ node-1 থেকে যাত্রা শুরু করে node-2, node-3 হয়ে আমরা পুনরায় node-1 এ ফিরে আসতে পারি। তাই এখানে 1,2,3,1 একটি cycle. আবার চিত্র-২ এর গ্রাফ-২ এ আমরা কোন node থেকে যাত্রা শুরু করে cycle এর শর্ত মেনে পুনরায় ওই node এ ফিরে আসতে পারব না। তাই এই গ্রাফে কোন cycle নেই। 

Self-loop: যদি গ্রাফে কোন node নিজের সাথে একটি edge দিয়ে যুক্ত হয়, তবে ওই edge আমরা self-loop বলে থাকি। যেমন, চিত্র-৩ এর গ্রাফে node-1 নিজের সাথে একটি self-loop দিয়ে যুক্ত আছে। 

            চিত্র-৩

লিখতে গিয়ে আমার মনে একটা প্রশ্ন জেগে উঠলো, “Self-loop কে আমরা cycle বলতে পারি কি?” প্রশ্নটির উত্তর দেওয়ার আগে আমি আমার প্রিয় পাঠককে বলব, আপনি একটু ভেবে দেখুন তো আপনার কি মনে হয়। আগে থেকে নিজের মনে একটা উত্তর আর সেই উত্তরের স্বপক্ষে যুক্তি ভেবে রাখুন এবং এরপর অগ্রসর হয়ে আপনার উত্তরের সাথে আমার খুঁজে বের করা উত্তরটি মিলিয়ে নিন। 

এই প্রশ্নের উত্তর খুঁজতে হলে আমাদের ফিরে যেতে হবে Cycle এর সংজ্ঞায়। সেখানে বলা আছে cycle এর প্রথম node আর শেষ node একই হবে। এখন self-loop ব্যবহার করে আমরা যখন একটি node থেকে আবার ওই node এ যাই, তখন আমাদের path এর প্রথম node আর শেষ node একই তো থাকে, তাই না? যদি তাই হয় তবে আমরা তো বলতেই পারি যে self-loop ও একটি cycle যার length 1. 

Multiple edges বা Parallel edges: গ্রাফে একটি node থেকে তার adjacent কোন node এ যাওয়ার জন্য একাধিক edge থাকতে পারে। এই ব্যাপারটি multiple edges বা parallel edges বলে। যেমন, চিত্র-৪ এর গ্রাফে node-1 আর node-2 এর মধ্যে ৩টি edge আছে। এটি parallel edges এর একটি উদাহরণ। 

              চিত্র-৪

Discussion or tutorial for 2015-2016 XVI Open Cup, Grand Prix of Bashkortostan, SKB Kontur Cup Stage 2

Discussion or tutorial for 2015-2016 XVI Open Cup, Grand Prix of Bashkortostan, SKB Kontur Cup Stage 2

Problem L - Liesbeth and the String

The observation is if n is even, then after applying n operations we get a string consisting of only (n/2) numbers of 'a'. On the other hand, if the n is odd, then after applying (n+1) operations we get a string consisting of only ( ( (3*(n+1)) / 2) -1) numbers of 'a'. So, we can run a loop and update n until it becomes 1. You may check the idea by writing some testcases on paper. 

My Solution: https://vjudge.net/solution/36427286/mSvEESfhmwF1SloHe7PL 

Imam Hossain Santho's Software Engineering Interview Experience With SELISE

Imam Hossain Santho ভাই আমার ভার্সিটির সিনিয়র। তিনি এপ্রিল, ২০২২ এ  SELISE Digital Platforms কোম্পানিতে Software Engineer পদে যোগদান করেন। তার ইন্টারভিউ অভিজ্ঞতা শুনুন তার মুখ থেকে।

 

"আমি প্রথম LinkedIn এ SELISE এর  Ruby and Rails Developer পজিশন এর জন্য জব সার্কুলার দেখি। জব ডেসক্রিপশন দেখে মোটামুটি মিলে যাওয়ায় তাদের ওয়েবসাইটের Apply অপশন এর মাধ্যমে সিভি জমা দেই।

পাশপাশি আমি SELISE এ কর্মরত একজনের সাথে LinkedIn এর মাধ্যমে পরিচিত হই এবং তাকে সিভি রেফার করতে বলি যেহেতু পরিচিত কেউ সেখানে ছিলো না।

Apply করার প্রায় ১৫ দিনের মধ্যে আমাকে প্রথম ইন্টার্ভিউ এর জন্য HR থেকে কল করে একটি সুবিধাজনক সময় নির্ধারণ করা হয় এবং এর জন্য বিস্তারিত একটি ইমেইল করে তারা।

 

প্রথম ইন্টারভিউটি অনলাইনে এক ঘণ্টা থেকে একটু বেশি সময় ধরে ছিল। ইন্টার্ভিউ এর শুরুটা করেছিল একজন বাংলাদেশী HR, এরপর বাকি ইন্টার্ভিউ Selise Bhutan Team এর সাথে হবে বলে তাদের কাছে কল হ্যান্ডওভার করে দেয়। সেখানে তিনজন ভুটানি ইঞ্জিনিয়ার ছিলেন। পুরো ইন্টারভিউ তাই  ইংরেজিতে হয়। 

সম্পূর্ণ ইন্টারভিউটা মোটামুটি চারটা ছোট ছোট সেশনের মতো হয়েছিলো বলা যায়, যদিও পুরাটা একসাথেই হয়েছিলো। শুরুতে তারা তাদের পরিচয় দেয় এবং আমাকেও নিজের সম্পর্কে বলতে বলা হয়। পরিচয় পর্ব শেষে আমার সিভি দেখে। এখানে আমার CV তে দেয়া কয়েকটি Skill এর উপর নিজেকে ১০ এ কত দিবো জানতে চাওয়া হয়। যেগুলায় বেশি কনফিডেন্ট সেগুলায় ৭-৮, লেস কনফিডেন্ট গুলায় ৫-৬ দিবো এরকম বলি । এরপর Previous Work Experience, কি ধরনের Project এ কাজ করেছি এগুলো নিয়ে জানতে চাওয়া হয়।

 

এরপর হয় জেনারেল সফটওয়্যার ইঞ্জিনিয়ারিং Question Answer part। এই পার্টে তিনজন ইন্টারভিউয়ারই এক দুইটা করে প্রশ্ন করে। প্রথমে ডাটাবেজ থেকে কিছু প্রশ্ন করে, এরপর একটা SQL কুয়েরি লিখতে দেয়া হয়। Raw SQL লিখতে একটু ঝামেলা  হচ্ছিলো,পরে তাদের মধ্যে একজন Hint দিয়ে হেল্প করে। প্রথমেদিকেই ব্যাড পারফরমেন্স এর কারণে একটু নার্ভাস হয়ে গিয়েছিলাম। তারপর Ruby Language, API Design, GraphQL ইত্যাদি নিয়ে কিছু প্রশ্ন করে। SQL ছাড়া অন্য প্রশ্নগুলোর উত্তর ভালভাবে দিতে পেরেছিলাম।

 

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

 

কোডিং রাউন্ড শেষে মোটামুটি তাদেরকে হ্যাপি মনে হইসে এবং আমিও কনফিডেন্স ফিরে পাই। এরপর আমাকে একটি এনালাইটিকাল প্রশ্ন দেয়া হয়। প্রশ্ন টা যদিও ফ্যামিলিয়ার ছিলো, উত্তর সেই মুহূর্তে মনে আসতেছিলো না। আমি চিন্তা করার জন্য একটু সময় চেয়ে নেই, এবং ১-২ মিনিট এর মত brainstorming করার পর উত্তর টা মনে আসে এবং তাদের বলি। উত্তর শুনে মনে হইলো তারা খুব মজা পাইসে। এরপর জেনারেল আরো দুই একটা প্রশ্ন করার পর আমার কোন প্রশ্ন আছে কিনা জানতে চাওয়া হয়। ইন্টার্ভিউয়ার সবাই অনেক ফ্রেন্ডলি ছিলো, শেষদিকে তো Regex নিয়ে প্রশ্ন করায় একটু মজাও করেছিলাম!

তো আমি প্রথমে জানতে চাই আমার ওভারঅল আমার ইন্টার্ভিউ কেমন হইসে এবং পরবর্তী আর কয়াটা রাউন্ড আছে। তারা আমার কমিউনিকেশন স্কিল ভালো বলে জানায় এবং সিলেক্টেড হলে বাকি টা HR শীঘ্রই জানাবে বলে জানায়। এরপর আমি আরো কিছু প্রশ্ন করেছিলাম যেমন হায়ারড হলে কি ধরনের প্রজেক্টে কাজ করবো, কোন টিম এর সাথে কাজ করবো। তারা হাই লেভেলে মোটামুটি একটা আইডিয়া দেয় Selise Bhutan এ project এবং main business নিয়ে। তারা মূলত Selise Bhutan টিম বাংলাদেশে এক্সপান্ড করতে চাচ্ছে বলে জানায়।

 

এর কিছুদিন পর HR থেকে একটি মেইল দেয়া হয় যেখানে আমাকে একটি ছোট প্রজেক্ট এর আইডিয়া দেওয়া থাকে। আমাকে সেটির কোড করে গিটহাব লিঙ্ক ১ সপ্তাহ সময়ের মধ্যে সাবমিট করতে বলা হয়। Requirements PDF এর মধ্যে কয়েকটি মারকিং ক্রাইটেরিয়া উল্লেখ করা হয় যেমন Object Oriented Design, Usage of design patterns, tests & tests quality etc. এটি মূলত একটি CLI Based গেইম এর মতো ছিল। আমি এক সপ্তাহ এর মধ্যে মোটামুটি একটা প্রজেক্ট দাঁড় করাই এবং ডেডলাইন এর দিন সাবমিট করি।

 

এর দুদিন পর আমাকে দ্বিতীয় interview এর জন্য invitation পাঠানো হয়। এই ইন্টাভিউতে নতুন তিনজন ইন্টারভিউয়ার ছিলেন। পরিচয় পর্ব শেষে আমাকে Project টি রান করে দেখাতে বলা হয়। রান করার সময় প্রজেক্ট এ আমার আইডিয়া কি ছিলো এবং এর ফিচার গুলা সম্পর্কে বলি। পাশাপাশি test যেগুলো লিখেছিলাম সেগুলো রান করে দেখাতে বলেছিলেন। তারপর কোড আর্কিটেকচার কিভাবে করেছি এর উপর একটা শর্ট ডিসকাশন এর মতো হয়। তবে কোড নিয়ে খুব বেশি কিছু জিজ্ঞেস করে নাই।

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

 

এর এক সপ্তাহ পর HR থেকে কল করে আমাকে জব অফার করা হয়।"

  

Difference Array

n সাইজের একটি integer array arr[ ] এর difference array diff[ ] এর i তম element হবে diff[i] = arr[i] - arr[i-1]. যেমন,

arr[ ] = { 12, 9, 91, 20 }

diff[ ] = { 12, -3, 82, -71 }

এই diff[] array এর উপর যদি আমরা prefix sum করি, তবে আমরা arr[] টি পাব। উপরের diff[ ] এর উপর prefix sum করার পর প্রাপ্ত array { 12, 9, 91, 20 }.

এই concept এর উপর আমরা এখন একটি সমস্যার ও এর সমাধান দেখবো। আমাদের একটি n সাইজের integer array a[ ] এবং সাথে q সংখ্যক update query দেওয়া আছে। প্রত্যেক update query তে একটি range [ L, R ] ও একটি integer v দেওয়া আছে। আমাদেরকে  a[L] থেকে a[R] পর্যন্ত সবগুলো element এর সাথে v যোগ করতে হবে। এভাবে সবগুলো update query চালানোর পর আমাদেরকে array টি print করতে হবে। 

প্রতি কুয়েরির জন্য [ L, R ] রেঞ্জের সকল element একটি একটি করে update করে আমরা খুব সহজেই O(q*n) সমাধান লিখতে পারি। কিন্তু আমরা difference array এর concept ব্যবহার করে সমস্যাটি O(q+n) এ সমাধান করতে পারি। সেই সমাধানটি এখন আমরা দেখবো। 

প্রথমেই আমরা একটি লুপ ব্যবহার করে array a[ ] এর difference array diff[ ] বের করে নিবো। আমরা একটু আগেই দেখেছি যে কোন array এর difference array এর উপর prefix sum apply করলে সেই array টি পাওয়া যায়। এখন আমরা এই concept টি কাজে লাগাবো। 

diff[0] = a[0]; for( int i=1; i<n; i++){     diff[i] = a[i] - a[i-1]; }

আমরা প্রত্যেক update query range [ L, R ] এর জন্য diff[L] এর সাথে v যোগ করবো এবং diff[R+1] থেকে v বিয়োগ করবো। এর ফলে ভবিষ্যতে আমরা যখন prefix sum করবো তখন এই অতিরিক্ত যোগ করা অংশ L থেকে R range এর সব element এর সাথে যোগ হয়ে যাবে, যেমনটি আমাদের সমস্যায় চাওয়া হচ্ছে। এভাবে প্রত্যেক update query এর জন্য এভাবে update করার পর diff[ ] array কে prefix sum করলেই আমরা ultimate answer array পেয়ে যাবো। 

for( int i=0; i<numberOfQueries; i++){     int L, R, v;    cin>>L>>R>>v;     diff[L] += v;         if(R+1 < n) diff[R+1] -=v; } for( int i=1; i<n; i++)    diff[i] += diff[i-1];

একই আইডিয়া সামান্য আলাদাভাবে কোড করা যায়। এক্ষেত্রে আমরা given array থেকে difference array বানাবো না। (n+1) size এর একটি integer array d[ ] রাখবো। শুরুতে d[ ] এর প্রতিটি element হবে 0. এবার আগের মতোই প্রত্যেক update query range [ L, R ] এর জন্য d[L] এর সাথে v যোগ করবো এবং d[R+1] থেকে v বিয়োগ করবো। এখন d[ ] এর উপর prefix sum করলে d[i] নির্দেশ করবে given array তে a[i] এর সাথে কত যোগ করলে আমরা ultimate answer array পাবো। 

memset(d, 0, sizeof d); for( int i=0; i<numberOfQueries; i++){     int L, R, v;    cin>>L>>R>>v;     d[L] += v;         if(R+1 < n) d[R+1] -=v; } for( int i=0; i<n; i++)    a[i] += d[i];

My software engineering interview experience with Enosis Solutions

আমি Enosis Solutions এর recruitment এর ব্যাপারে জানতে পারি আমার ডিপার্টমেন্টের এক সিনিয়র বড় ভাইয়ের থেকে। আমাদের ক্লাস থেকে যারা সেখানে Software Engineer পদে আবেদন করতে ইচ্ছুক তাদের name, e-mail, contact info ইত্যাদি Enosis Solutions এর HR উনার মাধ্যমে সংগ্রহ করেন। 

অতঃপর HR থেকে আমাকে একটি mail করা হয় এবং রিপ্লাই হিসেবে আমাকে CV পাঠাতে বলা হয়। আমার CV আগেই তৈরি ছিলো। আমি একবার check করে কিছু জিনিস update করে CV পাঠিয়ে দেই। 

HR call করে আমাকে interview এর প্রথম প্রোগ্রামিং সেশনের ব্যাপারে জানান এবং আমাকে নির্ধারিত সময়ের ৫মিনিট আগে থেকেই সেখানে উপস্থিত থাকতে বলেন। পাশাপাশি তিনি এ ব্যাপারে বিস্তারিত একটি mail ও পাঠান। উনি জানান যে প্রোগ্রামিং ল্যাঙ্গুয়েজ হিসেবে আমি শুধু C# ব্যবহার করতে পারবো, যদি syntax ব্যবহারে কোন complication face করা লাগে, সেক্ষেত্রে interviewer আমাকে সহয়তা করবেন। সেশনের দৈর্ঘ্য হবে ১৫ মিনিট এবং এটি অনলাইনে হবে। 

কথামত আমি ৫ মিনিট আগে থেকেই মিটিং এ জয়েন দিয়ে থাকি। Interviewer ও নির্ধারিত সময়ের আগেই চলে আসেন। ছোট করে greetings এর পর তিনি আমাকে স্ক্রিন শেয়ার করতে বলেন, ফেস ক্যাম আগে থেকেই অন ছিলো। এরপর তিনি আমাকে একটি IDE এর লিঙ্ক দেন, যেখানে আমাকে solution code লিখতে হতো। এরপর তিনি আমাকে প্রথম প্রব্লেমের লিঙ্ক দেন ও সেটি explain করে দেন। প্রব্লেমটি ছোট implementation type ছিলো, কিন্তু প্রথম দেখায় আমি optimal কিছু চিন্তা করতে পারিনি। এক মুহূর্তের জন্য মনে হয়েছিলো আমি হয়তো solve করতে পারবো না। কিন্তু কিছুক্ষণ চিন্তা করার পর optimal solution বের করতে পারি। প্রথমটা solve করতে আমার ১০ মিনিটের মতো লেগে যায়। এরপর interviewer আমাকে দ্বিতীয় প্রব্লেমটি দেন। এটি আগেরটির তুলনায় সহজ ছিলো। তাই খুব বেশি কিছু চিন্তা না করেই আমি কোড করে ফেলি। Interviewer আমাকে program রান করে দেখতে বলেন। রান করার পর দেখা গেল কোডে প্রিন্ট করার জন্য যে লুপ ঘুরাচ্ছিলাম সেটি একবার কম ঘুরছিলো। Interviewer আমাকে debug করার সুযোগ দেয়। আমি দ্রুত debug করে আবার রান করি, এবার সঠিক আউটপুট দেখাচ্ছিল। তিনি কোডের ফাইলটি জমা নেন এবং interview সমাপ্ত হয়। 

পরদিন বিকেলে HR আমাকে কল করে জানায় যে আমি পরের ধাপের জন্য নির্বাচিত হয়েছি। এবারের ধাপটি ১:৩০ ঘন্টার প্রোগ্রামিং সেশন। এবারও আমাকে C# এ কোড লিখতে হবে। এই ধাপে অনলাইনে স্ক্রিন কন্ট্রোলের মাধ্যমে interviewer এর PC তে code লিখা লাগে। আমাকে দুটি প্রব্লেম দেওয়া হয় সল্ভ করার জন্য। দুর্ভাগ্যবশত দুটি প্রব্লেমেই আমার statement পড়ে প্রব্লেম বুঝতে অনেক সময় লেগে যায়। 

প্রথম প্রব্লেমটির ইনপুট ফরম্যাট আমি ভুল বুঝে কোড করি। পরে interviewer সেটি বুঝতে পারে এবং প্রব্লেমটি আরেকবার সহজ করে ব্যাখ্যা করেন। প্রব্লেমটি বুঝার সাথেসাথে আমি ঝটপট কোড লিখে ফেলি এবং সেটি সঠিক আউটপুট দেখাচ্ছিল। Interviewer আউটপুট সামান্য পরিবর্তন করে সেটি generate করতে বলেন। আমি কোডে খুব সামান্য modification করেই সেটি করে ফেলি।  

দ্বিতীয় প্রব্লেমের আমি কোড লিখার আগে নিজের সল্যুশন আইডিয়া interviewer এর সাথে শেয়ার করি। কারণ আগের প্রব্লেমে ভুল সল্যুশন implement করতে গিয়ে অনেক সময় নষ্ট হয়েছিলো। তবে এবারও আমার ঝামেলা কম পোহাতে হয় না। ইনপুট class এর object হিসেবে থাকায় আমার মাথায় শুধু object oriented programming approach আসছিলো। Interviewer আমার ভুলটা আলোচনার মাধ্যমে ধরিয়ে দেন এবং ছোট করে একটি hint দিয়ে দেন যে data structure ব্যবহার করতে হতে পারে। কথাটা শুনার সাথে সাথে আমার ব্রেইনে প্রথম যে আইডিয়াটা হিট করে সেটাই correct solution ছিলো। এবারো প্রব্লেম বুঝতে দেরি, কিন্তু কোড করতে দেরি হয় না। একবার রান করেই সঠিক আউটপুট generate করতে পারি।

এই দুটি প্রব্লেমের পর interviewer আরও একটি প্রব্লেম আমাকে মুখে মুখে জিজ্ঞাসা করেন। এটি গ্রাফ সম্পর্কিত একটি classical সমস্যা ছিলো। এ ধরনের সমস্যা আমার সমাধানের পূর্ব অভিজ্ঞতা থাকায় আমি সহজেই সল্যুশন আইডিয়া উনাকে ব্যখ্যা করতে সক্ষম হই। তবে এই প্রব্লেমের difficulty আগের দুটির তুলানায় অনেক high ছিলো। 

Interview শেষে আমি উনার থেকে feedback চাই আমার performance এর ব্যাপারে। উনি খুব উৎসাহের সাথেই feedback দিলেন। বললেন, আমি প্রব্লেমগুলোর সল্যুশন খুব জটিল করে চিন্তা করছিলাম। টাইম ম্যানেজমেন্টের ব্যাপারেও improve করার পরামর্শ দিলেন। আসলে প্রতিটি প্রব্লেমের জন্য ২৫ মিনিট করে বরাদ্দ ছিল, কিন্তু উভয় প্রব্লেমের ক্ষেত্রেই আধা ঘন্টা উপরে সময় লেগেছিলো। Interview শেষ করার পর আমি মোটামুটি শিউর ছিলাম যে জব অফার পাবো, কারণ আমি প্রব্লেম সবগুলোই সল্ভ করতে পেরেছি, হোক না একটু দেরিতে :( . তবে আফসোস একটাই প্রব্লেম বুঝতে দেরি না করলে performance আরও অনেক ভাল হত। 

এক সপ্তাহের মধ্যেই আমাকে HR থেকে কল করা হয়। তিনি আমার academic কার্যকলাপ, উচ্চতর শিক্ষার পরিকল্পনা, ঢাকায় কোথায় জব করছি ও থাকছি, expected salary ইত্যাদি সম্পর্কে জানতে চান। এরপরের এক সপ্তাহের মধ্যে আমি জব অফার পাই। আমি ফেব্রুয়ারি ১, ২০২২ থেকে Enosis Solutions এ জয়েন করি। 

Rubel's full stack web development interview expericence with Namespace IT

Namespace IT তে Full stack web developer পদে আমার বন্ধু Rubel Hossain এর interview expericence শুনুন তারই মুখ থেকে।

"আমি নভেম্বর, ২০২১ এ bdjobs আর facebook এ Namespace IT তে Full stack web developer এর জব সার্কুলার দেখি। Apply করার পরে কোম্পানি থেকে আমাকে ফোন কল দেওয়া হয় এবং কি কি skills আছে, CV তে যা লিখা আছে এর বাইরে কিছু বলার আছে কিনা, expected salary কত এসব সম্পর্কে জানতে চাওয়া হয়। 

প্রায় এক সপ্তাহ পর, এর পরের ধাপে আমাকে একটি project করতে দেওয়া হয় (CRUD operation type, Fullstack). Backend এবং Frontend দুটিই develop করতে বলা হয়। আমি Laravel এবং React ব্যবহার করে project টি করি। Requirement এ আরও বলা ছিল, আমি যদি এটিকে host করতে পারি, তবে বোনাস পয়েন্ট পাবো। Host করার কাজটায় আমার একটু ঝামেলা পোহাতে হয়েছিল, অনেক error আসতেছিল, যা debug করতে হয়েছিল। তবে শেষ পর্যন্ত আমি সফলভাবে এটি host করতে সক্ষম হই। 

এটি করার জন্য আমাকে ৪ দিন সময় দেওয়া হয়, কিন্তু আমি ওদের mail দুইদিন পর দেখি। ফলে আমার হাতে project টি করার জন্য মাত্র দুইদিন সময় ছিল। এই সময়ের মধ্যে project টি শেষ করা challenging ছিলো বটে, আমি ওই দুদিন ঠিকমতো ঘুমাতেও পারিনি। তবে আমার experience থাকায় আমি এটি যথাসময়ে complete করতে পারি। 

প্রজেক্ট সাবমিশনের পর আমাকে পরের ধাপের জন্য কল করা হয়। পরের ধাপটি ছিল face to face interview. এটি তাদের অফিসে হয়। তাদের দেওয়া schedule এ আমি comfortable ছিলাম না, ব্যাপারটি তাদের সাথে শেয়ার করায়, তারা interview তারিখ ৪দিন পিছিয়ে দেয়। 

Interview এর দিন আমি নির্ধারিত সময়ে তাদের অফিসে যাই। একটি doc file এ আমার e-mail id, contact info, expected salary এগুলো collect করে তারা। সাথে রিফ্রেশমেন্টের জন্য চা অফার করা হয় আমাকে।

Face to face interview তে আমাকে judge করার জন্য তিন জন interviewers উপস্থিত ছিলেন। শুরুতে আমাকে আমার CV তে লিখা skills গুলোর উপর questions করা হয়। Questions গুলো খুবই বেসিক ছিল। যেমন, লারাভেল থেকে জিজ্ঞাসা করে faker কি, faker এবং seeder এর মধ্যে পার্থক্য কি। আমি প্রাক্টিক্যাল উদাহরণ দিয়ে সেগুলো তাদের বুঝানোর চেষ্টা করি। React থেকে virtual DOM, single page এগুলো সম্বন্ধে জানতে চাওয়া হয়। এরপর আমাকে javascript এর console log based একটি ছোট question করা হয়। Full Stack development এর পাশাপাশি আমার CV তে উল্লেখ করা ছিলো যে আমি Machine learning নিয়ে অভিজ্ঞ। তাই তারা সেখান থেকে কিছু প্রশ্ন করে আমাকে। যেমন, Feature extraction, Principal Component Analysis ইত্যাদি। Database সম্পর্কিত question ও করা হয়। যেমন, mySQL, PostgreSQL নিয়ে। একটি সহজ programming problem দেওয়া হয়, লুপ আর কন্ডিশনাল লজিক দিয়ে সল্ভ করার মতো। প্রব্লেমটি আমাকে সুন্দরভাবে বুঝিয়ে দেওয়া হয় এবং পরে আমাকে debug করার সুযোগ দেওয়া হয়। আমার একটি লাইভ প্রজেক্ট তারা দেখতে চায়। কিন্তু দুর্ভাগ্যবশত, আমার সেইসময় তাদের দেখানোর মতো কোন লাইভ প্রজেক্ট ছিলো না। 

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

একদিন পর আমার সাথে কোম্পানি থেকে যোগাযোগ করা হয় এবং তারা আমাকে একটি negotiable salary amount অফার করে। আমি negotiation এর মাধ্যমে salary amount বাড়িয়ে নেই। আমি জানুয়ারি, ২০২২ এর ১ তারিখ থেকে তাদের সাথে জয়েন করি।"

Goldbach's Conjecture

Conjecture বা অনুমান হচ্ছে এমন ধারণা যার প্রমাণিত নয়। এ ধরনের অনুমান করা হয় উপলব্ধ তথ্যের উপর ভিত্তি করে। জার্মান গণিতবিদ Christian Goldbach একটি conjecture দেন ১৭৪২ সালে। সেটি ছিলো, 

“যেকোনো জোড় সংখ্যাকে আমরা দুটি মৌলিক সংখ্যার যোগফল হিসেবে লিখতে পারি।” 

সেসময় 1 কে ও  মৌলিক সংখ্যা হিসেবে ধরা হতো। তাই পরবর্তীকালে এই conjecture কে পরিবর্তন করে বলা হয়, 

“2 থেকে বড় যেকোনো জোড় সংখ্যাকে আমরা দুটি মৌলিক সংখ্যার যোগফল হিসেবে লিখতে পারি।”

যেমন, 4 = 2 + 2, 6 = 3 + 3, 8 = 5+ 3 ইত্যাদি। এই conjecture কে বলা হয় Goldbach’s strong conjecture. এই conjecture এর উপর ভিত্তি করে আরও একটি conjecture রয়েছে। সেটি হলো,

“5 থেকে বড় যেকোনো বিজোড় সংখ্যাকে আমরা তিনটি মৌলিক সংখ্যার যোগফল হিসেবে লিখতে পারি।”

এই conjecture টি Goldbach’s strong conjecture এর উপর ভিত্তি করে দেওয়া হয়েছে, তাই এটিকে Goldbach’s weak conjecture বলা হয়। খেয়াল করলে দেখবো, 5 থেকে বড় যেকোনো বিজোড় সংখ্যা n এর জন্য n-3 অবশ্যই 2 থেকে বড় জোড় সংখ্যা হবে। তাহলে আমরা n-3 কে তো দুটি মৌলিক সংখ্যার যোগফল হিসেবে লিখতেই পারছি। এরপর শুধু ওই যোগফলের সাথে 3 যোগ করে দিলেই তো আমরা n পেয়ে যাচ্ছি। 

এবার আমরা এ সম্পর্কিত কিছু সমস্যা দেখবো।

উদাহরণ সমস্যা ১

উৎস: Codeforces Round #324 (Div. 2), Problem D 

সমস্যার Link: https://codeforces.com/problemset/problem/584/D  

একটি বিজোড় সংখ্যা n ( 3 <= n <= 1e9 ) দেওয়া আছে। একে তিন বা তার কম সংখ্যক মৌলিক সংখ্যার যোগফল হিসেবে প্রকাশ করতে হবে। 

n যদি মৌলিক সংখ্যা হয়, তবে একে আর ভাঙার দরকার হবে না। তাই শুরুতে আমরা যাচাই করে নিবো n মৌলিক সংখ্যা কিনা। 

এবার n যদি মৌলিক সংখ্যা না হয়, তাহলে এটি অবশ্যই 9 বা তার চেয়ে বড় হবে। কারণ 3, 5, 7 এরা সবাই মৌলিক সংখ্যা। আমরা 3 কে আউটপুটের একটি  মৌলিক সংখ্যা হিসেবে ধরে নিবো। 

এখন (n-3) হচ্ছে একটি জোড় সংখ্যা এবং 6 <= (n-3) <= 1e9. একটু আগেই তো Goldbach এর conjecture থেকে আমরা দেখলাম এই সীমার মধ্যে জোড় সংখ্যাগুলোকে আমরা দুটি মৌলিক সংখ্যার যোগফল আকারে লিখতে পারি। তাহলে আমরা একটি লুপ চালিয়েই মৌলিক সংখ্যা দুটি বের করতে পারি। 

সমাধান link: https://codeforces.com/contest/584/submission/150913786

অনুরূপভাবে আমরা Timus 1356 সমস্যাটির সমাধান করে ফেলতে পারি।