Common Time Complexities
| Name | Running Time: T(n) | Example |
|---|---|---|
| Constant | O(1) | Finding the median value in a list of sorted numbers |
| Logarithmic | O(log n) | Binary search |
| Linear | O(n) | Min / Max in an unsorted array |
| Polynomial | O(n2), O(n3) | Bubble sort, Naive matrix multiplication |
| Exponential | 2O(n), 2O(n2) | Traveling salesman using DP |
| Factorial | O(n!) | Traveling salesman using brute-force search |
Note: snippets of code are not intended to reflect the exact and complete FCL implementation but to give you the gist of common implementations.
Often provided out of the box in most languages with the <Type of the array items>[] syntax, including C#.
Note: arrays can also be jagged or mutlidimensional.
C# Example
// Declare and define an array of 42 int items
var array = new int[42];
// Get items at nth index
// Returns 0 for all items in the array
// since they have been initialized with:
// => default(<Type of the array items>)
// => default(int) = 0
var item0 = int[0];
var item40 = int[40];
// Set items at nth index
int[0] = -42;
int[35] = 42;
// Since arrays in C# are fully OO, their length is provided out of the box too
// Array length cannot be changed, it's fixed
// Resizing requires reallocation of a given size + copy of items
// Returns 42
var length = array.Length;All dimensions are the same, a cube is a 3D mutlidimensional array.
C# Example
// Two-dimensional array.
var array2D = new int[,] { { 1, 2 }, { 3, 4 }, { 5, 6 }, { 7, 8 } };
// The same array with dimensions specified.
var array2Da = new int[4, 2] { { 1, 2 }, { 3, 4 }, { 5, 6 }, { 7, 8 } };An array of arrays, elements of a jagged array can be of different dimensions and sizes.
C# Example
var jaggedArray = new int[3][,]
{
new int[,] { {1, 3}, {5, 7} },
new int[,] { {0, 2}, {4, 6}, {8, 10} },
new int[,] { {11, 22}, {99, 88}, {0, 9} }
};Otherwise a pointer * definition can also work out, even though it's strongly discouraged to resort to unsafe contexts.
C# Example
unsafe static void Main(string[] args)
{
// To pin the array, so that it won't get moved by the GC...
fixed (int* test = new int[10])
{
for (var i = 0; i < 10; i++)
{
test[i] = i * 10;
}
// Returns 50
var item5 = test[5];
var item5 = *(5 + test);
}
}LIFO (Last In First Out) DS
Note: The underlying storage can also be a linked list (instead of an array)
Common Operations:
T Peek(): get the last item that has been pushed (the one on the top of that stack)T Pop(): remove and return the item on the top of that stackvoid Push(T item): push an item onto the top of that stack
C# Partial Implementation
public class Stack<T> : IEnumerable<T>, ICollection, IReadOnlyCollection<T>
{
private T[] _storage;
private int _size;
public Stack()
{
_storage = Array.Empty<T>();
}
// Pops an item from the top of the stack. If the stack is empty, Pop
// throws an InvalidOperationException.
public T Pop()
{
var size = _size - 1;
var storage = _storage;
if ((uint)size >= (uint)array.Length)
{
ThrowForEmptyStack();
}
_version++;
_size = size;
var item = _storage[size];
if (RuntimeHelpers.IsReferenceOrContainsReferences<T>())
{
// Free memory quicker.
storage[size] = default;
}
return item;
}
// Pushes an item to the top of the stack.
public void Push(T item)
{
var size = _size;
var storage = _storage;
if ((uint)size < (uint)storage.Length)
{
storage[size] = item;
_version++;
_size = size + 1;
}
else
{
PushWithResize(item);
}
}
// Non-inline from Stack.Push to improve its code quality as uncommon path
[MethodImpl(MethodImplOptions.NoInlining)]
private void PushWithResize(T item)
{
Array.Resize(ref _storage, (_storage.Length == 0) ? DefaultCapacity : 2 * _storage.Length);
_storage[_size] = item;
_version++;
_size++;
}
private void ThrowForEmptyStack()
{
Debug.Assert(_size == 0);
throw new InvalidOperationException(SR.InvalidOperation_EmptyStack);
}
}FIFO DS (Fist In First Out)
Note: Just like for the Stack The underlying storage can also be a linked list (instead of an array)
Common Operations:
T Peek(): get the first item that has been pushed (the one on the bottom of that queue)T Dequeue(): remove and return the item on the bottom of that queuevoid Enqueue(T item): enqueue an item onto the bottom of that queue
C# Partial Implementation
public class Queue<T> : IEnumerable<T>, ICollection, IReadOnlyCollection<T>
{
private const int MinimumGrow = 4;
// Double each time
private const int GrowFactor = 200;
private T[] _storage;
private int _size;
// The index from which to dequeue if the queue isn't empty
private int _head;
// The index at which to enqueue if the queue isn't full
private int _tail;
public Queue()
{
_storage = Array.Empty<T>();
}
// Adds item to the tail of the queue.
public void Enqueue(T item)
{
if (_size == _storage.Length)
{
var newCapacity = (int)((long)_storage.Length * (long)GrowFactor / 100);
if (newCapacity < _storage.Length + MinimumGrow)
{
newCapacity = _storage.Length + MinimumGrow;
}
SetCapacity(newCapacity);
}
_storage[_tail] = item;
MoveNext(ref _tail);
_size++;
_version++;
}
// Removes the object at the head of the queue and returns it. If the queue
// is empty, this method throws an
// InvalidOperationException.
public T Dequeue()
{
var head = _head;
var storage = _storage;
if (_size == 0)
{
ThrowForEmptyQueue();
}
var removed = storage[head];
if (RuntimeHelpers.IsReferenceOrContainsReferences<T>())
{
storage[head] = default;
}
MoveNext(ref _head);
_size--;
_version++;
return removed;
}
// Increments the index wrapping it if necessary.
private void MoveNext(ref int index)
{
// It is tempting to use the remainder operator here but it is actually much slower
// than a simple comparison and a rarely taken branch.
// JIT produces better code than with ternary operator ?:
var tmp = index + 1;
if (tmp == _storage.Length)
{
tmp = 0;
}
index = tmp;
}
// PRIVATE Grows or shrinks the buffer to hold capacity objects. Capacity
// must be >= _size.
private void SetCapacity(int capacity)
{
var newStorage = new T[capacity];
if (_size > 0)
{
if (_head < _tail)
{
Array.Copy(_storage, _head, newStorage, 0, _size);
}
else
{
Array.Copy(_storage, _head, newStorage, 0, _storage.Length - _head);
Array.Copy(_storage, 0, newStorage, _storage.Length - _head, _tail);
}
}
_storage_ = newStorage;
_head = 0;
_tail = (_size == capacity) ? 0 : _size;
_version++;
}
private void ThrowForEmptyQueue()
{
Debug.Assert(_size == 0);
throw new InvalidOperationException(SR.InvalidOperation_EmptyQueue);
}
}A (array) list is an array that resizes on items insertion.
C# Partial Implementation
public class List<T> : IList<T>, IList, IReadOnlyList<T>
{
private const int DefaultCapacity = 4;
private T[] _items;
private int _size;
private static readonly T[] s_emptyArray = new T[0];
public List()
{
_items = s_emptyArray;
}
// Adds the given object to the end of this list. The size of the list is
// increased by one. If required, the capacity of the list is doubled
// before adding the new element.
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void Add(T item)
{
_version++;
var items = _items;
var size = _size;
if ((uint)size < (uint)items.Length)
{
_size = size + 1;
items[size] = item;
}
else
{
AddWithResize(item);
}
}
// Non-inline from List.Add to improve its code quality as uncommon path
[MethodImpl(MethodImplOptions.NoInlining)]
private void AddWithResize(T item)
{
var size = _size;
EnsureCapacity(size + 1);
_size = size + 1;
_items[size] = item;
}
// Inserts an element into this list at a given index. The size of the list
// is increased by one. If required, the capacity of the list is doubled
// before inserting the new element.
public void Insert(int index, T item)
{
// Note that insertions at the end are legal.
if ((uint)index > (uint)_size)
{
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_ListInsert);
}
if (_size == _items.Length) EnsureCapacity(_size + 1);
if (index < _size)
{
Array.Copy(_items, index, _items, index + 1, _size - index);
}
_items[index] = item;
_size++;
_version++;
}
// Removes the element at the given index.
// The size of the list is decreased by one.
public bool Remove(T item)
{
var index = IndexOf(item);
if (index >= 0)
{
RemoveAt(index);
return true;
}
return false;
}
// Removes the element at the given index.
// The size of the list is decreased by one.
public void RemoveAt(int index)
{
if ((uint)index >= (uint)_size)
{
ThrowHelper.ThrowArgumentOutOfRange_IndexException();
}
_size--;
if (index < _size)
{
Array.Copy(_items, index + 1, _items, index, _size - index);
}
if (RuntimeHelpers.IsReferenceOrContainsReferences<T>())
{
_items[_size] = default;
}
_version++;
}
// Ensures that the capacity of this list is at least the given minimum
// value.
// If the current capacity of the list is less than min,
// the capacity is increased to twice the current capacity or to min,
// whichever is larger.
private void EnsureCapacity(int min)
{
if (_items.Length < min)
{
var newCapacity = _items.Length == 0 ?
DefaultCapacity :
_items.Length * 2;
// Allow the list to grow to maximum possible capacity (~2G elements) before encountering overflow.
// Note that this check works even when _items.Length overflowed thanks to the (uint) cast
if ((uint)newCapacity > Array.MaxArrayLength)
{
newCapacity = Array.MaxArrayLength;
}
if (newCapacity < min)
{
newCapacity = min;
}
Capacity = newCapacity;
}
}
}Unlike the array list
Copy-pasted from my SO answer.
The .NET Dictionary<TKey, TValue> is a generic (in the sense of the C# language feature) implementation of an hash table.
An hash table is simply an associative array, that is when you pass a pair of (key, value), then the key is used to compute a hash code which would help to compute the location (called a bucket) in an underlying storage array (called buckets) in which the pair and some other additional information will be saved. This is usually achieved by computing the modulo % of the hash code on the size of the array / buckets: hashCode % buckets.Length.
What if the hash code computed from our key is the same for another one, or worse a bunch of others keys and we end up on the same location? How do we manage those collisions? Well people obviously already thought about that decades ago and came up with essentially 2 main ways of solving collisions:
-
Separate Chaining: basically the pair are stored in a different storage than the buckets (often called entries), for example for each bucket (each index computed) we can have a list of entries which stores the different values which have been stored at the same "index" (due to the same hashcode), basically in case of collisions you have to iterate through the keys (and find another way, other than the hashcode to to distinguish them)
-
Open Addressing: everything is stored in the buckets and based on the first bucket found we check next , it also exist different schemes in the way to probe the values Linear Probing, Quadratic Probing, Double Hashing etc.)
Ok now let's look at how things are inserted in the .NET Dictionary<TKey, TValue> which boils down to go through code of the method below:
private void Insert(TKey key, TValue value, bool add)Note: after reading the insertion steps below, you can figure out the rationale behind deletion and lookup operations by inspecting the code given as a link in the sources.
There are two ways the hash code of the TKey key can be computed:
-
One relies on the default
IEqualityComparer<TKey>implementation comparer if you don't pass any as a parameter ofDictionary<TKey, TValue>which basically is generated byEqualityComparer<TKey>.Default(implementation available here), in case ofTKeybeing a type different from all the usual stuff (like primitives andstring) like a custom type, theIEqualityComparer<in TKey>will leverage the implementation (including the overrides) of:bool Equals(object obj)int GetHashCode()
-
The other, well, relies on the implementation of
IEqualityComparer<in TKey>you can pass to theDictionary<TKey, TValue>constructor.
The interface IEqualityComparer<in TKey> looks like that:
// The generic IEqualityComparer interface implements methods to if check two objects are equal
// and generate Hashcode for an object.
// It is use in Dictionary class.
public interface IEqualityComparer<in T>
{
bool Equals(T x, T y);
int GetHashCode(T obj);
}Either way, the dictionary ends up having a first hash code using the comparer: comparer.GetHashCode()
The hash code we got from our TKey key through the IEqualityComparer<in T> might be sometimes negative which is not really helpful if we want to get a positive index for an array...
What happens is that in order to get rid of negative values the Int32 hashcode got by the comparer.GetHashCode() is "ANDed" with the Int32.MaxValue (ie. 2147483647 or 0x7FFFFFFF) (in the sense of the boolean logic: bits):
var hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;The target bucket (the index) is obtained as follows:
var targetBucket = hashCode % buckets.LengthWill also see in a moment how the buckets array is resized.
The buckets (ie. int[]) is a private field of the Dictionary<TKey, TValue> containing the indexes of of the first related slot in the entries field which is Entry[], with Entry being a struct defined as follows:
private struct Entry
{
public int hashCode;
public int next;
public TKey key;
public TValue value;
}The key, value and hashcode are self-explanatory fields, regarding the next field, it basically indicates an index if there is another item in that chain (ie. several keys with the same hashcode), if that entry is the last item of a chain then the next field is set to -1.
Note: the hashCode field in the Entry struct is the one after negative value adjustment.
At that stage it is important to note that the behaviour differs depending on whether you are updating (add = false) or strictly inserting (add = true) a new value.
We will now check the entries related to the targetBucket starting with the first entry which is can be given by:
var entryIndex = buckets[targetBucket];
var firstEntry = entries[entryIndex];The actual (simplified) source code with comments
// Iterating through all the entries related to the targetBucket
for (var i = buckets[targetBucket]; i >= 0; i = entries[i].next)
{
// Checked if all
if (entries[i].hashCode == hashCode &&
comparer.Equals(entries[i].key, key))
{
// If update is not allowed
if (add)
{
// Argument Exception:
// "Item with Same Key has already been added" thrown =]
ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
}
// We update the entry value
entries[i].value = value;
// Modification while iterating check field
version++;
return;
}
}
Note: the `version` field is field also used in other common .NET data structures (eg. `List<T>`) that helps detecting while iterating (on `MoveNext()`) (and `throw` the related exception).The actual (simplified) source code with com ments
// The entries location in which the data will be inserted
var index = 0;
// The freeCount field indicates the number of holes / empty slotes available for insertions.
// Those available slots are the results of prior removal operations
if (freeCount > 0)
{
// The freeList field points to the first hole (ie. available slot) in the entries
index = freeList;
freeList = entries[index].next;
// The hole is no longer available
freeCount--;
}
else
{
// The entries array is full
// Need to resize it to make it bigger
if (count == entries.Length)
{
Resize();
targetBucket = hashCode % buckets.Length;
}
index = count;
count++;
}Note: the about `Resize()`` call:
- It double-ish the size of the underlying arrays (buckets and entries), like many others collections in order to avoid too many resize operations by providing ample space whenever the collection is resized.
- Double->>ish<< since the size can only be a prime number from a precomputed set of
Int32eg.3,7,11,17, ...,7199369since using a prime can reduce the number of collisions (see that answer on SO)
| DS |
|---|
| Array |
| Stack |
| Queue |
|
- Arrays
- Stack, Queue
- Lists (Linked [singly / doubly], Skip list)
- Hash Table
- Heaps
- Trees (BST, RBT, BT)
- Graphs
- Common Algorithms
- Factorial / Power / Fibonacci
- Pi computation using Monte Carlo
- Sorted arrays merge
- Sorting arrays:
- Quicksort
- Mergesort
- Timsort
- Heapsort
- Bubble Sort
- Insertion Sort
- Selection Sort
- Tree Sort
- Shell Sort
- Bucket Sort
- Radix Sort
- Counting Sort
- Cubesort
- Longest Activity Retrieval
- Trees: retrieval, searchs, traversal, balancing
- Graphs:
- MST
- Shortest Path
- A*, pathfinding
- Others:
- Permutation Generation: Heap's, Lexicographic
- Knap-sack
- Money Change
- Travel Salesman
(Some can be found illegally for free... just saying)
A few websites to practice:
It all about packing data and functions into a single component. The features of encapsulation are usually supported using classes in most object-oriented programming languages, although other alternatives also exist (e.g. structures). This pillar is also strongly related to the abstraction pillar which is more about data and operations hiding.
It is often translated as a language construct that facilitates the bundling of operations and data.
E.g. a class, struct, etc.
Encapsulation is not data hiding, but Encapsulation leads to data hiding
It is the process of exposing essential features of an entity while hiding other irrelevant details. Basically, only make data and / or operations publicly accessible when it DOES matter (see Abstraction), in order to achieve that purpose, most of the OO compliant languages provide the two functionalities below:
Most of the time, this is used through a language mechanism such as access modifiers.
E.g. public, protected, internal, private, etc.
Abstraction reduces code complexity and at the same time makes it aesthetically pleasant.
A language mechanism of code reuse (but not only!) through extensions based on a relevant existing entity.
E.g. the Pig class inherits from the Animal class:
Code Example
public abstract class Animal { }
public class Pig : Animal { }The ability of creating a new class from an existing class. Bear in Mind that this is not (only) for code-reuse purposes but first and foremost for the sake of having a meaningful hierarchy
The characteristic of being able to assign a different meaning or usage to something in different contexts, specifically, to allow an entity such as a variable, a function, or an object to have more than one form.
A polymorphic type is one whose operations can also be applied to values of some other type, or types.
E.g. the Pig and Cat classes may both have their own feature of "walking" just like their parent class Animal.
Code Example
public abstract class Animal
{
public abstract void Walk();
}
public class Pig : Animal
{
public override void Walk()
{
// Implementation goes here...
}
}
public class Cat : Animal
{
public override void Walk()
{
// Implementation goes here...
}
}Note: duck typing, generics and interfaces can also be used to describe polymorphism...
Let’s rephrase the former definition of polymorphism given in our previous answer in order to make it a little bit shorter:
The provision of a single interface to entities of different types.
It's important to note that a software entity can relate to different types of polymorphism (i.e. classes, methods, attributes, etc.), such as:
Aka function / method overloading, different functions arguments (and thus different prototypes for the same function name) lead to different specific behaviors.
Generics, allow function or data type to handle data uniformly without depending on their types.
The translation consequence of Liskov Substitution Principle) also called inclusion polymorphism: when a name denotes instances of many different classes related by some common superclass.
The different types above must not be confused with the kind of implementation aspect listed below (i.e. when the implementation is selected):
Method overloading (determine at the compilation, which method is linked to the call), also called "ad hoc polymorphism" (since it is clearly related to).
Aka subtyping which is mostly about methods overriding (determined at the runtime), also called "inclusion / subtyping polymorphism".
Usually executes slower than statistical related implementation due to the late binding (i.e. at the runtime).
A class should have only one reason to change.
WRONG C# Example
public static class Client
{
public static void Main()
{
var square = new Square(5);
square.Draw();
}
}
public class Square
{
private readonly int _size;
public Square(int size)
{
_size = size;
}
public void Draw()
{
// Doing some complicated stuff
}
}RIGHT C# Example
public static void Main()
{
var square = new Square(5);
var drawer = new SquareDrawer(square);
drawer.Draw();
}
public class Square
{
private readonly int _size;
public Square(int size)
{
_size = size;
}
}
public class SquareDrawer
{
private readonly Square _square;
public SquareDrawer(Square square)
{
_square = square;
}
public void Draw()
{
// Doing some complicated stuff
}
}Software entities should be open for extension, but closed for modification.
WRONG C# Example
public static class Client
{
public static void Main()
{
var shapes = new IShape[] { new Square(5), new Circle(1) /*, ...*/ };
foreach (var shape in shapes)
{
if (shape is Square square)
{
var drawer = new SquareDrawer(square);
drawer.Draw();
}
else if (shape is Circle circle)
{
var drawer = new CircleDrawer(circle);
drawer.Draw();
}
// ...
}
}
}
public interface IShape
{
}
public class Square : IShape
{
private readonly int _size;
public Square(int size)
{
_size = size;
}
}
public class Circle : IShape
{
private readonly int _radius;
public Circle(int radius)
{
_radius = radius;
}
}
public class SquareDrawer
{
private readonly Square _square;
public SquareDrawer(Square square)
{
_square = square;
}
public void Draw()
{
// Doing some complicated stuff
}
}
public class CircleDrawer
{
private readonly Circle _circle;
public CircleDrawer(Circle circle)
{
_circle = circle;
}
public void Draw()
{
// Doing some complicated stuff
}
}RIGHT C# Example
public static class Client
{
public static void Main()
{
var drawers = new IDrawer[]
{
new SquareDrawer(new Square(5)),
new SquareDrawer(new Square(3)),
new CircleDrawer(new Circle(1))
};
foreach (var drawer in drawers)
{
drawer.Draw();
}
}
}
public interface IShape
{
}
public class Square : IShape
{
private readonly int _size;
public Square(int size)
{
_size = size;
}
}
public class Circle : IShape
{
private readonly int _radius;
public Circle(int radius)
{
_radius = radius;
}
}
public interface IDrawer
{
void Draw();
}
public class CircleDrawer : IDrawer
{
private readonly Circle _circle;
public CircleDrawer(Circle circle)
{
_circle = circle;
}
public void Draw()
{
// Doing some complicated stuff
}
}
public class SquareDrawer : IDrawer
{
private readonly Square _square;
public SquareDrawer(Square square)
{
_square = square;
}
public void Draw()
{
// Doing some complicated stuff
}
}Objects in a program should be replaceable with instances of their subtypes without altering the correctness of that program.
WRONG C# Example
public static class Client
{
public static void Main()
{
TestRectangleArea();
TestSquareArea();
}
public static void TestRectangleArea()
{
var rectangle = new Rectangle();
AssertArea(rectangle);
}
public static void TestSquareArea()
{
var square = new Square();
AssertArea(square);
}
private static void AssertArea(Rectangle rectangle)
{
rectangle.SetWidth(5);
rectangle.SetHeight(4);
if (rectangle.Area() != 20)
{
throw new Exception("Wrong area!");
}
}
}
public class Rectangle
{
private int _width;
private int _height;
public virtual void SetWidth(int width)
{
_width = width;
}
public virtual void SetHeight(int height)
{
_height = height;
}
public int Area()
{
return _width * _height;
}
}
public class Square : Rectangle
{
public override void SetWidth(int width)
{
base.SetWidth(width);
base.SetHeight(width);
}
public override void SetHeight(int height)
{
base.SetWidth(height);
base.SetHeight(height);
}
}RIGHT C# Example
public static class Client
{
public static void Main()
{
TestRectangleArea();
TestSquareArea();
}
private static void TestRectangleArea()
{
var rectangle = new Rectangle();
rectangle.SetWidth(5);
rectangle.SetHeight(4);
AssertArea(20, rectangle);
}
private static void TestSquareArea()
{
var square = new Square();
square.SetSize(5);
AssertArea(25, square);
}
private static void AssertArea(int expected, IShape actualShape)
{
if (actualShape.Area() != expected)
{
throw new Exception("Wrong area!");
}
}
}
public interface IShape
{
int Area();
}
public class Square : IShape
{
private int _size;
public void SetSize(int size)
{
_size = size;
}
public int Area()
{
return _size * _size;
}
}
public class Rectangle : IShape
{
private int _width;
private int _height;
public void SetWidth(int width)
{
_width = width;
}
public void SetHeight(int height)
{
_height = height;
}
public int Area()
{
return _width * _height;
}
}Many client-specific interfaces are better than one general-purpose interface.
WRONG C# Example
public static class Client
{
public static void Main()
{
var cube = new Cube();
cube.SetSize(3);
cube.Area();
cube.Volume();
var square = new Square();
square.SetSize(3);
square.Area();
// This computation below should not be possible...
// We need more granularity =]
square.Volume();
}
}
public interface IShape
{
int Area();
int Volume();
}
public class Cube : IShape
{
private int _size;
public void SetSize(int size)
{
_size = size;
}
public int Area()
{
return 6 * _size * _size;
}
public int Volume()
{
return _size * _size * _size;
}
}
public class Square : IShape
{
private int _size;
public void SetSize(int size)
{
_size = size;
}
public int Area()
{
return _size * _size;
}
public int Volume()
{
throw new System.NotImplementedException();
}
}RIGHT C# Example
public static class Client
{
public static void Main()
{
var cube = new Cube();
cube.SetSize(3);
cube.Area();
cube.Volume();
var square = new Square();
square.SetSize(3);
square.Area();
// This computation below is now no longer possible =]
// square.Volume();
}
}
public interface IAreaCalculable
{
int Area();
}
public class Square : IAreaCalculable
{
private int _size;
public void SetSize(int size)
{
_size = size;
}
public int Area()
{
return _size * _size;
}
}
public interface IVolumeCalculable
{
int Volume();
}
public class Cube : IAreaCalculable, IVolumeCalculable
{
private int _size;
public void SetSize(int size)
{
_size = size;
}
public int Area()
{
return 6 * _size * _size;
}
public int Volume()
{
return _size * _size * _size;
}
}One should depend upon abstractions not upon concretions.
WRONG C# Example
RIGHT C# Example
- Unit Testing: Arrange / Act / Assert
- TDD
- BDD
- DDD and related domain-centric architectures
- CI
- CD
Record: a row, there are different types:
- Data Record
- Index Record
Page
Sending ↓ (Encapsulate) → OSI → Receiving ↑ (Decapsulate)
| No. | Name | Data Unit | Layer | Definition | Examples |
|---|---|---|---|---|---|
| 7 | Application | Data | Host | High level APIs, sharing, remote access | HTTP, FTP, SMTP |
| 6 | Presentation | // | // | Encyphering, compression, encoding | ASCII, JPEG, GIF |
| 5 | Session | // | // | Manage sessions (continuous sessions) | RPC, SQL, Netbios Names |
| 4 | Transport | Segments | // | Reliable transmissions | TCP/ UDP |
| 3 | Network | Packets | Media | Manage multinode network | IP (Router) |
| 2 | Data Link | Frames | // | Transmission between 2 nodes | MAC, Switch / Bridge |
| 1 | Physical | Bits | // | Raw bits stream | Repeater / Hub |
Vocabulary
| Acronym | Definition |
|---|---|
| HTTP | Hyper Text Tranfer Protocol |
| FTP: | File Transfer Protocol |
| SMTP | Simple Mail Transfer Protocol |
| ASCII | American Standard Code for Information Interchange |
| JPEG | Joint Photographic Experts Group |
| GIF | Graphics Interchange Format |
| TCP | Transmission Control Protocol |
| UDP | User Datagram Protocol |
| IP | Internet Protocol |
| MAC | Media Access Control Address |
| NIC | Network Interface Card |
| Device | OSI No. | Definition |
|---|---|---|
| Repeater | 1 | Repeat incoming bits from one port to another |
| Hub | 1 | A multiport repeater |
| Bridge | 2 | A repeater with MAC filtering |
| Switch | 2 | A multiport bridge |
| Router | 3 | Route data based on their IPs |
| Verb | Definition | Idempotent | Safe |
|---|---|---|---|
OPTIONS |
|||
GET |
|||
HEAD |
|||
POST |
|||
PUT |
|||
PATCH |
|||
DELETE |
|||
TRACE |
Notes
- Idempotent:
- Safe:
| Category | Definition |
|---|---|
| 1XX | Informational |
| 2XX | Success |
| 3XX | Redirection |
| 4XX | Client Errors |
| 5XX | Server Errors |
Codes
| Code | Name | Definition |
|---|---|---|
| 100 | Continue | |
| 101 | Switching Protocols | |
| 200 | OK | |
| 201 | Created | |
| 202 | Accepted | |
| 204 | No Content | |
| 206 | Partial Content | |
| 301 | Moved Permanently | |
| 307 | Temporary Redirect | |
| 400 | Bad Request | |
| 401 | Unauthorized | |
| 403 | Forbidden | |
| 404 | Not Found | |
| 409 | Conflict | |
| 500 | Internal Server Error | |
| 501 | Not Implemented |
Representational State Transfer (REST) is a software architectural style that defines a set of constraints to be used for creating web services.
Note: does not require to use HTTP or specific verbs for certain cause there is not an actual standard but some broad loosely shared conventions.
| Constraint | Definition |
|---|---|
| Uniform Interface | |
| Client - Server | |
| Stateless | |
| Cacheable | |
| Layered System | |
| Code on demand |
-
The browser checks the cache for a DNS record to find the corresponding IP address of
maps.google.com.Details
i. First, it checks the browser cache. The browser maintains a repository of DNS records for a fixed duration for websites you have previously visited. So, it is the first place to run a DNS query.
ii. Second, the browser checks the OS cache. If it is not found in the browser cache, the browser would make a system call (i.e. gethostname on Windows) to your underlying computer OS to fetch the record since the OS also maintains a cache of DNS records.
iii. Third, it checks the router cache. If it's not found on your computer, the browser would communicate with the router that maintains its’ own cache of DNS records.
iv. Fourth, it checks the ISP cache. If all steps fail, the browser would move on to the ISP. Your ISP maintains its' own DNS server which includes a cache of DNS records which the browser would check with the last hope of finding your requested URL.
-
If the requested URL is not in the cache, ISP’s DNS server initiates a DNS query to find the IP address of the server that hosts
maps.google.com.Details
-
Browser initiates a TCP connection with the server.
Details
-
The browser sends an HTTP request to the web server.
-
The server handles the request and sends back a response.
-
The server sends out an HTTP response.
-
The browser displays the HTML content (for HTML responses which is the most common).
Details
undefined
null
bool
number
string
symbol
A truthy value is a value that is considered true when encountered in a Boolean context.
All values are truthy unless they are defined as falsy (i.e., except for false, 0, "", null, undefined, and NaN).
- Scope: variables access / visibility of a function
- Context: refers to the object to which a function belongs
3 types of execution contexts:
- Global execution context (GEC): default execution context in which JS code start it’s execution
- Functional execution context (FEC): Functional execution context is defined as the context created by the execution of code inside a function.
- Eval: Execution context inside eval function.
Hoisting: var declarations are lifted to the top
function.bind(thisArg[, arg1[, arg2[, ...]]]): creates a new function that, when called, has its this keyword set to the provided value as well as additional argumentsfunction.call(thisArg, arg1, arg2, ...): calls a function with a given this value and arguments provided individually.function.apply(thisArg, [argsArray]): calls a function with a given this value, and arguments provided as an array (or an array-like object).
Process to reduce functions of more than one argument to functions of one argument with the help of lambda calculus.
Uncurrying also exists.
(function () {
// statements go here...
})();Note: this prevents accessing variables within the IIFE idiom as well as polluting the global scope.
- Stores data with no expiration date, and gets cleared only through JavaScript, or clearing the Browser cache / Locally Stored Data
- Storage limit is the maximum amongst the three
- The
sessionStorageobject stores data only for a session, meaning that the data is stored until the browser (or tab) is closed. - Data is never transferred to the server.
- Storage limit is larger than a cookie (at least 5MB).
- Event queue
- ES6 Features
A Promise represents the eventual completion (or failure) of an asynchronous operation, and its resulting value.
| State | Definition |
|---|---|
pending |
initial state, neither fulfilled nor rejected. |
fulfilled |
meaning that the operation completed successfully. |
rejected |
meaning that the operation failed. |
Example
// Custom Promise
const myFirstPromise = new Promise((resolve, reject) => {
// do something asynchronous which eventually calls either:
//
// resolve(someValue); // fulfilled
// or
// reject("failure reason"); // rejected
})
.then((someValue) => {
// someValue is whatever we passed in the resolve(...) function above.
// It doesn't have to be a string, but if it is only a succeed message, it probably will be.
console.log("Yay! " + someValue);
})
.catch((err) => {
console.log("Noo! " + err);
});
// "Built-in"
fetch('https://no-such-server.blabla') // rejects
.then(response => response.json())
.catch(err => alert(err)) // TypeError: failed to fetch (the text may vary)Compiler Difference with AngularJS
Data Resolution
- Difference Process / AppDomain / Thread
- Synchronization Primitives
- Execution Context
- Synchronization Context
- How does an asynchronous method work: pattern-based + machine state
Adding more machines into your pool of resources
Adding more power (CPU, RAM) to an existing machine
Notes:
-
It is typically costly. It does not make the system fault tolerant, i.e if you are scaling application running with single server, if that server goes down, your system will go down.
-
Also the amount of threads remains the same in vertical scaling.
-
Vertical scaling may require your system to go down for a moment when process takes place.
Responsibilities:
- Applications
- Data
- Runtime
- Middleware
- OS
- Virtualization
- Servers
- Storage
- Networking
"On-demand" software
Responsibilities that you have to manage: none
Examples: Google Apps, Microsoft Office 365, etc.
Computing platforms
Responsibilities that you have to manage:
- Applications
- Data
Examples: Windows Azure, Heroku, etc.
Computing infrastructures
Responsibilities that you have to manage:
- Applications
- Data
- Runtime
- Middlware
- OS
Examples:
Responsibilities that you have to manage: everything