Data Structures And Algorithms

Question 1

Unpacking a Sequence into Separate Variables

Answer 1

>>>p = (4, 5) >>>x,y = p >>>x 4 >>>y 5 >>> >>>data = [‘ACME’, 50, 91.1, (2012, 12, 21)] >>>name, shares, price date = data >>>name ‘ACME’ >>>year 2012 >>>mon 12 >>>day 21

Question 2

Unpacking Elements of Iterable of Arbitrary Length

Answer 2

Def drop_first_last(grades): First, *middle, last = grades Return avg(middle) >>>record = (‘Dave’, ‘dave@example.com, ‘773-555-2837’, ‘847-555-2837’) >>>name, email, *phone-numbers = record >>>name ‘Dave’ >>>email ‘Dave@example.com’ . . . Etc *trailing_qtrs, current_qtr = sales_record Trailing avg_comparison(trailing_avg, current_qtr) >>>*trailing, current = [10, 8, 7, 1, 9, 5, 10, 3] >>>trailing [10, 8, 7, 1, 9, 5, 10, 3] >>>current 3

Question 3

Keeping the last N Items

Answer 3

From collections import deque Def search(lines, pattern, history=5): Previous_lines = deque(maxlen=history) For line in lines: If pattern in line: Yield line, previous_lines Previous_lines.append(line) #Example use on a file If _name_ ==‘_main_: With open(‘Somefile.txt’) as f: For line, per lines in search(f, ‘Python’, 5): Print(plane, end=‘ ‘) Print(line, end=‘ ‘) Print(‘-‘*20)

Question 4

Finding the largest and smallest of N Items

Answer 4

Import heapq Nums = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 23] Print(heapq.nlargest(3 , nums)) #Prints [42, 37, 23] Print(heapq.nsmallest(3, nums)) #prints [-4, 1, 2] Portfolio = [{‘name’: ‘IBM’, ‘shares’: 100, ‘price’: 91.1}, {‘name’: ‘AAPL’, ‘shares’: 50, ‘price’: 543.22}, {‘name’:’FB’, ‘shares’: 200, ‘price’: 21.09}, {‘name’: ‘HPQ”, ‘shares’: 35, ‘price’: 31.75}, {‘name’: ‘YHOO’, ‘shares’: 45, ‘price’ 16.35}, {‘name’: ‘ACME’, ‘shares’: 75, ‘price’: 115.65}] Cheap = heapq.nsmallest(3, portfolio, key=lambda s: s[‘price’]) Expensive = heapq.nlargest(3, portfolio, key=lambda s: s[‘price’])

Question 5

Heappop()

Answer 5

>>>nums = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2] >>>import heapq >>>heap = list(nums) >>>heapq.heapify(heap) >>>heap [-4, 2, 1, 23, 7] >>>heapq.heappop(heap) -4 >>>heapq.heappop(heap) 1 >>>heapq.heappop(heap) 2

Question 6

Implementing a Priority Queue

Answer 6

Import heapq Class PriorityQueue Def_init_(self): Self.queue = [] Self.index = 0 Def push(self, item, priority): Heapq.heappush(self._queue, (-priority, self._index, item)) Self.index += 1 Def pop(Self): Return heapq.heappop(self._queue)[-1] >>>class Item: … def _init_(self, name): … Self.name = name … def _repr_(self): … Return ‘Item({!r})’.format(self.name) … >>>q = PriorityQueue() >>>q.push(Item(‘foo’), 1) >>>q.push(Item(‘bar’), 5) >>>q.push(Item(‘spam’), 4) >>>q.push(Item(‘grock’), 1) >>>q.pop() Item(‘bar’) >>>q.pop() Item(‘spam’) >>>q.pop() Item(‘foo’) >>>q.pop() Item(‘grok’)

Question 7

Mapping Keys to Multiple Values in a Dictionary

Answer 7

d = {

‘a’ : [1, 2, 3],

‘b’ : [4, 5]

}

e = {

‘a’ : {1, 2, 3},

‘b’ : {4, 5}

}

The choice of list or set depends on intended use - list if you want to preserve insertion order for items, set if want to eliminate duplicates and don’t care about the order

. . . or use defaultdict . . .

d = defaultdict(list)

d[‘a’].append(1)

d[‘a’].append(2)

d[‘b;].append(4)

. . .

d =defaultdict(set)

d[‘a’].add(1)

d[‘a’].add(2)

d[‘b’]add(4)

Question 8

Keeping Dictionaries in Order

Answer 8

prints “foo 1”, “bar 2”, “spam 3”, “grok 4”

from collections import OrderedDict

d = OrderedDict()

d[‘foo’] = 1

d[‘bar’] = 2

d[‘spam’] = 3

d[‘grok’] = 4

for key in d:

print(key, d[key])

>>> import json

>>> json.dumps(d)

’{“foo”: 1, “bar”: 2, “spam”: 3, “grok”:4}’

Question 9

Calculating with Dictionaries

Answer 9

can be useful to invert values using zip()

prices = {

‘ACME’: 45.23,

‘AAPL’: 612.78,

‘IBM’: 205.55,

‘HPQ’: 37.20,

‘FB’: 10.75

}

min_price = min(zip(prices.values(), prices.keys()))

max_price = max(zip(prices.values(), prices.keys()))

Similarly, to rank data, use zip() with sorted()

prices_sorted = sorted(zip(prices.values(), prices.keys()))

prices_sorted is [(10.75, ‘FB’), ( . . .

Question 10

Finding Commonalities in Two Dictionaries

Answer 10

a = {

‘x’: 1,

‘y’: 2,

‘z’: 3

}

b = {

‘w’: 10,

‘x’: 11,

‘y’: 2

}

Find keys in common

a.keys() & b.keys()

Find keys in a that are not in b

a.keys() - b.keys()

Find (key,value) pairs in common

a.items() & b.items()

Make a new dictionary with certain keys removed

c = {key:a[key] for key in a.keys() - {‘z’, ‘w’}}

Question 11

Removing Duplicates from a Sequence while Maintainging Order

Answer 11

def dedupe(items):

seen = set()

for item in items:

if item not in seen:

yield item

seen.add(item)

>>> a = [1, 5, 2, 1, 9, 1, 5, 10]

>>> list(dedupe(a))

[1, 5, 2, 9, 10]

non hashable sequences (such as dicts):

def dedupe(items, key=None):

seen = set()

for item in items:

val = item if key is None else key(item)

if val not in seen:

yield item

seen.add(val)

>>> a = [{‘x’: 1, ‘y’: 2}, {‘x’:1, ‘y’: 3}, {‘x’ : 1, ‘y’: 2} , {‘x’: 2, ‘y’: 4}]

>>>list(dedupe(a, key = lambda d: (d[‘x’], d[‘y’])))

[{‘x’: 1, ‘y’: 2}, {‘x’: 1, ‘y’: 3}, {‘x’: 2, ‘y’: 4}]

>>>list(dedupe(, key=lambda d: d[‘x’]))

[{‘x’: 1, ‘y’: 2}, {‘x’: 2, ‘y’: 4}]