Delete Duplicate Nodes from Linked List

Problem:
Given an unsorted linked list, delete duplicate nodes from the linked list.

Thinking:
This problem is again similar to previous 2 posts (determine uniqueness and remove duplicates). There are several algorithms available.

Node definition:
Suppose the node in this linked list is defined as the class below.

Solution 1:
Without using extra buffer, delete every duplicates for each node encountered. Time complexity \(O(n^2)\).

Solution 2:
Without using extra buffer, each time encountering a node, detect if it's a duplicate. If yes, then delete it. Time complexity \(O(n^2)\).

Solution 3:
Using an extra hash table / hash set / hash map to keep track which nodes have already existed. Average time complexity \(O(n)\).

Notes:

1. Would there be any differences if the linked list is doubly linked?
   ==> Probably not.
2. How about sorting the list first?
   ==> As long as you are allowed to destroy the original order, this should work.

Space Restricted String Hashing

Source: CLRS, Introduction to Algorithms, 2nd Edition, Page 236, Problem 11.3-2

Problem:
Suppose that a string of r characters is hashed into m slots by treating it as a radix-128 number and then using the division method. The number m is easily represented as a 32-bit computer word, but the string of r characters, treated as a radix-128 number, takes many words. How can we apply the division method to compute the hash value of the character string without using more than a constant number of words of storage outside the string itself?

Basics:
This problem requires some basic number theory principles, and more specifically modulo arithmetic. The following 2 will be applied to solve this problem. (The second one holds for integers only)
\begin{equation} (a+b)\%m=(a\%m+b\%m)\%m \end{equation} and \begin{equation} (a \cdot b )\%m=((a\%m) \cdot (b\%m))\%m \end{equation}

Solution:
Based on above analysis, the string of r characters can be hashed using division method with constant space. Any string of length r can be converted to a radix-128 number, say, \[n=c_{0} \cdot 128^{0}+c_{1} \cdot 128^{1}+c_{2} \cdot 128^{2} + \ldots + c_{r-1} \cdot 128^{r-1},\] where \(c_{i}\) means the \(i\)th character starting from the least significant end with 0 (which can also be viewed as an integer of its ASCII code).

Hence, apply the division hashing function, \begin{eqnarray} n\%m &=& (c_{0} \cdot 128^{0}+c_{1} \cdot 128^{1} + \ldots + c_{r-1} \cdot 128^{r-1})\%m \\ &=& ((c_{0} \cdot 128^{0})\%m+(c_{1} \cdot 128^{1})\%m + \ldots + (c_{r-1} \cdot 128^{r-1})\%m)\%m \\ \end{eqnarray} However, it looks that we need first compute some large numbers, for example, \(128^{r-1}\) of the last term. If so, we still need many words to store them. But based on the second rule mentioned above, we don't have to store such large numbers. All we need to do is take the modulo operation after each multiplication. In this way, only constant number of words for storage is needed.

Here is the code.


However, the above code involves nested loops, which is unnecessary. Based on Horner's rule, we can rewrite \(n\) as \[n=c_0+128(c_1+128(c_2+...+128(c_{r-2}+128\cdot c_{r-1}) \ldots))\]
This is also the basis for Rabin-Karp algorithm. Now, the code can be improved as below.

Direct Addressing on Huge Array

Source: CLRS, Introduction to Algorithms, 2nd Edition, Page 223, Problem 11.1-4

Problem:
We wish to implement a dictionary by using direct addressing on a huge array. At the start, the array entries may contain garbage, and initializing the entire array is impractical because of its size. Describe a scheme for implementing a direct-address dictionary on a huge array. Each stored object should use O(1) space; the operations SEARCH, INSERT, and DELETE should take O(1) time each; and the initialization of the data structure should take O(1) time.

Hint:
Use an additional stack, whose size is the number of keys actually stored in the dictionary, to help determine whether a given entry in the huge array is valid or not.

Solution:
Simply speaking, given an uninitialized huge array, implement a dictionary.
Besides the huge array, one more array can be used to store the actual objects (or their pointers). Call these 2 arrays H and S, respectively. Initially, the arrays contains no records and define a variable n = 0. For a certain key k, if k already exists in the dictionary, we want to keep this relationship: H[k] = i and S[i] = k (or S[i] points to the object with key k). Therefore, H[ S[i] ] = i and S[ H[k] ] = k should both hold for a valid record.

Now we design the dictionary operations:
Initialize: build an empty stack.
Search: given a key k, test 1 ≤ H[k] ≤ n && S[ H[k] ] == k, if true, found and return S[ H[k] ]; otherwise, not found.
Insert: if key k already exists, replace it; otherwise push k into S, say, S[n+1] ← k and n ← n+1, and update the dictionary by H[k] ← n (already incremented).
Delete: delete the object with key k. First search to make sure the record is in the dictionary. If found, after simply deleting the record, there will be a gap in the entry with index H[k] in array S. Need fill in this gap while maintaining the correct relationship between H and S. This involves the following steps:

• S[ H[k] ] ← S[n]
• H[ S[n] ] ← H[k]
• H[k] ← NULL
• S[n] ← NULL
• n ← n-1

All these operations can be done in time O(1).

References:

http://ripcrixalis.blog.com/2011/02/08/hello-world/

http://www.cs.duke.edu/courses/summer02/cps130/Homeworks/Solutions/H11-solution.pdf