A consolidated collection of resources for you to learn and understand algorithms and data structures easily.
A consolidated collection of resources for you to learn and understand algorithms and data structures easily.
It is difficult to find consolidated resources on algorithms. This repo hopes to gather resources to help one understand algorithms better to prepare for technical tests or simply to strengthen your foundation of computer science to help you become a better coder.
Contributions are more than welcome. I cant do everything myself, so I will need all the help I can get. To
If you are arent sure of how to create a pull request, view the pull request documentation.
Summaries of the algorithms topics:
What is P vs NP?
P vs NP is a notorious problem in algorithms and in Computer Science.
P stands for polynomial time (Polynomial time means that the complexity of the algorithm is O(n^k), where n is the size of your data (e. g. number of elements in a list to be sorted), and k is a constant).
NP stands for non-deterministic polynomial time.
NP-complete is a family of NP problems for which you know that if one of them had a polynomial solution then everyone of them has.
Problems can be divided into P problems, which are easily solved by computers, and NP problems are not easily solvable, but if you present a potential solution it’s easy to verify whether it’s correct or not.
Is P=NP and why do I need to care?
For the longest of time, people have been trying to prove that P=NP or otherwise. It is important that we pay attention to it because many NP problems are problems we want to solve, e.g. in circuit design or in other industrial design applications.
If it were proven that P = NP and the proof provided a specific polynomial time algorithm for an NP-complete problem, then because of the existing reduction proofs, we could immediately produce polynomial time algorithms for all our other NP problems.
Read more here:
Brute force method (Generate & Test) is simplest way to explore the space of solutions - it simply means to go through all solutions, however unlikely they may be, something which is not particularly elegant.
Divide and Conquer means to break down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly.
Examples:
What is DP?
DP or dynamic programming basically means to take our problem and somehow break it down into a reasonable number of subproblems so that we can use optimal solutions to the smaller subproblems to give us optimal solutions to the larger ones.
Read more:
Courses
Practice here:
Common interview questions:
Memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.
Read more here:
In greedy algorithm approach, it builds up a solution piece by piece, where the next piece that offers the most obvious and immediate benefit is chosen.
Algorithms which use the greedy approach:
Knapsack problem or the rucksack problem is part of dynamic programming and it is where given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
Read more here:
Practice here:
TODO
TODO
Introduction to linked lists/ Vectors vs. Linked List (13 minute video)
Link − Each link of a linked list can store a data called an element.
Next − Each link of a linked list contains a link to the next link called Next.
LinkedList − A Linked List contains the connection link to the first link called First.
Linked List contains a link element called first.
Each link carries a data field(s) and a link field called next.
Each link is linked with its next link using its next link.
Last link carries a link as null to mark the end of the list.
The linked lists have pointers to the next and the previous item unlike arrays.
Advs of Linked Lists
Disadvs of Linked Lists
Item navigation is forward only
Items can be navigated forward and backward
In a circular singly linked list, the last node of the list is made to point to the first node.
Common interview questions:
Practice here:
source: Stoimen.
Queues is a data structure which follows a First-In-First-Out (FIFO) or Last-In-Last-Out (LILO) methodology. One end is always used to insert data (enqueue) and the other is used to remove data (dequeue).
Practice here:
source: Stoimen.
Stacks is a data structure which follows a LIFO (last in, first out) methodology.
To insert an item, it is called “Push”, to remove an item off is called “Pop”.
Practice here:
Common interview questions for queues and stacks:
TODO
TODO
TODO
The Big O notation describes the complexity of an algorithm. It describes:
O(1)
Same time regardless of the size of the input data
Coding examples:
O(N)
Performance will grow linearly and in direct proportion to the size of the input data set.
Coding examples:
O(N)^2
Performance is directly proportional to the square of the size of the input data set. This is common with nested iterations over the data set.
These ones are supposed to be the less efficient algorithms if their O(n log n) counterparts are present.
Coding examples:
O(2N)
Performance doubles with each additon to the input data set. The growth curve of an O(2N) function is exponential.
Coding examples:
O(log n)
O(log n) is slightly more difficult to explain. One good example of a O(log n) problem is when searching up a phone book. Even if the phone book is thick, you would not need to search every name, but you just have to look for the name under the correct alphabet.
Reducing the problem size with every iteration
Coding examples:
O(n log n)
To better understand it, think of it as O(N) and O(log n). An example of such a notation is the Quick sort when we divide the array into two parts and each time it takes O(N) time to find a pivot element.
Coding examples:
It describes:
An example of Big O vs Big Omega of a problem: http://www.programmerinterview.com/index.php/data-structures/big-o-versus-big-omega-notations/
Common interview questions
Read more here
How does it work?
Assume we have an array of numbers which are arranged in sequence where we want to find out if the number, 17 is within the array.
[2, 3, 5, 7, 11, 13, 17, 19, 23]
Based on linear search, we have to start at index 0 and progressively go through each element in the array. That would take us 7 searches before we arrive at 17. However, based on binary search,
Set the minIndex and maxIndex - In this case, let minIndex = 0 and maxIndex = 8.
Set the middle element as the first guess - The first guess would be value 11, index 4 (since 8/4). Since the array is sorted, we know that if 17 exists, it would be on the right side of the array since 17>11.
Change the minIndex/maxIndex - We shift the minIndex to be 5 and maxIndex stays the same at 8.
Make another guess based on the new minIndex/maxIndex - Taking the average, our second guess would be at index (8+5)/2 = 6.5 ~ 6, with a value of 17. We have found our integer.
In conclusion:
Search | |
---|---|
Linear | 7 |
Binary | 2 |
Practice here:
Read more here
Common interview questions:
A red-black tree is a binary search tree.
Its properties:
Courses
TODO
TODO
This sorting algorithm is where each item is compared to adjacent items and is exchanged with those that are out of order. Simply put, each item “bubbles” up to the location where it belongs
Bubble sort in C :
This sorting algorithm is where a list of numbers is divided into two parts, the sorted part at the left end and the unsorted part at the right end. Initially, the list is unsorted.
Read more here:
A sorting algorithm which uses divide-and-conquer.
How it works?
Pick a pivot - Given an unsorted list of numbers, pick an element in the list as a pivot
Partitioning - Rearrange the elements so that all other elements in the list that are less than or equal to the pivot are to its left and all elements in the list are to the pivot's right
Recursively sort - Recursively sort the elements to the left of the pivot, which must be less than or equal to the pivot) and the elements to the right of the pivot, which must be greater than the pivot
Read more here
Practice here:
How it works?
Continuously split the whole list into equal halves until atomic values are achieved and it can no longer be divided. If the list is empty or has one item, it is sorted by definition (the base case).
Merge the smaller lists into a new list in sorted order
Source: Tutorialspoint
Practice here
TODO
TODO
TODO
I myself have learnt a lot while compiling these resources. Thanks to:
Inspired by: https://github.com/donnemartin/system-design-primer#step-1-review-the-scalability-video-lecture
I would really like to learn from you, so contact me for any issues or questions or ideas. My github page is here and my email is [email protected]
Creative Commons Attribution 4.0 International License (CC BY 4.0)
http://creativecommons.org/licenses/by/4.0/