Thuật toán đố phỏng vấn

Question

Tôi thấy câu hỏi phỏng vấn này, và tôi không thể đưa ra một thuật toán tốt hơn so với O (N^2 * P):

Cho một vector của các số tự nhiên P (1,2 , 3, ..., P) và một vectơ có chiều dài N khác có các phần tử từ vector đầu tiên, tìm chuỗi dài nhất trong vector thứ hai, sao cho tất cả các phần tử được phân bố đồng đều (có cùng tần số).

Ví dụ: (1,2,3) và (1, 2,1,3,2,1,3,1,2,3, 1). Đoạn dài nhất là trong khoảng [2,10], bởi vì nó chứa tất cả các phần tử từ dãy đầu tiên có cùng tần số (1 xuất hiện ba lần, 2 ba lần, và 3 ba lần).

Độ phức tạp thời gian phải là O (N * P).

Answer 1

"Hậu quả" thường có nghĩa là không liền kề. Tôi sẽ giả định rằng bạn có nghĩa là "danh sách phụ".

Đây là thuật toán O (N P) giả sử chúng ta có thể băm (giả định không cần thiết; chúng tôi có thể sắp xếp theo thứ tự thay thế). Quét mảng giữ tổng số đang chạy cho mỗi số. Ví dụ:

1 2 3 
-------- 
    0 0 0 
1 
    1 0 0 
2 
    1 1 0 
1 
    2 1 0 
3 
    2 1 1 
2 
    2 2 1 
1 
    3 2 1 
3 
    3 2 2 
1 
    4 2 2 
2 
    4 3 2 
3 
    4 3 3 
1 
    5 3 3 

Bây giờ, chuẩn hóa mỗi hàng bằng cách trừ phần tử tối thiểu. Kết quả là

0: 000 
1: 100 
2: 110 
3: 210 
4: 100 
5: 110 
6: 210 
7: 100 
8: 200 
9: 210 
10: 100 
11: 200. 

Chuẩn bị hai băm, ánh xạ mỗi hàng đến chỉ mục đầu tiên xuất hiện và chỉ mục cuối cùng xuất hiện. Lặp lại thông qua các phím và lấy một với tối đa cuối cùng - đầu tiên.

000: first is at 0, last is at 0 
100: first is at 1, last is at 10 
110: first is at 2, last is at 5 
210: first is at 3, last is at 9 
200: first is at 8, last is at 11 

Khóa tốt nhất là 100, vì danh sách con của nó có chiều dài 9. Danh sách con là phần tử thứ 1 (1 + 1) vào ngày 10.

Điều này hoạt động vì danh sách con được cân bằng nếu và chỉ khi biểu đồ không chuẩn hóa đầu tiên và cuối cùng của nó giống nhau để thêm hằng số, xảy ra nếu và chỉ khi biểu đồ chuẩn hóa đầu tiên và cuối cùng giống hệt nhau.

Answer 2

Dưới đây là một quan sát: bạn không thể nhận được chuỗi được phân bố đồng đều, không phải là phép nhân dài P. Điều này ngụ ý rằng bạn chỉ phải kiểm tra các chuỗi phụ của N là các chuỗi P, 2P, 3P ... dài - (N/P)^2 như vậy.

Answer 3

Nếu sử dụng bộ nhớ là không quan trọng, thật dễ dàng ...

Bạn có thể cung cấp cho các kích thước ma trận N*p và lưu trong cột (i) giá trị tương ứng với bao nhiêu yếu tố p đang tìm kiếm giữa (i) phần tử đầu tiên trong vector thứ hai ...

Sau khi hoàn thành ma trận, bạn có thể tìm kiếm cột i rằng tất cả các phần tử trong cột i không khác nhau. Tối đa i là câu trả lời.

Answer 4

Với tính năng ngẫu nhiên hóa, bạn có thể chuyển nó xuống thời gian tuyến tính. Ý tưởng là thay thế mỗi giá trị P bằng một số nguyên ngẫu nhiên, sao cho các số nguyên đó tổng bằng không.Bây giờ hãy tìm hai tiền tố bằng nhau. Điều này cho phép một số cơ hội giả mạo nhỏ, mà chúng tôi có thể khắc phục bằng cách kiểm tra đầu ra của chúng tôi.

Trong Python 2.7:

# input: 
vec1 = [1, 2, 3] 
P = len(vec1) 
vec2 = [1, 2, 1, 3, 2, 1, 3, 1, 2, 3, 1] 
N = len(vec2) 
# Choose big enough integer B. For each k in vec1, choose 
# a random mod-B remainder r[k], so their mod-B sum is 0. 
# Any P-1 of these remainders are independent. 
import random 
B = N*N*N 
r = dict((k, random.randint(0,B-1)) for k in vec1) 
s = sum(r.values())%B 
r[vec1[0]] = (r[vec1[0]]+B-s)%B 
assert sum(r.values())%B == 0 
# For 0<=i<=N, let vec3[i] be mod-B sum of r[vec2[j]], for j<i. 
vec3 = [0] * (N+1) 
for i in range(1,N+1): 
    vec3[i] = (vec3[i-1] + r[vec2[i-1]]) % B 
# Find pair (i,j) so vec3[i]==vec3[j], and j-i is as large as possible. 
# This is either a solution (subsequence vec2[i:j] is uniform) or a false 
# positive. The expected number of false positives is < N*N/(2*B) < 1/N. 
(i, j)=(0, 0) 
first = {} 
for k in range(N+1): 
    v = vec3[k] 
    if v in first: 
     if k-first[v] > j-i: 
      (i, j) = (first[v], k) 
    else: 
     first[v] = k 
# output: 
print "Found subsequence from", i, "(inclusive) to", j, "(exclusive):" 
print vec2[i:j] 
print "This is either uniform, or rarely, it is a false positive." 

Answer 5

Bạn có thể có được điều này xuống O (N) thời gian, không có sự phụ thuộc vào P bằng cách tăng cường giải pháp UTY của.

Đối với mỗi hàng, thay vì lưu trữ số lượng chuẩn hóa của từng phần tử, hãy lưu trữ giá trị băm chuẩn hóa trong khi chỉ giữ số đếm bình thường cho chỉ mục hiện tại. Trong mỗi lần lặp lại, trước tiên bạn cần phải cập nhật số đếm chuẩn hóa, trong đó có một chi phí phân bổ của O (1) nếu mỗi lần giảm số được trả cho khi nó được tăng lên. Tiếp theo bạn tính toán lại băm. Chìa khóa ở đây là hash cần phải dễ dàng cập nhật sau khi tăng hoặc giảm của một trong các phần tử của bộ dữ liệu đang được băm.

Ít nhất một cách để thực hiện việc băm này một cách hiệu quả, với đảm bảo độc lập lý thuyết tốt được thể hiện trong câu trả lời cho this question. Lưu ý rằng chi phí O (lg P) để tính toán hàm mũ để xác định số tiền thêm vào băm có thể được loại bỏ bằng cách precomputing các số mũ modulo nguyên tố trong với tổng thời gian chạy của O (P) cho precomputation, cho tổng số thời gian chạy của O (N + P) = O (N).