Bit manipulation ও interval সমস্যা: interview-এর প্যাটার্ন

এই সিরিজের এই অংশ দুটি ছোট বিষয়ে শেষ হচ্ছে, কারণ এগুলো ছোট, interview-তে প্রায়ই আসে আর সূক্ষ্মভাবে ভুল করা সহজ: bit manipulation ও interval সমস্যা। নিচের code ও output প্রকাশের আগে Python 3-এ চালানো।

অংশ ১: জানার মতো bit কৌশল

• XOR (^): a ^ a = 0 ও a ^ 0 = a। যে list-এ একটি বাদে সব মান দুবার আছে, সব সংখ্যা XOR করলে শুধু একক মানটি থাকে।
• n & (n - 1) সবচেয়ে নিচের set bit মুছে দেয়। বারবার করলে সংখ্যার 1-bit গোনা যায়, বা power of two যাচাই: ধনাত্মক সংখ্যা power of two হলে তাতে ঠিক একটি set bit থাকে, তাই n & (n - 1) == 0।
• Bitmask সর্বোচ্চ প্রায় ২০টি আইটেমের একটি সেটকে একটি integer-এর bit হিসেবে রাখে। mask 0 থেকে 2^n - 1 পর্যন্ত চালালে সব উপসেট পাওয়া যায়।
• Shift: 1 << i শুধু i নম্বর bit set করা সংখ্যা বানায়, আর x >> i & 1 i নম্বর bit পড়ে।

অংশ ২: interval প্যাটার্ন

• Interval merge। শুরুর সময় ধরে sort করুন। হাঁটতে থাকুন: পরের interval শেষ merge হওয়াটির শেষে বা তার আগে শুরু হলে সেটি বাড়ান, নইলে নতুন একটি শুরু করুন। খরচ O(n log n)।
• সর্বনিম্ন meeting room। শুরুর সময় ধরে sort করুন। ব্যবহৃত ঘরগুলোর শেষের সময়ের একটি min-heap রাখুন। সবচেয়ে আগের শেষ নতুন শুরুর সময় বা তার আগে হলে ওই ঘর আবার ব্যবহার করুন, নইলে ঘর যোগ করুন। শেষে heap-এর আকারই উত্তর।

Code

import heapq

def single_number(nums):                 # every value appears twice except one
    x = 0
    for n in nums:
        x ^= n
    return x

def count_bits(n):
    c = 0
    while n:
        n &= n - 1                       # clears the lowest set bit
        c += 1
    return c

def is_power_of_two(n):
    return n > 0 and n & (n - 1) == 0

def subsets(items):
    return [[items[i] for i in range(len(items)) if mask >> i & 1] for mask in range(1 << len(items))]

def merge_intervals(intervals):
    out = []
    for start, end in sorted(intervals):
        if out and start <= out[-1][1]:
            out[-1][1] = max(out[-1][1], end)
        else:
            out.append([start, end])
    return out

def min_meeting_rooms(intervals):
    ends = []                            # min-heap of end times of rooms in use
    for start, end in sorted(intervals):
        if ends and ends[0] <= start:
            heapq.heapreplace(ends, end)
        else:
            heapq.heappush(ends, end)
    return len(ends)

আসল output

single number: 4
bits in 13 (1101): 3 | 255: 8
power of two: [1, 2, 4, 8, 16, 32]
subsets of [a,b,c]: [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']]
merge: [[1, 6], [8, 10], [15, 20]]
rooms: 2 | back-to-back: 1
all checks passed

merge_intervals [1,3], [2,6]-কে [1,6] এবং [15,18], [17,20]-কে [15,20] করেছে। (0,30), (5,10), (15,20) meeting-এ দুটি ঘর লাগে, আর পরপর meeting (0,5), (5,10)-এ একটি ঘরই যথেষ্ট কারণ 5-এ শেষ হওয়া meeting 5-এ শুরু হওয়া meeting-এর জন্য ঘর খালি করে। ছোঁয়া interval merge হবে কি না সেটি সমস্যায় বলা থাকতে হবে, তাই সবসময় জিজ্ঞেস করুন। bit function গুলোকে 300টি random সংখ্যায় Python-এর bin(n).count("1")-এর সঙ্গে এবং merge_intervals-কে 300টি random সেটে brute-force কভারেজ যাচাইয়ের সঙ্গে মিলিয়ে দেখা হয়েছে।

সাধারণ ভুল

• অপারেটরের অগ্রাধিকার। C, C++ ও JavaScript-এ == &-এর চেয়ে আগে বসে, তাই n & (n - 1) == 0 মানে n & ((n - 1) == 0)। Python এটি আপনার প্রত্যাশামতো পড়ে, তবু বন্ধনী লিখুন: (n & (n - 1)) == 0।
• power-of-two যাচাইয়ে n > 0 ভুলে গেলে 0 ভুলভাবে গৃহীত হয়।
• প্রায় ২০টির বেশি আইটেমে bitmask: 2^n খুব দ্রুত বাড়ে।
• interval আগে sort না করা।
• সীমানার নিয়ম ভোলা ([1,2] ও [2,3] merge হবে কি?), বা অন্য interval-এর ভেতরে সম্পূর্ণ থাকা interval, যেটি max সামলায়।
• যে list caller বদলাতে চায় না সেটি বদলে ফেলা।

মূল কথা: XOR জোড়া কেটে দেয়, n & (n - 1) সবচেয়ে নিচের bit মোছে, আর bitmask উপসেট গোনে। interval-এ শুরু ধরে sort করুন, হাঁটতে হাঁটতে merge করুন, আর ঘরের জন্য শেষের সময়ের min-heap ব্যবহার করুন।

---

Interview প্রস্তুতি ও DSA সিরিজ, পর্ব ৩ (আরও algorithm): 5 নম্বর (মোট 5)। আগের লেখা: Greedy algorithm: interval scheduling ও greedy কখন ব্যর্থ.