# Interview Cake's Hashing problems

In-flight entertainment, Permutation palindrome, Word cloud data, Topscores

### 1. Given a list of movie lengths and a total flight length, determine if there exist two movies that add up to the total length.

Example:

``````- Input: list=[]int{2, 3, 4}, length=6
Output: true, because there exists 2 and 4 that add up to 6
``````

Approach:

``````- Could use hashmap to keep track of movie lengths that we've seen so far and
look it up as we iterate through the list.
``````

Cost:

``````- O(n) time, O(n) space.
``````

### 2. Given a string, check if its permutation is a palindrome.

Example:

``````- Input: "ivicc"
Output: true
- Input: "civic"
Output: true
``````

Approach:

``````- To determine if a permutation is a palindrome, need to check if each
character in the string appears an even number of times, allowing for
only one character to appear an odd time, that is the middle one.
- Could use a hashmap store the characters and their number of occurrences.
``````

Cost:

``````- O(n) time, O(1) space.
``````

### 3. Given a sentence (string), return its word count map.

Example:

``````- Input: "Cliff finished his cake and paid the bill. Bill finished his cake at the edge of the cliff."
Output: map[string]int{"cliff": 1, "Cliff": 1, "finished": 2, "his": 2, "cake": 2, "and": 1, "paid": 1, "the": 3, "bill": 1, "Bill": 1, "at": 1, "edge": 1, "of": 1}
``````

Approach:

``````- First get rid of special characters, then use a hashmap to keep counts of words
as we iterate through the string.
``````

Cost:

``````- O(n) time, O(n) space.
``````

### 4. Given an unsorted list scores (integer) and a highest possible score (integer), return a sorted list utilizing that fact.

Example:

``````- Input: []int{37, 89, 41, 65, 91, 53}, 100
Output: []int{91, 89, 65, 53, 41, 37}
``````

Approach:

``````- Utilize the highest score to allocate a fix-sized list ahead of time where
where its indices represent the scores themselves and its values represent
how many time these scores appear in the list.
``````

Cost:

``````- O(n) time, O(n) space.
``````