Họ có thể hỏi gì khi phỏng vấn: Cấu trúc dữ liệu trong Java. Phần 1

Xin chào! Cho dù bạn nhìn nó như thế nào, bạn không thể trở thành nhà phát triển nếu không vượt qua thành công cuộc phỏng vấn đầu vào kỹ thuật. Có rất nhiều công nghệ liên quan đến Java và không thể học hết mọi thứ. Theo quy định, một điều gì đó cụ thể chỉ được hỏi trong các cuộc phỏng vấn nếu họ đang tìm kiếm một nhà phát triển có kinh nghiệm tốt trong một số framework quan trọng đối với dự án. Nếu đúng như vậy, bạn sẽ bị truy đuổi hết tốc lực quanh khuôn khổ này, bạn không nghi ngờ gì về điều đó. Nhưng bây giờ chúng ta đang nói về nền tảng mà mọi nhà phát triển Java nên biết. Về kiến ​​thức cổ điển mà từ đó mọi chuyện bắt đầu. Hôm nay tôi muốn đề cập đến một trong những chủ đề cơ bản của bất kỳ cuộc phỏng vấn nào - cấu trúc dữ liệu trong Java . Vì vậy, thay vì quanh co, hãy bắt đầu. Tìm danh sách các câu hỏi mà bạn có thể được hỏi về chủ đề này trong một cuộc phỏng vấn.

1. Giới thiệu một chút về cấu trúc dữ liệu

Cấu trúc dữ liệu là một kho lưu trữ dữ liệu chứa thông tin được cấu trúc theo một cách nhất định. Những cấu trúc này được thiết kế để thực hiện hiệu quả một số hoạt động nhất định. Ví dụ điển hình về cấu trúc dữ liệu là:

• mảng,
• ngăn xếp,
• hàng đợi,
• danh sách liên quan,
• đồ thị,
• cây,
• cây tiền tố,
• bảng băm.

Bạn có thể tìm hiểu thêm về họ ở đây và ở đây . Dữ liệu là thành phần chính trong một chương trình và các cấu trúc cho phép dữ liệu này được lưu trữ ở dạng cụ thể, có cấu trúc rõ ràng. Dù ứng dụng của bạn làm gì thì khía cạnh này sẽ luôn hiện diện trong đó: nếu là cửa hàng trực tuyến thì thông tin về sản phẩm sẽ được lưu trữ, nếu đó là mạng xã hội, dữ liệu về người dùng và tệp, v.v.

2. Bạn biết gì về Mảng?

Mảng là nơi chứa các giá trị cùng loại, số lượng đã được chỉ định trước. Một ví dụ về tạo một mảng với các giá trị chuỗi:

String[] strArray = {"Java","is","the","best","language"};

Khi tạo một mảng, bộ nhớ được phân bổ cho tất cả các phần tử của nó: càng có nhiều ô cho các phần tử được chỉ định ban đầu thì càng có nhiều bộ nhớ được phân bổ. Nếu một mảng trống có số lượng ô nhất định được tạo thì tất cả các phần tử của mảng sẽ được gán giá trị mặc định. Ví dụ:

int[] arr = new int[10];

Vì vậy, đối với một mảng có các phần tử thuộc kiểu boolean , các giá trị ban đầu ( mặc định ) sẽ là false , đối với các mảng có giá trị số - 0, với các phần tử thuộc kiểu char - \u0000 . Đối với một mảng thuộc loại lớp (đối tượng) - null (không phải chuỗi trống - “” mà cụ thể là null ). Tức là trong ví dụ trên, tất cả các giá trị của mảng arr sẽ bằng 0 cho đến khi chúng được chỉ định trực tiếp. Không giống như bộ sưu tập, mảng không động. Khi một mảng có kích thước nhất định được khai báo, kích thước đó không thể thay đổi được. Để thêm một phần tử mới vào một mảng, bạn cần tạo một mảng mới lớn hơn và sao chép tất cả các phần tử từ mảng cũ vào đó (đây là cách ArrayList hoạt động). Có một điểm mà không phải ai cũng biết và bạn có thể nắm bắt khá rõ. Có hai loại biến trong Java - loại đơn giản và tham chiếu đến các đối tượng chính thức. Cái nào trong số này là mảng? Ví dụ: ở đây:

int[] arr = new int[10];

Có vẻ như mọi thứ đều đơn giản - đây là 10 phần tử int . Vậy có thể nói đây là loại đơn giản? Cho dù nó thế nào đi chăng nữa. Trong Java, mảng là các đối tượng, được tạo động và có thể được gán cho các biến kiểu Object. Tất cả các phương thức của lớp Object đều có thể được gọi trên một mảng. Vì vậy chúng ta thậm chí có thể viết:

Object arr = new int[]{7,5,4,3};
System.out.println(arr.toString());

Khi xuất ra bảng điều khiển, bạn có thể nhận được một cái gì đó như: Đọc thêm về các tính năng của mảng trong Java trong bài viết này về Java Array . Để củng cố kiến ​​thức của mình, bạn có thể giải một số bài toán từ bộ sưu tập này .

3. Giải thích thứ bậc của các bộ sưu tập

Bộ sưu tập được sử dụng trong trường hợp bạn cần sự linh hoạt khi làm việc với dữ liệu. Bộ sưu tập có thể thêm một phần tử, xóa một phần tử và thực hiện nhiều thao tác khác. Có nhiều cách triển khai khác nhau trong Java và chúng ta chỉ cần chọn bộ sưu tập phù hợp với tình huống hiện tại. Thông thường, khi bạn đề cập đến giao diện Bộ sưu tập , bạn sẽ được yêu cầu liệt kê một số cách triển khai và mối quan hệ của nó với Map . Vâng, chúng ta hãy tìm hiểu. Vì vậy, Bộ sưu tập và Bản đồ là hai hệ thống phân cấp khác nhau cho cấu trúc dữ liệu. Hệ thống phân cấp Bộ sưu tập trông như thế nào : Giao diện Bộ sưu tập là liên kết chính trên cùng với danh sách các phương thức cơ bản, từ đó bắt nguồn ba loại cấu trúc dữ liệu cơ bản - Set , List , Queue . Set<T> là giao diện đại diện cho một tập hợp các đối tượng trong đó mỗi đối tượng là duy nhất. List<T> là một giao diện đại diện cho một chuỗi các đối tượng có thứ tự được gọi là danh sách. Queue<T> là giao diện chịu trách nhiệm về các cấu trúc được tổ chức dưới dạng hàng đợi (lưu trữ tuần tự các phần tử). Như đã đề cập trước đó, Map là một hệ thống phân cấp riêng biệt: Map<K, V> là một giao diện đại diện cho một từ điển trong đó các phần tử được chứa dưới dạng cặp khóa-giá trị. Hơn nữa, tất cả các khóa (K) là duy nhất trong đối tượng Map . Kiểu bộ sưu tập này giúp tìm kiếm một phần tử dễ dàng hơn nếu chúng ta biết khóa - mã định danh duy nhất của đối tượng.

4. Bạn biết gì về Set?

Như đã nêu trước đó, bộ sưu tập này có nhiều yếu tố độc đáo. Nói cách khác, cùng một đối tượng không thể xuất hiện nhiều lần trong Bộ Java. Tôi cũng muốn chỉ ra rằng chúng ta không thể trích xuất một phần tử từ Tập hợp theo số (chỉ mục) - chỉ bằng vũ lực. Điều quan trọng là việc triển khai Set khác nhau có các cách cấu trúc dữ liệu khác nhau. Chúng tôi sẽ xem xét việc triển khai cụ thể hơn nữa. Vì vậy, cách triển khai chính của Set : HashSet là một tập hợp dựa trên bảng băm, từ đó giúp ích cho việc tìm kiếm. Sử dụng hàm băm giúp cải thiện hiệu suất trong quá trình tra cứu và chèn. Bất kể số lượng phần tử, việc chèn và tìm kiếm (đôi khi xóa) thường được thực hiện trong khoảng thời gian gần như không đổi - O(1). Chúng ta sẽ xem xét hàm băm chi tiết hơn sau. Tôi cũng muốn lưu ý rằng HashSet chứa HashMap , đây là nơi tất cả những điều kỳ diệu xảy ra. Đây là bài viết chi tiết về HashSet trong Java . LinkedHashSet - lớp này mở rộng HashSet mà không thêm bất kỳ phương thức mới nào. Giống như LinkedList , lớp này duy trì một danh sách liên kết các phần tử của một tập hợp theo thứ tự chúng được chèn vào. Điều này cho phép bạn sắp xếp thứ tự cần thiết trong quá trình triển khai Set nhất định . Lớp TreeSet tạo một tập hợp dựa trên cây đỏ đen để tổ chức cấu trúc lưu trữ các phần tử. Nói cách khác, trong một tập hợp nhất định, chúng ta có thể sắp xếp các phần tử theo thứ tự tăng dần. Nếu chúng ta sử dụng một số đối tượng tiêu chuẩn từ “hộp”, ví dụ: Integer , thì chúng ta không cần phải làm gì để sắp xếp tập hợp các Số nguyên theo thứ tự tăng dần:

TreeSet set = new TreeSet<>();
set.add(4);
set.add(2);
set.add(3);
set.add(1);

System.out.println(set);

Và trong bảng điều khiển, chúng ta sẽ nhận được kết quả: Nghĩa là, trong tập hợp này , các số được lưu trữ ở dạng được sắp xếp. Nếu chúng ta sử dụng các phần tử String trong TreeSet , chúng sẽ được sắp xếp nhưng theo thứ tự bảng chữ cái. Chà, nếu chúng ta có một số lớp tiêu chuẩn (tùy chỉnh) thì sao? Các đối tượng của lớp này sẽ cấu trúc TreeSet như thế nào ? Nếu chúng ta cố gắng gán một đối tượng tùy ý cho Set này :

TreeSet set = new TreeSet<>();
set.add(new Cat(4, "Murzik"));
set.add(new Cat(2, "Barsik"));
set.add(new Cat(3, "Гарфилд"));

System.out.println(set);

Chúng ta sẽ nhận được ClassCastException vì TreeSet không biết cách sắp xếp các đối tượng thuộc loại này. Trong trường hợp này, chúng ta cần đối tượng tùy chỉnh của mình để triển khai giao diện Comparable và phương thức so sánh của nó :

public class Cat implements Comparable {
    int age;
    String name;

   public Cat(int age, String name) {
       this.age = age;
       this.name = name;
   }

   @Override
   public int compareTo(Cat cat) {
       return age > cat.age ? 1 : -1;
   }

   @Override
   public String toString() {
       return "Cat{" +
               "age=" + age +
               ", name='" + name + '\'' +
               '}';
   }
}

Như bạn đã nhận thấy, phương thức so sánh trả về int :

• 1 nếu đối tượng hiện tại (này) được coi là lớn;
• -1 nếu đối tượng hiện tại được coi là nhỏ hơn đối tượng được đưa ra dưới dạng đối số;
• 0 nếu các đối tượng bằng nhau (chúng tôi không sử dụng giá trị này trong trường hợp này).

Trong trường hợp này, TreeSet của chúng ta sẽ hoạt động chính xác và hiển thị kết quả: Một cách khác là tạo một lớp sắp xếp riêng biệt thực hiện giao diện so sánh và phương thức so sánh của nó :

public class CatComparator implements Comparator {

   @Override
   public int compare(Cat o1, Cat o2) {
       return o1.age > o2.age ? 1 : -1;
   }
}

Trong trường hợp này, để sử dụng nó, chúng ta phải đặt một đối tượng của lớp này thành hàm tạo TreeSet :

TreeSet set = new TreeSet<>(new CatComparator());

Sau đó, tất cả các đối tượng của lớp Cat có trong TreeSet sẽ được sắp xếp bằng lớp Cat Comparator . Bạn có thể tìm hiểu thêm về Comparator và Comparable trong Java từ bài viết này .

5. Hãy cho chúng tôi biết về Hàng đợi

Hàng đợi là giao diện chịu trách nhiệm về các cấu trúc được tổ chức dưới dạng hàng đợi - cấu trúc dữ liệu lưu trữ các phần tử một cách tuần tự. Ví dụ: trong một hàng người, người đầu tiên vào sẽ là người đến sớm hơn những người khác và người cuối cùng sẽ là người đến muộn hơn những người khác. Phương thức này được gọi là FIFO , tức là vào trước ra trước . Các phương thức Hàng đợi duy nhất tập trung vào làm việc với phần tử đầu tiên hoặc cuối cùng, ví dụ:

• thêm và cung cấp - chèn một phần tử vào cuối hàng đợi,
• xóa - truy xuất và xóa tiêu đề của hàng đợi này,
• nhìn trộm - Truy xuất nhưng không xóa tiêu đề hàng đợi.

PHẦN 2