কোডিং প্যাটার্নস: কোডিং ইন্টারভিউ প্রস্তুতির জন্য একটি বুদ্ধিমান পদ্ধতি

কোডিং সাক্ষাত্কারের জন্য প্রস্তুতি একটি বাস্তব চ্যালেঞ্জ হতে পারে যেখানে বিকাশকারীরা প্রায়শই নতুন উপাদান পর্যালোচনা এবং শেখার জন্য কয়েক সপ্তাহ ব্যয় করে।

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

চলুন ঐতিহ্যগত কোডিং ইন্টারভিউ প্রস্তুতির সাথে যুক্ত কিছু সমস্যা ঘনিষ্ঠভাবে দেখে নেওয়া যাক।

ঐতিহ্যগত ইন্টারভিউ প্রস্তুতির ক্ষতি

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

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

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

এই কৌশলটির সাথে আমার শেষ সমস্যাটি হল যে, দীর্ঘমেয়াদে, এটি আরও চাপ এবং মাথাব্যথা তৈরি করে। আপনি যদি প্রতিবার চাকরি পরিবর্তন করতে চান একই কয়েক সপ্তাহ-ব্যাপী ক্র্যামিং সেশনের মধ্য দিয়ে যেতে হয়, আপনি প্রতিবার সংগ্রাম করতে যাচ্ছেন। আপনি জিনিসগুলি পুনরায় শিখতে এবং আগের মতো একই সমস্যাগুলি সমাধান করতে সপ্তাহগুলি ব্যয় করবেন।

এই চ্যালেঞ্জের পরিপ্রেক্ষিতে, আরও ভাল উপায় থাকতে হবে।

একটি ভাল উপায়: কোডিং নিদর্শন আলিঙ্গন

সুতরাং, কোডিং ইন্টারভিউ প্রস্তুতির জন্য একটি আরো কার্যকর এবং টেকসই পদ্ধতি আছে? উত্তরটি কোডিং প্যাটার্ন বোঝা এবং ব্যবহার করার মধ্যে রয়েছে।

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

কোডিং প্যাটার্নগুলিতে ফোকাস করে, আপনি আপনার ইন্টারভিউ প্রস্তুতিকে উল্লেখযোগ্যভাবে প্রবাহিত করতে পারেন, এটি আরও দক্ষ করে তোলে।

মনে রাখবেন, আরও বুদ্ধিমান প্রস্তুতি নিন, কঠিন নয়।

কি আশা করছ?

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

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

এখন এই কোডিং নিদর্শন মধ্যে ডুব দেওয়া যাক.

1. লিংকড লিস্ট রিভার্সাল

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

এটি একটি লিঙ্কযুক্ত তালিকার সাথে ডিল করার সময় দরকারী এবং সীমাবদ্ধতা হল এটিকে বিপরীতে রাখা।

একটি লিঙ্কযুক্ত তালিকাকে বিপরীত করার প্রক্রিয়াটি নিম্নরূপ:

1. তিনটি ভেরিয়েবল সংজ্ঞায়িত করে শুরু করুন: বর্তমান , পূর্ববর্তী এবং পরবর্তী । লিঙ্ক করা তালিকার প্রধান হিসাবে বর্তমান সেট করুন, এবং পূর্ববর্তী এবং পরবর্তী None হিসাবে আরম্ভ করুন।

2. বর্তমান ভেরিয়েবলটি None না হলেও, নিম্নরূপ এগিয়ে যান:

   1. একটি অস্থায়ী পরিবর্তনশীল মধ্যে পরবর্তী নোড সংরক্ষণ করুন.
   2. পূর্ববর্তী নোডের দিকে নির্দেশ করতে বর্তমান নোডের পয়েন্টারটিকে বিপরীত করুন।
   3. বর্তমান নোড হতে পূর্ববর্তী আপডেট করুন এবং বর্তমানটি পরবর্তী নোড হতে হবে।

3. অবশেষে, বিপরীত তালিকার মাথাটি শেষ নোডে পৌঁছে দিন, যা আগের ভেরিয়েবলে সংরক্ষিত আছে।

প্রধান নির্দেশক:

• আপনাকে একটি লিঙ্ক করা তালিকার উপাদানগুলির ক্রম বিপরীত করতে হবে।
• লিঙ্কযুক্ত তালিকায় প্যালিনড্রোমগুলির জন্য পরীক্ষা করা সমস্যাগুলি জড়িত৷
• আপনি তালিকার মধ্যে একটি নির্দিষ্ট সাবলিস্টে উপাদানের ক্রম বিপরীত করতে চান।

টেমপ্লেট কোড:

পাইথন

 def reverse_linked_list(head): curr = head prev = None while curr: next_node = curr.next curr.next = prev prev = curr curr = next_node return prev

জেএস

 function reverseLinkedList(head) { let curr = head; let prev = null; while (curr) { const nextNode = curr.next; curr.next = prev; prev = curr; curr = nextNode; } return prev; }

জাভা

 public ListNode reverseLinkedList(ListNode head) { ListNode curr = head; ListNode prev = null; while (curr != null) { ListNode nextNode = curr.next; curr.next = prev; prev = curr; curr = nextNode; } return prev; }

2. পরিবর্তিত বাইনারি অনুসন্ধান

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

যদি আপনাকে কখনও একটি সাজানো অ্যারে, লিঙ্কযুক্ত তালিকা বা ম্যাট্রিক্স দেওয়া হয়, তাহলে একটি পরিবর্তিত বাইনারি অনুসন্ধান ব্যবহার করার কথা বিবেচনা করুন।

একটি সাজানো ডেটা স্ট্রাকচারে এই প্যাটার্নটি কীভাবে প্রয়োগ করবেন তার একটি ব্রেকডাউন এখানে রয়েছে:

1. শুরু এবং শেষ অবস্থানের মধ্যে মধ্যবিন্দু চিহ্নিত করে শুরু করুন। সম্ভাব্য পূর্ণসংখ্যা ওভারফ্লো এড়াতে, নিম্নরূপ মধ্যম গণনা করা নিরাপদ: middle = start + (end - start) / 2 ।
2. মাঝামাঝি সূচকের উপাদানটির সাথে কীটি মেলে কিনা তা পরীক্ষা করুন। যদি তা হয়, ফলাফল হিসাবে মধ্যম সূচকটি ফেরত দিন।
3. যদি কীটি মধ্যম সূচকের উপাদানের সাথে মেলে না, তাহলে পরবর্তী ধাপে যান।
4. সূচী মাঝামাঝি এলিমেন্টের চেয়ে কীটি কম কিনা তা মূল্যায়ন করুন। যদি তা হয়, শেষ থেকে মাঝামাঝি আপডেট করে আপনার অনুসন্ধানের পরিসর সংকুচিত করুন - 1 ।
5. বিপরীতভাবে, যদি কীটি সূচী মধ্যম এলিমেন্টের চেয়ে বড় হয়, তাহলে স্টার্ট + 1- এ আপডেট করে আপনার সার্চ রেঞ্জ সামঞ্জস্য করুন।

প্রধান নির্দেশক:

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

টেমপ্লেট কোড:

পাইথন

 def binary_search(arr: List[int], target: int) -> int: left, right = 0, len(arr) - 1 first_true_index = -1 # Perform binary search until left and right pointers meet while left <= right: mid = (left + right) // 2 if feasible(mid): # If the condition is true at mid index, update first_true_index first_true_index = mid right = mid - 1 else: # If the condition is false at mid index, narrow down the search space left = mid + 1 return first_true_index

জেএস

 function binarySearch(arr, target) { let left = 0; let right = arr.length - 1; let firstTrueIndex = -1; // Perform binary search until left and right pointers meet while (left <= right) { const mid = Math.floor((left + right) / 2); if (feasible(mid)) { // If the condition is true at mid index, update firstTrueIndex firstTrueIndex = mid; right = mid - 1; } else { // If the condition is false at mid index, narrow down the search space left = mid + 1; } } return firstTrueIndex; }

জাভা

 public int binarySearch(int[] arr, int target) { int left = 0; int right = arr.length - 1; int firstTrueIndex = -1; // Perform binary search until left and right pointers meet while (left <= right) { int mid = left + (right - left) / 2; if (feasible(mid)) { // If the condition is true at mid index, update firstTrueIndex firstTrueIndex = mid; right = mid - 1; } else { // If the condition is false at mid index, narrow down the search space left = mid + 1; } } return firstTrueIndex; }

3. দুটি পয়েন্টার

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

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

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

আপনি যদি একটি ডেটা কাঠামো অতিক্রম করার জন্য একাধিক পয়েন্টার নিয়োগ করেন, তাহলে আপনি "দুই পয়েন্টার" প্যাটার্ন অনুসরণ করে আপনার পদ্ধতিকে শ্রেণীবদ্ধ করতে পারেন।

প্রধান নির্দেশক:

• আপনাকে বিভিন্ন অবস্থানে উপাদানগুলির তুলনা বা পরিচালনা করতে হবে।
• সমস্যাগুলির জন্য একটি সাজানো অ্যারেতে উপাদানগুলির জোড়ার জন্য অনুসন্ধান করা প্রয়োজন৷
• আপনি একটি সাজানো অ্যারে থেকে দক্ষতার সাথে সদৃশগুলি সরাতে চান।
• রৈখিক ডেটা স্ট্রাকচার (অ্যারে, স্ট্রিং বা লিঙ্কযুক্ত তালিকা) নিয়ে কাজ করার সময় এবং একটি দ্বিঘাত সময় জটিলতার ( O(n^2) ব্রুট ফোর্স সলিউশনের মুখোমুখি হওয়ার সময়), দুটি পয়েন্টার নিয়োগ করার কথা বিবেচনা করুন।

টেমপ্লেট কোড:

"বিপরীত দিক" বৈচিত্রের জন্য টেমপ্লেট

পাইথন

 def two_pointers_opposite(arr): left = 0 right = len(arr) - 1 ans = 0 while left < right: # Perform logic using the left and right pointers if CONDITION: left += 1 else: right -= 1 return ans

জেএস

 function twoPointersOpposite(arr) { let left = 0; let right = arr.length - 1; let ans = 0; while (left < right) { // Perform logic using the left and right pointers if (CONDITION) { left++; } else { right--; } } return ans; }

জাভা

 public int twoPointersOpposite(int[] arr) { int left = 0; int right = arr.length - 1; int ans = 0; while (left < right) { // Perform logic using the left and right pointers if (CONDITION) { left++; } else { right--; } } return ans; }

4. স্লাইডিং উইন্ডো

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

এই প্যাটার্নটি প্রায়ই একটি হ্যাশ ম্যাপ ব্যবহার করে উইন্ডোর মধ্যে পৃথক ডেটা ট্র্যাক করার সুবিধার্থে। যাইহোক, এটা মনে রাখা গুরুত্বপূর্ণ যে এই পদ্ধতির ফলে O(n) এর স্থান-কালের জটিলতা হতে পারে।

প্রধান নির্দেশক:

• আপনাকে সংলগ্ন বা অ-সংলগ্ন সাবয়ারে বা সাবস্ট্রিংগুলি বিশ্লেষণ করতে হবে।
• সমস্যাগুলি একটি বড় ডেটাসেটের মধ্যে পরিবর্তনশীল-দৈর্ঘ্যের ক্রমগুলিকে ট্র্যাক করা জড়িত৷
• আপনি নির্দিষ্ট দৈর্ঘ্যের সর্বাধিক যোগফল সাব্যারে খুঁজে পেতে চান।
• সমস্যা ইনপুট হল একটি লিনিয়ার ডাটা স্ট্রাকচার যেমন একটি অ্যারে, লিঙ্কড লিস্ট বা স্ট্রিং।

টেমপ্লেট কোড:

পাইথন

 def slidingWindow(nums): # Initialize necessary variables left = 0 window = [] # Initialize the window ans = 0 # Initialize the answer variable for right in range(len(nums)): window.append(nums[right]) # Expand the window to the right while invalid(window): # Condition to shrink the window from the left until it is valid again window.pop(0) # Remove the left element from the window left += 1 ans = max(ans, len(window)) # Update the answer, can vary on your implementation return ans

জেএস

 function slidingWindow(nums) { let left = 0; const window = []; // Initialize the window let ans = 0; // Initialize the answer variable for (let right = 0; right < nums.length; right++) { window.push(nums[right]); // Expand the window to the right while (invalid(window)) { // Condition to shrink the window from the left until it is valid again window.shift(); // Remove the left element from the window left++; } ans = Math.max(ans, window.length); // Update the answer , can vary on your implementation } return ans; }

জাভা

 public static int slidingWindow(int[] nums) { int left = 0; List<Integer> window = new ArrayList<>(); // Initialize the window int ans = 0; // Initialize the answer variable for (int right = 0; right < nums.length; right++) { window.add(nums[right]); // Expand the window to the right while (invalid(window)) { // Condition to shrink the window from the left until it is valid again window.remove(0); // Remove the left element from the window left++; } ans = Math.max(ans, window.size()); // Update the answer , can vary on your implementation } return ans; }

5. শীর্ষ K উপাদান

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

যে কোনো সময় আমাদের একটি প্রদত্ত ডেটাসেটের মধ্যে সবচেয়ে ঘন ঘন, সবচেয়ে ছোট, বা শীর্ষ 'K' উপাদানগুলি খুঁজে পেতে বলা হয় আমরা এই প্যাটার্নটি ব্যবহার করে বিবেচনা করতে পারি।

এটা কাজ সহজ হয়:

1. আমরা আমাদের মিন বা সর্বোচ্চ হিপে 'কে' উপাদান সন্নিবেশ করি (এটি বাস্তবায়নের উপর নির্ভর করে)।
2. যখনই আমরা আমাদের হিপে যোগ করি তখন আমাদের অবশ্যই সামঞ্জস্য করতে হবে যাতে সর্বদা ঘন ঘন/ছোটতম/শীর্ষ 'কে' উপাদানগুলি বজায় থাকে।

এই পদ্ধতির সৌন্দর্য এর দক্ষতার মধ্যে নিহিত; আপনাকে কোনো সাজানোর অ্যালগরিদম অবলম্বন করতে হবে না, কারণ গাদা নিজেই স্বাভাবিকভাবেই আপনার জন্য প্রয়োজনীয় ক্রম বজায় রাখে।

প্রধান নির্দেশক:

• আপনাকে একটি সংগ্রহের K বৃহত্তম বা ক্ষুদ্রতম উপাদান সনাক্ত করতে হবে।
• সমস্যাগুলির জন্য নির্দিষ্ট মানদণ্ডের উপর ভিত্তি করে র‌্যাঙ্কিং উপাদান প্রয়োজন।
• আপনি একটি ডেটাসেটে শীর্ষ K ঘন ঘন উপাদানগুলি খুঁজে পেতে চান৷

টেমপ্লেট কোড:

পাইথন

 import heapq def top_k_elements(arr, k): heap = [] for num in arr: # Define your own criteria and logic to push elements onto the heap # For example, if you want to find the top k largest elements, push (-num, num) onto the heap heapq.heappush(heap, (-CRITERIA, num)) if len(heap) > k: heapq.heappop(heap) return [num for _, num in heap]

জেএস

 function topKElements(arr, k) { const minHeap = []; for (const num of arr) { // Define your own criteria and logic to push elements onto the heap // For example, if you want to find the top k smallest elements, push num onto the heap minHeap.push(CRITERIA); if (minHeap.length > k) { minHeap.sort((a, b) => a - b).shift(); } } return minHeap.sort((a, b) => a - b); }

জাভা

 import java.util.*; public List<Integer> topKElements(int[] arr, int k) { PriorityQueue<Integer> heap = new PriorityQueue<>(Comparator.comparingInt(a -> -CRITERIA)); for (int num : arr) { // Define your own criteria and logic to push elements onto the heap // For example, if you want to find the top k largest elements, push -num onto the heap heap.offer(-CRITERIA); if (heap.size() > k) { heap.poll(); } } List<Integer> topK = new ArrayList<>(); while (!heap.isEmpty()) { topK.add(-heap.poll()); } Collections.reverse(topK); return topK; }

6. দুই গাদা

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

এখানে কিভাবে এটা কাজ করে:

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

প্রধান নির্দেশক:

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

টেমপ্লেট কোড:

পাইথন

 import heapq class TwoHeaps: def __init__(self): self.min_heap = [] # Right heap to store larger half self.max_heap = [] # Left heap to store smaller half def add_num(self, num): if not self.max_heap or num <= -self.max_heap[0]: heapq.heappush(self.max_heap, -num) else: heapq.heappush(self.min_heap, num) # Balance the heaps if necessary if len(self.max_heap) > len(self.min_heap) + 1: heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap)) elif len(self.min_heap) > len(self.max_heap): heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap)) def find_median(self): if len(self.max_heap) == len(self.min_heap): return (-self.max_heap[0] + self.min_heap[0]) / 2.0 else: return -self.max_heap[0] # Usage: two_heaps = TwoHeaps() two_heaps.add_num(1) two_heaps.add_num(2) median = two_heaps.find_median() print("Median:", median)

জেএস

 class TwoHeaps { constructor() { this.minHeap = []; // Right heap to store larger half this.maxHeap = []; // Left heap to store smaller half } addNumber(num) { if (this.maxHeap.length === 0 || num <= -this.maxHeap[0]) { this.maxHeap.push(-num); } else { this.minHeap.push(num); } // Balance the heaps if necessary if (this.maxHeap.length > this.minHeap.length + 1) { this.minHeap.push(-this.maxHeap.shift()); } else if (this.minHeap.length > this.maxHeap.length) { this.maxHeap.push(-this.minHeap.shift()); } } findMedian() { if (this.maxHeap.length === this.minHeap.length) { return (-this.maxHeap[0] + this.minHeap[0]) / 2; } else { return -this.maxHeap[0]; } } } // Usage: const twoHeaps = new TwoHeaps(); twoHeaps.addNumber(1); twoHeaps.addNumber(2); const median = twoHeaps.findMedian(); console.log("Median:", median);

জাভা

 import java.util.*; class TwoHeaps { private PriorityQueue<Integer> minHeap; // Right heap to store larger half private PriorityQueue<Integer> maxHeap; // Left heap to store smaller half public TwoHeaps() { minHeap = new PriorityQueue<>(); maxHeap = new PriorityQueue<>(Collections.reverseOrder()); } public void addNumber(int num) { if (maxHeap.isEmpty() || num <= -maxHeap.peek()) { maxHeap.offer(-num); } else { minHeap.offer(num); } // Balance the heaps if necessary if (maxHeap.size() > minHeap.size() + 1) { minHeap.offer(-maxHeap.poll()); } else if (minHeap.size() > maxHeap.size()) { maxHeap.offer(-minHeap.poll()); } } public double findMedian() { if (maxHeap.size() == minHeap.size()) { return (-maxHeap.peek() + minHeap.peek()) / 2.0; } else { return -maxHeap.peek(); } } } // Usage: TwoHeaps twoHeaps = new TwoHeaps(); twoHeaps.addNumber(1); twoHeaps.addNumber(2); double median = twoHeaps.findMedian(); System.out.println("Median: " + median);

7. একঘেয়ে স্ট্যাক

একঘেয়ে - (একটি ফাংশন বা পরিমাণের) এমনভাবে পরিবর্তিত হয় যে এটি কখনও হ্রাস পায় না বা বাড়ে না।

একঘেয়ে স্ট্যাক অ-বাড়ন্ত বা অ-হ্রাস ক্রমে উপাদানগুলির একটি স্ট্যাক বজায় রাখে, প্রায়শই একটি অ্যারের নিকটতম ছোট/বৃহত্তর উপাদানগুলি খুঁজে পেতে ব্যবহৃত হয়। কিছু সমস্যা অপ্টিমাইজ করার জন্য এটি একটি শক্তিশালী টুল।

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

প্রধান নির্দেশক:

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

টেমপ্লেট কোড:

পাইথন

 def monotonic_stack(items): stack = [] for item in items: # Adjust the condition for comparisons to suit your needs while stack and stack[-1] <= item: stack.pop() # Do something with the popped item here stack.append(item)

জেএস

 function monotonicStack(items) { const stack = []; for (const item of items) { // Adjust the condition for comparisons to suit your needs while (stack.length > 0 && stack[stack.length - 1] <= item) { stack.pop(); // Do something with the popped item here } stack.push(item); } return stack; }

জাভা

 import java.util.*; public static int[] monotonicStack(int[] items) { Deque<Integer> stack = new ArrayDeque<>(); for (int item : items) { // Adjust the condition for comparisons to suit your needs while (!stack.isEmpty() && stack.peekLast() <= item) { stack.pollLast(); // Do something with the popped item here } stack.offerLast(item); } int[] result = new int[stack.size()]; int i = stack.size() - 1; while (!stack.isEmpty()) { result[i--] = stack.pollLast(); } return result; }

8. গভীরতা-প্রথম অনুসন্ধান

DFS , বা Depth-First Search হল একটি ট্রাভার্সাল পদ্ধতি যেখানে আপনি ব্যাকট্র্যাক করার আগে একটি শাখা বরাবর যতটা সম্ভব গভীরভাবে অন্বেষণ করেন; বিশেষ করে ট্রাভার্সাল এবং সার্চ অপারেশনের জন্য গাছ এবং গ্রাফ সম্পর্কিত সমস্যায় এটি ব্যাপকভাবে প্রয়োগ করা হয়।

একটি গাছে DFS সঞ্চালন করার জন্য, আপনাকে মূল থেকে শুরু করতে হবে। তারপর নিচের ধাপগুলো অনুসরণ করুন:

1. বর্তমান নোডটি এর চিলড্রেন নোডগুলি পরিদর্শন করে, সাধারণত বাম থেকে ডানে অন্বেষণ করুন৷
2. গাছের গভীরে গিয়ে প্রতিটি চাইল্ড নোডে পুনরাবৃত্তভাবে ডিএফএস প্রক্রিয়া প্রয়োগ করুন ।
3. একবার সমস্ত চাইল্ড নোড পরিদর্শন করা হলে, প্যারেন্ট নোডে ফিরে যান ।
4. গাছের সমস্ত নোড পরিদর্শন না করা পর্যন্ত বর্তমান নোডের প্রতিটি অনাদর্শিত শিশুর জন্য ধাপ 1-3 পুনরাবৃত্তি করুন ।

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

প্রধান নির্দেশক:

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

টেমপ্লেট কোড:

পাইথন

 def dfs(root, target): if root is None: # Base case: Check if the current node is None return None if root.val == target: # Base case: Check if the current node value matches the target return root left = dfs(root.left, target) # Recursively search the left subtree if left is not None: # If the target is found in the left subtree, return the result return left return dfs(root.right, target) # Recursively search the right subtree

জেএস

 function dfs(root, target) { if (root === null) { // Base case: Check if the current node is null return null; } if (root.val === target) { // Base case: Check if the current node value matches the target return root; } let left = dfs(root.left, target); // Recursively search the left subtree if (left !== null) { // If the target is found in the left subtree, return the result return left; } return dfs(root.right, target); // Recursively search the right subtree }

জাভা

 public TreeNode dfs(TreeNode root, int target) { if (root == null) { // Base case: Check if the current node is null return null; } if (root.val == target) { // Base case: Check if the current node value matches the target return root; } TreeNode left = dfs(root.left, target); // Recursively search the left subtree if (left != null) { // If the target is found in the left subtree, return the result return left; } return dfs(root.right, target); // Recursively search the right subtree }

9. ব্রেডথ-প্রথম অনুসন্ধান

BFS হল গাছ এবং গ্রাফের জন্য একটি ট্রাভার্সাল কৌশল যা পরবর্তী স্তরে যাওয়ার আগে বর্তমান গভীরতায় সমস্ত নোড অন্বেষণ করে।

একটি গাছে BFS সঞ্চালন করার জন্য, আপনাকে মূল থেকে শুরু করতে হবে। তারপর নিচের ধাপগুলো অনুসরণ করুন:

1. পরিদর্শন করা নোডগুলির ট্র্যাক রাখতে একটি খালি সারি ডেটা কাঠামো শুরু করুন৷

2. সারিতে রুট নোড সারিবদ্ধ করুন ।

3. সারি খালি না হওয়া পর্যন্ত একটি লুপ লিখুন:

   1. সারির সামনে নোড ডিক্যু করুন।
   2. সারিবদ্ধ নোড প্রক্রিয়া করুন (যেমন, এটিতে যান বা কিছু অপারেশন করুন)।
   3. নোডের সমস্ত শিশুকে (যদি থাকে) সারিবদ্ধ করুন।

4. সারিটি খালি না হওয়া পর্যন্ত 3a-3c ধাপগুলি পুনরাবৃত্তি করুন ৷

5. BFS ট্রাভার্সাল সম্পূর্ণ হয় যখন গাছের সমস্ত নোড বাম থেকে ডানে স্তর অনুসারে পরিদর্শন করা হয়।

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

একটি গ্রাফে BFS-এর সাথে পার্থক্য: DFS-এর মতো, গ্রাফ BFS নোডের মধ্যে চক্র এবং একাধিক পথের উপস্থিতির সাথে খাপ খায়। এটি গ্রাফগুলির মধ্যে সম্পর্কের জটিল নেটওয়ার্ককে দক্ষতার সাথে নেভিগেট করার জন্য পরিদর্শন করা নোডগুলি চিহ্নিত করা এবং বিশেষায়িত সমাপ্তির শর্তগুলির মতো প্রক্রিয়াগুলি নিয়োগ করে৷

প্রধান নির্দেশক:

• আপনি স্তর দ্বারা একটি গাছ স্তর অতিক্রম করতে হবে.
• ওজনহীন গ্রাফে সংক্ষিপ্ততম পথ খুঁজে পাওয়া সমস্যা জড়িত।
• আপনি একটি প্রস্থ-প্রথম পদ্ধতিতে একটি গাছ বা গ্রাফ অন্বেষণ করতে চান।

টেমপ্লেট কোড:

পাইথন

 from collections import deque def bfs(root): # Create a queue and initialize it with the root node queue = deque([root]) # Perform breadth-first search until the queue is empty while len(queue) > 0: # Dequeue the front node from the queue node = queue.popleft() # Process the current node for child in node.children: if is_goal(child): # If the goal condition is satisfied, return the child node return FOUND(child) # Enqueue the child node to explore it in the next iterations queue.append(child) # Return NOT_FOUND if the goal is not reached return NOT_FOUND

জেএস

 function bfs(root) { const queue = []; // Create a queue and initialize it with the root node queue.push(root); while (queue.length > 0) { // Perform breadth-first search until the queue is empty const node = queue.shift(); // Dequeue the front node from the queue for (const child of node.children) { // Process the current node if (isGoal(child)) { // If the goal condition is satisfied, return the child node return `FOUND ${child}`; } queue.push(child); // Enqueue the child node to explore it in the next iterations } } return 'NOT_FOUND'; // Return NOT_FOUND if the goal is not reached }

জাভা

 import java.util.LinkedList; import java.util.Queue; public String bfs(Node root) { Queue<Node> queue = new LinkedList<>(); // Create a queue and initialize it with the root node queue.offer(root); while (!queue.isEmpty()) { // Perform breadth-first search until the queue is empty Node node = queue.poll(); // Dequeue the front node from the queue for (Node child : node.getChildren()) { // Process the current node if (isGoal(child)) { // If the goal condition is satisfied, return the child node return "FOUND(child)"; } queue.offer(child); // Enqueue the child node to explore it in the next iterations } } return "NOT_FOUND"; // Return NOT_FOUND if the goal is not reached }

10. ইউনিয়ন খুঁজুন (ডিসজয়েন্ট-সেট ইউনিয়ন)

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

ইউনিয়ন খুঁজুন নিম্নরূপ প্রয়োগ করা হয়:

1. প্রারম্ভিকতা: উপাদানগুলির একটি সংগ্রহ দিয়ে শুরু করুন, প্রতিটিকে আলাদা আলাদা সেট হিসাবে বিবেচনা করা হয়। প্রতিটি সেটে একটি অনন্য প্রতিনিধি (প্রায়শই উপাদান নিজেই) বরাদ্দ করুন।
2. ইউনিয়ন অপারেশন: দুটি সেট একত্রিত করতে, ইউনিয়ন অপারেশন সম্পাদন করুন। একটি সেটের প্রতিনিধি নির্বাচন করুন (প্রায়শই কিছু মানদণ্ডের উপর ভিত্তি করে, যেমন র‍্যাঙ্ক বা আকার) এবং এটিকে অন্য সেটের প্রতিনিধির অভিভাবক করুন। এটি কার্যকরভাবে দুটি সেটকে সংযুক্ত করে।
3. ফাইন্ড অপারেশন: যখন আপনাকে একটি উপাদানের সাথে সম্পর্কিত সেটটি নির্ধারণ করতে হবে, তখন ফাইন্ড অপারেশন ব্যবহার করুন। প্রশ্নে থাকা উপাদানটি দিয়ে শুরু করে, এর সেটের রুট নোড (প্রতিনিধি) খুঁজে পেতে গাছটিকে উপরের দিকে অতিক্রম করুন। পাথ সংকোচন কৌশলটি এখানে প্রয়োগ করা যেতে পারে ভবিষ্যতের অনুসন্ধান ক্রিয়াকলাপগুলিকে অপ্টিমাইজ করতে পাথ বরাবর উপাদানগুলিকে সরাসরি মূলের দিকে নির্দেশ করে৷
4. চক্র সনাক্তকরণ: ইউনিয়ন-ফাইন্ড প্রায়শই গ্রাফে চক্র সনাক্ত করতে ব্যবহৃত হয়। ইউনিয়ন অপারেশন সম্পাদন করার সময়, যদি উভয় উপাদান একই সেটের অন্তর্গত হয় (অর্থাৎ, তাদের একই প্রতিনিধি থাকে), এটি নির্দেশ করে যে নোডগুলির মধ্যে একটি প্রান্ত যুক্ত করা গ্রাফে একটি চক্র তৈরি করবে।
5. অপ্টিমাইজেশান: ইউনিয়ন-ফাইন্ড ক্রিয়াকলাপগুলির দক্ষতা উন্নত করতে বিভিন্ন অপ্টিমাইজেশান কৌশল প্রয়োগ করা যেতে পারে, যেমন র্যাঙ্ক এবং পাথ কম্প্রেশন দ্বারা ইউনিয়ন।

টেমপ্লেট কোড:

পাইথন

 class UnionFind: def __init__(self): self.id = {} def find(self, x): y = self.id.get(x, x) if y != x: self.id[x] = y = self.find(y) return y def union(self, x, y): self.id[self.find(x)] = self.find(y)

জেএস

 class UnionFind { constructor() { this.id = {}; } /** * Find the root parent of an element in the set. * Implements path compression for better efficiency. * @param x The element to find the root parent for. * @returns The root parent of the element. */ find(x) { let y = this.id[x] || x; if (y !== x) { this.id[x] = y = this.find(y); } return y; } /** * Union two elements into the same set. * @param x The first element. * @param y The second element. */ union(x, y) { this.id[this.find(x)] = this.find(y); } }

জাভা

 import java.util.*; class UnionFind { private Map<String, String> id; public UnionFind() { id = new HashMap<>(); } /** * Find the root parent of an element in the set. * Implements path compression for better efficiency. * @param x The element to find the root parent for. * @return The root parent of the element. */ public String find(String x) { String y = id.getOrDefault(x, x); if (!y.equals(x)) { id.put(x, find(y)); } return y; } /** * Union two elements into the same set. * @param x The first element. * @param y The second element. */ public void union(String x, String y) { id.put(find(x), find(y)); } }

11. টপোলজিক্যাল বাছাই

একটি নির্দেশিত অ্যাসাইক্লিক গ্রাফ (DAG) হল একটি নির্দেশিত গ্রাফ যার কোন নির্দেশিত চক্র নেই।

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

এখানে টপোলজিকাল বাছাইয়ের একটি ধাপে ধাপে ব্রেকডাউন রয়েছে:

1. সূচনা: একটি নির্দেশিত অ্যাসাইক্লিক গ্রাফ ( ডিএজি ) দিয়ে শুরু করুন যা নির্ভরতা সহ কার্য বা নোডগুলিকে প্রতিনিধিত্ব করে। সাজানো নোড ধরে রাখতে একটি সারি শুরু করুন।

2. ইন-ডিগ্রী গণনা: গ্রাফে প্রতিটি নোডের জন্য ইন-ডিগ্রী (আগত প্রান্তের সংখ্যা) গণনা করুন। 0-এর ইন-ডিগ্রী সহ নোডগুলির কোনও নির্ভরতা নেই এবং টপোলজিক্যাল সাজানোর শুরুর বিন্দু হতে উপযুক্ত।

3. প্রারম্ভিক কিউ ফিলিং: সারিতে 0 এর ইন-ডিগ্রী সহ সমস্ত নোড সারিবদ্ধ করুন। এই নোডগুলি প্রথমে প্রক্রিয়া করা যেতে পারে।

4. টপোলজিকাল সর্ট লুপ: সারিটি খালি না থাকলেও নিম্নলিখিত পদক্ষেপগুলি সম্পাদন করুন:

   1. সারির সামনে থেকে একটি নোড ডিক্যু করুন।
   2. নোড প্রক্রিয়া করুন (যেমন, এটি সাজানো তালিকায় যোগ করুন)।
   3. প্রতিটি নোডের প্রতিবেশীর জন্য (নোড এটি নির্দেশ করে), তাদের ইন-ডিগ্রী 1 দ্বারা হ্রাস করুন।
   4. যদি কোনো প্রতিবেশীর ইন-ডিগ্রী হ্রাসের ফলে 0 হয়ে যায়, তাহলে সেটিকে সারিতে রাখুন।

5. সমাপ্তি: টপোলজিকাল সাজানোর লুপ সম্পূর্ণ হলে, সারিটি খালি থাকবে এবং বাছাই করা তালিকায় একটি বৈধ টপোলজিক্যাল ক্রমে সমস্ত নোড থাকবে।

6. চক্র শনাক্তকরণ: টপোলজিকাল সাজানোর প্রক্রিয়া চলাকালীন যে কোনো সময়ে, সারিতে 0-এর মধ্যে-ডিগ্রী সহ কোনো নোড না থাকলে, এটি গ্রাফে চক্রের উপস্থিতি নির্দেশ করে, যা টপোলজিক্যাল সাজানোকে অসম্ভব করে তোলে।

টপোলজিক্যাল সর্টের ফলাফল হল নোডগুলির একটি রৈখিক ক্রম যা তাদের নির্ভরতাকে সম্মান করে, এটিকে বিভিন্ন অ্যাপ্লিকেশনে কার্য নির্ধারণ বা কার্য সম্পাদনের ক্রম বিশ্লেষণের জন্য উপযুক্ত করে তোলে।

প্রধান নির্দেশক:

• সমস্যাটি নির্ভরশীলতার সাথে কাজগুলি নির্ধারণ বা অর্ডার করা জড়িত।
• আপনি একটি নির্দেশিত অ্যাসাইক্লিক গ্রাফ (DAG) নিয়ে কাজ করছেন।
• তাদের নির্ভরতা মেনে চলার সময় একটি নির্দিষ্ট ক্রমে কার্য সম্পাদন করা প্রয়োজন।

টেমপ্লেট কোড:

পাইথন

 from collections import deque def find_indegree(graph): # Calculate the indegree of each node in the graph indegree = {node: 0 for node in graph} for node in graph: for neighbor in graph[node]: indegree[neighbor] += 1 return indegree def topological_sort(graph): result = [] queue = deque() indegree = find_indegree(graph) # Add nodes with 0 indegree to the queue for node in indegree: if indegree[node] == 0: queue.append(node) while queue: node = queue.popleft() result.append(node) # Update the indegree of neighboring nodes for neighbor in graph[node]: indegree[neighbor] -= 1 if indegree[neighbor] == 0: queue.append(neighbor) # If all nodes are visited, return the result if len(graph) == len(result): return result else: return None

জেএস

 /** * Finds the indegree of each node in the graph. * @param {object} graph - The input graph. * @returns {object} - The indegree of each node. */ function findIndegree(graph) { const indegree = {}; for (const node in graph) { indegree[node] = 0; } for (const node in graph) { for (const neighbor of graph[node]) { indegree[neighbor]++; } } return indegree; } /** * Performs topological sorting on the given graph. * @param {object} graph - The input graph. * @returns {array|null} - The sorted nodes in topological order or null if a cycle is detected. */ function topologicalSort(graph) { const result = []; const queue = []; const indegree = findIndegree(graph); // Add nodes with no incoming edges to the queue for (const node in indegree) { if (indegree[node] === 0) { queue.push(node); } } while (queue.length > 0) { const node = queue.shift(); result.push(node); // Decrement the indegree of neighbors and enqueue if indegree becomes zero for (const neighbor of graph[node]) { indegree[neighbor]--; if (indegree[neighbor] === 0) { queue.push(neighbor); } } } // Check if all nodes have been visited (no cycles) if (Object.keys(graph).length === result.length) { return result; } else { return null; } }

জাভা

 import java.util.*; /** * Finds the indegree of each node in the graph. * @param graph - The input graph. * @return The indegree of each node. */ public Map<String, Integer> findIndegree(Map<String, List<String>> graph) { Map<String, Integer> indegree = new HashMap<>(); for (String node : graph.keySet()) { indegree.put(node, 0); } for (String node : graph.keySet()) { for (String neighbor : graph.get(node)) { indegree.put(neighbor, indegree.getOrDefault(neighbor, 0) + 1); } } return indegree; } /** * Performs topological sorting on the given graph. * @param graph - The input graph. * @return The sorted nodes in topological order or null if a cycle is detected. */ public List<String> topologicalSort(Map<String, List<String>> graph) { List<String> result = new ArrayList<>(); Queue<String> queue = new LinkedList<>(); Map<String, Integer> indegree = findIndegree(graph); // Add nodes with no incoming edges to the queue for (String node : indegree.keySet()) { if (indegree.get(node) == 0) { queue.offer(node); } } while (!queue.isEmpty()) { String node = queue.poll(); result.add(node); // Decrement the indegree of neighbors and enqueue if indegree becomes zero for (String neighbor : graph.get(node)) { indegree.put(neighbor, indegree.get(neighbor) - 1); if (indegree.get(neighbor) == 0) { queue.offer(neighbor); } } } // Check if all nodes have been visited (no cycles) if (graph.size() == result.size()) { return result; } else { return null; } }

12. চেষ্টা (প্রিফিক্স-ট্রি)

A Trie হল একটি গাছের মত ডেটা স্ট্রাকচার যা দক্ষ স্ট্রিং ম্যাচিং এবং শব্দের স্টোরেজের জন্য ব্যবহৃত হয়। সাধারণ উপসর্গ সহ স্ট্রিংগুলির জন্য আপনাকে সঞ্চয় করতে এবং অনুসন্ধান করতে হবে এমন সমস্যাগুলির মধ্যে এটি এক্সেল।

এখানে কিভাবে একটি ট্রাই বাস্তবায়ন করা যায়:

1. ইনিশিয়ালাইজেশন: একটি খালি ট্রাই দিয়ে শুরু করুন, যেটিতে সাধারণত কোনো যুক্ত অক্ষর ছাড়াই একটি রুট নোড থাকে।

2. সন্নিবেশ: ট্রাই-এ একটি শব্দ সন্নিবেশ করতে, রুট নোড থেকে শুরু করুন এবং গাছের নিচে, একবারে একটি অক্ষর অতিক্রম করুন। শব্দের প্রতিটি অক্ষরের জন্য:

   1. সেই অক্ষর সহ একটি চাইল্ড নোড বর্তমান নোডের অধীনে বিদ্যমান কিনা তা পরীক্ষা করুন।
   2. যদি তা হয়, চাইল্ড নোডে যান।
   3. যদি না হয়, চরিত্রের সাথে একটি নতুন চাইল্ড নোড তৈরি করুন এবং এটিতে যান।

3. শব্দ সমাপ্তি: Trie-তে একটি শব্দ বিদ্যমান আছে কিনা তা পরীক্ষা করতে, সন্নিবেশের অনুরূপভাবে এটি অতিক্রম করুন। নিশ্চিত করুন যে শব্দের প্রতিটি অক্ষর বর্তমান নোডের একটি চাইল্ড নোডের সাথে মিলে যায়। যদি ট্র্যাভার্সাল শব্দের শেষে পৌঁছায় এবং শেষ অক্ষর নোডে একটি বৈধ প্রান্ত চিহ্নিতকারী (যেমন, একটি বুলিয়ান পতাকা) থাকে, তাহলে শব্দটি Trie-তে বিদ্যমান থাকে।

4. উপসর্গ অনুসন্ধান: উপসর্গ অনুসন্ধানে শ্রেষ্ঠত্বের চেষ্টা করুন। একটি প্রদত্ত উপসর্গ সহ সমস্ত শব্দ খুঁজে পেতে, রুট নোডে ট্র্যাভার্সাল শুরু করুন এবং উপসর্গের অক্ষর অনুসরণ করে গাছের নিচে যান। একবার আপনি উপসর্গের শেষ অক্ষরে পৌঁছে গেলে, আপনি একই উপসর্গ ভাগ করে এমন সমস্ত শব্দ খুঁজে পেতে সেই নোড থেকে একটি গভীরতা-প্রথম অনুসন্ধান (DFS) সম্পাদন করতে পারেন।

5. মুছে ফেলা: Trie থেকে একটি শব্দ মুছে ফেলার জন্য, শব্দটি অনুসন্ধান করুন। যখন আপনি শব্দের শেষে পৌঁছান, শেষ চিহ্নিতকারীটি সরান (যদি এটি বিদ্যমান থাকে)। যদি নোডের অন্য কোন সন্তান না থাকে, তাহলে আপনি নিরাপদে ট্রাইয়ের পুরো শাখাটি সরিয়ে ফেলতে পারেন, যা শব্দটি উপস্থাপন করে।

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

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

প্রধান নির্দেশক:

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

টেমপ্লেট কোড:

পাইথন

 class TrieNode: def __init__(self, value): self.value = value self.children = {} def insert(self, s, idx): # idx: index of the current character in s if idx != len(s): self.children.setdefault(s[idx], TrieNode(s[idx])) self.children.get(s[idx]).insert(s, idx + 1)

জেএস

 class TrieNode { constructor(value) { this.value = value; this.children = {}; } insert(s, idx) { // idx: index of the current character in s if (idx !== s.length) { if (!this.children[s[idx]]) { this.children[s[idx]] = new TrieNode(s[idx]); } this.children[s[idx]].insert(s, idx + 1); } } }

জাভা

 import java.util.*; class TrieNode { char value; Map<Character, TrieNode> children; TrieNode(char value) { this.value = value; this.children = new HashMap<>(); } void insert(String s, int idx) { // idx: index of the current character in s if (idx != s.length()) { char c = s.charAt(idx); if (!children.containsKey(c)) { children.put(c, new TrieNode(c)); } children.get(c).insert(s, idx + 1); } } }

13. ডাইনামিক প্রোগ্রামিং

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

এখানে এর মূল বৈশিষ্ট্য এবং এটি কীভাবে কাজ করে:

সর্বোত্তম সাবস্ট্রাকচার:

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

ওভারল্যাপিং উপসমস্যা:

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

কিভাবে ডাইনামিক প্রোগ্রামিং কাজ করে:

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

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

গুরুত্বপূর্ণ ধারণা: বটম আপ অ্যাপ্রোচ, টপ-ডাউন, মেমোাইজেশন, ট্যাবুলেশন

প্রধান নির্দেশক:

• সমস্যাটিকে ছোট ওভারল্যাপিং সাব-প্রবলেমগুলিতে বিভক্ত করা যেতে পারে।
• উপ-সমস্যাগুলির সমাধানগুলি সংরক্ষণ এবং পুনঃব্যবহার করে অপ্টিমাইজ করার প্রয়োজন রয়েছে৷
• আপনি অপ্টিমাইজেশান বা গণনা জড়িত সমস্যা সমাধান করতে চান.

টেমপ্লেট কোড:

টপ-ডাউন মেমোাইজেশনের জন্য টেমপ্লেট ডায়নামিক প্রোগ্রামিং বাস্তবায়নের অনেক উপায়ের মধ্যে একটি।

পাইথন

 def top_down_memo(arr): def dp(state): # Base case(s): Define your own base case(s) for the problem if base_case: return 0 # Check if the state has already been memoized if state in memo: return memo[state] # Calculate the result using recurrence relation and memoize it result = recurrence_relation(state) memo[state] = result return result memo = {} # Memoization table to store calculated results return dp(initial_state)

জেএস

 function topDownMemo(arr) { function dp(state) { // Base case(s): Define your own base case(s) for the problem if (baseCase) { return 0; } // Check if the state has already been memoized if (memo.has(state)) { return memo.get(state); } // Calculate the result using recurrence relation and memoize it const result = recurrenceRelation(state); memo.set(state, result); return result; } const memo = new Map(); // Memoization map to store calculated results return dp(initialState); }

জাভা

 import java.util.HashMap; import java.util.Map; public int topDownMemo(int[] arr) { Map<StateType, Integer> memo = new HashMap<>(); // Memoization map to store calculated results return dp(initialState, memo); } private int dp(StateType state, Map<StateType, Integer> memo) { // Base case(s): Define your own base case(s) for the problem if (baseCase) { return 0; } // Check if the state has already been memoized if (memo.containsKey(state)) { return memo.get(state); } // Calculate the result using recurrence relation and memoize it int result = recurrenceRelation(state); memo.put(state, result); return result; }

14. ব্যাকট্র্যাকিং

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

ব্যাকট্র্যাকিং কীভাবে কাজ করে তা এখানে গভীরভাবে দেখুন:

1. সমস্যা স্পেস এক্সপ্লোরেশন: ব্যাকট্র্যাকিং সমস্যা স্থানটি অন্বেষণ করে ক্রমবর্ধমানভাবে একটি সমাধান এক টুকরো তৈরি করে। প্রতিটি পদক্ষেপে, এটি একটি সিদ্ধান্ত নেয় এবং এগিয়ে যায়।
2. পুনরাবৃত্তিমূলক কাঠামো: ব্যাকট্র্যাকিং প্রায়ই পুনরাবৃত্তি জড়িত। এটি একটি প্রাথমিক আংশিক সমাধান দিয়ে শুরু হয় এবং এটি প্রসারিত করার সমস্ত সম্ভাব্য উপায় অন্বেষণ করে। এই প্রক্রিয়াটি পুনরাবৃত্তিমূলকভাবে চলতে থাকে যতক্ষণ না একটি সম্পূর্ণ সমাধান পাওয়া যায় বা এটি স্পষ্ট হয়ে ওঠে যে কোনও বৈধ সমাধান নেই।
3. সিদ্ধান্তের পয়েন্ট: প্রতিটি ধাপে, সিদ্ধান্তের পয়েন্ট রয়েছে যেখানে অ্যালগরিদমকে অবশ্যই উপলব্ধ বিকল্পগুলি থেকে বেছে নিতে হবে। এই পছন্দগুলি অন্বেষণ প্রক্রিয়ায় শাখা তৈরি করে।
4. সমাধান বৈধতা: একটি পছন্দ করার পরে, অ্যালগরিদম বর্তমান আংশিক সমাধান বৈধ কিনা তা পরীক্ষা করে। এটি বৈধ হলে, অ্যালগরিদম পরবর্তী ধাপে চলে যায়। যদি তা না হয়, এটি পিছনে চলে যায়, পূর্ববর্তী পছন্দটি পূর্বাবস্থায় ফেরানো এবং অন্যান্য বিকল্পগুলি অন্বেষণ করে৷
5. সমাপ্তির শর্তাবলী: দুটি শর্তের একটি পূরণ না হওয়া পর্যন্ত ব্যাকট্র্যাকিং চলতে থাকে:
   • একটি বৈধ সমাধান পাওয়া যায়, এই ক্ষেত্রে অ্যালগরিদম থেমে যায় এবং সমাধানটি ফেরত দেয়।
   • এটি নির্ধারণ করা হয়েছে যে কোনও বৈধ সমাধান বিদ্যমান নেই, এই সময়ে অ্যালগরিদম পূর্ববর্তী সিদ্ধান্তের বিন্দুতে ফিরে যায় এবং বিভিন্ন বিকল্পগুলি অন্বেষণ করে।
6. ছাঁটাই: অনুসন্ধান অপ্টিমাইজ করতে, ব্যাকট্র্যাকিং প্রায়ই ছাঁটাই কৌশল অন্তর্ভুক্ত করে। ছাঁটাইয়ের মধ্যে এমন পথের অন্বেষণ এড়ানো জড়িত যা অবৈধ সমাধানের দিকে নিয়ে যাওয়ার গ্যারান্টিযুক্ত, অনুসন্ধানের স্থান উল্লেখযোগ্যভাবে হ্রাস করে।

ব্যাকট্র্যাকিংয়ের অ্যাপ্লিকেশন:

ব্যাকট্র্যাকিং বিভিন্ন সমস্যা ডোমেনে ব্যবহৃত হয়, যার মধ্যে রয়েছে:

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

প্রধান নির্দেশক:

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

টেমপ্লেট কোড:

পাইথন

 def backtrack(curr, OTHER_ARGUMENTS...): if BASE_CASE: # Modify the answer according to the problem's requirements return ans = 0 for ITERATE_OVER_INPUT: # Modify the current state according to the problem's requirements ans += backtrack(curr, OTHER_ARGUMENTS...) # Undo the modification of the current state (backtrack) return ans

জেএস

 function backtrack(curr, ...OTHER_ARGUMENTS) { if (BASE_CASE) { // Modify the answer according to the problem's requirements return; } let ans = 0; for (let i = 0; i < ITERATE_OVER_INPUT.length; i++) { const item = ITERATE_OVER_INPUT[i]; // Modify the current state according to the problem's requirements ans += backtrack(curr, ...OTHER_ARGUMENTS); // Undo the modification of the current state (backtrack) } return ans; }

জাভা

 public int backtrack(StateType curr, OtherArgumentType... OTHER_ARGUMENTS) { if (BASE_CASE) { // Modify the answer according to the problem's requirements return; } int ans = 0; for (int i = 0; i < ITERATE_OVER_INPUT.length; i++) { ItemType item = ITERATE_OVER_INPUT[i]; // Modify the current state according to the problem's requirements ans += backtrack(curr, OTHER_ARGUMENTS); // Undo the modification of the current state (backtrack) } return ans; }

15. ইন্টারভাল মার্জ করুন

একীভূত ব্যবধানের মধ্যে ওভারল্যাপিং বা সংলগ্ন ব্যবধানগুলিকে একত্রিত সেটে একত্রিত করা জড়িত, যা প্রায়ই সময়ের ব্যবধান বা সময়সূচী সংক্রান্ত সমস্যায় ব্যবহৃত হয়। এটি ব্যবধান-ভিত্তিক ক্রিয়াকলাপগুলিকে সরল করে।

মার্জিং ব্যবধানগুলি কীভাবে কাজ করে তা এখানে ঘনিষ্ঠভাবে দেখুন:

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

একত্রিত ব্যবধানের প্রয়োগ:

মার্জিং বিরতি সাধারণত ব্যবহৃত হয়:

• সময়সূচী এবং সময় ব্যবস্থাপনা অ্যাপ্লিকেশন।
• ক্যালেন্ডার সিস্টেমে ওভারল্যাপিং ইভেন্ট সনাক্তকরণ।
• ব্যবধান-ভিত্তিক ডেটা বিশ্লেষণ, যেমন ডাটাবেস প্রশ্নে।
• সম্পদ বরাদ্দ এবং মিটিং সময়সূচী সংক্রান্ত সমস্যা সমাধান করা।

ওভারল্যাপিং ব্যবধানগুলিকে একত্রিত করে, এই কৌশলটি ব্যবধান-ভিত্তিক ক্রিয়াকলাপগুলিকে সরল করে এবং বিভিন্ন অ্যাপ্লিকেশনগুলিতে দক্ষতা বাড়ায়।

প্রধান নির্দেশক:

• আপনি বিরতি বা সময়-ভিত্তিক ডেটা নিয়ে কাজ করছেন।
• সমস্যাগুলি ওভারল্যাপিং বা সন্নিহিত ব্যবধানগুলিকে একত্রিত করা জড়িত৷
• আপনি ব্যবধান-ভিত্তিক ক্রিয়াকলাপ সহজ করতে চান বা ইভেন্ট সময়সূচী অপ্টিমাইজ করতে চান।

টেমপ্লেট কোড:

পাইথন

 def merge_intervals(intervals): # 1. Sort the intervals based on their start values. intervals.sort(key=lambda x: x[0]) # 2. Initialize an empty list to store merged intervals. merged_intervals = [] # 3. Iterate through the sorted intervals. for interval in intervals: # 4. If the merged_intervals list is empty or the current interval does not overlap with the last merged interval: if not merged_intervals or interval[0] > merged_intervals[-1][1]: merged_intervals.append(interval) else: # 5. If the current interval overlaps with the last merged interval, merge them. merged_intervals[-1][1] = max(merged_intervals[-1][1], interval[1]) # 6. Return the merged_intervals list. return merged_intervals

জেএস

 function mergeIntervals(intervals) { // 1. Sort the intervals based on their start values. intervals.sort((a, b) => a[0] - b[0]); // 2. Initialize an empty array to store merged intervals. const mergedIntervals = []; // 3. Iterate through the sorted intervals. for (const interval of intervals) { // 4. If the mergedIntervals array is empty or the current interval does not overlap with the last merged interval: if (mergedIntervals.length === 0 || interval[0] > mergedIntervals[mergedIntervals.length - 1][1]) { mergedIntervals.push(interval); } else { // 5. If the current interval overlaps with the last merged interval, merge them. mergedIntervals[mergedIntervals.length - 1][1] = Math.max(mergedIntervals[mergedIntervals.length - 1][1], interval[1]); } } // 6. Return the mergedIntervals array. return mergedIntervals; }

জাভা

 public class MergeIntervals { public int[][] merge(int[][] intervals) { // 1. Sort the intervals based on their start values. Arrays.sort(intervals, (a, b) -> a[0] - b[0]); // 2. Create a list to store merged intervals. List<int[]> mergedIntervals = new ArrayList<>(); // 3. Iterate through the sorted intervals. for (int[] interval : intervals) { // 4. If the mergedIntervals list is empty or the current interval does not overlap with the last merged interval: if (mergedIntervals.isEmpty() || interval[0] > mergedIntervals.get(mergedIntervals.size() - 1)[1]) { mergedIntervals.add(interval); } else { // 5. If the current interval overlaps with the last merged interval, merge them. mergedIntervals.get(mergedIntervals.size() - 1)[1] = Math.max(mergedIntervals.get(mergedIntervals.size() - 1)[1], interval[1]); } } // 6. Convert the list to an array and return it. return mergedIntervals.toArray(new int[mergedIntervals.size()][]); } }

আরো জানতে চান?

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

$30 ছাড়ে আমাদের প্রচার কোড TECH30 দিয়ে আজই আপনার কোডিং ইন্টারভিউ প্রস্তুতির জন্য সুপারচার্জ করুন!