प्रॉम्प्ट और दायरा
set(key, value, timestamp) और get(key, timestamp) के साथ एक इन-मेमोरी संरचना लागू करें। get उस की (key) के लिए नवीनतम वर्शन लौटाता है जिसका टाइमस्टैम्प क्वेरी समय से अधिक न हो; जब कोई मौजूद न हो तो यह एक स्पष्ट मिस लौटाता है। स्पष्ट करें कि क्या टाइमस्टैम्प प्रति-की मोनोटोनिक हैं, क्या समान टाइमस्टैम्प अधिलेखित (overwrite) होते हैं, क्या रीड और राइट समवर्ती (concurrent) हैं, और क्या विलोपन (deletion) या दृढ़ता (persistence) की आवश्यकता है। मुख्य बात प्रति-की इतिहास इनवेरिएंट को बनाए रखना है, न कि हर रिकॉर्ड को बार-बार सॉर्ट और स्कैन करना।
इंटरव्यूअर क्या मूल्यांकन करता है
एक मजबूत उत्तर O(log m) लुकअप को लक्षित करता है, जहां m की (key) के लिए वर्शनों की संख्या है, और अपेंड-ओनली तथा आउट-ऑफ-ऑर्डर इनपुट के बीच राइट ट्रेड-ऑफ की व्याख्या करता है। इंटरव्यूअर खाली कुंजियों, दोनों समय सीमाओं, डुप्लिकेट टाइमस्टैम्प, नल मानों, अज्ञात कुंजियों और नवीनतम प्रभावी वर्शन तथा क्वेरी समय के बाद के वर्शन के बीच अंतर की जांच करेगा। थ्रेड-सुरक्षा के दावे में लॉक ग्रैन्युलैरिटी और स्नैपशॉट सिमेंटिक्स शामिल होने चाहिए।
कोडिंग से पहले स्पष्ट करने वाले प्रश्न
- क्या टाइमस्टैम्प प्रति-की मोनोटोनिक हैं? यदि हाँ, तो अपेंड करें और एक संक्षिप्त रिवर्स स्कैन या बाइनरी सर्च का उपयोग करें; यदि नहीं, तो क्रम बनाए रखें या आउट-ऑफ-ऑर्डर राइट्स को अस्वीकार करें।
- समान टाइमस्टैम्प का क्या अर्थ है? लास्ट-राइट-विन्स (last-write-wins) के लिए, एक स्थिर टाई-ब्रेकर के रूप में मोनोटोनिक रूप से बढ़ते अनुक्रम को रखें; अन्यथा संघर्षों को अस्वीकार करें।
- क्या मान नल हो सकते हैं? यदि ऐसा है, तो मिस को नल द्वारा भी प्रदर्शित नहीं किया जा सकता है; एक स्पष्ट
foundध्वज के साथ परिणाम लौटाएं। - क्या कॉनकरेंसी आवश्यक है? पहले सिंगल-थ्रेडेड इनवेरिएंट को पूरा करें, फिर दृश्यता परिभाषित करें और प्रति-की लॉक या अपरिवर्तनीय (immutable) स्नैपशॉट चुनें।
- क्या इतिहास असीमित है? एक रिटेंशन विंडो या वर्शन कैप निष्कासन (eviction) और पुरानी क्वेरी के अर्थ को बदल देता है।
30-सेकंड का उत्तर ढांचा
“मैं प्रत्येक की (key) के लिए एक समय-क्रमबद्ध वर्शन ऐरे संग्रहीत करता हूं। get क्वेरी से बड़े पहले वर्शन को खोजने के लिए upper_bound(timestamp) का उपयोग करता है और पिछली प्रविष्टि लौटाता है, इसलिए लुकअप O(log m) है। यदि राइट्स मोनोटोनिक नहीं हैं, तो मैं ऑर्डर्ड इंसर्शन का उपयोग करता हूं और इसकी लागत का उल्लेख करता हूं; यदि राइट थ्रूपुट प्रमुख है, तो मैं एक लॉग में अपेंड करता हूं और बैचों में एक इंडेक्स बनाता हूं। एक अनुक्रम संख्या समान टाइमस्टैम्प को नियतात्मक (deterministic) बनाती है, और मिस की एक स्पष्ट स्थिति होती है। मैं खाली कुंजियों, सीमाओं, आउट-ऑफ-ऑर्डर राइट्स और डुप्लिकेट टाइमस्टैम्प का परीक्षण करता हूं।”
चरण-दर-चरण समाधान
प्रत्येक रिकॉर्ड को (timestamp, sequence, value) के रूप में दर्शाएं और प्रत्येक की के ऐरे को (timestamp, sequence) द्वारा गैर-घटते क्रम (nondecreasing) में रखें। get(k, t) के लिए, timestamp > t के साथ पहली स्थिति i खोजें। यदि i शून्य है तो कोई प्रभावी वर्शन नहीं है; अन्यथा records[i - 1] लौटाएं। यह अपर-बाउंड नियम ठीक t पर राइट को शामिल करता है।
जब टाइमस्टैम्प प्रति-की मोनोटोनिक होते हैं, तो अपेंड करने से set को परिशोधित (amortized) O(1) और get को O(log m) प्राप्त होता है। आउट-ऑफ-ऑर्डर टाइमस्टैम्प के साथ, इंसर्शन बिंदु का पता लगाना लॉगरिदमिक है लेकिन एक ऐरे को स्थानांतरित (shift) करना सबसे खराब स्थिति में O(m) है। एक संतुलित पेड़ (balanced tree) अधिक आवंटन और पॉइंटर ओवरहेड की कीमत पर स्थानांतरण से बचाता है। एकल वैश्विक सॉर्ट किया गया ऐरे गलत है क्योंकि क्वेरी सीमाएं प्रति-की स्वतंत्र होती हैं।
डुप्लिकेट टाइमस्टैम्प के लिए एक नियतात्मक नियम की आवश्यकता होती है। लास्ट-राइट-विन्स के लिए, प्रत्येक कॉल को एक बढ़ता हुआ अनुक्रम सौंपें और (timestamp, sequence) द्वारा सॉर्ट करें; अपर बाउंड केवल टाइमस्टैम्प की तुलना करता है, इसलिए उस टाइमस्टैम्प पर अंतिम रिकॉर्ड जीतता है। यदि टाइमस्टैम्प भाषा की सुरक्षित पूर्णांक सीमा से अधिक हो सकते हैं, तो चुपचाप फ्लोटिंग पॉइंट में बदलने के बजाय एक उपयुक्त पूर्णांक प्रकार या तुलनित्र (comparator) का उपयोग करें।
कॉनकरेंसी के लिए, सबसे छोटा विस्तार किसी एक की (key) के ऐरे को बदलते समय या बाइनरी सर्च चलाते समय उसे लॉक करता है। रीड्स को गैर-अवरोधक (non-blocking) रखने के लिए, एक राइटर एक नया अपरिवर्तनीय ऐरे बना सकता है और संदर्भ को परमाणु रूप से (atomically) बदल सकता है; रीडर्स या तो पुराना या नया स्नैपशॉट देखते हैं, कभी भी आंशिक ऐरे नहीं। पर्सिस्टेंस एक लॉग, चेकसम और रिकवरी कर्सर जोड़ता है और इस पर तभी चर्चा की जानी चाहिए जब इंटरव्यूअर दायरा बढ़ाए।
उच्च-गुणवत्ता वाला नमूना उत्तर
“मैं मानूंगा कि टाइमस्टैम्प आउट-ऑफ-ऑर्डर आ सकते हैं, समान टाइमस्टैम्प लास्ट-राइट-विन्स का उपयोग करते हैं, और पहला वर्शन सिंगल-थ्रेडेड है। प्रत्येक की (key) (timestamp, sequence) द्वारा सॉर्ट किए गए ऐरे पर मैप होती है। get क्वेरी से बड़े पहले टाइमस्टैम्प के लिए अपर-बाउंड खोज करता है और पूर्ववर्ती वर्शन लौटाता है, जिससे O(log m) लुकअप और सही समानता व्यवहार मिलता है। यदि टाइमस्टैम्प के बढ़ने की गारंटी है, तो set परिशोधित (amortized) O(1) बन जाता है। यदि राइट्स रीड्स पर हावी हैं, तो मैं एक लॉग में अपेंड करूंगा और एसिंक्रोनस रूप से एक इंडेक्स बनाऊंगा। परीक्षण अज्ञात कुंजियों, पहले वर्शन से पहले, पहले और अंतिम वर्शन के बराबर, अंतिम वर्शन के बाद, आउट-ऑफ-ऑर्डर राइट्स, डुप्लिकेट टाइमस्टैम्प और नल मानों को कवर करते हैं।”
सामान्य गलतियाँ
- गलती → अंतिम वर्शन के लिए रैखिक रूप से स्कैन करना; यह क्यों विफल होता है → लुकअप
O(m)बन जाता है और खराब रूप से स्केल करता है; सुधार → सॉर्ट किए गए इतिहास को बनाए रखें और अपर-बाउंड खोज का उपयोग करें। - गलती →
timestamp < tका उपयोग करना; यह क्यों विफल होता है → ठीकtपर राइट छूट जाता है; सुधार → पहलाtimestamp > tखोजें। - गलती → मान लेना कि सभी राइट्स बढ़ रहे हैं; यह क्यों विफल होता है → एक आउट-ऑफ-ऑर्डर इवेंट ऐरे इनवेरिएंट को तोड़ता है; सुधार → बाधा बताएं और ऑर्डर्ड इंसर्शन या ट्री का उपयोग करें।
- गलती → मिस और संग्रहीत मान दोनों के लिए नल का उपयोग करना; यह क्यों विफल होता है → कॉल करने वाले स्थितियों में अंतर नहीं कर सकते; सुधार →
{ found, value }या एक स्पष्ट विकल्प (option) प्रकार लौटाएं। - गलती → समान टाइमस्टैम्प को अनदेखा करना; यह क्यों विफल होता है → परिणाम आकस्मिक क्रम पर निर्भर करते हैं; सुधार → एक अनुक्रम जोड़ें या संघर्ष को अस्वीकार करें।
फॉलो-अप प्रतिक्रियाएं
यदि टाइमस्टैम्प के बढ़ने की गारंटी हो तो आप कैसे अनुकूलित करेंगे?
परिशोधित O(1) राइट्स के लिए प्रति की (key) अपेंड करें। पूर्वानुमेय O(log m) रीड्स के लिए बाइनरी सर्च रखें, या केवल तब पीछे की ओर स्कैन करें जब एक्सेस पैटर्न दिखाते हैं कि क्वेरी आमतौर पर नवीनतम वर्शन के करीब होती हैं। यह दावा न करें कि बैकवर्ड स्कैनिंग सबसे खराब स्थिति में स्थिर समय (constant time) लेती है।
आप प्रति-की केवल पिछले 30 दिनों को कैसे बनाए रखेंगे?
परिभाषित करें कि कटऑफ ईवेंट समय का उपयोग करता है या सेवा समय का, फिर क्रम को संरक्षित करते हुए पुराने उपसर्ग (prefix) को समय-समय पर हटा दें। कटऑफ से पहले की क्वेरी को "इतिहास अनुपलब्ध" लौटाना चाहिए, न कि एक सामान्य मिस के रूप में दिखना चाहिए।
समवर्ती रीडर्स और राइटर्स के लिए क्या बदलता है?
पहले एक लीनियरइज़ेशन बिंदु को परिभाषित करें। एक सीधा डिज़ाइन प्रति-की रीड-राइट लॉक का उपयोग करता है। नॉन-ब्लॉकिंग रीड्स के लिए, एक नया ऐरे बनाएं और इसके संदर्भ को एटॉमिक रूप से स्वैप करें ताकि रीडर्स एक पूर्ण पुराना या नया स्नैपशॉट देख सकें।
क्रैश के बाद आप डेटा को कैसे बनाए रखेंगे (persist) और पुनर्प्राप्त करेंगे?
राइट को स्वीकार करने से पहले एक अनुक्रमित लॉग में अपेंड करें, समय-समय पर एक इंडेक्स स्नैपशॉट को मेटरियलाइज़ करें, और अनुक्रम संख्याओं को मान्य करते हुए रिकवरी के बाद प्रत्यय (suffix) को फिर से चलाएं। जब प्रॉम्प्ट केवल मेमोरी के लिए पूछे तो पूरा डेटाबेस डिज़ाइन न जोड़ें।