पाठ्यक्रम 148 में से पाठ 50 · उधार की मशीनें
उधार की मशीनें

Hold queue उधार लें: निष्पक्ष reservations

यह क्यों मायने रखता है शुरू से बने reservation सिस्टम सबसे तेज़ click करने वाले को इनाम देने की ओर झुकते हैं, या एक न आने वाले को सबको रोकने देते हैं। जो जगहें हर दिन लोगों को दुर्लभ चीज़ें बाँटती हैं वे बहुत पहले एक बेहतर डिज़ाइन पर पहुँचीं।

तीन counters

एक library hold। आप बाहर गई एक किताब पर hold लगाते हैं। जब एक copy लौटती है, वह hold queue के पहले व्यक्ति को जाती है, जिसे एक संदेश और उसे लेने के कुछ दिन मिलते हैं। अगर वे न आएँ, copy अगले व्यक्ति को जाती है, और पहला अपनी जगह खो देता है।

एक buzzer वाली restaurant प्रतीक्षा सूची। आप अपना नाम देते हैं और एक buzzer पाते हैं। जब एक table ख़ाली होती है, अगली पार्टी को buzz किया जाता है और उसके पास host stand तक पहुँचने के लिए पाँच मिनट हैं, नहीं तो table अगली पार्टी को जाती है।

Deli counter का ticket। आप एक नंबर लेते हैं। जब आपका नंबर बुलाया जाए और आप वहाँ न हों, अगला नंबर बुलाया जाता है। आप एक नया ticket ले सकते हैं, पीछे।

code से पहले तुलना करें

  1. हर एक में, line में आपकी जगह कब तय होती है: जब आप माँगते हैं, या जब चीज़ ख़ाली होती है?
  2. न आने वाले व्यक्ति का क्या होता है, और उन्हें कितना समय मिलता है?
  3. चीज़ का क्या होता है जब वह किसी के लेने का इंतज़ार करती है?
  4. साझा नियम एक वाक्य में कहें जो किताबों, tables या मांस का ज़िक्र न करे।

लक्ष्य

mobile टीम test फ़ोनों की एक छोटी lab साझा करती है। Engineers एक model माँगते हैं; जब उस model का एक फ़ोन ख़ाली हो, वह उन्हें दिया जाता है, और उन्हें उसे दो घंटे के अंदर lab ऐप में claim करना होता है। एक claim किया फ़ोन आठ घंटे के slot के लिए book होता है और फिर अपने आप लौटता है। आज ऐप एक ख़ाली फ़ोन उसे देता है जो पहले "claim" दबाए, और लोगों ने उसे दबाने के लिए scripts लिखनी शुरू कर दी हैं।

stock = [("dev1", "pixel")]
events = [("request", 0, "ana", "pixel"), ("request", 5, "ben", "pixel"),
          ("claim", 10, "ben", "pixel"), ("claim", 30, "ana", "pixel")]
loans(stock, events)   # -> [("ana", "dev1", 30)]  (ben is not first)
आपकी बारी

loans(stock, events) लिखें। stock (device_id, model) सूचीबद्ध करता है, सब समय 0 पर ख़ाली। events ("request", t, person, model) या ("claim", t, person, model) हैं, मिनटों में समय t से sorted। नियम:

  1. हर model की request क्रम में एक queue है। एक request नज़रअंदाज़ होती है अगर वह व्यक्ति उस model के लिए पहले से queue में है, या उस पर एक offer रखता है।
  2. एक ख़ाली फ़ोन उसके model की queue के पहले व्यक्ति को दिया जाता है (वे queue छोड़ देते हैं)। अगर कोई queue में नहीं, वह shelf पर इंतज़ार करता है, और उस model की एक बाद की request उसे तुरंत पाती है। shelf पर कई के साथ, सबसे छोटी device id दें।
  3. समय o पर दिया एक offer तब तक claim हो सकता है जब तक t < o + 120। उस व्यक्ति और model के लिए बिना live offer वाला claim नज़रअंदाज़ होता है।
  4. o + 120 पर एक बिना claim offer समाप्त होता है और फ़ोन उसी पल फिर ख़ाली होता है (नियम 2)।
  5. समय t पर एक claim एक loan शुरू करता है; फ़ोन t + 480 पर ख़ाली होता है।
  6. एक event के समय पर या उससे पहले देय समाप्तियाँ और वापसियाँ उससे पहले होती हैं, समय के क्रम में, फिर device id।
loans को (person, device_id, claim_time) के रूप में उस क्रम में लौटाएँ जिसमें वे claim हुए।

इस पाठ में कोई समस्या दिखी? बताएँ · इस पाठ के बारे में पूछें

यह अभ्यास जल्द खुलेगा

इससे पहले वाला पाठ पूरा करें और यह खुल जाएगा। पूरा कोर्स मुफ़्त है, कोई खाता नहीं चाहिए, और आप यह पाठ अभी पढ़ सकते हैं।