> For the complete documentation index, see [llms.txt](https://huang-jason.gitbook.io/complat-software-training-101/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://huang-jason.gitbook.io/complat-software-training-101/lv-data-structure.md).

# lv - array

static array = a fixed capacity that needs to be specified at allocation.

dynamic array = allows elements to be added or removed, without specify length in the beginning.

![](https://437555650-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lq83PytCJFhVoqGvu-1%2F-Lq83RGMs1nIq67HB7g9%2F-Lq83UKrjzR43bHBsBcY%2Fdynamic_arr.png?generation=1569962720125381\&alt=media)

| python list      |      | python dict |      |
| ---------------- | ---- | ----------- | ---- |
| indexing         | O(1) | get item    | O(1) |
| index assignment | O(n) | iteration   | O(n) |
| pop(i)           | O(n) | copy        | O(n) |

### Python array

#### array sequence: \[1]List, \[2]tuple, \[3]string; (support indexing)

Lists = dynamic arrays of pointers. (indexing = O(1))

RAM (random access memory) = indexing with O(1)

Python Unicode = 2 Bytes

indexing = start + cell\_size \* index

#### slice = new array instance pointing to same locations.

![](https://437555650-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lq83PytCJFhVoqGvu-1%2F-Lq83RGMs1nIq67HB7g9%2F-Lq83UKuk39E-U0uOx3V%2Fslice.png?generation=1569962720355947\&alt=media)

shallow copy = copy reference

deep copy = copy elements

**dynamic array with amortized to append elements**: *average* expanding op is O(1), actually \~O(3)

![](https://437555650-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lq83PytCJFhVoqGvu-1%2F-Lq83RGMs1nIq67HB7g9%2F-Lq83UKwAtZ7Z5-z2reV%2Famortized_2.png?generation=1569962720190598\&alt=media)

## 1. Anagram

```
Given: s1 = 'god', s2 = 'd og'
Question: is s1 == s2?
```

1. two sorted string are the same -> anagram.
2. white space is not considered.
3. solution = hash table 

## 2. Array Pair Sum

```
Given: integer array = [1, 3, 2, 2], target = 4
Question: return [1]pairs sum = target [2]uniq pairs
```

solution: sets for checking

## 3. Find missing elements

```
Given: arr_one = [1, 2, 3, 4, 5, 6, 7] non-negative array, arr_two = [3, 7, 2, 1, 4, 6] shuffuled & deleted random
Question: find missing
```