Trung tâm cá nhân
cuốn sách gpt4 ai đã làm

thuật toán - Phỏng vấn kỹ thuật của Microsoft: Thuật toán ma trận

In lại Tác giả: Taklimakan Thời gian cập nhật: 2023-11-03 05:29:10 27 4
mua khóa gpt4 Nike

Gần đây tôi đã có một cuộc phỏng vấn trong đó người phỏng vấn đưa cho tôi một số mã giả và đặt câu hỏi về nó. Thật không may, do thiếu chuẩn bị nên tôi không thể trả lời câu hỏi của anh ấy. Do thời gian có hạn nên tôi không thể hỏi anh ấy cách giải quyết vấn đề này. Tôi sẽ rất biết ơn nếu ai đó có thể hướng dẫn tôi và giúp tôi hiểu vấn đề để tôi có thể cải thiện trong tương lai. Đây là mã giả:

Một trạng thái mẫu của 'a': 
[[ 2, KHÔNG, 2, KHÔNG], 
 [2, KHÔNG, 2, KHÔNG], 
 [NULL, KHÔNG, KHÔNG, KHÔNG], 
 [NULL, KHÔNG, KHÔNG, KHÔNG]]

CHỨC NĂNG foo()
  CHO y = 0 đến 3 
    CHO x = 0 đến 3
      NẾU a[x+1][y] != NULL
        NẾU a[x+1][y] = a[x][y]:
          a[x][y] := a[x][y]*2
          a[x+1][y] := NULL
        KẾT THÚC NẾU
        NẾU a[x][y] = NULL
          a[x][y] := a[x+1][y]
          a[x+1][y] := NULL
        KẾT THÚC NẾU
      KẾT THÚC NẾU
    KẾT THÚC CHO
  KẾT THÚC CHO
CHỨC NĂNG KẾT THÚC

Người phỏng vấn hỏi tôi:

  1. Đoạn mã trên có vấn đề gì và làm cách nào để khắc phục?

  2. Sau khi sửa xong, hàm foo làm gì? Tập trung vào kết quả của chức năng chứ không phải chi tiết thực hiện.

  3. Làm thế nào để làm cho foo tổng quát hơn? Giải thích tối đa ba hướng khái quát hóa có thể và mô tả các chiến lược cho từng hướng mà không cần viết mã!

Tôi đã đề cập với anh ấy:

  • Trạng thái của ma trận có vẻ không chính xác vì ma trận số nguyên không thể có giá trị null. Theo mặc định, chúng được gán là 0, giá trị bool được gán là SAI, kiểu tham chiếu được gán là null.
  • Một vấn đề khác với đoạn mã trên làNẾU a[x+1][y] != NULL,khix, điều kiện này sẽ tạo ra lỗi chỉ mục mảng vượt quá giới hạn 等于 3.

Nhưng tôi có cảm giác như người phỏng vấn đang tìm kiếm điều gì đó khác trong câu trả lời của tôi và không hài lòng với lời giải thích.

câu trả lời hay nhất

Bạn đã chơi trò chơi "2048" chưa (liên kết đến trò chơi)? Nếu không, câu hỏi này có thể không có nhiều ý nghĩa trực quan đối với bạn và do đó, tôi nghĩ đó là một câu hỏi phỏng vấn tồi.

Những gì nó cố gắng làm là mô phỏng một bước tiến lên trong trò chơi năm 2048. Các số sẽ di chuyển lên một ô trừ khi chúng chạm vào một số khác hoặc ranh giới ma trận (hãy nghĩ rằng trọng lực kéo tất cả các số lên trên). Nếu hai số bằng nhau thì chúng được kết hợp và tạo ra một số mới (tổng của chúng).

LƯU Ý: Đây không hẳn là một bước trong trò chơi 2048, vì các con số chỉ di chuyển lên một ô, trong khi trong trò chơi, chúng di chuyển "luôn luôn" cho đến khi chạm vào thứ khác. Để có được một bước trong trò chơi 2048, bạn cần lặp lại chức năng đã cho cho đến khi không có gì thay đổi nữa.

Như bạn đã nêu, vấn đề trong mã của bạn là chỉ mục mảng nằm ngoài giới hạn. Nó nên được đi qua bởi x = 0 đến 2 để sửa chữa.

Để làm cho nó linh hoạt hơn, bạn phải sáng tạo:

  1. Điểm khái quát chính là nó phải có tham số "hướng". (Một lần nữa, nếu bạn chưa chơi trò chơi 2048 thì bạn sẽ không biết điều này.) Thay vì kéo các con số lên trên, lực hấp dẫn có thể kéo các con số theo bất kỳ hướng nào trong 4 hướng chính.
  2. Có lẽ thuật toán không nên kiểm tra NULL Nhưng một số giá trị thẻ khác cần được kiểm tra (là một đầu vào khác).
  3. Cũng dễ dàng khái quát hóa điều này cho các ma trận lớn hơn.
  4. Có lẽ nên có một số quy tắc khác về thời điểm các số kết hợp và cách chúng kết hợp chính xác (không nhất thiết phải gấp đôi số đầu tiên). Những quy tắc này có thể được đưa ra dưới dạng lambdas.

Đáp án phần này:

ma trận số nguyên không thể có giá trị null, theo mặc định chúng được gán 0, false cho Boolean và null cho loại tham chiếu

Điều này phụ thuộc rất nhiều vào ngôn ngữ được sử dụng, vì vậy tôi sẽ không nói đó là lỗi trong mã giả (không nên sử dụng nó trong bất kỳ ngôn ngữ cụ thể nào). Ví dụ, trong một ngôn ngữ được gõ yếu tất nhiên bạn có thể có một hàm chứa int Và NULL ma trận các giá trị.

Bạn đã không đề cập đến những gì bạn nói về hoạt động của chức năng. Nếu tôi là người phỏng vấn, tôi muốn thấy ai đó “suy nghĩ rõ ràng” và nhận ra ít nhất những điều sau:

  • Mã cố gắng so sánh từng phần tử với phần tử bên dưới nó.
  • Trừ khi phần tử cơ bản là NULL, nếu không sẽ không có chuyện gì xảy ra.
  • Nếu hai phần tử bằng nhau thì thay phần tử thấp hơn bằng NULLvà các phần tử cao hơn sẽ lớn gấp đôi.
  • Nếu phần tử trên cùng là NULL, thì giá trị thấp hơn không NULL Phần tử "di chuyển" đến vị trí của phần tử trên cùng.

Những quan sát về mã này có thể được thực hiện trực tiếp bằng cách đọc mã nguồn. Việc bạn có hiểu "quy tắc" và nhận thấy rằng nó (tương tự) trò chơi năm 2048 hay không phụ thuộc phần lớn vào việc bạn đã chơi trò chơi đó trước đây hay chưa.

Về thuật toán - Phỏng vấn kỹ thuật của Microsoft: Thuật toán ma trận, chúng tôi đã tìm thấy một câu hỏi tương tự trên Stack Overflow: https://stackoverflow.com/questions/50338479/

27 4 0
Bài viết khuyến nghị: ruby - Thuật toán đệ quy: Cách thực hiện đệ quy mà không lưu trữ trạng thái
Bài viết khuyến nghị: XPathFactory không hoạt động
Bài viết khuyến nghị: Có tham chiếu phương thức nào có thể được sử dụng để đưa ra ngoại lệ không?
Bài viết khuyến nghị: Kiểm tra xem danh sách có phải là danh sách con của danh sách khác mà không kiểm tra sự bằng nhau giữa các phần tử không
Taklimakan
Hồ sơ

Tôi là một lập trình viên xuất sắc, rất giỏi!

Nhận phiếu giảm giá taxi Didi miễn phí
Phiếu giảm giá taxi Didi
Các bài viết phổ biến trên toàn bộ trang web
Chứng chỉ ICP Bắc Kinh số 000000
Hợp tác quảng cáo: 1813099741@qq.com 6ren.com
Xem sitemap của VNExpress