Khám phá các câu hỏi và câu trả lời từ cuộc phỏng vấn xin việc cho vị trí nhà phát triển Java. Phần 10

CHÀO! Mất bao nhiêu giờ để trở thành bậc thầy ở một lĩnh vực nào đó? Tôi thường nghe những câu như: “Để trở thành bậc thầy trong bất cứ việc gì, bạn cần dành 10.000 giờ cho nó”. Quả là một con số đáng sợ phải không? Tuy nhiên, tôi vẫn tự hỏi liệu điều đó có đúng không. Và tôi không ngừng cố gắng tính xem mình đã đầu tư bao nhiêu giờ để thành thạo nghệ thuật lập trình. Và khi tôi vượt qua ranh giới đặc biệt 10.000 giờ đó và trở thành bậc thầy, liệu tôi có cảm nhận được sự khác biệt không? Hay tôi đã vượt qua ranh giới đó từ lâu rồi mà không nhận ra? Dù thế nào đi nữa, bạn cũng không cần phải đầu tư nhiều thời gian như vậy để trở thành một lập trình viên. Điều quan trọng là sử dụng thời gian của bạn một cách khôn ngoan. Mục tiêu chính của bạn là có được một cuộc phỏng vấn. Và trong các cuộc phỏng vấn, những người muốn trở thành nhà phát triển phần mềm trước tiên sẽ được hỏi về lý thuyết, vì vậy đó cần phải là một thế mạnh. Trên thực tế, khi chuẩn bị cho một cuộc phỏng vấn, công việc của bạn là khám phá tất cả những lỗ hổng kiến ​​thức về lý thuyết Java cơ bản và sau đó lấp đầy chúng. Hôm nay tôi ở đây để giúp bạn làm điều đó, vì hôm nay chúng ta sẽ tiếp tục xem xét các câu hỏi phỏng vấn phổ biến nhất. Vâng, chúng ta hãy tiếp tục!

89. ArrayList khác với LinkedList như thế nào?

Đây là một trong những câu hỏi phổ biến nhất, cùng với câu hỏi về cấu trúc bên trong của HashMap . Không có cuộc phỏng vấn nào hoàn tất nếu không có nó, vì vậy câu trả lời của bạn sẽ dễ dàng khiến bạn thốt ra. Ngoài điều hiển nhiên (chúng có tên khác nhau), chúng còn khác nhau về cấu trúc bên trong. Trước đó, chúng ta đã thảo luận về cấu trúc bên trong của cả ArrayList và LinkedList , vì vậy tôi sẽ không đi sâu vào chi tiết triển khai của chúng. Tôi sẽ chỉ nhắc bạn rằng ArrayList được triển khai bằng cách sử dụng một mảng bên trong có kích thước tăng dần theo công thức sau:

<size of the current array> * 3 / 2 + 1

Ngoài ra, việc triển khai LinkedList sử dụng danh sách liên kết đôi nội bộ, nghĩa là mỗi phần tử có một tham chiếu đến các phần tử trước và phần tử tiếp theo, ngoại trừ các phần tử ở đầu và cuối danh sách. Người phỏng vấn thích hỏi những câu hỏi như thế này, "Cái nào tốt hơn, ArrayList hay LinkedList ?" hy vọng bắt được bạn. Suy cho cùng, nếu bạn nói cái này hay cái kia tốt hơn thì bạn đã trả lời sai. Thay vào đó, bạn nên làm rõ tình huống cụ thể mà bạn đang nói đến: truy cập các phần tử theo chỉ mục hoặc chèn vào giữa danh sách. Sau đó, tùy vào câu trả lời của họ, bạn có thể giải thích cái nào tốt hơn. Trước đây tôi đã mô tả cách hoạt động của ArrayList và LinkedList trong từng tình huống. Hãy tóm tắt điều này bằng cách xếp chúng thành một hàng để so sánh: Thêm một phần tử (thêm)

1. Nếu chỉ mục không được chỉ định thì một mục mới sẽ tự động được thêm vào cuối cho cả hai loại danh sách. Trong LinkedList , phần tử mới sẽ trở thành đuôi mới (chỉ một cặp tham chiếu sẽ được viết lại, do đó độ phức tạp của thuật toán là O(1) ).

   Phương thức add thêm một phần tử vào ô trống cuối cùng trong mảng ( O(1) ).

2. Thêm một mục theo chỉ mục thường có nghĩa là chèn nó vào đâu đó ở giữa danh sách. Trong LinkedList , trước tiên phương thức sẽ tìm kiếm vị trí mong muốn bằng cách lặp qua các phần tử từ đuôi và đầu ( O(n/2) ) và sau đó sẽ chèn giá trị bằng cách ghi đè tham chiếu của các phần tử ở cả hai phía của vị trí phần tử mới được chèn vào ( O(1) ). Độ phức tạp thuật toán tổng thể của thao tác này sẽ là O(n/2) .

   Trong tình huống tương tự (thêm theo chỉ mục), ArrayList tìm vị trí mong muốn ( O(1) ) và sau đó dịch chuyển tất cả các phần tử nằm ở bên phải (bao gồm cả phần tử đã được lưu trữ tại chỉ mục đã chỉ định) sang phải một (điều này có thể yêu cầu tạo một mảng nội bộ mới và sao chép các phần tử vào đó) ( O(n/2) ). Độ phức tạp tổng thể là O(n/2) .

3. Thêm một phần tử vào đầu LinkedList cũng tương tự như thêm một phần tử vào cuối: phần tử mới trở thành phần đầu mới ( O(1) ). Nhưng đối với ArrayList, thao tác đó yêu cầu di chuyển tất cả các phần tử sang phải ( O(n) ).

Điểm mấu chốt là đối với LinkedList, độ phức tạp của thuật toán sẽ nằm trong khoảng từ O(1) đến O(n/2) . Một quan sát khác là việc chèn càng gần cuối hoặc đầu danh sách thì tốc độ càng nhanh. Đối với ArrayList , độ phức tạp thuật toán nằm trong khoảng từ O(1) đến O(n) và việc chèn càng gần cuối danh sách thì tốc độ càng nhanh. Thiết lập một phần tử (bộ) Thao tác này ghi một phần tử vào vị trí được chỉ định trong danh sách, ghi đè bất kỳ phần tử hiện có nào. Trong LinkedList , thao tác này tương tự như việc thêm, vì thách thức lớn nhất ở đây là tìm vị trí của phần tử. Phần tử hiện có được ghi đè bằng cách cập nhật một cặp tham chiếu, do đó, một lần nữa chúng ta có độ phức tạp thuật toán thay đổi từ O(1) đến O(n/2) , tùy thuộc vào khoảng cách của vị trí mong muốn từ cuối hoặc đầu danh sách. Nhưng đối với ArrayList , thao tác này tìm ô mong muốn theo chỉ mục và ghi phần tử mới vào đó. Giống như thao tác tập hợp, tìm kiếm theo chỉ mục có độ phức tạp về mặt thuật toán là O(1) . Lấy một phần tử theo chỉ mục (get) Lấy một phần tử từ LinkedList tuân theo nguyên tắc tìm kiếm tương tự được sử dụng trong các hoạt động khác. Độ phức tạp phụ thuộc vào khoảng cách từ đầu hoặc cuối, tức là nó thay đổi từ O(1) đến O(n/2) . Như đã lưu ý trước đó, đối với ArrayList , việc tìm một phần tử theo chỉ mục trong mảng bên trong có độ phức tạp là O(1) . Xóa phần tử theo chỉ mục (xóa) Đối với LinkedList , nguyên tắc tương tự lại được áp dụng một lần nữa. Đầu tiên, phần tử được định vị, sau đó các tham chiếu được viết lại, các phần tử lân cận của phần tử đã xóa bây giờ tham chiếu lẫn nhau, loại bỏ các tham chiếu đến phần tử đã xóa, sau đó phần tử này sẽ được dọn sạch bởi trình thu gom rác. Nói cách khác, độ phức tạp thuật toán vẫn như cũ - nó thay đổi từ O(1) đến O(n/2) . Đối với ArrayList , thao tác này giống như thêm một phần tử mới (thêm). Đầu tiên, phương thức tìm phần tử mong muốn ( O(1) ), loại bỏ nó và sau đó tất cả các phần tử nằm ở bên phải được dịch chuyển một bước sang trái để thu hẹp khoảng cách được tạo bởi việc loại bỏ. Việc xóa một phần tử có độ phức tạp về thuật toán tương tự như thao tác thêm - từ O(1) đến O(n). Phần tử bị loại bỏ càng gần cuối danh sách thì độ phức tạp thuật toán của thao tác này càng thấp. Và bây giờ chúng tôi đã đề cập đến tất cả các hoạt động chính. Hãy để tôi nhắc bạn rằng khi so sánh hai loại danh sách này, bạn cần làm rõ tình huống cụ thể mà chúng được sử dụng. Chỉ khi đó bạn mới có thể trả lời một cách dứt khoát câu hỏi của người phỏng vấn.

90. ArrayList khác với HashSet như thế nào?

Nếu chúng ta có thể so sánh ArrayList và LinkedList trên cơ sở từng hoạt động để xác định cái nào tốt hơn, thì chúng ta sẽ không dễ dàng so sánh giữa ArrayList và HashSet vì chúng là các bộ sưu tập hoàn toàn khác nhau. Bạn có thể so sánh món tráng miệng này với món tráng miệng khác, nhưng so sánh món tráng miệng và món mặn là một thách thức - chúng hoàn toàn khác nhau. Tuy nhiên, tôi sẽ cố gắng chỉ ra một số khác biệt giữa chúng:

• ArrayList triển khai giao diện List trong khi HashSet triển khai giao diện Set .

• ArrayList cho phép bạn truy cập một phần tử theo chỉ mục: thao tác get có độ phức tạp thuật toán O(1) , nhưng HashSet chỉ cho phép bạn truy cập phần tử mong muốn bằng phép lặp, điều này mang lại độ phức tạp thuật toán từ O(1) đến O(n) .

• ArrayList cho phép các phần tử trùng lặp. Trong HashSet , tất cả các phần tử là duy nhất: mọi nỗ lực thêm phần tử đã có trong HashSet sẽ không thành công (các phần tử trùng lặp được kiểm tra bằng mã băm, do đó có tên của bộ sưu tập này).

• ArrayList được triển khai bằng mảng nội bộ, nhưng HashSet được triển khai bằng HashMap nội bộ .

• ArrayList duy trì thứ tự chèn của các phần tử, nhưng HashSet là tập hợp không có thứ tự và không duy trì thứ tự các phần tử.

• ArrayList cho phép bất kỳ số lượng giá trị null nào, nhưng bạn chỉ có thể thêm một giá trị null vào HashSet (xét cho cùng, các phần tử phải là duy nhất).

91. Tại sao Java có nhiều cách triển khai mảng động khác nhau như vậy?

Đây là một câu hỏi triết học nhiều hơn. Chúng ta cũng có thể hỏi tại sao họ lại nghĩ ra nhiều công nghệ mới và đa dạng như vậy? Cho thuận tiện. Và điều tương tự cũng đúng đối với một số lượng lớn việc triển khai mảng động. Không ai trong số họ có thể được gọi là cách triển khai tốt nhất hoặc lý tưởng. Mỗi cái đều có ưu điểm riêng cho từng tình huống cụ thể. Công việc của chúng tôi là biết sự khác biệt cũng như điểm mạnh/điểm yếu của họ để có thể sử dụng bộ sưu tập phù hợp nhất cho mọi tình huống nhất định.

92. Tại sao Java có nhiều triển khai lưu trữ khóa-giá trị khác nhau như vậy?

Ở đây tình huống cũng giống như việc triển khai mảng động. Chắc chắn không có cái nào tốt hơn những cái khác: mỗi cái đều có điểm mạnh và điểm yếu. Và tất nhiên chúng ta phải tận dụng tối đa điểm mạnh của họ. Ví dụ: gói đồng thời, có nhiều lớp đa luồng, có các bộ sưu tập Đồng thời riêng . Lớp ConcurrentHashMap có lợi thế hơn HashMap tiêu chuẩn về mặt an toàn khi làm việc với dữ liệu trong môi trường đa luồng, nhưng điều đó phải trả giá bằng hiệu năng chậm hơn. Và những triển khai không phải là lựa chọn tốt nhất trong mọi tình huống sẽ dần dần không còn được sử dụng. Ví dụ: Hashtable , ban đầu được dự định là HashMap an toàn theo luồng , đã bị lãng quên và không còn được sử dụng, vì ConcurrentHashMap thậm chí còn tốt hơn Hashtable khi làm việc trong môi trường đa luồng.

93. Làm cách nào để sắp xếp một tập hợp các phần tử?

Điều đầu tiên cần nói là lớp đại diện cho các phần tử của bộ sưu tập phải triển khai giao diện Comparable , bao gồm phương thức so sánh . Hoặc bạn cần một lớp triển khai giao diện Comparator , bao gồm cả phương thức so sánh của nó . Cả hai phương pháp đều chỉ ra cách so sánh các đối tượng cùng loại. Điều này rất quan trọng khi sắp xếp, vì thuật toán sắp xếp cần hiểu nguyên tắc nào sẽ sử dụng để so sánh các phần tử. Điều này chủ yếu được thực hiện bằng cách triển khai Comparable trực tiếp trong lớp mà bạn muốn sắp xếp. Sử dụng Comparator ít phổ biến hơn. Giả sử bạn đang sử dụng một lớp từ thư viện nào đó và nó không triển khai Comparable nhưng bạn cần sắp xếp một tập hợp các đối tượng của nó. Vì bạn không thể thay đổi mã của lớp này (ngoại trừ bằng cách mở rộng nó), nên bạn có thể viết một phần triển khai của Comparator để chỉ ra cách so sánh các đối tượng của lớp. Và một ví dụ nữa. Nếu bạn cần sắp xếp các đối tượng cùng loại theo những cách khác nhau thì bạn có thể viết nhiều triển khai Bộ so sánh để sử dụng trong các tình huống khác nhau. Theo quy định, nhiều lớp có sẵn, ví dụ: String , đã triển khai giao diện Comparable . Điều đó có nghĩa là bạn không cần phải lo lắng về cách so sánh các lớp này. Bạn chỉ có thể tiếp tục và sử dụng chúng. Cách đầu tiên và rõ ràng nhất là sử dụng lớp TreeSet hoặc TreeMap . Các lớp này lưu trữ các phần tử theo thứ tự được sắp xếp dựa trên bộ so sánh được các phần tử lớp thực hiện. Đừng quên rằng TreeMap sắp xếp các khóa chứ không phải giá trị. Nếu bạn sử dụng Comparator thay vì Comparable thì bạn cần chuyển một đối tượng Comparator cho hàm tạo của bộ sưu tập khi bạn tạo nó:

TreeSet treeSet = new TreeSet(customComparator);

Nhưng nếu bạn có một loại bộ sưu tập khác thì sao? Bạn sắp xếp nó như thế nào? Trong trường hợp này, cách thứ hai của lớp tiện ích Bộ sưu tập - phương thức sắp xếp() - là phù hợp. Phương thức này là tĩnh, vì vậy tất cả những gì bạn cần là thêm tên của lớp vào trước rồi chuyển vào danh sách cần sắp xếp. Ví dụ:

Collections.sort(someList);

Nếu bạn đang sử dụng cách triển khai Comparator thay vì Comparable thì bạn cần chuyển nó vào làm đối số thứ hai:

Collections.sort(someList, customComparator);

Thao tác này sẽ thay đổi thứ tự bên trong của các phần tử trong danh sách đã truyền: danh sách sẽ được sắp xếp bằng bộ so sánh. Lưu ý rằng danh sách được thông qua phải có thể thay đổi được, nếu không phương thức sẽ thất bại và ném ra ngoại lệ UnsupportedOperationException . Tùy chọn thứ ba là sử dụng phương thức được sắp xếp của lớp Stream để sắp xếp các phần tử của bộ sưu tập. Nếu chúng tôi đang sử dụng Comparable :

someList = someList.stream().sorted().collect(Collectors.toList());

Nếu chúng tôi đang sử dụng Comparator :

someList = someList.stream().sorted(customComparator).collect(Collectors.toList());

Cách thứ tư là triển khai thuật toán sắp xếp theo cách thủ công, ví dụ: sắp xếp bong bóng hoặc sắp xếp hợp nhất .

Lớp đối tượng. bằng() và hashCode()

94. Hãy mô tả ngắn gọn về lớp Object trong Java.

Trong phần thứ hai của bài đánh giá, chúng ta đã thảo luận về các phương thức của lớp Object . Ở đây tôi sẽ nhắc bạn rằng lớp Object là tổ tiên của mọi lớp trong Java. Nó có 11 phương thức được kế thừa bởi tất cả các lớp.

95. Equals() và hashCode() dùng để làm gì trong Java?

hashCode() là một phương thức của lớp Object được kế thừa bởi tất cả các lớp. Công việc của nó là tạo ra một số đại diện cho một đối tượng cụ thể. Bạn có thể tìm thấy một ví dụ về phương thức này đang hoạt động trong HashMap , trong đó nó được gọi trên các đối tượng chính để lấy mã băm cục bộ, mã này sẽ xác định nhóm nào (ô của mảng bên trong) mà cặp khóa-giá trị sẽ được lưu trữ. Ngoài ra, Phương thức này thường được sử dụng trong phương thức Equals() như một trong những cách chính để xác định đối tượng. Equals() là một phương thức của lớp Object có nhiệm vụ so sánh các đối tượng và xác định xem chúng có bằng nhau hay không. Phương thức này được sử dụng ở mọi nơi chúng ta cần so sánh các đối tượng, vì toán tử so sánh == tiêu chuẩn không phù hợp với các đối tượng, vì nó chỉ so sánh các tham chiếu đối tượng.

96. Hãy cho chúng tôi biết về hợp đồng giữa Equals() và hashCode() trong Java?

Đầu tiên, hãy để tôi nói rằng để các phương thức bằng() và hashCode() hoạt động chính xác, chúng phải được ghi đè chính xác. Việc triển khai mới của họ phải tuân theo các quy tắc sau:

• Các đối tượng giống hệt nhau trả về giá trị true phải có cùng mã băm.
• Các đối tượng có cùng mã băm không nhất thiết phải bằng nhau.

Bây giờ có vẻ là thời điểm thích hợp để tạm dừng cho đến phần tiếp theo của bài đánh giá!