ডাটা স্ট্রাকচার

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

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

ব্যাকএন্ড ইঞ্জিনিয়ারিং: এল-আর-ইউ ক‍্যাশ

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

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

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

ডাটা স্ট্রাকচার: কিউ এবং সার্কুলার কিউ

কিউ একটা বেসিক ডাটা স্ট্রাকচার। এটাকে তুমি চিন্তা করতে পারো বাসের লাইনের মত, যে সবার সামনে দাড়িয়ে আছে সে সবার আগে উঠবে, নতুন কোনো যাত্রী আসলে সে লাইনের পিছনে দাড়াবে। কিউতে দুইরকম অপারেশন থাকে। এনকিউ(Enqueue) মানে হলো কিউতে নতুন এলিমেন্ট যোগ করা এবং ডিকিউ(Dequeue) বা পপ মানে হলো সবথেকে পুরোনো এলিমেন্টটা কিউ থেকে সরিয়ে ফেলা। অ্যারে ব্যবহার করে আমরা ফিক্সড সাইজের কিউ ইমপ্লিমেন্ট করতে পারি। আমাদেরকে সবসময় দুইটা পয়েন্টার রাখতে হবে, হেড (Head) পয়েন্টার নির্দেশ করবে কিউয়ের সামনের এলিমেন্টের পজিশন এবং টেইল (Tail) পয়েন্টার নির্দেশ করবে পিছনের এলিমেন্টের পজিশন। একদম শুরুতে Head = -1, Tail ...
Read More

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

তোমাকে একটা লিংকড লিস্ট দেয়া আছে, বলতে হবে লিংকড লিস্টে কোনো সাইকেল আছে নাকি। এটা খুবই কমন একটা ইন্টারভিউ প্রশ্ন, আমরা ফ্লয়েডের সাইকেল ফাইন্ডিং অ্যালগোরিদম দিয়ে এই সমস্যাটা সমাধান করা শিখবো। (If you want to read the same article in english, go to my english blog) ছবির লিংকড লিস্টে দেখা যাচ্ছে ৭ দৈর্ঘ্যের একটা সাইকেল আছে। সাইকেল ডিটেক্ট করার সবথেকে সহজ উপায় হলো ডিকশনারি বা হ্যাশম্যাপ ব্যবহার করা। প্রথম নোড থেকে এক এক ঘর আগাতে হবে এবং প্রতিটা নোডকে ডিকশনারিতে সেভ করে রাখতে হবে। যদি কোনো নোডে গিয়ে দেখা যায় নোডটা আগে থেকেই ডিকশনারিতে আছে তাহলে বুঝতে হবে লিংকড লিস্টটা সাইক্লিক।...
Read More

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

লিংকড লিস্ট বেসিক একটা ডাটা স্ট্রাকচার। আমরা সাধারণত তথ্য রাখার জন্য অ্যারে ব্যবহার করি, তবে অ্যারের কিছু সীমাবদ্ধতা আছে যে কারণে অনেক সময় লিংকড লিস্ট ব্যবহারের দরকার হয়। লিংকড লিস্ট নিয়ে জানতে হলে অবশ্যই পয়েন্টার সম্পর্কে ধারণা থাকতে হবে। লিংক লিস্টের প্রতিটা এলিমেন্ট কে বলবো আমরা নোড। প্রতিটা নোডে সাধারণত দুইটা তথ্য থাকে: ১) যে তথ্যটা আমরা সংরক্ষণ করতে চাচ্ছি ২) পরবর্তি তথ্যটা কোথায় আছে তার ঠিকানা।   ছবিতে দেখা যাচ্ছে প্রথম নোড এ একজন ছাত্রের রোল নম্বর লেখা আছে, এবং পরবর্তি ছাত্রের তথ্য কোন নোড এ আছে সেটা দেখিয়ে দিচ্ছে next নামের একটা পয়েন্টার। দ্বিতীয় নোডটাই শেষ ন...
Read More

ডাটা স্ট্রাকচার : স্ট্যাক

যেকোনো ডাটা স্ট্রাকচার কোর্সে একদম শুরুর দিকে যেসব ডাটা স্ট্রাকচার পড়ানো হয় তার মধ্যে স্ট্যাক অন্যতম। স্ট্যাককে বলা হয় LIFO বা লাস্ট-ইন-ফার্স্ট-আউট ডাটা স্ট্রাকচার। তুমি এভাবে চিন্তা করতে পারো, তোমার কাছে অনেকগুলো বই একটার উপর আরেকটা সাজানো আছে, তুমি চাইলে সবার উপরের বইটা সরিয়ে ফেলতে পারো(Pop), অথবা সবার উপরে আরেকটা বই রাখতে পারো(Push)। এটা হলো বইয়ের একটা স্ট্যাক। তুমি এই স্ট্যাকের উপরে ছাড়া কোনো জায়গায় বই ঢুকাতে পারবে না, উপরের বই ছাড়া কোনো বই সরাতে পারবে না, এগুলো করলে সেটা আর স্ট্যাক থাকবে না। স্ট্যাক হলো কিছু বস্তুর(এলিমেন্ট) একটা সংগ্রহ। এখানে দুইরকম অপারেশন করা যায়: ...
Read More

স্লাইডিং রেঞ্জ মিনিমাম কুয়েরি

মনে করো তোমাকে একটা অ্যারে দেয়া হয়েছে যেখানে $n$ টা সংখ্যা আছে। তোমাকে বলা হলো সেই অ্যারের m=৩ আকারের যতগুলো সাবঅ্যারে আছে সবগুলো থেকে সবথেকে ছোটো সংখ্যাটা বের করতে হবে। যেমন অ্যারেটা যদি হয় ১০,২,৫,৯,৬,৪ তাহলে m=৩ সাইজের সবগুলো সাবঅ্যারে হলো: ১০,২,৫ , সর্বনিম্ন সংখ্যা ২ ২,৫,৯ , সর্বনিম্ন সংখ্যা ২ ৫,৯,৬,  সর্বনিম্ন সংখ্যা ৫ ৯,৬,৪ , সর্বনিম্ন সংখ্যা ৪ তাহলে তোমার আউটপুট হবে [২,৫,৫,৪]। $m$ এর মান ৩ না হয়ে ১ থেকে $n$ পর্যন্ত যেকোনো সংখ্যা হতে পারে। $n$ এর মান যদি ছোটো হয় তাহলে আমরা সহজেই প্রতিটা সাবঅ্যারের উপর লুপ চালিয়ে সমস্যাটা সমাধান করতে পারি। নিচের পাইথন কোডটি দে...
Read More

ডাটা স্ট্রাকচার: বাইনারি ইনডেক্সড ট্রি

বাইনারি ইনডেক্স ট্রি খুবই চমৎকার একটা ডাটা স্ট্রাকচার যার সবথেকে ভালো দিক হলো কয়েক মিনিটেই কোড লিখে ফেলা যায়। আর খারাপ দিক হলো ভিতরে কি হচ্ছে বুঝতে একটু কষ্ট হয়, তবে তুমি লেখাটা মনযোগ দিয়ে পড়লে আমি নিশ্চিত কোন সমস‍্যা হবে না। বাইনারি ইনডেক্সড ট্রি বা BIT এর আরেক নাম হলো ফেনউইক(fenwick) ট্রি। এই লেখাটা পড়ার আগে তোমাকে বিটওয়াইজ অপারেশনগুলো(AND,OR ইত‍্যাদি) সম্পর্কে ভালো জানতে হবে। আমরা একটা সহজ সমস‍্যা সমাধান করতে করতে বাইনারি ইনডেক্স ট্রি সম্পর্কে জানব। এই লেখায় আমরা ধরে নিব অ‍্যারের ইনডেক্স ১ থেকে শুরু, BIT কিভাবে কাজ করে জানার পরে বুঝতে পারবে এটা কেন গুরুত্বপূর্ণ। তোমাকে একটা অ‍...
Read More

লোয়েস্ট কমন অ্যানসেস্টর

লোয়েস্ট কমন অ্যানসেস্টর জিনিসটা শুনতে একটু কঠিন মনে হলেও জিনিসটা সহজ আর খুবই কাজের। বেশ কিছু ধরণের প্রবলেম সলভ করে ফেলা যায় এই অ্যালগোরিদম দিয়ে। আমরা প্রথমে লোয়েস্ট কমন অ্যানসেস্টর বের করার ব্রুটফোর্স অ্যালগোরিদম দেখবো, তারপর স্পার্স টেবিল নামের নতুন একটা ডাটা স্ট্রাকচার শিখে কমপ্লেক্সিটি লগ এ নামিয়ে আনবো। প্রথমেই আমরা জেনে নেই লোয়েস্ট কমন অ্যানসেস্টর বা এল.সি.এ(LCA) কি সেটা। নিচের ছবিটা দেখ:   ছবিতে k আর n নোডের প্যারেন্ট ধরে পিছে যেতে থাকলে তারা i নোডে এসে মিলবে। i হলো k,n এর লোয়েস্ট কমন অ্যানসেস্টর। 'a' ও দুইজনের কমন অ্যানসেস্টর কিন্তু i হলো 'লোয়েস্ট' বা সবথে...
Read More

ডাটা স্ট্রাকচার: ট্রাই (প্রিফিক্স ট্রি/রেডিক্স ট্রি)

ট্রাই বা প্রিফিক্স ট্রি ব্যবহার করে ডাটাবেস থেকে খুব সহজে স্ট্রিং খুজে বের করা যায়। ধরো একটা ফোনবুকে একটা শহরের সব মানুষের ফোন নম্বর রাখা আছে। শহরে মানুষ আছে হয়তো কয়েক লক্ষ্য, কিন্তু প্রতিটা মানুষের নাম সর্বোচ্চ ২০টা অক্ষর ব্যবহার করে লেখা যায়। আমরা এমন একটা ডাটা স্ট্রাকচার ব্যবহার করে নাম খুজবো যে নির্ভর করে শুধু মাত্র নামটিতে কয়টি অক্ষর আছে তার উপর। যেমন "Alice" নামটি খুজতে মাত্র ৫টি অপারেশন করা লাগবে ডাটাবেস যত বড়ই হোক না কেন। এই লেখা পড়ার আগে লিংকড লিস্ট এবং রিকার্সন সম্পর্কে ধারণা থাকতে হবে। ধরো তোমাকে একটা ডিকশনারী দেয়া হলো যেখানে নিচের শব্দগুলো আছে: algo algea also ...
Read More

ডাটা স্ট্রাকচার: সেগমেন্ট ট্রি-২ (লেজি প্রপাগেশন)

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

ডাটা স্ট্রাকচার: সেগমেন্ট ট্রি-১

তুমি হয়তো এরকম প্রবলেম কনটেস্টে দেখেছ, একটি ইন্টিজার অ্যারে দেয়া আছে আর অনেকগুলো কুয়েরি দেয়া আছে। প্রতিটা কুয়েরিতে বলেছে একটা রেঞ্জের মধ্যে সবগুলো সংখ্যার যোগফল বলতে। অ্যারের সাইজ ১০^৫, কুয়েরির সংখ্যাও ১০^৫! বুঝতেই পারছো প্রতি কুয়েরিতে লুপ চালিয়ে যোগফল বের করতে পারবেনা। কিভাবে প্রবলেমটি সলভ করবে? এটা সলিউশন খুব সহজ, তোমাকে কিউমুলেটিভ সাম রাখতে হবে। ধরো একটি অ্যারে আছে sum[MAX], তাহলে sum[i] তে রাখবে ১ থেকে i নম্বর ইনডেক্স পর্যন্ত সবগুলো সংখ্যার যোগফল। i থেকে j পর্যন্ত যোগফল বের করতে দিলে(i<=j) sum[j]-sum[i-1] হবে তোমার উত্তর। বুঝতে না পারলে নিচের উদাহরণটা দেখো: ইনপুট: arr[...
Read More

অ্যারে কম্প্রেশন

খুবই সহজ কিন্তু দরকারি একটা টেকনিক নিয়ে আলোচনা করবো আজকে। STL এর ম্যাপ ব্যবহার করে আমরা অ্যারে কম্প্রেশন করবো। মনে করো কোনো একটা প্রবলেমে তোমাকে বলা হলো একটি অ্যারেতে ১ লাখটা সংখ্যা দেয়া থাকবে যাদের মান হবে ০ থেকে সর্বোচ্চ ১০০০। এখন যেকোনো আমি একটি সংখ্যা বললে তোমাকে বলতে হবে অ্যারের কোন কোন পজিশনে সংখ্যাটি আছে। যেমন মনে করো ইনপুট অ্যারেটা হলো: ১ ০ ০ ২ ৫ ২ ১ ০ ৪ ৫ ১ ২ খুবই সহজ সলিউশন হলো একটি ভেক্টর নেয়া। i তম পজিশনে x সংখ্যাটি পেলে ভেক্টরের x তম পজিশনে পুশ করে রাখবে i। তাহলে ইনপুট নেবার পর ভেক্টরগুলোর চেহারা হবে: [0]->1 2 7 [1]->0 6 10 [2]->3 5 11 [3]->empt...
Read More