समस्या:

पाँच क्रमबद्ध संख्या सरणियाँ हैं और प्रत्येक सरणी से केवल एक संख्या चुनें। जांचें कि क्या पांच संख्याओं का योग 2018 हो सकता है। यदि कर सकते हैं, तो सत्य लौटाएं। अन्यथा, झूठी वापसी।

मेरा समाधान:

सबसे भोला...

sort the array in descending order
for a in arr1:
  for b in arr2:
     for c in arr3:
        for d in arr4:
           for e in arr5:
              if a+b+c+d+e == 2018:
                  return true
return false

मेरे समाधान का परिणाम:

समय सीमा से अधिक


यह एक ऐसी समस्या है जिसका मुझे साक्षात्कार में सामना करना पड़ रहा है। मुझे नहीं पता कि इसे कैसे हल किया जाए, इसलिए मदद मांगने के लिए यहां लिखें।

2
doUWannaBuildASnowMan 20 जून 2020, 06:19

2 जवाब

सरल विचार। पहले 3 सरणियों के योगों की एक क्रमबद्ध सूची ABC बनाएं। दूसरी 2 सरणियों के योगों की रिवर्स लिस्ट DE में क्रमबद्ध करें। यह अब तक जगह लेता है O(n^3) और समय O(n^3 log(n))

और अब ABC से तत्वों को DE के तत्वों के विरुद्ध जोड़ना शुरू करें। हर बार योग 2018 से कम होने पर ABC में अग्रिम करें। हर बार यह DE में अग्रिम से ऊपर है। यदि आप 2018 पाते हैं तो आपका उत्तर True है। वरना यह False है। वह अंतिम तुलना O(n^3 + n^2) है। कुल चलने का समय O(n^3 log(n)) है।

यदि आप प्राथमिकता कतारों के साथ चतुर हैं तो आप वास्तव में ABC को क्रमबद्ध क्रम में O(n^2) मेमोरी से अधिक का उपयोग करके उत्पन्न कर सकते हैं। हालांकि चलने के समय में सुधार नहीं किया जा सकता है।

1
btilly 20 जून 2020, 07:20

आपका प्रश्न सर्वकालिक सबसे सामान्य साक्षात्कार प्रश्न का व्युत्पन्न है, जो 2Sum है।


मुझे लगता है कि यह एल्गोरिथ्म इन तीन ब्लॉकों के साथ काम कर सकता है:

  • ए + बी के लिए काउंटर (सरणी 1 और सरणी 2)
  • सी + डी के लिए काउंटर (सरणी 3 और आगमन 4)
  • सरणी के माध्यम से लूप 5

तकनीकी रूप से, यह समय जटिलता विश्लेषण के लिए तीन अलग-अलग ब्लॉक होंगे:

# This block is O(N ^ 2)
for element in array 1
    for element in array 2
        generate dictionary 1 # O(N) space
# This block is O(N ^ 2)
for element in array 3
    for element in array 4
        generate dictionary 2 # O(N) space

# This block is O(N ^ 3)
for element in dictionary 1
    for element in dictionary 2
        for element in array 5
            if statement

फिर अंतरिक्ष जटिलता के लिए, यह दो शब्दकोश होंगे, प्रत्येक एक एन का क्रम है, फिर स्मृति ओ (एन) होगी।


यह एक O(N ^ 3) समय और O(N) अंतरिक्ष समाधान होगा।

अजगर

import collections


def five_sum(A, B, C, D, E):
    AB = collections.Counter(a + b for a in A for b in B) # O (N ^ 2)
    CD = collections.Counter(c + d for c in C for d in D) # O (N ^ 2)

    # O (N ^ 3)
    for ab in AB: 
        for cd in CD:
            for e in E:
                if ab + cd + e == 2018:
                    return True
    return False


A = [0, 2000]
B = [0, 10]
C = [0, 10]
D = [0, -1]
E = [0, -1]

print(five_sum(A, B, C, D, E))

उत्पादन

True

इसे और अधिक कुशल बनाना संभव है, लेकिन मुझे नहीं लगता कि समय की जटिलता बदलेगी।

0
Emma 20 जून 2020, 07:45