ডেটা স্ট্রাকচার এবং অ্যালগরিদম: প্রোগ্রামারদের জন্য একটি সম্পূর্ণ নির্দেশিকা

ইনফরমটেক ডিজিটাল » মানে » ডেটা স্ট্রাকচার এবং অ্যালগরিদম: প্রোগ্রামারদের জন্য একটি সম্পূর্ণ নির্দেশিকা

অ্যালগরিদম এবং ডেটা স্ট্রাকচার এগুলি দুটি টুকরো যা ধাঁধার মতো একসাথে ফিট করে: একটি সমস্যা সমাধানের পদ্ধতির রূপরেখা দেয় এবং অন্যটি নির্ধারণ করে যে আমরা কোথায় এবং কীভাবে তথ্য সংরক্ষণ করব। যদিও এটি একাডেমিক শোনাতে পারে, এই জোড়াটি আয়ত্ত করা এমন একটি কোডকে আলাদা করে যা কেবল কাজ করে এমন কোড থেকে যা উড়ে যায় এবং ভাঙে না।

আপনি যদি পেশাদার প্রোগ্রামিং করতে চান, টেকনিক্যাল ইন্টারভিউয়ের জন্য প্রস্তুতি নিতে চান, অথবা LeetCode এবং Codewars-এর মতো অনুশীলনের সাথে লড়াই করা বন্ধ করতে চান, তাহলে আপনার একটি শক্ত ভিত্তির প্রয়োজন ডেটা স্ট্রাকচার এবং অ্যালগরিদমএই প্রবন্ধ জুড়ে আপনি দেখতে পাবেন যে সেগুলি কী, কেন সেগুলি এত গুরুত্বপূর্ণ, কোন প্রধান প্রকারগুলি বিদ্যমান, সেগুলি কী কী মৌলিক ক্রিয়াকলাপ সম্পাদন করে এবং পরীক্ষা এবং নির্বাচন প্রক্রিয়ায় সাধারণত কোন প্রশ্নগুলি উপস্থিত হয়।

ডেটা স্ট্রাকচার এবং অ্যালগরিদম কী?

একটি তথ্য কাঠামো এটি মূলত, মেমোরিতে তথ্য সংগঠিত এবং সংরক্ষণের একটি নির্দিষ্ট উপায় যাতে এটি দক্ষতার সাথে পরিচালনা করা যায়। এই সংগঠনটি এলোমেলো নয়: এটি সরাসরি নির্ধারণ করে যে কোন ক্রিয়াকলাপগুলি দ্রুত এবং কোনটি ব্যয়বহুল (সন্নিবেশ, অনুসন্ধান, মুছে ফেলা, ট্র্যাভার্স ইত্যাদি)।

যখন আপনি সঠিক ডেটা স্ট্রাকচার নির্বাচন করেন, তখন আপনার প্রোগ্রাম পরিচালনা করতে পারে ডেটা বৃহত পরিমাণে ঘাম না ভাঙিয়ে; যখন আপনি ভুলভাবে নির্বাচন করেন, তখন একটি ছোট অ্যাপ্লিকেশনও ধীর হয়ে যেতে পারে, অত্যধিক মেমরি গ্রাস করতে পারে, অথবা সময়ের সাথে সাথে বজায় রাখা অসম্ভব হয়ে পড়ে।

একটি অ্যালগরিদম এটি সুনির্দিষ্ট ধাপগুলির একটি সীমিত এবং সুবিন্যস্ত ক্রম যা একটি নির্দিষ্ট সমস্যা সমাধানের জন্য ইনপুটগুলিকে আউটপুটে রূপান্তরিত করে। এটি একটি রান্নার রেসিপির মতো: এটি আপনাকে কী করতে হবে, কোন ক্রমে এবং কোন পরিস্থিতিতে তা বলে, তবে এটি রেফ্রিজারেটরে উপাদানগুলি কীভাবে সংরক্ষণ করবেন তা নিয়ে চিন্তা করে না, যা ডেটা স্ট্রাকচারের অংশ হবে।

কম্পিউটার বিজ্ঞানে, প্রতিটি অ্যালগরিদম সেই ধরণের ডেটার কথা মাথায় রেখে ডিজাইন করা হয় যা এটি কাজ করবে। ডেটা স্ট্রাকচারের পছন্দ কোনও ছোটখাটো বিষয় নয়: কাঠামো এবং অ্যালগরিদম একসাথে চলেএবং দুটি অংশের একটিতে ছোট ছোট পরিবর্তন কর্মক্ষমতা বৃদ্ধি করতে পারে অথবা হ্রাস করতে পারে।

তাত্ত্বিক দৃষ্টিকোণ থেকে, নিক্লাস উইর্থের মতো লেখকরা ১৯৭০-এর দশকের গোড়ার দিকে এই ধারণাটি জনপ্রিয় করে তুলেছিলেন যে অ্যালগরিদম + ডেটা স্ট্রাকচার = প্রোগ্রামদশকের পর দশক ধরে, এটা ঠিক ততটাই সত্য: আপনি জাভা, পাইথন, সি++ প্রোগ্রামিং করেন কিনা বা বুটক্যাম্প থেকে আসেন কিনা তা বিবেচ্য নয়, ইন্টারভিউ এবং গুরুতর প্রকল্পগুলিতে আপনার যা প্রয়োজন তা হল উভয় উপাদানকে কীভাবে ভালভাবে বেছে নিতে হয় এবং একত্রিত করতে হয় তা জানা।

প্রোগ্রামিংয়ে এগুলো এত গুরুত্বপূর্ণ কেন?

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

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

তাদের পক্ষ থেকে, অ্যালগরিদম অনুমতি দেয় দক্ষতার সাথে তথ্য প্রক্রিয়াকরণ করুন: এগুলি সাজান, ফিল্টার করুন, উপাদানগুলি অনুসন্ধান করুন, সর্বোত্তম রুটগুলি সন্ধান করুন, প্যাটার্নগুলি সনাক্ত করুন ডেটা মাইনিং, রিসোর্স অপ্টিমাইজ করা ইত্যাদি। অ্যালগরিদম এবং ডেটা স্ট্রাকচারের সঠিক সমন্বয় খুঁজে পেলে অনেক কঠিন সমস্যাই তুচ্ছ হয়ে যায়।

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

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

পূর্বশর্ত এবং প্রয়োজনীয় ভিত্তি

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

এটি ধারণাটি বুঝতেও অনেক সাহায্য করে অ্যালগরিদমিক জটিলতা এবং বিগ O নোটেশন: ডেটা সাইজ (n) বৃদ্ধির সাথে সাথে এক্সিকিউশন সময় বা মেমোরির ব্যবহার কীভাবে বৃদ্ধি পায়। O(1), O(log n), O(n), O(n log n), এবং O(n²) এর মধ্যে পার্থক্য কীভাবে করতে হয় তা জানা আপনাকে সঠিক বিচারবুদ্ধির সাথে বিকল্পগুলির তুলনা করতে এবং আপনার সিদ্ধান্তগুলিকে ন্যায্যতা দিতে সাহায্য করে।

আরেকটি গুরুত্বপূর্ণ দিক হল, সমস্যা সমাধানস্ট্রাকচার্ড প্রোগ্রামিং অনুশীলন, ছোট ছোট লজিক চ্যালেঞ্জ, সহজ কাতা ইত্যাদি। আপনি যত বেশি আপনার "নাক" কে ধাপে ধাপে সমস্যাটি ভেঙে ফেলার জন্য প্রশিক্ষণ দেবেন, ততই আপনার পক্ষে বোঝা সহজ হবে যে কোন ডেটা স্ট্রাকচার প্রতিটি ক্ষেত্রে উপযুক্ত।

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

অবশেষে, কিছু পরিচিতি বাস্তব-বিশ্বের ব্যবহারিক পরিবেশ (যেমন ছোট ওয়েব প্রকল্প, স্ক্রিপ্ট, অথবা কনসোল অ্যাপ্লিকেশন) আপনাকে প্রতিটি কাঠামোকে সম্পূর্ণরূপে একাডেমিক কিছু হিসেবে দেখার পরিবর্তে, কী জন্য ব্যবহার করতে যাচ্ছেন তা আরও ভালভাবে কল্পনা করতে সাহায্য করে।

সর্বাধিক ব্যবহৃত ডেটা স্ট্রাকচার

কম্পিউটার বিজ্ঞানে অনেক ডেটা স্ট্রাকচার আছেতবে, "মৌলিক" ফাংশনগুলির একটি গ্রুপ আছে যা বারবার পুনরাবৃত্তি করা হয়: অ্যারে (ভেক্টর), স্ট্যাক, সারি, লিঙ্কড লিস্ট, ট্রি, গ্রাফ, ট্রাই এবং হ্যাশ টেবিল। প্রোগ্রামিং কীভাবে কাজ করে, কোন অপারেশনগুলি অফার করে এবং তাদের সাধারণ খরচগুলি বোঝা প্রোগ্রামিং এর মাধ্যমে সুচারুভাবে এগিয়ে যাওয়ার মূল চাবিকাঠি।

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

অ্যারে

অ্যারে এটি সবচেয়ে সহজ রৈখিক ডেটা স্ট্রাকচার এবং সর্বাধিক ব্যবহৃত একটি। এটিতে একটি সংলগ্ন মেমরি ব্লক থাকে যা একই ধরণের উপাদানের একটি সংগ্রহ সংরক্ষণ করে, যা একটি পূর্ণসংখ্যা সূচক দ্বারা অ্যাক্সেসযোগ্য, সাধারণত শূন্য থেকে শুরু হয়।

কল্পনা করুন ৪ নম্বর আকারের একটি অ্যারে যেখানে ১, ২, ৩ এবং ৪ মান রয়েছে। প্রতিটি অবস্থানের একটি icendice (0, 1, 2, 3) এবং আপনি যেকোনো উপাদানকে তার সূচক সহ ধ্রুবক সময়ে O(1) সরাসরি অ্যাক্সেস করতে পারবেন। এটি অ্যারেগুলিকে র্যান্ডম রিডিংয়ের জন্য খুব দক্ষ করে তোলে।

দুটি প্রধান বিভাগ রয়েছে: এক-মাত্রিক অ্যারে (উপাদানের একটি একক সারি) এবং বহুমাত্রিক অ্যারে (উদাহরণস্বরূপ, ম্যাট্রিক্স, যা অ্যারের অ্যারে)। অনেক প্রোগ্রামিং ভাষা স্থানীয়ভাবে অথবা বাক্য গঠন এবং কর্মক্ষমতার ক্ষেত্রে সামান্য পার্থক্য সহ উভয় রূপই অফার করে।

একটি অ্যারের মৌলিক ক্রিয়াকলাপগুলি সাধারণত:

• ঢোকান: একটি নির্দিষ্ট অবস্থানে একটি উপাদান স্থাপন করা, যার মধ্যে স্ট্যাটিক অ্যারেতে অন্যান্য উপাদান স্থানান্তর জড়িত থাকতে পারে।
• পান: একটি নির্দিষ্ট সূচকে উপাদানটি অ্যাক্সেস করা, সাধারণত O(1)।
• মুছে ফেলুন: একটি নির্দিষ্ট অবস্থানে উপাদানটি মুছে ফেলুন বা খালি হিসেবে চিহ্নিত করুন, সাধারণত উপাদানগুলিকে বাম দিকে সরিয়ে।
• আকার: কতগুলি উপাদান সংরক্ষণ করা হয়েছে বা অ্যারের সর্বোচ্চ ধারণক্ষমতা পরীক্ষা করুন।

সাক্ষাৎকার এবং পরীক্ষায়, এই ধরণের অনুশীলন খুবই সাধারণ। একটি অ্যারের দ্বিতীয় সর্বনিম্ন সংখ্যা বের করোপ্রথম অ-পুনরাবৃত্তিমূলক পূর্ণসংখ্যা খুঁজে বের করা, দুটি ইতিমধ্যে সাজানো অ্যারে একত্রিত করা, অথবা নির্দিষ্ট বৈশিষ্ট্য বজায় রেখে ধনাত্মক এবং ঋণাত্মক সংখ্যা পুনর্বিন্যাস করা। এই সবকিছুই সূচক অ্যাক্সেস এবং রৈখিক বা দ্বিগুণ ট্র্যাভার্সালের উপর নির্ভর করে।

স্ট্যাকস

লা পাইলা এটি একটি রৈখিক ডেটা স্ট্রাকচার যা LIFO নীতি অনুসরণ করে: শেষ প্রবেশ, প্রথম আউট। কল্পনা করুন যে বইয়ের একটির উপরে আরেকটি রাখা হয়েছে: আপনি কেবল উপর থেকে বই নিতে বা রাখতে পারবেন।

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

সাধারণ স্ট্যাক অপারেশনগুলি হল:

• ধাক্কা: উপরে একটি নতুন আইটেম ঢোকান।
• পপ: উপরের উপাদানটি বের করে ফিরিয়ে আনুন, স্ট্যাকের আকার কমিয়ে দিন।
• উপরে অথবা উঁকি দিন: উপরের উপাদানটি মুছে না ফেলে দেখুন।
• খালি: ব্যাটারি খালি আছে কিনা তা পরীক্ষা করুন।

সাক্ষাৎকারের প্রেক্ষাপটে, নিম্নলিখিত সমস্যাগুলি দেখা যায়: পোস্টফিক্স নোটেশনে রাশিগুলি মূল্যায়ন করুন (RPN), শুধুমাত্র স্ট্যাক ব্যবহার করে উপাদান বাছাই করা, অথবা পুশ এবং পপ ব্যবহার করে বন্ধনীর একটি স্ট্রিং (এবং অন্যান্য প্রতীক) সঠিকভাবে ভারসাম্যপূর্ণ কিনা তা পরীক্ষা করা।

বাস্তবে, ভাষার অনেক অভ্যন্তরীণ বাস্তবায়ন (উদাহরণস্বরূপ, সিস্টেম কল স্ট্যাক) এই একই নীতি অনুসরণ করে কাজ করে, যদিও আমরা সেগুলি সরাসরি দেখতে পাই না।

সারি

লেজ এটি আরেকটি রৈখিক ডেটা স্ট্রাকচার, কিন্তু LIFO নীতি অনুসরণ করার পরিবর্তে, এটি FIFO মডেল ব্যবহার করে: ফার্স্ট ইন, ফার্স্ট আউট। সবচেয়ে স্পষ্ট উপমা হল সিনেমা হলের টিকিট বুথে অপেক্ষারত মানুষের লাইন।

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

মৌলিক সারি অপারেশনগুলির মধ্যে রয়েছে:

• সারিবদ্ধ: সারির শেষে একটি নতুন আইটেম সন্নিবেশ করান।
• ডেকিউ: শুরুতে অবস্থিত উপাদানটি সরিয়ে ফেরত পাঠান।
• সামনের দিকে অথবা উপরে: প্রথম আইটেমটি না সরিয়েই দেখুন।
• খালি: সারি খালি আছে কিনা তা পরীক্ষা করুন।

প্রোগ্রামিং চ্যালেঞ্জের ক্ষেত্রে, তাদের কাছে আপনাকে জিজ্ঞাসা করা সাধারণ, উদাহরণস্বরূপ, দুটি সারি ব্যবহার করে একটি স্ট্যাক বাস্তবায়ন করুন, বাকি অংশ পরিবর্তন না করেই একটি সারির প্রথম k উপাদানগুলিকে বিপরীত করুন, অথবা সারির FIFO আচরণ ব্যবহার করে 1 থেকে n পর্যন্ত বাইনারি সংখ্যা তৈরি করুন।

মৌলিক লেজ ছাড়াও, এর মতো বৈচিত্র্য রয়েছে বৃত্তাকার লেজ, অগ্রাধিকার সারি বা ডাবল সারি (deque), যা অতিরিক্ত ক্রিয়াকলাপ প্রদান করে এবং নির্দিষ্ট পরিস্থিতিতে কর্মক্ষমতা উন্নত করে।

লিঙ্ক করা তালিকা

লিঙ্কযুক্ত তালিকা একটি লিঙ্কড লিস্টও একটি রৈখিক কাঠামো, কিন্তু অভ্যন্তরীণভাবে এটি অ্যারে থেকে অনেক আলাদা। মেমরির একটি সংলগ্ন ব্লক ব্যবহার করার পরিবর্তে, এটি স্পার্স নোড দিয়ে তৈরি যা রেফারেন্স বা পয়েন্টার দ্বারা একে অপরের সাথে সংযুক্ত থাকে।

প্রতিটি নোডে সাধারণত দুটি অংশ থাকে: তথ্য যেগুলো সংরক্ষণ করতে হবে এবং একটি পয়েন্টার (অথবা একাধিক) যা ক্রমের পরবর্তী নোডের দিকে নির্দেশ করে (এবং, দ্বিগুণ লিঙ্কযুক্ত তালিকার ক্ষেত্রে, পূর্ববর্তীটির দিকেও)। তালিকাটি তার মাথার একটি রেফারেন্সের মাধ্যমে পরিচালিত হয়, যা প্রথম নোডের দিকে নির্দেশ করে, এবং আরও জটিল তালিকায় লেজের একটি রেফারেন্সও বজায় রাখা হয়।

দুটি প্রধান রূপ আছে:

• একক লিঙ্কযুক্ত তালিকা: প্রতিটি নোড কেবল পরবর্তী নোডের দিকে নির্দেশ করে; পথটি সাধারণত একই দিকে থাকে।
• দ্বিগুণ লিঙ্কযুক্ত তালিকাপ্রতিটি নোড পরবর্তী এবং পূর্ববর্তী নোডের দিকে নির্দেশ করে, দ্বিমুখী ট্র্যাভার্সাল এবং আরও দক্ষ মুছে ফেলার ক্রিয়াকলাপগুলিকে সহজতর করে।

লিঙ্কড তালিকার সাধারণ ক্রিয়াকলাপগুলির মধ্যে রয়েছে:

• ইনসার্টঅ্যাটহেড: তালিকার শুরুতে একটি নতুন নোড সন্নিবেশ করান।
• সন্নিবেশ করুনএন্ডে: শেষে একটি নোড যোগ করুন, যদি কিউ থাকে তবে তা আপডেট করুন।
• মুছে ফেলা: একটি নির্দিষ্ট নোড সরান, পার্শ্ববর্তী নোডের পয়েন্টারগুলি সামঞ্জস্য করুন।
• DeleteAtHead সম্পর্কে: প্রথম নোডটি মুছে ফেলুন এবং হেডটি পরবর্তীটিতে সরান।
• সার্চ: একটি নির্দিষ্ট মান খুঁজতে তালিকাটি অতিক্রম করুন।
• খালি: হেডটি নাল কিনা এবং তালিকাটিতে কোনও উপাদান নেই কিনা তা পরীক্ষা করুন।

ক্লাস এবং সাক্ষাৎকারে এই ধরণের সমস্যা প্রচুর। একটি লিঙ্কযুক্ত তালিকা উল্টে দিন, কোন চক্র আছে কিনা তা সনাক্ত করুন (সাধারণত "কচ্ছপ এবং খরগোশ" অ্যালগরিদম ব্যবহার করে), শেষ থেকে গণনা করে নোড N পান, অথবা ডুপ্লিকেট নোডগুলি সরিয়ে ফেলুন, সর্বদা সাবধানে পয়েন্টারগুলি পরিচালনা করুন।

লিঙ্কযুক্ত তালিকাগুলি বাস্তবায়নের জন্য ব্যাপকভাবে ব্যবহৃত হয় চেইনিং সহ হ্যাশ টেবিলগ্রাফে সংলগ্ন তালিকা, এবং গতিশীল ডেটা স্ট্রাকচার যেখানে উপাদানগুলি ঘন ঘন সন্নিবেশ করানো এবং মুছে ফেলা হয়।

Arboles

একটি গাছ এটি একটি শ্রেণিবদ্ধ ডেটা কাঠামো যা প্রান্ত দ্বারা সংযুক্ত নোড দিয়ে তৈরি। সাধারণ গ্রাফের বিপরীতে, একটি গাছের চক্র থাকে না: সর্বদা একটি মূল, সন্তান, পিতামাতা, ভাইবোন, পাতা, স্তর এবং উপবৃক্ষ থাকে, যার একটি "পরিবার" বা "সাংগঠনিক চার্ট" ধরণের সংগঠন থাকে।

আমরা যখন চাই তখন গাছ খুবই কার্যকর শ্রেণিবদ্ধ সম্পর্ক উপস্থাপন করে অথবা একটি সমস্যাকে ছোট ছোট উপ-সমস্যায়ে ভাগ করুন: ফাইল সিস্টেম, মেনু, ব্রাউজারে DOM স্ট্রাকচার, কৃত্রিম বুদ্ধিমত্তায় ডিসিশন ট্রি ইত্যাদি।

গাছের অনেক প্রকারভেদ রয়েছে, যার মধ্যে রয়েছে:

• এন-আরি গাছ: প্রতিটি নোডে একটি পরিবর্তনশীল (এবং সম্ভবত বৃহৎ) সংখ্যক শিশু থাকতে পারে।
• সুষম গাছ: কর্মক্ষমতা হ্রাস এড়াতে শাখাগুলিকে একই গভীরতায় রাখে।
• বাইনারি ট্রি: প্রতিটি নোডে সর্বাধিক দুটি শিশু থাকে (বাম এবং ডান)।
• বাইনারি সার্চ ট্রি (BST): বাইনারি ট্রি যার বৈশিষ্ট্য হল নোডের বাম দিকের সবকিছু ছোট এবং ডান দিকের সবকিছু বড় (কিছু ক্রম মানদণ্ড অনুসারে)।
• AVL গাছ, লাল-কালো, 2-3 এবং অন্যান্য রূপএগুলি হল সুষম অনুসন্ধান গাছ যা সন্নিবেশ, মুছে ফেলা এবং অনুসন্ধান ক্রিয়াকলাপে ভাল জটিলতার সীমা নিশ্চিত করে।

অনুশীলনে, ব্যায়ামের ক্ষেত্রে সবচেয়ে বেশি ঘন ঘন হয় বাইনারি গাছ এবং বাইনারি অনুসন্ধান বৃক্ষসাধারণ সমস্যাগুলির মধ্যে রয়েছে গাছের উচ্চতা গণনা করা, BST-তে k-th সর্বোচ্চ মান খুঁজে বের করা, মূল থেকে একটি নির্দিষ্ট দূরত্বে নোডগুলি তালিকাভুক্ত করা, অথবা একটি নির্দিষ্ট নোডের পূর্বপুরুষ নির্ধারণ করা।

অধিকন্তু, ট্র্যাভার্সাল অ্যালগরিদম (প্রি-অর্ডার, ইন-অর্ডার, পোস্ট-অর্ডার, লেভেল বাই লেভেল) পরবর্তী অনেক প্রক্রিয়ার জন্য মৌলিক: সাজানো মুদ্রণ, এক্সপ্রেশন মূল্যায়ন, ট্রি সিরিয়ালাইজেশন এবং ডিসিরিয়ালাইজেশন ইত্যাদি।

গ্রাফ

একটি গ্রাফ এটি নোডের মধ্যে চক্র এবং একাধিক স্বেচ্ছাসেবী সংযোগের অনুমতি দিয়ে একটি গাছের ধারণাকে সাধারণীকরণ করে। এটি শীর্ষবিন্দু (নোড) এবং প্রান্তের একটি সেট নিয়ে গঠিত যা জোড়া শীর্ষবিন্দুকে সংযুক্ত করে, কখনও কখনও একটি সম্পর্কিত ওজন বা খরচ সহ।

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

কোডে, গ্রাফগুলি সাধারণত দুটি মৌলিক উপায়ে উপস্থাপন করা হয়:

• সংলগ্ন ম্যাট্রিক্স: একটি ম্যাট্রিক্স যেখানে ঘরটি নির্দেশ করে যে শীর্ষবিন্দু i এবং j এর মধ্যে একটি প্রান্ত আছে কিনা (এবং সম্ভবত সংযোগের ওজন)।
• সংলগ্ন তালিকা: প্রতিটি শীর্ষবিন্দুর জন্য তার প্রতিবেশীদের একটি তালিকা সংরক্ষণ করা হয়, যা স্পার্স গ্রাফগুলিতে মেমরি সংরক্ষণ করে।

সবচেয়ে ক্লাসিক ট্র্যাভার্সাল অ্যালগরিদম হল ব্রেডথ-ফার্স্ট সার্চ (BFS) এবং গভীর অনুসন্ধান (DFS)উভয়ই বিভিন্ন সমস্যার জন্য মৌলিক বিল্ডিং ব্লক হিসেবে ব্যবহৃত হয়: একটি গ্রাফ সংযুক্ত কিনা তা পরীক্ষা করা, চক্র সনাক্ত করা, সংযুক্ত উপাদানগুলি খুঁজে বের করা ইত্যাদি।

কারিগরি পরীক্ষায়, BFS এবং DFS বাস্তবায়ন করতে বলা হয়, একটি গ্রাফ একটি গাছ তৈরি করে কিনা তা পরীক্ষা করতে বলা হয়, প্রান্তের সংখ্যা গণনা করতে বলা হয়, অথবা অনুসন্ধান করতে বলা হয় সবচেয়ে ছোট পথ দুটি নোডের মধ্যে (উদাহরণস্বরূপ, শহরের মানচিত্রে) ওজনহীন গ্রাফে Dijkstra বা BFS এর মতো রূপ ব্যবহার করে।

ট্রাই বা প্রিফিক্স ট্রি

ট্রাই (অথবা প্রিফিক্স ট্রি) হল একটি বৃক্ষ-আকৃতির ডেটা স্ট্রাকচার যা অক্ষরের স্ট্রিং পরিচালনার জন্য অপ্টিমাইজ করা হয়, বিশেষ করে শব্দ অভিধান, স্বয়ংসম্পূর্ণ সিস্টেম বা প্রিফিক্স অনুসন্ধানের সাথে কাজ করার সময় কার্যকর।

একটি ট্রাইতে, প্রতিটি নোড সাধারণত একটি অক্ষরকে প্রতিনিধিত্ব করে এবং মূল থেকে নির্দিষ্ট নোডের পথগুলি চিহ্নিত করে সম্পূর্ণ শব্দসাধারণ উপসর্গ থেকে আলাদা করার জন্য, শেষ শব্দের নোডগুলিকে সাধারণত কোনওভাবে চিহ্নিত করা হয় (উদাহরণস্বরূপ, একটি বুলিয়ান সূচক দিয়ে)।

যদি আমরা "top", "thus", এবং "their" শব্দগুলিকে একটি trie-তে সংরক্ষণ করি, তাহলে আমরা একই অক্ষর দিয়ে শুরু হওয়া সকলের জন্য প্রাথমিক পথের কিছু অংশ ভাগ করে নেব, যার ফলে উপসর্গ দ্বারা অনুসন্ধান এবং পরামর্শের সুযোগ থাকবে। খুব কার্যকর সময়, আমরা যে শব্দটি খুঁজছি তার দৈর্ঘ্যের সমানুপাতিক এবং মোট সঞ্চিত শব্দের সংখ্যার সাথে নয়।

সাধারণ অপারেশন এবং চেষ্টার সমস্যাগুলির মধ্যে রয়েছে: কত শব্দ সঞ্চিত আছে তা গণনা করো।, সমস্ত শব্দ অভিধানের ক্রমে মুদ্রণ করুন, একটি অ্যারের উপাদানগুলিকে একটি ট্রাইতে সন্নিবেশ করে সাজান, অক্ষরের একটি সেট থেকে বৈধ শব্দ তৈরি করুন অথবা একটি T9 অভিধানের মতো কাঠামো তৈরি করুন।

সাক্ষাৎকারের প্রেক্ষাপটে, এটি সবচেয়ে মৌলিক কাঠামো নয় যা তারা চাইবে, তবে এটি নিয়মিতভাবে এমন কোম্পানিগুলিতে দেখা যায় যারা অনুসন্ধান, শব্দ প্রক্রিয়াকরণ, অথবা পরামর্শ ব্যবস্থা.

হ্যাশ টেবিল এবং হ্যাশিং

হ্যাশিং এটি এমন একটি কৌশল যার মাধ্যমে প্রতিটি তথ্যের অংশে একটি সংখ্যাসূচক কী (হ্যাশ) নির্ধারণ করা হয়, যাতে আমরা প্রায় স্থির সময়ে উপাদানগুলি সংরক্ষণ এবং পুনরুদ্ধার করতে পারি, সেই কীটিকে একটি অভ্যন্তরীণ কাঠামোতে, সাধারণত একটি অ্যারেতে সূচক হিসাবে ব্যবহার করে।

La হ্যাশ টেবিল এই প্রক্রিয়াটি ব্যবহার করে ডেটা স্ট্রাকচার। প্রতিটি উপাদান একটি কী-মান জোড়া হিসেবে সংরক্ষণ করা হয়: একটি হ্যাশ ফাংশন ব্যবহার করে কীটিকে একটি টেবিল সূচকে রূপান্তরিত করা হয় এবং মান (অথবা এর একটি রেফারেন্স) সেখানে সংরক্ষণ করা হয়। পরে, অনুসন্ধান করার জন্য, কেবল কীটি আবার হ্যাশ করুন এবং সংশ্লিষ্ট অবস্থানে প্রবেশ করুন।

একটি হ্যাশ টেবিলের কর্মক্ষমতা তিনটি বিষয়ের উপর অত্যন্ত নির্ভর করে: হ্যাশ ফাংশন নির্বাচিত (ঘনত্ব এড়াতে আপনাকে অবশ্যই চাবিগুলি ভালভাবে বিতরণ করতে হবে), টেবিলের আকার (অপর্যাপ্ত আকারের কারণে অনেক সংঘর্ষ হয়) এবং সংঘর্ষ পরিচালনার পদ্ধতি (লিঙ্ক করা তালিকার সাথে লিঙ্ক করা, ঠিকানা খোলা, ইত্যাদি)। এটি একটি এর অনুরূপ ডাটাবেসে সূচকযেখানে উপযুক্ত কাঠামোর সিদ্ধান্ত নেওয়ার ফলে অনুসন্ধান এবং অ্যাক্সেস উন্নত হয়।

সাধারণ হ্যাশ প্রোগ্রামিং অনুশীলনের জন্য প্রায়শই প্রয়োজন হয়, উদাহরণস্বরূপ, একটি অ্যারেতে প্রতিসম জোড়া খুঁজুনহ্যাশ টেবিলের আনুমানিক O(1) অনুসন্ধানের সুবিধা গ্রহণ করে পৃথক ফ্লাইট থেকে একটি ভ্রমণের সম্পূর্ণ ভ্রমণপথ পুনর্গঠন করা, একটি অ্যারে অন্যটির উপসেট কিনা তা দ্রুত পরীক্ষা করা, অথবা দুটি অ্যারে বিচ্ছিন্ন কিনা তা যাচাই করা।

বেশিরভাগ আধুনিক ভাষায়, কাঠামো যেমন মানচিত্র, অভিধান, হ্যাশ মানচিত্র বা হ্যাশ সেট তারা অভ্যন্তরীণভাবে হ্যাশ টেবিলের উপর নির্ভর করে, যদিও প্রোগ্রামারকে একটি উচ্চ-স্তরের ইন্টারফেস দেওয়া হয়।

অ্যালগরিদম এবং ডেটা স্ট্রাকচার কীভাবে সম্পর্কিত

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

উদাহরণস্বরূপ, যদি আপনি একটি বৃহৎ সংগ্রহে বারবার কী অনুসন্ধান করতে চান, তাহলে ডেটা সংরক্ষণ করে একটি হ্যাশ টেবিল অথবা বাইনারি অনুসন্ধান বৃক্ষ এটি আপনাকে এমন অনুসন্ধান অ্যালগরিদম ডিজাইন করতে দেয় যা একটি সাধারণ অ-সর্টেড অ্যারে ব্যবহার করার চেয়ে অনেক দ্রুত। একই কথা অগ্রাধিকার সারি এবং হিপগুলির জন্য সময় নির্ধারণ বা সংক্ষিপ্ততম পথ অ্যালগরিদমের ক্ষেত্রেও প্রযোজ্য।

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

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

অতএব, অ্যালগরিদম এবং ডেটা স্ট্রাকচার আয়ত্ত করা কোনও প্রায় অপরিহার্য চাহিদা আজকের চাকরির বাজারে একজন দক্ষ এবং প্রতিযোগিতামূলক প্রোগ্রামার হতে আগ্রহী যে কারো জন্য।

ডেটা স্ট্রাকচার এবং অ্যালগরিদম কীভাবে শিখবেন

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

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

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

একাডেমি এবং প্রশিক্ষণ কেন্দ্রগুলিতে ওয়েব ডেভেলপার বা অ্যাপ্লিকেশন প্রোগ্রামারদের জন্য তাদের প্রোগ্রামের মধ্যে ডেটা স্ট্রাকচার এবং অ্যালগরিদমের উপর নির্দিষ্ট মডিউল অন্তর্ভুক্ত করাও সাধারণ। অনেক ক্ষেত্রে, একটি নির্দিষ্ট পদ্ধতির উপর জোর দেওয়া হয়। খুবই ব্যবহারিক এবং প্রকল্প-ভিত্তিক, ক্রমবর্ধমান অসুবিধার অনুশীলন এবং সাধারণ প্রযুক্তিগত সাক্ষাৎকার সমস্যার সিমুলেশন সহ।

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

সাক্ষাৎকারের প্রস্তুতি নেওয়ার সময়, কেবল কাঠামোগুলিই নয় বরং ব্রুট ফোর্স অ্যালগরিদম এবং সংশ্লিষ্ট ধ্রুপদী অ্যালগরিদম (ট্রাভার্সাল, অনুসন্ধান, বাছাই, সহজ ব্যাকট্র্যাকিং, মৌলিক গতিশীল প্রোগ্রামিং) এবং নিশ্চিত করুন যে আপনি কেন একটি নির্দিষ্ট কাঠামো বেছে নিয়েছেন এবং কী তা জোরে জোরে ব্যাখ্যা করতে পারেন আপনার সমাধানের জটিলতা.

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

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