Different algorithms and data structure challenges from Codility, interviewcake I usually create a PR for each solution I add to the repo. Check the closed PRs sections for more details on my implementation process and what I learnt/discovered through each exercise.
- Merge meeting intervals
- Reverse string in place
- Reverse words in place in an array of chars
- Merge sorted Arrays
- Merge multiple sorted arrays
- First-come-first-served-checker - associated PR
Solutions comprised only of link to report on codility to respect Codility's copyright policy.
Lesson 1
Lesson 2
- cyclic-rotation -PR for solution
Recursion
- flatten array of unkown nesting level - associated PR
- reverse string - associated PR
- count-vowels - associated PR
- Find index of first occurrence of number - associated PR
- Fibonacci with memoized values - associated PR
- Greatest common divisor - associated PR
- Pascal Triangle - associated PR
- Sort Binary Search Tree - associated PR
- Toeplitz Matrix - associated PR
- Drone Flight Planner - associated PR
Big O notation is used to estimate how much runtime and space certain algorithms use relative to the input
A O(1) space complexity means only a single value is stored in memory throughout the algorithm's lifecycle A O(n) space complexity means n values are stored in memory throughout the algorithm's lifecycle
A O(n^2) runtime complexity means the runtime grows on the order of the square of the size of the input. This happens when you loop twice within an array for example
function printAllPossibleOrderedPairs(items) {
items.forEach(firstItem => {
items.forEach(secondItem => {
console.log(firstItem, secondItem);
});
});
}
An algorithm can have a worse case runtime complexity of O(n) and a best case of O(1) depending on how the data is structured. For example finding the max value in an already sorted array is a lot faster than having to find it in an unsorted array.
Similarly, you can also make statements about "average case" space and runtime complexity.
Generally, time and space have an inversely proportional relationship with each other; if space increases then execution time decreases, and if execution time increases then space decreases.
Logarithms in computer science refer usually to base 2 logarithms and help us respond to two questions:
- how many times do we have to add 2 to get to n
- how many times do we have to divide n by 2 to get to 1
Can be found in:
- binary search: O(log(n))
- merge sort: O(nlog(n)) best worse case runtime
- finding the height (number of levels) of a binary tree: O(log(n+1))
n is the number of elements
Can be:
- Fixed size
- Dynamic
Pros đź‘Ť
- Fast lookups: O(1) to get element at given index
- Cache friendly: elements are stored next to each other in memory
Cons đź‘Ž
- Slow worst-case appends: O(n^2) as the array expands whole blocks of elements might require to be moved around
- Costly inserts and deletes: O(n^2) because of elements being next to each other, they all need to be moved on insertion and deletions
This cost is nevertheless amortized thanks to the fast lookup
Consists in solving a problem by choosing a local optimal that will lead to an optimal global solution.
Can be applied in problems like:
-
change register: Calculating the change to give to someone using as few coins as possible : take the highest-value coin you could. A quarter, another quarter, then a dime, a nickel, and finally two pennies
-
Trying to fit as many overlapping meetings as possible in a conference room. At each step, schedule the meeting that ends earliest.
-
Looking for a minimum spanning tree in a graph. At each step, greedily pick the cheapest edge that reaches a new vertex.
Can give bad results when trying to:
- fill a duffel bag with cakes of different weights and values
- find the cheapest route visiting a set of cities, visiting the cheapest city doesn't amount to the cheapest intinerary overall
It's a series of numbers where each number could be the row of an equilateral triangle.
Properties
- Pairs of numbers on each side will always add up to the same value.
- That value will always be 1 more than the series’ n.
If you know the sum of a triangular series, you can find n by solving a quadratic equation.
If you know n, you can easily find the sum with the series sum formula above
Interview Cake - Tutorials and exercise practice with solutions
Codility - Tutorials and exercise practice without solutions (tests your solution for edge cases and runtime and space performance)
GeeksForGeeks - Interview Prep exercises and solutions
Educative.io - Algorithms, Design Systems and Programming Interview Tutorials
- Big-O Notation For Coding Interviews and Beyond
- Mastering Data Structures and Sorting Algorithms in JavaScript
- Recursion for Coding Interviews in JavaScript
Hackerrank - Practice, Certificates, Competitions
LeetCode - Practice, Certificates, Competitions
Introduction to Data Structures for Interviews
A Practical Guide to Algorithms with JavaScript
Pramp - Live interview practice with pears
- How to approach solving algorithms
Details these problem solving framework:
- Understand
- Plan
- Divide
- Stuck ? Debug, Research
- Practice
- Algorithms and data structures study plan
" The first requisite for success is the ability to apply your physical and mental energies to one problem incessantly without growing weary. " Thomas A. Edison
" The secret of success is constancy to purpose. " Benjamin Disraeli
" Most of the shadows of life are caused by standing in our own sunshine. " Ralph Waldo Emerson
" When you doubt your power, you give power to your doubt. " Honore de Balzac
- NodeJS: >=10
- Yarn: v1.22.0
To run any of the javascript solution exercises:
- Clone this repo
- Open a terminal command and run
yarnin the root folder Cdinto the directory where the file you want to run is and runnode file_name.js. This will run the associated tests for that file.
Test data can be found in the testData/index.js folder for each exercise category subfolder
- run
npm run testin the root of the repo
-
If you'd like to make suggestions or ask questions around some of the solutions, please feel free to open an Issue. I'll reply to all of them.
-
Star the repo to receive notifications when I add new solutions, notes and PRs to the repo.
-
Share this repo in your network if you think someone might find it useful.