Transform linked list to hash map

Question

Given a linked list, transform it into a hash map where each unique value in the linked list is a key, and its corresponding value is the count of occurrences of that key in the list. The output should be a hash map object that represents this mapping.

Codemia · Accepted Answer

The problem requires us to transform a linked list into a hash map (dictionary) that counts the occurrences of each unique value in the list. The most suitable pattern for this problem is the use of a hash map for frequency counting. This is because we need to keep track of how many times each unique value appears in the linked list, which aligns perfectly with the capabilities of a hash map—offering average O(1) time complexity for insertions and lookups. Additionally, the linked list must be traversed in a linear fashion, making this a straightforward application of a single-pass algorithm.

1. **Initialize a Hash Map**: Start with an empty hash map to store the frequency of each value.
2. **Traverse the Linked List**: Use a pointer to iterate through each node in the linked list.
   - For each node, retrieve its value. 
   - Check if the value is already a key in the hash map.
   - If it is, increment its count. If it is not, add it to the hash map with a count of 1.
3. **Return the Hash Map**: After completing the traversal, return the hash map containing the counts.

**Example**: Given a linked list: 1 -> 2 -> 2 -> 3 -> 1, the resulting hash map should be: {1: 2, 2: 2, 3: 1}.

```python
class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

def linked_list_to_hash_map(head):
    count_map = {}
    current_node = head
    while current_node is not None:
        count_map[current_node.value] = count_map.get(current_node.value, 0) + 1
        current_node = current_node.next
    return count_map
```

The time complexity of this solution is O(n), where n is the number of nodes in the linked list. This is because we perform a single traversal of the linked list, visiting each node exactly once. The space complexity is also O(k), where k is the number of unique values in the linked list. This is due to the hash map storing the counts of each unique value, which could be as many as n in the case of all unique values.

1. **Empty Linked List**: If the head of the linked list is None, the output should be an empty hash map: `{}`.
2. **Single Node**: A linked list with a single node should return a hash map with that one value: e.g., for a list containing only `5`, the output should be `{5: 1}`.
3. **All Unique Values**: In a case where all values are unique, the output hash map should have each value with a count of 1. For example, for the list `1 -> 2 -> 3`, the output should be `{1: 1, 2: 1, 3: 1}`.

Transform linked list to hash map

Spotify

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Spotify Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string