Insertion Sort is another simple sort algorithm that works with sorted and unsorted parts of an array. Values from unsorted part picked and placed to correct position in sorted part.

## Example1

## Example 2

[4 | `3` 2 10 12 1 4 6] -> [`3` 4 | 2 10 12 1 4 6]

[3 4 | `2` 10 12 1 4 6] -> [`2` 3 4 | 10 12 1 4 6]

[2 3 4 | `10` 12 1 4 6]-> [2 3 4 `10` | 12 1 4 6]

[2 3 4 10 | `12` 1 4 6] -> [2 3 4 10 `12` | 1 4 6]

[2 3 4 10 12 | `1` 4 6] -> [`1` 2 3 4 10 12 | 4 6]

[1 2 3 4 10 12 | `4` 6] -> [1 2 3 4 `4` 10 12 | 6]

[1 2 3 4 4 10 12 | `6`] -> [1 2 3 4 4 `6` 10 12]

*Time complexity* is O(N^2), because each next element of an unsorted part iterates through elements of the sorted part. There are two nested loops in the algorithm.

*Space complexity*: O(1).

def insertionSort(arr):
  
  # Iterate unsorted subarrays
  for i in range(1, len(arr)):
    key = arr[i] # Element to move
    j = i-1

    # Iterate sorted part and replace elements one position right
    while j>=0 and key < arr[j]: 
      arr[j+1] = arr[j]
      j-=1

    # Put key element on its position
    arr[j+1]= key
  return arr

Sorting is one of the main topics on Tech Interviews. There are a lot of different sorting algorithms that differ by time and space complexity and approaches. In this mini-course, we’ll take a look through the most popular and relevant of them. Then6 you'll try to solve some Interview problems.

Some useful info about algorithms. You'll familiarize yourself with the popular algorithms for beginners.

More advanced, but commonly used algorithms.

Try to solve interview problems using Sorting Algorithms!

Bill studies in a school and he adores Maths. His class has been studying arithmetic expressions. On the last class the teacher wrote three positive integers `a`, `b`, `c` on the blackboard. The task was to insert signs of operations `+` and `*`, and probably brackets between the numbers so that the value of the resulting expression is as large as possible.

Possible variants:
- **a+b\*c=v1**
- **a\*(b+c)=v2**
- **a\*b\*c=v3**
- **(a+b)\*c=v4**

Note that you can insert operation signs only between `a` and `b`, and between `b` and `c`, that is, you cannot swap integers. For instance, in the given sample you cannot get expression **(a+c)\*b**.

Given an integers `a`, `b` and `c`. Return **maximum value of the expression** that you can obtain.

Bob likes to play his game on paper. He writes `n` integers **a1, a2, ..., an**. Each of those integers can be either `0` or `1`. He's allowed to do exactly one move: he chooses two indices `i` and `j` **(1 ≤ i ≤ j ≤ n)** and flips all values `ak` for which their positions are in range `[i, j]` **(that is i ≤ k ≤ j)**. Flip the value of `ak` means to apply operation **ak = 1 - ak**.

The goal of the game is that after exactly one move to obtain **the maximum number of ones**.

Given a list of `0` or `1`. Return **the maximal number of 1s** that can be obtained after exactly one move.

Bob has three sisters: Ann, Bella, and Caroline. They're collecting coins. Currently, Ann has `a` coins, Bella has `b` coins and Caroline has `c` coins. Recently Bob has returned from the trip around the world and brought `n` coins.

He wants to distribute all these `n` coins between his sisters in such a way that the number of coins Ann has is equal to the number of coins Bella has and is equal to the number of coins Caroline has. In other words, if Bob gives `A` coins to Ann, `B` coins to Bella and `C` coins to Caroline **A+B+C=n**, then **a+A=b+B=c+C**

Note that `A`, `B` or `C` (the number of coins Bob gives to Ann, Bella and Caroline correspondingly) can be 0. Help Bob to find out if it is possible to distribute all `n` coins between sisters in a way described above.

Given an integers `a` - the number of coins Ann has , `b` - number of coins Bella has, `c` - number of coins Caroline has and `n` - the number of coins Bob has. Return `YES` if Bob can distribute all `n` coins between his sisters and `NO` in the opposite case.

Bob has recently started commuting by bus. We know that a one bus ride ticket costs `a` dollars. Besides, Bob found out that he can buy a special ticket for `m` rides, also he can buy it several times. It costs `b` dollars. Bob will need to use bus `n` times. Help Bob to calculate what is **the minimum sum of money** he will have to spend to make `n` rides?

Bill decided to visit his friend. It turned out that the Bill's house is located at point 0 and his friend's house is located at point `x` **(x > 0)** of the coordinate line. In one step Bill can move `1`, `2`, `3`, `4` or `5` positions forward.

Given integer `x`, return **the minimum number of steps** Bill needs to make in order to get to his friend's house.

Given two integers `x` and `y`, return a list of integers: the first being the **minimum** of `x` and `y`, and the second being the **maximum** of `x` and `y`.

Given three digits `a`, `b`, `c`, where two of them are equal and one is different, return the value that occurs exactly once.

Given a ticket string consisting of **six digits**, return `YES` if its lucky and `NO` in the opposite case. A ticket is considered lucky if the sum of the first three digits is equal to the sum of the last three digits, even when there are leading zeroes.

Given three integers `a`, `b`, and `c`, return `+` if the equation `a + b = c` is true, and `-` if the equation `a - b = c` is true

Given an integer `n`, return **the number of ordered pairs** of positive integers (a, b) such that `a = n - b`, where both `a` and `b` are positive integers.

Given a binary array consisting of only 0s and 1s, return the length of the longest segment of consecutive 0s (also referred to as a blank space) in the array.

Given a string as `a+b` expression, where `a` and `b` are integers, return a sum of `a` and `b` as an integer.

Given an integer `n`, return the last two digits of the number 5 raised to the power of `n`. Note that `n` can be rather large, so direct computation may not be feasible. The task requires an efficient approach to solve the problem.

Given a list of integers and a threshold integer, return a sum of numbers, where each number contributes `2` if it exceeds or equals the threshold and `1` otherwise.

Given an integers `a` and `b`, return a count of numbers that each have no repeated digits.

Bear Bill wants to become the largest of bears, or at least to become larger than his brother Bob. Right now, Bill and Bob weigh `a` and `b` respectively. It's guaranteed that Bill's weight is **smaller than or equal** to his brother's weight. Bill eats a lot and his weight is **tripled** after every year, while Bob's weight is **doubled** after every year.
After how many full years will Bill become strictly heavier than Bob?

Given an integer `a` and an integer `b`, return the smallest integer `n` such that if `a` is tripled `n` times and `b` is doubled `n` times, `a` exceeds `b`.

Given an `array of three arrays of triples of integers`, return `the missing triple of integers` to make them all add up to `0 coordinatewise`

Given an array of operations `++x`, `x++`, `--x`. `x--` and an integer `target`, return an initial integer, so that the final value is the target value.

Given an alphabetic string `s`, return a string where removed all vowels and inserted a `.` before each remaining letter, and make everything lowercase.

Vowels are letters `A`, `O`, `Y`, `E`, `U`, `I`, and the rest are consonants.

Given an array of integers `nums` and an integer `k`, return an amount of integers in array are larger than the `k`.

Given an integer `n`, determine how many integers `x` (where 1 ≤ x ≤ n) are interesting. An integer `x` is considered interesting if the sum of its digits decreases when incremented by 1, i.e., S(x+1) < S(x), where S(x) represents the sum of the digits of `x` in the decimal system.

Your task is to count how many such interesting numbers exist within the given range.

A string consisting only of the characters `b`, `d` and `w` is painted on a glass window of a store. Alex walks past the store, standing directly in front of the glass window, and observes string `s`. Alex then heads inside the store, looks directly at the same glass window, and observes string  `r`.

Alex gives you string `s`. Your task is to find and output string `r`.

The price of one tomato at grocery-store is `a` dollars, but there is a promotion where you can buy two tomatoes for `b` dollars. Bob needs to buy exactly `n` tomatoes. When buying two tomatoes, he can choose to buy them at the regular price or at the promotion price.

What is the minimum amount of dollars Bob should spend to buy `n` tomatoes?

Bill has found a set. The set consists of small English letters. Bill carefully wrote out all the letters from the set in one line, separated by a comma. He also added an opening curved bracket at the beginning of the line and a closing curved bracket at the end of the line. Unfortunately, from time to time Bill would forget writing some letter and write it again. Help Bill to count the total number of distinct letters in his set.

Given a string of set format `set_str`, return an integer of total number of distinct letters from set.

Bill keeps his most treasured savings in a home safe with a combination lock. The combination lock is represented by `n` rotating disks with digits from `0` to `9` written on them. Bill has to turn some disks so that the combination of digits on the disks forms a secret combination. In one move, he can rotate one disk one digit forwards or backwards. In particular, in one move he can go from digit `0` to digit `9` and vice versa. What minimum number of actions does he need for that?

Given an integer `original` and an integer of final code combination `target`, return an integer of the minimum number of moves Bill needs to open the lock

There is a game called **Mario Adventures**, consisting of `n` levels. Bill and his friend Bob are addicted to the game. Each of them wants to pass the whole game. Bill can complete certain levels on his own and Bob can complete certain levels on his own. If they combine their skills, can they complete all levels together?

Given an integer `n` - the total number of levels, list of integers `bill_levels`  - the number of levels Bill can complete and Another list of integers `bob_levels` - the number of levels Bob can complete. Return string `I become the hero!` If they can complete all levels together, in the opposite case `Oh, no! The castle is locked!`

Bill and Bob have recently joined the Codefinity University for Cool Engineers. They are now moving into a dormitory and want to share the same room. The dormitory has `n` rooms in total. Each room has a current occupancy and a maximum capacity. Your task is to determine how many rooms have enough space for both Bill and Bob to move in.

Given a list of `n` sublists, where each sublist contains two integers `c` (number of people currently living in the room) and `m` (room's maximum capacity), return the number of rooms where Bill and Bob can move in together.

Liam enjoys playing chess, and so does his friend Noah. One day, they played `n` games in a row. For each game, it is known who the winner was—Liam or Noah. None of the games ended in a tie.

#### Now Liam is curious to know who won more games - him or Noah. Can you help him find out?

Given a string `s`, consisting of uppercase English letters `L` and `N` — the outcome of each of the games. The i-th character of the string is equal to `L` if the Liam won the i-th game and `N` if Noah won the i-th game, return a string with `Noah` If Noah won more games than Liam and `Liam` in the opposite case. If Noah and Liam won the same number of games, return `Friendship`

Alex loves lucky numbers. Help him find out if the given number `n` is lucky, return `YES` if its lucky and `NO` in the opposite case. Lucky numbers are positive integers that contain only the digits `4` and `7` in their decimal representation.

For example, numbers like 47, 744, and 4 are lucky, while numbers like 5, 17, and 467 are not.

A young girl named Emily is learning how to subtract one from a number, but she has a unique way of doing it when the number has two or more digits.

#### Emily follows these steps:
- If the last digit of the number is not zero, she simply subtracts one from the number.
- If the last digit of the number is zero, she divides the number by 10 (effectively removing the last digit).

You are given an integer number `n`. Emily will perform this subtraction process `k` times. Your task is to determine the final result after all `k` subtractions. It is guaranteed that the result will always be a positive integer.

Jane, a budding mathematician and a second-grade student, is learning how to perform addition. Her teacher wrote down a sum of several numbers on the board, and the students were asked to calculate the total. To keep things simple, the sum only includes the numbers `1`, `2`, and `3`. However, Jane is still getting the hang of addition, so she can only calculate the sum if the numbers are arranged in non-decreasing order (i.e., each number is greater than or equal to the one before it). For example, she cannot compute a sum like `2+1+3+2`, but she can handle sums like `1+2+2+3`.

Your task is to rearrange the numbers in the given sum so that Sophia can compute it.

One day three best friends Bill, Bob, and Jane decided to form a team and take part in programming contests. During these contests, participants are typically given several problems to solve.

#### Before the competition began, the friends agreed on a rule:

They would only attempt to solve a problem if at least two of them were confident in their solution. Otherwise, they would skip that problem.

For each problem, it is known which of the friends are sure about the solution. Your task is to help the friends determine the number of problems they will attempt to solve based on their rule.

Given a list of lists of triples of integers `1` or `0`. If the first number in the line equals 1, then Bill is sure about the problem's solution, otherwise he isn't sure. The second number shows Bob’s view on the solution, the third number shows Jane’s view. Return an **integer** - the number of problems the friends will implement on the contest.

Sometimes, certain words like `optimization` or `kubernetes` are so lengthy that writing them repeatedly in a single text becomes quite tedious.

Let’s define a word as too long if its length is strictly greater than **7 characters**. All such words should be replaced with a special abbreviation.

#### The abbreviation is created as follows:

Write the first and last letter of the word, and between them, insert the number of letters that appear between the first and last letters. This number is written in decimal format and should not contain any leading zeros.

Your task is to automate the process of abbreviating words. Replace all too long words with their abbreviations, while leaving shorter words unchanged.

One cozy afternoon, Lily and her friend Noah decided to buy a large cake from their favorite bakery. They chose the most decadent one, layered with rich frosting and fresh berries. After purchasing, the cake was weighed, showing a total weight of `n` grams. Excited to share it, they hurried home but soon realized they faced a tricky problem.

Lily and Noah are big fans of even numbers, so they want to divide the cake in such a way that each of the two portions weighs an even number of grams. The portions don’t need to be equal, but each must have a positive weight. Since they’re both tired and eager to enjoy the cake, you need to help them determine if it’s possible to split it the way they want.

Given an integer number `n` - the weight of cake bought by Lily and Noah, return a string `YES`, if Lily and Noah can divide the cake into two parts, each of them weighing an even number of grams and `NO` in the opposite case.

The ternary numeric system is commonly used in Codeland, and to represent ternary numbers, the Tick alphabet is employed. In this system, the digit 0 is represented by `.`, 1 by `-.`, and 2 by `--`. Your task is to decode a Tick-encoded string and determine the corresponding ternary number.

Bill is excited about the transition from the year 2020 to 2021 and wants to represent a given number `n` as a sum of some number of 2020s and some number of 2021s.

Given an integer `n`, return `YES` if the number n is representable as the sum of a certain number of 2020 and a certain number of 2021 and `NO` in otherwise.

A positive integer `n` is called ordinary if all its digits in decimal notation are the same. For example, 1, 2, and 99 are ordinary numbers, while 719 and 2021 are not.

Given a number `n`, count how many ordinary numbers exist between 1 and n.

You have gifts, and each gift contains a certain number of candies and oranges. Your goal is to make all gifts identical in terms of the number of candies and oranges.
You are allowed to perform the following operations on any gift:
- Remove one candy.
- Remove one orange.
- Remove one candy and one orange at the same time.
- You cannot remove more than what is available in a gift (no negative values).

After performing some moves, all gifts must have the same number of candies and the same number of oranges (though candies and oranges do not need to be equal to each other).
Your task is to find the **minimum number** of moves required to achieve this.

Groups of schoolchildren wants to visit Circus after their lessons. Each group consists of a certain number of children (between 1 and 4), and all children in a group must travel together in the same taxi. Each taxi can hold up to four passengers, and multiple groups can share a taxi as long as the capacity allows.
Find the **minimum number of taxis** needed to transport all the children without splitting any group.

We know that prime numbers are positive integers that have exactly two distinct positive divisors. Similarly, we define a positive integer `t` as a T-prime if it has exactly three distinct positive divisors.

Given an array of positive integers, return an array of `True` or `False` for each integer if it T-prime

Megabyte attempted to take control of Hexadecimal by loading `n` different natural numbers (ranging from 1 to n) into her memory. However, Hexadecimal only recognizes numbers written entirely in binary (containing only the digits 0 and 1). Any number with other digits was ignored. Now, Megabyte wants to determine how many numbers were successfully stored in her memory.

The Codefinity University is hosting a ballroom dance in celebration of its anniversary! `n` boys and `m` girls are already busy. We know that several boy and girl pairs are going to be invited to the ball. However, the partners' dancing skill in each pair must differ by at most one. For each boy, we know his dancing skills. Similarly, for each girl we know her dancing skills.

Given an array of boys with dancing skill and array of girls with dancing skills, return the largest possible number of pairs that can be bormed from boys and girls.

You have a 5x5 matrix consisting of 24 zeroes and a single number one. The matrix is indexed with rows from 1 to 5 (top to bottom) and columns from 1 to 5 (left to right). In one move, you can apply one of the two following transformations to the matrix:
- Swap two neighboring rows (i.e., rows with indices `i` and `i+1` for some integer `i`, where 1 ≤ i < 5).
- Swap two neighboring columns (i.e., columns with indices `j` and `j+1` for some integer `j`, where 1 ≤ j < 5).

You consider the matrix beautiful if the number one is located in the center of the matrix, at the intersection of the third row and the third column.
Given a matrix, return the **minimum number of moves** needed to make the matrix beautiful.

You are given an integer `n`. In one move, you can either:
Multiply `n` by 2, or Divide `n` by 6 (only if it is divisible by 6 without a remainder).
Return the **minimum number of moves** needed to obtain 1 from `n`, or return -1 if it's impossible to do so.

Bob enjoys relaxing after a long day of work. Like many programmers, he's a fan of the famous drink *Fantastic*, which is sold at various stores around the city. The price of one bottle in store `i` is `xi` coins. Bob plans to buy the drink for `q` consecutive days, and for each day, he knows he will have `mi` coins to spend. On each day, Bob wants to know how many different stores he can afford to buy the drink from.

You are given two arrays:
- An array of prices in the shops: `prices = [x1, x2, x3, ..., xn]` where each `xi` is the price of one bottle in store `i`.
- An array of coins Bob can spend each day: `coins = [m1, m2, m3, ..., mq]` where each `mi` represents the coins Bob can spend on the `i-th` day.

Return **number of shops** where Bob will be able to buy a bottle of the drink on the `i-th` day.

You are given a team of athletes, each with a specific strength, numbered from 1 to n. Your goal is to divide these athletes into two teams, ensuring that each team contains at least one athlete and that each athlete belongs to only one team.

The objective is to split the athletes in such a way that the difference between the strongest athlete in the first team and the weakest athlete in the second team is as small as possible. In other words, you want to minimize the absolute difference between the **maximum strength** in the first team **(max(A))** and the **minimum strength** in the second team **(min(B))**.

Your task is to find and print the minimum value of |max(A) - min(B)|.

Bill and Jack received cookies from their parents. Each cookie weighs either `1` gram or `2` grams. Now they want to divide all cookies among themselves fairly so that the total weight of Bill's cookies is equal to the total weight of Jack's cookies. Help them to check if they can do that. Note that cookies are not allowed to be cut in half.

You are given an array of integers where each integer represents the weight of a cookie. The weight can either be `1` gram or `2` grams. Return `YES` if all cookies can be divided into two sets with the same weight and `NO` in the opposite case.

Bob discovered a peculiar device with a green button, a purple button, and a display showing a positive integer. Pressing the green button **doubles** the number on the display, while pressing the purple button **subtracts** one from it. If the number becomes non-positive at any point, the device will break. The display is capable of showing very large numbers. Initially, the display shows the number `n`. Bill wants to transform the number on the display to `m`.

Given integers `n` and `m`, return a minimum number of button presses required to transform number `n` to `m`.

Alex loves lucky numbers. Lucky numbers are positive integers that contain only the digits `4` and `7` in their decimal representation.

For example, numbers like 47, 744, and 4 are lucky, while numbers like 5, 17, and 467 are not.

Alex calls a number almost lucky if it could be evenly divided by some lucky number. Help him find out if the given number `n` is almost lucky, return `YES` if its almost lucky and `NO` in the opposite case.

Bob has an array of `n` elements, where each element is an integer between `1 and n`. He has recently learned about permutations and their lexicographical order. Now, he wants to modify (replace) the fewest number of elements in his array to transform it into a valid permutation, where every integer from `1 to n` appears exactly once. If there are multiple ways to achieve this, Bob prefers the lexicographically smallest permutation.

To summarize, his goal is to:
- Minimize the number of changes needed to turn the array into a valid permutation.
- Among the possible valid permutations, choose the lexicographically smallest one.

When comparing two permutations to determine which is lexicographically smaller, we first compare their first elements. If those are equal, we compare the second elements, and so on. A permutation `x` is considered lexicographically smaller than permutation `y` if, at the first position where they differ, the element in `x` is smaller than in `y`.

Return an array of the lexicographically minimal permutation which can be obtained from array with minimum changes

You have the ability to accurately predict the price of a specific stock for the next `N` days. Your goal is to maximize your profit using this information, but you're restricted to performing only one transaction per day: buying one share, selling one share, or doing nothing. At the start, you don't own any shares, and you can only sell shares if you own them. By the end of the `N` days, you must again own zero shares, and your objective is to achieve the highest possible profit.

You are given an array of non-negative integers `[a1, a2, ..., an}]`.
In each step, you choose two elements x and y from the an array, remove them, and insert their mean value (x + y) / 2 back into the array.
This process continues until only two numbers, `A` and `B`, remain. Your goal is to determine the maximum possible absolute difference `|A - B|`.
Since the answer is not necessarily an integer, output the result modulo `10^9 + 7`.

Bill has a sentence with `n` words and wants to compress it into a single word. To do this, he merges words from left to right. When merging two words, he removes the longest prefix of the second word that matches a suffix of the first word. For example, merging `sample` and `please` results in `samplease`
Given a sentence string. Each word consists of uppercase and lowercase English letters and digits. Return final compressed string.

Clock angle problems relate two different measurements: angles and time. The angle is typically measured in degrees from the mark of number 12 clockwise. The time is usually based on a 12-hour clock.
Find clock hands = `[hour, min]` such that the angle is `target_angle` degrees.

The Tower of Hanoi is a mathematical puzzle consisting of three rods and a set of disks of varying sizes, initially stacked in decreasing order on one rod, forming a conical shape. The objective is to move the entire stack from the first rod to the last while following these rules:
- Only one disk may be moved at a time.
- Each move involves taking the top disk from one rod and placing it on another rod or an empty rod.
- No disk may be placed on top of a smaller disk.

Given a setup with eight disks (sizes 1-8) stacked on three rods (indexed as 0, 1, and 2), where each rod maintains a sorted order from largest at the bottom to smallest at the top, find a sequence of moves `[i, j]` where `i` is the index of the rod from which the smallest disk is taken, and `j` is the index of the rod where it is placed, ensuring all moves remain valid.

Sorting Algorithms

Insertion Sort

Example1

Example 2

Løsning

Insertion Sort

Example1

Example 2

Løsning