Given an array of integers where each value

`1 <= x <= len(array)`

, write a function that finds all the duplicates in the array.

### C++ Solution

```
$ g++ -std=c++11 ./FindDuplicates.cc
$ ./a.out
1 2
```

Advertisements

Leave a reply

Given an array of integers where each value

`1 <= x <= len(array)`

, write a function that finds all the duplicates in the array.

```
$ g++ -std=c++11 ./FindDuplicates.cc
$ ./a.out
1 2
```

Advertisements

A hashmap has a time complexity of O(1) for **all** operations.

You have to find a constant time method to *uniformly* random selection of a key in a Hash map.

- The map can grow to memory size.
- You can use any readymade hash map.

I’m discussing the pseudo code for a Python solution. All operations work in constant time except `remove()`

.

```
randMap = {}
def insert(k, v):
randMap[k] = v
```

The random must pick a random key. But how? We can store all the keys in a list and then run `random()`

on the list indexes.

```
randMap = {}
indexMap = {}
keyList = []
last = 0
def insert(k, v):
randMap[k] = v
keyList.append(k)
last += 1
# Maintain index of each key
indexMap[k] = len(keyList)
```

```
def getRandom():
start = 0
end = len(keyList) - 1
randomIndex = random(start, end)
key = keyList[randomIndex]
return key
```

This is the crux of the problem. Deletion of a key would need us to change the index array too. That means we need to shift all elements of the array and complexity would shoot to O(n).

```
def remove(k):
# Remove from the hash map
randMap.pop(k, None)
# Remove from key list
index = indexMap[k]
# This is O(n) operation
keyList.remove(index)
# Pop the index too
indexMap.pop(k)
```

- Delete the entry and mark the entry invalid. The probability distribution does not change, however with more and more deletions, you have a sparse array. Thus you would need multiple
`getRandom()`

to get a valid key. - Move the last element to the deleted element. Adjust the index of the last element.

```
def remove(k):
# Remove from the hash map
randMap.pop(k, None)
index = indexMap[k]
indexMap[last] = index
# This is O(1) operation
keyList[index] = keyLast[last]
# Pop the index too
indexMap.pop(k)
last -= 1
```

This is a constant time solution.

- Start as
`ROOT --> Subtree-1 --> ROOT --> Subtree-2 --> ROOT --> Subtree-3 --> ROOT`

- Recurse at each subtree as above
- All nodes of a subtree appear together, contiguously in the traversal.

Assume we want LCA of a node `u`

in subtree `a`

and node `v`

in subtree `c`

. A Euler walk of the tree will have all nodes of the subtree `a`

followed by the LCA node `ROOT`

and all the nodes of subtree `c`

.

Thus Euler walk/ traversal of a tree will always have the LCA for any two nodes.

Written with StackEdit.

**Singly link list**

A link list is a non-linear data structure with a head pointer. The rest of the nodes in the list could be accessed by using “next” of head.

The code to create a list of N node involves creating head separately. Rest of the nodes are appended to the head.

That looked ugly to me and so I wrote it in a generic manner. Using a temporary pointer, I wrote a single loop to create N link list nodes, keeping head intact.

Here is the code:

#define NULL (char*)0 typedef struct node_ { int n; struct node_ *next; } node; int main() { int i = 5; node *head = NULL; node *temp = NULL; while (i-- > 0) { head = malloc(sizeof(node)); head->n = i; head->next = temp; temp = head; } temp = head;

%d bloggers like this: