Saya melakukan wawancara dengan perusahaan hedge fund di New York beberapa bulan yang lalu dan sayangnya, saya tidak mendapatkan tawaran magang sebagai insinyur data / perangkat lunak. (Mereka juga meminta solusinya dengan Python.)

Saya cukup banyak mengacaukan masalah wawancara pertama ...

Pertanyaan: Diberikan string sejuta angka (Pi misalnya), tulis fungsi / program yang mengembalikan semua angka 3 digit berulang dan jumlah pengulangan lebih dari 1

Misalnya: jika stringnya adalah: 123412345123456maka fungsi / program akan mengembalikan:

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

Mereka tidak memberi saya solusi setelah saya gagal dalam wawancara, tetapi mereka memberi tahu saya bahwa kompleksitas waktu untuk solusi tersebut konstan 1000 karena semua kemungkinan hasil antara:

000 -> 999

Sekarang setelah saya memikirkannya, saya rasa tidak mungkin menghasilkan algoritma waktu yang konstan. Apakah itu?

Anda turun dengan ringan, Anda mungkin tidak ingin bekerja untuk hedge fund di mana quants tidak memahami algoritme dasar :-)

Tidak ada cara untuk memproses struktur data berukuran sewenang-wenang O(1)jika, seperti dalam kasus ini, Anda perlu mengunjungi setiap elemen setidaknya sekali. Yang terbaik yang dapat Anda harapkan adalah O(n)dalam hal ini, di mana npanjang senar.

Meskipun, sebagai tambahan, O(n)algoritme nominal akan digunakan O(1)untuk ukuran masukan tetap, jadi secara teknis, algoritme tersebut mungkin benar di sini. Namun, biasanya orang tidak menggunakan analisis kompleksitas seperti itu.

Menurut saya, Anda dapat membuat mereka terkesan dalam beberapa cara.

Pertama, dengan memberi tahu mereka bahwa tidak mungkin melakukannya O(1), kecuali Anda menggunakan alasan "tersangka" yang diberikan di atas.

Kedua, dengan menunjukkan keahlian elit Anda dengan memberikan kode Pythonic seperti:

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])

Output ini:

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

meskipun Anda dapat, tentu saja, mengubah format keluaran menjadi apapun yang Anda inginkan.

Dan, akhirnya, dengan memberi tahu mereka hampir pasti tidak ada masalah dengan O(n)solusi, karena kode di atas memberikan hasil untuk string satu juta digit dalam waktu kurang dari setengah detik. Tampaknya skala juga cukup linier, karena string 10.000.000 karakter membutuhkan waktu 3,5 detik dan 100.000.000 karakter membutuhkan waktu 36 detik.

Dan, jika mereka membutuhkan yang lebih baik dari itu, ada cara untuk memparalelkan hal-hal semacam ini yang bisa sangat mempercepatnya.

Tidak dalam satu interpreter Python tentu saja, karena GIL, tetapi Anda dapat membagi string menjadi sesuatu seperti (tumpang tindih yang ditunjukkan oleh vvdiperlukan untuk memungkinkan pemrosesan yang tepat dari area batas):

    vv
123412  vv
    123451
        5123456

Anda dapat mengumpulkan ini untuk pekerja terpisah dan menggabungkan hasilnya setelahnya.

Pemisahan input dan penggabungan output cenderung membanjiri penghematan dengan string kecil (dan mungkin bahkan string jutaan digit) tetapi, untuk kumpulan data yang jauh lebih besar, ini mungkin membuat perbedaan. Mantra saya yang biasa "mengukur, jangan menebak" berlaku di sini, tentu saja.

Mantra ini juga berlaku untuk kemungkinan lain , seperti melewati Python sama sekali dan menggunakan bahasa lain yang mungkin lebih cepat.

Misalnya, kode C berikut, yang berjalan pada perangkat keras yang sama dengan kode Python sebelumnya, menangani seratus juta digit dalam 0,6 detik, kira-kira jumlah waktu yang sama dengan kode Python yang memproses satu juta. Dengan kata lain, jauh lebih cepat:

#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;
}

Waktu yang konstan tidak memungkinkan. Semua 1 juta digit perlu dilihat setidaknya satu kali, jadi itu adalah kompleksitas waktu O (n), di mana n = 1 juta dalam kasus ini.

Untuk solusi O (n) sederhana, buat larik berukuran 1000 yang mewakili jumlah kemunculan setiap kemungkinan 3 digit angka. Maju 1 digit sekaligus, indeks pertama == 0, indeks terakhir == 999997, dan increment array [3 digit angka] untuk membuat histogram (jumlah kejadian untuk setiap kemungkinan 3 digit angka). Kemudian keluarkan konten array dengan jumlah> 1.

Satu juta kecil untuk jawaban yang saya berikan di bawah. Berharap hanya bahwa Anda harus dapat menjalankan solusi dalam wawancara, tanpa jeda, maka berikut ini bekerja dalam waktu kurang dari dua detik dan memberikan hasil yang diinginkan:

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)

Semoga pewawancara akan mencari penggunaan koleksi perpustakaan standar. Kelas Counter.

Versi eksekusi paralel

Saya menulis posting blog tentang ini dengan lebih banyak penjelasan.

Solusi O (n) sederhana adalah menghitung setiap angka 3-digit:

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

Ini akan mencari 1 juta digit 1000 kali.

Melintasi digit hanya sekali:

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)

Waktu menunjukkan bahwa iterasi hanya sekali di atas indeks dua kali lebih cepat daripada menggunakan count.

Berikut adalah implementasi NumPy dari algoritma "konsensus" O (n): telusuri semua triplet dan bin sambil jalan. Binning dilakukan dengan menemukan kata "385", menambahkan satu ke bin [3, 8, 5] yang merupakan operasi O (1). Tempat sampah diatur dalam 10x10x10kubus. Karena binning telah tervektorisasi sepenuhnya, tidak ada loop dalam kode.

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:]))

Tidak mengherankan, NumPy sedikit lebih cepat daripada solusi Python murni @ Daniel pada kumpulan data besar. Output sampel:

# 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

Saya akan menyelesaikan masalah sebagai berikut:

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

Diterapkan ke string contoh Anda, ini menghasilkan:

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

Solusi ini berjalan dalam O (n) karena n adalah panjang string yang disediakan, dan, saya rasa, yang terbaik yang bisa Anda dapatkan.

Menurut pemahaman saya, Anda tidak dapat memiliki solusi dalam waktu yang konstan. Ini akan membutuhkan setidaknya satu kali melewati jutaan digit angka (dengan asumsi itu adalah string). Anda dapat memiliki iterasi bergulir 3 digit di atas digit nomor panjang sejuta dan meningkatkan nilai kunci hash sebesar 1 jika sudah ada atau membuat kunci hash baru (diinisialisasi dengan nilai 1) jika belum ada di kamus.

Kode tersebut akan terlihat seperti ini:

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

Anda dapat memfilter kunci yang memiliki nilai item lebih besar dari 1.

Seperti yang disebutkan dalam jawaban lain, Anda tidak dapat melakukan algoritme ini dalam waktu konstan, karena Anda harus melihat setidaknya n digit. Waktu linier adalah yang tercepat yang bisa Anda dapatkan.

Namun, algoritma dapat dilakukan dalam O (1) ruang . Anda hanya perlu menyimpan hitungan setiap 3 digit angka, jadi Anda membutuhkan sebuah array yang terdiri dari 1000 entri. Anda kemudian dapat mengalirkan nomor tersebut.

Dugaan saya adalah bahwa pewawancara salah bicara ketika mereka memberi Anda solusi, atau Anda salah dengar "waktu konstan" ketika mereka mengatakan "ruang konstan".

Inilah jawaban saya:

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]))

Metode pencarian array sangat cepat (bahkan lebih cepat dari metode numpy @ paul-panzer!). Tentu saja, ini curang karena tidak selesai secara teknis setelah selesai, karena mengembalikan generator. Itu juga tidak harus memeriksa setiap iterasi jika nilainya sudah ada, yang kemungkinan akan sangat membantu.

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)]

Gambar sebagai jawaban:

Tampak seperti jendela geser.

Inilah solusi saya:

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}

Dengan sedikit kreativitas dalam perulangan (dan daftar pencarian tambahan dengan True / False / None misalnya), Anda seharusnya dapat menghilangkan baris terakhir, karena Anda hanya ingin membuat kunci di dict yang kami kunjungi sekali hingga saat itu . Semoga membantu :)

-Mengatakan dari perspektif C. -Anda dapat memiliki hasil array 3-d int [10] [10] [10]; -Pergi dari lokasi ke-0 ke lokasi n-ke-4, di mana n adalah ukuran larik string. -Pada setiap lokasi, periksa arus, berikutnya dan selanjutnya berikutnya. -Menambahkan cntr sebagai hasil [saat ini] [berikutnya] [berikutnya berikutnya] ++; -Cetak nilai

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]

-Ini adalah O (n) waktu, tidak ada perbandingan yang terlibat. -Anda dapat menjalankan beberapa hal paralel di sini dengan mempartisi array dan menghitung kecocokan di sekitar partisi.

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