पाठ्यक्रम 148 में से पाठ 55 · cache के बिना रफ़्तार
cache के बिना रफ़्तार

दो pointers, कोई table नहीं

यह क्यों मायने रखता है "दो चीज़ें ढूँढो जो X तक जुड़ें" का एक मशहूर जवाब है: सब कुछ एक set में रखो और साथी खोजो। यह तेज़ है, और इसे सारे डेटा की एक copy चाहिए। जब डेटा sorted हो, आपको लगभग कोई memory नहीं चाहिए।

एक gift service एक तय bundle क़ीमत पर दो अलग products के bundles बेचती है। product क़ीमत सूची sorted है, उसमें कोई दोहराव नहीं, और यह बहुत कम ख़ाली memory वाले एक embedded device पर बैठती है। एक bundle क़ीमत के लिए, आपको उन product जोड़ों की संख्या चाहिए जिनकी क़ीमतें ठीक उस क़ीमत तक जुड़ें।

prices = [1, 2, 3, 4, 5, 6]   # sorted, no repeats
count_pairs(Tape(prices), 7)    # 3: (1, 6), (2, 5), (3, 4)
आपकी बारी

count_pairs(tape, target) लिखें। tape पूर्ण-संख्या क़ीमतों का एक Tape है, बढ़ते क्रम में sorted, बिना दोहराव के। लौटाएँ कि दो अलग items के कितने जोड़े ठीक target तक जुड़ते हैं (हर जोड़ा एक बार गिना)। Budgets: 20,000 items के लिए ज़्यादा से ज़्यादा 60,000 मान पढ़ें, और आपके function के चलते समय ज़्यादा से ज़्यादा 16,000 bytes working memory इस्तेमाल करें (tracemalloc से मापी; 20,000 क़ीमतों का एक set या सूची 150,000 bytes से ऊपर है)। len(tape) मुफ़्त है।

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

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

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