ডেটা স্ট্রাকচার: XOR লিংকড লিস্ট

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

ব্যাকএন্ড ইঞ্জিনিয়ারিং: ডিস্ট্রিবিউটেড ফাইল সিস্টেম

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

অ্যালগরিদম কমপ্লেক্সিটি(বিগ “O” নোটেশন)

তুমি যখন একটা অ্যালগরিদমকে কোডে ইমপ্লিমেন্ট করবে তার আগে তোমার জানা দরকার অ্যালগরিদমটি কতটা কার্যকর। অ্যালগোরিদম লেখার আগে নিজে নিজে কিছু প্রশ্নের উত্তর দিতে হবে,যেমন: ১. আমার অ্যালগোরিদম কি নির্ধারিত সময়ের মধ্যে ফলাফল এনে দিবে? ২. সর্বোচ্চ কত বড় ইনপুটের জন্য আমার অ্যালগোরিদম কাজ করবে? ৩. আমার অ্যালগোরিদম কতখানি মেমরি ব্যবহার করছে? আমরা অ্যালগোরিদমের কমপ্লেক্সিটি বের করে প্রথম দুটি প্রশ্নের উত্তর দিতে পারি। একটি অ্যালগরিদম যতগুলো "ইনস্ট্রাকশন" ব্যবহার করে কাজ করে সেটাই সোজা কথাই সেই অ্যালগোরিদমের কমপ্লেক্সিটি। দুটি নম্বর গুণ করা একটি ইনস্ট্রাকশন, আবার একটি লুপ ১০০ বার চললে সেখান...
বিস্তারিত

ব্যাকএন্ড ইঞ্জিনিয়ারিং: কনসিস্টেন্ট হ্যাশিং

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

ব্যাকএন্ড ইঞ্জিনিয়ারিং: লগ-স্ট্রাকচার্ড-ট্রি

আজকে কথা বলবো ডেটাবেজ বানাতে ব্যবহার করা হয় এমন একটি ডেটা স্ট্রাকচার নিয়ে। সাধারণত ডেটাবেসের সাথে আমাদের পরিচয় হয় Sql ধরণের ট্রানজেকশনাল ডেটাবেজ দিয়ে, যেমন MySQL, PostGreSQL। এসব ডেটাবেসে বি+ ট্রি (B+ Tree) ব্যবহার করে ডেটা সংরক্ষণ করা হয়।  এই লেখায় আমি আলোচনা করবো ডেটাবেজ তৈরি করতে জনপ্রিয় আরেকটি ডেটা স্ট্রাকচার নিয়ে যার নাম লগ-স্ট্রাকচার্ড-ট্রি বা সংক্ষেপে LSM Tree। আগেই বলে নেই, এটা প্রোগ্রামিং কনটেস্টে ব্যবহার করার মত কোন ডেটা স্ট্রাকচার না। তবে সফটওয়্যার ইঞ্জিনিয়ারারদের কেন ডেটা স্ট্রাকচার, অ্যালগরিদম এবং হার্ডওয়্যার নিয়ে জানা দরকার তার একটা উদাহরণ এই LSM Tree। ব্যাকএন্ড ইঞ্জিন...
বিস্তারিত

ডাইনামিক প্রোগ্রামিং ৯ (ট্রি, মিনিমাম ভারটেক্স কভার)

(সবগুলো পর্ব) ডাইনামিক প্রোগ্রামিং দিয়ে ট্রি(Tree) সংক্রান্ত অনেক সমস‍্যার সমাধান করা যায়। সাধারণ গ্রাফে পলিনোমিয়াল টাইমে সমাধান করা যায় না এমন অনেক প্রবলেম ট্রি গ্রাফে সহজেই ডাইনামিক প্রোগ্রামিং দিয়ে সমাধান করা যায় কারণ ট্রি তে কোন সাইকেল থাকে না। এই পর্বে আমরা সেরকমই একটা ক্লাসিক প্রবলেম দেখবো যার নাম মিনিমাম ভারটেক্স কভার। ধরা যাক একটি শহরে কিছু রাস্তা আছে, এখন প্রতি রাস্তায় মোড় বা জাংশনে আমরা পাহারাদার বসাতে চাই। কোনো মোড়ে পাহারাদার বসালে সে মোড়ের সাথে যুক্ত রাস্তাগুলো একাই পাহারা দিতে পারে। এখন তোমাকে বলতে হবে সব কয়টা রাস্তা পাহারা দিতে নূন্যতম কয়জন পাহারাদার দরকার? একট...
বিস্তারিত

ডাইনামিক প্রোগ্রামিং ৮ (বিটমাস্ক, ট্রাভেলিং সেলসম‍্যান)

(সবগুলো পর্ব) বিটমাস্ক ব‍্যবহার করে বেশ কিছু NP-Complete/NP-Hard প্রবলেম সলভ করা যায়। বিটমাস্কের ব‍্যবহার জানা থাকলে এটা তেমন কঠিন কিছু নয়। এই লেখা পড়ার আগে তোমার জানা লাগবে কিভাবে বিট ম‍্যানিপুলেশন করতে হয়, সেজন‍্য তুমি এই লেখাটা পড়তে পারো। এই প্রবলেম সলভ করতে গ্রাফ থিওরি জানার দরকার নেই। আজকে আমরা বিখ‍্যাত ট্রাভেলিং সেলসম‍্যান প্রবলেম বিটমাস্ক দিয়ে সলভ করবো।  প্রবলেমটা হলো তোমাকে কিছু শহর এবং রাস্তা একটা গ্রাফ হিসাবে দেয়া আছে। তোমাকে প্রথম শহর থেকে শুরু করে সবগুলো শহর ঠিক একবার করে ভ্রমণ করে প্রথম শহরে ফিরে আসতে হবে। প্রশ্ন হলো সর্বনিম্ন কত দূরত্ব অতিক্রম করে তুমি কাজটা করতে পারব...
বিস্তারিত

ডাইনামিক প্রোগ্রামিং ৭ (ম‍্যাট্রিক্স চেইন মাল্টিপ্লিকেশন)

(সবগুলো পর্ব) ম‍্যাট্রিক্স চেইন মাল্টিপ্লিকেশন আরেকটা ক্লাসিক ডাইনামিক প্রোগ্রামিং প্রবলেম যেখানে আমাদেরকে বের করতে হবে কিছু ম‍্যাট্রিক্সকে কিভাবে সবথেকে কম অপারেশন ব‍্যবহার করে গুণ করা যাবে।  ডিভাইড এন্ড কনকোয়ার পদ্ধতির খুবই চমৎকার একটা উদাহরণ এই প্রবলেমটা। আমি আশা করবো ম‍্যাট্রিক্স কিভাবে গুণ করতে হয় সেটা সবাই জানো, আমি সেটা নিয়ে বিস্তারিত বলবো না। আমি খালি কয়েকটা প্রোপার্টির কথা মনে করিয়ে দিতে চাই। ধরা যাক আমাদের দুটি ম‍্যাট্রিক্স আছে $A_{1}$ এবং $A_{2}$ এবং তাদের ডাইমেনশন হলো $(r_{1} \times c_{1})$ এবং $(r_{2} \times c_{2})$। $A_{1}$ এবং $A_{2}$ গুণ করা যাবে শুধুমাত্র যদি $...
বিস্তারিত

ডাইনামিক প্রোগ্রামিং ৬ (সাবসেট সাম, কম্বিনেটরিক্স, ডিসিশন প্রবলেম)

আগের পর্বগুলোয় যেসব প্রবলেম দেখেছি তার মধ‍্যে ফিবোনাচ্চি সবগুলোতেই আমাদেরকে কিছু না কিছু ম‍্যাক্সিমাইজ বা মিনিমাইজ করতে হয়। এগুলো ছাড়া ডাইনামিক প্রোগ্রামিং এর আরো কিছু ব‍্যবহার আছে, একটা হলো কোন একটা কাজ কত ভাবে করা যায় সেটা বের করা, আরেকটা হলো ডিসিশন প্রবলেম সলভ করা (অর্থাৎ কোন একটা কাজ করা যাবে কি যাবে না সেটা বের করা)। শুরুতেই দেখবো সাবসেট সাম প্রবলেম। এই প্রবলেমটা অনেকটাই কয়েন চেঞ্জ প্রবলেমের মত, আশা করবো তুমি কয়েন চেঞ্জ নিয়ে লেখাটা পড়ে ফেলেছো, কারণ এবার আমি আগের মত এত বিস্তারিত বর্ণনা করবো না। সাবসেট সাম তোমাকে একটা ইন্টিজার অ‍্যারে $C$ দেয়া আছে এবং একটা ভ‍্যালু $W$ দে...
বিস্তারিত

ডাইনামিক প্রোগ্রামিং ৫ (কয়েন চেঞ্জ, ০-১ ন‍্যাপস‍্যাক)

(আগের পর্ব) আজকে আরো দুটি ক্লাসিকাল ডাইনামিক প্রোগ্রামিং প্রবলেম শিখবো। প্রথমটা হলো কয়েন চেঞ্জ। প্রবলেমটার নাম শুনেই বোঝা যাচ্ছে এটা টাকা ভাংতি করা নিয়ে প্রবলেম, তোমাকে সবথেকে কম সংখ‍্যক কয়েন ব‍্যবহার করে নির্দিষ্ট পরিমাণ টাকা ভাংতি করতে হবে। মনে করো তোমার কাছে $n$ টা ভিন্ন ভিন্ন কয়েন আছে, কয়েনগুলোর ভ‍্যালুকে $C_{0},  C_{1}...C{n-1}$ দিয়ে প্রকাশ করা যায়। আর তোমাকে  একটা অ‍্যামাউন্ট দেয়া আছে $W$। এখন  তোমাকে বলতে সর্বনিম্ন কয়টা কয়েন ব‍্যবহার করে তুমি $W$ অ‍্যামাউন্টটা বানাতে পারবে। প্রতিটা ভ‍্যালুর কয়েন আছে মাত্র ১টা করে। একটা উদাহরণ দেখি। ধরা যাক কয়েনগুলোর ভ‍্যালু হলো $C = \...
বিস্তারিত

ডাইনামিক প্রোগ্রামিং ৪ (লংগেস্ট কমন সাবসিকোয়েন্স)

আগের পর্ব গুলোতে আমরা যেসব প্রবলেম দেখে এসেছি সেগুলোর সাবপ্রবলেমের স্টেট ছিল মাত্র ১টা। এইবার আমরা আরেকটু জটিল সমস‍্যা সমাধান করবো যার নাম লংগেস্ট কমন সাবসিকোয়েন্স বা LCS। এটা শেখার পরে আমি এডিট ডিসটেন্স প্রবলেম নিয়ে অল্প কিছু কথা বলবো এবং তোমার কাজ হবে সেটা নিজে নিজে সমাধান করা। এই প্রবলেমে তোমাকে দুটি স্ট্রিং দেয়া থাকবে $S$ এবং $W$। তোমাকে তাদের মধ‍্যে লংগেস্ট কমন সাবসিকোয়েন্স এর দৈর্ঘ‍্য বের করতে হবে। সাবসিকোয়েন্সের সংজ্ঞাটা মনে করিয়ে দেই, একটা স্ট্রিং থেকে কিছু ক‍্যারেক্টার মুছে দিলে যা বাকি থাকে সেটাই স্ট্রিংটা সাবসিকোয়েন্স। একটা স্ট্রিং এর $2^{n}$ টা সাবসিকোয়েন্স থাকতে পার...
বিস্তারিত

ডাইনামিক প্রোগ্রামিং-৩ (লংগেস্ট ইনক্রিজিং সাবসিকোয়েন্স, পাথ প্রিন্টিং)

আমরা এরই মধ‍্যে ডাইনামিক প্রোগ্রামিং এর বেসিক শিখে গিয়েছি, আমরা ফিবোনাচ্চি এবং DAG এ শর্টেস্ট পাথ বের করতে পারি। এবার আমরা শিখবো Longest Increasing Subsequence বা LIS বের করা। এতদিন আমরা শুধু অপটিমাল সলিউশনটা বের করতে শিখেছি, কোন পথ ধরে সলিউশনে পৌছাতে হয় সেটা বের করা শিখিনি। এবার আমরা নেক্সট-পয়েন্টার ব‍্যবহার করে সেটা বের করাও শিখবো। ধরা যাক আমাদের নিচের ছবির মতো একটা অ‍্যারে আছে যার নাম $A$। একটা অ‍্যারের সাবসিকোয়েন্স বলতে বুঝায় অ‍্যারে থেকে কিছু এলিমেন্ট মুছে দিলে বাকি যে সিকোয়েন্সটা থাকে সেটা। এলিমেন্টগুলোর অর্ডারিং পরিবর্তন করা যাবে না। $n$ সাইজের একটা অ‍্যারের $2^{n}$ টি স...
বিস্তারিত

ডাইনামিক প্রোগ্রামিং-২ (শর্টেস্ট পাথ)

আগের পর্বে আমরা ফিবোনাচ্চি নাম্বার নিয়ে আলোচনা করেছি। আমরা দেখেছি কিভাবে ডাইনামিক প্রোগ্রামিং ব‍্যবহার করে রিকার্সিভলি এবং ইটারেটিভলি ফিবোনাচ্চি সংখ‍্যা জেনারেট করা যায়। এই পর্বে আমরা কথা বলবো শর্টেস্ট পাথ প্রবলেম নিয়ে এবং সেটা নিয়ে আলোচনা করার সময় ডিপির কিছু নতুন প্রোপার্টি নিয়ে জানবো। যদিও শর্টেস্ট পাথ গ্রাফ থিওরির একটা প্রবলেম, এই লেখা বুঝতে গ্রাফ নিয়ে না জানলেও চলবে। মনে করো আমাদেরকে এক শহর থেকে অন‍্য শহরে যাবার শর্টেস্ট পাথ খুজে বের করতে হবে। শহর আছে মোট $n$ টি। $0$ হলো প্রথম শহর, এবং $n - 1$ হলো শেষ শহর। কোন শহর থেকে কোন শহরে সরাসরি যাওয়া যায় এবং শহরগুলোর মধ‍্যে দুরত...
বিস্তারিত

ডাইনামিক প্রোগ্রামিং – ১ (ফিবোনাচ্চি)

ডাইনামিক প্রোগ্রামিং নামটা শুনতে একটু কঠিন মনে হলেও এর পিছনে কনসেপ্টটা বেশ সহজ। ডাইনামিক প্রোগ্রামিং কে এক কথায় বর্ণনা করতে গেলে বলা যায় - একটা সমস‍্যাকে ছোট ছোট ভাগ করে সাব-প্রবলেমগুলো সমাধান করবো তবে একই সাবপ্রবলেম একবারের বেশি সমাধান করবো না। মোটা দাগে বলতে গেলে এটাই ডাইনামিক প্রোগ্রামিং। তবে কখন একটা প্রবলেমকে ডাইনামিক প্রোগ্রামিং দিয়ে সমাধান করা যাবে সেটা বুঝতে একটু অভিজ্ঞতা প্রয়োজন। তো এই সিরিজে আমরা দেখবো ডাইনামিক প্রোগ্রামিং কি এবং কিছু কমন সমস‍্যা যেগুলো ডাইনামিক প্রোগ্রামিং দিয়ে সমাধান করা যায়। ডাইনামিক প্রোগ্রামিং বা ডিপি টার্মটা একটু কনফিউজিং কারণ 'ডাইনামিক' শব্...
বিস্তারিত