SDE - 1

Step 1: Brute Force Approach
I initially thought of generating all possible subarrays using two nested loops.
For each subarray, I calculated the sum and checked if it equals the target.
Time Complexity: O(N²)
This works but is inefficient for large inputs.
Step 2: Optimization Using Prefix Sum + HashMap (for positive & negative numbers)
I used the concept of cumulative (prefix) sum.
While iterating through the array:
Maintain a running sum.
If currentSum == target, subarray exists from index 0 to current index.
If (currentSum - target) exists in a HashMap, it means a subarray with sum = target exists.
Store prefix sums in the HashMap with their indices.
Time Complexity: O(N)
Space Complexity: O(N)
Step 3: Special Case Optimization (Only Positive Numbers)
If the array contains only positive numbers, I used the Sliding Window (Two Pointer) approach.
Expand window if sum < target.
Shrink window if sum > target.
Time Complexity: O(N)
Space Complexity: O(1)
The interviewer was satisfied when I moved from brute force to an optimized O(N) solution and explained when to use each approach.

Tip 1: Singleton Pattern and How to Implement It
The Singleton pattern ensures that a class has only one instance and provides a global access point to it.
Key Points:
Private constructor
Static instance variable
Public static method to return the instance
Thread-safe implementation (Double-Checked Locking or Enum-based Singleton in Java)
I explained lazy initialization and how to make it thread-safe using synchronized or volatile.

Tip 2: SOLID Principles:
S – Single Responsibility Principle
O – Open/Closed Principle
L – Liskov Substitution Principle
I – Interface Segregation Principle
D – Dependency Inversion Principle
I gave practical examples from real-world service classes and explained how following SOLID improves maintainability and scalability.
Decorator Design Pattern:
Used to add new functionality to an object dynamically without modifying existing code.
Follows Open/Closed Principle.
I explained it using an example like adding features to a coffee order or adding logging/security layers to a service

Tip 3: I designed a high-level database schema including:
Main Tables:
Users (user_id, name, email, phone)
Hotels (hotel_id, name, location, rating)
Rooms (room_id, hotel_id, type, price, availability)
Bookings (booking_id, user_id, room_id, check_in, check_out, status)
Payments (payment_id, booking_id, amount, payment_status)
I also discussed:
Relationships (One-to-Many between Hotel and Rooms)
Indexing on location and dates
Handling concurrency for room availability