প্রোবাবিলিস্টিক ডাটা স্ট্রাকচার: কাউন্ট-মিন স্কেচ

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

ক‍্যাশিং অ‍্যালগরিদম: এল-আর-ইউ ক‍্যাশ

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

প্রোবাবিলিস্টিক ডাটা স্ট্রাকচার: ব্লুম ফিল্টার

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

বাগ ফ্রি কোডিং – অপরিবর্তনীয় বা ইমিউটেবল ভ‍্যারিয়েবল

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

স্কয়ার-রুট ডিকম্পোজিশন

স্কয়ার-রুট ডিকম্পোজিশন টেকনিক ব‍্যবহার করে বেশ কিছু প্রবলেমের টাইম কমপ্লেক্সিটি $O(Sqrt(n))$ এ নামিয়ে আনা যায়। একটা উদাহরণ দিয়ে শুরু করি। ধরা যাক তোমাকে একটা ইন্টিজার অ‍্যারে দেয়া আছে এবং কিছু অপারেশন দেয়া আছে। অপারেশন দুই ধরণের হতে পারে, একটা হলো $[l, r]$ ইনডেক্সের ভিতর সবগুলো সংখ‍্যার যোগ ফল বের করতে হবে, অন‍্যটা হলো i তম ইনডেক্সের মান আপডেট করতে হবে। অনেকে হয়তো সেগমেন্ট ট্রি বা বাইনারি ইনডেক্সড ট্রি ব‍্যবহার করে এটা সমাধান করতে পারবে। আজকে আমরা এটা সমাধান করার আরেকটা নতুন পদ্ধতিতে শিখবো। একেবারেই সাধারণ পদ্ধতিতে আমরা কি করবো? প্রতিবার যোগফল বের করতে বললে $[l, r]$ রেঞ্জে একট...
বিস্তারিত

অবজেক্ট ওরিয়েন্টেড প্রোগ্রামিং: ইন্টারফেস এবং পলিমর্ফিজম

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

টেইল-কল রিকার্শন অপটিমাইজেশন

রিকার্শন ব‍্যবহার করতে গেলে অনেক সময় দেখা যায় রিকার্শনের গভীরতা অনেক বেশি হয় গেলে মেমরি শেষ হয়ে যায় এবং কোড ক্র‍্যাশ করে। আমরা আজকে একটি অপটিমাইজেশন টেকনিক শিখবো যেটা ব‍্যবহার করে কোনো কোনো সময় রিকার্শনের মেমরি ব‍্যবহার অনেক কমিয়ে আনা সম্ভব। প্রথমে জানা দরকার টেইল-কল  (Tail call)  জিনিসটা কি। সহজভাবে বলতে গেলে, টেইল-কল হলো একটা ফাংশনের শেষ লাইন। অর্থাৎ যে কাজটি করার পর ফাংশনের আর কোনো কাজ থাকে না সেটাই টেইল-কল। যেমন নিজের ফাংশনটি দেখ: [crayon-5e87e48f8579b992759891/] এটা ফ‍্যাক্টরিয়াল বের করার একটি ফাংশন। এই ফাংশনে return ans  এর পর  ফাংশনটির আর কোনো কাজ নেই, তাই এটাই হলো টেইল...
বিস্তারিত

ট্রাভেলোকা এবং আমার সফটওয়্যার ইঞ্জিনিয়ারিং এ হাতেখড়ি

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

স্ট্রিং ম্যাচিং: নুথ-মরিসন-প্র্যাট (কেএমপি) অ্যালগরিদম

আজকে আমরা শিখবো কেএমপি (KMP) অ্যালগরিদম ব্যবহার করে স্ট্রিং ম্যাচিং করা। কেএমপি শব্দটি এসেছে ৩জন কম্পিউটার বিজ্ঞানী Donald Knuth, James H. Morris এবং Vaughan Pratt এর নাম থেকে। আমাদের প্রবলেম হলো একটা দুটি স্ট্রিং text এবং pattern দেয়া আছে, আমাদের বলতে হবে text এর ভিতর pattern স্ট্রিংটি সাবস্ট্রিং হিসাবে আছি কিনা। যেমন ধরো টেক্সটটি হলো "MOD", এই স্ট্রিংটার ৬টা সাবস্ট্রিং আছে "M", "O", "D", "MO", "OD" এবং "MOD", এখন যদি pattern = "MO" খুজতে বলে আমরা true রিটার্ন করবো। ব্রুটফোর্স অ্যালগরিদম ব্যবহার করে স্ট্রিং ম্যাচিং করার টাইম কমপ্লেক্সিটি $O(n*m)$, যেখানে $n$ এবং $m$ হলো টেক্সট ও ...
বিস্তারিত

অয়লার ট্যুর (ফ্লিরি এবং হেয়ারহজলার অ্যালগরিদম)

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

হতাশ প্রোগ্রামার

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

কনফিউজড প্রোগ্রামার

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

প্রোবাবিলিটি: এক্সপেক্টেড ভ্যালু

মনে করো তুমি লুডু খেলতে গিয়ে একটা ডাইস বা ছক্কা নিয়ে রোল করছো। এখন তোমার যেকোনো একটা সংখ্যা পাবার প্রোবাবিলিটি কত? বেসিক প্রোবাবিলিটি যদি জেনে থাকো তাহলে তুমি সহজেই বলতে পারবে যে উত্তরটা হলো $\frac{1}{6}$। প্রোবালিটি $\frac{1}{6}$ এর মানেটা কী এখানে? এর মানে হলো, তুমি যদি ছক্কাটা নিয়ে অসীম সংখ্যকব বার খেলতে থাকো তাহলে ছয় ভাগের এক ভাগ বার তুমি $1$ পাবে, অন্য আরেকভাগ বার তুমি $2$ পাবে, অন্য আরেকভাগ বার তুমি $3$ পাবে ইত্যাদি। যেমন তুমি $600$ বার খেললে, $1$ থেকে $6$ পর্যন্ত প্রতিটা সংখ্যা $100$ বার করে পাবে। এটাতো গেলে গাণিতিক হিসাব, বাস্তবে $600$ বার খেলতে গেলে দেখা যাবে প্রতিটা $10...
বিস্তারিত

রবিন-কার্প স্ট্রিং ম্যাচিং

রবিন-কার্প (Rabin-carp) একটি স্ট্রিং ম্যাচিং অ্যালগোরিদম। দুটি স্ট্রিং দেয়া থাকলে এই অ্যালগোরিদমটি বলে দিতে পারে যে ২য় স্ট্রিংটি প্রথম স্ট্রিং এর সাবস্ট্রিং কিনা। রবিন-কার্প রোলিং হ্যাশ টেকনিক ব্যবহার করে স্ট্রিং ম্যাচিং করে। যদিও স্ট্রিং ম্যাচিং এর জন্য কেএমপি অ্যালগোরিদম ব্যবহার করাই ভালো, কিন্তু রবিন-কার্প শেখা গুরুত্বপূর্ণ মূলত রোলিং হ্যাশ কিভাবে কাজ করে সেটা শেখার জন্য। এই লেখাটা পড়ার আগে মডুলার অ্যারিথমেটিক সম্পর্কে জেনে আসতে হবে। স্ট্রিং ম্যাচিং করার সময় প্রথম স্ট্রিং টাকে আমরা বলবো টেক্সট (Text) এবং দ্বিতীয়টিকে প্যাটার্ন (Pattern)। আমাদের কাজ হলো টেক্সট এর মধ্যে প্যাটার্ন...
বিস্তারিত