Phỏng vấn câu hỏi: thừa và bộ nhớ đệm

Question

Gần đây tôi đã đi qua các câu hỏi phỏng vấn sau đây:

Bạn cần phải thiết kế một hệ thống để cung cấp câu trả lời cho giai thừa cho từ 1 đến 100. Bạn có thể cache 10 số. Làm cách nào để bạn sắp xếp/quản lý bộ nhớ cache đó và trường hợp xấu nhất để tìm kiếm trên bộ nhớ cache là gì.

Bạn nghĩ gì sẽ là câu trả lời phù hợp và điều gì sẽ là lý do đằng sau điều này? Cá nhân, tôi sẽ lưu trữ mười số đầu tiên cho đầu vào đầu tiên, và sau đó duy trì bộ nhớ cache LRU dựa trên đầu vào gần đây nhất vì mọi người có nhiều khả năng lặp lại tìm kiếm. Không thực sự chắc chắn những gì các trường hợp xấu nhất cho tra cứu trên bộ nhớ cache bỏ lỡ sẽ được mặc dù. Có lẽ O (n) nếu bạn sử dụng một phương pháp lập trình động trong việc thực hiện chức năng giai thừa. Bạn nghĩ sao?

Answer 1

sau đó duy trì một bộ nhớ cache LRU dựa trên đầu vào gần đây nhất bởi vì mọi người có nhiều khả năng lặp lại tìm kiếm

Đó có thể là một sự lựa chọn thiết kế hợp lý, nhưng trong cuộc phỏng vấn tôi muốn cụm từ mà nhiều như một câu hỏi cho người phỏng vấn: "sẽ là hợp lý để giả định rằng các cuộc gọi sẽ giống như được thực hiện với các giá trị gần đây, hoặc có một số nhóm dự kiến ​​khác (số lượng lớn sẽ được yêu cầu thường xuyên hơn sau đó nhỏ hoặc ngược lại)?"

Ví dụ, nó có thể có ý nghĩa với bộ nhớ cache LRU, nhưng không bao giờ vứt bỏ các giá trị cho 10, 20, 30, 40, v.v. Đó là trường hợp xấu nhất để tính giai thừa khi bộ nhớ cache đầy với các giá trị đó phải thực hiện 10 phép nhân.

Một xem xét bạn có thể thực hiện là máy tính có thể dễ dàng đối phó với giai thừa nhất định:

• 12! là tệp lớn nhất có thể được giữ trong từ 32 bit.
• 20! là tệp lớn nhất có thể được giữ trong từ 64 bit.
• 34! là tệp lớn nhất có thể được giữ trong từ 128 bit.

Vì các máy ngày nay có thể dễ dàng xử lý số học 64 bit (thậm chí có thể là số học 128 bit), nên cũng không bao giờ nhớ giá trị cho 20! hoặc bên dưới khi bộ nhớ cache đầy các giá trị lớn hơn.

Trường hợp xấu nhất để tra cứu lỗi bộ nhớ cache sẽ phụ thuộc vào cách bạn lưu bộ nhớ cache. Có một mảng được sắp xếp theo đối số cho hàm không? (tra cứu là O (log n)) Đây có phải là mảng trong thứ tự LRU không?(tra cứu cache nhớ là O (n)). Tôi nghĩ bạn cũng muốn làm rõ rằng bạn muốn tìm kiếm bộ nhớ cache để luôn trả về giá trị cao nhất trong bộ nhớ cache nhỏ hơn những gì bạn đang tìm kiếm - giá trị bộ nhớ cache đó đại diện cho công việc mà bạn không phải làm cho tính toán giai thừa cụ thể này.

Answer 2

Ý tưởng ở đây là chọn một số số để có thể tính toán số khác từ chúng. Giả sử hệ thống của bạn thực hiện phép nhân với tốc độ không đổi và không có phân chia nào cả, bộ nhớ đệm (hoặc "tính toán trước") 1 !, 11 !, 21 !, 31 !, 41 !, 51 !, 61 !, 81 !, 91! cho phép tính toán tất cả các số còn lại với tối đa 9 phép nhân cho mỗi số.

Trong thực tế nhân số lớn hơn là tốn kém hơn, và bạn cũng có thể phân chia (ví dụ 90! = 91!/91), và bạn không thực sự cần 1 !, có thể dẫn đến phân phối tối ưu khác số.

Answer 3

Cách sử dụng 9 trong số các vùng bộ nhớ cache cho giai thừa 10, 20, 30, 40, 50, 60, 70, 80 và 90? Khe thứ 10 có thể là LRU. Tra cứu trường hợp xấu nhất sau đó là O (10) hoặc thời gian không đổi.

Answer 4

Ý tưởng của tôi giống như của ConnorDoyle, tôi sẽ lưu trữ tất cả các bội số của 10. Không biết loại cuộc gọi mà người dùng sẽ thực hiện điều này sẽ khiến bạn có trường hợp xấu nhất nhỏ nhất là 7 phép nhân/bộ phận bao gồm ban đầu hai để tìm những người và hàng chục chữ số, hoặc thời gian liên tục.

Một psuedo-thuật toán nhanh chóng ra khỏi đỉnh đầu của tôi:

total; 
mod = input%10; 
div = input/10; 
if(input%10 == 0) 
    output(cache[input/10]); 
else{ 
    if(mod < 5) { 
     total = cache[div]; 
     for(i = 1; i<=mod; i++) 
      total = total * (cache[div] + i); 
    } 
    else { 
     total = cache[div + 1]; 
     for(i = 9; i>mod; i--) 
      total = total/(cache[div] + i); 
    } 
    output(total); 
} 

Trường hợp xấu nhất sẽ là bất cứ điều gì với 5 trong những chữ số.