Skip to content

8. Database.md

Latest commit

 

History

History
464 lines (361 loc) · 12.5 KB

8. Database.md

File metadata and controls

464 lines (361 loc) · 12.5 KB
Raw

31. Difference Between an Array and a Linked List

Array

  • Fixed Size: Size is predefined.
  • Contiguous Memory: Data stored in consecutive memory locations.
  • Access Time: O(1) for accessing elements.
  • Insertion/Deletion: O(n) as shifting elements is required.

Linked List

  • Dynamic Size: Grows or shrinks dynamically.
  • Non-Contiguous Memory: Nodes are linked using pointers.
  • Access Time: O(n) for accessing elements.
  • Insertion/Deletion: O(1) if pointer is known.

When to Use?

  • Use array for fast access or fixed-size collections.
  • Use linked list for dynamic collections or frequent insertions/deletions.

32. Hash Table

What is a Hash Table?

A data structure that maps keys to values using a hash function.

Collision Handling Techniques

  1. Chaining: Use linked lists to store multiple values at the same index.
  2. Open Addressing: Find the next available slot using techniques like linear probing.

Example: Chaining

class HashTable {
    private LinkedList[] table;

    public HashTable(int size) {
        table = new LinkedList[size];
    }

    void put(int key, String value) {
        int index = key % table.length;
        if (table[index] == null) table[index] = new LinkedList<>();
        table[index].add(new Entry(key, value));
    }
}

class Entry {
    int key;
    String value;

    Entry(int key, String value) {
        this.key = key;
        this.value = value;
    }
}

33. Difference Between a Stack and a Queue

Stack

  • LIFO: Last In, First Out.
  • Operations: push(), pop(), peek().

Queue

  • FIFO: First In, First Out.
  • Operations: enqueue(), dequeue().

Implement a Stack Using an Array

class Stack {
    private int[] stack;
    private int top;

    public Stack(int size) {
        stack = new int[size];
        top = -1;
    }

    void push(int value) {
        if (top == stack.length - 1) return;
        stack[++top] = value;
    }

    int pop() {
        if (top == -1) return -1;
        return stack[top--];
    }

    int peek() {
        return (top == -1) ? -1 : stack[top];
    }
}

34. Trees and Graphs

Trees

  • A hierarchical data structure.
  • Binary Search Tree (BST): A tree where the left subtree has values less than the root, and the right subtree has values greater.

Graphs

  • A collection of nodes (vertices) and edges.
  • DFS: Depth-First Search.
  • BFS: Breadth-First Search.

Implement a Binary Search Tree (BST)

class Node {
    int value;
    Node left, right;

    Node(int value) {
        this.value = value;
        left = right = null;
    }
}

class BST {
    Node root;

    void insert(int value) {
        root = insertRec(root, value);
    }

    private Node insertRec(Node root, int value) {
        if (root == null) return new Node(value);
        if (value < root.value) root.left = insertRec(root.left, value);
        else root.right = insertRec(root.right, value);
        return root;
    }

    void inorder(Node root) {
        if (root != null) {
            inorder(root.left);
            System.out.print(root.value + " ");
            inorder(root.right);
        }
    }
}

DFS Implementation

void dfs(Node root) {
    if (root == null) return;
    System.out.print(root.value + " ");
    dfs(root.left);
    dfs(root.right);
}

BFS Implementation

void bfs(Node root) {
    Queue queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
        Node current = queue.poll();
        System.out.print(current.value + " ");
        if (current.left != null) queue.add(current.left);
        if (current.right != null) queue.add(current.right);
    }
}

35. Difference Between a Heap and a Stack in Memory

Heap

  • Purpose: Stores dynamically allocated objects.
  • Lifespan: Managed by the garbage collector.
  • Access: Slower due to non-contiguous memory and complex management.
  • Examples: Objects, instance variables.

Stack

  • Purpose: Stores method calls and local variables.
  • Lifespan: Automatically deallocated when the method exits.
  • Access: Faster due to LIFO structure.
  • Examples: Primitive types, references to objects.
Aspect Stack Heap
Allocation Static Dynamic
Management Automatically deallocated Managed by garbage collector
Speed Faster Slower
Use Case Method calls, local vars Objects, instance vars

41. Difference Between TCP and UDP

TCP (Transmission Control Protocol)

  • Connection-Oriented: Establishes a connection before data transfer.
  • Reliable: Ensures data delivery and retransmits lost packets.
  • Slower: Due to overhead from error checking and acknowledgment.
  • Use Case: Email (SMTP), File Transfer (FTP), Web Browsing (HTTP/HTTPS).

UDP (User Datagram Protocol)

  • Connectionless: No handshake or connection establishment.
  • Unreliable: No guarantee of data delivery or order.
  • Faster: Minimal overhead.
  • Use Case: Video Streaming, Online Gaming, Voice Calls.

42. OSI Model

What is the OSI Model?

The Open Systems Interconnection (OSI) model standardizes network communication into seven layers.

Layers and Roles

  1. Physical Layer: Transmits raw binary data over physical mediums.
  2. Data Link Layer: Manages error detection/correction and frames.
  3. Network Layer: Handles routing and addressing (IP addresses).
  4. Transport Layer: Ensures reliable data transfer (TCP/UDP).
  5. Session Layer: Manages sessions and connections.
  6. Presentation Layer: Ensures data translation, encryption, and compression.
  7. Application Layer: Provides network services to applications (HTTP, FTP).

43. DNS (Domain Name System)

What is DNS?

DNS translates human-readable domain names (e.g., www.google.com) into IP addresses.

How It Works

  1. Query Initiation: User types a domain in the browser.
  2. Recursive Query: DNS resolver contacts other DNS servers.
  3. Name Resolution: DNS root, TLD, and authoritative name servers work together to return the IP address.
  4. Response: Browser uses the IP to establish a connection with the server.

44. Difference Between HTTP and HTTPS

HTTP (HyperText Transfer Protocol)

  • Insecure: Data is transferred in plain text.
  • No Encryption: Susceptible to interception.
  • Use Case: General information transfer where security is not critical.

HTTPS (HTTP Secure)

  • Secure: Encrypts data using SSL/TLS.
  • Authentication: Ensures server identity with certificates.
  • Use Case: E-commerce, banking, and any sensitive data transfer.

45. What are Firewalls?

What is a Firewall?

A firewall is a security system that monitors and controls incoming and outgoing network traffic based on predefined security rules.

How It Works

  1. Packet Filtering: Inspects packets and allows or blocks based on rules.
  2. Stateful Inspection: Tracks active connections and determines packet validity.
  3. Proxy Firewall: Intercepts traffic and validates requests before forwarding.

Types of Firewalls

  1. Hardware Firewall: Dedicated devices (e.g., routers with built-in firewalls).
  2. Software Firewall: Installed on individual systems (e.g., Windows Firewall).
  3. Cloud Firewall: Protects cloud infrastructure.

Use Case Example

  • Allowing HTTP/HTTPS traffic: Rules to allow only web traffic on ports 80 (HTTP) and 443 (HTTPS).
  • Blocking unauthorized access: Deny all incoming requests except those explicitly allowed.

31. Difference Between an Array and a Linked List

Array

  • Fixed Size: Size is predefined.
  • Contiguous Memory: Data stored in consecutive memory locations.
  • Access Time: O(1) for accessing elements.
  • Insertion/Deletion: O(n) as shifting elements is required.

Linked List

  • Dynamic Size: Grows or shrinks dynamically.
  • Non-Contiguous Memory: Nodes are linked using pointers.
  • Access Time: O(n) for accessing elements.
  • Insertion/Deletion: O(1) if pointer is known.

When to Use?

  • Use array for fast access or fixed-size collections.
  • Use linked list for dynamic collections or frequent insertions/deletions.

32. Hash Table

What is a Hash Table?

A data structure that maps keys to values using a hash function.

Collision Handling Techniques

  1. Chaining: Use linked lists to store multiple values at the same index.
  2. Open Addressing: Find the next available slot using techniques like linear probing.

Example: Chaining

class HashTable {
    private LinkedList[] table;

    public HashTable(int size) {
        table = new LinkedList[size];
    }

    void put(int key, String value) {
        int index = key % table.length;
        if (table[index] == null) table[index] = new LinkedList<>();
        table[index].add(new Entry(key, value));
    }
}

class Entry {
    int key;
    String value;

    Entry(int key, String value) {
        this.key = key;
        this.value = value;
    }
}

33. Difference Between a Stack and a Queue

Stack

  • LIFO: Last In, First Out.
  • Operations: push(), pop(), peek().

Queue

  • FIFO: First In, First Out.
  • Operations: enqueue(), dequeue().

Implement a Stack Using an Array

class Stack {
    private int[] stack;
    private int top;

    public Stack(int size) {
        stack = new int[size];
        top = -1;
    }

    void push(int value) {
        if (top == stack.length - 1) return;
        stack[++top] = value;
    }

    int pop() {
        if (top == -1) return -1;
        return stack[top--];
    }

    int peek() {
        return (top == -1) ? -1 : stack[top];
    }
}

34. Trees and Graphs

Trees

  • A hierarchical data structure.
  • Binary Search Tree (BST): A tree where the left subtree has values less than the root, and the right subtree has values greater.

Graphs

  • A collection of nodes (vertices) and edges.
  • DFS: Depth-First Search.
  • BFS: Breadth-First Search.

Implement a Binary Search Tree (BST)

class Node {
    int value;
    Node left, right;

    Node(int value) {
        this.value = value;
        left = right = null;
    }
}

class BST {
    Node root;

    void insert(int value) {
        root = insertRec(root, value);
    }

    private Node insertRec(Node root, int value) {
        if (root == null) return new Node(value);
        if (value < root.value) root.left = insertRec(root.left, value);
        else root.right = insertRec(root.right, value);
        return root;
    }

    void inorder(Node root) {
        if (root != null) {
            inorder(root.left);
            System.out.print(root.value + " ");
            inorder(root.right);
        }
    }
}

DFS Implementation

void dfs(Node root) {
    if (root == null) return;
    System.out.print(root.value + " ");
    dfs(root.left);
    dfs(root.right);
}

BFS Implementation

void bfs(Node root) {
    Queue queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
        Node current = queue.poll();
        System.out.print(current.value + " ");
        if (current.left != null) queue.add(current.left);
        if (current.right != null) queue.add(current.right);
    }
}

35. Difference Between a Heap and a Stack in Memory

Heap

  • Purpose: Stores dynamically allocated objects.
  • Lifespan: Managed by the garbage collector.
  • Access: Slower due to non-contiguous memory and complex management.
  • Examples: Objects, instance variables.

Stack

  • Purpose: Stores method calls and local variables.
  • Lifespan: Automatically deallocated when the method exits.
  • Access: Faster due to LIFO structure.
  • Examples: Primitive types, references to objects.
Aspect Stack Heap
Allocation Static Dynamic
Management Automatically deallocated Managed by garbage collector
Speed Faster Slower
Use Case Method calls, local vars Objects, instance vars