J'écris une évaluation interne de l'entreprise dans Hackerrank en Python. J'ai une question comme ci-dessous. ce n'est pas une question exacte, car je ne pouvais pas copier de la page HackerRank.

Vous avez un papier de questions avec «n» questions. Les notes pour chaque question sont prédéfinies. Si une question a la valeur de réponse 1, vous obtenez +1 score, si elle est 0, vous obtenez -1 score pour cette question. Si vous répondez à un nombre «k» de questions, votre ami doit répondre à des questions «n-k».

Déterminez la valeur de k pour que votre score soit supérieur à celui de vos amis.

Exemple de cas:

Notes prédéfinies pour 10 questions: {1,0,1,0,1,1,0,0,1,1}

Vous devez répondre à au moins 6 questions pour que votre score soit supérieur à celui de votre ami.

J'ai écrit le code ci-dessous avec un exemple d'entrée. pouvez-vous m'aider à l'optimiser afin que l'exécution soit terminée en 10 secondes?

import numpy as np

arr= np.random.randint(0,2,500000)
n=len(arr)
#print(n)
#print(arr)
for m,x in enumerate(arr):
    k=n-m
    #print("m:", end=" ")
    #print(m)
    arr_k = arr[m:]
    arr_m = arr[:m]
    c1m = np.sum(arr_m == 1)
    c0m = np.sum(arr_m == 0)
    m_score = c1m - c0m
    c1k = np.sum(arr_k == 1)
    c0k = np.sum(arr_k == 0)
    k_score = c1k - c0k
    #print(m_score)
    #print(k_score)
    if m_score > k_score:
        print("Questions to be answered:", end=" ")
        print(m_score)
        break
  

La valeur de arr est fournie dans le cas de test dans hackerrank. Chaque fois que nous obtenons des valeurs différentes. je viens de mettre ici pour tester mon code.

0
Sailaja 2 sept. 2020 à 15:20

2 réponses

Meilleure réponse

Votre solution est proche, elle a juste besoin d'un léger ajustement (impact majeur) comme suit pour créer du code qui est O (n):

import numpy as np

arr= np.random.randint(0,2,100000)
arr[arr==0] = -1
n_score = np.sum(arr)
print("n_score:",n_score)
m_score = 0    # will use for running total
for m,x in enumerate(arr):
    #m_score = np.sum(arr[:m+1])  # replace this which is O(n)
    m_score += arr[m]             # with this which is O(1) (popular code pattern)
    k_score = n_score - m_score
    if m_score > k_score:
        print("Questions to be answered:", end=" ")
        print(m+1)
        break

Remarque: bien qu'aucun effet sur l'exécution ou la sortie, je suggérerais pour plus de clarté d'utiliser:

print(f"Questions to be answered: {m+1}")

Plutôt que:

print("Questions to be answered:", end=" ")
print(m+1)
0
DarrylG 4 sept. 2020 à 07:35

Voici la version mise à jour de mon code. toutes les suggestions sont les bienvenues.

import numpy as np

arr= np.random.randint(0,2,100000)
arr[arr==0] = -1
n_score = np.sum(arr)
print("n_score:",n_score)
for m,x in enumerate(arr):
    m_score = np.sum(arr[:m+1])
    k_score = n_score - m_score
    if m_score > k_score:
        print("Questions to be answered:", end=" ")
        print(m+1)
        break
0
Sailaja 3 sept. 2020 à 11:22