Problem-1

Implement kỹ thuật giải quyết xung đột sử dụng giải pháp separate chaining

Solution: Code phần này mình tham khảo ở đây

import java.util.ArrayList;
import java.util.Objects; // A node of chains
class HashNode<K, V> { K key; V value; final int hashCode; // Reference to next node HashNode<K, V> next; // Constructor public HashNode(K key, V value, int hashCode) { this.key = key; this.value = value; this.hashCode = hashCode; }
} // Class to represent entire hash table
class Map<K, V> { // bucketArray is used to store array of chains private ArrayList<HashNode<K, V> > bucketArray; // Current capacity of array list private int numBuckets; // Current size of array list private int size; // Constructor (Initializes capacity, size and // empty chains. public Map() { bucketArray = new ArrayList<>(); numBuckets = 10; size = 0; // Create empty chains for (int i = 0; i < numBuckets; i++) bucketArray.add(null); } public int size() { return size; } public boolean isEmpty() { return size() == 0; } private final int hashCode (K key) { return Objects.hashCode(key); } // This implements hash function to find index // for a key private int getBucketIndex(K key) { int hashCode = hashCode(key); int index = hashCode % numBuckets; // key.hashCode() could be negative. index = index < 0 ? index * -1 : index; return index; } // Method to remove a given key public V remove(K key) { // Apply hash function to find index for given key int bucketIndex = getBucketIndex(key); int hashCode = hashCode(key); // Get head of chain HashNode<K, V> head = bucketArray.get(bucketIndex); // Search for key in its chain HashNode<K, V> prev = null; while (head != null) { // If Key found if (head.key.equals(key) && hashCode == head.hashCode) break; // Else keep moving in chain prev = head; head = head.next; } // If key was not there if (head == null) return null; // Reduce size size--; // Remove key if (prev != null) prev.next = head.next; else bucketArray.set(bucketIndex, head.next); return head.value; } // Returns value for a key public V get(K key) { // Find head of chain for given key int bucketIndex = getBucketIndex(key); int hashCode = hashCode(key); HashNode<K, V> head = bucketArray.get(bucketIndex); // Search key in chain while (head != null) { if (head.key.equals(key) && head.hashCode == hashCode) return head.value; head = head.next; } // If key not found return null; } // Adds a key value pair to hash public void add(K key, V value) { // Find head of chain for given key int bucketIndex = getBucketIndex(key); int hashCode = hashCode(key); HashNode<K, V> head = bucketArray.get(bucketIndex); // Check if key is already present while (head != null) { if (head.key.equals(key) && head.hashCode == hashCode) { head.value = value; return; } head = head.next; } // Insert key in chain size++; head = bucketArray.get(bucketIndex); HashNode<K, V> newNode = new HashNode<K, V>(key, value, hashCode); newNode.next = head; bucketArray.set(bucketIndex, newNode); // If load factor goes beyond threshold, then // double hash table size if ((1.0 * size) / numBuckets >= 0.7) { ArrayList<HashNode<K, V> > temp = bucketArray; bucketArray = new ArrayList<>(); numBuckets = 2 * numBuckets; size = 0; for (int i = 0; i < numBuckets; i++) bucketArray.add(null); for (HashNode<K, V> headNode : temp) { while (headNode != null) { add(headNode.key, headNode.value); headNode = headNode.next; } } } } // Driver method to test Map class public static void main(String[] args) { Map<String, Integer> map = new Map<>(); map.add("this", 1); map.add("coder", 2); map.add("this", 4); map.add("hi", 5); System.out.println(map.size()); System.out.println(map.remove("this")); System.out.println(map.remove("this")); System.out.println(map.size()); System.out.println(map.isEmpty()); }
}

Problem-2

Cho một mảng ký tự, đưa ra thuật toán loại bỏ các ký tự trùng lặp.

Solution: Bắt đầu với ký tự đầu tiên và kiểm tra xem nó có xuất hiện trong phần còn lại của chuỗi hay không bằng cách sử dụng tìm kiếm tuyến tính đơn giản. Nếu nó lặp lại, hãy đưa ký tự cuối cùng đến vị trí đó và giảm kích thước của chuỗi đi một. Tiếp tục quá trình này cho từng ký tự riêng biệt của chuỗi đã cho.

public void removeDuplicates(char[] s, int n){ for (int i = 0; i < n; i++) { for (int j = i+1; j < n;) { if(s[i] == s[j]){ s[j] = s[--n]; } else { j++; } } } }

Time Complexity: $O(n^2)$. Space Complexity: $O(1)$.

Problem-3

Chúng ta có thể tìm ra ý tưởng nào khác để giải quyết vấn đề này trong thời gian tốt hơn $O(n^2)$ không?
Lưu ý rằng thứ tự các ký tự không quan trọng.

Solution: Sử dụng sorting để tập hợp các ký tự lặp lại với nhau. Cuối cùng quét qua mảng để loại bỏ các bản sao ở các vị trí liên tiếp.

Time Complexity: $Θ(nlogn)$.
Space Complexity: $O(1)$.

Problem-4

Chúng ta có thể giải quyết vấn đề này chỉ bằng một lần duyệt qua mảng đã cho không?

Solution: Chúng ta có thể sử dụng hash table để kiểm tra xem một ký tự có lặp lại trong chuỗi đã cho hay không. Nếu ký tự hiện tại không có sẵn trong bảng băm thì hãy chèn nó vào bảng băm và giữ nguyên ký tự đó trong chuỗi đã cho. Nếu ký tự hiện tại tồn tại trong bảng băm thì bỏ qua ký tự đó.

 public void removeDuplicates(char[] s){ Set<Character> h = new HashSet<>(); int current = 0, last = 0; for(; current < s.length; current++){ if(!h.contains(s[current])){ s[last++] = s[current]; h.add(s[current]); } } s[last] = '\0'; }

Time Complexity: $Θ(n))$.
Space Complexity: $O(n))$.

Problem-5

Cho hai mảng số không có thứ tự, kiểm tra xem cả hai mảng có cùng bộ số không?

Solution: Giả sử hai mảng cho trước là A và B. Một giải pháp đơn giản cho bài toán đã cho là: với mỗi phần tử của A, hãy kiểm tra xem phần tử đó có thuộc B hay không. Một vấn đề phát sinh với cách tiếp cận này nếu có sự trùng lặp. Ví dụ, hãy xem xét các đầu vào sau:

Thuật toán trên cho kết quả sai vì với mỗi phần tử của A cũng có một phần tử thuộc B. Nhưng nếu nhìn vào số lần xuất hiện thì chúng không giống nhau. Độ phức tạp về thời gian của phương pháp này là $O(n^2)$, vì với mỗi phần tử của A chúng ta phải quét B.

Problem-6

Chúng ta có thể cải thiện độ phức tạp về thời gian của Problem-5 không?

Solution: Để cải thiện độ phức tạp về thời gian, giả sử rằng chúng ta đã sắp xếp cả hai danh sách. Vì kích thước của cả hai mảng là n nên chúng ta cần thời gian $O(n logn)$ để sắp xếp chúng. Sau khi sắp xếp, chúng ta chỉ cần quét cả hai mảng bằng hai con trỏ và xem liệu chúng có trỏ đến cùng một phần tử mỗi lần hay không và tiếp tục di chuyển các con trỏ cho đến khi chúng ta đến cuối mảng.

Độ phức tạp về thời gian của phương pháp này là $O(n logn)$. Điều này là do chúng ta cần $O(n logn)$ để sắp xếp các mảng. Sau khi sắp xếp, chúng ta cần thời gian $O(n)$ để quét nhưng ít hơn so với $O(n log n)$.

Problem-7

Chúng ta có thể cải thiện hơn nữa độ phức tạp về thời gian của Problem-5 không?

Solution: Có, bằng cách sử dụng bảng băm. Hãy xem xét thuật toán sau.

Algorithm:

• Xây dựng bảng băm với các phần tử mảng A làm key.
• Trong khi chèn các phần tử, hãy theo số lần xuất hiện của mỗi số. Điều đó có nghĩa là, nếu có sự trùng lặp thì hãy tăng bộ đếm(value) của key tương ứng đó.
• Sau khi xây dựng bảng băm cho các phần tử của A, bây giờ hãy quét mảng B.
• Với mỗi lần xuất hiện các phần tử của B, hãy giảm giá trị bộ đếm tương ứng.
• Cuối cùng, kiểm tra xem tất cả các bộ đếm có bằng 0 hay không.
• Nếu tất cả các bộ đếm đều bằng 0 thì cả hai mảng đều giống nhau, nếu không thì các mảng sẽ khác nhau.

Time Complexity: $O(n)$. Space Complexity; $O(n)$ for hash table.

Problem-8

Cho một danh sách các cặp số; nếu cặp(i,j) tồn tại và cặp(j,i) tồn tại, hãy báo cáo tất cả các cặp đó. Ví dụ: trong {{1,3},{2,6},{3,5},{7,4},{5,3},{8,7}}, chúng ta thấy rằng {3,5} và {5,3} đều có mặt. Báo cáo cặp này khi bạn gặp {5,3}. Chúng ta gọi những cặp như vậy là 'cặp đối xứng'. Hãy đưa ra một thuật toán hiệu quả để tìm tất cả các cặp như vậy.

Solution: Bằng cách sử dụng hàm băm, chúng ta có thể giải quyết vấn đề này chỉ trong một lần quét. Hãy xem xét thuật toán sau.

Algorithm:

• Đọc từng cặp phần tử và chèn chúng vào bảng băm. Đối với mỗi cặp, coi phần tử đầu tiên là key và phần tử thứ hai là value.
• Trong khi chèn các phần tử, hãy kiểm tra xem giá trị băm của phần tử thứ hai của cặp hiện tại có giống với key đã tồn tại trong hashtable hay không, nếu có kiểm tra thêm phần tử thứ nhất có trùng với value tương ứng của key đã tồn tại kia không.
• Nếu chúng giống nhau thì điều đó cho thấy một cặp đối xứng và in ra cặp đó.
• Ngược lại thì chèn phần tử đó vào đó.
• Vào thời điểm chúng ta hoàn thành việc quét tất cả các cặp, chúng ta đã xuất ra tất cả các cặp đối xứng.

Time Complexity: $O(n)$ cho việc quét mảng.
Space Complexity; $O(n)$ cho hash table.

Problem-9

Cho một danh sách liên kết đơn, kiểm tra xem nó có vòng lặp hay không.

Solution: Using Hash Tables

Algorithm:

• Duyệt qua từng nút danh sách liên kết.
• Kiểm tra xem địa chỉ của nút có trong bảng băm hay không.
• Nếu nó đã có sẵn trong bảng băm, điều đó cho biết chúng ta đang truy cập một nút đã được truy cập. Điều này chỉ có thể thực hiện được nếu danh sách liên kết đã cho có một vòng lặp trong đó.
• Nếu địa chỉ của nút không có trong bảng băm thì chèn địa chỉ của nút đó vào bảng băm.
• Tiếp tục quá trình này cho đến khi đến cuối danh sách liên kết hoặc tìm thấy vòng lặp.

Time Complexity: $O(n)$ cho việc quét Linked List.
Space Complexity; $O(n)$ cho hash table.

Problem-10

Cho một mảng gồm 101 phần tử. Trong số đó có 50 phần tử khác nhau, 24 phần tử được lặp lại 2 lần và một phần tử được lặp lại 3 lần. Tìm phần tử được lặp lại 3 lần trong O(1).

Solution: Using Hash Tables

Algorithm:

• Quét từng phần tử của mảng đầu vào.
• Kiểm tra xem phần tử đã có trong bảng băm hay chưa.
• Nếu nó đã có sẵn trong bảng băm, hãy tăng giá trị bộ đếm của nó [điều này cho biết số lần xuất hiện của phần tử].
• Nếu phần tử không có trong bảng băm, hãy chèn nút đó vào bảng băm có giá trị bộ đếm là 1.
• Tiếp tục quá trình này cho đến hết mảng.
• Cuối cùng quét mảng để tìm phần tử lặp lại 3 lần

Time Complexity: $O(n)$ cho việc quét.
Space Complexity; $O(n)$ cho hash table.

Problem-11

Cho m tập hợp số nguyên có n phần tử, hãy đưa ra thuật toán tìm phần tử có số lượng xuất hiện trong nhiều tập hợp nhất?

Solution: Using Hash Tables
Algorithm:

• Quét từng tập hơp đầu vào.
• Đối với mỗi phần tử, hãy theo dõi bộ đếm.
• Bộ đếm cho biết tần suất xuất hiện trong tất cả các tập hợp.
• Sau khi hoàn tất quá trình quét tất cả các tập hợp, hãy chọn phần tử có giá trị bộ đếm tối đa.

Time Complexity: O(mn), vì chúng ta cần quét tất cả các tập hợp. Space Complexity: O(mn), Bởi vì, trong trường hợp xấu nhất, tất cả các phần tử có thể khác nhau.

Problem-12

Cho hai tập hợp A và B và một số K, hãy đưa ra thuật toán tìm xem có tồn tại một cặp phần tử, một từ A và một từ B, cộng lại thành K hay không.

Solution: Để đơn giản, chúng ta giả sử rằng kích thước của A là m và kích thước của B là n.

• Chọn tập hợp có size nhỏ hơn.
• Đối với tập hợp đã chọn, hãy tạo một bảng băm. Chúng ta có thể để cả key và value như nhau.
• Bây giờ quét mảng thứ hai và kiểm tra xem (Giá trị K - phần tử đang được chọn) có tồn tại trong bảng băm hay không.
• Nếu nó tồn tại thì trả về cặp phần tử.
• Nếu không thì tiếp tục cho đến khi kết thúc tập hợp.

Time Complexity: O(Max(m,n)), vì chúng ta đang thực hiện hai lần quét.
Space Complexity: O(Min(m,n)), đối với bảng băm. Chúng ta có thể chọn tập hợp nhỏ để tạo bảng băm.

Problem-13

Đưa ra thuật toán để loại bỏ các ký tự khỏi một chuỗi được cho trước mà nằm trong một chuỗi khác?

Solution: Để đơn giản, chúng ta hãy giả sử rằng số lượng ký tự khác nhau tối đa là 256. Đầu tiên, chúng ta tạo một mảng phụ được khởi tạo bằng 256. Quét các ký tự cần loại bỏ và đối với mỗi ký tự đó, chúng ta đặt giá trị thành 1, điều này cho biết rằng chúng ta cần loại bỏ ký tự đó.

Sau khi khởi tạo, quét chuỗi đầu vào, với từng ký tự ta kiểm tra xem ký tự đó có cần xóa hay không. Nếu cờ được đặt thì chúng ta chỉ cần chuyển sang ký tự tiếp theo, nếu không chúng ta sẽ giữ ký tự đó trong chuỗi đầu vào. Tiếp tục quá trình này cho đến khi chúng ta đến cuối chuỗi đầu vào.

Time Complexity: Thời gian quét ký tự cần loại bỏ + Thời gian quét mảng đầu vào= $O(n) +O(m) ≈ O(n)$. Trong đó m là độ dài của ký tự cần loại bỏ và n là độ dài của chuỗi đầu vào.
Space Complexity: $O(m)$, độ dài của các ký tự cần xóa. Nhưng vì chúng ta giả định số lượng ký tự khác nhau tối đa là 256 nên chúng ta có thể coi đây là một hằng số. Nhưng chúng ta nên nhớ rằng khi xử lý các ký tự nhiều byte, tổng số ký tự khác nhau nhiều hơn 256.

Problem-14

Đưa ra thuật toán tìm ký tự không lặp lại đầu tiên trong chuỗi. Ví dụ: ký tự không lặp lại đầu tiên trong chuỗi “abzddab” là ‘z’.

Solution: Quét toàn bộ: với mỗi ký tự trong chuỗi đã cho, chúng ta có thể quét chuỗi còn lại nếu ký tự đó xuất hiện trong đó. Nếu nó không xuất hiện thì chúng ta đã giải quyết xong và chúng ta trả về ký tự đó. Nếu ký tự xuất hiện ở chuỗi còn lại thì chuyển sang ký tự tiếp theo.

public char firstNonRepeatedChar(char[] str, int len){ int i, j, repeated = 0; for (i = 0; i < len; i++) { repeated = 0; for (j = 0; j < len; j++) { if(i != j && str[i] == str[j]){ repeated = 1; break; } } if (repeated == 0){ return str[i]; } } return ''; }

Time Complexity: $O(n^2)$ cho 2 vòng lặp
Space Complexity: O(1).

Problem-15

Có thể cải thiện Problem-14 không

Solution: Bằng cách sử dụng bảng băm, chúng ta có thể giảm độ phức tạp về thời gian. Tạo bảng băm bằng cách đọc tất cả các ký tự trong chuỗi đầu vào và đếm số lần mỗi ký tự xuất hiện. Sau khi tạo bảng băm, chúng ta có thể đọc các mục trong bảng băm để xem phần tử nào có số đếm bằng 1. Cách tiếp cận này chiếm không gian O(n) nhưng cũng giảm độ phức tạp về thời gian xuống O(n).

public char firstNonRepeatedCharUsingHash(char[] str) { int[] count = new int[256]; for (int i = 0; i < 256; i++) { count[i] = 0; } for (int i = 0; i < str.length; i++) { count[str[i]]++; } for (int i = 0; i < str.length; i++) { if (count[str[i]] == 1){ return str[i]; } } return ''; }

Time Complexity: Chúng ta có $O(n)$ để tạo bảng băm và một $O(n)$ khác để đọc các mục của bảng băm. Vậy tổng thời gian là $O(n) + O(n) = O(2n) ≈ O(n)$.
Space Complexity: $O(n)$ để giữ các giá trị đếm.

Problem-16

Cho một chuỗi, hãy đưa ra thuật toán tìm chữ cái lặp lại đầu tiên trong chuỗi?

Solution: Giải pháp cho vấn đề này tương tự Problem-15. Điểm khác biệt duy nhất là thay vì quét bảng băm hai lần, chúng ta có thể đưa ra câu trả lời chỉ sau một lần quét. Điều này là do khi chèn vào bảng băm, chúng ta có thể xem phần tử đó đã tồn tại hay chưa. Nếu nó đã tồn tại thì chúng ta chỉ cần trả về ký tự đó.

 public char firstRepeatedCharUsingHash(char[] str) { int[] count = new int[256]; for (int i = 0; i < 256; i++) { count[i] = 0; } for (int i = 0; i < str.length; i++) { if (count[str[i]] == 1){ return str[i]; } else { count[str[i]]++; } } return ''; }

Time Complexity: Chúng ta có $O(n)$ để quét và tạo bảng băm. Lưu ý rằng chúng ta chỉ cần một lần quét cho vấn đề này. Vậy tổng thời gian là $O(n)$.
Space Complexity: $O(n)$ để giữ các giá trị đếm.

Problem-17

Cho một dãy n số, hãy tạo một thuật toán hiển thị tất cả các cặp có tổng là S.

Solution: Vấn đề này tương tự như Problem-12. Nhưng thay vì sử dụng hai tập hợp chúng ta chỉ sử dụng một tập hợp.

Algorithm:

• Quét từng phần tử của mảng đầu vào và tạo bảng băm. Cả key và value đều có thể giống nhau.
• Sau khi tạo bảng băm, quét lại mảng đầu vào và kiểm tra xem (S – phần tử đã chọn) có tồn tại trong bảng băm hay không.
• Nếu có thì trả về cặp phần tử
• Nếu không thì tiếp tục và đọc tất cả các phần tử của mảng.

Time Complexity: Chúng ta có $O(n)$ để tạo bảng băm và một $O(n)$ khác để đọc các mục của bảng băm. Vậy tổng thời gian là $O(n) + O(n) = O(2n) ≈ O(n)$.

Space Complexity: $O(n)$ để tạo bảng băm

Problem-18

Có cách nào khác để giải quyết Problem-17 không?

Solution: Có. Giải pháp thay thế cho vấn đề này là sắp xếp. Đầu tiên sắp xếp mảng đầu vào. Sau khi sắp xếp, sử dụng hai con trỏ, một ở đầu và một ở cuối. Mỗi lần cộng giá trị của cả hai phần tử và xem tổng của chúng có bằng S hay không. Nếu chúng bằng nhau thì in cặp đó. Mặt khác, tăng con trỏ bên trái nếu tổng nhỏ hơn S và giảm con trỏ bên phải nếu tổng lớn hơn S.

Time Complexity: Time for sorting + Time for scanning = $O(nlogn) + O(n) ≈ O(nlogn)$.
Space Complexity: $O(1)$.

Problem-19

Chúng ta có một tập tin với hàng triệu dòng dữ liệu. Chỉ có hai dòng giống hệt nhau; phần còn lại là duy nhất. Mỗi dòng dài đến mức có thể không vừa với bộ nhớ. Giải pháp hiệu quả nhất để tìm các dòng giống hệt nhau là gì?

Solution: Vì một dòng hoàn chỉnh có thể không vừa với bộ nhớ chính, nên hãy đọc một phần dòng đó và tính hàm băm từ một phần dòng đó. Sau đó đọc phần tiếp theo của dòng và tính giá trị băm. Lần này cũng sử dụng hàm băm trước đó trong khi tính toán giá trị băm mới. Tiếp tục quá trình này cho đến khi chúng ta tìm thấy hàm băm cho dòng hoàn chỉnh. Thực hiện việc này cho từng dòng và lưu trữ tất cả các giá trị băm trong một tệp [hoặc duy trì bảng băm của các giá trị băm này]. Nếu tại bất kỳ thời điểm nào bạn nhận được cùng một giá trị băm, hãy đọc từng dòng tương ứng và so sánh.

Problem-20

Nếu h là hàm băm và được sử dụng để băm n key vào một bảng có kích thước s, trong đó n <= s, thì số lần xung đột dự kiến liên quan đến một khóa X cụ thể là (A) nhỏ hơn 1.
(B) nhỏ hơn n.
(C) nhỏ hơn.
(D) nhỏ hơn $n/2$ .

Solution: A