कोडिंग इंटरव्यू: आप K सबसे अधिक बार आने वाले शब्द कैसे लौटाएंगे?

प्रॉम्प्ट और संदर्भ

एक ऐरे words और पूर्णांक k दिए जाने पर, k सबसे अधिक बार आने वाले शब्द लौटाएं। बराबरी होने पर आरोही (ascending) लेक्सिकोग्राफ़िकल क्रम के अनुसार निर्णय लें।

इंटरव्यू आकार k के एक कैंडिडेट सेट को बनाए रखने और यह तय करने पर केंद्रित है कि हीप रूट सबसे खराब कैंडिडेट का प्रतिनिधित्व करता है या सबसे अच्छे कैंडिडेट का। जावा का उपयोग केवल एक कंपैरेटर प्रदर्शित करने के लिए किया गया है; एल्गोरिदम भाषा-स्वतंत्र (language-independent) है।

इंटरव्यूअर क्या जांच रहा है

काउंटिंग

प्रत्येक शब्द को गिनने के लिए एक हैश मैप का उपयोग करें और ऐरे की लंबाई n को यूनीक-शब्दों की संख्या m से अलग पहचानें।

क्रमबद्ध करने के नियम

उच्च फ़्रीक्वेंसी जीतती है; समान फ़्रीक्वेंसी होने पर छोटे लेक्सिकोग्राफ़िकल क्रम का उपयोग किया जाता है। Min-heap रूट बदतर कैंडिडेट होना चाहिए ताकि अतिरिक्त प्रविष्टियों को हटाया जा सके।

जटिलता

पूरी तरह सॉर्ट करने में O(m log m) समय लगता है। साइज़-k हीप O(n + m log k) लेता है, जो तब उपयोगी होता है जब k यूनीक शब्दों की संख्या से काफी छोटा हो।

शुद्धता (Correctness)

समझाएं कि निष्कासन (eviction) के लिए हीप का क्रम अंतिम आउटपुट क्रम से भिन्न क्यों है: हीप सबसे खराब कैंडिडेट को हटाता है, जबकि उत्तर में सबसे अच्छे कैंडिडेट पहले सूचीबद्ध होने चाहिए।

पूछने योग्य स्पष्टीकरण प्रश्न

क्या शब्द लोअरकेस अंग्रेज़ी में हैं और केस-सेंसिटिव हैं?
क्या k का 1 और यूनीक शब्दों की संख्या के बीच होना सुनिश्चित है?
क्या लेक्सिकोग्राफ़िकल क्रम ASCII, Unicode, या किसी बिज़नेस लोकेल पर आधारित है?
क्या इनपुट को स्ट्रीम के रूप में प्रोसेस किया जाना चाहिए?
क्या आउटपुट स्थिर (stable) होना चाहिए, या कोई भी क्रम स्वीकार्य है?
क्या फ़्रीक्वेंसी 32-बिट पूर्णांक से अधिक हो सकती है?

30-सेकंड का उत्तर ढांचा

"मैं एक हैश मैप के साथ फ़्रीक्वेंसी गिनूंगा। प्रत्येक यूनीक शब्द के लिए मैं एक साइज़-k min-heap बनाए रखूंगा जिसका रूट बदतर कैंडिडेट होगा: कम फ़्रीक्वेंसी, या बराबरी होने पर बड़ा लेक्सिकोग्राफ़िकल क्रम। डालने के बाद, जब हीप k से बड़ा हो जाता है तो मैं पॉप करता हूँ। अंत में, मैं हीप प्रविष्टियों को घटती फ़्रीक्वेंसी और बढ़ते लेक्सिकोग्राफ़िकल क्रम में उत्सर्जित करता हूँ। काउंटिंग में O(n), हीप रखरखाव में O(m log k) का खर्च आता है, और स्पेस O(m) है।"

चरण-दर-चरण गहन विश्लेषण

चरण 1: फ़्रीक्वेंसी गिनें

प्रत्येक शब्द को उसकी संख्या में मैप करें। एक स्ट्रीमिंग लॉग बाहरी एकत्रीकरण (aggregation) या एक अनुमानित काउंटर का उपयोग कर सकता है, लेकिन यह समस्या मानती है कि यूनीक-शब्दों का मैप मेमोरी में समा जाता है।

चरण 2: सबसे खराब कैंडिडेट को परिभाषित करें

कैंडिडेट A, B से बदतर तब होता है जब A की फ़्रीक्वेंसी कम हो; बराबरी होने पर, A का लेक्सिकोग्राफ़िकल क्रम बड़ा होता है। कंपैरेटर उस कैंडिडेट को हीप रूट पर रखता है।

चरण 3: साइज़ k बनाए रखें

फ़्रीक्वेंसी मैप से प्रत्येक प्रविष्टि डालें और जब हीप k से अधिक हो जाए तो पॉप करें। इसलिए हीप उन k प्रविष्टियों को बनाए रखता है जिनकी अंतिम उत्तर में होने की सबसे अधिक संभावना है।

चरण 4: आउटपुट उत्पन्न करें

हीप पॉप सबसे खराब से बेहतर की ओर चलते हैं, इसलिए उन्हें सीधे वापस नहीं किया जा सकता है। एकत्रित प्रविष्टियों को उलट दें या उन्हें घटती फ़्रीक्वेंसी और बढ़ते लेक्सिकोग्राफ़िकल क्रम के साथ सॉर्ट करें।

चरण 5: शुद्धता सिद्ध करें

जब भी साइज़ k से अधिक हो, वर्तमान सेट के सबसे खराब सदस्य को हटा दें। वह सदस्य बनाए रखे गए k सदस्यों में से किसी से भी बेहतर रैंक नहीं कर सकता। इंडक्शन द्वारा, अंतिम हीप में वैश्विक Top K शामिल होते हैं।

चरण 6: सीमाओं (Boundaries) को संभालें

k=1, समान फ़्रीक्वेंसी, एक यूनीक शब्द, कई डुप्लिकेट, और k=m का परीक्षण करें। कंपैरेटर को गलती से बराबरी को उलटना नहीं चाहिए।

मॉडल उच्च-गुणवत्ता वाला उत्तर

java

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> count = new HashMap<>();
        for (String word : words) {
            count.merge(word, 1, Integer::sum);
        }

        PriorityQueue<String> heap = new PriorityQueue<>((a, b) -> {
            int byFrequency = Integer.compare(count.get(a), count.get(b));
            if (byFrequency != 0) return byFrequency;
            return b.compareTo(a); // larger lexicographic value is worse
        });

        for (String word : count.keySet()) {
            heap.offer(word);
            if (heap.size() > k) heap.poll();
        }

        List<String> answer = new ArrayList<>();
        while (!heap.isEmpty()) answer.add(heap.poll());
        Collections.reverse(answer);
        return answer;
    }
}

काउंटिंग में O(n) का खर्च आता है। m यूनीक शब्दों के साथ, हीप संचालन में O(log k) का खर्च आता है, कुल O(n + m log k) समय और O(m) स्पेस के लिए।

सामान्य गलतियाँ

हीप रूट पर सबसे अच्छे कैंडिडेट को रखना → सही उत्तर निष्कासित हो जाता है → रूट पर सबसे खराब कैंडिडेट को रखें।
बराबरी के कंपैरेटर को उलटना → आउटपुट क्रम गलत हो जाता है → समान फ़्रीक्वेंसी पर पहले लेक्सिकोग्राफ़िक रूप से छोटे शब्दों को बनाए रखें।
हीप पॉप को सीधे लौटाना → आउटपुट सबसे खराब से सबसे अच्छे की ओर जाता है → उलट दें या अंतिम सॉर्ट करें।
पूर्ण सॉर्टिंग के बाद O(n log k) का दावा करना → जटिलता गलत है → पूर्ण सॉर्टिंग की लागत O(m log m) है।
केवल अलग-अलग फ़्रीक्वेंसी का परीक्षण करना → बराबरी के व्यवहार का परीक्षण नहीं होता है → सभी-समान फ़्रीक्वेंसी और कई बराबरी के मामलों को शामिल करें।
k=m की अनदेखी करना → अनावश्यक निष्कासन या बाउंड त्रुटियाँ → हीप को सभी यूनीक शब्दों को शामिल करने की अनुमति दें।
गलती से लोकेल-निर्भर क्रमबद्धता का उपयोग करना → परिणाम अलग-अलग वातावरणों में भिन्न होते हैं → आवश्यक क्रम को स्पष्ट रूप से बताएं।
स्पेस विश्लेषण के बिना हैश मैप का नाम लेना → पैमाना अस्पष्ट रहता है → n, m, और k जटिलता बताएं।

फॉलो-अप प्रश्न और उत्तर

फॉलो-अप 1: क्या आप तब भी हीप का उपयोग करेंगे जब k, m के करीब हो?

पूर्ण सॉर्टिंग में बेहतर स्थिरांक (constants) और सरल कोड हो सकता है। एक हीप मान्य रहता है, लेकिन O(m log k), O(m log m) के करीब पहुंच जाता है।

फॉलो-अप 2: क्या होगा यदि इनपुट एक असीमित स्ट्रीम है?

सटीक गणनाओं के लिए अभी भी स्थिति (state) की आवश्यकता होती है। विंडो, बाहरी एकत्रीकरण, या सन्निकटन का उपयोग करें; सटीक Top K के लिए पर्याप्त रूप से बनाए रखी गई फ़्रीक्वेंसी स्थिति की आवश्यकता होती है।

फॉलो-अप 3: क्या होगा यदि यूनीक शब्द मेमोरी से अधिक हो जाएं?

डिस्क पर विभाजन-हैश (Partition-hash) करें, प्रत्येक विभाजन की गणना करें, और उम्मीदवारों को मर्ज करें, या बाहरी सॉर्टिंग का उपयोग करें। पूरी ऐरे को मेमोरी में लोड न करें।

फॉलो-अप 4: आप केस-इनसेंसिटिव शब्दों का समर्थन कैसे करेंगे?

गिनती से पहले एक स्पष्ट लोकेल के साथ सामान्यीकृत (Normalize) करें। परिभाषित करें कि क्या आउटपुट मूल वर्तनी को सुरक्षित रखता है और समकक्ष रूपों को दो बार गिनने से बचें।

फॉलो-अप 5: आप कंपैरेटर का परीक्षण कैसे करेंगे?

विपरीत लेक्सिकोग्राफ़िकल क्रम के साथ समान फ़्रीक्वेंसी, k=1, k=m, और बहुत सारे डुप्लिकेट वाले इनपुट पर जांच (assert) करें; पूर्ण-सॉर्ट संदर्भ के साथ यादृच्छिक मामलों की तुलना करें।

स्रोत 1: LeetCode 692

यह समस्या घटती फ़्रीक्वेंसी, आरोही लेक्सिकोग्राफ़िकल बराबरी, और O(n log k) फ़ॉलो-अप को परिभाषित करती है, जो आउटपुट और जटिलता लक्ष्य स्थापित करती है।

स्रोत 2: NeetCode Top K

NeetCode फ़्रीक्वेंसी-मैप और Top K दृष्टिकोण प्रदर्शित करता है और कंपैरेटर और हीप-बनाम-सॉर्ट ट्रेडऑफ़ पर प्रकाश डालता है।

स्रोत 3: Oracle PriorityQueue

Oracle प्राकृतिक क्रम या Comparator द्वारा PriorityQueue क्रमबद्धता का दस्तावेजीकरण करता है, जो कस्टम min-heap कंपैरेटर और poll सेमांटिक्स का समर्थन करता है।