গণিত

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

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

ফ্লয়েডের সাইকেল ফাইন্ডিং অ্যালগোরিদম

তোমাকে একটা লিংকড লিস্ট দেয়া আছে, বলতে হবে লিংকড লিস্টে কোনো সাইকেল আছে নাকি। এটা খুবই কমন একটা ইন্টারভিউ প্রশ্ন, আমরা ফ্লয়েডের সাইকেল ফাইন্ডিং অ্যালগোরিদম দিয়ে এই সমস্যাটা সমাধান করা শিখবো। ছবির লিংকড লিস্টে দেখা যাচ্ছে ৭ দৈর্ঘ্যের একটা সাইকেল আছে। সাইকেল ডিটেক্ট করার সবথেকে সহজ উপায় হলো ডিকশনারি বা হ্যাশম্যাপ ব্যবহার করা। প্রথম নোড থেকে এক এক ঘর আগাতে হবে এবং প্রতিটা নোডকে ডিকশনারিতে সেভ করে রাখতে হবে। যদি কোনো নোডে গিয়ে দেখা যায় নোডটা আগে থেকেই ডিকশনারিতে আছে তাহলে বুঝতে হবে লিংকড লিস্টটা সাইক্লিক। এই অ্যালগোরিদমের টাইম কমপ্লেক্সিটি আর মেমরি কমপ্লেক্সিটি দুইটাই $O(n)$। ...
Read More

মডুলার অ্যারিথমেটিক

$-১৭$ কে $৫$ দিয়ে ভাগ করলে ভাগশেষ কত হয়? $২^{১০০০}$ কে $১৭$ দিয়ে ভাগ করলে ভাগশেষ কত হয় সেটা কি তুমি ওভারফ্লো এড়িয়ে নির্ণয় করতে পারবে? $O(n)$ এ পারলে $O(\log_2 {n})$ কমপ্লেক্সিটিতে পারবে? যদি কোনো একটি উত্তর "না" হয় তাহলে এই পোস্ট তোমার জন্য। তবে তুমি যদি মডুলার ইনভার্স বা এডভান্সড কিছু শিখতে পোস্টটি খুলো তাহলে তোমাকে আপাতত হতাশ করতে হচ্ছে। সি/জাভা সহ বেশিভাগ প্রোগ্রামিং ল্যাংগুয়েজে এ $\%$ কে ভাগশেষ অপারেটর ধরা হয়। $x$ কে $m$ দিয়ে ভাগকরে ভাগশেষ বের করার অর্থ $x\%m$ এর মান বের করা অথবা আমরা বলতে পারি $x$ কে $m$ দিয়ে mod করা। "determine answer modulo 1000" এ কথাটির অর্থ হলো উত্তরকে...
Read More