Ich hatte vor einigen Monaten ein Interview mit einer Hedgefondsfirma in New York und leider habe ich das Praktikumsangebot als Daten- / Software-Ingenieur nicht erhalten. (Sie baten auch um die Lösung in Python.)

Ich habe das erste Interviewproblem ziemlich vermasselt ...

Frage: Schreiben Sie bei einer Zeichenfolge von einer Million Zahlen (z. B. Pi) eine Funktion / ein Programm, die alle sich wiederholenden dreistelligen Zahlen und die Anzahl der Wiederholungen größer als 1 zurückgibt

Beispiel: Wenn der String: 123412345123456wäre, würde die Funktion / das Programm Folgendes zurückgeben:

123 - 3 times
234 - 3 times
345 - 2 times

Sie gaben mir die Lösung nicht, nachdem ich das Interview nicht bestanden hatte, aber sie sagten mir, dass die zeitliche Komplexität für die Lösung konstant 1000 war, da alle möglichen Ergebnisse zwischen:

000 -> 999

Jetzt, wo ich darüber nachdenke, denke ich nicht, dass es möglich ist, einen Algorithmus mit konstanter Zeit zu entwickeln. Ist es?

Sie sind leichtfertig ausgestiegen und möchten wahrscheinlich nicht für einen Hedgefonds arbeiten, bei dem die Quants grundlegende Algorithmen nicht verstehen :-)

Es gibt keine Möglichkeit, eine Datenstruktur beliebiger Größe zu verarbeiten, O(1)wenn Sie wie in diesem Fall jedes Element mindestens einmal besuchen müssen. Das Beste, auf das Sie hoffen können, ist O(n)in diesem Fall, wo ndie Länge der Zeichenfolge ist.

Obwohl, wie nebenbei bemerkt, ein nominaler O(n)Algorithmus wird sein O(1)für eine feste Eingangsgröße so, technisch gesehen , kann sie richtig hier gewesen. Normalerweise verwenden Menschen die Komplexitätsanalyse jedoch nicht so.

Mir scheint, Sie hätten sie auf verschiedene Weise beeindrucken können.

Indem Sie sie zunächst darüber informieren, dass dies nicht möglich ist, es O(1)sei denn, Sie verwenden die oben angegebene "verdächtige" Argumentation.

Zweitens, indem Sie Ihre Elite-Fähigkeiten unter Beweis stellen, indem Sie Pythonic-Code wie den folgenden bereitstellen:

inpStr = '123412345123456'

# O(1) array creation.
freq = [0] * 1000

# O(n) string processing.
for val in [int(inpStr[pos:pos+3]) for pos in range(len(inpStr) - 2)]:
    freq[val] += 1

# O(1) output of relevant array values.
print ([(num, freq[num]) for num in range(1000) if freq[num] > 1])

Dies gibt aus:

[(123, 3), (234, 3), (345, 2)]

Natürlich können Sie das Ausgabeformat nach Belieben ändern.

Und schließlich, wenn man ihnen sagt, dass es mit ziemlicher Sicherheit keine gibt Problem mit einer O(n)Lösung, da der obige Code in weniger als einer halben Sekunde Ergebnisse für eine einstellige Zeichenfolge liefert. Es scheint auch ziemlich linear zu skalieren, da eine Zeichenfolge mit 10.000.000 Zeichen 3,5 Sekunden und eine Zeichenfolge mit 100.000.000 Zeichen 36 Sekunden dauert.

Und wenn sie Besseres brauchen , gibt es Möglichkeiten, solche Dinge zu parallelisieren, die es erheblich beschleunigen können.

Natürlich nicht innerhalb eines einzelnen Python-Interpreters, aufgrund der GIL, aber Sie könnten die Zeichenfolge in so etwas aufteilen (eine Überlappung vvist erforderlich, um eine ordnungsgemäße Verarbeitung der Grenzbereiche zu ermöglichen):

    vv
123412  vv
    123451
        5123456

Sie können diese auf separate Mitarbeiter verteilen und die Ergebnisse anschließend kombinieren.

Die Aufteilung der Eingabe und die Kombination der Ausgabe überschwemmen wahrscheinlich jede Einsparung mit kleinen Zeichenfolgen (und möglicherweise sogar Zeichenfolgen mit Millionen Ziffern), aber bei viel größeren Datenmengen kann dies durchaus einen Unterschied bewirken. Hier gilt natürlich mein übliches Mantra "Messen, nicht raten" .

Dieses Mantra gilt auch für andere Möglichkeiten, z. B. die Umgehung von Python insgesamt und die Verwendung einer anderen Sprache, die möglicherweise schneller ist.

Der folgende C-Code, der auf derselben Hardware wie der frühere Python-Code ausgeführt wird, verarbeitet beispielsweise hundert Millionen Ziffern in 0,6 Sekunden, ungefähr so ​​lange, wie der Python-Code eine Million verarbeitet hat . Mit anderen Worten, viel schneller:

#include <stdio.h>
#include <string.h>

int main(void) {
    static char inpStr[100000000+1];
    static int freq[1000];

    // Set up test data.

    memset(inpStr, '1', sizeof(inpStr));
    inpStr[sizeof(inpStr)-1] = '\0';

    // Need at least three digits to do anything useful.

    if (strlen(inpStr) <= 2) return 0;

    // Get initial feed from first two digits, process others.

    int val = (inpStr[0] - '0') * 10 + inpStr[1] - '0';
    char *inpPtr = &(inpStr[2]);
    while (*inpPtr != '\0') {
        // Remove hundreds, add next digit as units, adjust table.

        val = (val % 100) * 10 + *inpPtr++ - '0';
        freq[val]++;
    }

    // Output (relevant part of) table.

    for (int i = 0; i < 1000; ++i)
        if (freq[i] > 1)
            printf("%3d -> %d\n", i, freq[i]);

    return 0;
}

Konstante Zeit ist nicht möglich. Alle 1 Million Stellen müssen mindestens einmal betrachtet werden, so dass dies eine zeitliche Komplexität von O (n) ist, wobei in diesem Fall n = 1 Million ist.

Erstellen Sie für eine einfache O (n) -Lösung ein Array der Größe 1000, das die Anzahl der Vorkommen jeder möglichen dreistelligen Zahl darstellt. Stellen Sie jeweils 1 Stelle, den ersten Index == 0, den letzten Index == 999997 und das Inkrementarray [3-stellige Zahl] vor, um ein Histogramm zu erstellen (Anzahl der Vorkommen für jede mögliche 3-stellige Zahl). Geben Sie dann den Inhalt des Arrays mit einer Anzahl> 1 aus.

Eine Million ist klein für die Antwort, die ich unten gebe. Erwarten Sie nur, dass Sie in der Lage sein müssen, die Lösung im Interview ohne Pause auszuführen. Dann funktioniert Folgendes in weniger als zwei Sekunden und liefert das erforderliche Ergebnis:

from collections import Counter

def triple_counter(s):
    c = Counter(s[n-3: n] for n in range(3, len(s)))
    for tri, n in c.most_common():
        if n > 1:
            print('%s - %i times.' % (tri, n))
        else:
            break

if __name__ == '__main__':
    import random

    s = ''.join(random.choice('0123456789') for _ in range(1_000_000))
    triple_counter(s)

Hoffentlich würde der Interviewer nach der Verwendung der Standardbibliothekssammlungen suchen. Gegenklasse.

Parallele Ausführungsversion

Ich habe einen Blog-Beitrag dazu mit mehr Erklärungen geschrieben.

Die einfache O (n) -Lösung wäre, jede dreistellige Zahl zu zählen:

for nr in range(1000):
    cnt = text.count('%03d' % nr)
    if cnt > 1:
        print '%03d is found %d times' % (nr, cnt)

Dies würde 1000 Mal alle 1 Million Ziffern durchsuchen.

Die Ziffern nur einmal durchlaufen:

counts = [0] * 1000
for idx in range(len(text)-2):
    counts[int(text[idx:idx+3])] += 1

for nr, cnt in enumerate(counts):
    if cnt > 1:
        print '%03d is found %d times' % (nr, cnt)

Das Timing zeigt, dass die Iteration nur einmal über den Index doppelt so schnell ist wie die Verwendung count.

Hier ist eine NumPy-Implementierung des "Consensus" O (n) -Algorithmus: Gehen Sie alle Triplets und Bin durch, während Sie gehen. Das Binning erfolgt, indem Sie auf "385" stoßen und eins zu bin [3, 8, 5] hinzufügen, was eine O (1) -Operation ist. Die Behälter sind in einem 10x10x10Würfel angeordnet . Da das Binning vollständig vektorisiert ist, enthält der Code keine Schleife.

def setup_data(n):
    import random
    digits = "0123456789"
    return dict(text = ''.join(random.choice(digits) for i in range(n)))

def f_np(text):
    # Get the data into NumPy
    import numpy as np
    a = np.frombuffer(bytes(text, 'utf8'), dtype=np.uint8) - ord('0')
    # Rolling triplets
    a3 = np.lib.stride_tricks.as_strided(a, (3, a.size-2), 2*a.strides)

    bins = np.zeros((10, 10, 10), dtype=int)
    # Next line performs O(n) binning
    np.add.at(bins, tuple(a3), 1)
    # Filtering is left as an exercise
    return bins.ravel()

def f_py(text):
    counts = [0] * 1000
    for idx in range(len(text)-2):
        counts[int(text[idx:idx+3])] += 1
    return counts

import numpy as np
import types
from timeit import timeit
for n in (10, 1000, 1000000):
    data = setup_data(n)
    ref = f_np(**data)
    print(f'n = {n}')
    for name, func in list(globals().items()):
        if not name.startswith('f_') or not isinstance(func, types.FunctionType):
            continue
        try:
            assert np.all(ref == func(**data))
            print("{:16s}{:16.8f} ms".format(name[2:], timeit(
                'f(**data)', globals={'f':func, 'data':data}, number=10)*100))
        except:
            print("{:16s} apparently crashed".format(name[2:]))

Es überrascht nicht, dass NumPy bei großen Datenmengen etwas schneller ist als die reine Python-Lösung von @ Daniel. Beispielausgabe:

# n = 10
# np                    0.03481400 ms
# py                    0.00669330 ms
# n = 1000
# np                    0.11215360 ms
# py                    0.34836530 ms
# n = 1000000
# np                   82.46765980 ms
# py                  360.51235450 ms

Ich würde das Problem wie folgt lösen:

def find_numbers(str_num):
    final_dict = {}
    buffer = {}
    for idx in range(len(str_num) - 3):
        num = int(str_num[idx:idx + 3])
        if num not in buffer:
            buffer[num] = 0
        buffer[num] += 1
        if buffer[num] > 1:
            final_dict[num] = buffer[num]
    return final_dict

Auf Ihre Beispielzeichenfolge angewendet ergibt dies:

>>> find_numbers("123412345123456")
{345: 2, 234: 3, 123: 3}

Diese Lösung läuft in O (n), wobei n die Länge der bereitgestellten Zeichenfolge ist, und ich denke, sie ist die beste, die Sie bekommen können.

Nach meinem Verständnis können Sie die Lösung nicht in einer konstanten Zeit haben. Es dauert mindestens einen Durchgang über die millionenstellige Zahl (vorausgesetzt, es handelt sich um eine Zeichenfolge). Sie können eine dreistellige fortlaufende Iteration über die Ziffern der Millionenlänge durchführen und den Wert des Hash-Schlüssels um 1 erhöhen, wenn er bereits vorhanden ist, oder einen neuen Hash-Schlüssel (initialisiert durch den Wert 1) erstellen, wenn er noch nicht vorhanden ist das Wörterbuch.

Der Code sieht ungefähr so ​​aus:

def calc_repeating_digits(number):

    hash = {}

    for i in range(len(str(number))-2):

        current_three_digits = number[i:i+3]
        if current_three_digits in hash.keys():
            hash[current_three_digits] += 1

        else:
            hash[current_three_digits] = 1

    return hash

Sie können bis zu den Schlüsseln filtern, deren Elementwert größer als 1 ist.

Wie in einer anderen Antwort erwähnt, können Sie diesen Algorithmus nicht in konstanter Zeit ausführen, da Sie mindestens n Ziffern betrachten müssen. Die lineare Zeit ist die schnellste, die Sie bekommen können.

Der Algorithmus kann jedoch im O (1) -Raum durchgeführt werden . Sie müssen nur die Anzahl jeder dreistelligen Nummer speichern, sodass Sie ein Array mit 1000 Einträgen benötigen. Sie können die Nummer dann streamen.

Ich vermute, dass entweder der Interviewer falsch geschrieben hat, als er Ihnen die Lösung gegeben hat, oder dass Sie "konstante Zeit" falsch gehört haben, als er "konstanter Raum" sagte.

Hier ist meine Antwort:

from timeit import timeit
from collections import Counter
import types
import random

def setup_data(n):
    digits = "0123456789"
    return dict(text = ''.join(random.choice(digits) for i in range(n)))


def f_counter(text):
    c = Counter()
    for i in range(len(text)-2):
        ss = text[i:i+3]
        c.update([ss])
    return (i for i in c.items() if i[1] > 1)

def f_dict(text):
    d = {}
    for i in range(len(text)-2):
        ss = text[i:i+3]
        if ss not in d:
            d[ss] = 0
        d[ss] += 1
    return ((i, d[i]) for i in d if d[i] > 1)

def f_array(text):
    a = [[[0 for _ in range(10)] for _ in range(10)] for _ in range(10)]
    for n in range(len(text)-2):
        i, j, k = (int(ss) for ss in text[n:n+3])
        a[i][j][k] += 1
    for i, b in enumerate(a):
        for j, c in enumerate(b):
            for k, d in enumerate(c):
                if d > 1: yield (f'{i}{j}{k}', d)


for n in (1E1, 1E3, 1E6):
    n = int(n)
    data = setup_data(n)
    print(f'n = {n}')
    results = {}
    for name, func in list(globals().items()):
        if not name.startswith('f_') or not isinstance(func, types.FunctionType):
            continue
        print("{:16s}{:16.8f} ms".format(name[2:], timeit(
            'results[name] = f(**data)', globals={'f':func, 'data':data, 'results':results, 'name':name}, number=10)*100))
    for r in results:
        print('{:10}: {}'.format(r, sorted(list(results[r]))[:5]))

Die Array-Suchmethode ist sehr schnell (sogar schneller als die Numpy-Methode von @ paul-panzer!). Natürlich betrügt es, da es nach Abschluss nicht technisch fertig ist, weil es einen Generator zurückgibt. Es muss auch nicht jede Iteration überprüft werden, ob der Wert bereits vorhanden ist, was wahrscheinlich sehr hilfreich ist.

n = 10
counter               0.10595780 ms
dict                  0.01070654 ms
array                 0.00135370 ms
f_counter : []
f_dict    : []
f_array   : []
n = 1000
counter               2.89462101 ms
dict                  0.40434612 ms
array                 0.00073838 ms
f_counter : [('008', 2), ('009', 3), ('010', 2), ('016', 2), ('017', 2)]
f_dict    : [('008', 2), ('009', 3), ('010', 2), ('016', 2), ('017', 2)]
f_array   : [('008', 2), ('009', 3), ('010', 2), ('016', 2), ('017', 2)]
n = 1000000
counter            2849.00500992 ms
dict                438.44007806 ms
array                 0.00135370 ms
f_counter : [('000', 1058), ('001', 943), ('002', 1030), ('003', 982), ('004', 1042)]
f_dict    : [('000', 1058), ('001', 943), ('002', 1030), ('003', 982), ('004', 1042)]
f_array   : [('000', 1058), ('001', 943), ('002', 1030), ('003', 982), ('004', 1042)]

Bild als Antwort:

Sieht aus wie ein Schiebefenster.

Hier ist meine Lösung:

from collections import defaultdict
string = "103264685134845354863"
d = defaultdict(int)
for elt in range(len(string)-2):
    d[string[elt:elt+3]] += 1
d = {key: d[key] for key in d.keys() if d[key] > 1}

Mit ein wenig Kreativität in der for-Schleife (und einer zusätzlichen Suchliste mit True / False / None zum Beispiel) sollten Sie in der Lage sein, die letzte Zeile loszuwerden, da Sie nur Schlüssel in Diktaten erstellen möchten, die wir bis zu diesem Zeitpunkt einmal besucht haben . Ich hoffe es hilft :)

- Erzählen aus der Perspektive von C. - Sie können int-3-d-Array-Ergebnisse erzielen [10] [10] [10]; -Gehen Sie von der 0. Position zur n-4. Position, wobei n die Größe des String-Arrays ist. -Überprüfen Sie an jedem Ort den aktuellen, den nächsten und den nächsten. -Inkrementiere den cntr als resutls [current] [next] [next's next] ++; -Drucken Sie die Werte von

results[1][2][3]
results[2][3][4]
results[3][4][5]
results[4][5][6]
results[5][6][7]
results[6][7][8]
results[7][8][9]

-Es ist O (n) Zeit, es gibt keine Vergleiche. -Sie können hier einige parallele Dinge ausführen, indem Sie das Array partitionieren und die Übereinstimmungen um die Partitionen berechnen.

inputStr = '123456123138276237284287434628736482376487234682734682736487263482736487236482634'

count = {}
for i in range(len(inputStr) - 2):
    subNum = int(inputStr[i:i+3])
    if subNum not in count:
        count[subNum] = 1
    else:
        count[subNum] += 1

print count