Data Structures and Time Complexity

 

Collections Overview

https://docs.oracle.com/javase/7/docs/technotes/guides/collections/overview.html

Hashset vs TreeSet vs LinkedHashSet

https://dzone.com/articles/hashset-vs-treeset-vs 

HashMap vs TreeMap vs LinkedHashMap vs HashTable

https://dzone.com/articles/hashmap-vs-treemap-vs

LinkedList vs Arraylist vs Vector

https://dzone.com/articles/arraylist-vs-linkedlist-vs

LinkedIn Learning
https://www.linkedin.com/learning/learning-java-collections/java-collections-framework

Load Balancers

 

A load balancer accepts incoming traffic from clients and routes requests to its registered targets (such as EC2 instances) in one or more Availability Zones. The load balancer also monitors the health of its registered targets and ensures that it routes traffic only to healthy targets. When the load balancer detects an unhealthy target, it stops routing traffic to that target. It then resumes routing traffic to that target when it detects that the target is healthy again.

You configure your load balancer to accept incoming traffic by specifying one or more listeners. A listener is a process that checks for connection requests. It is configured with a protocol and port number for connections from clients to the load balancer. Likewise, it is configured with a protocol and port number for connections from the load balancer to the targets.

Elastic Load Balancing supports the following types of load balancers:

• Application Load Balancers

• Network Load Balancers

• Gateway Load Balancers

• Classic Load Balancers

There is a key difference in how the load balancer types are configured. With Application Load Balancers, Network Load Balancers, and Gateway Load Balancers, you register targets in target groups, and route traffic to the target groups. With Classic Load Balancers, you register instances with the load balancer.

Reference: 

• https://docs.aws.amazon.com/elasticloadbalancing/latest/userguide/how-elastic-load-balancing-works.html
• https://www.educative.io/collection/page/5668639101419520/5649050225344512/5747976207073280
• https://en.wikipedia.org/wiki/Load_balancing_(computing)

Useful Links for Coding Interview

 10 Algorithms that Every engineer should know:
https://link.medium.com/CCWovOubwrb 

17 Killer GitHub Repos You Need to Save Right Now!

https://link.medium.com/A2Td7GDbwrb 

Code Review
 https://google.github.io/eng-practices/review/reviewer/looking-for.html 

https://deepsource.io/blog/java-code-review-guidelines/

https://web.mit.edu/6.005/www/fa15/classes/04-code-review/

https://trishagee.github.io/presentation/code_review_best_practice/

Free EBook for What to look for in a Code Review 

http://leanpub.com/whattolookforinacodereview

What to look for in a Code Review for Java 8
https://blog.jetbrains.com/upsource/2016/08/03/what-to-look-for-in-java-8-code/

Tech Interview Handbook

https://github.com/yangshun/tech-interview-handbook

Coding Interview University
https://github.com/jwasham/coding-interview-university

https://medium.com/codex/my-google-coding-interview-question-166f2922b548

Encoding vs Encryption vs Hashing vs Obfuscation

https://www.linkedin.com/pulse/encoding-vs-encryption-hashing-obfuscation-liban-mohamud

Code Review Best Practices

Caching Solutions

 CACHING SOLUTION

REDIS:

Interactive tutorial : http://try.redis.io/

JAVA Implementation: https://www.tutorialspoint.com/redis/redis_java.htm

Advantages: https://www.tutorialspoint.com/redis/redis_quick_guide.htm

Redis Cluster

Alternative to Redis : Memcached

https://www.linkedin.com/pulse/memcached-vs-redis-which-one-pick-ranjeet-vimal/

https://www.instaclustr.com/blog/redis-vs-memcached/

Caching Best Practices 

1. Validity
2. High Hitrate
3. Cache Miss
4. TTL

There can be three ways to write in the cache

1. Cache Aside
2. Read Through cache 
3. Write through - Write to the Cache, then write to the DB and then return success 
4. Write around - Write to the DB and return success. When there is a cache miss the cache would be updates.
5. Write back - Write to the Cache and return success. there is another system which asynchronously 

Fault Tolerance for Cache

1. Regular Interval Snapshot
2. Log Reconstruction

Learn more about caching using this video 

How to design a Distributed Cache ?

Reading 

https://codeahoy.com/2017/08/11/caching-strategies-and-how-to-choose-the-right-one/

https://www.instaclustr.com/blog/redis-vs-memcached

General Topics for Distributed System

 

What is Service Mash ?

Google File System

Map Reduce

Fallacies of Distributed Systems

1. The network is reliable;
2. Latency is zero;
3. Bandwidth is infinite;
4. The network is secure;
5. Topology doesn't change;
6. There is one administrator;
7. Transport cost is zero;
8. The network is homogeneous.

https://en.wikipedia.org/wiki/Fallacies_of_distributed_computing 

Software Quality
https://asq.org/quality-resources/software-quality 

Lambdas & Streams

 

https://docs.oracle.com/javase/8/docs/api/java/util/function/package-summary.html

https://www.linkedin.com/learning/java-lambdas-and-streams 

Time Complexity Calculation

 Time Complexity Calculation

Code Review Interview

When doing a code review interview or even looking in the code review for the team the following steps can be used 

• Look into the main logic first
• Understand the complete code
• Check for Time and Space complexity. Can we make it better ?
• Check if alternate data structure can be used ?
• Can the Dependency Injection and Inversion of Control be used ?
• Is there code redundancy or code duplication ?  
• Will the code work with concurrency ?
• Naming Conventions
• Readability of the code
• Check if the Logging (Error, Debug, Info) is properly done?
• Check if the Constants can be moved ?
• Can we apply any design patterns to make the code more readable
• Check if it is easy to write the unit test for the code ?
• Unit testing 
• Comments added to the code ?
• IO calls are expensive. Use caching, request collapsing and batch queries to reduce load.

Google Code Review Standards

https://github.com/google/eng-practices/blob/master/review/reviewer/index.md

Videos to watch before a Code Review Interview :

Good Reads :

https://blog.tryexponent.com/how-to-ace-a-code-review/

Probabilistic Algorithms

Bloom Filter

Calculate the memory required and the number of hash functions required here

https://hur.st/bloomfilter/ 

Bloom filter can test with 100% confidence if the value is not present and with lower confidence if the value is present.

Efficiently count with BitMap
https://www.youtube.com/watch?v=8ZgRW0DNus4

Count Min Sketch
The algorithm is used for data which is coming as a stream and we want to have a fast processing. We will have multiple hash functions and will have a table where we store the output of the values hashes. 
If we need to find the occurrence of the value we run the values through the hash, get the stored value and then take the minimum of those values.

https://link.medium.com/Tr0RDZZt2qb 

Sharding

 Sharding

Sharding helps in spreading out the data in different machines in case the data volume to too high. Sharding has its own disadvantages like increase maintenance, query result aggregation, increased infrastructure cost.

Before considering sharding we should consider if vertical scaling will solve the issue. If yes then should go for vertical scaling rather than Sharding.

Advantages of Sharding

• Increase read/write throughput
• Increased storage capacity
• Data Locality

Sharding Types

• Range/Dynamic Sharding
• Algorithmic / Hash Sharding
• Entity/Relationship Sharding
• Geography Based Sharding

References

https://www.mongodb.com/features/database-sharding-explained

https://www.mongodb.com/basics/sharding

Microservices Design Patterns

If you are preparing for an interview or just trying to get started with a Microservice then you should be aware of some of the design patterns which can be used to make your microservices resilient and useful.

Principles Used to Design Microservice Architecture

The principles used to design Microservices are as follows:

1. Independent & Autonomous Services
2. Scalability
3. Decentralization
4. Resilient Services
5. Real-Time Load Balancing
6. Availability
7. Continuous delivery through DevOps Integration
8. Seamless API Integration and Continuous Monitoring
9. Isolation from Failures
10. Auto -Provisioning

 These are some of the Microservices Design Patterns

1. Retry Pattern
   In this pattern we try to retry to request to another microservice for certain number of time in case there is a failure before return a failure status to the client.
   
   
2. Circuit Breaker Pattern
   In this pattern the microservices will keep track on the number of times a service returns failure. In case the number of failures goes above a threshold then the circuit opens and starts returning error for the calling service. The circuit breaker will keep on checking the failing service. Once we get a success then the circuit will close again so that the traffic can go to the service which was failing previously.
   
   
   
   
   
   
   
   
   
3. Bulkhead Pattern
   The patterns helps in isolating the services within a microservice from failure.
   
   
   
   
   
4. Aggregator Pattern
   The pattern is used to get the response from various microservices and the aggregate the result together.  
   
   
5. API Gateway
   The request first goes to the API gateway which routes the request to respective service based on the API Gateway.
   
   
6. Chained or Chain of Responsibility
   Chained or Chain of Responsibility Design Patterns produces a single output which is a combination of multiple chained outputs. So, if you have three services lined up in a chain, then, the request from the client is first received by Service A. Then, this service communicates with the next Service B and collects data. Finally, the second service communicates with the third service to generate the consolidated output. 
   
   
7. Asynchronous Messaging
   This pattern is used for asynchronous messaging between different microservices. We can add a messaging queue between the services. This pattern is helpful if we have a lot of requests coming and the service might need some time to process the request. 
   
   
8. Event Sourcing
   The event sourcing design pattern creates events regarding the changes in the application state. Also, these events are stored as a sequence of events to help the developers track which change was made when. So, with the help of this, you can always adjust the application state to cope up with the past changes. You can also query these events, for any data change and simultaneously publish these events from the event store.
   
   
9. Command Query Responsibility Segregation
   According to this pattern, the application will be divided into two parts: Command and Query. The command part will handle all the requests related to CREATE, UPDATE, DELETE while the query part will take care of the materialized views. 
   
   
10. Branch
    Branch microservice design pattern is a design pattern in which you can simultaneously process the requests and responses from  two or more independent microservices.
    
    
11. Saga Pattern
    This pattern helps with implementing a business transaction that spans multiple services. A saga is a sequence of local transactions. Each local transaction updates the database and publishes a message or event to trigger the next local transaction in the saga. If a local transaction fails because it violates a business rule then the saga executes a series of compensating transactions that undo the changes that were made by the preceding local transactions.
    

    There are two ways of coordination sagas:

• Choreography - each local transaction publishes domain events that trigger local transactions in other services
• Orchestration - an orchestrator (object) tells the participants what local transactions to execute
  https://medium.com/javarevisited/distributed-transaction-management-in-microservices-part-2-saga-pattern-53808a55e641
12. 2 Phase or 3 Phase Commit
    https://medium.com/javarevisited/distributed-transaction-management-in-microservices-part-1-bb7dc1fbee9f 
13. Backend for Frontend (BFF) design pattern
    BFF is a variant of the API Gateway pattern, but it also provides an additional layer between microservices and each client type separately. Instead of a single point of entry, it introduces multiple gateways
    Video : https://www.droidcon.com/2021/11/10/backend-for-frontend-the-secret-of-a-great-mobile-project/

Reference:

• https://medium.com/aspnetrun/microservices-resilience-and-fault-tolerance-with-applying-retry-and-circuit-breaker-patterns-c32e518db990 
• https://www.edureka.co/blog/microservices-design-patterns
  
• https://microservices.io/patterns/data/saga.html
• https://medium.com/trendyol-tech/saga-pattern-briefly-5b6cf22dfabc#:~:text=2PC%20works%20as%20a%20single,makes%20the%20data%20eventually%20consistent.
• https://medium.com/mobilepeople/backend-for-frontend-pattern-why-you-need-to-know-it-46f94ce420b0

Algorithms

Sorting Algorithm

 https://www.geeksforgeeks.org/radix-sort/

https://www.geeksforgeeks.org/heap-sort/

Dynamic Programming - Optimization of the solution.

1. Greedy Algorithm  - In a greedy algorithm the decision is taken once and the result is calculated based on the same decision. Like Dijastra's Algorithm where we always take the shortest vertex to find the shortest path. Other example Minimum cost spanning tree - Always select the minimum cost edge.

2. Dynamic Programming - The decision is taken at every step to get to an optimal solution.

Memoization  is a technique used to optimize the time complexity. In the technique we store the result of the calculation so that we can use them again. It is a top down approach. This is used in Recursion.

Tabulation is a technique which is a bottom up approach. We start with the smallest value and calculate the bigger problems. It is used as part of the iterative method

Software Architectural Patterns

 

Architectural Patterns

1. Layered pattern
2. Client-server pattern
3. Master-slave pattern
4. Pipe-filter pattern
5. Broker pattern
6. Peer-to-peer pattern
7. Event-bus pattern
8. Model-view-controller pattern
9. Blackboard pattern
10. Interpreter pattern

Hexagonal Architecture

Onion Architecture

Layered Architecture

Domain Driven Design

Domain-Driven Design is about creating shared understanding of the problem space that is reinforced ubiquitously via conversations, code and diagrams.
Things to know in Domain Driven Design 

1. What is Bounded Context ?
   Bounded context defines tangible boundaries of applicability of some sub-domain. It is an area where a certain sub-domain makes sense, while the others don't. It can be a talk, a presentation, a code project with physical boundaries defined by the artifact.
   
   
2. What is Ubiquitous Language ?
   A Bounded Context is an explicit boundary within which a domain model exists. Inside the boundary all terms and phrases of the Ubiquitous Language have specific meaning, and the model reflects the Language with exactness.

Event Driven Design

Reactive Architecture

https://www.lightbend.com/blog/understand-reactive-architecture-design-and-programming-in-less-than-12-minutes

Reference

• https://towardsdatascience.com/10-common-software-architectural-patterns-in-a-nutshell-a0b47a1e9013
• https://medium.com/@edamtoft/onion-vs-clean-vs-hexagonal-architecture-9ad94a27da91
• https://www.codeguru.com/csharp/understanding-onion-architecture/

Network Layer

 Websockets vs HTTP

WebSockets, on the other hand, allow for sending message-based data, similar to UDP, but with the reliability of TCP. WebSocket uses HTTP as the initial transport mechanism, but keeps the TCP connection alive after the HTTP response is received so that it can be used for sending messages between client and server.

https://sookocheff.com/post/networking/how-do-websockets-work/#:~:text=WebSockets%2C%20on%20the%20other%20hand,messages%20between%20client%20and%20server.

Network Layer

Capacity Estimation and Planning

 1 Byte = 8 bits

1 byte = 1 ASCII character. 

2 bytes = 1 UTF-16

UTF-8

UTF-8 is based on 8-bit code units. Each character is encoded as 1 to 4 bytes.

2^32  = 4,294,967,296

1 KB = 1000 Bytes

1 MB = 1000 KB

1 GB = 1000 MB

1 TB = 1000 GB

1 PB = 1000TB 

1 Million = 1,000,0000 = 10^6

1 Billion = 1,000,000,000 = 10^9

1 Trillion = 1,000,000,000,000 = 10^12

Request Calculation per second

1 M req per day = 1 M req / 86400 seconds = 12 req per second

1.5 M req per day = 1.5 * (1 M req / 86400 seconds) = 18 req per second

10 M req per day = 10 M req / 86400 seconds = 120 req per second

1 B req per day = 1B req / 86400 seconds = 12000 req per second

Redis can handle 81000 req per second

Number of users
Twitter users = 300 million active monthly users

Youtube = 2 Billion active monthly users
Number of videos watched per day = 5 billion

Facebook users 3 billion users out of which 2 billion are daily active users

Pastebin users = 17 million

Bitly = 600 million bitly link created per month.

Name	Length
char	1 byte
short	2 bytes
int	4 bytes
long	4 bytes
float	4 bytes
double	8 bytes
long double	16 bytes Note that on AIX® and Linux® PPC a long double is 8 bytes.
pointer	4 bytes
ptrdiff_t	4 bytes
size_t	4 bytes
time_t	4 bytes
clock_t	4 bytes

Videos :

Design Principles and Design Pattern

 Design Principles

• Encapsulate what varies
• Favor Composition over Inheritance
• Loose Coupling
• Program to interfaces
• SOLID Principle
• Single Responsibility Principle
• Open/Closed Principle
• Liskov's substitution principle
• Interface Segregation Principle
• Dependency Inversion Principle.

   Design Patterns

• Creational Design Pattern
• Factory Pattern - 
  Let the factory do the job of creating the objects rather than instantiating the object using New
  https://java-design-patterns.com/patterns/factory/ 
• Abstract Factory Pattern -
  Creating a Factory from list of factories.
  https://java-design-patterns.com/patterns/abstract-factory/
• Builder Pattern - 
  The builder pattern is an object creation software design pattern with the intentions of finding a solution to the telescoping constructor anti-pattern. Telescoping constructor anti-pattern means that the constructor is getting bigger and bigger due to addition of a lot of parameters.
  https://java-design-patterns.com/patterns/builder/
• Prototype Pattern - Clone the existing object and then make modification to the object rather than creating the object from scratch.
  https://java-design-patterns.com/patterns/prototype/
  In java can be done by implementing the Cloneable  and overriding the Clone() method. But Clonable makes a shallow copy. We need to override the clone method for the child objects and the clonable method should be updated
• Singleton Pattern
  

Restful Services

https://www.softwaretestinghelp.com/restful-web-services-interview-question/

https://restfulapi.net/caching/

Microservices Design Patterns : https://vslive.com/Blogs/News-and-Tips/2018/02/Go-Fast-by-Going-Micro-Microservices-Design-Patterns-You-Should-Know.aspx

http://blog.arungupta.me/microservice-design-patterns/

https://www.edureka.co/blog/microservices-design-patterns

Authentication & Authorization : https://medium.com/tech-tajawal/microservice-authentication-and-authorization-solutions-e0e5e74b248a

Learn to be a backend Developer : https://medium.com/tech-tajawal/modern-backend-developer-in-2018-6b3f7b5f8b9

Design Steps

• Identify object model
• Create Model URIs
• Determine Representations
• Assign HTTP Methods

JAX-RS 2.0 (Java API for RESTful Services).

JAX-RS stands for JAVA API for RESTful Web Services

From <https://www.tutorialspoint.com/restful/restful_jax_rs.htm>

From <https://restfulapi.net/create-rest-apis-with-jax-rs-2-0/>

Caching

https://www.tutorialspoint.com/restful/restful_caching.htm

Has the following attributes in the header

• Date
• Last Modified
• Cache Control - Public, Private, no-cache/no-store, max-age, must-revalidate
• Expires
• Age

1. Scope microservices using Bounded Context
1. Domain Driven Design- Bounded Context
2. Ubiquitous Language
2. N+1 problem - https://restfulapi.net/rest-api-n-1-problem/
3. Asynchronous Web Services - Event Based
1. Competing Worker Pattern
2. Fanout Pattern
3. Async API Call
4. Architecture of API Based Microservice
1. Functional Requirement
1. Loosely coupled
2. Independently changeable
3. Independently deployable
4. Support and honor contracts
5. Technology Agnostic
6. Stateless API
2. API Architectural Styles
1. Basic REST Implementation
1. Following the rest constraints
2. HTTP Protocol is followed
3. Inherits the advantages of the Web
4. Uses JSON/XML to send and receive data
5. Uses Resource End point to communicate
6. Uniform Resource Identifier
7. Stateless
8. Cacheable
9. Example
   
2. Pragmatic REST
1. Not all resources would do CRUD Operation
2. Some resources takes actions/Task
3. Name these resources as Verbs instead of nouns
3. HATEOAS REST
4. RPC
5. SOAP
3. API Architectural Pattern
1. Façade Pattern
1. Proxy Pattern
1. Stateless service pattern

1. No State information maintained on server
2. Clients maintain state
3. State is send as part of the request
4. Advantages: Help in scalability, performance and availability

5. Composing Microservices
1. Composition Patterns
1. Broker Composition Pattern
2. Aggregate Composition Pattern
3. Chained Composition Pattern
4. Proxy Composition Pattern
5. Branch Composition Pattern

Data Consistency

1. Two Phase Commit
2. Saga Pattern-Saga Execution Coordinator

3. Eventual Consistency : Eventually the Data would be consistent across the systems. It is a practice rather than pattern. It chooses Availability over Consistency.

API Gateway

Open Source API Gateway

https://konghq.com/