Low Level Designs

Introduction to OOP & LLD

    • High level Design
      • HLD Deals with different infrastructure layers that are going to work together for efficient working of a system.
        • Load balancer, appln servers, DB, Cache
    • Low Level Design(Object oriented design)
      • Deals with details/implementation of software/code that is running
    • A research says that an software engineer only spends 12% of time doing coding. Other 88% goes in other productive things like meetings, reviews, testing, automation.
    • LLD helps make better use of 88% of time

    LLD includes

    • Readable & understandable
    • Requirement gathering
    • Extensible system -> easy to add new features
    • Maintainable system -> Easy to keep current system(w/o new requirements) working. Bugs/updates/3rd party library changes,

    Programmatic Paradigm

    • Procedural -> C
      • Set of instructions(Function), 
      • Action is performed on Entities(in real world Entities perform action)
      • Any procedure can play around with entity attributes

    • Object Oriented -> Java, Python, JS, c#
      • Software system should have entities & each entity controls its attributes and also has a defined behavior
      • Entities are core of OOP
      • 1 Principal(fundamental concept) of OOP
        • Abstraction
      • 3 pillars of oop
        • Encapsulation, Inheritance, Polymorphism 
    • Functional programming -> Scala, Haskel, F#
    • Reactive Programming -> Java

     Abstraction

    • Representing complex system in terms of ideas. Idea is any thing that has attributes/data and associated behavior
    • Others don't need to know about the details of impl of idea

    Encapsulation

    • Store attributes & behavior together of an idea
    • Protects attributes & behaviors from illegitimate access from other classes. 

    Terms of OOP

    • Class - Blueprint of an idea. It represents structure of idea

    OOP and Design Principles

    • Default constructor
      • no args
      • sets values 
    • Primitive type Variables are stored outside of Java Memory
    • Object type variables are stored in Java Memory & Variable stores address of Object
    • Shallow copy: Where new object is created, however, the new object still refers to attributes of old object. Which means, they share some data
    • Deep Copy: No shared data. It is impossible to create Deep copy in Java

    OOPs - 3 


    LLD : Solid Design Principles (set of guidelines for software engineer that help in developing good systems). Software systems should be extensible, maintainable, reusable, easily testable. modular.  

    • S - single responsibility
      • Every code unit(Package, class, method) in my code base should have exactly 1 responsibility
    • O - Open Close(open for extension and closed for modification)
      • Adding new features should not require modification to existing code
    • L- Liskovs substitution principle
    • I - Interface segregation
    • D- Dependency inversion
    Design a Bird
    • Bird
      • name
      • type
      • noOfWings
      • color
      • fly()
      • makeSound() -> write code based on type of make/print sound
      • dance()
        • makeSound() -> write code based on type of make/print sound
        • Problems due to too many if-else
          • Understandability
          • Difficult testing due to too many if-else
          • merge conflicts(difficult for multiple engineers work in parallel)
          • code duplication
          • less code reuse
          • It violates S of SOLID principles
        • Monster method
          • Does more than what its name suggests
        • Common/Utility Package
          • They end up becoming garbage place for all the code that engineer doesn't want to think on where to put 
    • v2 bird
      • Let bird class have generic details and not specifics
      • sub classes sparrow(), peacock(), crow() have the specifics
      • to add new bird, just add new sub class(open/close priciple)
      • Bird() class has less reason for change(single responsbility followed)
      • How to extend to a bird like penguin which doesn't fly
        • Empty implementation for fly() method
        • raise exception in the method
        • Ideal sol: If an entity doesn't support a behavior, it should not have method to do the behavior
          • bird() 
            • flyingBird()
              • crow(), sparrow()
            • Non-flying bird() 
              • penguin()

    LLD : Solid - 2 (Liskov, Interface Segregation, and Dependency Inversion)

    • Liskovs substitution
      • Classes are meant for Entities(not behaviors)
      • Interfaces are meant for behaviors
      • Bird class will have generic attributes & behaviors
      • Instead of subclass for fly(), create an interface flyable with method fly(). Bird sub classes that can fly will implement interface and others wont.
    • Liskovs substitution
      • Objects of any any child should as-is substitutable in a variable of parent type with out requiring any code changes
      • Overriding is to do things in different way not to do different thing
    • Interface Segregation
      • Interfaces should be as light as possible. Ideally, interfaces should have only one method. Such interfaces are called Functional Interfaces.
    • Dependency inversion
      • No two concrete classes should directly depend on each other. They should depend on each other via interface
      • For code reuse, create utility Interface. Concrete classes will implement the Interface which will be used in Bird sub classes.
      • Dependency Injection(not design principle AND not part of SOLID)
        • It is related to Dependency inversion
        • No need to create object of dependency by self. 
        • Let creator of your class give object to you(via constructor of class dependent)

    LLD: Creational Design Principles

    •  Design Patterns(Implementation of design principles)
      • The pattern is concerned with how to create an object(directly, builder, separate class like factory class, singleton)
      • Pattern is something that happens regularly/frequently
      • Design pattern is well established pattern to common software design problems.
      • GOF(Gand of Four) book - published 23 design patterns
      • Why learn design pattern
        • shared vocabulary
        • saves lot of time
      • Creational Design Pattern
        • How an object is created
        • How many objects created
      • Structural design patterns
        • How will a class be structured
        • What attributes will be there in class
        • How will it interact with other classes
      • Behavioral design patterns
        • How to code an action
    • Creational Design Patterns
      • Singleton(only one object can be created)
        • Def: Allows to create only one object
        • Problem statement(why): 
          • Class which is having a common resource. Creating duplicate db resources is waste of memory.
          • Creation of object is expensive
        • Uses Cases: DB connection, Loggers
        • How to implement:
          • Approach 1: (single threaded appln)
            • Make constructor private 
            • create a public static method to check if instance already exists, if no create else return the existing object 
          • Approach2: To avoid concurrency issues
            • make instance variable as Static & initialize it to create DB connection
            • This will be created when class is first loaded in to jvm
            • Cons: 
              • Application startup time can increase
              • Can't give variable params as input
          • Approach3(Double check locking): 
            • There may be issue that multiple objects are created in concurrency situations.
            • use Synchronize to lock the instance creation using double check locking. This is best approach in prod where perf is important.
            • Pros: Addresses concurrency issues
            • Cons: Fails Serialization
          • Enums: How to implement Singleton using Enums
        • Pros: Resource Efficiency
        • Cons: Difficult to test the singleton class with various inputs as only one instance is created in lifetime
      • Builder
      • Factory
      • Prototype

    LLD: Factory and Prototype Design Principles

    • Problem statement: We had a class that had too many attributes. It requires to validate attributes prior to Object creation. 
      • Soln options: Create too many constructors. It results in telescoping constructors and sometimes it is not possible as well
      • soln option2: Some data structure that can allow multiple attributes with each having a specific name eg: constructor with a parameter map<string, object>. Data type verification cannot be done in map(eg: int cannot be validated in map)
      • Soln3: Helper class which can be passed as parameter to actual class. The Helper helps in building actual object. This is Builder Design pattern. 
    • Builder Design Pattern: Allows to create an object where we have following constraints
      • Too many attributes
      • Validate attributes before creating an object and do not create object if validation fails
      • Immutable class
    • Implementation
      • Create class Student with all the attributes, constructor with builder obj & getBuilder method
      • create class Helper as inner class with same set of attributes. Add setters & getters
      • setters to return builder/helper object instead of void
      • Add build method to Builder class that creates and returns Student Object
      • Student s = new Student(helper){
            s.name = helper.name;
            if (helper.age >50) raise exception else s.age=helper.age;
        }
        Copy helper attributes to Student attributes in helper after validations
      • Now validations can be added in Student constuctor
      • User.javapublic class User
      • {
      • //All final attributes
      • private final String firstName; // required
      • private final String lastName; // required
      • private final int age; // optional
      • private final String phone; // optional
      • private final String address; // optional
      • private User(UserBuilder builder) {
      • this.firstName = builder.firstName;
      • this.lastName = builder.lastName;
      • this.age = builder.age;
      • this.phone = builder.phone;
      • this.address = builder.address;
      • }
      • //All getter, and NO setter to provde immutability
      • public String getFirstName() {
      • return firstName;
      • }
      • public String getLastName() {
      • return lastName;
      • }
      • public int getAge() {
      • return age;
      • }
      • public String getPhone() {
      • return phone;
      • }
      • public String getAddress() {
      • return address;
      • }

      • public static class UserBuilder
      • {
      • private final String firstName;
      • private final String lastName;
      • private int age;
      • private String phone;
      • private String address;
      • public UserBuilder(String firstName, String lastName) {
      • this.firstName = firstName;
      • this.lastName = lastName;
      • }
      • public UserBuilder age(int age) {
      • this.age = age;
      • return this;
      • }
      • public UserBuilder phone(String phone) {
      • this.phone = phone;
      • return this;
      • }
      • public UserBuilder address(String address) {
      • this.address = address;
      • return this;
      • }
      • //Return the finally consrcuted User object
      • public User build() {
      • User user =  new User(this);
      • validateUserObject(user);
      • return user;
      • }
      • private void validateUserObject(User user) {
      • //Do some basic validations to check
      • //if user object does not break any assumption of system
      • }
      • }
      • }

      • UserBuilder Examplepublic static void main(String[] args)
      • {
      • User user1 = new User.UserBuilder("Lokesh", "Gupta")
      • .age(30)
      • .phone("1234567")
      • .address("Fake address 1234")
      • .build();
      • System.out.println(user1);
      • }
    • Articles/books/sites: refactoring.guru, sourcemaking & read api reference of firebase

    LLD: Prototype and Factory Design Principles

    • Problem: Given an object of a class, we need to create a copy of it
    • Possible soln: copy each attribute by attribute
      • Cons: tight coupling, attributes would be private and not accessible to client, there may be many child classes incase of inheritance
      • If a client wants to create copy of an object, having logic to create copy within the client is prone to errors.
      • Ideal soln is to out source the work to create Copy to Object itself.
        • Benefits: 
          • No tight coupling and client doesn't need to know internals of the class to be copied
          • No violation of open/close principal
    • Prototype design pattern
      • Often there are scenarios where we create instance of a prototype, change few attributes and done. Prototype works as a template
      • Often there are scenarios where we don't want to create objects from scratch. Rather we want to create from template and changing the values from copy
      • How to create 
        • In the class that you want to create prototypes of, declare a method clone(), It creates the copy of current object Note: if you have child classes, then they must also override. 
        • Store the prototypes in a registry(Registry is also a class)
        • Client calls registry to get prototype, it then creates a prototype and does its work on the copy.
        • Normally the prototypes are stored in Registry at app start time. Registry is a singleton
      • Prototype design pattern: If you want to create copy of object, rather than copying yourself, the object should have the responsibility to create copy. 
      • Registry Design Pattern: If you need something again and again, store those things in registry. Eg: spring boot dependency injection.
      • Implementation

        package designpatterns.prototype
        public class Prototype<T>{
           T clone();
        }
        Public class Student implements Prototype<Student>{
               Public Student clone(){
                     Student copy = new Student();
                      copy.age=this.age;
                      copy.name=this.name;
                      copy.batch=this.batch;
                      copy.avgpsp=this.avgpsp;
                }
               public class StudentRegistry{
                  private Map<String, Student> map = new Hashmap();
                  void Register (String key, String student){
                            map.put(key, student);
                   }
                   Student get(String key){
                        map.get(key);
                     }
                  }
        public class client{
                 public static void fillRegistry(StudentRegistry registry){
                  Student aprBatchStudent = new Student("apr 21");......
                   registry.register(key:"april21batch",student:aprBatchStudent);
        }
              public static void main(){
                 StudentRegistry studentRegistry = new StudentRegistry();
                 fillRegistry(studentRegistry);
                 Student venk=studentRegistry.get("april21Batch").clone();
                 venk.name="Desu";
                 venk.age=45;
                 

    LLD: Factory Design Pattern

    • UserService{
         Database db =...;
          Create User(){
               Query q = db.createQuery("insert int...");
                q.execute();
      }

      DataBase will be interface or Abstract class. If Database was a class, Dependency Inversion design principle will get violated.
      We would want DB to be an interface/abstract class so that in future we can change DB
      Similarly Query will also be interface/abstract class

      createQuery is to do nothing but return a new object of corresponding query(Factory Method)

    • Factory Method
      • Purpose of such method is nothing but to create a new object required class.
      • A method in a class that returns a new object of related class
      • Factory Method Design Pattern says, often we have interface which has a method that does nothing but returning an object of some other class. When you implement such interface, each of the implementations of that interface will return an object that is either of the Query or of any its subclass
        Benefit: When DB is changed from sql to postgres, no change to code is required
    • Abstract Factory design method
      • Divide class into 2 classes
        • To have attributes  -> <<Database>>
        • to have factory methods -> <<DatabaseFactory>>
        • Database will have Factory method to return DatabaseFactory instance
      • A collection of factory methods
      • UserService {
            Database db;
            DatabaseFactory dbf;
        }
      • Use Case: UI Libraries
      • Frameworks to create apps: Flutter, React Native which are cross platform frameworks
      • Based on object of a class, we need corresponding object of some other class
        However, it will have lot of factory methods which will lead to SRP design violation.
        Hence, we break into 2 classes. One is DBClass and other is DBFactoryClass. These are linked by adding factory method in DBClass which returns DBFactoryClass object.
    • Practical Factory Design method
      • Whenever multiple variants of class/interface create object of correct one based on parameter
      • Different ways to create object of subclass
      • Create object of the same class
      • XFactory - It will have methods to create objects of X based on different criteria. 
      • case study/applicability : When ever there are multiple variants of a class and you want to create object of the correct variant based on parameter.
    • Summary
      • Based on Obj of a class we need corresponding object of some other class
      • So, we put a factory method for it
      • But a lot of factory methods come up =>  SRP is getting violated
      • We break into 2 classes (regular and factory class)
      • We link the 2 classes by having factory method in regular class to return factory class
    • UIFactory{
        public Button createButton();
        public Menu createMenu();
      }
    • IOSFactory extends UIFactory
    • AndroidFactory extends UIFactory


    • https://refactoring.guru/design-patterns/factory-method
    • https://github.com/Naman-Bhalla/tictactoeaug21/blob/master/src/main/java/com/scaler/tictactoe/factories/player/PlayerFactory.java

    LLD: Structural Design Pattern

    • How a code base should be structured
      • what classes should be there
      • what attributes should be in class
      • How one class should talk to other classes
    • Adaptor Design Pattern
      • Adapters - They try to convert one format to other to allow working with a device not directly supported.
      • Adapter design patten allows a class to work with another class that is not already supported.
      • Consider using Adapter Design pattern when you have to work with 3rd party api.
      • How to implement
        • Step1: When connecting to 3rd party api, create an interface with the methods that you need
        • Step2: Create a class that implements the interface 
    • Decorator Design Pattern
      • When we have an entity, and add multiple things to that entity, still the combined entity remains the same type.
      • Whenever we want to enhance the behavior of an object at runtime. 

    LLD: Structural Design Pattern - Fly Weight and Facade

    • Design a coffee machine
    • Design a Pizza maker
    • watch video on Facade design pattern https://www.youtube.com/watch?v=K4FkHVO5iac
    • Flyweight design pattern
      • Online games PubG, CoD, Clash of Clans
      • When we play any online games 
        • initial state of the game is loaded to all user devices
        • Any action that any person takes is replicated to all other player devices
      • Often we have objects with 2 different type of properties. Intrinsic and Extrinsic properties. Extrinsic are external and can change. If the repetition of intrinsic properties is leading to lot of memory then consider removing intrinsic properties from the class
      • Divide/split class into 2 classes. One with intrinsic property and other with extrinsic property.

    LLD: Behavioural Design Pattern

    • How will you implement particular type of functionality(behavior) in the codebase.
    • Strategy Design Pattern: Whenever there are multiple ways to do something(perform a behavior) don't put the code in client class. It will violate open/close principal. Instead create an interface to represent the behavior, and make each variant of that behavior as a sub-class of the interface. 
      Whenever there are multiple algorithms/ways/strategies to do something, 
    • Pros of Strategy Design Pattern
      • SRP & O/C
    • Adapter vs Strategy design pattern
      • Structural vs behavior design pattern -> they are similar but not same.
      • talk to 3rd party vs how to implement a behavior which has multiple variants
      • classes wrap 3rd party libraries vs classes implement the behavior.
      • Client talks to interface and interface has multiple classes that wrap 3rd party classes vs client talks to interface and interface has multiple classes.
    • Observer Design Pattern
      •  Publisher -  Consumer model OR Producer - Consumer model OR Speaker listening model OR Subject observer model
        • We have a class(publisher) that has special event that others(Consumers) are interested about to perform own actions.
        • Publisher class should maintain list of subscribers.
          Subscribers in an interface implemented by any one who wants to know when the event happened. 
          Publisher provide a way for subscribers to register & unregister
    • https://github.com/Naman-Bhalla/lldSept2022
    • https://refactoring.guru/design-patterns/factory-method
    • https://refactoring.guru/design-patterns/observer
    • HM:

    LLD: UML Diagrams and Schema Design

    • Use case diagrams
    • Class diagrams
    • Stakeholders in software design
      • Client - requirement gathering and demo final product
      • Architect - review the design and get approval
      • manager - carrier progression
      • Business(product, ceo) - Understanding the requirements.
    • A picture worth 1000 words
    • UML - Unified Modeling Language
      • It provides standardization on how to represent different software engineering concepts in diagram.
    • Types of UML diagrams
      • Structural -> how the codebase is structured
      • Behavioral -> How the system/feature works, different features supported by system
    • Structural UML diagrams: 
      • Class diagram- represents diff entities in the software system & relationship between these entities. It includes Classes, Abstract Classes, Interfaces, Enums.
        • implementation of interface, extension of a class, having an attribute of another class.
        • 3 Blocks-> Name, attributes, methods of the class
          • Class
            • Name
            • attributes: accessmodifier(+, -, #) name:datatype 
            • methods: accessmodifier(+, -, #) name(datatype of parameters):return type
            • Static is represented with Underline below it
            • Interfaces
              • <<Name>>
              • name(datatype of parameters):return type
              • Static is represented with Underline below it
            • Abstract Class
              • Exactly like a normal class with just 1 diff
              • anything abstract is represented in Italics
            • Enums
              • Name
              • diff values separated by comma
          • How to represent relationship between entities
            • 2 categories of relations
              • Inheritance(is-a) relation. Arrow from Child to Parent.
                • Parent-child(extending class)
                • interface implementation
              • Association(has-a) relation. 
                • having an attribute of other class
                • It is of 2 types
                  • Composition
                    • Creation
                    • Strong Association
                    • Represented by line & empty Rhombus 
                    • A composes B, if objects of B can't exists with out object of A.
                    • Class -> Assignment relationship
                  • Aggregation
                    • Weak Association
                    • Represented by line & filled Rhombus
                    • The other entity has independent existence.
                    • Bookmyshow -> show & ticket relation
        • Package diagrams
        • Object diagrams
        • Component diagram
      • Behavioral 
        • Activity diagram
        • Use case diagram - Different features/functionalities that are supported by a software system.
          • Who uses those functionalities
          • 5 key words
            • System Boundary(scope of  my system). It doesn't include any outsourced feature. It is represented by RECTANGLE
            • Use Cases. It is functionality/feature/behavior. It is represented as verb. Represented side an OVAL
            • Actor: People who use a particular use case. It is NOUN. Represented by a stick diagrams. Rep by arrow the relation between a use case and actor
            • Includes: Think of every feature as a function. eg: checkout includes fill address & pay. Parent use case includes child use case. Arrow from parent to child.
            • Extends: One feature has multiple variants. Login by email, mobile, social. In this case the arrow is from specialty to Generality. 
        • Assignment
          • Draw a use case diagram for scalers software system
            • Atleast 5 use cases
            • Atleast 2 actors
            • Atleast 1 use case should involve some other use case
            • Atleast 1 use case should have special variant
        • sequence diagram
      • HM
        • Component diagram
        • Activity diagram
        • sequence diagram
      • https://www.youtube.com/watch?v=pCK6prSq8aw
      • https://www.youtube.com/watch?v=Iz6FnvhQ4Ms
      • https://github.com/Naman-Bhalla/splitwise_nov21/blob/master/README.md

      LLD: Schema Design

      • Diff types of LLD problems
        • LLD round/coding/theoretic round (Amazon, MS)
        • Design round -> Design a real system(non-startup orgs)
        • Machine Coding(popular in startups)- test your OOPs & end-end implementation
          • No gathering requirements required.
          • Clarifying req
          • Use case diagram
          • Class diagram
          • Schema 
          • code end-end impl with good practice
          • Followup qns like how do you handle concurrency, How will you scale the system,  
        • Theory(oop, design principles, design patterns)
        • Design(non-startups) -> test knowledge by solving problem
          • Evaluate person in Gathering requirements eg: https://github.com/Naman-Bhalla/splitwise_nov21/blob/master/README.md
          • Clarifying requirements
          • Identify edge cases
          • Use case diagram
          • Class diagram
          • Schema design
        • Design & Impl(Startups) -> 
      • Scaler classes approach
        • 1 liner statements - 5mins
        • Gather req- 5mins
        • Clarifying the requirements
        • Class diagram- 5mins
        • Schema design- 5mins 
        • End-End implementation - > 1hr
        • Discussion
      • Gathering requirement
        • Input: one liner
        • output: a) list of features b) visualization in your mind 
        • How to go about: start with overview. 
          • You know about system
            • Brief about the system and take confirmation if you are correct
          • You don't know the system
            • Do you mind to give idea about what system does & problem statement that system solves
            • Overview & scope 
            • What kind of problem is it
              • Entity (Bird, Pen)
              • Real life systems / management systems(webapis) - book my show, Parking lot, 
              • Real time appln/systems(Gaming where multiple people works) - Tic Tac Toe, ludo
              • Engineering cases - Distributed cache
        • Product mindset
          • suggest ideas for gathering requirements
            • take a step back and see if everything makes sense
            • scope of clarification
            • see if everything fits together
            • more about edge cases of a behavior
            • try to visualize and if you have any doubts, ask
            • Ideally ask doubts that affect design
            • Stop when you think you are able to clearly visualize the scope of the system.
            • Internally you should have thought about classes at high level
          • Class Diagram
            • Identify entities & cardinality
            • Identify classes
              • Nouns in the requirement - check if info has to 
              • Visualize
              • draw.io
      • How to approach diff LLD problems
      • Design a Pen
      • Code 

      LLD: Design and code a Pen

      • Design Pen(Entity Design)
        • Overview: Request for overview to understand
          • Kind of system
          • Scope of the system
          • what does system do
        • Gathering Requirements
          • Suggest ideas/features
          • What qualifies as pen. Any thing that can write?
          • Do they have cap or no
          • What attributes to be stored - length, brand, name
            • refillable or now?
            • A refill has ink and nip
            • ink color
            • ball pen will have ball pen ink & gel pen will have gel pen ink
          • Behavior
            • How a pen writes(Behavior design pattern)
            • Many pen can write in same way
            • nib can have diff dimensions
            • fountain pen has ink and tip
        • Clarifying requirement
          • Can multiple entities have same behavior, - Yes
        • use case diagram - not needed for entities
        • Class diagram
          • ways to come up with Class diagram
            • nouns 
            • visualization of system
          • nouns
            • pen, ball pen, gel pen, cap, refill, nib, ball pen ink, gel pen ink

      LLD: Design TicTacToe

      • Entity -> Bird, Pen
      • Games -> Tic Tac Toe
      • Overview
        • Know about system
          • What kind of the system are we thinking about
            • Different entities OR
            • Real time system where multiple people can interact or
            • web based applns with controllers, repository 
        • Don't know about system
          • I have heard about the game but never played. Can you give overview so that I can align my self on correct direction.
      • Requirement gathering (suggest ideas)
        • Do we need leader board(no)
        • undo(yes)
        • bot(yes)
        • Tournament(no)
        • Timer(no)
        • difficulty levels for bots(yes)
        • reply(yes)
      • Clarifying requirement
        • Asking questions on how the features are going to work
        • eg: how will we declare winner, how will we start game
        • Board size?
        • players = dimension -1
        • each player can choose their symbol
        • Every player must have diff symbo
        • How will game start & how will game end
          • Random person can start
          • when 1st person wins OR when only 1 person left
          • When all cells are finished
          • infinite undo is possible
          • how to decide winner
        • https://docs.google.com/document/d/12Skted-939u8FYeco0gwqXtROBLojlzMFHePydp8Ywg/edit?usp=sharing
      • Class diagram
        • interviewer is only concered with classes for entities & design pattern you may use
        • How to approach
          • by visualization(out to in)
          • or nouns
        • Outer most entity
          • Game
            • Board
            • List<Player>
            • List<WinningStrategy>
            • int lastMovedPlayerIndex
            • gameStatus
            • PlayerWinner
            • List<Moves>
          • Board
            • size
            • List<List<Cell>>
          • Cell
            • Player
            • row
            • column
          • Player
            • Name
            • Symbol
            • type
          • BotType
            • Human
            • Bot
          • Bot extends Player
            • difficulty
          • Symbol
            • char
          • Move
            • Cell
          • <<Winning Strategy>>
            • checkVictory()
          • DiagWinningStrategy implements Winning Strategy
          • RowWinningStrategy implements Winning Strategy
          • ColWinningStrategy implements Winning Strategy
          • CornerWinningStrategy implements Winning Strategy
          • <<BotPlayingStrategy>>
          • EasyPlayingStragegy implements BotPlayingStrategy
          • MedPlayingStragegy implements BotPlayingStrategy
          • HardPlayingStragegy implements BotPlayingStrategy
          • Game.Builder
        • How to implement Undo
          •  When it is easy to reverse a move
            • Store list<Moves>
            • When an undo is called, just reverse last Move
          • When reversing a move is complex
            • Maintain list of moves
            • Create a new board
            • Redo all the moves except last one
          • Optimize time complexity by using more space
        • Assignment
          • Design Chess: https://docs.google.com/document/d/1z4xJBqO4IZe67douVb7jZEnzBHdPtU3kcyWMljtfUi8/edit


      Note: Many design problems have a hidden DSA problem. Tic Tac Toe - how to check win in o(1), In Splitwise - graph copy

      • https://github.com/Naman-Bhalla/tictactoeoct2022
      • Package by Layers
        • Client -> 
        • Controller -> 
        • Services ->
        • Repository(Storage/Database/Model) Note: Each entity is a model & all classes are models 
      • Start coding the models
        • Create models package 
        • Create classes, add attributes, Setters & Getters
        • Create constructors to initialize the attributes
      • Focus on how users interact with my appln & code the appln one by one 
      • https://github.com/Naman-Bhalla/ticTacToeJul22
      TicTacToe Optimization and Code Complete
      • https://github.com/Naman-Bhalla/ticTacToeJul22/blob/master/src/main/java/com/scaler/tictactoe/strategies/gamewinningstrategies/OrderOneGameWinningStrategy.java
      • Schema Design
        • less redundancy to reduce anamolies
        • Fast retrival
      • Approach
        • Find entities in the use case(class diagram)
        • Create one table for each class(put only non-association/non-relation attributes)
        • In 1:M relation, put one side id on M side except for Sparce table and space optimization is required
          • Sparce table is table where there are lot of null values 
          • Create a separate table with id-batch_id relation/mapping. This will compromise on time complexity
      • Assignments
        • code tictactoe
        • schema design for NetFlix

      LLD: Design Parking Lot

      • Ask for overview
        • Know about system
        • Don't know about system
        • Kind of system
          • design entities
          • Management system
        • Requirements
          • single floor or multi floor
          • Multiple entry & multiple exits
          • multiple types of vehicle
          • Ticket generated at entry
          • Assigning a spot
          • Payment at exit
          • Diff parking spots for diff types of vehicle. A vehicle can be assigned only for a spot of its type
          • Diff types of payment(cash, online)
          • Details of operator
          • Vehicle details on ticket
        • Clarifying Requirements
          • Qns about working/behavior
          • Spot assignment strategy
            • Random
            • nearest to entry/exit
            • How is bill going to be calculated
              • duration of parking 
              • type of parking
            • Partial payment support
            • There might be different ways to calculate fee in future
            • Payment Algorithm
              • For diff types of vehicles, diff base price/hr
              • For diff types of vehicles, diff multiplier
            • For Electric vehicles, bills + charging electricity used
        • Use Case diagram
          • Operator -> generate ticket(includes assign spot), generate bill(includes calculate fee), pay(cash)
          • User -> pay(online)
        • Class Diagram
          • Visualization & nouns
          • Name of classes & interfaces
            • ParkingLot
              • Id
              • Address
              • List<ParkingFloor>
              • List<Gate>
              • Map<VehicleType, Price> price
              • Map<VehicleType, double> multiplier
            • ParkingFloor
              • id
              • FloorNumber
              • List<ParkingSpot>
            • ParkingSpot
              • Id
              • VehicleType
              • SpotNumber
              • Status(Available, UnAvailable, Occupied)
            • ElectricParkingSpotEVCharge extends ParkingSpot
              • Meter
            • Meter
              • Id
              • int consumption
            • Operator
              • Id
              • Name
            • Vehicle
              • Id
              • VehicleNumber
              • VehicleType
            • Ticket
              • Id
              • DateTime
              • Operator
              • Spot
              • Vehicle
              • Gate
              • Status
            • Bill
              • Id
              • Ticket
              • exitTime
              • Amount
              • Operator
              • Gate
              • List<Payment>
              • status
            • Payment
              • Id
              • Mode
              • referenceId
              • amount
              • status
          • Interfaces
            • SlotAssignmentStrategy
            • BillCalculationStrategy
      • Code
        • https://github.dev/Naman-Bhalla/parkingLotMay22/blob/master/src/com/scaler/parkinglot/models/

      LLD: code Parking Lot

      • Create class with BaseModel to represent common attributes of the entities
      • All attributes must be private other than getters/setters
      • Archived session - code walk thru
      • Schema Design
        • ParkingLots
          • id, address, 
        • ParkingFloors
          • id, floorNum, lotId
        • ParkingSpots
          • id, spotNumber, floorId, vehicleTypeId, parkingSpotStatusId
        • ElectricParkingSpots
          • id, parkingSpotId
        • Gates
          • id, num, lotId
        • ElectricCharges
          • id, consumption
        • Invoices
          • id, amount
        • Operator
          • id, name
        • Payments
          • id, amount, referenceNum, amount
        • Tickets
          • id, entryName
        • Vehicle
          • id, number, ownerName
        • 2 ways to store Enums
          • Enums as Strings
          • Every Enum gets its own table
        • GatesStatuses
          • id, value
        • GateTypes
          • id, values
        • BillStatus
          • id, value
        • SpotStatus
          • id, value
      LLD: Schema Design Practical: Parking Lot finish
      • Schema design
        • Class/Entity diagram
        • Every entity - one diagram
        • start with primitive data types
        • Represent relationships/associations
          • Find cardinality  
          • Based on cardinality, access pattern, sparsity
      • Scaler design
        • Scaler has students
        • Every student should be able to login
        • scaler has batches
        • one student may be part of multiple batches
        • scaler has multiple modules(DSA, CS, LLD, HLD)
        • Every student will go thru every module of every batch they are part of
        • Every module has exam
        • Every exam has a duration
        • For every module exam has a fixed date
        • One exam can be given only Once for a particular module
        • We have to store marks of every student for every exam they attempted
      • https://drive.google.com/file/d/1rMUhw9xqs2r7--o9TmcfKA4abzpQiX0T/view?usp=sharing
      • Class Diagram for Scaler
        • Batches(id, name, startDate)
        • Modules(id, name)
        • Exam(id, duration, date)
        • Students(id, name, email, password)
        • StudentBatches
        • BatchModule
        • BatchModuleExam 
        • StudentBatchModule
        • StudentBatchModuleExam
      • Schema Design
        • Batches(id, name)
        • Modules(id, name)
        • Exam(id, name, duration)
        • BatchModule(id, start_date)
        • BatchModuleExam(id, time)
        • Students(id, name, email, password)
        • Students-batch(student-id, batch-id)
        • Student-module-batch-exam(id, marks, attempted, result)
      • Netflix schema design
      • Code- https://github.com/Naman-Bhalla/scalerschemadesignnov22

      LLD: Design BookMyShow

      • Overview
        • Implement classes, schema that will be there for most basic features of appln like movie booking appln
        • Same thing can be asked as Restaurant Booking System
      • Features
        • multiple cities & multiple theaters
        • multiple screens
        • screen can have diff set of features
        • each will have multiple seats
        • Seats are of different types
        • Each type of seat will have different price for a show
        • Inside a theater there might be multiple shows running at one time
        • Every show is for a movie at a particular time and particular screen 
        • For a movie, we want to store its name, language, gener, cast, duration
        • Users should be able to search movies
        • Partial payment is allowed
        • only online payments
        • Handling payments is outsourced (razorpay, payu/3rd party payment provider) -> Adapter class to implement?
        • Support for cancellation
        • Do we have to implement Theater aggregator or do we maintain data with us
        • Are shows available for any one to book
      • Class Diagram
        • Visualization vs nouns
        • Visualization (physical systems like theater ..  & user behavior)
          • City(id, name, location)
          • Theaters(id, name, address, list<Screens>)
          • Screen(id, name, List<Seats>, List<Features>)
          • Seat(id, row, column, seatname, type, status)
          • Show(id, screen, movie, start time, end time, list<Features>)
          • SeatTypeShow(id, show, seattype, price)
          • ShowSeat(id, show, seat, status)
      • Assignment
        • Class diagram & schema design for BMS
      • Code
        • https://github.com/Naman-Bhalla/bookMyShowJuly2022/tree/master/src/main/java/com/scaler/bookmyshow/models

      LLD: Code BookMyShow

      • Class design
        • Movie(id, name, List<Actors>, List<Features>, genre)
        • Actor(id, name)
        • GenreEnum(COMEDY, HORROR)
        • Payment(id, amount, mode, ticket, transaction number, time, status)
        • Method(CreditCard, DebitCard, UPI, Cash)
        • Status(Success, Failures, Processing, Aborted, Refunded)
        • Ticket(id, show, time, List<ShowSeats>, amount, List<Payment>, Status)
      • Schema design
        • City(id, Name)
        • Theaters(id, Name, Address, CityId)
        • Screens(id, Name, TheaterId)
        • Seats(id, row, column, name, ScreenId, SeatTypeId, StatusId)
        • Shows(id, startTime, endTime, movieId, ScreenId)
        • show-features(showid, featureid)
        • Seat-Type-Show(id, price, showId, seattypeid)
        • Show-Seats(id, show_id, seat_id, statusId)
        • Movie(id, name,  )
        • Actor(id, name)
        • Movie-actior(movieId, actorId)
        • gener(id, value)
        • Payment(id, amount, time, transactionNumber)
        • Ticker(id, time, amount)

      LLD: Finish BookMyShow

      • DB isolation levels(how one transaction behaves in presence of other transactions)
        • Read uncommitted
        • Read committed
        • Repeatable read
        • Serializable(book my show & banks use it)


      LLD: Machine Coding: Splitwise -1


      LLD: Machine Coding: Splitwise -2


      Comments

      Post a Comment

      Popular posts from this blog

      System Design

      Load balancer Does only routing and no computing. Hence, it can handle higher traffic.  To avoid single point of failure, have a standby routing server. Standby comes into picture only when main server goes down. Assign the same static IP to passive Standby server. Modern systems can route 1M requests per sec Managing large datasets Vertical scaling - Increasing capacity of server Functional Scaling -  Split data logically like users, purchasing..  Microservices share data to other apis Implemented at Application layer Horizontal scaling Also called as Sharding Split and store single logical database over multiple servers called data nodes Can be implemented at Application layer or DB layer Consistent Hashing Distribution scheme that doesn’t directly depend on number of servers, so that, the number of keys to be redistributed is minimised. Consistent Hashing ring Say 2 hash functions Hs & Hc Hs - Marks servers on consistent hashing ring Hc is used to mark partition ke...
      Read more

      CS Fundamentals

       Operating Systems - 1 Resource Manager API for apps developers(It gives set of methods(system calls) that can be made by applications to get work done from the resources   UniProgramming :  Only one program can run at a time - ATM Embedded systems Multi Programming More than one program at a time Multi-tasking systems is same as multi program systems Unix: MacOS, Linux(programs) Windows: Tasks 2 types of multi program categorization non-preemtive supports mutli-programming but only one program runs at a time you cannot switch to another program until the current one completes Preemptive - where a task can be paused/stopped in the middle of execution CPU vs GPU CPU is one intelligent person with speed in GHz GPU is 100 not so intelligent persons with speed 600 MHz Program - set of instructions to run. It is stored on disk Process - Program that is running. It is stored on RAM and run by CPU Process Control Block (PCB) Info about all the process running id resources used(m...
      Read more