Algorithms and data stricture

What is the Big O of binary search

O(log n)

What is the big O of bubble sort

O(n2)

What is the big O of merge sort

O(n log n))

What is the big O of quick sorting

O(N log N

What is the big O of a single loop

O(N)

What is the big O of two nested loops

O(N2)

What is the big O of three nested loops

O(N3)

What is profiling

Measuring where a program spends its running time to identify performance problems

What is cProfile

Pythons built-in tool for measuring function calls and execution times

What is the correct profiling approach

Find the problem, fix it, then check whether performance improved

runtime concentration

A small proportion of functions can account for most programs running time

What is ncalls

The number of times a function was called

What is tottime

The time spent executing the function itself, excluding child functions

What is percall

The average time taking by one function call

What is cumtime

The total time of a function, including time spent in child functions

What is call frequency

How often a function runs; even a fast function may become costly when called millions of times

What is big O

A measure of how an algorithms resource use grows as input size growsn

What is HashMap

A data structure that stores key-value pairs for fast lookup

What is a dictionary

Python’s implementation of a hash map using key-value pairs

What is hashing

The process of converting data into a numerical hash value to locate it quickly

What is collision in HashMaps

The situation in which different values map to the same hash-table location

What is dictionary operations

Access, add, update and delete entries using their keys

What is constant time lookup

O(1), access time remain broadly constant as data grows

What is a set

An unordered collection of unique values with no duplicates

What is union

The operation | that returns every element found in either set

Intersection

The operation “&” that returns only elements common to both sets

Difference

The operation “-“ that returns elements present only in the first set

Stack

A last in first out structure used for matching tags, undo operations and backtracking through maze choices

Queue

A first in first out structure in which the earliest item added is the first item removed

Demerging

Partitioning one input queue into separate queues while preserving the original order within each group

Binary tree

A hierarchical structure whose nodes have at most one left child and one right child

Binary search tree

A binary tree where smaller values are placed in the left subtree and larger values in the right subtree

Tree traversal

A systematic method for visiting every tree node in a chosen order, such as in-order, pre order or post order

Balanced tree

A tree whose height remains sufficiently small so searching, insertion and deletion can take logarithmic time

Min heap

A complete binary tree stored commonly in an array with the smallest element at the root

Heapq

Pythons built-in module for maintaining heaps, including efficient insertion and removal of the smallest item