রানিং মিডিয়ান – প্রোগ্রামিং ইন্টারভিউ সমস্যা ১০

সমস্যাঃ একটি অ্যারেতে বা লিস্টে শুরুতে কোনো সংখ্যা নেই। অ্যারেতে ক্রমান্বয়ে n সংখ্যক সংখ্যা যুক্ত হবে, আর প্রতিটি সংখ্যা যুক্ত হওয়ার পরে ওই অ্যারের বর্তমান সংখ্যাগুলোর মিডিয়ান বের করতে হবে।

অ্যারের সংখ্যাগুলো যদি সর্ট করা হয়, তাহলে মাঝখানের সংখ্যাটি হচ্ছে মিডিয়ান। তবে অ্যারেতে যদি জোড় সংখ্যক সংখ্যা থাকে, তাহলে মাঝখানের দুটি সংখ্যার গড় হচ্ছে ওই অ্যারের মিডিয়ান।

উদাহরণঃ ধরা যাক, অ্যারেতে ক্রমান্বয়ে 1, 2, 3, 4-এই চারটি সংখ্যা যুক্ত করতে হবে। শুরুতে অ্যারেটি খালি। তারপর 1 যোগ করি, তাহলে অ্যারের অবস্থা দাঁড়াবে এমন – [1]। এখন মিডিয়ান হচ্ছে 1। তারপর 2 যোগ করি – [1, 2]। এখন মিডিয়ান হচ্ছে 1.5 ((1 + 2) / 2)। তারপর 3 যোগ করি – [1, 2, 3]। এখন মিডিয়ান হচ্ছে 2। তারপর 4 যোগ করি – [1, 2, 3, 4]। এখন মিডিয়ান হবে 2.5 (2 ও 3-এর গড়)।

সমাধানঃ সমস্যাটির সহজ একটি সমাধান হচ্ছে ইনসার্শন সর্ট (insertion sort)। আমরা প্রতিবার একটি করে সংখ্যা নিয়ে অ্যারেটি সর্ট করে ফেলবো, আর যেহেতু নতুন সংখ্যা আসার পূর্ব পর্যন্ত অ্যারেটি সর্ট করা আছে, তাই ইনসার্শন সর্ট এক্ষেত্রে একটি কার্যকর পদ্ধতি। ইন্টারভিউয়ারের সঙ্গে আলোচনা করার পরে উনি বলবেন যে, এই পদ্ধতির কমপ্লেক্সিটি কত সেটা বের করতে, কিংবা হয়ত এটি ইমপ্লিমেন্ট করতেও বলতে পারেন। এই পদ্ধতির ওয়ার্স্ট কেস টাইম কমপ্লেক্সিটি হচ্ছে O(n^2), বেস্ট কেস হচ্ছে O(n)। আর কোড করতেও 5-6 মিনিটের বেশি সময় লাগা উচিত নয়। এখন প্রশ্ন হচ্ছে, আমরা কিভাবে আরো ভালো পদ্ধতিতে সমাধান করতে পারি?

কেউ সমস্যাটি সমাধান করতে চাইলে এখানে করতে পারে – https://www.hackerrank.com/challenges/find-the-running-median/

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

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

হিপ ডেটা স্ট্রাকচার নিয়ে আমি বিস্তারিত আলোচনা করেছি কম্পিউটার প্রোগ্রামিং ৩য় খণ্ড – ডেটা স্ট্রাকচার ও অ্যালগরিদম পরিচিতি এবং পাইথন দিয়ে প্রোগ্রামিং শেখা ৩য় খণ্ড – ডেটা স্ট্রাকচার ও অ্যালগরিদম পরিচিতি বইতে। যারা হিপের সঙ্গে পরিচিত নয়, তারা ওই বইগুলো থেকে, কিংবা ডেটা স্ট্রাকচারের অন্য কোনো বই বা ইন্টারনেট ঘেঁটে শিখে নিতে পারবে।

এখন কথা হচ্ছে হিপ কি আমরা শুরু থেকে ইমপ্লিমেন্ট করবো নাকি কোনো লাইব্রেরি (পাইথনে যেমন heapq) ব্যবহার করবো? এটি ইন্টারভিউয়ারকে জিজ্ঞাসা করতে হবে। হিপ নিজে ইমপ্লিমেন্ট করার অভ্যাস থাকতে হবে কারণ অনেক ইন্টারভিউয়ার সেটাও দেখতে চাইবেন। আমি এখানে কোড লিখে রেখেছি – https://gist.github.com/tamim/4dd1e7fede8e5d76f0b4c4e397e3538c

Facebook Comments

Leave a Reply