Priority Queue

প্রায়োরিটি কিউ (Priority Queue)

ঠিক কিউ এর মতই, তবে এর একটি সুন্দর দিক হচ্ছে এটি প্রোগ্রামারের প্রায়োরিটি অনুযায়ী কাজ করে।
ধরি কোন একটি জিনিস নিলামের জন্য ডাকা হল। এখন ক্রেতা অনেক। একেকজন একেক দাম হাঁকছে। ধরলাম ক্রেতা আবির, কালাম, হাসান, মমতাজ যথাক্রমে ১০, ৩০, ১২, ১৪ টাকা দাম ডাকলো। এখন আবির আগে ১০ টাকা ডাকলেও, কালাম কিন্তু ৩০ টাকা ডাকার কারনে তার প্রায়োরিটি বেশি হবে বিক্রেতার কাছে। তাই বিক্রেতা চাবে কালামকে জিনিসটি দিতে। এরপরে কালাম চলে গেলে বেশি প্রায়োরিটি পাবে মমতাজ। প্রায়োরিটি কিউ ঠিক এরকম বিক্রেতার মত আচরন করে। default প্রায়োরিটি কিউ বড় থেকে ছোট ভ্যালু প্রসেস করে। কাজেই এক্ষেত্রে ৩০, ১৪, ১২, ১০ এভাবে ভ্যালুগুলি সাজানো থাকবে কিউতে।
Captureএখন আমরা যদি ছোট থেকে বড় প্রায়োরিটি অনুসারে সাজাতে চাই? তাহলে ব্যাপারটা কি হবে? একটি হিনটস দেইঃ আমরা ইনসার্ট এর সময় ভ্যালুগুলিকে মাইনাস ১ ( -1 ) দিয়ে গুন করে ইনসার্ট করতে পারি। এছাড়াও সর্টিং, কমপ্যারিং এর আরো কিছু মেথড আছে, সেগুলা আমরা পরে অন্য কোন জায়গায় আলোচনা করবো।

Map

ম্যাপ ( Map )

ম্যাপ খুব দরকারি একটি ডাটা স্ট্রাকচার। আমরা অ্যাারে এর কনসেপ্ট থেকে ম্যাপ কে বুঝার চেষ্টা করবো। আমরা অ্যাারে এর ব্যাপার গুলি থেকে যা জানি, অ্যাারে তে 0 থেকে n সংখ্যক কিছু ইনডেক্স থাকে, সেসব ইনডেক্স এ আমরা আমাদের ডাটা টাইপ অনুযায়ী ডাটা রাখি। অতঃপর আমরা অ্যাারে এর ইনডেক্স কে কল করলে, সে ইনডেক্স এ রাখা ডাটা কে খুব সহজে পেয়ে যাই। এটা মোটামুটি অ্যাারে এর ব্যাসিক আইডিয়া। এখন আমরা অ্যাারে এর ইনডেক্স এর জন্য কেবল মাত্র ইন্টিজার নম্বর ব্যবহার করি, অর্থাৎ কোন একটি ইন্টিজার নম্বর এর সাপেক্ষে আমরা ঐ ইনডেক্স এর ভ্যালু পাবো। এক্ষেত্রে এই ইন্টিজার নম্বরগুলি হচ্ছে key or index, আর এরমধ্যে রাখা জিনিসগুলি হচ্ছে value or data.
এখন একটি গল্প দেখা যাক–>
ধরি কোন এক রাজ্যে কোন এক রাজা আছে। রাজার প্রায় ১০০+ বউ আছে, এবং ৩০০+ বাচ্চাকাচ্চাও আছে !! আচ্ছা ব্যাপারটা একটু কেমন দাঁড়ায়। আসলে ইনি রাজা নন, এনাকে আমরা মহারাজা বলবো এখন থেকে 😀 । তো, মহারাজার নাম হচ্ছে সেন্টিনো। সেন্টিনোর মন্ত্রীর নাম লুসিফার। প্রতি মাসের প্রাইম নম্বর এর দিনগুলিতে মহারাজা সেন্টিনো, লুসিফার এর কাছে তার বউ বাচ্চার খবর জানতে চায়। আসলে খবর বলতে সেন্টিনো খালি জানতে চায় অমুক নামের মানুষটি কি তার বউ? নাকি বাচ্চা? ( অনেক বাচ্চাকাচ্চা, বউ, পাইক – পেয়াদা, সৈন্য সবার নাম, পদবী তার মনে থাকেনা, এজন্য মন্ত্রী মশাইয়ের কাছে উনি একেটটি নাম দিয়ে তার পজিশন জিজ্ঞাসা করেন  😛 )। এখন সেন্টিনো খুব বদমেজাজী রাজা। পান থেকে চুন খসলেই গর্দান ফালায়ে দিবে এরকম টাইপ। লুসিফার এর ভয় ,যদি সে উলটাপালটা কোন ইনফরমেশন দেয়, তাহলে তার জীবন ঐদিন ই শেষ 😦 । তো লুসিফার অন্য এক সাম্রাজ্য থেকে তোমাকে ডেকে নিয়ে আসলো এবং মহারাজার এই ব্যাপারটায় সাহা্য্য করতে বললো। সাহায্য না করলে তোমার গর্দান যাবে বলে হুমকিও দিল। মজার কথা হচ্ছে, তুমি যদি ম্যাপ জানো, তাহলে তোমার জন্য এটা পুরা পান্তা ভাত, আর না জানলে তো গর্দান যাবে বুঝতেই পারছো।
এখন মহারাজা একটি একটি করে নাম বলে, এবং তোমাকে বলতে হবে ঐ নামধারী ব্যাক্তি আসলে মহারাজার কি হয়? বউ? বাচ্চা? নাকি অন্য কিছু। যেমন সেন্টিনো জানতে চাইলো, মর্জিনা আমার কি হয়? উত্তর ঃ বউ। এখন তুমি যদি উত্তর দেও যে মর্জিনা আপনার বাচ্চা হয়, এবং মর্জিনা কে ডেকে আনার পর যখন মহারাজা বুঝবে যে তুমি মিথ্যা বলেছো, তুমি ওইখানেই শেষ। ( ধরি হিসাবের সুবিধার্থে, কোন বাচ্চা, বউ, সৈন্য কারো নামের ডুপ্লিকেট কেউ থাকবে না )।
এখন আসি সমাধানে –>
এখন ম্যাপ জানা থাকলে তুমি একটি নাম কে, আরেকটি নাম দিয়ে রিপ্রেসেন্ট করবে। যেমন এখানে মর্জিনা হচ্ছে key, আর বউ হচ্ছে তার value. এখন মর্জিনা, বউ এগুলা তো স্ট্রিং টাইপ, কাজেই আমরা ম্যাপ এভাবে ডিক্লার করতে পারি।
#include <map>
map < string, string > m;
এখানে ম্যাপ আসলে এভাবে থাকে ঃ map < key, value >
তাহলে আমরা m নামের একটি ম্যাপ ডিক্লার করলাম।
এখন আমরা এই ম্যাপ এ ভ্যালু ইনসার্ট করবো।
m [ “Morjina” ] = “Bou“;  // এরমানে হচ্ছে, “Morjina” নামের একটি ইনডেক্স এ “Bou” কে ইনসার্ট করলাম।
cout << m [ “Morjina” ] << endl; // এখানে আউটপুট আসবে ঃ “Bou
আশা করি ব্যাপারটা বুঝে গেছো সবাই। এভাবে আমরা ম্যাপিং এর মাধ্যমে যেকোন ডাটা টাইপ কে যে কোন টাইপ দিয়ে রিপ্রেসেন্ট করতে পারি।
m [ “Sokhina” ] = “Bachcha“;
m [ “Anika” ] = “Bou“;
m [ “Solayman” ] = “Soldier“;
m [ “Lucifer” ] = “Minister“;
m [ “Keka Ferdousi” ] = “Radhuni“;
এরকম ইনসার্ট করার পরে আমরা মহারাজা সেন্টিনোর কথা অনুযায়ী ম্যাপ থেকে খুব সহজেই ডাটা রিট্রিভ করতে পারবো।
যদি ম্যাপ এর সবকিছু আমরা আগের অবস্থায় আনতে চাই, তাহলে map.clear() লিখলে ম্যাপ একদম empty হয়ে যাবে।
ম্যাপ নিয়ে আপাতত এটুকুই। আরো ডিটেইলস জানতে চাইলে তোমরা গুগল করে শিখে নিলে সেটা বেটার হয়।
মহারাজার আজগুবি কাহিনী পড়ার জন্য ধন্যবাদ 😛 

Queue

কিউ(Queue)

কিউ পুরোপুরি স্ট্যাক এর উলটা। এর কাজ করার সিস্টেম হল ঃ First In First Out ( FIFO ).
আমরা কিউ এর উদাহরন এভাবে দিতে পারি, ধরি আমরা বসুন্ধরায় “ভালোবাসা দিবি কিনা বল” মুভি দেখতে গেলাম। আমরা n সংখ্যক বন্ধু বান্ধব মিলে লাইন এ দাড়ালাম টিকেট কিনার জন্য। এই লাইনটিই কিন্তু একটি কিউ। ধরি আমাদের দাড়ানোর সিরিয়ালটি এরকম ঃ তারেক->আমি->জামি->আহানাফ->ইসলাম।
তাহলে কিউ এর একদম প্রথমে আছে তারেক। যখন ওর টিকেট কিনা হয়ে যাবে, ও সামনে দিয়ে লাইন থেকে বের হয়ে যাবে। প্রোগ্রাম এর ভাষায় একে বলে পপ ( pop() ). তাহলে তারেক পপ হবার পরে কিউ এর সামনে থাকবো এখন আমি। এভাবে যে আগে কিউ তে প্রবেশ করবে, সে আগে বের হবে, এটা হল আসল কথা।
কিউ এর জন্য হেডার ফাইল : #include<queue>
int main(){

queue <string> q;
q.push(“Tarek”);  // কিউ তে insert এর জন্য push() ফাংশন
q.push(“Shishir”);
q.push(“Jami”);
q.push(“Ahanaf”);
q.push(“Islam”);

 while ( !q.empty() ){
 cout << q.front() << endl;  // কিউ এর প্রথম এলেমেন্ট প্রিন্ট করলাম
q.pop(); // কিউ এর প্রথম এলেমেন্ট রিমুভ করলাম
}

return 0;
}
প্র্যাকটিস এর জন্য কিছু প্রব্লেম ঃ

১। একটি কিউ এ ১ থেকে ১০০ পর্যন্ত নম্বর পুশ কর এবং এর মধ্যে থেকে কেবল মাত্র জোড় সংখ্যাগুলো প্রিন্ট কর।
২। কিউ তে কতগুলি স্ট্রিং পুশ কর এবং তাদেরকে LIFO আকারে প্রিন্ট কর। (using queue, print the values like stack).

 

String

  স্ট্রিং(String)

স্ট্রিং একটি বেশ মজার এবং কাজের ডাটা স্ট্রাকচার। এর কাজ নরমাল ক্যারেক্টার অ্যারে এর মতই, কিন্তু এর ব্যবহার খুব সহজ এবং অনেক কাজ অনেক সহজে করা যায়। স্ট্রিং এর জন্য হেডার ফাইল : #include<string>
একটি কোড দেখা যাক –>
#include<string>
int main(){
                string a; // স্ট্রিং টাইপ একটি ভ্যারিয়েবল ‘a’ ডিক্লার করলাম
                cin >> a; // user থেকে ইনপুট নিলাম
                cout << a << endl; // ইনপুট এর স্ট্রিং প্রিন্ট করলাম
                return 0;
}
স্ট্রিং এর ক্ষেত্রে এভাবে নিয়ে আমরা স্ট্রিং প্রিন্ট করতে পারি। কিন্তু এখানে স্পেস এর পরে কোন ক্যারেক্টার প্রিন্ট হবেনা। তোমরা ইনপুট নিয়ে দেখতে পারো। এরকম ক্ষেত্রে আমরা তাহলে কি করবো? আমাদের দরকার পুরা একটি লাইন ইনপুট নেয়া। এরজন্য ইনপুট নিতে হবে এভাবে–>
getline ( cin, a );
getline() ফাংশন এর কাজ হচ্ছে লাইন শেষ না হওয়া পর্যন্ত ইনপুট নিবে। এখন আমরা স্পেস সহ ইনপুট নিতে পারবো। উপরের কোড এ cin>>a এর বদলে getline (cin,a) লিখে তোমরা ব্যাপারটা দেখতে পারো।
স্ট্রিং এর মজার ব্যাপার হচ্ছে স্ট্রিং কে আরেক স্ট্রিং এ সরাসরি কপি, অ্যাড করা যায়।

string a,b,c;
a = “I eat rice”;
b = ” and I eat pizza.”;
c = a + b;
cout << c << endl;  // এখানে আউটপুট হবে : “I eat rice and I eat pizza”
সুন্দরভাবে concatanation হয়ে গেলো!! সি তে char array নিয়ে করতে গেলে ব্যাপারটা এত সহজ না।
string.size() ফাংশন স্ট্রিং এর সাইজ রিটার্ন করে (integer).
কোন একটি স্ট্রিং কে উলটা করে লিখার জন্য আমরা এভাবে for loop ব্যবহার কতে পারি–>
string a;
cin >> a;
int len = a.size();
string b = “”; // একটি empty string ডিক্লার করলাম
for ( int i = len-1, pos = 0; i >= 0; i–, pos++ )
b [ pos ] = a [ i ];
cout << b << endl; // রিভার্স করা স্ট্রিংটি ‘b’ এর মধ্যে আছে এখন।
স্ট্রিং একটি নরমাল ডাটা টাইপ (like int,float,double), কাজেই এটাকে আমরা অন্যান্য ডাটা টাইপ লিখার জন্য যেভাবে লিখি, সেভাবে লিখতে পারবো।
স্ট্রিং এর ভেক্টর  : vector < string > vec;
স্ট্রিং এর স্ট্যাক   : stack < string > sec;  এরকম।

স্ট্রিং এর জিনিসগুলি ভালোভাবে রপ্ত করার জন্য তোমরা নিচের সমস্যাগুলি চেষ্টা করতে পারোঃ

১। একটি স্ট্রিং প্যালিন্ড্রম কিনা চেক কর।
example :

hello -> not palindrome
1234321 -> palindrome
wecanacwe ->not palindrome
২। একটি স্ট্রিং দেয়া হবে। যেখানে কেবলমাত্র 0 এবং 1থাকবে। একে ডেসিমাল ভ্যালুতে প্রকাশ কর
example :

00000010 -> the decimal value is 2
111 -> the decimal value is 7
৩। একটি স্ট্রিং এ মোট কতটি ওয়ার্ড আছে এবং কিকি লিখ।
example :

Hello, how are you ?
–> there are 4 words. They are : Hello, how, are, you.

Producing Random Numbers in C

আমরা প্রথমে srand() ফাংশন ব্যবহার করবো, যেটা randomizer কে seed করবে।মূল কথা হল, কম্পিউটার একটি র‍্যানডম নাম্বার তৈরী করবে এমন নাম্বার এর উপর ভিত্তি করে, যেটা srand() ফাংশন এর ভিতর seed হিসাবে দেয়া হবে।এখন আমরা যদি প্রতিবার একই সিড ভ্যালু দেই, তাহলে বারবার একই নাম্বার তৈরী হবে।তাই আমাদের আসলে এমন কিছু করা দরকার যাতে প্রতিবার আমাদের প্রোগ্রাম রান করলে সিড ভ্যালুটি একেকবার একেক রকম হয়। এজন্য আমরা time() ফাংশন ব্যবহার করবো।আমরা time() ফাংশন এর মাধ্যমে প্রতিবার আমাদের কম্পিউটার এর বর্তমান সময়কে সিড হিসেবে srand() এ পাস করবো এবং এর ফলে আমরা প্রতিবার প্রোগ্রাম রান করলে আলাদা আলাদা মান পাবো।
Captureএখানে র‍্যানডম নাম্বার তৈরী হবে ঠিকি, কিন্তু আমরা যদি একটি নির্দিষ্ট রেঞ্জ এর মধ্যে নাম্বার চাই, তাহলে আমাদের rand() কে মড ( modulus ‘%’ ) করতে হবে। যেমন ঃ n % 3 = { 0 , 1 , 2 } এর মধ্যে যে কোন সংখ্যা হবে।
তাই আমরা যদি 0 থেকে n-1 পর্যন্ত সংখ্যার মধ্যে rand() করতে চাই, তাহলে rand() % n দিলেই কাজ হবে 🙂
0 থেকে n এর মধ্যে চাইলে, rand() % (n+1) or rand() % n + 1 দিলেই আমাদের কাজ শেষ।

Intra AUST Preliminary Round (Senior group) Editorial

Contest link : https://www.hackerrank.com/contests/intra-aust-preliminary-round-senior-group/challenges

Diamond lover : Just implement the diamond shape and carefully calculate the spaces between the diamonds.
Easy to solve 1 : From 0 to N, if we X-OR all the integers, we get a binary representation which length is exactly the same length as N. As N is large, using brute force to generate result won’t help. We just need to find the binary representation of N and replace every digit with “1”. The decimal format of that is the answer.
Strength check :  Just check all the information about the password is whether present in the string or not.
Can you solve it? : It’s a bit manipulation problem. If you are familiar with the concept of bit handling it should be easy for you. However, I found a pattern and solved it accordingly. Here is how : Can you solve it?
Longest String : A simple brute force will be enough for the solution. Just implement the code and keep in mind about the alphabetical order.

Can you solve it?

Link : https://www.hackerrank.com/contests/intra-aust-preliminary-round-senior-group/challenges

18449995_1018356501634797_1094689825_n

আমাকে N দেয়া হবে এবং আমার ১ থেকে N পর্যন্ত সব ইন্টিজার এর বাইনারি রিপ্রেসেন্টেশন এ কতটি ১ আছে, তা বলতে হবে। ধরি N = ৮। উপরের চিত্র তে আমি ০ থেকে ৮ পর্যন্ত সংখ্যাগুলির বাইনারি লিখেছি। লক্ষ্য করলে দেখা যায়, এই বাইনারি এর মাঝে একটি নির্দিষ্ট সময় পরপর ১ আসে। প্রথম ঘর এর জন্য একটি ০, একটি ১, এভাবে, দ্বিতীয় ঘরের জন্য দু’টি ০, দু’টি ১, এভাবে… খেয়াল করলে দেখা যায় ব্যাপারটা আসলে ২ এর পাওয়ার হিসেবে আসতে থাকে। আমরা বাইনারি নম্বর এর এই ব্যাপারগুলি অবশ্যি জানি। এখন আমি এই জিনিসটি থেকে একটি প্যাটার্ন বানানোর চেষ্টা করবো।

যেহেতু আমার N জানা আছে, কাজেই প্রথমে N এর বাইনারি বের করে ফেলি। ৮ এর ক্ষেত্রে ১০০০। এখন খেয়াল করি, (ডান দিক থেকে ০ – ৮ সকল নম্বর) প্রথম ঘরে, ০ থেকে ৮ এর মাঝে ১ আছে মোট ৪ টি। দ্বিতীয় ঘরেও ৪ টি, তৃতীয় ঘরেও ৪ টি, চতুর্থ ঘরে ১ টি। মোট ১৩ টি ১ আছে। প্রতি ঘরের জন্য এই ১ এর কাউন্ট টা কিভাবে করবো ? কিছু টেস্টকেস চিন্তা করলে ব্যাপারটা সবার ধরতে পারার কথা। প্যাটার্ন বের করতে পারলে ভালো, নাহলে চিত্রের বামদিকে আমি আমার প্যাটার্ন এর ফরমুলা লিখে দিয়েছি। এখানে xtra জিনিসটি একটু ইম্পরটেন্ট। নরমালি আমরা ১,২,৪,৮,১৬… ২ এর পাওয়ার এর ব্যাপারগুলি সহজে প্যাটার্ন এ ফেলেতে পারি, কিন্তু যদি ৯,১৩,২১,…এরকম নম্বর থাকে, যেটা আসলে কমপ্লিট প্যাটার্ন এর মধ্যে পরে না, তাদের জন্য বারতি কিছু যোগ এর দরকার হয়। ৯ এর জন্য চিন্তা করলে এমনটা দেখা যাবে। যাহোক, এখানে ব্যাপারটা হল N এর বাইনারির length পর্যন্ত আমাকে লুপ চালায়ে আর কিছু ক্যালকুলেশন করে টোটাল কতটি ১ আছে তা বের করতে হবে।