Leaving the definition of this broad term aside, in the context of [[showcase relevant expertise|our approach]] for [[tech competence assessment]] we usually imply: - ability to transform logic described by words into code - ability to analyse, to structure, to isolate - knowledge of patterns for solving problems (may include data structures, design patterns, coding principles, etc.) --- Referencing a spectrum of algorithmic quizzes and questions below, the level we usually seek in those wishing to [[join us]]: - the [[algorithmic mindset#Basic|basic]] quizzes should be easy for you to solve - you should have an idea on how to solve the [[algorithmic mindset#Intermediate|intermediate]] ones, while the first 3 should be relatively easy - the [[algorithmic mindset#Advanced|advanced]] ones are an overkill, but cool if you find them exciting These are just examples to elaborate what we mean by "algorithmic mindset" in the context of requirement for some of our vacancies. **You don't need to actually solve any of these, at least not for our sake :)** --- ## Basic ### A Stranger in the Dead End Street Read the function below, explain its purpose and simplify the implementation. ```python def ensure(a, b): """ A strange function. Its behaviour requires explanation. :param a: natural number :param b: natural number :return: a number, but what it means? """ while a >= b: a -= b return a ``` ### River Bend Write a function than receives NxM matrix and rotates it clockwise. You can use numpy functions but not the `numpy.rot90` which does the thing. ```python def rot90(x): """ The function rotates NxM matrix clockwise. :param x: NxM matrix :return: rotated matrix """ return x ``` ## Intermediate ### Solitude of Sand You have an array of natural numbers. We know that all numbers have pairs except one. Write a function that returns that number. Note that numbers in different pairs may coincide. For example `[1, 2, 1, 2, 1]` is a correct sequence as well as `[1, 1, 1, 1, 1]`. Is it possible to create a `O(1)` solution for this problem? ```python def find_singleton_number(xs): """ :param xs: list of of natural numbers where all numbers has a pair except some one poor solitary number :return: number that has only one occurrence in specified array """ pass ``` ### Chaotic Islands Given a function random() which returns a random value in `[0,1)`, write a function that shuffles a list of items. The solution should have a linear complexity. ```python def shuffle(xs): """ Receives a list of xs and returns it's shuffled version :param xs: a list of anything :return: shuffled version of xs """ ys = xs.copy() # Your implementation return ys ``` ### The Case on a River Bank Describe what the following function does. ```python def wat_function(n): """ This function definitely do something. But what? :param n: natural number :return: integer """ assert n < 0, "Wrong input value: " + n if n < 2: return n else: return wat_function(n-1) + wat_function(n-2) ``` What will happen if we would try to pass 100 as an argument? What is the complexity of this solution? Do you see a way to improve it? ### Tehran Ornament From the school algebra we know that the set of rational numbers is dense. Which means that between any rationals `a` and `b` there is always a rational `n`. Actually, there is infinite rationals between any `a` and `b`. However, there is a famous proof that shows the sets of natural rational numbers have the same cardinality. That means it is possible to create (an infinite) list of rational numbers (the argument concerns positive rationals but it is easy to show that **R**+ have the same cardinality as all rationals **R**). The idea is the following: the first row of the table consists of `[1, 2, 3, ...]`, the second `[1/2, 2/2, 3/2, ...]` and so on: | | **1** | **2** | **3** | **4** | | ----- | ----- | ----- | ----- | ----- | | **1** | 1 | 2 | 3 | 4 | | **2** | 1/2 | 2/2 | 3/2 | 4/2 | | **3** | 1/3 | 2/3 | 3/3 | 4/3 | | **4** | 1/4 | 2/4 | 3/4 | 4/4 | The list is created diagonally, e.g.: `[1, 2, 1/2, 1/3, 2/2, 3, ...]`: | | **1** | **2** | **3** | **4** | | ----- | ----- | ----- | ----- | ----- | | **1** | 1st | 2nd | 6th | 7th | | **2** | 3rd | 5th | 8th | 13th | | **3** | 4th | 9th | 12th | ... | | **4** | 10th | 11th | ... | ... | Write a function which calculates position of a positive rational number in the list (the number is specified as a pair of `numerator`/`denominator` of natural numbers). ```python def index_of_rational(n, d): """ Returns position of a rational number represented as n/d in the list of rationals. :param n: int natural number, numerator :param d: int natural number, denominator :return: position in the list """ return 0 ``` ## Advanced ### 1000 Streets of Samarkand Read about [adjacency matrix](https://www.wikiwand.com/en/Adjacency_matrix) and write a function that calculates the number of paths of length N from vertex A to vertex B of a given undirected graph. ```python def count_n_paths(graph, n, start, end): """ Returns amount of paths from vertex `start` to vertex `end` given a graph `graph`. :param graph: Graph graph to analyse :param n: int path length :param start: str vertex to depart :param end: str vertex to arrive :return: how many paths exists """ return 0 ``` Graph has the following structure: ```python class Graph: """ Structure which represents a graph. Example: g = Graph(['A', 'B', 'C'], [('A', 'B'), ('B', 'C'), ('C', 'A')]) # a triangle ABC """ def __init__(self, vertices, edges): """ Constructs a graph, takes care about integrity :param vertices {str} list of vertices :param edges {(str, str)} """ self.vertices = vertices.copy() self.edges = {tuple(sorted(e)) for e in edges} self.validate() def validate(self): for e in self.edges: for v in e: assert v in self.vertices, f'Vertex {v} of edge {e} is not in the list of vertices!' def __str__(self): return f'Graph(\n' \ f' vertices={self.vertices},\n' \ f' edges={self.edges}\n' \ f')' ``` ### The Proof of Serendipity Take a standard function that shuffles an array or use the function you wrote in the [[algorithmic mindset#Chaotic Islands|shuffle]] quiz and prove that it shuffles an array truly randomly. First you should stipulate the criteria and only then implement the solution. ### Colors of the Desert You have a 24bit RGB image and you have to reduce color palette to 8 colors. Search for optimal solutions, explain how they work and give a sketch of the algorithmic implementation.