Một thuật toán phỏng vấn thú vị của Google mà tôi tìm thấy trực tuyến yêu cầu thời gian tuyến tính

Question

Vì vậy, tôi đã tìm thấy câu hỏi về thuật toán phỏng vấn Google trực tuyến này. Nó thực sự thú vị và tôi vẫn chưa đưa ra một giải pháp tốt. Xin vui lòng có một cái nhìn, và cho tôi một gợi ý/giải pháp, nó sẽ là tuyệt vời nếu bạn có thể viết mã trong Java :).

"Thiết kế một thuật toán, được đưa ra danh sách gồm n phần tử trong một mảng, tìm tất cả các phần tử xuất hiện nhiều hơn n/3 lần trong danh sách Thuật toán sẽ chạy trong thời gian tuyến tính. (N> = 0) Bạn đang dự kiến ​​sẽ sử dụng sự so sánh và đạt được thời gian tuyến tính không băm/không gian quá mức/và không sử dụng tiêu chuẩn thời gian tuyến tính lựa chọn xác định algo"

Answer 1

Gợi ý:. Nhìn vào Boyer and Moore's Linear Time Voting Algorithm

Better Gợi ý: Hãy suy nghĩ về cách giải quyết phần lớn vấn đề đầu tiên. Đó là, cố gắng tìm một yếu tố xảy ra ít nhất n/2 lần. Ý tưởng cơ bản của thuật toán là nếu chúng ta hủy từng lần xuất hiện của một phần tử e với tất cả các phần tử khác khác với e thì e sẽ tồn tại cho đến khi kết thúc nếu nó là phần tử đa số.

findCandidate(a[], size) 
    //Initialize index and count of majority element 
    maj_index = 0; 
    count = 1; 

    for i = 1 to n–1 { 
     if a[maj_index] == a[i] 
      count++; 
     else 
      count--; 

     if count == 0 { 
      maj_index = i; 
      count = 1; 
     } 
    } 
    return a[maj_index] 

Thuật toán này lặp qua từng thành phần và duy trì số lượng a[maj_index]. Nếu phần tử tiếp theo giống nhau thì tăng số đếm, nếu phần tử tiếp theo không giống nhau thì giảm số đếm và nếu số đếm đến 0 thì thay đổi maj_index thành phần tử hiện tại và đặt thành số 1.

Tiếp theo bạn cần kiểm tra xem yếu tố này có thực sự xảy ra ít nhất n/2 lần, nhưng điều đó có thể được thực hiện trong một lần vượt qua hay không.

Answer 2

Giải pháp của tôi được lấy cảm hứng từ trò chơi Tetris. Làm nổi bật giải pháp (được gọi là 'quá trình bình minh'): sử dụng ba cặp khóa-giá trị để lưu giữ sổ sách, với khóa yếu tố, giá trị tổng của phần tử. Trong một vòng lặp chính, chúng tôi giữ tối đa 3 yếu tố riêng biệt mới nhất. Khi tổng số của cả ba khóa không khác, chúng tôi sẽ giảm số lượng của tất cả và loại bỏ (các) khóa không đếm, nếu có. Cuối cùng, có thể có hoặc không có một số yếu tố còn lại. Đây là những người sống sót trong quá trình Tetris. Lưu ý rằng không thể có nhiều hơn 3 phần tử còn lại. Nếu không có gì, chúng ta trả về null. Nếu không, chúng ta lặp qua các phần tử n ban đầu, đếm số lượng các phần tử còn lại này và trả về các phần tử có số đếm> n/3.

Gợi ý bằng chứng: Để hiển thị tính đúng đắn của thuật toán trên, lưu ý rằng đối với phần tử phải tồn tại trong quá trình Tetris hoặc vẫn còn trong phần dư để đáp ứng yêu cầu. Để xem lý do tại sao, hãy biểu thị số hoạt động loại bỏ dưới dạng m và tổng số phần tử còn lại r. Sau đó, chúng tôi có n = 3 * m + r. Từ đây chúng tôi nhận được m < = n/3, vì r> = 0. Nếu một phần tử không tồn tại trong quá trình Tetrise, sự xuất hiện tối đa có thể xuất hiện là m < = n/3.

Độ phức tạp về thời gian O (n), độ phức tạp của không gian O (1).