Flipkart Interview Preparation and Recruitment Process

To reverse a linked list, use an iterative or recursive approach.
Iterative Method:

• Initialize three pointers: prev (null), current (head), and next (null).

• Traverse the list, updating next to current.next, then reverse the link by setting current.next to prev.

• Move prev and current forward. Repeat until current is null. The new head is prev.
  Time Complexity: O(n), Space: O(1).
  Recursive Method:

• Base case: If the node is null or the last node, return it as the new head.

• Recursively reverse the rest. Set current.next.next to current, and current.next to null.
  Time Complexity: O(n), Space: O(n) (stack).

Use the two-pointer (Tortoise and Hare) approach:

• Initialize slow and fast pointers at the head.

• Move slow by 1 node and fast by 2 nodes in each iteration.

• When fast reaches the end, slow points to the middle.
  Edge Cases:

• Even nodes: Return the first or second middle based on requirements.
  Time Complexity: O(n), Space: O(1).
  Example: In 1 -> 2 -> 3 -> 4 -> 5, slow stops at 3.

Use two stacks (s1 and s2):
Enqueue: Push elements to s1. Time: O(1).
Dequeue:

• If s2 is empty, transfer all elements from s1 to s2 (reversing order).

• Pop from s2. Amortized Time: O(1) per operation.
  Example:

• Enqueue 1, 2, 3: s1 = [1, 2, 3].

• Dequeue: Transfer to s2 = [3, 2, 1], pop 1.
  This approach ensures FIFO order efficiently.

Use a stack to track opening brackets:

• Traverse the string. For (, {, [, push to stack.

• For closing brackets, check if the stack is empty (unbalanced) or if the top matches.

• After traversal, the stack must be empty.
  Example: {[()]} is balanced. {[}] is not.
  Edge Cases:

• Empty string: Balanced.

• Extra closing brackets: Unbalanced.
  Time: O(n), Space: O(n).

Use expand around center approach:

• For each character, expand left and right to find the longest odd-length palindrome.

• Repeat for even-length (centered between two characters).

• Track the maximum length and its start index.
  Example: For "babad", the longest is "aba" or "bab".
  Time: O(n²), Space: O(1).
  Alternative: Dynamic Programming (table for substring validity) but uses O(n²) space.

Components:

• Short URL Generation: Use hash functions (e.g., MD5) or Base62 encoding of a unique ID.

• Database: Store mappings (shortURL, longURL, expiry).

• Redirection: HTTP 301/302 redirects.
  Optimizations:

• Caching: Use Redis for frequent requests.

• Scalability: Database sharding, load balancers.

• Collision Handling: Retry on hash collision.
  Example: TinyURL uses Base62 encoding for 7-character short URLs.

Key Services:

• User Service: Authentication, profiles.

• Product Service: Catalog, search (Elasticsearch).

• Order Service: Transactions, inventory updates.

• Payment Gateway Integration: Idempotent API for payments.
  Scalability:

• Microservices: Isolate failures.

• Database: Sharding (by user/product), read replicas.

• Caching: Redis for product details.

• Async Processing: Queues (Kafka) for order processing.
  High Traffic: CDN for images, auto-scaling, rate limiting.

Indexes (e.g., B+ trees) speed up queries by reducing disk I/O.
Clustered Index: Determines data storage order (e.g., primary key).
Non-Clustered Index: Separate structure with pointers to data.
Trade-offs:

• Faster reads vs slower writes (index updates).

• Use for columns in WHERE, JOIN, ORDER BY.
  Example: Index on users.email speeds up login queries.

• Atomicity: Transactions are all-or-nothing.

• Consistency: Valid state transitions (e.g., no negative balance).

• Isolation: Concurrent transactions don’t interfere (via locks/MVCC).

• Durability: Committed data survives crashes.
  Example: Bank transfers require ACID to prevent errors.

Deadlock: Processes hold resources and wait cyclically.
Conditions: Mutual exclusion, hold and wait, no preemption, circular wait.
Prevention:

• Resource ordering: Acquire resources in fixed order.

• Timeouts: Release resources after a period.

• Deadlock detection: Periodically check for cycles.

• Stateless: No client context stored.

• HTTP Methods: GET (read), POST (create), PUT (update), DELETE.

• Status Codes: 200 (OK), 201 (Created), 404 (Not Found).
  Best Practices: Versioning (/api/v1), HATEOAS, pagination.

• Horizontal Scaling: Add more servers.

• Caching: CDN for static content, Redis for DB queries.

• Database: Read replicas, sharding.

• Async: Queues for non-critical tasks (e.g., emails).

Algorithms:

• Round Robin: Distribute requests sequentially.

• Least Connections: Send to least busy server.
  Tools: AWS ALB, NGINX.
  Benefits: Redundancy, improved uptime, scalability.

• HTTPS: Encrypt data in transit.

• OAuth2/JWT: Token-based authentication.

• Rate Limiting: Prevent abuse.

• Input Validation: Sanitize user inputs.