# Oct 28, 2018

## Python `collections`

### `defaultdict`

dict subclass that calls a factory function to supply missing values

Returns a new dictionary-like object. [`defaultdict`](https://docs.python.org/2/library/collections.html#collections.defaultdict) is a subclass of the built-in [`dict`](https://docs.python.org/2/library/stdtypes.html#dict) class. It overrides one method and adds one writable instance variable. The remaining functionality is the same as for the [`dict`](https://docs.python.org/2/library/stdtypes.html#dict) class and is not documented here.

### `OrderedDict`

dict subclass that remembers the order entries were added

Return an instance of a dict subclass, supporting the usual [`dict`](https://docs.python.org/2/library/stdtypes.html#dict) methods. An `OrderedDict` is a dict that remembers the order that keys were first inserted. If a new entry overwrites an existing entry, the original insertion position is left unchanged. Deleting an entry and reinserting it will move it to the end.

### `deque`

Returns a new `deque` object initialized left-to-right (using [`append()`](https://docs.python.org/2/library/collections.html#collections.deque.append)) with data from *iterable*. If *iterable* is not specified, the new deque is empty.

Deques are a generalization of stacks and queues (the name is pronounced “deck” and is short for “double-ended queue”). Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same `O(1)` performance in either direction.

Though `list` objects support similar operations, they are optimized for fast fixed-length operations and incur O(n) memory movement costs for `pop(0)` and `insert(0, v)` operations which change both the size and position of the underlying data representation.

`append`(*x*)

Add *x* to the right side of the deque.

`appendleft`(*x*)

Add *x* to the left side of the deque.

`clear`()

Remove all elements from the deque leaving it with length 0.

`count`(*x*)

Count the number of deque elements equal to *x*.

`extend`(*iterable*)

Extend the right side of the deque by appending elements from the iterable argument.

`extendleft`(*iterable*)

Extend the left side of the deque by appending elements from *iterable*. Note, the series of left appends results in reversing the order of elements in the iterable argument.

`pop`()

Remove and return an element from the right side of the deque. If no elements are present, raises an [`IndexError`](https://docs.python.org/2/library/exceptions.html#exceptions.IndexError).

`popleft`()

Remove and return an element from the left side of the deque. If no elements are present, raises an [`IndexError`](https://docs.python.org/2/library/exceptions.html#exceptions.IndexError).

`remove`(*value*)

Remove the first occurrence of *value*. If not found, raises a [`ValueError`](https://docs.python.org/2/library/exceptions.html#exceptions.ValueError).

`reverse`()

Reverse the elements of the deque in-place and then return `None`.

`rotate`(*n=1*)

Rotate the deque *n* steps to the right. If *n* is negative, rotate to the left.

When the deque is not empty, rotating one step to the right is equivalent to `d.appendleft(d.pop())`, and rotating one step to the left is equivalent to `d.append(d.popleft())`.

Deque objects also provide one read-only attribute:`maxlen`

Maximum size of a deque or `None` if unbounded.

```bash
>>> from collections import deque
>>> d = deque('ghi')                 # make a new deque with three items
>>> for elem in d:                   # iterate over the deque's elements
...     print elem.upper()
G
H
I

>>> d.append('j')                    # add a new entry to the right side
>>> d.appendleft('f')                # add a new entry to the left side
>>> d                                # show the representation of the deque
deque(['f', 'g', 'h', 'i', 'j'])

>>> d.pop()                          # return and remove the rightmost item
'j'
>>> d.popleft()                      # return and remove the leftmost item
'f'
>>> list(d)                          # list the contents of the deque
['g', 'h', 'i']
>>> d[0]                             # peek at leftmost item
'g'
>>> d[-1]                            # peek at rightmost item
'i'

>>> list(reversed(d))                # list the contents of a deque in reverse
['i', 'h', 'g']
>>> 'h' in d                         # search the deque
True
>>> d.extend('jkl')                  # add multiple elements at once
>>> d
deque(['g', 'h', 'i', 'j', 'k', 'l'])
>>> d.rotate(1)                      # right rotation
>>> d
deque(['l', 'g', 'h', 'i', 'j', 'k'])
>>> d.rotate(-1)                     # left rotation
>>> d
deque(['g', 'h', 'i', 'j', 'k', 'l'])

>>> deque(reversed(d))               # make a new deque in reverse order
deque(['l', 'k', 'j', 'i', 'h', 'g'])
>>> d.clear()                        # empty the deque
>>> d.pop()                          # cannot pop from an empty deque
Traceback (most recent call last):
  File "<pyshell#6>", line 1, in -toplevel-
    d.pop()
IndexError: pop from an empty deque

>>> d.extendleft('abc')              # extendleft() reverses the input order
>>> d
deque(['c', 'b', 'a'])
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://lintcode-solutions.gitbook.io/project/oj-review/oct-28-2018.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.