Mục lục[Ẩn giấu][Chỉ]
- 1. Bạn định nghĩa một Mảng như thế nào?
- 2. Mảng động: Chúng là gì? Điều gì làm chúng khác biệt với Mảng cơ bản?
- 3. Làm thế nào để một mảng và một từ điển khác nhau?
- 4. Nêu một số lợi ích và hạn chế của mảng.
- 5. “Mảng thưa thớt” ám chỉ điều gì?
- 6. Khi nào bạn chọn một danh sách liên kết trên một mảng?
- 7. Điều gì phân biệt một mảng được lập chỉ mục với một mảng kết hợp?
- 8. Heap có ưu điểm gì so với mảng đã sắp xếp?
- 9. Chúng ta có thể xác định kích thước của mảng là âm không?
- 10. Làm cách nào để xác định vị trí số nguyên bị thiếu trong mảng từ 1 đến 100 phần tử?
- 11. Làm thế nào để bạn tìm chỉ mục của một phần tử trong một mảng?
- 12. Làm thế nào bạn có thể loại bỏ một phần tử cụ thể khỏi một mảng?
- 13. Làm thế nào để xác minh tính bình đẳng của hai mảng?
- 14. Khi chúng ta thảo luận về mảng, bạn hiểu cụm từ “Thứ nguyên” và “Chỉ số phụ” có nghĩa là gì?
- Câu hỏi phỏng vấn mã hóa
- 15. Tìm kiếm một cặp trong một mảng có tổng được chỉ định
- 16. Sắp xếp mảng nhị phân với thời gian tuyến tính
- 17. Tìm tích hai int lớn nhất trong một mảng.
- 18. Cách chuyển tất cả các số không của mảng về cuối
- 19. Cách sắp xếp một mảng có hai mục được chuyển đổi trong một thao tác.
- 20. Cách kết hợp hai mảng đã sắp xếp tại chỗ.
- 21. Làm thế nào để sắp xếp lại một mảng các mục ở các vị trí cao và thấp xen kẽ?
- 22. Làm thế nào để thay thế từng phần tử của mảng mà không cần sử dụng toán tử chia bằng tích của từng phần tử trong mảng?
- 23. Tìm phần tử lẻ nhất trong một mảng theo thời gian logarit
- 24. Làm thế nào để lấy phần tử lớn hơn tiếp theo cho mỗi phần tử trong một mảng tròn?
- 25. Tìm số nghịch đảo của một mảng?
- 26. Vấn Đề Bẫy Nước Mưa Là Gì?
- Kết luận
Các cuộc phỏng vấn mã hóa chứa một loạt các câu hỏi DSA. Bạn nên có kỹ năng về mảng nếu bạn đã sẵn sàng cho cuộc phỏng vấn công nghệ sắp tới với FAANG hoặc một doanh nghiệp công nghệ Cấp 1 khác.
Trong hầu hết các cuộc phỏng vấn về mã hóa, nó đứng ở vị trí thứ hai sau Strings. Mảng là một nhóm các phần tử dữ liệu có liên quan được lưu giữ gần nhau trong bộ nhớ.
Vì chúng được kết nối với tất cả các ngôn ngữ lập trình, chẳng hạn như C, C ++, Java, Python, Perl và Ruby, chúng ở khắp mọi nơi. Tiếp tục đọc để biết một số thử thách viết mã thực hành và các câu hỏi phỏng vấn và câu trả lời dựa trên các mảng.
Python sẽ được sử dụng trong bài đăng này để giải quyết các vấn đề về mã hóa vì nó dễ sử dụng, dễ hiểu và phải quen thuộc với hầu hết chúng ta.
Hãy bắt đầu nào.
1. Bạn định nghĩa một Mảng như thế nào?
- Một nhóm các kiểu dữ liệu có liên quan là một mảng.
- Mảng luôn cố định.
- Cùng một loại biến được lưu trữ ở một số nơi bởi các đối tượng mảng.
- Các kiểu nguyên thủy và các tham chiếu đối tượng đều tương thích với nó.
2. Mảng động: Chúng là gì? Điều gì làm chúng khác biệt với Mảng cơ bản?
Việc chia tỷ lệ tự động mà mảng động (còn được gọi là mảng có thể phát triển, mảng có thể thay đổi kích thước, mảng có thể thay đổi hoặc ArrayLists trong Java) cung cấp là một lợi thế đáng kể.
Bạn phải luôn biết trước có bao nhiêu phần tử mà mảng của bạn sẽ lưu trữ vì mảng có kích thước cố định. Mặt khác, một mảng động sẽ phát triển khi bạn thêm các thành viên bổ sung vào nó, vì vậy bạn không cần biết trước kích thước chính xác của nó.
3. Làm thế nào để một mảng và một từ điển khác nhau?
Đây là một loạt các câu hỏi phỏng vấn dựa trên nguyên tắc cơ bản thường được hỏi. Sau đây là những điểm khác biệt chính giữa mảng và từ điển:
- Mảng là một danh sách có thứ tự các mục tương tự. Mặt khác, từ điển có các cặp khóa-giá trị.
- Kích thước mảng có thể thay đổi động. Những ý tưởng năng động như vậy không tồn tại trong từ điển.
- Trước khi sử dụng một mảng, kích thước của nó phải được chỉ định. Kích thước từ điển không cần phải được tùy chỉnh.
- Sử dụng câu lệnh Redim nếu bạn muốn mở rộng kích thước của mảng. Trong từ điển, một phần tử có thể được thêm vào mà không cần khai báo.
4. Nêu một số lợi ích và hạn chế của mảng.
Ưu điểm:
- Mảng có thể sắp xếp một số phần tử đồng thời.
- Nền tảng khác cấu trúc dữ liệu, chẳng hạn như ngăn xếp, hàng đợi, danh sách được liên kết, cây, đồ thị, v.v., có thể được triển khai trong một mảng.
- Một chỉ mục có thể được sử dụng để tiếp cận một phần tử của một mảng.
Nhược điểm:
- Kích thước của một mảng phải được khai báo trước. Tuy nhiên, tại thời điểm khai báo mảng, chúng ta có thể không lưu ý đến kích thước mà chúng ta yêu cầu.
- Cấu trúc của mảng là tĩnh. Nó ngụ ý rằng kích thước mảng luôn cố định và không thể tăng hoặc giảm cấp phát bộ nhớ.
5. “Mảng thưa thớt” ám chỉ điều gì?
Mảng thưa thớt là mảng dữ liệu có rất nhiều mục nhập có giá trị bằng không. Ngược lại, một mảng dày đặc chứa phần lớn các mục của nó có giá trị khác XNUMX. Các chỉ số của một mảng thưa thớt, chuyển đổi số thành các đối tượng, có thể bao gồm các khoảng trống. So với HashMap, chúng tiết kiệm bộ nhớ hơn.
6. Khi nào bạn chọn một danh sách liên kết trên một mảng?
Khi sử dụng danh sách được liên kết thay vì mảng, hãy xem xét:
- Bạn không cần bất kỳ yếu tố nào để có quyền truy cập ngẫu nhiên.
- Trong trường hợp khả năng dự đoán theo thời gian là cần thiết, bạn cần chèn và xóa liên tục khỏi danh sách.
- Để tạo hàng đợi ưu tiên, bạn có thể cần đặt các mục ở giữa danh sách.
- Bạn không biết danh sách sẽ dài bao lâu. Nếu kích thước mảng tăng lên, bạn phải khai báo lại và nhân bản bộ nhớ, giống như với các mảng đơn giản.
7. Điều gì phân biệt một mảng được lập chỉ mục với một mảng kết hợp?
Sự khác biệt chính giữa mảng kết hợp và mảng được lập chỉ mục được liệt kê trong bảng sau.
- Một cặp khóa-giá trị ở định dạng văn bản hoặc số được sử dụng để sắp xếp một mảng kết hợp. Các khóa của mảng được lập chỉ mục đều là số và mỗi khóa được kết nối với một giá trị riêng biệt.
- Trong một mảng kết hợp, khóa có thể là một chuỗi. Mảng được lập chỉ mục với các khóa số nguyên bắt đầu từ 0.
- Một bảng hai cột bắt chước hành vi của một mảng kết hợp. Tương tự như bảng một cột là các mảng được lập chỉ mục.
- Bản đồ là một kiểu mảng kết hợp. Một mảng chỉ mục không phải là một bản đồ.
8. Heap có ưu điểm gì so với mảng đã sắp xếp?
Hiệu quả về thời gian của việc sử dụng Heap trên Mảng đã sắp xếp là lợi ích chính. Trong khi các hoạt động đống nhanh hơn, việc sắp xếp một mảng đòi hỏi nhiều thời gian. Một đống có thể khám phá phần tử nhỏ nhất nhanh hơn đáng kể so với một mảng có thể được sắp xếp.
Một tập hợp các số nhất định có thể được sắp xếp theo một trong hai cách bằng cách sử dụng Mảng đã sắp xếp. Mặt khác, đối với một tập hợp các số nhất định, có thể có nhiều hơn một đống tiềm năng.
9. Chúng ta có thể xác định kích thước của mảng là âm không?
Không, chúng ta không thể xác định một số nguyên âm là kích thước của một mảng. Sẽ không có lỗi thời gian biên dịch nếu chúng tôi khai báo. Tuy nhiên, trong thời gian chạy, chúng ta sẽ gặp phải NegativeArraySizeException.
10. Làm cách nào để xác định vị trí số nguyên bị thiếu trong mảng từ 1 đến 100 phần tử?
Tổng của chuỗi có thể được tính bằng cách áp dụng hàm sau: n (n + 1) / 2
Chỉ khi mảng không có bất kỳ bản sao nào hoặc có nhiều hơn một số nguyên bị thiếu thì hàm này mới hoạt động. Cho dù một mảng có các phần tử trùng lặp, bạn có thể sắp xếp mảng để xem có bất kỳ phần tử nào tương đương hay không.
11. Làm thế nào để bạn tìm chỉ mục của một phần tử trong một mảng?
Chỉ mục của một phần tử có thể được phát hiện thông qua tìm kiếm tuyến tính hoặc nhị phân. Cho đến khi nó xác định vị trí khớp của phần tử được yêu cầu, một hàm tìm kiếm tuyến tính sẽ lặp lại từng phần tử trong một mảng. Nó trả về chỉ mục khi nó định vị phần tử phù hợp. Do đó, độ phức tạp theo thời gian của tìm kiếm tuyến tính là O. (n). Cả mảng được sắp xếp và không được sắp xếp đều có thể sử dụng tìm kiếm tuyến tính.
Sử dụng tìm kiếm nhị phân, liên tục chia mảng thành một nửa cho đến khi trung vị của khoảng phù hợp với phần tử được yêu cầu và cung cấp chỉ mục, bạn có thể lấy chỉ mục của phần tử nếu mảng được sắp xếp. Do đó, độ phức tạp theo thời gian của tìm kiếm nhị phân là O. (log n).
12. Làm thế nào bạn có thể loại bỏ một phần tử cụ thể khỏi một mảng?
Vì bạn không thể xóa các phần tử khỏi mảng ban đầu một cách đơn giản vì chúng là các tập hợp cố định với kích thước xác định, người phỏng vấn đang tìm cách để bạn đề xuất một cách tiếp cận khác và giải quyết vấn đề mà câu hỏi đặt ra. Cách tốt nhất của hành động là tạo một mảng mới để xóa một phần tử. Bạn có thể sao chép các phần tử từ mảng đầu tiên trong mảng này và chỉ bao gồm phần tử bạn muốn xóa.
Một chiến lược khác liên quan đến việc tìm phần tử mục tiêu trong mảng và sau đó đảo ngược thứ tự của tất cả các mục ở bên phải của phần tử mục tiêu.
13. Làm thế nào để xác minh tính bình đẳng của hai mảng?
Trước tiên, bạn phải xác minh độ dài của hai mảng được cung cấp. Các mục phù hợp của cả hai mảng được so sánh khi độ dài của chúng bằng nhau. Hai mảng sẽ được coi là bằng nhau. nếu mỗi cặp thành phần trong mọi thư từ là bằng nhau. Cách tiếp cận này không được khuyến khích để kiểm tra sự bằng nhau của hai mảng nếu các mảng có kích thước lớn vì nó sẽ mất rất nhiều thời gian. Bạn cũng có thể sử dụng phương thức equals () có trong lớp Mảng, tuy nhiên, nếu người phỏng vấn yêu cầu bạn so sánh hai mảng mà không sử dụng các phương thức có sẵn, thì cách này sẽ hữu ích.
14. Khi chúng ta thảo luận về mảng, bạn hiểu cụm từ “Thứ nguyên” và “Chỉ số phụ” có nghĩa là gì?
"Thứ nguyên" của một mảng là số chỉ số hoặc chỉ số con, được yêu cầu để xác định từng thành viên riêng lẻ. Chỉ số và thứ nguyên có thể không rõ ràng. Thứ nguyên là mô tả về phạm vi khóa được phép, trong khi chỉ số con là một số. Chỉ có một chỉ số con được yêu cầu cho mỗi kích thước mảng.
Ví dụ, mảng arr [10] [5] có hai thứ nguyên. Kích thước 10 trên một và 5 trên khác. Để giải quyết các thành phần của nó, bạn cần có hai chỉ số phụ. Cả hai đều nằm trong khoảng từ 0 đến 4; một từ 0 đến 9, bao gồm.
Câu hỏi phỏng vấn mã hóa
15. Tìm kiếm một cặp trong một mảng có tổng được chỉ định
Ví dụ,
Đầu vào:
- số = [8, 7, 2, 5, 3, 1]
- mục tiêu = 10
Đầu ra:
- Đã tìm thấy cặp (8, 2)
- Or
- Đã tìm thấy cặp (7, 3)
Đầu vào:
- số = [5, 2, 6, 8, 1, 9]
- mục tiêu = 12
Đầu ra:
- Không tìm thấy cặp
16. Sắp xếp mảng nhị phân với thời gian tuyến tính
Sắp xếp một mảng nhị phân theo thời gian tuyến tính và trong một khu vực cố định. Đầu ra phải hiển thị tất cả các số không trước, sau đó là tất cả các số.
Ví dụ,
- Đầu vào: {1, 0, 1, 0, 1, 0, 0, 1}
- Đầu ra: {0, 0, 0, 0, 1, 1, 1, 1}
Một cách tiếp cận đơn giản sẽ là tính toán tổng số 0 của mảng, chẳng hạn như k, và sau đó điền k chỉ số đầu tiên trong mảng bằng 0 và các chỉ số còn lại bằng 1. Để thay thế, chúng ta có thể tính tổng số 1 trong mảng mảng k, điền k chỉ số cuối cùng trong mảng bằng 1 và để phần còn lại của chỉ số được điền bằng 0.
Phương pháp đã cho có độ phức tạp về thời gian là O (n) và không sử dụng thêm dung lượng lưu trữ, trong đó n là kích thước của đầu vào.
17. Tìm tích hai int lớn nhất trong một mảng.
Tìm tích lớn nhất của hai số trong một mảng số nguyên.
Hãy nghĩ về mảng 10 3 5 6 2 như một ví dụ. Cặp (-10, -3) hoặc (5, 6) là sản phẩm cao nhất.
Để suy nghĩ về mọi sự kết hợp yếu tố và tìm ra sản phẩm của họ là một cách tiếp cận ngu ngốc. Nếu sản phẩm của cặp hiện tại lớn hơn sản phẩm tối đa thu được cho đến nay, hãy cập nhật sản phẩm tối đa. In các thành phần của sản phẩm cuối cùng.
Giải pháp trên, với n là số lượng đầu vào, có độ phức tạp về thời gian là O (n2) và không chiếm thêm dung lượng.
18. Cách chuyển tất cả các số không của mảng về cuối
Di chuyển tất cả các số không trong một mảng số nguyên đến cuối. Câu trả lời nên tránh sử dụng không gian không đổi và bảo toàn thứ tự tương đối của các thành phần của mảng.
Đầu vào: {1,2,3,0,8,0,4,7}
Đầu ra sẽ là {1,2,3,8,4,7,0,0}
Đặt phần tử ở vị trí có sẵn sau đây trong mảng nếu phần tử hiện tại không phải là số không. Điền vào tất cả các chỉ số còn lại bằng 0 khi tất cả các mục của mảng đã được xử lý.
Giải pháp trước có độ phức tạp thời gian O (n), trong đó n là kích thước của đầu vào.
19. Cách sắp xếp một mảng có hai mục được chuyển đổi trong một thao tác.
Sắp xếp một mảng theo thời gian tuyến tính cho trước hai mục được hoán đổi và một mảng có tất cả các phần tử của nó được sắp xếp theo thứ tự tăng dần. Giả sử rằng mảng không chứa bản sao.
Đầu vào: = [1,9,3,4,7,2] hoặc [9,3,7,2,1,4] hoặc [2,4,1,7,3,9]
Đầu ra: = [1,2,3,4,7,9]
Bắt đầu với phần tử thứ hai trong mảng, mục tiêu là so sánh từng phần tử với phần tử trước của nó. Vị trí của tranh chấp được lưu trữ bằng cách lấy hai con trỏ, x và y.
Cập nhật x vào chỉ mục của phần tử trước đó và y vào chỉ mục của phần tử hiện tại nếu cái trước lớn hơn cái sau. Cập nhật y vào chỉ mục của phần tử hiện tại nếu nó cho thấy rằng phần tử trước đó lớn hơn phần tử hiện tại.
Cuối cùng, chuyển đổi các phần tử tại các chỉ mục x và y khi chúng ta đã xử lý xong từng cặp phần tử liền kề.
Do phương pháp nói trên chỉ thực hiện một lần quét duy nhất mảng đầu vào có kích thước n nên độ phức tạp về thời gian của nó là O (n). Không cần thêm chỗ cho giải pháp.
20. Cách kết hợp hai mảng đã sắp xếp tại chỗ.
Hợp nhất các mục của mảng X [] và Y [] - hai mảng được sắp xếp có kích thước m và n mỗi mảng — bằng cách giữ lại thứ tự đã sắp xếp, nghĩa là, bằng cách điền vào X [] với m phần tử nhỏ nhất đầu tiên và điền vào Y [] với các yếu tố còn lại.
Nếu một phần tử trong mảng X [] đã ở đúng vị trí (tức là phần tử nhỏ nhất trong số các phần tử còn lại), hãy bỏ qua nó; nếu không, hãy thay thế nó bằng phần tử nhỏ nhất, cũng là phần tử đầu tiên của Y []. Để giữ lại thứ tự đã sắp xếp sau khi hoán đổi, hãy chuyển phần tử (bây giờ là Y [0]) đến vị trí thích hợp của nó trong Y [].
Kích thước của mảng đầu tiên là m và kích thước của mảng thứ hai là n, và độ phức tạp về thời gian là O (mn).
21. Làm thế nào để sắp xếp lại một mảng các mục ở các vị trí cao và thấp xen kẽ?
Sắp xếp lại một mảng số nguyên để mỗi phần tử tiếp theo lớn hơn các phần tử trước và sau. Giả sử mảng không bao gồm bất kỳ phần tử trùng lặp nào.
Sắp xếp mảng hoặc sử dụng thêm không gian là không cần thiết để có một cách tiếp cận hiệu quả. Đầu tiên, kế hoạch là thành viên thứ hai của mảng và tăng lên hai cho mỗi lần lặp vòng lặp.
Hoán đổi các thành phần nếu phần tử cuối cùng vượt quá phần tử đầu tiên. Theo cách tương tự, hãy chuyển đổi cả hai mục nếu phần tử sau lớn hơn phần tử hiện tại. Chúng ta sẽ có được mảng mong muốn tuân thủ các hạn chế đã chỉ định khi kết thúc vòng lặp.
22. Làm thế nào để thay thế từng phần tử của mảng mà không cần sử dụng toán tử chia bằng tích của từng phần tử trong mảng?
Không sử dụng toán tử chia, hãy thay thế mỗi phần tử trong một mảng số nguyên bằng tích của tất cả các phần tử khác.
Trong thời gian tuyến tính và không gian không đổi, chúng ta có thể sử dụng đệ quy để giải quyết vấn đề này. Tính toán đệ quy các sản phẩm của từng phần tử trong mảng con bên phải và chuyển sản phẩm của mảng con bên trái dưới dạng các tham số hàm là khái niệm.
Độ phức tạp về thời gian là O (n).
23. Tìm phần tử lẻ nhất trong một mảng theo thời gian logarit
Cho một mảng số nguyên trong đó tất cả trừ một phần tử có số lần xuất hiện chẵn, vấn đề là xác định xem một phần tử này xuất hiện bao nhiêu lần. Tìm phần tử xuất hiện lẻ theo thời gian logarit và không gian hằng số nếu các phần tử giống nhau xuất hiện thành từng cặp trong mảng và không bao giờ có thể có nhiều hơn hai trường hợp của một phần tử đã cho trong một hàng.
Hoạt động XOR cho phép chúng tôi giải quyết vấn đề này trong thời gian tuyến tính. Mục tiêu là XOR mọi phần tử trong mảng. Chỉ các phần tử xuất hiện lẻ còn lại sau khi các phần tử chẵn triệt tiêu lẫn nhau.
Vấn đề này thậm chí có thể được giải quyết trong thời gian O (log (n)).
24. Làm thế nào để lấy phần tử lớn hơn tiếp theo cho mỗi phần tử trong một mảng tròn?
Phần tử lớn hơn tiếp theo cho mỗi phần tử trong mảng số nguyên tròn sẽ được đặt. Số nguyên lớn hơn đầu tiên sau một phần tử x trong mảng là phần tử lớn hơn tiếp theo của phần tử đó.
Từ phải sang trái, chúng ta có thể thao tác trên các mục mảng. Mục đích là lặp lại cho mỗi phần tử x cho đến khi ngăn xếp trống hoặc chúng ta có phần tử cao hơn ở trên nó. Đặt phần tử lớn hơn tiếp theo của x xuất hiện trên đầu ngăn xếp khi nó xuất hiện.
25. Tìm số nghịch đảo của một mảng?
Tìm tổng số nghịch đảo của một mảng. Cặp I j) được coi là sự nghịch đảo của mảng A nếu I j) và (A [i]> A [j]). Chúng ta phải đếm từng cặp trong số này trong mảng.
Đếm tất cả các thành viên mảng ít hơn nó ở bên phải của nó và thêm kết quả vào đầu ra là một cách tiếp cận đơn giản.
Giải pháp này có độ phức tạp O (n2), trong đó n là kích thước của đầu vào.
26. Vấn Đề Bẫy Nước Mưa Là Gì?
Tìm lượng nước nhiều nhất có thể bị giữ lại trong một tập hợp các thanh nhất định với chiều rộng mỗi thanh là một đơn vị được gọi là vấn đề "bẫy lượng mưa".
Mục đích là để xác định thanh cao nhất có thể được đặt ở bên trái và bên phải của mỗi thanh. Mức tối thiểu của các thanh dẫn ở bên trái và bên phải, trừ đi chiều cao của thanh hiện tại, là lượng nước được chứa trên mỗi thanh.
Kết luận
So với các chủ đề cấu trúc dữ liệu khác, mảng đơn giản hơn. Để hoàn thành tốt các câu hỏi phỏng vấn mảng, bạn cần có hiểu biết cơ bản về mảng.
Bạn nên xem lại toàn bộ nền tảng của mảng, bao gồm các phép toán mảng (từ khai báo / tạo mảng đến truy cập / sửa đổi các mục của mảng), cũng như các khái niệm lập trình như vòng lặp, đệ quy và các toán tử cơ bản để trả lời thành công các câu hỏi phỏng vấn mảng. Nhận ra vấn đề một cách hoàn chỉnh.
Bạn nên tìm hiểu rõ nếu bạn có bất kỳ thắc mắc nào. Hãy suy nghĩ về việc chia vấn đề thành các phần dễ quản lý hơn. Đảm bảo rằng bạn đã nghĩ đến thuật toán trước khi bắt đầu lập trình; viết nó ra hoặc hình dung nó trong một sơ đồ. sau đó bắt đầu viết mã.
Bình luận