DEV Community: limjy

System Design

limjy — Sat, 29 May 2021 09:49:48 +0000

System Design study guide / interview prep for me

Content here is not original. It is is a summary of the following sources:

freeCodeCamp - System Design Interview Question (really comprehensive 20/10 will recommend you give it a read)

IGotAnOffer - Database: system design interview concepts
freeCodeCamp - System Design interview concepts
medium - 25 java software design questions ### HTTP Methods
GET
- retrieve resources
POST
- submit new data
PUT
- update / replace existing data
DELETE
- removes data
PATCH
- modify resource. only contains changes not whole resource
OPTIONS
- requests available communication methods
HEAD
- request resource metadata without retrieve full resource representation

reference: SO & stackprint

Standard Error Code

400 Bad request
- client side input fail validation
401 Unauthorized
- user not authenticated
403 forbidden
- user authenticated but not privileged to access resources
404 Not Found
- resource not found
500 Internal Server Error
- generic server error. shouldn't be thrown explicitly.
502 Bad gateway
- invalid response from upstream server
503 Service Unavailable
- something unexpected happen on server side (server overload, some parts fiail( reference: SO

Storage: Memory VS Disk

Disk is persistent. (when power is off, data will "persist").
RAM is transient. When lost power memory is wiped away.

If data is useful only during session of server then keep it in Memory.

Keeping it in RAM is much faster and less expensive than writing to persistent database.

Latency VS Throughput

Latency: duration for action to complete / produce result
Throughput: maximum capacity of system / work done in unit time.

Latency:
- load site fast & smoothly
- fast lookups
- avoid pinging distant servers.
Throughput
- can improve by reducing bottleneck
- system will only be as fast as its slowest bottleneck
- increase by improving slowest bottleneck

Hard ware definition from compritech:

Latency: time taken for packet to be transferred across network
Throughput: quantity of data being send & recevied per unit time

Scaling: Vertical VS Horizontal

Vertical Scaling: adding compute (CPU) and memory (RAM, Disk, SSD) resources to a single computer.
Horizontal Scaling: adding more computers to a cluster

Vertical
- fairly straightforward
- much lower overall memory capacity
Horizontal
- higher overall compute and storage capacity
- sized dynamically without downtime
- most popular DB model hard to scale horizontally.

Availability: Intro

availability is like resiliency of system. fault tolerant system makes an available system.

Uptime
Measured using (uptime): percentage time system's primary function is available in given window of time

Service Level Agreement / Assurance
set of guaranteed service level metrics.

How to achieve High Availability

Reduce or eliminate single points of failure
This is done by designing redundancy into the system.

Eg. two or more servers to provide services.

Why Caching

Caching helps reduce latency of system.

app can perform faster
- faster to retrieve data from memory than disk

Works best when

store static / infrequently caching data

source of change is single operations rather than user-generate operations

If data consistency & freshness is critical. Caching may not be optimal unless cache is refreshed frequently (refresh cache frequently may not be ideal either)

Caching: Use Case

when using certain piece of data often

backend has computationally intensive work (cache reduces complexity to O(1))

server makes multiple netwrk requests & API calls

Example

CDN (content delivery network)
- caches content (images / videos/ webpages) in proxy server located closer to end user than origin server
- can deliver content more quickly.

Caching Strategy

deals with the "write" operations of cache.

keep cache & DB in sync

should it be done synchronously or asyncrhonouslt

data eviction - Which old records to "kick out" for new data?

Caching Strategies

LIFO
FIFO
LRU
LFU ### Proxy:basics proxy: basically a middleman between client & origin server.

There are 2 kinds of proxies

forward
reverse Forward
computer make requests to sites on internet
proxy server intercepts request
communicate to web server on behalf of clients

Reverse

client send request to origin server of website
requests intercepted at network edge by reverse proxy server
reverse proxy sends request to & receive response from origin server

Forward VS Reverse Proxy

proxy: basically a middleman between client & origin server.

How proxies work

Forward: sits in front of client, no origin server communicates with specific client. Server has no knowledge of client
Reverse: sits in front of origin server, no client communicate directly with origin server. Client has no knowledge of server.

Forward proxy
- avoid company browsing restrictions.
- clients connect to proxy rather than directly to sites they are visiting
- block access to certain content
- school network, configure to connect to web via proxy that blocks stuff
- privacy
- IP address of client is harder to tarce, only IP address of prxy server is visible
Reverse proxy
- load balancing
- distribute incoming traffic among different origin servers
- protection from attacks
- web site/service never needs to reveal IP address of original server
- harder to have targeted attack against origin server (eg. DDoS). hackers can only target reverse proxy. Reverse proxy will have tighter security & more resources.
- Global Server Local Balancing
- website distributed on several servers around the globe.
- reverse proxy send clients to server geographically closets to them.
- Caching
- reverse proxy can cache content -> faster performance
- SSL encryption
- reverse proxy can decrypt all incoming requests & encrypt all outgoing repsonses
- free up valuable resources on origin server.

Reference: cloudflare

Why Load balancing

Maintain availability & throughput
By distributing incoming request loads across multiple servers

When server get lots of requests it can:

slow down (throughput reduces, more latency)
fail (no availability)

Load Balancing helps this by Distribute incoming traffic among origin servers

Load Balancing Strategies

Probability server selection

Round Robin
- loop through servers in fixed sequence
Weighted Round Robin
- assign different weights / probabilities each server.
- traffic split up according to weights
Load-based server selection
- monitor current capacity / performance of servers
- send request to server with highest throughput / lowest latency.
IP Hashing based selection
- hash IP address of incoming request
- use hash value to allocate server
Path / Service based selection
- route requests based on path / service provided.

CAP Theorem

any distributed DB can only satisfy 2 of three features

Consistency: every node responds with most recent version of data

Availability: Any node can send a response

Partition tolerance: system continues working even if communication between any of the nodes is broken

DB is usually CP or AP database. Since cannot garuntee statbility of network, P is non-negotiable.

Relational Database

database using a relational data model, organizes data in tables with rows of data entries and columns of predetermined data types.

Use when

many-to-many relatinoship between entries
data needs to follow predetermined schema
consistent transactions are important
relationship between data always need to be accurate

ACID properties

Atomicity
- transaction is atomic / smallest unit.
- all instructions in transaction will execute or non at all
Consistency
- If DB in initially consistent, it should remain consistent after every transaction
- eg. write operation (transfer money from A to B) failed & transaction not rolled back. Db is inconsistent because amount of money between A &B (A+B) not equal before & after transaction
Isolation
- multiple transaction running concurrently they should be affected by each other
- result should be same as result obtained if transactions running sequentially.
Durability
- changes committed to DB should remain even in case of software & system failure.

Reference educative & tutorialspoint

Non-relational Database

also known as NoSQL database.
at core, DB hold data in hash-table like structure.
Use cases: caching, environment variables, configuration files / session state
Use environment: in memory & persisten storage

Since their structure is like hashtable there is minimal over head

extremely fast
simple & easy to use

NoSQL Base properties

Basically available: system guarantees availability
soft state: state of system may change over time even without input
eventual consistency: system will be consistent over very short period of time unless inputs are received

Types of Nosql DB

Graph database
- many-to-many realtinoships
- fase at following graph edges
Document Store
- isolated documents, retrieve by a key
- documents with different schemas that are easy to update
- easy to scale
Key-value store
- like a very large hashtable
- opaque values (DB has no notion of what is stored in value only provides read, overwrite and delete operations)
- simple operations (no schemas, joins or indices)
- minimal overhead - easy to scale
- suitable for caching implementations
column-family DB

NoSQL VS Relational

NoSQL
- dynamic schema.
- dev can use "unstructured data" can build application without defining schema
- Scaling
- scales horizontally over cheap commodity servers
- Simple Operations
- data retrieval is simple
- Cheap hardware
- app deployed to commodity hardware like public clouds
SQL
- workload volume is consistent
- ACID garuntees required
- data is predictable & highly structured
- data est expressed relationally
- write safety required
- app deployed to large high-end hardware

https://www.mongodb.com/scale/nosql-vs-relational-databases
https://www.mongodb.com/nosql-explained/when-to-use-nosql
https://docs.microsoft.com/en-us/dotnet/architecture/cloud-native/relational-vs-nosql-data#considerations-for-relational-vs-nosql-systems

Leader Election: Basics

When system scales horizontally, some tasks require precise coordination between nodes. Where there is leader nodes directing follower nodes.

Leader Election algo

how cluster of nodes without leader communicate with each other & choose one to be leader.

algo executed when cluster starts or when leader node goes down.

Use Case

Any node can be leader, no single point of failure required to coordinate system
System doing complex work that need good coordination
- eg. compute how protein folds. cluster needs leader node to assign each node to work on different part then add results together
System executes many distributed writes to data & requires strong consistency
- no matter which node handles request user will always have most up-to-date version of data.
- leader creates consistency by being source of truth on what the most recent state of system is.

Drawbacks

split brain
- bad implementation -> 2 nodes controlling system
single point of failure / bottleneck
leader starts making bad decisions entire system will follow

Reference: iGotAnOffer

MQ Benefits

Resilience
- app specific faults wont impact system
- if one component fails, all others can continue interacting with queue, processing / producing messages.

Reference: IBM

Core Java / Java Theory

limjy — Thu, 27 May 2021 16:02:23 +0000

Theory stuff about Java

Content here is not original. It is my summary of the following resources
References:
This medium post by Edureka (along with other articles in the series) are insanely good

in28Minutes github - this is a great resource for interview prep. ( However do double check with other sources. I find their explanation of encapsulation & unchecked VS checked exception strange )

Other good resources:

javarevisited is a very good resource for in-depth questions. It's good for harder / obscure questions and makes your understanding clearer by doing a deep dive.

https://www.edureka.co/blog/interview-questions/oops-interview-questions/

Quick Summaries of OOP:
https://blog.udemy.com/oops-interview-questions/
https://blog.udemy.com/oop-interview-questions/

HashMap
- how hashmap works internally
  - 16 initial buckets, 0.75 load factor, threshold of 12
  - hashCode for bucket index calculation
  - LinkedList for collision
  - equals() to compare keys
  - rehashing when meet threshold, buckets are doubled
- null key added
HashSet
- hashset internal implementation in Java
  - implemented with hashmap
  - set element are hashmap keys
  - all hashmap values are a dummy object.
ArrayList
- capacity VS size
- how arraylist works internally
  - implemented with array
  - initial capacity of 10
  - grows 50% when no space
Vector
- Java vector class
  - thread safe arraylist
Stack
- how is stack implemented by java
  - empty on creation
  - dynamic array NOT linkedlist
Queue
- queue implementations in Java
  - interface not a class
  - implemented by PriorityQueue & LinkedList

Java Implementations / Interfaces / Common Classes ( will only go through general-purpose implementations coz no time )

Map Implementations
- HashMap
- TreeMap
- LinkedHashMap
Set Implementations
- HashSet
- TreeSet
- LinkedHashSet
List Implementations
- ArrayList
- LinkedList
Queue Implementations (see above)
- PriorityQueue
- LinkedList
Dequeue Implementations (double-ended queue) ( going to skip this )
- LinkedList
- ArrayDequeue

OOP Concepts & OOP in Java( references in this section mainly from educative articles: OOP & OOP in Java

What is OOP
4 Pillars of OOP
- inheritance
  - Types of Inheritance
  - single inheritance
  - multilevel
  - multiple
  - hierarchical
  - hybrid
  - inheritance-in-java
  - extends VS implements
- Abstraction
  - abstraction in java
  - abstract class VS interface
- Encapsulation
  - encapsulation in java
    - getters & setters
    - tight encapsulation
- Polymorphism
  - compile time VS runtime
  - method overloading
  - method overloading conditions
  - method overriding
  - method overriding rules
    - overriding VS hiding (static methods)
Abstraction VS Encapsulation (https://stackoverflow.com/a/51304341)
Relationships (https://www.c-sharpcorner.com/UploadFile/3614a6/is-a-and-has-a-relationship-in-java/)
- IS-A relationship (inheritance)
- HAS-A relationship (composition)
Other concepts
- Association
  - association (2 classes have a link, need to communicate between them)
  - aggregation (weak association, child can exist independently of the parent)
  - composition (strong association, child cannot exist independent of parent)
- association VS aggregation VS composition
- Coupling
- Cohesion

Java Exception Handling (JournalDev Exception Handling article primarily used as reference for this section )

runtime exceptions
exception handling keyword
- try
- catch
- finally
Java Exception Hierarchy
- Unchecked VS Runtime Exception
Exception Class Methods
Excpetion Handling criteria
Exception Handling Best Practice

OOP Concepts

SOLID (https://www.baeldung.com/solid-principles)
- single responsibility
- openfor extension closed to modfication
- lishov subsitution (sub subclass for base class)
- interface segregation (split big interface itno smaller ones)
- dependency inversion (depend on abstract classes/ interfaces instead of classes)

UML

needed to understand different design patterns
Class Diagram
- Association
- inheritance / generalization / abstraction
- multiplicty
Sequence Diagram

Design Patterns

Creational
- singleton
- factory & abstract factory
- Builder
Structural
- decorator
- flyweight
- adapter
Behavioural
- observer
- strategy
- state

MultiThreading

thread VS process
Threads & Runnable
Thread VS Runnable
keywords
- synchronized
- volatile
- wait()
- notify()
- notifyAll() https://howtodoinjava.com/java/multi-threading/wait-notify-and-notifyall-methods/ https://dzone.com/articles/difference-between-volatile-and-synchronized-keywo https://stackoverflow.com/a/3519736 https://howtodoinjava.com/java/multi-threading/java-runnable-vs-thread/ https://stackoverflow.com/a/15471504

Statically Typed

Reference: Oracle Documentation

perform type checking at compile time
- provides type safety
- if Java code contains errors, it will fail to compile until the errors have been fixed
declare data types of variables before you use them
- int num; num = 5; VS num =5
- expects variables to be declared before it can be assigned value.

Opposite of statically typed is dynamically-typed (eg. python)

Class based

Reference: mozilla developer docs & stack overflow & zendesk & wikipedia

Class based programming / class-orientation is a style of Object-oriented programming (OOP)
Class-based: makes distinction between objects & class.
prototype-based: no distinction. It has objects. start with an instance / object & modify it.

Defining class
- define class in class definition & specify methods (constructors) to create instances of the class.
- prototype : class definition not separate from constructor. constructor function creates object with initial set of properties & values
Subclass / inheritance
- create heirachy via class definition Manager extends Employee
- prototype: associate object with any construtor function. (call another object in the constructor function of subclass)
Adding & removing properties
- cannot change type / number of properties after class definition
- class created at compile time & objects instantiated at compile or run time
- prototype: ca remove or add properties of any object at run time.

Opposite of class based is protoype-based / object-based (eg. javascript)

What is Object-oriented programming

Reference: wiki & educative & educative - Oop JS

OOP is a programming paradigm based on the concept of "objects".
Program is broken down into segments of objects that communicate with each other.
Each objct is define by:

its functions (called methods)

its data (called properties)

This is a general overview of OOP. as seen in previous section that are also different "styles" of OOP (object-based & class-based).

From some articles we can also see the question "Is a OOP langauge?" is not a straight forward yes or no answer.

To be OOP language, programming language has to satisfy a list of OOP condition / properties. Depending on whether programming language has satisfied some / all OOP conditions we can then say "yes" or "no".
Even if the answer is "yes" programming language is OO. There is still the question of "is purely object-oriented?"

Alternatives / Opposite
There is no "opposite" of object -oriented proramming. But there are different programming paradigms like: (reference: SO)

procedural
fuctional etc.

Java not pure OOP

Reference: GeeksforGeeks & dataflair

Java is not a pure object-oriented language. Because it has:

primitive data type

static keyword

wrapper class

To fulfill pure OOP, language must satisfy all 7 conditions:

Encapsulation / Data Hiding
inheritance
polymorphism
abstraction
All predefined types are objects
All user defined types are objects
All operations performed on objects must be only through methods exposed at objects

Java fails condition 5(all predefined types are objects) & 7(operations performed on objects must be only through methods exposed at objects)

primitive data types
- primitives are not objects
static keyword
- when class is static, it can be used without objects
- static function / variables. can be called without creating an object of class.
Wrapper class
- unboxing: when using arithemtic operators (% or +=) are performed on wrapper classes. compiler converts object to primitive datatype at runtime. Thus violating condition 5 (primitive types are not objects)
- arithmetic operations on object String test = "hello" + " world" use of arithmetic operations on wrapper class also violate condition 7 (can communicate with objects with calling their methods)

Java platform Independent

Java is WORA (Write once Run anywhere). java source code can run on all operating systems.
byte code (.class) generated by javac compiler can be executed on any OS. Bytecode is understandable is any JVM installed on any OS.

JAVA is platform-independent language, the JVM is platform-dependent.
must install different JVM for different OS.

JVM will convert bytecode (.class) to machine code
Since machine code is run, this makes run time faster.

Reference: javatpoint & codingningjas & guru99

Java: JVM, JRE, JDK

JDK: Java development Kit
software development environment used for making applets & Java applications.

JRE + compiler + debugger JRE: Java Runtime Environment software designed to run other software. To run Java you need JRE. It contains class libraries, loader class & JVM.

JVM + libraries + other components (to run applets / java applications) JVM:

Virtual machine running java bytecode

maeks java portable

comes with JIT(Just-In-Time) compiler that converts java source code to low-level machine langauge.

Reference: guru99 & javatpoint & geeksforgeeks

Java JIT Compilation

Just-In-Time (JIT) Compilation also known as dynamic compilation.
Program is compiled to native code during runtime to improve performance.

In JIT compilation,

translates bytecode(.class) to machine code instructions of running machines
- resulting machine code is optimized for running machine's CPU architecture
compilation is done at runtime of program (as opposed to prior to execution)
since compilation takes place in run time, JIT compiler has access t dynamic runtime information enabling it to mae better optimizations

The hope is that the efficiency of running machine code will overcome inefficiency of recompiling program every time it runs.

Optimizations
JVM execute bytecode & mantians count of how many times function is executed
If count exceeds pre-defined limit, JIT compiles code into machine lanaguage that can directly be execute by processor.

Next time, function is calaculated, compiled code is executed again unlike normal interpretatio --> faster execution

Reference: freeCodeCamp & GeeksforGeeks & javatpoint

Memory Managment in Java

Memory management is the process of allocation & de-allocation of objects. Java uses automatic memory management system called garbage collector.

Reference: javatpoint & oracle docs & peter lee medium

Java: Heap Space VS Stack Memory

To run application in optiomal way, JVM divide memory into stack & heap memory
Stack:

used for execution of thread

primitive values specific to a method

references to objects that are in a heap, referred from method.

thread-safe: eahc thread operated in its own stack Heap:

actual objects

dynamic memory allocation for Java objects & JRE classes at runtime

String Pool

not thread-safe: needs to be guarded by properly synchronizing code

New objects are always created in heap space and the references to this objects are stored in stack memory. When the heap becomes full, garbage is collected. So, no longer used are cleared, thus making space for new objects.

Heap
- created when JVM starts up & may increase/decrease in size while application runs
- when heap is full, garbage is collected
- new objects created in heap space references to objects stored in stack memory
- objects have global access and can be accessed from anywhere in the application, not thread safe
- Broken down to 3 parts
- Young Generation: all new objects are allocated & aged.
- Old / Tenured Generation: long surviving objects stored. object stored in young gen, threshold for its age set. when threshold reached. Object moved to old gen
- Permanent Generation: JVM metatdata for runtime classes & application methods.
- When heap becomes full garbage is collected
Stack
- referenced in LIFO order
- when new method is called, new block on top of stack is created which contains values specific to that method (eg. primitive variables & references to objets)
- method finish execution -> corresponding stack frame is flushed, flow goes back to calling method. space available for next method

package com.journaldev.test;

public class Memory {

    public static void main(String[] args) { // Line 1
        int i=1; // Line 2
        Object obj = new Object(); // Line 3
        Memory mem = new Memory(); // Line 4
        mem.foo(obj); // Line 5
    } // Line 9

    private void foo(Object param) { // Line 6
        String str = param.toString(); //// Line 7
        System.out.println(str);
    } // Line 8

}

Run program -> load runtime classes to Heap space
main() method found at line 1, runtime create stack mem to be used by main() method thread. Whenever new object created,
object created in heap memory
stack memory contains the reference for it.
when new method called -> new block created on top of stack (LIFO)
String, reference in stack mem -> reference points to String pool in heap space
when method (foo())terminates, stack becomes free (stack mem created for function destroyed)
move to next program below (main())

Reference: stackify & baledung & JournalDev

Java Garbage Collection

GC: Process by which Java performs automatic memory management
When Java programs run on JVM, objects are created on the heap. When some objects no longer needed. GC will find the, delete them to free up memory.

4 garbage collectors: planning to bomb this if asked

serial
parallel
concurrent mark sweep
G1 (h=garbage first)

Benefits

automatically handles deletion of unused objects / objects out of reach to free up virtual memory resources.

Reference: stackify

Java: Comparison to Python

Java programs expected to run faster than python
- Python tun time typing, python run time "works harder" than java (more tasks to do
- python run time must inspect objects and find type then invoke operation
Java programs take longer time to develop
Java programs are longer (number of lines of code) than python
- java is statically typed

Reference: python org

Objects & Classes

Class: user defined blueprint from which object is created
Object: basic unit of OOP, instance of a class.

objects can be created from class via constructor. There are 2 kinds

Default / non-parameterised
- 0 arguments
Parameterised
- constructors have specific number of arguments to be passed

constructor cannot be abstract final or static

Variables & Methods

Types of variables

local
instance
static

each object has own copy of instance variable however, all objects will share only one copy of static variable

Methods
Methods consist of

modifier
- eg. private / public
return type
method name
parameters
method body / logic

static methods belong to a class, no need to instantiate object to use the method

Method Signature

Method signature is <method name>()<argument types>)
Does NOT include: access modifier & return type

In java, you cannot have >=2 methods with same method signature in the same class (even if methods have different return types)

public void display(String info){
  System.out.println(info);
}

// ERROR: duplicate method Signature
public String display(String info){
  // logic
}

Packages

Group of classes & interfaces & sub-packages which has similar functionalities.
Provide folder structure to organise classes

packages naming style:

lower case
reverse domain

Access Modifiers

Modifiers set accessibility of classes or methods or any memebers

public
private
protected
default (no modifiers)

Reference: Jenkov tutorials & GeeksforGeeks

Abstract Keyword

non-access modifier applicable for classes and methods but not variables
Used to achieve abstraction in Java (one of the pillars of OOP)

Abstract class

cannot create / instantiate object of abstract class
Any subclass of abstract class must either implement all abstract methods or be declared abstract itself.

abstract class class-name{
    //body of class
}

Due to partial implementation of classes, object cannot be instantiated.
Abstract class depend on subclass to provide complete implementation.
Any sub

Abstract method

Abstract method dont contain body. sub classes will implement them

abstract type method-name(parameter-list);

any class containing abstract method must be abstarct
the following combinations of modifiers cannot be used with abstract
- final (class & method)
- private (method)
- static (method)
- synchronized (method)
- native / strictfp

Further reading of abstract method on Java Goal

References: GeeksforGeeks & javatpoint

Abstract Illegal modifiers

Abstract final

Class: final used to prevent inheritance
- Abstract classes depend on child classes to complete implementation.
Method: final used to prevent overidding -abstarct method need to be overidden in sub classes

Abstract private

Method: private method cannot be accessed outside current class
- child classes cannot access private abstract methods & cannot implement it.
Class: nested class. everything within class can access a nested private class
- can have a nested private abstract class SO example

Reference: tutorialspoint & stackoverflow

Abstract static

Method: static methods can be hidden but not overidden
- abstract method must be overidden to be implemented. Static methods cannot be overidden, so they cannot be abstarct.

Reference: tutorialspoint & stackoverflow

Abstract synchronized

Method: synchronised. thread gets lock on object on entering method
- thread entering synchronized method must get lock of the object in which method is define. cannot instantiate abstract class so no object with lock. https://javagoal.com/abstract-method-in-java/ https://stackoverflow.com/a/12805823

Abstract strictfp

strictgp is a an access-modifier. no modifiers allowed on abstarct methods except public and protected.

Final Keyword

for classes, variables & methods
used to finalize implementation of them

Final variable
- to create constant variable
- cannot change the value of final variable once it is assigned. It will be constant.
- can be initialized in constructor.
Final method
- prevent method overriding
- can be inherited but cannot be overridden.
- constructor cannot be made final. constructor cannot be inherited so it cannot be overriden, will have compile time error.
Final class
- prevent inheritance

references javatpoint & GeeksforGeeks & tutorialspoint

Static Keyword

for variables, methods, block, nested class
used to define classes members indepedent from any instances

static variable
- single copy of variable is create & shared among all objects at class level
static methods
- can be accessed before any objects of class created & without reference to any object.
- can only directly call other static methods
- can only directly access static data
- cannot refer to this or super
static nested / inner class
- mainly for convinience
- no need to instantiate outer class to instantiate inner class
- refer to: https://stackoverflow.com/a/47568544
- useful for: builder pattern (inner builder class is static)
static block
- do computation to initialize static variables
- is executed exactly once - when class is first loaded.

class Test {
    // static variable
    static int a = 10;
    static int b;

    // static block
    static {
        System.out.println("Static block initialized.");
        b = a * 4;
    }
}

References: GeeksforGeeks & javatpoint & Baeldung

Static VS Instance block

static block:

runs at time of class loading
will execute in same order they appear in the class
static block of parent class execute FIRST because compiler loads parent class BEFORE child class

instance block:

runs at time of instance creation
executees during every constructor invocation
parents instance block will run first BEFORE child's instance block

Order is
Super class - static
Sub class - static
Super class - instance
Super class - constructor
Sub class - instance
sub class - constructor

Note that by default JVM will insert super() ins first line of sub class constructor if developer has not done so.

ref: https://www.quora.com/In-Java-does-every-object-constructor-automatically-call-super-in-object-before-its-own-constructors
ref: https://www.javamadesoeasy.com/2015/06/differences-between-instance.html

ref: https://www.baeldung.com/java-static-instance-initializer-blocks

Wrapper Classes are immutable

Wrapper classes are immutable so operations like add, subtarct create new object and do not modify the old

Reference: GeeksforGeeks
eg.

public static void main(String[] args)  {
        Integer i = new Integer(12);
        System.out.println(i); // 12
        modify(i);
        System.out.println(i); //12
}

private static void modify(Integer i) {
        i = i + 1;
}

paramete i is referenced in modify however it does not change since objects are immutable.

Creating new object
Reference: SO & []

Integer a=3;
Integer b=3;
a+=b; // a=a+b
System.out.println(a); // 6

In this case, a+=b actually does a = new Integer(3+3)
a is a reference, in the line a+=b, the code changes the reference a to points to a different, equally immutable Integer.

Why wrapper class

Wrapper classes wraps around data type and give it an object appearance, this provides object methods to primitive types.
Reasons:

null is possible value

use it in Collection

methods that support object (eg. creation from other types Integer test = new Integer("55");

Different wrapper classes

Constructor VS valueOf

There are two ways to create wrapper class

constructor Integer test = new Integer("100");
valueOf Integer test = Integer.valueOf("100");

constructor: always creates new object
valueOf: may return a cached value if it is within range. (eg. if long is between -128 to 127, valueOf implements a cache). If not in cache gives new object.

valueOf is generally recommended since it results in better space and time performance by caching frequently requeste values.

Since wrapper classes are immutable, its important to reuse values.

Under the hood autoboxing also invokes the static valueOf method

Reference: java docs & SO answer

Autoboxing & Unboxing

automatic conversion Java compiler makes between primitive types & their corresponing object wrapper class.
Conversion the other way is called unboxing.

// autoboxing
Integer test = 9; 

// autounboxing
Integer test1 = Integer.valueOf(10);
test1++;

Autoboxing
create Integer object from primitive data type
Integer test = Integer.valueOf(9);

Auto Unboxing
airthmetic operations (+, %, +=) do not apply to Integer objects. Java compiler compiles code with no errors since it does autounboxing, invoking intValue to convert Integer to an int at runtime. test1.intValue()++;

reference: java docs

Autoboxing Advantages

lets developers write cleaner code that is easier to read.

Additionally, Autoboxing uses static valueOf method which is more efficient

Reference: java docs

Typecasting - Implicit & Explicit

Typecasting: converting primitive/interface/class in Java into another type.
If 2 types are compatible java performs conversion automatically else they need to be converted explicitly.

Implicit/widening/automatic
- happens if both types are compatible & target type is larger than source type

casting smaller value to a larger variable types

byte i = 50; // 50
short j = i; // 50
int k = j; // 50
long l = k; // 50
float m = l; // 50.0
double n = m; // 50.0

Explicit/narrowing
- assigning larger type to a smaller type

casting larger value to a smaller variable types

double d = 75.0; // 75.0
float f = (float) d; // 75.0
long l = (long) f; // 75 
int i  = (int) l; // 75
short s = (short) i; // 75
byte b = (byte) s; // 75

Reference: GeeksforGeeks & javainterviewpoint & edureka

Strings - immutable

Value of String object once created cannot be modified.
Any modification creates a String object
String is mainly immutable becuase it encapsulates a char[]

String test = "hello";
test.concat(" world");
System.out.println(test); // hello

value of String object was not modified. the concat()operator like toUppercase() operator produces a new String. The original value remains unchanged.

String str = "hello";
str = str + "world";
System.out.println(str); //hello world

In the code snippet, str was not changed. Rather a new String object "hello world" was instantiated and assigned to the reference str.

Reference: SO

Where are string values stored i memory?

depends on how we create them

String literal -> String constant pool (in heap)

new Object -> heap memory

String literal
- value stored in String constant pool (heap memory)
- compiler finds String literal -> check if exists in pool, reused.
String object constructor
- new object created on heap, reference in stack.
- not reuse of values

Java String Pool

String Pool in java is a pool of Strings sorted in Java Heap memory.

saves space for Java runtime

more time to create string.

only possible becuase

String is immutable in Java
implementation of String interning concept

String pool is an example of Flyweight design pattern.

String literal
String test = "hello";
when create string via String literal,

java looks for string with same value in string pool
- found: returns reference
- else: create new String in pool -> return reference.

String constructor
force Java to create new String object in heap space

String s1 = "Cat";
String s2 = "Cat";
String s3 = new String("Cat");

System.out.println(s1==s2); // true
System.out.println(s1==s3); // false

Reference: JournalDev

Java String Interning

method of storing only 1 copy of each distinct String value, which must be immutable.

Java String class has public method intern()

invoke intern() method on String object.
looks for the string contained by object in the pool
if string is found
- string from pool is returned
else:
- String object added to pool & reference to String object returned.

So by applying String.intern() on strings will ensure all strings with same content share same memory. eg. if 'hello' appears 100 times, interning ensures 1 'hello' is actually allocated memory.

String s1 = "Test"; // s1 in SCP
String s2 = "Test"; // s2 in SCP
String s3 = new String("Test"); // s3 in heap
final String s4 = s3.intern(); // s4 in SCP
System.out.println(s1 == s2); // true
System.out.println(s2 == s3); // false
System.out.println(s3 == s4); // false
System.out.println(s1 == s3); // false
System.out.println(s1 == s4); // true
System.out.println(s1.equals(s2)); // true
System.out.println(s2.equals(s3)); // true
System.out.println(s3.equals(s4)); // true
System.out.println(s1.equals(s4)); // true
System.out.println(s1.equals(s3)); // true

Reference: GeeksforGeeks & DZone

Number of Objects created in String Construction

String str = new String("Cat");

Either 1 or 2 objects created

String literal
- "Cat" String created in String pool (if does not exist)
String str object
- String object created on heap Reference: JournalDev & SO

Never + String in loops

each concatenation creates a new object, since string in immutable
use String Buffer/Builder

String test = "lup";
String test2 = "dup";
for (int i=0;i<100000;i++){
  test = test + test2;
}

Loop creates about 100 000 String objects.

String Buffer

StringBuilder test = new StringBuilder("lup");
String test2 = "dup";
for (int i=0;i<100000;i++){
  test.append(test2);
}
String result = test.toString();

This would yield better performance.

String VS StringBuffer

String immutable, StringBuffer used to represent values that can be modifed.
both are thread safe

StringBuilder VS StringBuffer

String Builder not thread safe String Buffer is

Java What is a class

template for creating multiple objects.
It defines:

state

behaviour that an object can exhibit

State
Values object has.
In Java, this would be the instance variables of the object

Behaviour
methods that are part of the class

State of object can change with time, can change via behaviour / class methods.

Java:

instance of class
Can create objects via constructor

ParentClass of every class

Java Object class is the super / parent class of every class in Java

Useful if you want to refer to any object whose type you dont know.

Classes will inherit all properties & methods of Java Object class.
eg.

toString
hashCode
equals
clone

Java Object toString method

used to print content of object
It is inherited from the Java objects class.
Default : print hash code
overridden : content returns by toString overidden implementation is printed.

The toString() method MUST

be public

return type: String

not accept any parameteres

Object class default toString method

public String toString()
{
      return getClass().getName()+"@"+Integer.toHexString(hashCode());
}

MyClass test = new MyClass();
System.out.println(test);
// com.example.demo.MyClass@f7e66a96

Reference: GeeksforGeeks & in28Minutes

Java equals() method

used to compare 2 object
Inhierited from java Objects class
Default: uses == operator (check if references point to the same object)
overidden: usually implemented as checking all properties of object have equals value

If making you own custom class, must override equals method to check the contents of the object.

equals() Method Criteria

All implementation of equals method must meet following criteria

Reflexive

For any reference values x, x.equals(x) returns true

Symmetric

x.equals(y) == y.equals(x)

transitive

if x.equals(y) = true & y.equals(z) = true, thenx.equals(z) == true.

Consistent

multiple invocations x.equals(y) will consistently return true or consistently / always return false.

outcome wont change when operation is repeated.

Null comparison

For any non null reference x, x.equals(null) must return false.

Usually just use IDE to generate

Reference JournalDev & in28minutes

Java hashCode() method

used in collections like hashmap.
Default: derived from memory address of object used in heap
Used in hashing to decide which bucket object should be place in.
Therefore, hashCode() decides the effectiveness of Hashing.
Good hashing function will distribute objects evenly across different buckets.

hashCode Method Criteria

Good hashCode should have following proerties

obj1.equals(obj2) == true --> obj1.hashCode() == obj2.hashCode()

consistent. obj.hashCode() shuould return same value when run multiple times if values used in obj equals() have not changed

if obj1.equals(obj2) == false --> obj1.hashCode MAY BE == obj2.hashCode().

Basically.

two unequal objects
- might have same hashcode (hash collision)
two equals objects
- must have same hashcode
  - if 2 equal objects have same hashcode, they can be placed in different buckets.
  - equals() function will never run on obj1 & obj2. obj2 will never replace obj1
  - hashmap can hold duplicate keys

Importance of equals() & hashCode()

It is a must to override / implement equals() & hashCode() method if you are using objects as hashma keys

Implementtation of equals() & hashCoe() follow these rules / contarct:

if o1.equals(o2) --> o1.hashCode() == o2.hashCode()
if o1.hashCode() == o2.hashCode() == true, o1.equals(o2) MAY NOT be true

So, if you implement equals method, its good practice to override hashCode so both methods follow contract.

however, this will only really come into play if you use objects as hashmap keys.

In hashing
equals():used to check if key exists in Hashmap
If wrongly implemented,

hashMap.get(obj) may return null, since wrong equals method cant tell that obj and key are equal
hashMap.put(obj1) may give "duplicate" keys. Since Java cant tell that obj1.equals(obj) and make obj1 override obj

hashCode(): decide which bucket obj will be placed in
If wrongly implemented:

equivalent objects can get placed in two different buckets.
- since equals() only runs on 1 bucket, Java cant tell that obj already exists on HashMap
- HashMap can store "duplciate" keys.

Reference: JournalDev

Java Objects Inheritance

process where one class aquires properties (methods & field) of another.
IS-A type of relationship
class : ChildClass extends ParentClass
interface : ChildClass implements Interfae1, Interface2

Sub Class: child class
Super class: parent class

Only 1 superClass
In Java,

child class can only extend 1 Parent Class
child class can implement >=1 Interface

Inheriting constructors
subclass inherits all memebers (fields methods, nested classes). but constructos are nont members & are not inhierted.
but constructor os superclass can be invoked from subclass super()

Private member inheritance
subclass does not inherit private members of parent class.
but subclass can use superclass's public / protected methods (eg. getter, setter) To access superclass's private fields.

During inheritance, only object of subclass created not super class

public class ChildClass extends ParentClass{
}
ChildClass test = new ChildClass()

In this case, only 1 ChildClass object created no ParentClass object is created.

Reference: GeeksforGeeks & tutorialspoint & w3schools

Java == VS equals

==: compares if 2 references point to the same object
can apply == for every primitive type
equals(): overrides Object equals method.

String class

String pool ensures '==' works for string literals (references will point to same object / address in pool)
equals(): can check the value of the String object (String pool ensures == works for string literals) For String, can check value of object

Object class

java Object's default implemenetation of equals() is actually ==

public boolean equals(Object obj) {
  return (this == obj);
}

For custom object to correctly implement the equals() method you MUST override the default implementation.

@Override
public boolean equals(Object o) {
  if (this == o) {
    return true;
  }
  if (o == null || getClass() !=  o.getClass()) {
    return false;
  }
  Simpson simpson = (Simpson) o;
  return age == simpson.age && weight == simpson.weight && name.equals(simpson.name);
}

Reference: GeeksforGeeks & infoworld

How hashmap works internally

Hashamp works on principle of hashing- an algorithm to map object data to some representative integer value
load factor : entries / buckets (0.75)
capacity : number of buckets (16)
threshold : capacity * load factor (12)

In Java, threshold (default) is 12. that means after the 12th kay value air is added, capacity of hashmap will increase (double)

There are two main scenarios in a Java Hashmap

constructing & putting items in (hashMap.put(key,value))
retrieving items from hashmap via key (value = hashMap.get(key))

Constructing HashMap

16 initial buckets
- initial capacity = number of buckets = 16 (new HashMap<>())
default load factor is 0.75
default threshold = 12
- default threshold = 16 * 0.75 = 12
- rehash is performed on 12th key value pair insert
get hashCode of key
- on hashmap.put(key,value), Java calculate hashCode() of key key.hashcode()
calculate bucket index (eg. 6)
- since hashcode may be bigger than number of buckets
- bitwise AND. hashCode AND number of bucket. to determine bucket index to insert key value pair in
Create Node object with key-value pair
- Node like LinkeList

Since hashCodes are not unique, there will be a collision

Collision

get key1.hashCode()
get bucket index of key1 (eg. 6)
there is an object at index 6
check that inserted object and existing one are not equals
- key.equals(key1) to check equality
- if same: replace
- else: collision
Connect node of key1 to node of key via linked list
- keyNode.next = key1Node
- both key-value pairs stored at index 6

As more and more objects are inserted, load factor increases. An increasing load factor means more complex get() / put() which will defeat the great advantage of hashmap (ie. O(1) gets and puts)

To keep load factor low, once treashold is exceed, rehashing occurs

Rehashing

Threshold (12) exceeded
after 12th insert -> rehashing
new Hashmp object created with double the old capacity (so 32 buckets)
repeat hashMap.put(key,value) on all elements of old hashMap.
- all key-value pairs of old hashmap are placed into new hashMap
- must recalculate their hashcode, index
- then insert (linkedlist if collision)

Rehashing process is both space O(number of buckets) and Time consuming O(number of entries).
Therefore, a good balance must be struck between theshold and rehashing.

High threshold
- rarely rehash
- BUT: hashmap load factor is high
- get and put will be complex
Low threshold
- load factor of hashmap is low, will have efficient gets and puts
- rehash very often -> waste time and space

Getting Item from HashMap

Load factor (& hashing function) will affect the complexity of get()
value = hashMap.get(key)

calculate hashCode of key
calculate index of key (eg. 6)
go to bucket of index
compare first Node with key sing equals()
- node.equals(key)
if both are equal: return value
else go down linked list and check if node exists.

Reference: SO answer &&javaconceptoftheday && javarevisited && javacodegeeks && geeksforgeeks && baeldung

Adding Null key to hashmap

only one null key is permitted

hash calculation is not done
(key,value) pair always added to bucket 0

Reference: knpcode

HashSet internal implementation in Java

Hashset uses HashMap internally a dummy object is always added as value to backing HashMap.
HashSet class used to create collection that uses hash table for storage. It contains unique elements only.

Like HashMap,

Capacity = 16
load factor = 0.75
threshold = 0.75 * 16 = 12

add values
HashSet implementation, values are stored as hashmap keys. So set only contains unique elements.
In the underlying hashMap data, a dummy object is always added as value
hashSet.add(element);
underlying implementation is
hashMap.put(element,DUMMY)

get values
there are not values. just use key iterator to get keys
hashMap.keySet().iterator()

you can use hashMap to check if key is present in Set

remove values
same as removing items in hashmap

Reference: knpcode

ArrayList: Capacity VS Size

Capcity: maximum item list can hold before it can be resized
Size: number of itesm in the list.

List<Intger> test = new ArrayList(20);
test.add(1);
test.add(2);
test.add(3);

In this case, capacity is 20, size is 3.

How ArrayList works Internally in Java

Arraylist is resizeable array implementation in java.
backed by an array

default capacity = 10
add(): ensure arraylist has required capacity.
- if capacity exhausted
- new array created with 50% more capacity
- Arrays.copyOf() used to copy elements from old array to new array
remove(): remove element from array
- elements shift to fill gap created by removed element

Reference: GeeksforGeeks & javatpoint & knpcode

Java Vector class

Vector is basically a thread safe arraylist.
Vector is synchronised, can use it in multiple threads.

Vector came first (before arraylist), in jdk since jdk 1.0

Synchronization has an overhead, so if you are not using multiple threads you can use a class without synchronization overhead.

How is stack implemented by Java internally?

Stack is LIFO (last-in-first-out) stack of objects
operations: push, pop, peek, empty, search

No items on stack creation.

implemented with underlying Vector class. Vector is a growable/dynamic array.

This could be due to backwards compatibility (see Quora source)

Reference: SO & Quora & java docs

Queue implementations in Java

Queue is a FIFO (first-in-first-out) data structure
operations: add, remove, element

In java, Queue is an interface.
There is no Queue class, it has to be implemented.

Implementations

LinkedList
PriorityQueue
- based on heap data structure.
- orders elemnts accoridng to order specified at construction time.
- queue retrieval operations (poll, remove, peek) access element at head of queue.
- if mutliple elements are tied for head of queue, tie is broken arbitarrily.

Map Implementation: HashMap, TreeMap, LinkedHashMap

All offer unique key-> value mappings & implement Map interface .
Difference is time guarantees & ordering of keys
HashMap: implemented as hash table & no ordering on keys or values.
TreeMap: implemented based on red-black tree structure, & ordered by the key.
LinkedHashMap: preserves the insertion order
Hashtable: synchronized HashMap.

HashMap
- implemented by array of linked lists
- O(1) look up & insertion
- key orders -> arbitrary
TreeMap
- implemented by Red-Black Tree.
- O(logN) lookup & insertion
- keys orders -> ordered, need to iterate through keys in sorted order
- does not use hashing for storing key-pair values
Linked Hash
- implemented doubly linked list between key-value pairs (on top hashmap implementation) that keeps track of insertion order
- O(1) look up & insertion
- keys orders -> insertion order

Source

LinkedHashmap operations
- on top of hashmap, maintains an additional doubly-linked list to make it "aware" of ordering of key-value pairs

LinkedHashMap, internal implementation Medium article by Anmol Sehgal provides really good explanation of Linked hashamp

TreeMap internal workings
- does not use hashing
- sorts object kyes using red-black-tree algorithm

Reference: oracle docs & GeeksforGeeks & DZone

Set Implementation: HashSet, TreeSet, LinkedHashSet

HashSet -> HashMap
TreeSet -> TreeMap

Reference: oracle docs & GeeksforGeeks

<a name="arraylist-linkedlist-java

">List Implementation: ArrayList VS LinkedList

both implement List
Arraylist: dyamically add & remove items, automatically resizes iteself, elemnts stored in contiguous memory
LinkedList: linear data strucutres, every element is seaparate object with data & address part. elements are linked using points & addresses.

manipulating data like removing data. (arraylist, underlying array everything must shift).

Referece: javatpoint & GeeksforGeeks & Baeldung

What is OOP

OOP is a programming prardigm that relies on the concepts of classes & objects.
Developer will strcuture code in terms of classes & objects

An alternate paradisn is procedural programming.

program is divided into samller parts called mathos
methods are basic entities in this technique
use methods for code reuability

OOP's benefits are

Clear structure for program
Reusable code, Java code is DRY (dont repeat yourself)
code easier to maintain modify & debug

OOP Pillar: Inheritance

Allows classes to inherit features of other classes.

mechanism to create new class by deriving old classs

Inheritance supports reusability

Represents IS-A relationship

Subclasses are IS-A relationship with super class.

public class SuperClass{}
public class SubClass **extends** SuperClass{}

In Java, object class is super class of all objects.

References: javatpoint

Types of Inheritance

5 types

single

class inherit another class

multilevel

chain of inheritance

Corgi extends Dog, Dog extends Animal

heirarchical

2 or more classes inherit single class

multiple (interface)

sub class has >1 super class

hybrid (interface)

mix of 2 or more of above types.

Since java calsses can't support mutiple inheritance, class cannot support hybrid inheritance.

image from simplesnippets

Why Java class cannot support multiple iheritace

reduce complexity / simplify language If sub class (C) inherits 2 classes (A,B). If A & B have same method (testMethod()) & method is called from subclass C.testMethod(). Does subclass implement method from A or B?

references: GeeksforGeeks & javatpoint

Inheritance in Java: OOP

Reference:https://www.geeksforgeeks.org/inheritance-in-java/#:~:text=important%20facts%20about%20inheritance%20in%20java%20

Inheritance in Java done via following:

key words

extends

implements

types of classes

class

interface

abstract class

Important facts

Default super class
- besides object, every Java class has super class
- every class is implicty subclass of objet class
only 1 super class
inherit construcotrs
- cannot inherit super class constructors
- can call super class constructors super() in subclass constructor
private memeber inheritance
- cannot inherit private memebts (fields, methods, nested classes)
- can access / modify private methodss via super class getter / setters (super.getProperty())

What can be done

Inherited fields
- use them
- Declare new field in subclass
inherited methods
- use them
- override them (use same method signature as superclass @Override)
- Hide static methods (use same method signature as superclass static method)
- declare new methods
- write new subclass constructor that uses constructor of superclass (super())
- Call to super() must be first statement in subclass

Extends VS Implements

OOP Pillar: Abstration

process of hiding implementation details & only showing functionality to the user

Abstractions lets developer focus on what an object does instead of how an object is doing it.

Implementation of function is hidden from user.

Reference: SO

OOP Abstraction in Java

Java has 2 ways to achieve abstraction

Abstarct class (0-100%)

Interface 100%

Abstract class
- class declared as abstract
- can have abstarct & non-abstarct methods
- needs to be extended
- child class must implement all its abstarct methods
- cannot be instantiated
- can have constructor, data members, abstract & non-abstarct methods.

abstract class Bike{  
  abstract void run();  
}  
class Honda4 extends Bike{  
  void run(){
  System.out.println("running safely");
}  
public static void main(String args[]){  
   Bike obj = new Honda4();  
   obj.run();   // running safely
 }  
}

Interface
- can only have abstract methods (no method body)
- Java 8 allows default & static methods in interface
- allows multiple inheritance
- class implementing interface must implement all methods declared in interface
- cannot be instantiated
- all fields are public static final

interface Drawable{  
  void draw();  
  default void msg(){
    System.out.println("default method");
  }  
  static int cube(int x){
    return x*x*x;
  }
}  
class Rectangle implements Drawable{  
  public void draw(){
    System.out.println("drawing rectangle");
  }  
}  


Drawable d=new Rectangle();  
d.draw();  // drawing rectangle 
d.msg();  // default method
Drawable.cube(3); // 27

Reference: javatpoint & [javatpoint-interface]

Abstarct Class VS interface

From oracle docs

When to use:

Abstract Class
- share code among closely related classes*
- expect classes extending abstract class have many common methods / fields / require access modifiers other than public (abstract classes can declare non-public methods & fields)
- declare static or non-final fields
Interface
- unrelated classes will implement interface
- use multiple inheritance
- expect API to not change for a while (if change 1 interface method all classes must change)

Reference: techvidvan

OOP Pillar: Encapsulation

OOP technique of wrapping data & code in to achieve data hiding.
technique is
Data hiding: Unauthorized users should not have access to / modify data
Benefits:

flexibility: can decide which variables have read/ write priviledges

control: class can control what is stored in fields (is setter is bad input, reject it)

How does it achieve data hiding?

wrap data (vairables / fields) & code that manipualtes data (methods) together in a single unit
variables are hidden from other classes
variables are onlt accessed through methods in their current class

Code now becomes like a "protective shield" that prevents data from being acessed by unauthorize users / means.

Reference: Educative & javatpoint & GeeksforGeeks & tutorialspoint

Encapsulation in Java

Encapsulation in Java is achieved by

declare fields of class as private

provide public setter an getter methods & modify and fields

public class EncapTest {
   private int age;

   public int getAge() {
      return age;
   }

   public void setAge( int newAge) {
      age = newAge;
   }
}

Tight Encapsulation

Class has only private variables / fields

Reference: SO

OOP Pillar: Polymorphism

ability of object to take on many forms.

Compile-time Polymorphism / Static polymorphism

method overloading

Runtime Polymorphism / Dynamic method dispatch

method overriding In Java, inheritance allows for polymorphism (method overriding)

Compile-time polymorphism (
- static bining / early binding / overloading
- object bound with their functionality at compile time
- call is resolved by the compiler
- Fast execution: method to be executed known early (at compile time)
- less flexible/u>: all things execute at compile time
Run-time polymorphism
- dynamic binding / late binding / overriding
- object bound with functionality at run time
- method invocation is determined by JVM not the compiler
- Slow execution: method to be be executed only known at runtime
- more flexible all things execute at runtime

From: GeeksforGeeks

Polymorphism: Method Overloading

Allows a class to have more than 1 method with:

same name

different number & types of argument list At time of compilation, method calls get resolved by compiler (javac). Also known as: compile-time polymorphism / early binding

There are 2 ways this can be performed

changing number of arguments
changing the data type

public void display(String info){
  System.out.println("String into");
}

// method overloading - change data type
public String display(int info){
  System.out.println(info);
  return "result";
}

public void display(String info1,String info2){
  System.out.println("2 information string");
}

When call display method compiler display results based on the arugments dev pass.

if argument is int
- call display(int)
argument is string
- call display(string)
type promotion can be performed (implicitly) if no matching type is found and if there is no ambiguity.

Type Promotion Example
if not matching data types found, one type promoted to another.

public void sum(int a long b){
  System.out.println(a+b);
}

// second argment (int literal) will be promoted to long. 
sum(20,20); // 40

If there is ambiguity,

no matching type aguments in metho
each method promotes simliar number of arguments

public void sum(int a,long b){
  System.out.println("a method invoked");
}

public void sum(long a,int b){
  System.out.println("b method invoked");
}

//ambiguity
sum(20,20); // Compile Time Error

Now there is amiguity, both methods promote simliar number of arguments.

Benefits:

increase readability of program
- no need to create & remember different names for functions doing the same thing.

Method Overloading Conditions
CANNOT

not possible by changing return type of method only
- if only change return type but ethod signature remains same, there is ambiguity, which method should be called?
can't overload methods that differ only by static keyword
- number of parameters, type of parameters & method name is same
- same method signature -> not overlaoding CAN
can overload main() method
- main() method usually received string array as arguments.
- but can overload main()method to receive no arguments / different arugments
method overloading with type promotion
- one type can be promoted to another implicitly if not matching datatye found.
- one type cannot be de-promoted implicitly.
can overload static method
- can have >=2 static method with same name but difference in input parameters.

reference: javatpoint & GeeksforGeeks

Polymorphism: Method Overidding

allows subclass / child class to provide specific implementation of method that is already provided by by one of its super classes or parent classes
Subclass methods must have

same name

number & type of parameters

retur type JVM does the job of method resolution --> Runtime polymorphism Type of referred object determines which version of an overriden method will be executed

class Base {
  public void show(){}
}

class Derived extends Base {
  // method overriding
  public void show(){}
}

Derived der = new Derived();
der.show();

JVM first checkls if child class (Derived) has provided any implementation to method (show).
yes -> call derived overriden method,
no -> call parent method

Base obj = new Derived();
obj.show();

reference if of Base type, however object is still of Derived type.
Method resolution takes place at runtime.
show method of Derived class is called.

Derived obj = new Base(); // not valid

This is not valid.
Important
Important
type of referred object etermine which version of overidden method will be executed NOT typoe of reference variable.
Runtime object determines which method will be called --> overiding = runtime polymorphism

Rules

MUST have same retur type or at least subtype of parent's return type Exception Handling
super class overriden method does not throw exception
- sub class overridding method can only throw unchecked exception (i.e. exceptions that are not checked at ompile time)
super class overridding method throws exception
- sub class overriding metho can only throw same subclass exception. CAN
override access-modifiers
- can allow more but not less access (eg. protected instance method can be made public but not privde in sub class)
final methods cannot be overidden
- final keyword prevents overriding
call parent class method in overridding method
- super.method()
can override abstarct method
- abstarct methods in interface / abstarct class are menat to be overidden in derived class
can override synchronied / strictfcp method CANNOT
static methods cannot be overridden
- static method bound to class not object
- static method with saae method signature in subclass is method hiding NOT method overidding.
cannot override main method
- main metod is static
private methods cannot be overriden
- private methods not inherited
- private methods bonded during compile time
cannot override constructor
- parent & child constructor can never have same name
- constructors are not inhierited

Reference: GeeksforGeeks & javatpoint

Overriding VS Hiding (static methods)

static methods cannot be overidden. But they can be hidden.
When child class has same static method as parent class. Static method hides another static method.
Difference Overriding gives run-time polymorphism, hiding does not.

Code example and explanation taken from coderanch:

class Foo {
    public static void classMethod() {
        System.out.println("classMethod() in Foo");
    }

    public void instanceMethod() {
        System.out.println("instanceMethod() in Foo");
    }
}

class Bar extends Foo {
    public static void classMethod() {
        System.out.println("classMethod() in Bar");
    }

    public void instanceMethod() {
        System.out.println("instanceMethod() in Bar");
    }
}

class Test {
    public static void main(String[] args) {
        Foo f = new Bar();
        f.instanceMethod(); // instanceMethod in Bar
        f.classMethod(); // classMethod in Foo
    }
}

instanceMethod(overriding): JVM finds actual class of the instance f at run-time and determines which method to run. f is declared as Foo however class created is actually Bar. At run-time, JVM find that f is Bar instance and calls instanceMethod in Bar.

classMethod(hiding): class/static method. JVM wont expect to need an actual instance to invoke method. At compile-time compiler looks at declared type (Foo) of reference to decide which method to call.

Therefore static methods do not have run-time polymorphism.

References: Stack Overflow & CodeRanch

OOP Java: Association

Association is relation between 2 separate classes which establishes through their objects. Can be

one-to-one

one-to-many

many-to-one

many-to-many Composition & aggreagation are 2 forms of association

Aggregation

special form of assocation

Has-A relationship

unidirectional

parent can exist without the child & vice-versa

public class Foo {
  private Bar bar;
  Foo(Bar bar) {
    this.bar = bar;
  }
}

If Foo dies, object Bar can still "live".

Composition

restricted form of aggreagation, 2 entities are highly dependent on each other

*part-of-realtionship

child object cannot exist without parent entity

lifecycle of child is controlled by parent that owns it

public class House {
   private Room room;
   public House() {
       // without a house there can be no room, if house deleted, room is also deleted
       room = new Room();
   }
}

Reference: GeeksforGeeks & infoworld

OOP Java: Coupling

measure of how much class is dependent on other classes
There should be iminmal dependencis -> low coupling

OOP Java: Cohesion

measure of how related responsibilitie of class are
class must be highly cohesive (responsibilties shuold be highly related to one another)

Exceptions handled

Java Exception Handling frameowork handles runtime exceptions only. Compile time exceptions must be handled by developer or else code wont run

Reference: JournalDev

Exception Handling: keywords

throw -throws -try-catch -finally

throw
- used inside function / block of code
- to explicitly throw an exception in the rpgoram
throws
- used in method signature
- declare exception that might get thrown by method & method will not be handling it.
try-catch
- code block for excpetion handling in code
- can have multiple catch blocks with a try block -can be nested
try
- start of block
catch
- end of try block to handle exceptions
- required parameter that should be of type Exception
- java 7 automatic resource management (catch many resource in 1 catch block)
- catch(IOException | SQLException ex){}
finally
- optional
- always gets executed wheter exception occured or not
- onlt NOT executed if exception thrown in finally or if JVM crashes in between (System.exit())
- can be used with try catch block
- since exceptions halts process of execution, may have some resources open that will not get closed, close them in finally block

Java Exception Hierarchy

When exception is raise, an exception object is geting created.
Throwable is parent class of Java Exceptions Hierarchy & has 2 chid objects

Error

Exceptions

checked exceptions

runtime exceptions

Java Exceptions are hierarchichal & inheritance used to categorize different types of exceptions

Errors
- not possible to anticipate or recover from them (fatal)
  - hardware failure
  - OutOfMemoryError
  - StackOverflowError
Exceptions
- errors that can be anticiapted & recovered from
Checked Exceptions
- exceptions checked at compile time
- sually occures when interacting with outside resources
- FileNotFoundException
- IOException
Runtime Exception
- exceptions not checked at compile time
- usually due to bad programming / mistakes
- get element from array but give wrong index
- ArrayIndexOutOfBound, Arithemetic Exception

Java Unchecked VS Runtime Exception

CheckedException:

mandatory to provide try-catch / try-finally block

force by compiler

dealing with outside resoruces / networks Runtime exception: not mandatory

occur during runtime

programming errors

Checked Exception
- if not handled, will result in compile time errors
  - either handle with try-catch/ try-finally block or specify method uses throws
- usually error scenarios outside immediate control of program
- usually interacting with touside resources /networks
  - data base / network
- eg.ClassNotFoundException, IOException, SQLException, FileNotFound
RuntimeException
- not checked by compiler
- will occur once buggy code is executed
- method not forced to delared unchecked exception thrown
- eg. ArithmeticExcetion, ArrayStoreException, NullPointerException

Extend from CheckedExcetion or Runtime Excpetion?
Checked Exception

method likely to fail
Checked Exception to ensure alternalte processing in case of failure (enforces proper error handling) Runtime Exception

BUT

can make code ugly (lots of boilerplate code)

reference: GeeksforGeeks VS java67 & javadocs

Java Exception Class Methods

all methods depend on parent Throwable class

String getMessage()

String getLocalizedMessage()

synchronized Throwable getCause()

String toString()

void printStackTrace()

getMessage()
- message String of Throwable
- message provided when creating exception through constructor
getLocalisedMessage()
- subclass can override it to provide locale-specific message to calling program
getCause()
- cause of exception or null if cause is unnown
toString()
- name of throwable class & localised message
printStackTarce()
- prints the stack trace information to the standard error stream
- is overloaded and can pass PrintStream or PrintWriter as an argument to write the stack trace information to file or stream

Java Exception Handling Criteria

ALLOWED

finally can still be executed if try & catch have return statements
try without catch is allowed (try{}finally{})

NOT ALLOWED

try without catch & without finally

Java Exception Handling Best Practice

Use Specific Exceptions
- dont throw base exception class
throw early / fail fast
- throw exception as early as possible
catch late
- throw exception to caller
- let caller decide how to handle & caller can get notification for exception
closing resources
- close all resources i finally block
- java 7 try-with-resources block
- eg. try (Scanner scanner = new Scanner(new File("test.txt"))) {scanner.doSomething()}
log exceptions
- log exception messages when throwing exceptions
single catch block for multiple exceptions
- catch(SQLException|AnotherException ex){}

Reference: JournalDev

UML Class Diagram

Designing the class

Association

very generic term
one class used functionalities provided by another class

Composition

part-of

Aggregation

one object "owns" another object but child can exist without parent

Multiplicty

Generalization / Inheritance / Abstraction

source

UML Sequence Diagram

denote how objects and classes with code interact with each other
show sequence of the events

OOP: Design Patterns

basket of pre designed solutions / blueprints to common patterns in OOP or to solve given design problem in code.

Creational: creating objects
Structural: composition of classes & objects which form larger structures
Behaviour: responsibility & interaction between objects

Singleton Design Pattern

restricts instantiation of class to one. Ensure only 1 instance of class exists in JVM.
Used for: logging, drivers object, cahcing & thread pool.
Implementation

private construtor to restrict instantiation of class from other classes

private static variable of same class that is only instance of class

public static method getInstance() returning instance of class, so other classes can get instance of singleton

Techniques:

Eager initialization - create singleton BEFORE its used
- public static final SingletonClass instance = new SingletongClass()
- use static block
Lazy Initlialization
- creates instance in getInstance() method. can cause issues in multithreaded environment
Thread Sage singleton (for laxy initialization)
- make getInstance() method synchronized so only 1 thread executes this method at a time
use Enum to declare singleton
- Java ensures any enum value only instantiated once. does not allow lazy initialization. public enum EnumSingleton{INSTANCE;}
Serialization & singleton
- implement readResolve() method. When implement serializable interface, when deserialize singleton class, new instance of object is created. protected Object readResolve() {return getInstance()}

Reference: vainolo & journalDev

Factory Design Pattern

define an interface or abstract class for creating an object but let the subclasses decide which class to instantiate
Responsibility of instantiation is on factory class not client program.

Implementation

super class (Computer) can be interface , abstart class or normal class
Factory class can be singleton or can keep the method returning classes (getComputer) as static.
- very troublesome to keep instantiating factory clas
based on input parameter, different subclass created & returned

public class ComputerFactory {

    public static Computer getComputer(String type, String ram, String hdd, String cpu){
        if("PC".equalsIgnoreCase(type)) return new PC(ram, hdd, cpu);
        else if("Server".equalsIgnoreCase(type)) return new Server(ram, hdd, cpu);

        return null;
    }
}

Advantage

remove instantiation of actual classes from client code
layer of abstraction between implementation classes(PC & Server) & client code (ComputerFactory

Abstract Factory
Abstarct factory is like a factory of factories.

Reference: javatpoint& JouralDev & tutorialspoint

Decorator Design Patterns

Add new features to existing object with changing its structure
Decorate class wraps original class & provides additional functionality, keeping class methods signature intact

uses abstract classes or interface with **composition* to implement*

Decorator class implements HAS-A relationship with component interface. Concrete Decorators will extend base decorator functionality & modify component behaviour.

// Component Implementations
public class BasicCar implements Car {

    @Override
    public void assemble() {
        System.out.print("Basic Car.");
    }

}

// Decorator
public class CarDecorator implements Car {

    protected Car car;

    public CarDecorator(Car c){
        this.car=c;
    }

    @Override
    public void assemble() {
        this.car.assemble();
    }

}

// Concrete Decorator
public class SportsCar extends CarDecorator {

    public SportsCar(Car c) {
        super(c);
    }

    @Override
    public void assemble(){
        super.assemble();
        System.out.print(" Adding features of Sports Car.");
    }
}
public class LuxuryCar extends CarDecorator {

    public LuxuryCar(Car c) {
        super(c);
    }

    @Override
    public void assemble(){
        super.assemble();
        System.out.print(" Adding features of Luxury Car.");
    }
}

// Testing Decorator Program
Car sportsCar = new SportsCar(new BasicCar());
sportsCar.assemble(); 
// Basic Car Adding features of Sports Car
        System.out.println("\n*****");

Car sportsLuxuryCar = new SportsCar(new LuxuryCar(new BasicCar())); sportsLuxuryCar.assemble(); 
// Basic car. Adding features of Luxury Car. Adding Features of SportsCar.

Reference: Baeldung & tutorialspoint & JournalDev

Flyweight Design Pattern

factory which recycles created objects by storing them after creation. Existing object is returned otherwise new one created.
Flyweight objects must be immutable, any operation on state must be performance by factory.
Benefits

decrease memory footprint

increase performance

When to use

number of object to be created by application should be huge
object creation heavy on memory & can be time consuming
flyweight object must be divided into intrinsic & extrinsic. Intrinsic properties make object nuique, extrinsic properties are set by client code & used to perform different operations.

Reference: Baeldung & tutorialspoint & JournalDev

Adapter Design Pattern

act as connector between 2 incompatible interfaces that otherwise cannot be connected directly.
2 implementations

class adapter

uses inheritance & extends adaptee interface

single class called adaptor between 2 incompatible interfaces

object adapter

uses composition & adapter contains adaptee object.

wraps around class, allowing 2 classes / interface to work together without changing any code on either side.

Object Adapter

Client can only see target
adapter class implements target interface & provides implementation for Request()
adapter is composed with adaptee

Process

Client makes call to adapter
adapter does conversion
makes rqeuired call to adaptee

public class SocketObjectAdapterImpl implements Targer{

//Using Composition for adapter pattern
    private Adaptee sock = new Adaptee ();

    @Override
    public Volt get120Volt() {
        return sock.getVolt();
    }

    @Override
    public Volt get12Volt() {
        Volt v= sock.getVolt();
        return convertVolt(v,10);
    }

    @Override
    public Volt get3Volt() {
        Volt v= sock.getVolt();
        return convertVolt(v,40);
    }

    private Volt convertVolt(Volt v, int i) {
        return new Volt(v.getVolts()/i);
    }
}

Class Adapter

adaptor implements target
inherits adaptee

Process

Client makes call to adapter
adapter DOES NOT delegate request to adaptee
adapter uses inherited method (SpecificRequest()) from adaptee to handle specific request

//Using inheritance for adapter pattern
public class SocketClassAdapterImpl extends Adaptee implements Targer{

    @Override
    public Volt get120Volt() {
        return getVolt();
    }

    @Override
    public Volt get12Volt() {
        Volt v= getVolt();
        return convertVolt(v,10);
    }

    @Override
    public Volt get3Volt() {
        Volt v= getVolt();
        return convertVolt(v,40);
    }

    private Volt convertVolt(Volt v, int i) {
        return new Volt(v.getVolts()/i);
    }

}

JournalDev & GeeksforGeeks

Observer Design Pattern

one-to-many dependency between objects so when 1 object (subject) changes state, all of its dependents (observers) are notified & updated automatically.

eg. wishlist item is out of stock, tell website to notify you when it is in stock.

// subject
public interface Subject {

//methods to register and unregister observers
  public void register(Observer obj);
  public void unregister(Observer obj);

//method to notify observers of change
  public void notifyObservers();

//method to get updates from subject
  public Object getUpdate(Observer obj);
}

// object
public interface Observer {

//method to update the observer, used by subject
public void update();
// observers will print updated subject in this method

//attach with subject to observe
public void setSubject(Subject sub);
}

public class MyTopic implements Subject {

    private List<Observer> observers;
    private String message;
    private boolean changed;
    private final Object MUTEX= new Object();

    public MyTopic(){
        this.observers=new ArrayList<>();
    }
    @Override
    public void register(Observer obj) {
        if(obj == null) throw new NullPointerException("Null Observer");
        synchronized (MUTEX) {
        if(!observers.contains(obj)) observers.add(obj);
        }
    }

    @Override
    public void unregister(Observer obj) {
        synchronized (MUTEX) {
        observers.remove(obj);
        }
    }

    @Override
    public void notifyObservers() {
        List<Observer> observersLocal = null;
        //synchronization is used to make sure any observer registered after message is received is not notified
        synchronized (MUTEX) {
            if (!changed)
                return;
            observersLocal = new ArrayList<>(this.observers);
            this.changed=false;
        }
        for (Observer obj : observersLocal) {
            obj.update();
        }

    }

    @Override
    public Object getUpdate(Observer obj) {
        return this.message;
    }

    //method to post message to the topic
    public void postMessage(String msg){
        System.out.println("Message Posted to Topic:"+msg);
        this.message=msg;
        this.changed=true;
        notifyObservers();
    }

}

//create subject
MyTopic topic = new MyTopic();

//create observers
Observer obj1 = new MyTopicSubscriber("Obj1");
Observer obj2 = new MyTopicSubscriber("Obj2");
Observer obj3 = new MyTopicSubscriber("Obj3");

//register observers to the subject
topic.register(obj1);
topic.register(obj2);
topic.register(obj3);

//attach observer to subject
obj1.setSubject(topic);
obj2.setSubject(topic);
obj3.setSubject(topic);

//check if any update is available
obj1.update(); // Obj1:: No new message

//now send message to subject
topic.postMessage("New Message");

// OUTPUT
Message Posted to Topic:New Message
Obj1:: Consuming message::New Message
Obj2:: Consuming message::New Message
Obj3:: Consuming message::New Message

Mutex subject in code snippet is used for locks

Sequence Diagramm

Reference: vogella & JournalDev & Baeldung & tutorialspoint

Strategy Design Patterns

class behaviour or algorithm can be changed at runtime.
eg. Collections.sort()
2 ways:

interface & implement many times

start with interface which is used to apply an algorithm

implement it multiple times for each possible algorithm

Java 8 & lambdas

use lambda in place of anonymous inner type

Interface & Implementations

// Startegy interface
public interface Strategy {
   public int doOperation(int num1, int num2);
}

// Startegy concrete classes
public class OperationAdd implements Strategy{
   @Override
   public int doOperation(int num1, int num2) {
      return num1 + num2;
   }
}
public class OperationSubstract implements Strategy{
   @Override
   public int doOperation(int num1, int num2) {
      return num1 - num2;
   }
}
public class OperationMultiply implements Strategy{
   @Override
   public int doOperation(int num1, int num2) {
      return num1 * num2;
   }
}

// use context to call & execute startegy interface
public class Context {
   private Strategy strategy;

   public Context(Strategy strategy){
      this.strategy = strategy;
   }

   public int executeStrategy(int num1, int num2){
      return strategy.doOperation(num1, num2);
   }
}

Context context = new Context(new OperationAdd());      
      System.out.println(context.executeStrategy(10, 5)); // 15

context = new Context(new OperationSubstract());        
      System.out.println(context.executeStrategy(10, 5)); //5 

context = new Context(new OperationMultiply());     
      System.out.println(context.executeStrategy(10, 5)); // 50

Using Java Lambdas
Java 8 can create static methods in interfaces

public interface Discounter {
    BigDecimal applyDiscount(BigDecimal amount);

    static Discounter christmasDiscounter() {
        return amount -> amount.multiply(BigDecimal.valueOf(0.9));
    }

    static Discounter newYearDiscounter() {
        return amount -> amount.multiply(BigDecimal.valueOf(0.8));
    }

    static Discounter easterDiscounter() {
        return amount -> amount.multiply(BigDecimal.valueOf(0.5));
    }
}

Sequence Diagram

Reference: Baeldung & tutorialspoint & JournalDev

State Design Patterns

allows object to change its behaviour (during run time) when the internal state of the object changes.

used when: object depends on its state & behaviour must be changed during run time depending on its internal state. Implementation allow object to change its behaviour without changing its class

Context object will change its behaviour based on its internal state.
Context object will have an associated state which can change during program execution
Context will delegate behaviour to state implementation.

Example: TV remote can be on or off

// Staet interface 
public interface State {
    public void doAction();
}

// State implementations
public class TVStartState implements State {

    @Override
    public void doAction() {
        System.out.println("TV is turned ON");
    }

}

public class TVStopState implements State {

    @Override
    public void doAction() {
        System.out.println("TV is turned OFF");
    }

}

public class TVContext implements State {

    private State tvState;

    public void setState(State state){
        this.tvState=state;
    }

    public State getState() {
        return this.tvState;
    }

    @Override
    public void doAction() {
        this.tvState.doAction();
    }

}


TVContext context = new TVContext();
State tvStartState = new TVStartState();
State tvStopState = new TVStopState();
            context.setState(tvStartState);
context.doAction(); // TV is turned on  
        context.setState(tvStopState);
context.doAction(); // TV is turned off

Reference: Baeldung & tutorialspoint & JournalDev & DZone

RDBMS Theory

limjy — Wed, 12 May 2021 18:48:19 +0000

References:
https://www.educba.com/rdbms-interview-questions/
https://www.educba.com/dbms-keys/?source=leftnav
https://www.guru99.com/dbms-keys.html
https://www.studytonight.com/dbms/database-key.php
https://www.geeksforgeeks.org/types-of-keys-in-relational-model-candidate-super-primary-alternate-and-foreign/

Features

Name
- name of table
attribute
- column
tuple
- row in the table

E-R & OO Model

Entity-Relationship model & Object oriented model

E-R
- top-down approach
- real life scenarios are entityes
- properties & attributes in ER diagram & connections
Object oriented
- scenarios are objects
- objects with similar functionalities are grouped together & linked to different other objects

reference

Levels of Data Abstraction

Physical Level
- how data is stored
Logical Level
- what type of data stored &
- relationship between data
View Level
- entire DB

Types

In memory
- redis
- memcache

in-memory DB can be made persistent with transaction log
https://medium.com/@denisanikin/what-an-in-memory-database-is-and-how-it-persists-data-efficiently-f43868cff4c1

Keys Function

help uniquely rows of data in table
establish relationship between tables

Types of Keys

Super key
- group of single OR multiple keys which identifies rows in table
Candidate key
- super key but without attributes not important for uniquely identifying tuples/ rows.
- subset of super key
- can be >1 candidate key for a table
- cannot be NULL or empty.
- can be a combination of >1 attributes
Primary key
- uniquely identify each record in a table
- cannot be NULL
- cannot have duplicate values
Composite Key
- consists of >=2 attributes that uniquely identify any record in a table
- attributes forming composite key are not a key individually
- individual key cannot be foreign key
Foreign key
- column creating relationship between 2 tables
Alternate key
- candidate keys other than primary key
Compound key
- >=2 attributes that can uniquely identiy records.
- any part can be foreign key
Surrogate key
- artificial key which aims to uniquely identify each record
- its only purpose is to be unique identifier (eg. incremental key,
- it has no actual meaning
- eg. incremental key, time stamp
- used when:
- no property has the parameter of primary key
- primary key is too big or complicate

Further reading
https://www.tutorialspoint.com/Surrogate-Key-in-RDBMS
https://www.hackertrail.com/talent/database/sql-interview-questions-answers/

Transactions

logical unit of processing
entails one or more database access operation.

successful transaction can change database from one consistent state of anther
if DB is in inconsistent state before transaction it will be in inconsistent state after reference

Transaction Operations

Transactions access data in 2 ways
READ: read value from DB store in a buffer in main memory
WRITE: write value back to database from buffer

However transaction may fail before all operations in it are finished (due to hardware / software / power failure).

So there are two operators

Commit: save work done permanently
Rollback: undo work done

reference

Transaction Operations

To maintain consistency in database before & after transaction ACID properties are followed

Atomicity
- transaction takes place at once or not at all
Consistency
- DB must be consistent before and after transaction
- eg. if operations of add & subtract are executed concurrently, DB may be inconsistent (transactions may read different values)
Isolation
- result of transaction should not be visible to others before transaction is committed
Durable
- once database committed transaction, changes made by transaction should be permanent

Inconsistency Example

References:
https://www.geeksforgeeks.org/concurrency-control-in-dbms/?ref=lbp
https://www.geeksforgeeks.org/acid-
properties-in-dbms/

Transaction Schedule

series of operations from 1 or more transactions

Serial
- 1 transaction completely executes before starting another
Concurrent
- operations of transaction are interleaved with operations of other transactions of a schedule

Transaction Isolation Levels

part of ACID properties
Isolation Level define degree to which transaction must be isolated from data modification made by any other transaction in database system

Isolation levels determine by following phenomena

Dirty Read
- transaction reads data not yet commited
Non Repeatable read
- transaction reads same row twice gets different value each time
Phantom Read
- 2 same queries executed but rows retrieved by two are different.

There are 4 isolation levles

Read Uncommitted
- lowest isolation level
- allow dirty reads (1 transaction can read uncommitted changes made by other transactions)
Read Committed
- no dirty read
- any data read is committed the moment it is read
Repeatable Read
- most restrictive
- holds read locks on all rows it references and write locks on al rows it inserts / updates / deletes
- other transactions cannot read update or delete rows -> avoid non-repeatable read.
Serializable
- highest isolation level
- transaction will be serially executed

DB recovery

recovery techniques are heavily dependent on existence of system log
System log keeps track of all transaction operations that affect DB value
information is needed to recover from transaction failure.

Operating System

limjy — Sun, 09 May 2021 18:08:23 +0000

My summary of Operating system self study

Static RAM (SRAM)
- used to build cache memory
- memories that consist of circuits capable of retaining state as long as power is long
- fast
Dynamic RAM (DRAM)
- used for main memory (were currently opened programs / processes reside) vairable & state data / OS all are in DRAM
- stored information tends to loose over period of time. capacitor must be periodically recharged to retain usage.
- less expensive than SRAM

Further reading
https://www.quora.com/What-is-the-difference-between-DRAM-cache-memory

OS: Logical VS Physical Address

logical address: generated by CPU when program is running. It does not exist physically. Used as reference to access physical memory location by CPU
physical address: physical location of required data in memory. User never directly deals with physical address but can access it by logical address.

Logical address is mapped to physical address by MMU (memory management unit)

WHY

isolaiont & protection
- Logical / Virutal address are needed to ensure secure memory management. If processes can directly modify physical memory they can potentially disrupt other processes. (see SO answer)
ease of use
- OS give each program the view that it has large contiguous address space to put code and data in, programmers need not worry about memory space / addresses.

taken from geeksforgeeks

CPU Virtualization

Each process access its own private virtual address space which the OS maps to the physical memory of the machine.
As far as the running program is concerned it has physical memory all to itself. however, in reality the physical memory is shared amongst all processes and managed by the OS.

User often runs >1 program at once. User is never concerned with whether CPU is available, only with running programs. --> illusion of many CPUs.

OS creates illusion by virtualizing CPU.

Time sharing
- run 1 process, stop it & run another (implemented via context-switching)

OS also has policies

Scheduling policy
- given number of possible programs to run on CPU, policy decides which program OS should run.

Time Sharing

In multiprogramming multiple processes are ready to run at given time, OS will switch between them.

Time-sharing

run 1 process for a short while
- give it full access to all memory then stop it, save all state to some kind of disk load other process's state, run it fr a while
- very slo
- saving entire contents to disk is very slow
leave process in memory while switching between them
- OS can implement time sharing efficiently
- with multiple programs residing in memory concurrently, protection is important, process should not be able to read or write other process's memory.

Address Space

address space is OS abstraction of physical memory that is easy to use

Address space of process contains all memory state of running program

code
- instructions for program will be in memory
stack
- keep track of where program is in the function
- allocate local variables
- pass parameters
heap
- dynamically-allocated / user-managed memory
- eg. creating new object in Java

Stack VS heap memory

Stack

stores temporary values created by function

when task completed memory is automatically erased

contains methods/ local variables reference variables Heap

store global variables / static variables

Heap has nothing to do with data structure

Stack

only access from top (push and pop top one)
quick access speed

Heap

can take data out from anywhere --> fragmentation

https://icarus.cs.weber.edu/~dab/cs1410/textbook/4.Pointers/memory.html
https://www.guru99.com/stack-vs-heap.html

Virtualization

virtualizing memory is when OS provides layer of abstraction to running program.
The running program thinks it is loaded into memory at particular address and has potentially very large address space but the reality if quite different.

Address Traslation: MMU

Address tarnslation: converting hardware address to virtual address to program is done by *memory management unit (MMU)

Technique is dynamic relocation There are two hardware registers. one base & one bounds / limits.
The base-and-bounds register will allow OS to place address space anywhere in physical memory.

In virutal memory there is 0-16KB memory. base and bounds register will put it in 32KB-48KB of physical address.

Segmentation: Generalized Base / bounds

instead of having 1 base/bounds pair. Have a base/bounds pair per logical segment of address space. (code, stack & heap)

Must keep track of each segment + direction it grows (stack grows backwards)

Fragmentation

physcial memory becomes full of little holes of free space making it difficult to allocate new segments or grow existing ones
Problem because of segmentation

In simple MMU, each address space is same size so physical memory is just a bunch of slots where processes fit in
In segmentation, there are many segments / process and each segment is different size
Physical memory can become full of little holes

Solutions

Compact physical memory
- compact physical meory by rearranging exisiting segment
Management algorithm
- algo that tries to keep large extents of memory available for allocation
- eg. best-fit / worst-fit / buddy algorithm

external fragmentation will always exists algos will just minimize it.

Paging

Virtual memory: address space is divided into fixed-sized pieces.
as opposed to diving it into some number of variable-sized logical segments
Physical Memory: physical memory is now viewed as fixed-sized slots called page frames each frame contains a single virtual-memory page.

This helps prevent fragmentation which occurs when dividing space into different-size chunks (as in segmentation)

Pages in virtual address space will be places at different locations throughout physical memory

Advantages

flexibility
- can effectively support abstraction of address space. no need to make assumption about direction of heap / stack
simplicity
- OS needs to place 4 page of address space in eight page of physical memory, It just find 4 free pages.

Disadvantages
can be slow

hardware must know where page table for currently running process is
fetch proper page table entry from process's page table
perform translation of virtual memory to physical memory
load data from physical memory

Page Table

Used for address translations
It is a per process data stricture that records where each virtual page of address space is places in physical memory

Its per-process. If another process were to run OS will have to manage different page table for it since virtual pages will map to different physical page (isolation --> no sharing of memory)

Virtual Address -> Physical Address

address split into 2 parts:

VPN: Virtual Page Number
offset: offset within the page (which byte within the page)

In converting.

VPN. converted to PFN (physical fram / page number)
offset: not changed.

Page Table Contents

page table is just data structure mapping virtual address to physical address. simplest one can be linear page table (array)

Each page table entry (PTE) can include

protection bit
- page can be read / written / exeucted
present
- page is in physical memory or on disk (i.e. it's swapped out)
dirty
- page modified since it was brought into memory
reference bit
- track if page was accessed, determine which pages are popular and should be kept in memory --> useful for page replacement

TLB

translation lookaside buffer(TLB) is part of chip's MMU. It is a address-translation cache.
It's a hardware cache for popular virtual-to physical address translations

will speed up address translations & paging

Context Switch
address translation only valid per process. to handle this,

OS flush TLB on context switch
hardware support
- provide address space identifier (something like process identifier (PID)) in TLB

Virtual Memory: Secondary memory

https://www.geeksforgeeks.org/virtual-memory-in-operating-system/

Virtual Memory is a storage allocation scheme in which secondary memory can be addressed as though it were part of main memory

To support many concurrently-tuning large address spaces, we can use secondary memory (hard disk). OS can make use of this larger, slower device to provide the illusion of large virtual address sapce.

Further Reading:
https://www.guru99.com/virtual-memory-in-operating-system.html
https://www.geeksforgeeks.org/virtual-memory-in-operating-system/

Swap Space

Swap Space is space reserved on the disk for moving pages back and forth
OS will need to remember disk address of given page

proc 0-2 are actively sharing physical memory only some of their valid pages are in memory others are in swap space on disk.
Proc 4 has all ages swapped out to disk and isn't currently running.

Page Fault

process accesses a memory page that is mapped to virtual address space but not loaded in physical memory.

Remember that in Page table Entry (PTE) there is a present bit, which represents if page table is present in physical memory.

OS handles page fault (page-fault handler)

If page is not present and has been swapped to disk, OS will need to swap page into memory to service the page fault.

Page Replacement

https://www.geeksforgeeks.org/page-replacement-algorithms-in-operating-systems/

Page Replacement Policy When physical memory is full, OS must pick a page to kick out/ replace to make room to page in a page from swap space

FIFO

Optimal Page Replacement

kick out page that would not be used for the longest duration of time in the future.

LRU (least recently used)

kick out page that has been least recently used

Paging: Putting it all together

what happens when program fetches some data from memory?

Find VPN from virtual address
Check TLB (cache) to translate VPN to PPN
- TLB Hit (cache hit)
- physical address = PPN + offset
- TLB miss
- check page table entry(PTE) in page table
- PTE.present
  - grab PPN from PTE and retry
- PTE is absent (page fault)
  - OS page fault handler
  - find physical frame for page to be in
  - No page
  - Wait for replacement algorithm to kick out page
  - Read page in from swap space

Process

Process is a program in execution.

When write program in java & compile. Compiler creates binary code. Original code & binary code -> program. When u run the binary code -> process.

Process is 'active' program is 'passive'

In Memory

States

Context Switching

process of saving context of 1 process & loading context of another process

loading & unloading process form running state to the ready state

occurs when:

process with higher priority then running process comes to ready state
interrupt occurs
CPU scheduling

Thread

unit of execution within a process.
Threads are executed one after another but gives the illusion as if they are executing in parallel.
Threads are not independent of each other. they share code data OS resources.
Lightweight: have own stack space but can access shared data

Each thread has:

a program counter
a register set
a stack space

Two types of thread:

User level thread
Kernel level thread https://www.geeksforgeeks.org/threads-and-its-types-in-operating-system/

Multithreading
thread is known as a lightweight process.
Achieve parallelism by dividing a process into multiple threads.

2 types of threads

User level thread
kernal level thread

User VS Kernel level thread

user level - user managed threads
kernel level - OS managed threads acting on kernel on OS core.

https://www.tutorialspoint.com/operating_system/os_multi_threading.htm

MultiThreading

concurrency
Multithreaded process on single processor
processor switches execution resources between threads resulting in cocurrent execution
concurrency means more than 1 thread is making progress but threads are not actually running simultaneously. switching happens quick enough that threads might appear to run simultaneously.

Multithreaded process in shared-memory multiprocessor environment
Each thread in process can run concurrently on separate processor resulting in parallel execution. (when number of threads in process <= number of processors available)

concurrency: interleaving threads in time to give appearance of simultaneous execution
parallelism: genuine simultaneous execution

https://docs.oracle.com/cd/E19253-01/816-5137/mtintro-25092/index.html

MultiThreading models

system to support kernal and user thread in combined way

many to many model
- multiple user threads -> same / lesser kernel threads
- user thread blocked can schedule other user thread to other kernel thread
many to one model
- multiple user thread -> one kernel thread
- user makes blocking system call, entire process blocks
- one kernel thread & only 1 use can access kernel at a time -> multiple threads cannot access multiprocessor at same time
one to one model
- 1-1 relationship for user and kernel thread
- multiple thread can run on multiple processor
- creating user thread requires corresponding kernel thread.

Process VS Threads

Threads within same process run in shared memory space.
Process run in separate memory space

Threads are not independent of one another like processes, threads share with other threads OS resources
Like process, threads have their own program counter (PC), register set & stack space.

reference
blackblaze has a really comprehensive read and is where the pictures in this section are from

Computer Networks

limjy — Wed, 05 May 2021 15:52:53 +0000

Should be a short summary / quick cramming guide for Computer networks since i forgot everything from my networks course

only doing PART of application & network layer from TCP/IP model.

references:
https://www.homenethowto.com/
^ This provides a really good, simple concise introduction.
https://www.geeksforgeeks.org/computer-network-tutorials/#basics
https://www.geeksforgeeks.org/commonly-asked-computer-networks-interview-questions-set-1/
http://www2.ic.uff.br/~michael/kr1999/0_0-Contents.htm
Book: Computer Networking A Top-down Approach

Network: two or more devices connected through a link
link: communication pathway that transfer data from one device to another

Host name
each device in network is associate with a unique device name called hostname
IP Address
Internet Protocol address.
network address of the device across the network. to identify each device in www assigns IPV4 address as unique identifier to each device on internet
IPV4 - 32 bits
IPv6 - 128 bits
MAC Address
Media Access Control address / physical address assigned to Network Interface Controller / Card.

MAC address assigned by manufacturer of hardware interface IP address assigned by network administrator / ISP
MAC address defines device identity, IP describes how devices are connecte to internet
MAC: broadcasting. IP: broadcasting / multicasting
MAC: implement in data-link layer. IP: implemented in Netwrok layer reference

Port
logical channel through which data can be sent/received to an application

Protocol

format and the order of messages exchanged between entities, & actions taken on the transmission
and/or receipt of a message or other event.

set of rules defining how entities communicate

Network Topology

Network Topology is the arrangement with which computer systems or network devices are connected to each other.

See reference

Types of Networks

LAN -- local area network. covers smallest area
MAN -- Metropolitan are network. cover larger area than LAN smaller area then WAN
WAN -- Wide Area network. covers largest area. any network whose communications link cross metropolitan, regional or national boundaries.

media for data tranmission

LAN: Wifi/ Ehternet cables
MAN: modem & wire / cable
WAN: leased telephone lines / satellite links

Examples

LAN: usually group of computer / network devices connecte together usually within same building
MAN: spans several buildings
WAN: internet

See reference & examples

Line Configuration

For communication to occur, two deivces must be connected in some way to same link at same time. There are two possible types of connections:

point-to-point connection
multipoint connection

source

point-to-point connection

dedicated link between two devices
entire capacity is reserved for transmission between 2 devices

multipoint / multidrop connection

also called "Broadcast network"
packet transmitted by sender is received and processed by every device on link. But by address field in packet receiver determines whether the packet belongs to it or not.
2 or more devices share single link
capacity is shared spatially or temporal
spatial sharing - devices share link simultaneously
temporal sharing - users take turns using the link

Transmission Modes

transferring of data between two devices also known as communication mode

Simplex
half-duplex
full duplex

Simplex

communication is unidirectional
only one of two devices on link can transmit, other can receive
uses entire capacity of channel to send data in 1 direction

eg. keybord & monitor. keyboard only introduce input, monitor only give output

Half-Duplex
each station can transmit and receive but not at same time. When 1 send, other canon only receive.
Entire capacity of channel utilized for each direction
eg. walkie talkie. must say "over" so other person can speak

Full Duplex

both can transmit and receive simultaneously
signals going in 1 direction share capacity of signals going in other direction
link contains 2 physically separate transmission paths (one for sending other receiving)
capacity divided between signals

e.g. landline. both can talk and hear and talk over each other lmao.

Delay, Loss & Throughput

This slides provides a really great concise overview.

Delay

how long will it take for packet to travel from point A to point B

Processing Delay - time to examine packet's header and determine where to direct packet
Queuing delay - packet waits to be transmitted onto link
transmission delay - amount of time required to push / transmit all of packet's bits into link eg. if Ethernet link rate is R=10Mbps & length of packet is L bits. transmission delay is L(lenght of packet)/R (rate)
propagation delay - time required to propagate from beginning to link to router B. depends on physical medium of link

transmission VS propagation delay
transmission: amount of time required for router to push out packet. (function of packet's length & transmission rate of link, nothing to do with distance between routers)
propagation: time taken to propagate from one router to next
(function of distance between routers, nothing to do with packet's length / transmission rate of link)

Packet Loss

If packet arrives to a full queue, the router will drop it since there is no place to store packet

Throughput

Instantaneous Throughput - rate (in bits/sec) at which Host B is receiving file / packet
average throughput amount of bits recevied (F) / time taken for Host B to receive all bits (T) = F/T

bottleneck link
for two link network, throughput is limited by the minimum throughput of both links. Otherwise known as bottleneck link

throughut is min{Rs,Rc}. min is the bottleneck link

Socket

Interface between application layer and transport layer
eg. When process wants to send a message to another process on another host, it
shoves the message out its door (socket). Other process received message through door (socket) and acts on it.

HTTP

HyperText Transfer Protocol. is a stateless protocol

client program - browser, browser implement client side of Web
server program - Web server implement server side of HTTP, house Web objects each addressable by URL.

client and server program executed on different end systems talk to each other by exchanging HTTP messages.

HTTP uses TCP as underlying transport protocol

client initiate TCP connect with server
Browser & server processes access TCP via socket interface

TCP provides reliable data transfer service to HTTP, so each HTTP request response message sent by server eventually arrives intact at client.

layered architecture
HTTP need not worry about lost data or the details of how TCP recovers from loss or reordering of data within the network. That is the job of TCP and the protocols in the lower layers of the protocol stack

stateless
HTTP server maintains no information about client. if client asks for same object, server will server it will not response saying it just served object to client.

Persistent (long) VS non-persistent (short) connection

HTTP client & server will communicate for extended amount of time. must decide send each request/response over separate (non-persistent) OR same (persistent) TCP connection

pipelining

requests for objects can be made back-to-back without waiting for replies to pending requests

default HTTP mode uses HTTP with pipelining & connection closes when not used for certain time

persistent VS non-persistent

brand new connection established and maintained for each requested object. TCP buffers allocated TCP variable allocated in both server & client --> burden
each object suffer delivery delay of 2 RTT - 1 RTT to establish TCP connected 1 RTT to request & receive object.

reference

Cookies

Website needs to identify users & serve content as function of user identity.

HTTP VS HTTPS

HTTPS (or rather SSL) is a transport layer protocol, HTTP is a application layer protocol
HTTP transfer data in plain text HTTPS transfer data encrypted. hacker can read sensitive data or modify data, entities communicating will be none the wiser
HTTPS is slower since it consumes computation power to encrypt communication channel
independent authority (certificate authority, CA) verifies identity of certificate owner. over HTTPS, one cannot impersonate.
HTTPS can't stop stealing confidential information from pages cached in browser

reference

HTTPS

Details in this section taken from cloudflare

TLS is an encryption protocol designed to secure Internet communication. During TLS both parties exchange messages to acknolwedge eahc other, verify each toehr & establish encryption algos & agree on session keys
TLS handshakes are a foundational part of how HTTPS work.

Process

Client Hello
- client initiates by senidng "hello" along with:
- TLS version client supports
- ciper suite supported &
- client random (string of random bytes)
Server Hello
- Server's SSL cert
- Server's chosen cipher suite
- server random
Authenticaion
- client verfies server SSL cert with cert authority (CA)
premaster secret
- client sends premaster key (random string of bytes)
- premaster key is encrypted with server public key (can only be seen by server)
Session keys created
- BOTH client & server generate session keys from
- client random
- server random
- premaster key
Client ready
- client sends "finished" encrypted with session key
Server ready
- server send "finished" encrypted with session key

General phases

Negotiation
- server & client agree on cipher suite
- server sends SSL cert
Authentication
- client check that server cert is authentic / can be trusted
Key Exchange
- server & client create session key (symmetric keys)

Trusting certificates

CA
- certificate is issued by a Certificate Authority that browser trusts (usually pre-installed on browser, can add & remove)
Digital Signature
- verify that person presenting cert is also person controlling the domain
- certificate is "signed" by another authority to declare person controlling cert controls domain
- Authority uses "private key" (basically a unique key only authority can produce, much like a signature) to encrypt contents of cert. cipher text is attached to cert as digital signature
- anyone can use public key to decrypt and match contents. only authority can produce the signature.
- browser can use CA public key to check if signature is valid.

man in middle can technically replay info from client to server. but information is encrypted and attacker will not have server's private key to decrypt and read information.

Further reading:
https://robertheaton.com/2014/03/27/how-does-https-actually-work/
https://medium.com/@vanrijn/an-overview-of-the-ssl-handshake-3885c37c3e0f
https://www.thesslstore.com/blog/explaining-ssl-handshake/

Transmission Media

physical path between transmitter and receiver (i.e. channel through which data is sent from one palce to another)

DNS

Domain Name system. translates hostname (human friendly names) to IP addresses.

distributed database implemented in hierarchy of DNS servers
application-layer protocol that allows hosts to query distributed database.

when browser extracts hostname, DNS client sends query for hostname to DNS server. DNS server will reply with IP address.

DNS adds delay but delay is circumvented as IP address usually cached in "nearby" DNS server

How DNS works

DNS reply & query sent in UDP datagrams to port 53. DNS is a distributed hierarchical Database

Overview

browser invoke client side of DNS with hostname to be translated
DNS sends query message to network. All DNS reply & query are sent within UDP datagrams to port 53
DNS in user host receive DNS reply message with desired mapping
mapping passed to invoking application (browser)

distributed hierarchical Database

DNS uses a large number of servers,
organized in a hierarchical fashion and distributed around the world. mappings
are distributed across the DNS servers

root DNS server (at top)
top level domain (TLD) DNS server
authoritative DNS server (at bottom)

e.g. amazon.com -> client contact root server --> root server return IP address for TLD server (the com DNS server) -> client contact TLD server -> TLD server returns IP addrss for authoritative server for amazon.com -> authoritative server returns IP address
Local DNS server
not in hierachy. Each ISP will have local DNS server, when host connect to ISP, ISP provides host with IP address of DNS server (typically via DHCP)
host makes DNS query, query sent to local DNS server which acts as proxy forwarding query to DNS server hierarchy.
DNS queries can be iterative or recursive

Caching
in query chain, DNS servers do caching so results can be returned more quickly

Overview: TCP & UDP

TCP/IP network makes 2 distinct transport-layer protocols to application layer:

TCP (Transmission Control Protocol)
- provides reliable, connection-oriented service to the invoking application
UDP (User Datagram Protocol)
- provides unreliable connection-less service to invoking application

Relation between transport & network layer

extend host-to-host delivery service provided by network layer to process-to-process delivery service for applications running on hosts.

At destination host, transport layer receives segments from network layer below, transport layer responsible for delivering data in segments to appropriate application process running in host.

eg. in your computer u run 4 processes (FTP session, webpage HTTP session + 2 telnet sessions) transport layer on receiving data from network layer must direct it to 1 of these 4 processes

Process can have 1 or more sockets (door through which data passes from network to process) transport layer in receiving host delivers data to an intermediary socket.

Example.
transport layer: TCP / UDP
network layer: IP

Multiplexing & demultiplexing

demultiplexing: at receiving end, transport layer examine segment fields to identify receiving socket & deliver it to correct socket
multiplexing: at source host, gather data chunks from different socket, encapsulate each data chunk with header info to create segment and pass them to network

reference

TCP and UDP perform demultiplexing & multiplexing by including 2 fiels in segment headers:

source port
destination port

port numbers are 16 bit
both fields together uniquely identity application process running on destination host

Each socket assigned port umber when segment arrives at host tarnsport layer examines destination port number and directs segment to corresponding socket. Segment's data passes through socket to attached process.

Refernce:
http://www2.ic.uff.br/~michael/kr1999/3-transport/3_02-fund.html

UDP: connectionless tarnsport

connectionless because there is no handshaking between sending & receiving transport-layer entities before sending segment.

takes messages from application process
attaches source and destination port number (for multiplexing & demultiplexing)
adds 2 other small fields
pass resulting segment to network layer
network layer encapsulate transport-layer segment into an IP datagram & make best-effort attempt to deliver segment to receiving host
If segment arrives at receiving host, UDP use destination port number to deliver segment data to correct application process.

In Practice
DNS is an applicatio-layer protocol that uses UDP
when DNS application in host wants to make query

application constructs DNS query message & passes it to UDP
host-side UDP adds header fiels to message
host-side UDP passes resulting segment to network layer
netowrk layer encapsulates UDP segment to datagram & sends datagram to name server
DNS application at querying host waits for reply to query
If no reply (becuase underlying network lost query / reply), it tries sending query to another name server / inform invoking application that it can;t get reply

Why UDP

Lesser delays: No handshake = no delay to establish connection
Small packer header overhead
Support more clients: No connection state = server devoted to particular application can support more active client when application runs over UDP rather than TCP

UDP: Checksum

provides error detection: ensure bits in UDP segment have not been altered

Sender
- sender performs 1s complement of sum of all words in segment (any overflow is wrapped around)
- result is put in checksum field
Receiver
- if segment arrives
- all 4 16-bit words are added together with cehcksum
- sum = 1111111111111111
- segment has no errors. If there is >=one 0 there are errors.

Why checksum? -layer protocols) between source & destination provide error checking.

TCP: Connection-Oriented Transport

TCP(Transmission Control Protocol)Internet's transport-layer connection-oriented reliable transport protocol
TCP connection provides a full-duplex service.
TCP connection is always point-to-point (between single sender & single receiver)

Connection-Oriented
before 1 application process sends data to another, 2 processes must first "handshake" with each other

Reliable Data Transfer
TCP relies on principles of reliable data transmission

error detection
retransmission
cumulative acknowledgement
timers
header fields for sequence & acknowledgement numbers

TCP Connection: 3 way handshake

3-way handshake process to establish a fully-duplex communication

SYN
- client wants to establish connection with server.
- client send segment with SYN (synchronize Sequence Number) that informs server that client is likely to start communication with with what sequence number it starts segment with
SYN+ACK
- server responds to client request with SYN + ACK signal bits set.
- ACK: signifies response of segment it received
- SYN: signifies with what sequence number it is likely to start segments with
ACK
- client acknowledges response of server & both establish reliable connection with which they will start the actual data transfer

SYN & SYN+ACK establish connection parameter (sequence number) for one direction & it is acknowledged
SYN+ACK & ACK establish the connection parameter (sequence number) for other direction & it is acknowledged.

educative

Reliable Data Transfer - Concepts + Introduction

Information in this section is all taken from this medium article by Zack West.
I *HIGHLY RECOMMEND reading it. It introduces concepts for reliable data transfer in a really simple and concise way. In summary.

Reliable data transfer has 2 key components:

data loss
data corruption

There are a few components that address this:

ACK
- acknowledgement from receiver to let sender know data is received.
Timeout
- timeout in case sender never receives ACK/NACK response

Mapping ACK/NACK to data segment sent

stop and wait
- sender sends single data segment and waits for response
SEQ (send multiple data segments)
- SEQ (sequence numbers). When sender sends multiple data segments. SEQ lets the sender know which ACK / NACK message is for which data segment

Pipelined protocols

Go back N
- sliding window
- sender transmit packets waits on ACKs from receiver.
- as sender receives ACKs base value (representing window minimum) slides forward "quthorixing" incremented SEQ numbered-segments
- receiver: packets received out of order are discarded
selective repeat
- receiver can accept packets out of order.
- receiver can accept & buffer frames following a damaged or lost one
- retransmission of packets happen when:
- implicit: packets are not ACKed nefore time out
- explicit: explicit NACK

GBN & SR further reading:

TCP Is a mix of GBN & SR (https://networkengineering.stackexchange.com/a/29478)

TCP Connection: Reliable Data Transfer

TCP creates reliable data transfer service on top of IP's unreliable best-effort service.
TCP reliable data transfer service ensures data stream that a process reads out of its TCP receive buffer is uncorrupted

data received from application
- TCP receive data, encapsulate data in segment, pass segment to IP (each segment includes a sequence number - byte-stream number of first data byte in segment)
timer timeout
- TCP re transmits segment that caused timeout
- TCP restarts timer
ACK receipt
- sener TCP determine whether ACK is first time ACK for segment sender has yet to receive or a duplicate ACK
- first-time ACK: sender knows all data up to byte being acknowledge has been received correctly. It can update its TCP state variable. ACK from Host B to Host A is lost. Host A re transmits segment after timeout. Host B receives the retransmission and observers from sequence number that the segment contains data that has already be received. Host B will discard bytes in retransmitted segment. if second ACK segment arrives before the new timeout ends, the second segment (seq=100 sender segment) will not be sent. Host A sends 2 segments but ACK of first is lost. Host A gets ACK of 120. so it knows B has received both segments. Host A will not resend second segment.

TCP Connection Termination

4 step process

TCP VS UDP

Information from this sectio is taken from Guru99

TCP
- use when both client & server independently send packets at same time & occasional delay is acceptable (eg. Online Poker)
UDP
- both client and server may separately send packets & occasional delay is not acceptable (multiplayer games)
- multimedia

Applications / Advantages

TCP
- establish connection between 2 computers
UDP
- can be use for servers that answer small queries from larger client base (eg.DNS)
- used by time-sensitive applications
- multicasting sending

What happens when u put URL in browser

I HIGHLY RECOMMEND this medium article by maneesha wijesinghe1

It is super detailed and if you are short on time, the headers provide a really good brief.
basically,

type in URL
cache check for DNS record with IP address of URL. browser cache, OS cache, router cache, ISP cache
not in cache, ISP DNS server do DNS lookup of URL (to get IP address)
browser initiate TCP connection with server (of the website). SYN/ACK stuff
TCP connection initiated, browser send HTTP request to server
server contains web server (apache, nginx) server handles request sends back resposne
server send HTTP response (usually for SPA, the page loads coz browsers sends HTTP GET and webserver returns index.html)
browser displays HTML content

Store password in DB

https://www.vaadata.com/blog/how-to-securely-store-passwords-in-database/
https://www.geeksforgeeks.org/store-password-database/
https://auth0.com/blog/adding-salt-to-hashing-a-better-way-to-store-passwords/

Dont store plain text
Hash passwords
Add salt (random phrase) to password
Add dynamic salt (random phrase that changes for every user). each user will have to store hashed password + dynamic salt.
use BCrypt VS md5. (BCrypt does salt)

Note:

never tell someone their selected password is not unique

md5
very quick hashing function -> faster calculation - faster brute force attacks

BCrypt
more info

generate salt
hash password with generated salt
can choose value of salt Rounds (increase time to compute hash & reduce brute force attacks) however time to compute hash must not be too long so users will not run out of patience

bcrypt VS md5

slower => brute force attacks are less effective
can increase the number of iterations to match computing power. (if computing power increases)info Auth0 article explains why bcrypt (salt generation) is preferred

SQL

limjy — Wed, 05 May 2021 08:17:18 +0000

Should be a quick cramming / revision guide for SQL stuff.
Tis is for Oracle SQL (some basics)

### maximum salary per department
SELECT department, MAX(salary) AS "Highest salary"
FROM employees
GROUP BY department;

### find top earnings (salary * months) & number of employees with top earnings
SELECT MAX(salary*months), COUNT(*) FROM EMPLOYEE 
WHERE salary * months = (SELECT MAX(salary*months) FROM EMPLOYEE);

https://www.techonthenet.com/oracle/functions/max.php

types of joins

To exclude entries in left or right table (get right entries that DO NOT match left) try WHERE .id IS NULL

SELECT
    a.id id_a,
    a.color color_a,
    b.id id_b,
    b.color color_b
FROM
    palette_a a
RIGHT JOIN palette_b b ON a.color = b.color
WHERE a.id IS NULL;

https://www.oracletutorial.com/oracle-basics/oracle-joins/

select from joins

SELECT SUM(CITY.population)
FROM CITY
FULL OUTER JOIN COUNTRY
ON CITY.CountryCode = COUNTRY.Code
WHERE COUNTRY.Continent = 'Asia';

Web Dev Theory Stuff

limjy — Tue, 20 Apr 2021 15:49:05 +0000

Theory stuff

CORS
CSRF
403 vs 401
How to store password
HTTPS
process-when-visit-URL

CORS

Cross Origin Resource Sharing
HTTP-header based mechanism that allows a server to indicate any other origins than its own from which a browser should permit loading of resources.
source

CSRF

Cross Site Request Forgery
web security vulnerability that allows an attacker to induce users to perform actions that they do not intend to perform.
Attack requires:

Relevant action. There is a privileged action within the application that the attacker has a reason to induce.
Cookie-based session handling. Performing the action involves issuing one or more HTTP requests, and the application relies solely on session cookies to identify the user who has made the requests.
No unpredictable request parameters. The requests that perform the action do not contain any parameters whose values the attacker cannot determine or guess

https://portswigger.net/web-security/csrf
https://cheatsheetseries.owasp.org/cheatsheets/Cross-Site_Request_Forgery_Prevention_Cheat_Sheet.html

workaround:
same-site policy
cookies only accessible by only your domain

Cookie security:
HttpOnly cookie prevents client-side scripts from accessing data. It provides a gate that prevents the specialized cookie from being accessed by anything other than the server.

CORS

403: Forbidden
401: Unauthenticated

403 - can login, is authorized user of application but not enought priviledge to access functions.
401 - cannot login, unauthorised user

JWT

JSON Web token
compact and self-contained way for securely transmitting information between parties as a JSON object.
https://auth0.com/docs/tokens/json-web-tokens

JWT VS Cookie

Cookie is automatically sent by browser. JWT must be attached to HTTP headers every HTTP call.
https://stackoverflow.com/a/37635977

Scalability
as user base grows must store more session data.
Seurity
JWT if stored in web storage (local/sessino storage) is vulnerable to XSS.
Cookies may be vulnerable to CSRF

to circumvent attacks JWT usually have short expiration time

REST ful API
RESTful API is stateless - when request is made response with certain parameters can alwayse anticipated
JWT is stateless, cookie it not. cookie mantain session state
Performance
if a lot of data encoded in JWT there will be significant overhead with every HTTP request.

https://ponyfoo.com/articles/json-web-tokens-vs-session-cookies

XSS Cross site scripting inject malicious code into vulnerable web application. It doesn't directly target aplication, users of web application are the ones at risk.

https://www.imperva.com/learn/application-security/cross-site-scripting-xss-attacks/

localStorage VS sessionStorage data in sessionStorage clear when page session ends but data in localStorage doesnt expire.

both access a session storage object for the current origin.

https://developer.mozilla.org/en-US/docs/Web/API/Window/sessionStorage

Store password in DB

Dont store plain text
Hash passwords
Add salt (random phrase) to password
Add dynamic salt (random phrase that changes for every user). each user will have to store hashed password + dynamic salt.
use BCrypt VS md5. (BCrypt does salt)

Note:

never tell someone their selected password is not unique

md5
very quick hashing function -> faster calculation - faster brute force attacks

BCrypt
more info

generate salt
hash password with generated salt
can choose value of salt Rounds (increase time to compute hash & reduce brute force attacks) however time to compute hash must not be too long so users will not run out of patience

bcrypt VS md5

slower => brute force attacks are less effective
can increase the number of iterations to match computing power. (if computing power increases)info Auth0 article explains why bcrypt (salt generation) is preferred

HTTPS

previously SSL not TLS
https://robertheaton.com/2014/03/27/how-does-https-actually-work/

Hello
Certificate exchange - server sends client its cert + public key (authentication, server is not impersonator) (SSL cert contains public key) certificates usually come with digital signature, (signature encrypted with CA's "private" key) so you can take the CA public key decrypt and check if cert is signed by correct CA.
Key Exchange - exchange symmetric key (encrypted with public key). All information exchanged encrypted with symmetric key since symmetric key can do encryption a lot more efficiently.

man in middle can technically replay info from client to server. but information is encrypted and attacker will not have server's private key to decrypt and read information.

Angular Theory

limjy — Sat, 17 Apr 2021 10:36:11 +0000

Summary of Angular theory stuff for myself.

Some stuff to know

HTML DOM

HTML Document Object Model.
DOM is object-orientated representation of webpage which can be modified with scripting language like JS. Further reading

What is the architecture of Angular?
What are directives in Angular?
Component & Module in Angular
What are decorators in angular
What is a template in Angular?
What is Data Binding in Angular?
How is a SPA achieved in Angular?
What is routing in Angular?
How to implement routing in angular?
What is lazy-loading?
How to implement lazy loading?
What are services in Angular?
Service VS Component
What is dependency Injection
How to implement dependency injection
Benefits of Dependency Injection

Children stuff (ViewChild, ViewChildren, ContentChild, ContentChildren)

ViewChild & ViewChildren
Template reference variable
What is content projection?
ContentChild & ContentChildren
Static flag
ViewChild, ViewChildren VS ContentChild, ContentChildren

Angular Lifecycle questions

Importance of component lifecycle?
Events & sequence of component lifecycle?
constructor VS ngOnInit?

HTTP

How to make HTTP calls in angular?
Need for subscribe function
How to handle errors in HTTP calls?

Passing Data

Pass Data between components & routes
Passing data via service?

Pipe

What is Angular Pipe?
How to make custom pipe in Angular?
Change Detection in Angular pipe
Pure VS impure angular pipe

RxJS

Synchronous VS Asynchronous
What is RxJS?
What are Observables & observers?
Importance of subscribe in RxJS
How to unsubscribe?
Concept of operators

What is angular

Javascript framework.
Main help:
Helps bind view (HTML) to model (object). this helps developer implement MVC framework. Pure JS requires lots of code.
Main features:

SPA. angular helps developer implement single page application with routing. (url will change but only 1 index.html)
Dependency Injection. (Angular helps developer instantiate components) eg. to inject service into component just put it into constructor method.

Angular VS AngularJS

tbh im not very sure about this, I try not to work with AngularJS lmao

Javascript VS Typescript
CLI Builder
can use Angular CLI to build components & services
lazy-loading
load only certain modules when needed. loading is only done when user navigates to route of respective module see more

What are directives in Angular?

Instructions in HTML that tells angular how to transform the HTML DOM

3 main directives (SAC)

Component Directives
Structural Directives
Attribute Directives

Take note: a component is technically a directive

Component Directives

directives with templates. its like user control

A component is technically a directive. @Component extends the @Directive.

e.g. declare a custom component my-grid. component directive is then <my-grid></my-grid>

Structural Directives

Change structure of elements (add / remove DOM)
eg. NgIf, NgFor NgSwitch (switch case for ngif)

Attribute Directive

Change behaviour & appearance of elements
eg. NgStyle, NgClass

NPM & node_modules folder

NPM = node pacakge manager.
Helps make installization of JS framework libraries easy.
node_modules = folder where all packages are installed.
It also acts like a cache. when developer imports libraries without specific path nodeJs will look at node_modules folder
Taken from sitepoint & SO
global VS local

package.json file

states all the JS references (i.e. dependencies of the project, library name). So developer can quickly install all dependencies at one shot with npm install.
node_modules can be re-created from scratch by doing npm install

package.json VS package-lock.json

package.json record minimum version of libraries your application requires. It also defines project properties, author etc.
package-lock only used to lock dependencies to specific version number. It records exact version of each installed package.

What is Typescript?

superset of Javascript.

adds types to JavaScript
Object-oriented programming environment which compiles to JS

This results in

less errors
better code quality / productivity ???

** at the end of the day, TS will be compile to JS**

more information on guru99

errors are pointed out at compile time (code needs to be compiled)
TS uses concepts like types and interfaces to describe data
TS needs compilation. must compile to JS.

Importance / Advantages of angular CLI

Helps developer generate boiler plate code as opposed to starting from scratch

generate ready made project ng new my-app (make src files, module file)
generate ready-made schematics (eg. components / services / directives) ng generate service/component documentation

Importance of Component & Module in Angular

Components are the main building blocks in angular. Each component consists of :

HTML template (declares what renders on page)
typescript class that defines behaviour
CSS selector that defines how component is used in a template
CSS styles applied to template From documentation

Component VS Module

Component:

controls view (html)
communicate with other components and services to bring functionality to applucation

Modules are:

logical groups of components

Reference: SO answer

What is Decorator(Annotation / Metadata) in angular

tells Angular what kind of class it is.
Above the class declaration
eg. @Component -> Angular Component. @NgModule -> Angular Module
** may also be asked how to create component and module in angular) **

must be decorators when declaring components and modules in angular

What is a Template in Angular?

HTML view of Angular where you can write directives

There are two ways you can write templates:

inline (define it in @Component({template: <<here>>}) directive)
separate HTML file (define it in component templateUrl)

What is Data Binding in Angular?

How component and view communicate with each other.
Documentation and more details

Interpolation ------ {{expression}}
property binding-----[target]=expression
event binding--------(target)=statement
two-way binding-----[(ngModel)]

interpolation

one-way from component to view
Data flows from component to view. can stick it with HTML (one-way)

property

one-way biding from component.
Data flow from component to viewsets specific element property.

event binding

one-way. from event / view to component.
event in view triggers a function in component. Listends for an element change event

two-way binding

two-way. combines property binding with event binding

set event in component. if some event happens in view it can trigger function in component.
e.g. most commonly used in template forms

Explain architecture of Angular?

Angular consists of 7 main building blocks:

Template (HTML view)
Component (binds view an model)
Binding (how component & template talk to each other)
Module (groups components logically)
Directives (change style / behaviour of DOM)
Service (share common logic across the project project)
Dependency Injection (injects instances into constructor) (e.g. injecting services into component - just put into component constructor)

Further explanation in documentation

What is SPA?

Single page application
A Single page application is a web application /website taht ineracts with uer by dynamically rewriting current web page with new data from webserver. wiki
This means the main UI gets loaded once and the other features are loaded on demand / depending on user actions.
In production, this means that there is just 1 index.html file with CSS bundle and JavaScript bundle.
This is advantageous especially when there is rich client-side functionality. SPA can load more quickly since full page reloads are rare.

e.g. page with header, footer, drawer. in SPA only the stuff in between is loaded instead of the entire page. This gives performance improvements

More information about SPA on angular university blog

How to implement SPA in Angular

Routing

Angular routing is a simple collection with two things:

URL
Component to load when URL is called

helps to define navigation for angular application. It maps URL-like paths to views instead of pages. So when user moves from one screen / url to another, the application loads components not an entirely new page.

What is routing in Angular

In Angular, routes comprise of :

path (URL path)
Component
(optional) redirectTo path

Routes map a URL path to a component.
It helps users navigate from one view to another as users perform tasks on application
Helps developer respect SPA since only components in page are changing, entire page is not reloaded.

Taken from: pluralsight & smashingmagazine

How to implement routing in angular.

define collection of routes in angular --> map url paths to components
define router outlet --> where the component will be displayed
[routerLink] in HTML OR this.router.navigate(url) in TS file --> allows user to navigate to different route / view

What is lazy loading

Loading on demand.
Loading only the necessary HTML, CSS & JS files when needed. Loading other components only when needed (i.e. when user performs certain actions)

How to implement lazy loading?

Divide project into separate modules
declare loadChildren property in route object

What are services in Angular?

Service helps developer share common logic / common functionality across components

Service VS Component

From documentation
Components is to enable the user experience & nothing more
Component should: present properties and methods for data binding to mediate between template (view) & application logic (model)

Components should delegate other tasks (o.e. fetching data from server, validating user input) to a service.
The tasks in service can also be shared with other components vis dependency injection

What is dependency Injection?

application design pattern

Developer does not need to create object instances (no need to instantiate service let service: ExampleService = new ExampleService() instead, Angular injects is via the constrcutr

export class ExampleComponent{
  constructor (private service: ExampleService) {
    this.service.doSomething();
  }
}

taken from documentation

How to implement dependency Injection in Angular?

There are 3 ways to provide a service

root service is provided at root level, angular creates a single, shared (i.e. singleton) instance of service & injects it into any class asking for it.

Injectable root decorator is provided in service class

@Injectable({
 providedIn: 'root',
})

this is auto-generated with ng generate service
TO only provide service to certain module change root to ExampleModule

import { Injectable } from '@angular/core';

@Injectable({
  providedIn: 'any',
})
export class UserService {
}

With providedIn: any all eagerly loaded instance share singleton instance, but lazily loaded modules each get their own unique instance

provide in module register service in providers array in NgModule

@NgModule({
  providers: [
  ExampleService,
  Logger
 ],
 ...
})

If NgModule is root AppModule,
ExampleService will be singleton and available throughout the app.
Reference

Importing service in AppModule AND lazily loaded module, the app can generate multiple instance of a service.

Component level registering provider at component level, you get a new instance of service with each new instance of component

@Component({
  selector:    'app-hero-list',
  templateUrl: './hero-list.component.html',
  providers:  [ HeroService ]
})

Benefits of Dependency Injection

Decouples class dependencies.
can change dependencies of service class without changing code in all component classes. If instantiation of service class is in component, must change all the service instantiation code.

i.e. just change arguments in service constructor. no need to change anywhere else

ng serve VS ng build

ng serve - builds angular application in memory
ng build - builds application in harddisk. put all the compiled code in the /dist folder

--prod flag?

--prod flag ensures you build applciation for production. compresses JS files, removes comments. makes application ready for production.

Importance of component lifecycle?

directives have lifecycle too

tldr;
Developers can tap into key events of component lifecycle and write custom code by implementing lifecycle hook interfaces. (eg. ngOnInit())
Greater details in documentation

Component instance has lifecycle when angular instantiates component class & renders component view till angular destroys component and removes rendered template from DOM.

Dev can use lifecycle hook methods to tap into key events of lifecycle to init new instances / clean up before deletion of instances.

events & sequence of component life cycle?

Here is a great medium article by Shivani that goes in-depth into the angular lifecycle.

Angular Documentation offers list of lifecycle event sequence

Two types of events

Events fired when component is first loaded
Events fired on change detection

List of lifecycle events
(events called ONCE are italicized)

constructor (more of a typescript event, not an angular event)
ngOnChanges (also called when data bound input property @Input changes). This event happens very frequently
ngOnInit (data bound properties displayed on screen / sets component's @Input properties)
ngDoCheck() (fires immediately after ngOnChanges() on every change detection run)
ngAfterContentInit (after Angular projects external content into component's view) related to <ng-check>
ngAfterContentCheck (check content projected)
ngAfterViewInit (after angular initializes component's views & child views)
ngAfterViewChecked (after angular checks component's view & child views)
ngOnDestroy (cleanup before angular destroys component)

three parts

kick start event (change detection) (ngOninit, ngDoCheck)
projected content event fires (ngAfterContentInit, ngAfterContentChecked)
events of component view fires (ngAfterViewInit, ngAfterViewChecked)

constructor VS ngOnInit()?

constructor - typescript concept, invoked by typescript
ngOnInit - angular concept / event, invoked by angular framework

Sequence:

constructor is fire.
view and component initialized, binding happens
ngOnInit (after component is initializes, access to DOM elements)

Constructor:

initialize class variables
dependency injection

ngOnInit:

access to class variables
access to @Input variables

Accessing, @Input or from constructor will give undefined.

More information in this SO answer
@ViewChild only access in ngAfterViewInit

ViewChild & ViewChildren

@ViewChild : Reference ONE HTML element / DOM element in the component
@ViewChildren: Reference a collection of elements

If multiple elements detected by @ViewChild, it will only reference the first element.

Template Reference Variable

Template variables help developer use data from one part of template in another part of template

<input #phone placeholder="phone number" />

<!-- lots of other elements -->

<!-- phone refers to the input element; pass its `value` to an event handler -->
<button (click)="callPhone(phone.value)">Call</button>

To use template reference variable with ViewChild

<div #div1> this div </div>

@Viewchild('div1',{static: false}) div: ElementRef

What is content projection?

Projection: project HTML content / component content from parent to child.

<ng-content></ng-content>
Allows you to insert a shadow DOM as Input to a component.

@Input only allows you to pass simple string / objects to components. <ng-content> allows you to pass things HTML elements, another component.

<app-component>
  <h1>Header</h1>
  <p>paragraph</p>
</app-component>

Multi content projection: content projection slot
GreetComponent

<div class="container">
  <ng-content> </ng-content>
  <ng-content select="h1"></ng-content>
  <p>welcome text</p>
  <ng-content select=".content"></ng-content>
</div>

Parent Content

<div>
  <greet>
    <h3> everything else </h3>
    <h1> Header </h1>
    <span class="content"> something </span>
  </greet>
</div>

output after content projection is

<div>
  <div class="container">
    <h3> everything else </h3>
    <h1> Header </h1>
    <p>welcome text</p>
    <span class="content"> something </span>
</div>
</div>

reference

Content Child & Content Children

access projected content

CardComponent.html

<div class="card">
   <ng-content select="header"></ng-content>
   <ng-content select="content"></ng-content>
   <ng-content select="footer"></ng-content>
</div>

CardComponent.ts

@ContentChild("header") cardContentHeader: ElementRef;

ParentComponent.html

<card>
  <header><h1 #header>Angular</h1></header>
  <content>One framework. Mobile & desktop.</content>
  <footer><b>Super-powered by Google </b></footer>
</card>

tektutorialshub provides a concise write-up

Static flag

static is false as default behaviour.
static is false because we would like query to be resolved every change detection

Angular documentation & SO describes the flag in greater details

ViewChild, ViewChildren, ContentChild, ContentChildren

ViewChild: access DOM elements from its own view
ContentChild: access DOM elements from another view, access DOM elements projected by someone else
(e.g. @ContentChild is on CardComponent.ts, but the project content is from ParentComponent.html)

ViewChildren: collection of ViewChild
ContentChildren: collection of ContentChildren

Make HTTP calls in Angular

import HttpClient from @angular/common/http
import HttpModule in Angular Module
create HttpClient object via dependency injection constructor(public http:HttpClient)
make post / get class with HttpClient this.http.post(URL, data).subscribe(res => successfunc(res), err => errfunc(err)
subscribe to Http.post / Http.get. Subscribe takes 2 inputs: success function and error function

Need of Subscribe function

Provide success / error methods if HTTP calls are successful / fail.
Also, if there is no async pipe, subscribe is needed for an observable to execute

Handling errors in HTTP calls

error callback of subscribe method
catchError function in pipe. (catchError must return a new observable or throw an error) when throwing new error, error thrown will propate to subscriber More details on tekturotials

The second method achieves separation of concern in Angular
Additionally,
Chaining multiple observables (one after another

catchError keeps observable alive. If inner observable has errors, outer observable will still continue (coz it received an observable) Combinging multiple observables (execute multiple observables)
allows arrays of observables to complete. Else if only 1 observable fail, all will fail, with catchError it will allow observable to complete and emit something.

Pass Data between components & routes

Parent Child component
@Input : Parent -> child
@Output : Child -> parent
@ViewChild:
Data between routes -> Routing Query Params

this.route.navigate(['url'],
  {queryParams: {
    name: 'myname'
    }
   });

Services more of global data / storing more of sharing global data via singleton service
create service
inject service into components
access service data
Browser
*global data *
Local Storage / temp storage

Good practice to pass data using services

Sharing data VS passing data
If you are just passing data from one component to another, should avoid using service / global variables.
Other components may modify global variables. Code can become quite messy.

What is the need for Angular Pipes?

Pipes transform data on Angular UI expressions
Angular has some inbuilt pipes:

AsynPipe : read object from asynchronous source (impure by default)
JsonPipe: convert object to json string
KeyValuePipe: can use in ngFor to iterate keys and values of object
DatePipe: fomat date
CurrencyPipe: number -> currency string

Example:

<p>The hero's birthday is {{ birthday | date:"MM/dd/yy" }} </p>

You can also chain pipes (will implement first pipe then second pipe to the output of first pipe)

{{ birthday | date | uppercase}}

How to make custom pipes in Angular?

Use @Pipe to mark class as a pipe
Implement PipeTransform interface
Implements transform method.

@Pipe({name: 'uselessPipe'})
export class uselessPipe implements PipeTransform {
  transform(value: string, before: string, after: string): string {
    let newStr = `${before} ${value} ${after}`;
    return newStr;
  }
}

{{ user.name | uselessPipe:"Mr.":"the great" }}

Change detection in angular pipe.

Data is primitive input value (string, number) OR object reference as input (Date / Array)
Angular executes pipe whenever it detects change for the input value of reference
Change something inside a composite object (e.g. month of a date, element of array, object property)
use impure pipe

Referenced from Angular documentation

Detecting pure changes to primitives and object references

Angular pipes are pure by default. Angular executes pipe only when it detects pure change to input value. Pure change is either:

change to pimitive input value (string, number, boolean, symbol)
changed object reference (Date, Array, Function, Object)

In Pure pipe, Angular ignore changes within component object (eg. new added elemtn of existing array) because object reference did not change.

Example:

<div *ngFor="let hero of (heroes | flyingHeroes)">
  {{hero.name}}
</div>

@Pipe({ name: 'flyingHeroes' })
export class FlyingHeroesPipe implements PipeTransform {
  transform(allHeroes: Hero[]) {
    return allHeroes.filter(hero => hero.canFly);
  }
}

If user adds flying heroes, it will not be updated becuase reference to the array has not changed so angular does not update display. there are two ways to cirucmvent this

change object reference replace array with new array containing new changed elements, input new array to pipe.
make pipe detect impure changes set pure flag to false

@Pipe({
  name: 'flyingHeroesImpure',
  pure: false
})

What is change detection

Mechanism by which Angular sychronizes state of application UI with state of data

When component data is updated (e.g. from user event/ application logic), values bound to DOM properties in the view can change. The change detector is responsible for updating the view to reflect the current data model.

Reference: Angular documentation

Synchronous VS Asynchronous

Synchronous code is executed in sequence.
When one statement is executing nothing else can happen.

Asynchronous code doesn’t have to wait – your program can continue to run.
Asynchronous code is hard to achieve in Synchronous JS, developer is unsure how long code will take to finish (how long will it take to download image from API?)
So code like this:

let response = fetch('myImage.png'); // fetch is asynchronous
let blob = response.blob();
// display your image blob in the UI somehow

blob may be undefined.
Async JS has 2 main code styles:

callbacks (old-styles)
promise (new-style)

Async JS has two models: ( more details on RxJS

Pull mode (consumer is king, consumer decides when it receives data from producer, producer is unaware when data will be delivered)
Push model (producer is king, it determines when to send data to consumer)

Promises & observable follow the push model.
Promise (producer) delivers resolved value to registered callbacks (consumer)

more information here and on MDN

What is RxJS?

RxJS stands for Reactive Extensions for JavaScript

It is to handle asynchronous data streams
eg. async data source(HTTP data, timer) may take 1 second or 15 seconds to come. Then application should have listener
(e.g. http response, data comes in small time intervals)

RxJs helps you to handle asynchronous data streams easily.

What are Observables & observers?

Observable is a Push system for Javascript. It is a producer of multiple values "pushing" them to observers (consumers).

Observable can give multiple values either synchronously or asynchronously.

this freecodecamp article has a very comprehensive introduction

Observable has 4 main stages

Creation
Subscription
Executing
Disposing

Importance of subscribe in RxJS

Each call to observable.subscribe triggers its own indepdendent set up for that given subscriber.
RxJS: starts an "Observable execution" an deliver values / events to observer of execution.
Angular: Observable instance only begins publishing values when someone subscribes to it.

How to unsubscribe (Destroy phase of Observable)

Taken from RxJS documentation

const subscription = observable.subscribe(x => console.log(x));
subscription.unsubscribe();

Since Observable exeuctions may be infinite and its common for observer to abort execution in finitetime, we need API for cancelling execution. When execution is stopped / cancelled, we can avoid wasting computation power / memory resources.

Explain concept of operators with sample code

Operators are functions.
There are 2 types of operators:

Pipeable operator takes in observable as input and output is also an observable. pre-processing logic, can transform data in observable.
creation operator can be called as standalone functions to create new Observable

Taken from RxJS documentation

Algos - Complexity + Recursion

limjy — Wed, 31 Mar 2021 11:54:58 +0000

Summary for myself (from Leet Code explore card)

Analysis

Asymptotic

measure efficiency of function that dont depend on machine-specific constants

Guess run time of function in relation to the input size

Worst, Best, Average Case

Average case.

assumes all cases are uniformly distributed
calculate expected value Eg. linear search. Average complexity ~ O(n/2) ~ O(n) Full Explanation
assume that input is uniformly distributed
average case complexity = total number of comparisons made / number of inputs
element found on index 0, index 1, index 2, ... , index n
average complexity: = number of comparisons made / n = 1 + 2 + 3 + ... + n / n = (n* (n+1) /2 ) / n = (n+1) / 2 ~O(n/2) ~O(n)

Annotations

Theta (Θ) Notation --> upper and lower bound. (best & worst case)
Big O Notation --> upper bound (worst case)
Omega (Ω) Notation --> lower bound (best case)

Loops

O(1) no loop
O(n) loop, variable incremented by constant amount

for (int i = 1; i <= n; i += c) {  
        // some O(1) expressions
}

O(n^c) nested loops. c being the layers of nesting.

for (int i = n; i > 0; i -= c) {
       for (int j = i+1; j <=n; j += c) {
          // some O(1) expressions
}

O(log(n)) loop variables is divided / multiplied by a constant amount.

for (int i = n; i > 0; i /= c) {
       // some O(1) expressions
}

O(log(log(n))) loop variables is reduced / increased exponentially by a constant amount.

for (int i = 2; i <=n; i = pow(i, c)) { 
       // some O(1) expressions
}

**O(2²)

growth doubles with each addition to input data
often recursive algorithms by solving two smaller sub problems of N-1 SO answer

O(n!) adding loop for every element SO answer

Recursion

Recurrence Tree
draw recurrence tree
calculate time taken by every level of tree.
Master Method more details

Recursion

function calls itself

To avoid an infinite loop: rmb to have base case

Recursion functions usually consist of 3 parts

base case — terminating scenario that does not use recursion to produce an answer.
recurrence relation — set of rules that reduces all other cases towards the base case.
return - rmb to return things. usually there are two return statements one for base case and one for the recurrence relation.

In recursion, functions will get closer and closer to base case. When base case, function returns, and previous function calls are popped off the stack. If recurrence relation is not "returned" nothing is "returned" return type is void.

Complexity

This SO answer provides a quick analysis of time complexities of different recursion functions

Dyanmic Programming

Basically caching. Break problems down into sub problems.
Solve sub-problems only once and store their solution

can be divided into subproblems?
recursive solution
repetitive subproblems (like fibionacci, subproblems done over an over again) (use caching -> DP)
memoize subproblem

Memoization / Opti (Dynamic Programming)

optimize recursion problems by storing / caching previous functions. Preventing duplicate calls.

Eg. Fibionacci f(n) = f(n-1) + f(n-2)
In Fibionacci there can be multiple duplicate calls. (see below, duplicate calls are coloured same colour)

Complexity

Article provides more explanation

Time Complexity

Linear

Time Complexity = number of recursion invocations (R) and time complexity of 1 recursion call (O(s))
Time Complexity = R * O(s)

Example: Reverse String

printReverse(str) = printReverse(str[1...n]) + print(str[0])

Number of invocations = N (length of string)
Complexity of 1 invocation = O(1)
Therefore, time complexity = N * O(1) = O(N)

Execution Tree

Node = invocation of function. Therefore, number of invocations = number of nodes in tree (Ntree)
Time Complexity = number of nodes in tree (Ntree) * complexity of 1 invocation (O(s))
Time Complexity = Ntree * O(s)

This can also be used for linear. In linear, all nodes have 1 child and the number of nodes is the height of the tree.

The execution tree of recursion function will form an n-aray tree where n is the number of times recursion function appears in recursion relation

Example: Fibonacci
f(n) = f(n-1) + f(n-2)
recursion function appears twice in recursion relation. Therefore, execution tree is a binary tree.

Height of binary tree is N.
Number of nodes = number of nodes in binary tree of height N
= 2⁰ + 2¹ + 2² + ... + 2^N-1
= 2 ^N -1
~ O(2^N)

Therefore, time complexity
= nodes in execution tree * complexity of 1 invocation
= O(2^N) * 1
= O(2^N)

After Memoization

As mentioned previously, memoization optimizes complexity of recursion by minimizing duplicate calls. (i.e. reducing the number of children in the execution tree)

Example: Fibonacci
After memoization, duplicate calls are reduced. So
f(n) = f(n-1) + f(n-2) would now become
f(n) = f(n-1) + cache(n-2)

This is because result of f(n-2) would have been calculated in the previous invocation call f(n-1) where f(n-1) = f(n-2) + cache(n-3)
In optimized fibonacci, only f(n-1) must be calculated for calculation of f(n). f(n-2) is stored in cache. retrieving it from cache (hashmap) is constant operation.

Fibonacci = f(n) = f(n-1) + cache(n-2)
Recursion function only calls itself once. Nodes in Execution tree has 1 child. Recursion to calculate f(n) will be invoked f(n-1) times.

Time complexity
= Number of nodes in execution tree * complexity of 1 function call
= Height of execution tree * Complexity of 1 function call
= O(N) + O(1)
= O(N)

Space Complexity

Space complexity of recursion has 2 main components.

recursion related
non-recursion related

Recursion related

For normal function calls, space on stack is freed when function is returned. However in recursive functions, function (f2) calls another function (f1), so both functions are stored in stack. In recursive functions, functions will all be stored in stack until base case is base case is reached.

Space complexity = maximum depth of recursion tree

Stack Overflow

If stack allocated for program reaches maximum limit, program crashes.

Space complexity of recursion = Height of execution tree.

Non-recursion related

Space not directly relation to recursion. Eg.

storing global variables
saving intermediate result from recursion calls. (e.g. menoization: space complexity of hashmap from storing function call results)

Tail Recursion

** Java does not support tail recursion / tail call optimization

function is tail recursive if recursive call is last thing executed by function

This stackoverflow answer provides better details.

// non-tail recursive
function recsum(x) {
    if (x === 1) {
        return x;
    } else {
// non-tail because it does computation + recursive call
        return x + recsum(x - 1);
    }
}
// output
recsum(3)
3 + recsum(2)
3 + (2 + recsum(1))
3 + (2 + 1)
6

function tailrecsum(x, running_total = 0) {
    if (x === 0) {
        return running_total;
    } else {
// tail. only calls recursive function
        return tailrecsum(x - 1, running_total + x);
    }
}
// output
tailrecsum(3,0)
tailrecsum(2,3)
tailrecsum(1,5)
tailrecsum(0,6)
6

In tail recursive call, space is saved because, stack does not have to save space for every function call. Space is just "reused"

Stack allocated space for f(x1) to call f(x2). Then f(x2) will call f(x3). however stack wont have to allocate new space for f(x2) it will just "reuse" the space if allocated for f(x1).

** Tail recursion calls can be executed as non-tail recursive functions** i.e. un-optimized stack space is used. This depends on programming language. Java and Python DO NOT support tail call optimization
Javascript ???

Recursive VS Iterative

Readable: don't really have to repeat yourself.
Large Stack: large stack call.

useful for traversal.

When to use recursion

using a tree / convergin something into a tree

Can Divide & conquer using recursion

Divided into number of sub problems that are smaller instances of same problem
each instance of sub problem is identical in nature
solution of each sub problem can be combined to solve problem at hand.

Sorting

Bubble Sort
Insertion Sort
Selection Sort
Merge Sort
Quick Sort

sort()

JS: under the hood, JS sorts list of numbers like string.
[1,2,35,67,7,8]
[1,34,65,7,2,8] -- > [1,2,34,65,7,8]

Data Structure - Binary Tree

limjy — Fri, 26 Mar 2021 16:53:41 +0000

My summary of Leet Code [Binary Tree explore card](https://leetcode.com/explore/learn/card/data-structure-tree Also using GeeksforGeeks Binary Tree articles

Tree

Each node of tree has root value and list of references to other nodes (called child nodes)

From a graph point of view

directed acyclic graph which has N nodes and N-1 edges.

Binary Tree

tree structure where each node has at most two children. (left child & right child)

Traversing a Tree

Pre-order (root, left, right)
In-order (left, root, right)
Post-order (left, right, root)
level-order traversal

This article provides a great overview of tree traversals and how they relate to BFS / DFS

1. Pre-Order Traversal

visit root

visit left sub tree

visit right sub tree

(root first, then left right children)

Applications

used to create copy of a tree.
get prefix expression of an expression tree. (e.g. Polish notation)

class Solution{
    ArrayList<Integer> result = new ArrayList<>();
    ArrayList<Integer> preorder(Node root) {
        if (root != null) {
            result.add(root.data);
        }
        if (root != null && root.left != null) {
            result.add(root.left);
        }
        if (root != null && root.right != null) {
            result.add(root.right);
        }
        return result;
    }
}

2. Post-order Traversal

visit left sub tree

visit right sub tree

visit root

(children left,right first, then root)

Applications

delete tree
get postfix expressions (e.g. reverse polish notation)

class Tree {   
    ArrayList<Integer> result = new ArrayList<>();
    ArrayList<Integer> postOrder(Node root) {
       if (root != null && root.left!=null) {
            postOrder(root.left);
        }
        if (root != null && root.right!= null) {
            postOrder(root.right);
        }
        if (root != null) {
            result.add(root.data);
        }
        return result;
    }
}

3. In-order Traversal

visit left subtree

visit root

visit right subtree

(left -> right, left root right)

Applications

in BST, inorder traversal gives nodes in non-decreasing order.

class Solution {
    ArrayList<Integer> result = new ArrayList<>();
    ArrayList<Integer> inOrder(Node root)
    {
        if (root != null && root.left!= null) {
            inOrder(root.left);
        }
        if (root != null) {
            result.add(root.data);
        }
        if (root != null && root.right!=null) {
            inOrder(root.right);
        }
        return result;
    }
}

4. Level order tarversal

traverse tree by level

visit root node

visit children of root node

visit children of children of root node

continue till leaf nodes

Applications

Traversal - Complexity

Time complexity: O(1)
Space Complexity: (consider size of stack for function calls)
Worst: O(N) (skewed tree)
Best: O(log(n)) (balanced tree)

Properties

1. maximum number of nodes at height h is 2^h

level of root = 0
For root, h=0 and number of nodes is 2⁰ = 1
Therefore number of nodes when h = h is 2^h

2. Maximum number of nodes in a BINARY tree of height h is 2^h – 1.

In binary tree node can only have at most two children.
keep in mind that height index of root is 0. But height h refers to the number of nodes from root to leaf. Therefore leaf nodes have height index of h-1. (something like array indexes VS array length)
So total number of nodes in tree is
= 2⁰ + 2¹ + 2² + ... + 2^h-1
= 1 + 2 + 4 + ... + 2^h-1
= 2 ^h - 1 (geometric series)

Mathematical proof for last line:

3. In BINARY tree with N nodes, minimum possible height is log2(N+1).

Using point above we know that
2^h - 1 = N
2^h = N + 1
h = log2(N+1)

In Big O notation this is usually expressed as O(log(n))

4. BINARY Tree with L leaves has at least |log2L|+ 1 levels

From point 1 we know that the number of leaf nodes are 2^h-1.
2^h-1 = L
log2L = h - 1
h = log2(L) + 1

5. In a full binary tree, the number of leaf nodes is always one more than nodes with two children.

more here

Binary Tree Types

Full Binary Tree
Complete Binary Tree
Perfect Binary Tree
Balanced Binary Tree
Degenerate / pathological tree

This article gives a good description of each type of binary trees. and this article gives good illustrations of valid/ invalid types of binary treees.

1. Full Binary Tree

every node has either 0 or 2 children

Here the number of leaf nodes (no children) = number of internal nodes (2 children) + 1

2. Complete Binary Tree

All the levels are completely filled except the last level (level of height h) & last level has all keys as left as possible

3. Perfect Binary Tree

all the internal nodes have two children and all leaf nodes are at the same level.

Here, number of leaf nodes = number of internal nodes + 1.
In perfect binary tree, number of nodes is maximum number of nodes 2^h +1

4. Balanced Binary Tree

Binary tree that is height balanced

left and right subtrees of every node differ in height by no more than 1.

left and right subtrees' heights differ by at most one, AND
The left subtree is balanced, AND
The right subtree is balanced

In balanced tree, height is O(log(n))

5. Degenerate / pathological tree

every parent node has 1 child

behaves like linked list
height is n
worst case complexity basically super cursed

Binary Search Tree

Summary from LeetCode Explore Card
Its a binary tree satisfying binary search property

special form of binary tree where: value in is node must be
greater than (or equal to) any values in its left subtree AND
less than (or equal to) any values in its right subtree.

Traversal

same as binary tree only that:

inorder traversal = ascending order

Search

For each node:

if target value == node vale return the node

if target value < node value search in left subtree

if target value > node value search in right subtree

Search - Recursive

public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) {
            return null;
        } else {
            if (root.val == val) {
                return root;
            } else if ( root.val > val ) {
                return searchBST(root.left, val);
            } else {
                // root.val < val
                return searchBST(root.right, val);
            }
        }              
    }

Time Complexity
time complexity is O(h) where h is height of binary tree
Height Balanced: O(log(n))
Height Skewed: O(n) (n is the number of nodes in tree)

Space Complexity
More details in stack overflow answer
Space complexity of tree: O(n)
Space complexity of recursive function is the height of the stack which would be the height of the binary tree.
Height Balanced: O(log(n))
Height Skewed: O(n)

Search - Iterative

public TreeNode searchBST(TreeNode root, int val) {
    TreeNode init = root;
    while (init != null) {
        if (init.val == val) {
            return init;
        } else if (init.val > val) {
            init = init.left;
        } else {
            init = init.right;
        }
    }
    return init;
}

Time Complexity
Height Balanced: O(log(n))
Height Skewed: O(n)

Space Complexity
space complexity of tree: O(n)
Auxillary space complexity: O(1)

Insert

Find proper leaf position for target node and insert node as a leaf.

search left or right subtrees (if node.value > target or node.value < target)

repeat step1 until reach a leaf node

add new node as its left / right child

Insert - Recursive

    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        } else {
            return insert(root, root, val);
        }

    }

    public TreeNode insert(TreeNode root, TreeNode current, int val) {
        if (current.val < val && current.right != null) {
            return insert(root, current.right, val);
        } else if (current.val < val && current.right == null) {
            current.right = new TreeNode(val);
            return root;
        } else if (current.val > val && current.left !=null) {
            return insert(root, current.left, val);
        } else { // root.val > vall && root.left==null
            current.left = new TreeNode(val);
            return root;
        }

    }

Time Complexity
Time complexity will be proportional to height.
Height Balanced: O(log(n))
Height Skewed: O(n)

Auxillary Space Complexity
Height of recursion stack ~ height of BST
Height balanced: O(log(n))
Height Skewed: O(n)

Insert - Iterative

Node insert(Node root, int Key) {
    Node init = root;
    while (true) {
        if (init.data == Key) {
            break;
        } else {
            if (init.data < Key) {
                if (init.right != null) {
                    init = init.right;
                } else {
                    // init.right == null
                    init.right = new Node(Key);
                    break;
                }
            } else {
                // init.val > Key
                if (init.left != null) {
                    init = init.left;
                } else {
                    init.left = new Node(Key);
                    break;
                }
            }
        }
    }
    return root;
}

Time Complexity
Traversing BST. proportional to height of BST
Height Balanced: O(log(n))
Height Skewed: O(n)

Auxillary Space Complexity
Store current node. constant space
Complexity: O(1)

Deletion

target node has no child: remove the node.

target node has one child: use child to replace itself.

target node has two children: replace the node with its in-order successor / predecessor & and delete target node.

In-order successor: smallest node in right subtree
In-Order predecessor: biggest node in left subtree

class Tree {
    // Return the root of the modified BST after deleting the node with value X
    public static Node deleteNode(Node root, int X){
        // code here.
        Node pre = null;
        Node toDelete = root;
        while (toDelete != null && toDelete.data != X) {
            pre = toDelete;
            if (toDelete.data < X) {
                toDelete = toDelete.right;
            } else {
                toDelete = toDelete.left;
            }
        }
        if (toDelete == null) {
            // node not found
            return root;
        } else {
           // delete node
           if (toDelete.left == null && toDelete.right ==null) {
               // no children
               if (pre == null) {
                   return null;
               } else {
                   if (pre.left == toDelete) {
                       pre.left = null;
                   } else {
                       pre.right = null;
                   }
               }

           } else if (toDelete.left != null && toDelete.right != null) {
               // two children
               // inorder successor (smallest number in right subtree)
               Node preSucc = toDelete;
               Node successor = toDelete.right;
               while (successor.left != null) {
                   preSucc = successor;
                   successor = successor.left;
               }
               toDelete.data = successor.data;
               if (preSucc.left == successor) {
                   preSucc.left = null;
               } else {
                   preSucc.right = null;
               }
           } else {
               // onyl 1 child
               Node child = null;
               if (toDelete.left == null) {
                   child = toDelete.right;
               } else {
                   child = toDelete.left;
               }
               if (pre.left == toDelete) {
                   pre.left = child;
               } else {
                   pre.right = child;
               }
           }
        }
        return root;
    }
}

Self-balancing Binary tree

1. AVL Tree

left subtree & right subtree height diff <= 1
After insert, if height difference > 1, rotations are performed to balance tree

2. Red-Black Tree

each node painted red or black.

root of tree is always black

red node cannot have red parent or red child

every path from node (incl. root) to any of the NULL nodes have same number of black nodes

balances by ensuring that a chai of 3 nodes never gets to form.

Info from: SO

AVL more rigidly balanced -> provide faster look ups
Insert intensive tasks -> red-black
AVL may take more space. AVL store balance factor at each node (O(n)) space. for red-black if data stored in all nodes is >0. sign bit store colour information

Red-black is used for Java TreeMap & TreeSet

Heap

Binary Heap

min-heap
max-heap

min / max -heap is complete binary tree where value of root node is <= / >= either of its children. Same property must be recursively true for all subtrees in binary tree.

Analysis

use when ordering is important (e.g. priority queue)
good at doing comparative operations e.g. if you want values above x. just grab all parents of node X. no need to do any traversals all the down to leaf nodes.

Lookup

unlike BST, left and right subtree has no meaning. you can't divide the tree to search it.
Must go through all nodes
Complexity: O(n)

deletion: O(log(n))

Insertion:

increase heap size by 1
insert new element at end of heap
Heapify. let last node "bubbles up" (swaps with parents) Complexity: O(log(n)) unlike BST, left and right subtree has no meaning. you can't divide the tree to search it.

deletion

replace root / element by last element
delete last element from Heap
heapify to ensure last node is in correct position

Analysis

insertion is better tha O(n)
priority
flexible size
slow lookup. (fast if its finding max or min)

Priority Queue

Queue is FIFO. Objects with higher priority that enter later and get out first.

every element has priority associated with it

element with high priority is dequeued befor an element with low priority

2 elements have same priority they are served according to order in queue.

e.g. emergency room

Heap can be represented in the form of an array. In binary heap priority queue, objects with higher priority would be higher up.
Then look at binary heap as an array and dequeue objects.

Trie / Prefix tree

specialized tree for searching text.

can have >2 children. use to search if character in word exists / subword in word exists.

Space advantage: since its a prefix tree, if words share same prefix, dont have to store it twice.

Search

Lookup for word. Look up for first character. then search children to see if other characters match.
Complexity is the height of the tree.

Complexity: O(log(n))

Insertion

if character doesnt exist need to create new children. If character exists, mark end of word for last node.

insertion requires one to go down depth of trie.

Complexity: O(log(n))

Reasons for using Trees

Store information that naturally forms hierarchy. Eg. the file system on a computer.
Trees (e.g. BST) may provide moderately quick access/search. Quicker than Linked List, slower than arrays.
Trees provide moderate insertion/deletion, Quicker than arrays, slower than unordered linked lists.
No limit on number of nodes since nodes are linked using pointers (like linked list, unlike arrays)

Data Structure - Queue & Stack

limjy — Mon, 22 Mar 2021 16:20:17 +0000

Summary sheet for myself for Queue & Stack DS.
Resources from LeetCode & GeeksforGeeks

Queues & Stack can restrict processing order.

LIFO - Last In First Out
FIFO - First In Last Out

FIFO

First element added to the queue will be processed first

Operations

insert (enqueue) - item added to end of queue
delete (dequeue) - remove first element
rear - end of queue
front - front of queue

Queue - Implementation

Array implementation

ArrayList / dynamic array & an index pointing to head of the queue

class MyQueue {

    private List<Integer> data; //queue
    private int p_start; // head of queue 

    public MyQueue() {
        data = new ArrayList<Integer>();
        p_start = 0;
    }
}

Advantages

easy to implement

Limitations

Space wasted. when item is dequeued, head 'moves' forward and there is empty space at front of arraylist that is wasted.

Linked List Implementation

maintain two pointers front & rear (nodes of Linked List)

class MyQueue {
    QueueNode front, rear;

    // This function should add an item at
    // rear
    void push(int a)
    {
        // Your code here
        if (this.front == null) {
            this.front = new QueueNode(a);
            this.rear = front;

        } else {

            QueueNode addedItem = new QueueNode(a);
            this.rear.next = addedItem;
            this.rear = addedItem;
        }
    }

    // This function should remove front
    // item from queue and should return
    // the removed item.
    int pop()
    {
        // queue is empty
        if (this.front == null) {
            return -1;
        } else {
            int result = this.front.data;
            this.front = this.front.next;
            return result;
        } 

    }
}

Complexity
Time complexity for all operations: O(1) (no loops)
Space Complexity: O(N) for the linked list
Auxillary Space complexity: O(1) (extra space needed for operations)

Circular Queue / Ring Buffer

Array Implementation

resuses wasted storage space from array implementation

fixed size array
pointer - start position
point - end position

class MyCircularQueue {

    private int[] data;
    private int head;
    private int tail;
    private int size;

    /** Initialize your data structure here. Set the size of the queue to be k. */
    public MyCircularQueue(int k) {
        data = new int[k];
        head = -1;
        tail = -1;
        size = k;
    }   
}

initial head & tail is null / -1. cannot be 0. because when queue has 1 element head == tail.
queue is empty if head || tail is initial value (null / -1)

Complexity

Time Complexity
Enqueue O(1)
Dequeue O(1)
Front O(1)
Rear O(1)

Space Complexity
Space complexity: O(N)

Linked List Implementation

Queue in Java

In Java, Queue is an interface, concrete classes are Priority Queue or Linked list.

Priority Queues

allows users to process items based on priority

// Creating empty priority queue 
Queue<Integer> pQueue = new PriorityQueue<Integer>(); 

// Adding items to the pQueue 
// using add() 
pQueue.add(10); 
pQueue.add(20); 
pQueue.add(15); 

// Printing the top element of 
// the PriorityQueue 
System.out.println(pQueue.peek());

        // Printing the top element and removing it 
        // from the PriorityQueue container 
        System.out.println(pQueue.poll()); 

        // Printing the top element again 
        System.out.println(pQueue.peek());

Linked List

implements linked list data structure. Easier insertions / deletions make linked list preferred over arrays

// Creating empty LinkedList 
        Queue<Integer> ll 
            = new LinkedList<Integer>(); 

        // Adding items to the ll 
        // using add() 
        ll.add(10); 
        ll.add(20); 
        ll.add(15); 

        // Printing the top element of 
        // the LinkedList 
        System.out.println(ll.peek()); 

        // Printing the top element and removing it 
        // from the LinkedList container 
        System.out.println(ll.poll()); 

        // Printing the top element again 
        System.out.println(ll.peek())

Priority Blocking Queue

Priority Queue and Linked list are not thread safe. Priority Blocking Queue is thread safe.

// Creating empty priority 
        // blocking queue 
        Queue<Integer> pbq 
            = new PriorityBlockingQueue<Integer>(); 

        // Adding items to the pbq 
        // using add() 
        pbq.add(10); 
        pbq.add(20); 
        pbq.add(15); 

        // Printing the top element of 
        // the PriorityBlockingQueue 
        System.out.println(pbq.peek()); 

        // Printing the top element and 
        // removing it from the 
        // PriorityBlockingQueue 
        System.out.println(pbq.poll()); 

        // Printing the top element again 
        System.out.println(pbq.peek());

Applications

items need not be processed immediately
items processed in FIFO order (e.g. BFS)

Scenarios:

Resource shared among multiple consumers (CPU / Disk Scheduling)
data transferred asynchronously between two processes (response not receive at same rate as sent) (e.g. IO buffers, file IO, pipes etc.)

Queue & BFS

instantiate queue with length N (number of nodes)

start from root.

visit node and enqueue (add) it to queue

dequeue (pop) node from end of queue 5.1 visit all non-visited children nodes of popped node in 4 and enqueue them 5.2 if all child nodes are visited, delete node

repeat till 4-5 till queue is empty

process explained in more detail here
newly-added nodes are not processed immediately, they are processed in the next round (exact same process as queue)

NEVER visit a node twice, else one can get stuck in tree with loop (e.g. graph with cycle)

class Solution {
    //Function to return the level order traversal of a tree.
    Queue<Node> queue = new LinkedList<>();
    ArrayList<Integer> result = new ArrayList<>();
    ArrayList<Integer> levelOrder(Node node) {
        // Your code here
        queue.add(node);
        while (queue.size()>0) {
            Node top = queue.remove();
            result.add(top.data);
            if (top.left != null) {
                queue.add(top.left);
            }
            if (top.right != null) {
                queue.add(top.right);
            }
        }
        return result;
    }
}

Applications of BFS

Traversal
Find the shortest path

LIFO

newest element added to queue is processed first

Operations

push - add element to top of stack, if full then overflow
pop - remove element from top of stack, if empty its undeflow
peek / top - get top element of stack
isEmpty - check if stack is empty

Stack - Implementation

ArrayList Implementation

mantain top (for top of stack) & array

Linkedlist Implementation

Stack in Java

Java has a Stack class

// 1. Initialize a stack.
Stack<Integer> s = new Stack<>();
// 2. Push new element.
s.push(5);
s.push(13);
s.push(8);
s.push(6);
// 3. Check if stack is empty.
if (s.empty() == true) {
  System.out.println("Stack is empty!");
  return;
}
// 4. Pop an element.
s.pop();
// 5. Get the top element.
System.out.println("The top element is: " + s.peek());
// 6. Get the size of the stack.
System.out.println("The size is: " + s.size());

Stack and DFS

More details here

produces spanning tree (no loops)

1 Create an empty stack S.

Initialize current node as root

Push the current node to S and set current = current->left until current is NULL

If current is NULL and stack is not empty then 4.1. Pop the top item from stack. 4.2. Print the popped item, set current = popped_item->right 4.3. Go to step 3.

If current is NULL and stack is empty then we are done.

More details on the algorithm here

Algos - Searching & Sorting

limjy — Thu, 18 Mar 2021 15:58:17 +0000

algos stuff. summary sheet. Information here is all a combination from LeetCode & GeeksforGeeks

Summary: Big O Cheat Sheet

Searching

Linear Search
Binary Search
Jump Search

Linear Search

iterate through entire array, to search for intended item

Time Complexity: O(N)

Binary Search

searching for specific value in an ordered collection

Target - value to search for

Index - current location

Left, Right - indices from to maintain search space

Mid - index to apply condition to decide if search left or right

How it works

Get middle index of sequence, apply search condition to middle index
if unsatisfied / values unequal, half of sequence is eliminated
Continue search in remaining half until target is found

Complexity

Recursion
Time Complexity: O(log(n))
Space Complexity: O(log(n)) (height of stack call, ~ height of binary tree)

Iterative
Time Complexity: O(log(n))
Space Complexity: O(1)

public int search(int[] nums, int target) {
    int left = 0;
    int right = nums.length -1;
    int midIdx = ((right - left) / 2 ) + left;

    while (left <= right) {
        if (nums[midIdx] < target) {
            // search in right half 
            left = midIdx +1;
            midIdx = ((right-left) / 2) + left;
        } else if (nums[midIdx] > target) {
            // search in left half
            right = midIdx - 1;
            midIdx = ((right - left) / 2) + left;
        } else {
            // nums[midIdx] == target
            return midIdx;
        }
    }
    return -1;
}

Jump Search

Check fewer items then linear search ( in sorted array) by jumping / skipping elements.

Search elements in array by index 0,m,2m etc.

find indexes where arr[k*m] < target < arr[(*k+1)m]

linear search from k*m till (*k+1)m to find target

optimal block size to skip

Time complexity = (N/m) + m
For minimum time complexity,
1 = (N/m) + m
1 - m = N / m
m - m² = N
m ~ sqrt(N)
Therefore, optional block size (m) is sqrt(N)

Complexity

Space Complexity: O(1)
Time Complexity:
assuming optimum block size m = sqrt(N),
Time Complexity = (N/m) + m
= (N/sqrt(N)) + sqrt(N)
= sqrt(N) + sqrt(N)
~ O(sqrt(N))

Sorting

Impt: understand trade offs for each algorithm

Elementary : n²

Bubble Sort (stable)
Insertion Sort (stable)
Selection Sort (stable)

More complex : n*log(n), divide and conquer

Merge Sort (stable)
Quick Sort (unstable)

depending on the type of input (eg. list is reversed / nearly sorted) algo will perform differently

For options 4 & 5. merge and quick sort utilize Divide and conquer. Divide and conquer gives log(n) advantage.

sort()

Java arrays.sort() uses dual pivot quick sort
complexity: O(n log(n))

Stable VS Unstable sort

Stable: objects with equal keys appear in the same order in sorted output as input.
** if two objects are compared as equal their order is preserved**

Taken from SO answer

When is stable sort required?
Stable sort is needed when equal elements are distinguishable.

e.g. multiple criterias for sort. sort by object.A THEN object.B

in stable sort. sort by object.B THEN object.A.

Eg. Radix sort.
sorting integers by digits that share the same significant position & value

1. Bubble Sort

repeatedly swap adjacent elements if they are in the wrong order

First pass brings max value to the end of array. second pass brings 2nd max value to second last index of array. To sort all indexes in ascending order need to do N passes. therefore complexity of n²

Time Complexity: O(n²)
Space Complexity: O(1)
Stable: yes

Input: 4A 5 3 2 4B 1
1st pass: 4A 3 2 4B 1 5
2nd pass:
3 4A 2 4B 1 5
3 2 4A 4B 1 5
3 2 4A 4B 1 5
3 2 4A 1 4B 5
3rd pass:
3 2 1 4A 4B 5
output: 1 2 3 4A 4B 5

2. Selection Sort

Find minimum element from unsorted part and putting it at the beginning. min element and element at beginning swap places.

First pass through unsorted part to get min value. Second pass through unsorted part to get second min value. N passes are needed to sort all elements in the unsorted part.

Time Complexity: O(n²)
Space Complexity: O(1)
Stable: no

Input : 4A 5 3 2 4B 1
Output :
1st: 1 5 3 2 4B 4A
2nd: 1 2 5 3 4B 4A
final: 1 2 3 4B 4A 5
swapping of places 4A and 1 made the selection sort unstable

Code example

void sort(int arr[])
    {
        int n = arr.length;

        // One by one move boundary of unsorted subarray
        for (int i = 0; i < n-1; i++)
        {
            // Find the minimum element in unsorted array
            int min_idx = i;
            for (int j = i+1; j < n; j++)
                if (arr[j] < arr[min_idx])
                    min_idx = j;

            // Swap the found minimum element with the first
            // element
            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
        }
    }

3. insertion Sort

best for: small dataset & nearly sorted data
array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in sorted part. (compare one by one with elements in sorted part to find correct position).

class Solution {

  static void insert(int arr[],int i) {
      int num = arr[i];
      int insertionIdx = i;
      for (int j=i-1;j>=0;j--) {
          if (arr[i] < arr[j]) {
              insertionIdx--;
              if (j==0) {
                  break;
              } 
          }else {
              break;
          }   
      }
      for (int x=i;x>insertionIdx;x--) {
          arr[x]=arr[x-1];
      }
      arr[insertionIdx] = num;
  }
  //Function to sort the array using insertion sort algorithm.
  public void insertionSort(int arr[], int n) {
      //code here
      for (int i=1;i<arr.length;i++) {
          if (arr[i] < arr[i-1]) {
              int index = i-1;
              insert(arr,i);
          } 
      }
  }

}

Time Complexity
Best Case : O(n)
In best case, array already sorted, one pass, check that first element in unsorted part, is larger than last element in sorted part.
Worst & Average Case : O(n²
In worse case, array sorted in reverse order. algorithm will scan and shift through entire sorted subsection before inserting. will do this N times for all elements. so n²

Stable: Yes
Input: 4A 5 3 2 4B 1
Output:
1st pass: 1 4A 5 3 2 4B
2nd pass: 1 2 4A 5 3 4B
3rd pass: 1 2 3 4A 5 4B
4th pass: 1 2 3 4A 5 4B
output: 1 2 3 4A 4B 5

4. Merge Sort

Divide and Conquer algorithm
Divides the input array into two halves, (until each subarray is only size 2) calls itself for the two halves, and then merges the two sorted halves.

array is recursively divided into 2 halves until size is 1. Once size is 1, merge process starts and arrays are merged till complete array is merged.

Time Complexity: O(n*log(n))
Space Complexity: O(n)
Stable: yes

5. Quick Sort

best for: average complexity. Avoid if you cant garuntee a good pivot
Divide and conquer. Pick element as pivot point. Split array into two halves, lower than pivot element and higher than pivot element. Repeat process on subarrays until the halves have lenght of 1. Then combine all the elements back together to 1 array.

Time Complexity:
Best / Average : O (n*log(n))
Worst : O(n²)
worst case if the pivot point is the largest/ smallest element. List is not split into half.
Space Complexity: O(log(n))
Stable: no

Non-comparison Sort

Sorts are hard to beat O(n*log(n)) because you have to compare each element. to beat log(n) you need non-comparison sort

takes advantage of the way numbers (specifically integers) are stored in memory.

only work with numbers in a specific range

Radix sort
Counting sort

could be faster than merge or quick sort

When to use which sorting algo?

Insertion
few items / items are mostly sorted.
Bubble
Selection
Merge Sort

best average and worst case is always O(n*log(n)) --> we will always divide up the list equally.
if data set is big, suitable if you have external sorting (space complexity of O(n)) (data does not fit into main memory of computer device) Quick Sort
avoid if you are scared of worst case (cannot garuntee good pivot)
suitable if there is no external sorting. space complexity of O(log(n)) Radix / Counting Sort
sorting integers

Trees & Graph - Searching

BFS VS DFS

BFS:

node is in upper level of tree

shortest path / closest nodes

more memory (need to keep tarck of current nodes)

DFS:

node is in lower level of tree

less memory / does path exist?

can get slow

Eg.

solution if not far from root of tree BFS
tree is deep, solutions are rare
BFS (DFS will take long time) OR
tree is very wide
DFS (BFS will need too much memory)
solutions are frequent but located deep in tree
DFS
path exist between 2 nodes
DFS
path exist between two nodes
BFS

Djisktra & Bellman-Ford

shortest path between two nodes of weighted graph

Bellman: can accommodate for negative weights
Djisktra: more efficient but cannot accommodate for negative weights (greedy algo)

Djisktra cannot accomodate negative weights because it assumes "adding" a weight can never make a path shorter.

DEV Community: limjy

System Design

TOC

Core Java / Java Theory

TOC

Java Stuff

Java syntax

block

Wrapper Class

Strings

Objects class / Java Objects basics

Data Structure Implementations( knpcode.com has really good tutorials and write ups for DS implementations )

Java Implementations / Interfaces / Common Classes ( will only go through general-purpose implementations coz no time )

OOP Concepts & OOP in Java( references in this section mainly from educative articles: OOP & OOP in Java

Java Exception Handling (JournalDev Exception Handling article primarily used as reference for this section )

OOP Concepts

UML

Design Patterns

Constructing HashMap

Getting Item from HashMap

<a name="arraylist-linkedlist-java

Aggregation

Composition

RDBMS Theory

TOC