साक्षात्कार प्रश्न: factorials और कैशिंग

Question

मैं हाल ही में निम्नलिखित साक्षात्कार प्रश्न भर में आया था:

आप 1 के बीच और 100 आप कैश कर सकते 10 नंबर के लिए एक प्रणाली factorials के उत्तर प्रदान करने के लिए डिजाइन करने के लिए की जरूरत है। आप उस कैश को व्यवस्थित/प्रबंधित कैसे करेंगे, और कैश मिस पर लुकअप के लिए सबसे खराब स्थिति क्या है।

आपको क्या लगता है कि एक उपयुक्त उत्तर होगा और इसके पीछे तर्क क्या होगा? निजी तौर पर, मैं पहले इनपुट के लिए पहले दस नंबरों को कैश करता हूं, और उसके बाद सबसे हालिया इनपुट के आधार पर एक एलआरयू कैश बनाए रखता है क्योंकि लोग खोजों को दोहराने की अधिक संभावना रखते हैं। वास्तव में यह सुनिश्चित नहीं है कि कैश मिस पर लुकअप के लिए सबसे खराब मामला क्या होगा। शायद ओ (एन) यदि आप फैक्टोरियल फ़ंक्शन को लागू करने में गतिशील प्रोग्रामिंग दृष्टिकोण का उपयोग करते हैं। तुम क्या सोचते हो?

Answer 1

बाद में सबसे हाल ही में इनपुट के आधार पर एक LRU कैश बनाए रखने क्योंकि लोगों को अधिक खोजों

कि एक उचित डिजाइन विकल्प हो सकता है दोहराने की संभावना है, लेकिन साक्षात्कार में मैं वाक्यांश अधिक के रूप में है कि चाहते साक्षात्कारकर्ता से एक प्रश्न: "क्या यह मानना ​​उचित होगा कि कॉल हाल के मूल्यों के साथ और अधिक होने की तरह होंगे, या क्या कोई अन्य अपेक्षित समूह है (बड़ी संख्या में अक्सर छोटे या इसके विपरीत अनुरोध किया जाएगा)?"

उदाहरण के लिए, एलआरयू को कैश करने का अर्थ हो सकता है, लेकिन 10, 20, 30, 40 इत्यादि के लिए मूल्यों को कभी भी फेंकना नहीं है। इस तरह कैश को उन मानों के साथ भरने के बाद एक फैक्टरियल की गणना करने का सबसे बुरा मामला है 10 गुणा प्रदर्शन करना है।

एक अन्य विचार आप कर सकता है कि कंप्यूटर बहुत आसानी से कुछ factorials के साथ सौदा कर सकते हैं:

• 12! 32-बिट शब्द में सबसे बड़ा है।
• 20! 64-बिट शब्द में सबसे बड़ा है।
• 34! 128-बिट शब्द में सबसे बड़ा है जिसे रखा जा सकता है।

चूंकि आज की मशीनें 64-बिट अंकगणित (शायद 128 बिट अंकगणितीय) से आसानी से निपट सकती हैं, तो यह भी समझ सकता है कि 20 के लिए कोई मूल्य कैश नहीं किया जा सकता है! या एक बार कैश उस से अधिक मूल्यों के साथ भर जाता है।

कैश मिस पर लुकअप के लिए सबसे खराब मामला इस बात पर निर्भर करेगा कि आप कैश को कैसे स्टोर करते हैं। क्या यह एक सरणी है जो फ़ंक्शन के तर्क द्वारा क्रमबद्ध है? (लुकअप ओ है (लॉग एन)) क्या यह एलआरयू ऑर्डर में एक सरणी है?(कैश मिस पर देखो ओ (एन) है)। मुझे लगता है कि आप यह भी स्पष्ट करना चाहते हैं कि आप कैश लुकअप को हमेशा कैश में उच्चतम मान वापस करना चाहते हैं जो कि आप जो खोज रहे हैं उससे कम है - वह कैश मान उस काम का प्रतिनिधित्व करता है जिसे आपको करने की ज़रूरत नहीं है इस विशेष फैक्टरियल गणना के लिए।

Answer 2

यहां विचार कुछ संख्याओं का चयन करना है, इसलिए उनसे दूसरों की गणना करना संभव है। मान लें कि आपके सिस्टम को निरंतर गति और कोई विभाजन नहीं है, कैशिंग (या "प्री-गणना") 1 !, 11 !, 21 !, 31 !, 41 !, 51 !, 61 !, 81 !, 91! प्रत्येक के लिए अधिकतम 9 गुणाओं के साथ सभी शेष संख्याओं की गणना करने की अनुमति देता है।

वास्तविकता में बड़ी संख्या में गुणा करना अधिक महंगा है, और आप विभाजन भी कर सकते हैं (उदाहरण के लिए 90! = 91!/9 1), और आपको वास्तव में 1 की आवश्यकता नहीं है, जो उन एंकरों का एक और इष्टतम वितरण कर सकता है संख्या।

Answer 3

10, 20, 30, 40, 50, 60, 70, 80, और 9 0 के फैक्टोरियल के लिए 9 कैश स्लॉट का उपयोग करने के बारे में कैसे? 10 वीं स्लॉट एलआरयू हो सकती है। सबसे खराब केस लुकअप तब ओ (10) या निरंतर समय है।

Answer 4

मेरा विचार कुछ हद तक कॉनोरडॉयल की तरह है, मैं 10 के सभी गुणकों को कैश कर दूंगा। इस बात के बारे में कोई जानकारी नहीं है कि उपयोगकर्ता इसे बनाएंगे, यह आपको 7 गुणाओं/डिवीजनों के सबसे छोटे मामले के परिदृश्य के साथ छोड़ देगा मूल दो और दस अंकों, या निरंतर समय खोजने के लिए मूल दो। मेरे सिर के ऊपर से

एक त्वरित छद्म-कलन विधि:

total; 
mod = input%10; 
div = input/10; 
if(input%10 == 0) 
    output(cache[input/10]); 
else{ 
    if(mod < 5) { 
     total = cache[div]; 
     for(i = 1; i<=mod; i++) 
      total = total * (cache[div] + i); 
    } 
    else { 
     total = cache[div + 1]; 
     for(i = 9; i>mod; i--) 
      total = total/(cache[div] + i); 
    } 
    output(total); 
} 

सबसे खराब मामला वाले अंकों में 5 के साथ कुछ भी हो सकता है।