Friday, January 10, 2025

Understanding SOLID Principles with Easy Examples

The SOLID principles are a set of guidelines in software design that help create robust, maintainable, and scalable applications. In this blog, we'll explore each principle with easy-to-understand examples.


1. Single Responsibility Principle (SRP)

Definition: A class should have only one reason to change, meaning it should have a single responsibility or job.

Summary: We'll see how separating responsibilities between a controller and a service class ensures adherence to SRP.

Example: Controller and Service

Violating SRP:

In the code below, the UserController handles both the HTTP requests and the business logic:

class UserController {
    public String getUserDetails(int userId) {
        // Fetch user details (business logic)
        String user = "User: " + userId;
        return user;
    }
}

Following SRP:

We can separate the responsibilities by delegating the business logic to a UserService:

class UserController {
    private final UserService userService;

    public UserController(UserService userService) {
        this.userService = userService;
    }

    public String getUserDetails(int userId) {
        return userService.fetchUserDetails(userId);
    }
}

class UserService {
    public String fetchUserDetails(int userId) {
        return "User: " + userId;
    }
}

public class Main {
    public static void main(String[] args) {
        UserService userService = new UserService();
        UserController userController = new UserController(userService);
        System.out.println(userController.getUserDetails(1));
    }
}

Now, UserController only handles HTTP requests, and UserService takes care of business logic.


2. Open/Closed Principle (OCP)

Definition: A class should be open for extension but closed for modification.

Summary: We'll demonstrate how to add new payment methods without altering the existing payment processing code.

Example: Payment System

Code:

interface PaymentMethod {
    void pay(double amount);
}

class CreditCardPayment implements PaymentMethod {
    @Override
    public void pay(double amount) {
        System.out.println("Paid $" + amount + " using Credit Card.");
    }
}

class PayPalPayment implements PaymentMethod {
    @Override
    public void pay(double amount) {
        System.out.println("Paid $" + amount + " using PayPal.");
    }
}

class PaymentProcessor {
    private final PaymentMethod paymentMethod;

    public PaymentProcessor(PaymentMethod paymentMethod) {
        this.paymentMethod = paymentMethod;
    }

    public void processPayment(double amount) {
        paymentMethod.pay(amount);
    }
}

// Adding a new payment method without modifying existing code
class BitcoinPayment implements PaymentMethod {
    @Override
    public void pay(double amount) {
        System.out.println("Paid $" + amount + " using Bitcoin.");
    }
}

public class Main {
    public static void main(String[] args) {
        PaymentProcessor creditCardProcessor = new PaymentProcessor(new CreditCardPayment());
        creditCardProcessor.processPayment(100);

        PaymentProcessor paypalProcessor = new PaymentProcessor(new PayPalPayment());
        paypalProcessor.processPayment(200);

        PaymentProcessor bitcoinProcessor = new PaymentProcessor(new BitcoinPayment());
        bitcoinProcessor.processPayment(300);
    }
}

The PaymentProcessor can now handle new payment methods (like BitcoinPayment) by extending the PaymentMethod interface without modifying existing classes.


3. Liskov Substitution Principle (LSP)

Definition: Subtypes must be substitutable for their base types without affecting the program’s correctness.

Summary: We'll use examples from the Java Collection Framework and a storage service hierarchy to illustrate LSP.

Example 1: List and ArrayList

import java.util.List;
import java.util.ArrayList;

public class LspCollectionExample {
    public static void printList(List<String> list) {
        list.add("Item 1");
        list.add("Item 2");
        System.out.println("List contents: " + list);
    }

    public static void main(String[] args) {
        List<String> arrayList = new ArrayList<>(); // Subclass
        printList(arrayList); // Works seamlessly
    }
}

Here, ArrayList can replace List without any issues, adhering to LSP.

Example 2: Storage Services

Code:

class StorageService {
    public void store(String data) {
        System.out.println("Storing data: " + data);
    }
}

class S3Service extends StorageService {
    @Override
    public void store(String data) {
        System.out.println("Storing data in S3: " + data);
    }
}

class MinioService extends StorageService {
    @Override
    public void store(String data) {
        System.out.println("Storing data in Minio: " + data);
    }
}

public class LspStorageExample {
    public static void saveData(StorageService storageService, String data) {
        storageService.store(data);
    }

    public static void main(String[] args) {
        saveData(new S3Service(), "File1.txt"); // Storing data in S3
        saveData(new MinioService(), "File2.txt"); // Storing data in Minio
    }
}

Both S3Service and MinioService extend StorageService and can be used interchangeably without breaking functionality.


4. Interface Segregation Principle (ISP)

Definition: A class should not be forced to implement interfaces it does not use.

Summary: We'll see how splitting a notification interface into smaller ones ensures classes only implement what they need.

Example: Notification Service

Violating ISP:

interface NotificationService {
    void sendEmail(String message);
    void sendSMS(String message);
    void sendPushNotification(String message);
}

class EmailNotification implements NotificationService {
    @Override
    public void sendEmail(String message) {
        System.out.println("Sending email: " + message);
    }

    @Override
    public void sendSMS(String message) {
        // Not needed
    }

    @Override
    public void sendPushNotification(String message) {
        // Not needed
    }
}

Following ISP:

Split the interface into smaller ones:

interface EmailService {
    void sendEmail(String message);
}

interface SMSService {
    void sendSMS(String message);
}

interface PushNotificationService {
    void sendPushNotification(String message);
}

class EmailNotification implements EmailService {
    @Override
    public void sendEmail(String message) {
        System.out.println("Sending email: " + message);
    }
}

public class Main {
    public static void main(String[] args) {
        EmailNotification emailNotification = new EmailNotification();
        emailNotification.sendEmail("Hello World!");
    }
}

Now, EmailNotification only implements what it needs.


5. Dependency Inversion Principle (DIP)

Definition: High-level modules should not depend on low-level modules. Both should depend on abstractions.

Summary: We'll demonstrate how introducing an interface between a controller and a service class ensures flexibility and adherence to DIP.

Example: Controller and Service Interface

Violating DIP:

class UserService {
    public String fetchUserDetails(int userId) {
        return "User: " + userId;
    }
}

class UserController {
    private final UserService userService = new UserService(); // Direct dependency

    public String getUserDetails(int userId) {
        return userService.fetchUserDetails(userId);
    }
}

public class Main {
    public static void main(String[] args) {
        UserController userController = new UserController();
        System.out.println(userController.getUserDetails(1));
    }
}

Following DIP:

Introduce an abstraction (interface):

interface UserService {
    String fetchUserDetails(int userId);
}

class UserServiceImpl implements UserService {
    @Override
    public String fetchUserDetails(int userId) {
        return "User: " + userId;
    }
}

class UserController {
    private final UserService userService;

    public UserController(UserService userService) {
        this.userService = userService;
    }

    public String getUserDetails(int userId) {
        return userService.fetchUserDetails(userId);
    }
}

public class Main {
    public static void main(String[] args) {
        UserService userService = new UserServiceImpl();
        UserController userController = new UserController(userService);
        System.out.println(userController.getUserDetails(1));
    }
}

Now, UserController depends on the UserService interface, allowing flexibility in implementations.


By adhering to these SOLID principles, we can design systems that are easier to maintain, test, and extend while minimizing the risk of introducing bugs when adding new functionality.

Tuesday, January 7, 2025

The Crux of JWT-Based Authentication using Spring Security

In modern web applications, JSON Web Tokens (JWT) are widely used for securing APIs due to their stateless and scalable nature. In this post, we'll explore the core idea behind implementing JWT-based authentication in a Spring Security setup, including configuring public URLs for Actuator and Swagger, and handling unauthorized access with a custom authentication entry point.

Core Idea: How JWT Authentication Works

JWT authentication in Spring Security involves a few key steps:

  1. Extract and Validate the JWT:
    • Parse the incoming request's JWT token (usually from the Authorization header).
    • Verify the token's signature, expiration, and claims.
  2. Retrieve User Details:
    • Extract the username and roles from the token's claims.
  3. Set Security Context:
    • Create an Authentication object with the user's details and granted authorities.
    • Set the Authentication object in the SecurityContextHolder.
  4. Authorize Requests:
    • Spring Security uses the information in the SecurityContextHolder to authorize requests based on roles and permissions.

Key Components

JWT Filter

A custom filter is needed to intercept requests, validate JWTs, and populate the security context.

@Component
public class JwtAuthenticationFilter extends OncePerRequestFilter {

    @Autowired
    private JwtService jwtService;

    @Override
    protected void doFilterInternal(HttpServletRequest request, HttpServletResponse response, FilterChain filterChain)
            throws ServletException, IOException {
        String token = extractToken(request);

        if (token != null && jwtService.validateToken(token)) {
            String username = jwtService.extractUsername(token);
            List<GrantedAuthority> authorities = jwtService.extractRoles(token).stream()
                .map(SimpleGrantedAuthority::new)
                .collect(Collectors.toList());

            Authentication authentication = new UsernamePasswordAuthenticationToken(username, null, authorities);
            SecurityContextHolder.getContext().setAuthentication(authentication);
        }

        filterChain.doFilter(request, response);
    }

    private String extractToken(HttpServletRequest request) {
        String header = request.getHeader("Authorization");
        if (header != null && header.startsWith("Bearer ")) {
            return header.substring(7);
        }
        return null;
    }
}

Security Configuration

The filter must be added before the UsernamePasswordAuthenticationFilter. Additionally, we’ll configure public URLs for Actuator and Swagger, and a custom entry point for handling unauthorized access.

@Configuration
public class SecurityConfig {

    @Bean
    public SecurityFilterChain securityFilterChain(HttpSecurity http, JwtAuthenticationFilter jwtFilter) throws Exception {
        http.csrf().disable()
            .authorizeHttpRequests()
                .antMatchers("/swagger-ui/**", "/v3/api-docs/**", "/actuator/**").permitAll()
                .anyRequest().authenticated()
            .and()
            .exceptionHandling()
                .authenticationEntryPoint(customAuthenticationEntryPoint())
            .and()
            .sessionManagement()
                .sessionCreationPolicy(SessionCreationPolicy.STATELESS)
            .and()
            .addFilterBefore(jwtFilter, UsernamePasswordAuthenticationFilter.class);

        return http.build();
    }

    @Bean
    public AuthenticationEntryPoint customAuthenticationEntryPoint() {
        return (request, response, authException) -> {
            response.setStatus(HttpServletResponse.SC_UNAUTHORIZED);
            response.setContentType("application/json");
            response.getWriter().write("{\\"error\\":\\"Unauthorized\\"}");
        };
    }
}

JWT Service

A utility class for handling JWT-related operations, such as validation and claims extraction.

@Service
public class JwtService {

    private final String secretKey = "your-secret-key";

    public boolean validateToken(String token) {
        try {
            Jwts.parser().setSigningKey(secretKey).parseClaimsJws(token);
            return true;
        } catch (JwtException e) {
            return false;
        }
    }

    public String extractUsername(String token) {
        return Jwts.parser().setSigningKey(secretKey).parseClaimsJws(token).getBody().getSubject();
    }

    public List<String> extractRoles(String token) {
        Claims claims = Jwts.parser().setSigningKey(secretKey).parseClaimsJws(token).getBody();
        return claims.get("roles", List.class);
    }
}

Testing the Setup

  1. JWT Validation:
    • Send a request with a valid JWT in the Authorization header: Authorization: Bearer <your-token>.
    • The application should authenticate the user and allow access based on roles.
  2. Public Endpoints:
    • Access http://localhost:8080/actuator/health or http://localhost:8080/swagger-ui.html without a JWT to verify public access.
  3. Unauthorized Access:
    • Send a request to a secured endpoint without a JWT.
    • You should receive a 401 response with the custom error message: {"error":"Unauthorized"}.

Conclusion

JWT-based authentication in Spring Security provides a clean and scalable way to secure APIs. By setting up a custom filter, configuring public endpoints, and handling unauthorized access gracefully, you can create a robust security mechanism tailored to your application's needs. Let me know your thoughts or if you'd like more details on extending this setup!

Sunday, December 22, 2024

Managing Entity-DTO Conversions Using Static Methods in DTO Classes

In most Spring MVC applications, DTOs (Data Transfer Objects) are used to transfer data between layers, such as from the service to the controller or vice versa. However, a common challenge developers face is where to place the mapping logic for converting entities to DTOs and back.

This leads to several problems:

  1. Scattered Mapping Logic: Entity-to-DTO and DTO-to-Entity conversions are often written inline in controllers or services, making the code repetitive and harder to maintain.
  2. Bloated Service Layers: When services handle mapping, they become overloaded with responsibilities beyond business logic.
  3. Increased Complexity: Using external libraries like MapStruct for simple mapping adds unnecessary complexity for smaller projects.

Wouldn't it be better if we had a clean, reusable, and lightweight solution for these conversions? Static methods in DTOs provide an elegant way to address this issue.


The Solution: Static Methods in DTO Classes

Static methods in DTOs encapsulate the conversion logic directly within the DTO class. This approach has several advantages:

  1. Encapsulation of Mapping Logic: The conversion logic resides where it naturally belongs—within the DTO class.
  2. Reusability: Static methods can be reused across services and controllers, eliminating duplication.
  3. Simplified Code: Services and controllers become focused on their primary responsibilities, improving readability.
  4. Lightweight Approach: No need for additional dependencies or complex configurations.

Addressing the Debate: DTOs and Business Logic

Some argue that DTOs should not contain any business logic as per the classic DTO pattern, which emphasizes DTOs as simple data containers. Let’s address this concern:

  1. Static Methods Are Not Business Logic

    Static methods for entity-DTO conversions are not "business logic." They are structural logic or mapping logic, which deals with transforming data between formats. Business logic, on the other hand, involves applying rules, policies, or calculations specific to the domain.

  2. DTOs Already Handle Data Transformation

    By definition, DTOs are responsible for transferring and transforming data between layers. Static methods align perfectly with this responsibility by providing a clear and consistent way to handle conversions.

  3. Practicality Over Purism

    While strict adherence to the DTO pattern may advocate for no logic, in real-world projects, practicality often outweighs theoretical purity. Encapsulating mapping logic in DTOs simplifies the codebase without violating the separation of concerns.

Opinion:

Using static methods in DTOs is a pragmatic approach that balances maintainability, simplicity, and clarity. As long as the logic within the DTO is limited to data transformation, it aligns well with the DTO's purpose.


Example: Static Methods in DTO with Spring MVC

Let’s consider a user management system with a User entity and a UserDTO. The UserDTO will include static methods for mapping.


Step 1: Create the Entity Class

@Entity
public class User {
    @Id
    @GeneratedValue(strategy = GenerationType.IDENTITY)
    private Long id;
    private String name;
    private String email;

    // Getters and Setters
}


Step 2: Create the DTO Class

public class UserDTO {
    private Long id;
    private String name;
    private String email;

    // Getters and Setters

    // Static method to convert Entity to DTO
    public static UserDTO fromEntity(User user) {
        UserDTO dto = new UserDTO();
        dto.setId(user.getId());
        dto.setName(user.getName());
        dto.setEmail(user.getEmail());
        return dto;
    }

    // Static method to convert DTO to Entity
    public static User toEntity(UserDTO dto) {
        User user = new User();
        user.setId(dto.getId());
        user.setName(dto.getName());
        user.setEmail(dto.getEmail());
        return user;
    }
}


Step 3: Create the Service Class

@Service
public class UserService {
    @Autowired
    private UserRepository userRepository;

    public UserDTO getUserById(Long id) {
        User user = userRepository.findById(id)
                .orElseThrow(() -> new RuntimeException("User not found"));
        return UserDTO.fromEntity(user); // Entity to DTO conversion
    }

    public UserDTO createUser(UserDTO userDTO) {
        User user = UserDTO.toEntity(userDTO); // DTO to Entity conversion
        User savedUser = userRepository.save(user);
        return UserDTO.fromEntity(savedUser);
    }
}


Step 4: Create the Controller Class

@RestController
@RequestMapping("/api/users")
public class UserController {
    @Autowired
    private UserService userService;

    @GetMapping("/{id}")
    public ResponseEntity<UserDTO> getUser(@PathVariable Long id) {
        UserDTO userDTO = userService.getUserById(id);
        return ResponseEntity.ok(userDTO);
    }

    @PostMapping
    public ResponseEntity<UserDTO> createUser(@RequestBody UserDTO userDTO) {
        UserDTO createdUser = userService.createUser(userDTO);
        return ResponseEntity.status(HttpStatus.CREATED).body(createdUser);
    }
}


Benefits of Using Static Methods in DTOs

  • Encapsulation: Conversion logic stays within the DTO, improving cohesion.
  • Reusability: The static methods can be called wherever needed, without duplicating code.
  • Readability: The service and controller layers remain clean and focused on their core responsibilities.

When to Avoid Static Methods in DTO

Static methods are not always ideal. Avoid them in these scenarios:

  1. Complex Mapping Logic: For complex conversions involving multiple dependencies, use a dedicated mapper or service class.
  2. Dependency Injection: If mapping requires access to Spring-managed beans (e.g., services or repositories), static methods won't work.

Conclusion

Static methods in DTOs are a practical solution for entity-DTO mapping in Spring MVC applications. They strike a balance between simplicity and maintainability, making your code cleaner and more reusable. While some purists argue against any logic in DTOs, static mapping methods are well within the scope of their intended purpose—data transformation. Use this approach judiciously, and enjoy cleaner, more efficient code.

Wednesday, December 11, 2024

Calling 3rd Party APIs using RestTemplate - Have you handled all exceptions? Are you sure?

Let’s demonstrate the use of RestTemplate to call a third-party API with JWT Bearer authentication. This implementation includes detailed error handling for various HTTP status codes, connection issues, serialization errors, and more. All errors are logged appropriately, and meaningful error responses are returned to the API caller.

Overview

  1. Adding JWT Bearer Token: The implementation includes adding a JWT Bearer token to the request headers.
  2. Comprehensive Error Handling: Specific handling for different 4xx and 5xx HTTP status codes, connection issues, and serialization errors.
  3. Logging: All errors and important steps are logged using SLF4J.
  4. Error Response: Custom error responses are sent back to the API caller indicating why the external API call failed.

Dependencies

Ensure you have the following dependencies in your pom.xml:

<dependencies>
    <!-- Spring Web -->
    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-web</artifactId>
    </dependency>

    <!-- SLF4J for Logging -->
    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-logging</artifactId>
    </dependency>

    <!-- Jackson for JSON Processing -->
    <dependency>
        <groupId>com.fasterxml.jackson.core</groupId>
        <artifactId>jackson-databind</artifactId>
    </dependency>

    <!-- Optional: For Circuit Breaker (Resilience4j) -->
    <dependency>
        <groupId>io.github.resilience4j</groupId>
        <artifactId>resilience4j-spring-boot2</artifactId>
        <version>1.7.1</version>
    </dependency>
</dependencies>

Implementation

1. Custom Error Response Class

Create a class to represent the error response structure sent back to the API caller.

// src/main/java/com/example/demo/response/ErrorResponse.java
package com.example.demo.response;

public class ErrorResponse {
    private String error;
    private String message;
    private int status;

    public ErrorResponse() {}

    public ErrorResponse(String error, String message, int status) {
        this.error = error;
        this.message = message;
        this.status = status;
    }

    // Getters and Setters

    public String getError() {
        return error;
    }

    public void setError(String error) {
        this.error = error;
    }

    public String getMessage() {
        return message;
    }

    public void setMessage(String message) {
        this.message = message;
    }

    public int getStatus() {
        return status;
    }

    public void setStatus(int status) {
        this.status = status;
    }
}

2. Service Class with RestTemplate Call

Implement the service class that makes the external API call with comprehensive error handling.

// src/main/java/com/example/demo/service/ExternalApiService.java
package com.example.demo.service;

import com.example.demo.response.ErrorResponse;
import com.fasterxml.jackson.core.JsonProcessingException;
import com.fasterxml.jackson.databind.ObjectMapper;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import org.springframework.http.*;
import org.springframework.stereotype.Service;
import org.springframework.web.client.*;

@Service
public class ExternalApiService {

    private static final Logger logger = LoggerFactory.getLogger(ExternalApiService.class);
    private final RestTemplate restTemplate;
    private final ObjectMapper objectMapper;

    public ExternalApiService(RestTemplate restTemplate, ObjectMapper objectMapper) {
        this.restTemplate = restTemplate;
        this.objectMapper = objectMapper;
    }

    public ResponseEntity<?> callThirdPartyApi(String endpoint, String jwtToken, Object requestPayload) {
        String apiUrl = "<https://api.thirdparty.com/>" + endpoint; // Replace with actual API URL

        // Set up headers with JWT Bearer token
        HttpHeaders headers = new HttpHeaders();
        headers.setContentType(MediaType.APPLICATION_JSON);
        headers.setBearerAuth(jwtToken);

        HttpEntity<Object> entity = new HttpEntity<>(requestPayload, headers);

        try {
            logger.info("Initiating {} request to {}",
                        requestPayload == null ? "GET" : "POST", apiUrl);

            ResponseEntity<String> response;

            if (requestPayload == null) {
                // GET request
                response = restTemplate.exchange(apiUrl, HttpMethod.GET, entity, String.class);
            } else {
                // POST request
                response = restTemplate.exchange(apiUrl, HttpMethod.POST, entity, String.class);
            }

            logger.info("Received successful response from external API. Status Code: {}", response.getStatusCode());

            // Optionally, deserialize response to a specific class
            // Example:
            // MyResponse myResponse = objectMapper.readValue(response.getBody(), MyResponse.class);
            // return ResponseEntity.ok(myResponse);

            return ResponseEntity.ok(response.getBody());

        } catch (HttpClientErrorException e) {
            // Handle 4xx errors
            logger.error("Client error while calling external API. Status Code: {}, Response Body: {}",
                         e.getStatusCode(), e.getResponseBodyAsString(), e);
            return createErrorResponse(e.getStatusCode(), e.getResponseBodyAsString());

        } catch (HttpServerErrorException e) {
            // Handle 5xx errors
            logger.error("Server error while calling external API. Status Code: {}, Response Body: {}",
                         e.getStatusCode(), e.getResponseBodyAsString(), e);
            return createErrorResponse(e.getStatusCode(), "External service is unavailable. Please try again later.");

        } catch (ResourceAccessException e) {
            // Handle connection issues (e.g., timeout)
            logger.error("Connection error while calling external API. Message: {}", e.getMessage(), e);
            return ResponseEntity.status(HttpStatus.GATEWAY_TIMEOUT)
                                 .body(new ErrorResponse("Connection Error", "Unable to reach external service.", HttpStatus.GATEWAY_TIMEOUT.value()));

        } catch (RestClientException e) {
            // Handle other RestTemplate errors
            logger.error("RestClientException occurred while calling external API. Message: {}", e.getMessage(), e);
            return ResponseEntity.status(HttpStatus.INTERNAL_SERVER_ERROR)
                                 .body(new ErrorResponse("Internal Error", "An error occurred while processing the request.", HttpStatus.INTERNAL_SERVER_ERROR.value()));

        } catch (JsonProcessingException e) {
            // Handle JSON parsing errors
            logger.error("JSON processing error while handling external API response. Message: {}", e.getMessage(), e);
            return ResponseEntity.status(HttpStatus.BAD_GATEWAY)
                                 .body(new ErrorResponse("Parsing Error", "Failed to parse external service response.", HttpStatus.BAD_GATEWAY.value()));

        } catch (Exception e) {
            // Catch any other unexpected errors
            logger.error("Unexpected error while calling external API. Message: {}", e.getMessage(), e);
            return ResponseEntity.status(HttpStatus.INTERNAL_SERVER_ERROR)
                                 .body(new ErrorResponse("Unexpected Error", "An unexpected error occurred.", HttpStatus.INTERNAL_SERVER_ERROR.value()));
        }
    }

    private ResponseEntity<ErrorResponse> createErrorResponse(HttpStatus status, String message) {
        ErrorResponse errorResponse = new ErrorResponse(status.getReasonPhrase(), message, status.value());
        return new ResponseEntity<>(errorResponse, status);
    }
}

3. Controller to Expose the API Endpoint

Create a controller that uses the ExternalApiService to handle incoming API requests and respond accordingly.

// src/main/java/com/example/demo/controller/ApiController.java
package com.example.demo.controller;

import com.example.demo.service.ExternalApiService;
import com.example.demo.response.ErrorResponse;

import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.http.*;
import org.springframework.web.bind.annotation.*;

@RestController
@RequestMapping("/api")
public class ApiController {

    @Autowired
    private ExternalApiService externalApiService;

    /**
     * Example endpoint to get data from a third-party service.
     * Replace 'get-data' and requestPayload as needed.
     */
    @GetMapping("/get-data")
    public ResponseEntity<?> getData(@RequestParam String param, @RequestHeader("Authorization") String authHeader) {
        String jwtToken = extractJwtToken(authHeader);
        return externalApiService.callThirdPartyApi("get-data?param=" + param, jwtToken, null);
    }

    /**
     * Example endpoint to post data to a third-party service.
     * Replace 'post-data' and requestPayload as needed.
     */
    @PostMapping("/post-data")
    public ResponseEntity<?> postData(@RequestBody Object requestPayload, @RequestHeader("Authorization") String authHeader) {
        String jwtToken = extractJwtToken(authHeader);
        return externalApiService.callThirdPartyApi("post-data", jwtToken, requestPayload);
    }

    private String extractJwtToken(String authHeader) {
        if (authHeader != null && authHeader.startsWith("Bearer ")) {
            return authHeader.substring(7);
        }
        throw new IllegalArgumentException("Invalid Authorization header.");
    }
}

4. Global Exception Handler (Optional but Recommended)

To handle any exceptions not caught within the service layer, you can use @ControllerAdvice for centralized exception handling.

// src/main/java/com/example/demo/exception/GlobalExceptionHandler.java
package com.example.demo.exception;

import com.example.demo.response.ErrorResponse;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import org.springframework.http.*;
import org.springframework.web.bind.annotation.*;

@ControllerAdvice
public class GlobalExceptionHandler {

    private static final Logger logger = LoggerFactory.getLogger(GlobalExceptionHandler.class);

    @ExceptionHandler(IllegalArgumentException.class)
    public ResponseEntity<ErrorResponse> handleIllegalArgs(IllegalArgumentException ex) {
        logger.error("IllegalArgumentException: {}", ex.getMessage(), ex);
        ErrorResponse error = new ErrorResponse("Bad Request", ex.getMessage(), HttpStatus.BAD_REQUEST.value());
        return new ResponseEntity<>(error, HttpStatus.BAD_REQUEST);
    }

    // Add more exception handlers as needed

    @ExceptionHandler(Exception.class)
    public ResponseEntity<ErrorResponse> handleAllExceptions(Exception ex) {
        logger.error("Unhandled exception: {}", ex.getMessage(), ex);
        ErrorResponse error = new ErrorResponse("Internal Server Error", "An unexpected error occurred.", HttpStatus.INTERNAL_SERVER_ERROR.value());
        return new ResponseEntity<>(error, HttpStatus.INTERNAL_SERVER_ERROR);
    }
}

5. Configuration for RestTemplate (Optional: Timeout Settings)

Configure RestTemplate with timeout settings to handle scenarios where the external API is slow to respond.

// src/main/java/com/example/demo/config/RestTemplateConfig.java
package com.example.demo.config;

import org.springframework.context.annotation.*;
import org.springframework.http.client.*;
import org.springframework.web.client.RestTemplate;

import java.time.Duration;

@Configuration
public class RestTemplateConfig {

    @Bean
    public RestTemplate restTemplate() {
        // Customize the RestTemplate if needed
        SimpleClientHttpRequestFactory factory = new SimpleClientHttpRequestFactory();
        factory.setConnectTimeout(5000); // 5 seconds
        factory.setReadTimeout(5000); // 5 seconds

        return new RestTemplate(factory);
    }
}

6. Sample Request and Response

a. GET Request Example

  • Endpoint: /api/get-data?param=value
  • Headers:
    • Authorization: Bearer your_jwt_token

b. POST Request Example

  • Endpoint: /api/post-data

  • Headers:

    • Authorization: Bearer your_jwt_token
    • Content-Type: application/json
  • Body:

    {
        "key1": "value1",
        "key2": "value2"
    }
    
    

c. Successful Response

{
    "data": "Successful response from external API"
}

d. Error Response Example (Client Error)

{
    "error": "Bad Request",
    "message": "Invalid parameters provided.",
    "status": 400
}

Detailed Error Handling Implementation

Let's dive deeper into how specific HTTP status codes are handled within the ExternalApiService.

1. Handling 4xx Client Errors

Each 4xx status code indicates a client-side error. Here's how you can handle some common 4xx errors:

  • 400 Bad Request: The request was malformed or invalid.
  • 401 Unauthorized: Authentication failed or missing.
  • 403 Forbidden: The client does not have access rights.
  • 404 Not Found: The requested resource does not exist.
  • 429 Too Many Requests: Rate limiting has been applied.

Implementation:

catch (HttpClientErrorException e) {
    HttpStatus status = e.getStatusCode();
    String responseBody = e.getResponseBodyAsString();

    switch (status) {
        case BAD_REQUEST:
            logger.error("400 Bad Request: {}", responseBody, e);
            return createErrorResponse(status, "Invalid request parameters.");

        case UNAUTHORIZED:
            logger.error("401 Unauthorized: {}", responseBody, e);
            return createErrorResponse(status, "Authentication failed. Please check your credentials.");

        case FORBIDDEN:
            logger.error("403 Forbidden: {}", responseBody, e);
            return createErrorResponse(status, "You do not have permission to access this resource.");

        case NOT_FOUND:
            logger.error("404 Not Found: {}", responseBody, e);
            return createErrorResponse(status, "The requested resource was not found.");

        case TOO_MANY_REQUESTS:
            logger.error("429 Too Many Requests: {}", responseBody, e);
            return createErrorResponse(status, "Rate limit exceeded. Please try again later.");

        default:
            logger.error("{} Error: {}", status.value(), responseBody, e);
            return createErrorResponse(status, "Client error occurred.");
    }
}

2. Handling 5xx Server Errors

Server-side errors indicate issues with the external API.

  • 500 Internal Server Error: Generic server error.
  • 502 Bad Gateway: Invalid response from the upstream server.
  • 503 Service Unavailable: The server is not ready to handle the request.
  • 504 Gateway Timeout: The server did not receive a timely response.

Implementation:

catch (HttpServerErrorException e) {
    HttpStatus status = e.getStatusCode();
    String responseBody = e.getResponseBodyAsString();

    switch (status) {
        case INTERNAL_SERVER_ERROR:
            logger.error("500 Internal Server Error: {}", responseBody, e);
            return createErrorResponse(status, "External service encountered an error. Please try again later.");

        case BAD_GATEWAY:
            logger.error("502 Bad Gateway: {}", responseBody, e);
            return createErrorResponse(status, "Received invalid response from external service.");

        case SERVICE_UNAVAILABLE:
            logger.error("503 Service Unavailable: {}", responseBody, e);
            return createErrorResponse(status, "External service is currently unavailable. Please try again later.");

        case GATEWAY_TIMEOUT:
            logger.error("504 Gateway Timeout: {}", responseBody, e);
            return createErrorResponse(status, "External service timed out. Please try again later.");

        default:
            logger.error("{} Server Error: {}", status.value(), responseBody, e);
            return createErrorResponse(status, "Server error occurred.");
    }
}

3. Handling Connection Issues and Timeouts

ResourceAccessException is thrown when there are connection issues, such as timeouts or DNS failures.

Implementation:

catch (ResourceAccessException e) {
    logger.error("Connection error while calling external API. Message: {}", e.getMessage(), e);
    return ResponseEntity.status(HttpStatus.GATEWAY_TIMEOUT)
                         .body(new ErrorResponse("Connection Error", "Unable to reach external service.", HttpStatus.GATEWAY_TIMEOUT.value()));
}

4. Handling JSON Serialization/Deserialization Errors

If you expect a specific response structure, deserialize the JSON response into a Java object. Handle any JsonProcessingException that may occur during this process.

Implementation:

try {
    // Assuming you have a ResponseClass to map the response
    ResponseClass responseObj = objectMapper.readValue(response.getBody(), ResponseClass.class);
    return ResponseEntity.ok(responseObj);
} catch (JsonProcessingException e) {
    logger.error("JSON parsing error while handling external API response. Message: {}", e.getMessage(), e);
    return ResponseEntity.status(HttpStatus.BAD_GATEWAY)
                         .body(new ErrorResponse("Parsing Error", "Failed to parse external service response.", HttpStatus.BAD_GATEWAY.value()));
}

Best Practices Implemented

  1. JWT Bearer Token Management: Tokens are extracted from the Authorization header and added to the external API request headers securely.
  2. Specific Error Handling: Different 4xx and 5xx errors are handled explicitly, providing clear and actionable error messages.
  3. Logging: All errors and significant steps are logged with appropriate severity levels (info, error).
  4. Fallback Responses: In case of errors, meaningful fallback responses are returned to the API caller without exposing internal details.
  5. Configuration Management: Timeout settings are configured to prevent the application from hanging indefinitely.
  6. Centralized Exception Handling: A @ControllerAdvice is used to handle exceptions that may occur outside the service layer, ensuring consistency.

Testing the Implementation

To test the implementation, you can use tools like Postman or cURL to make requests to your API endpoints.

Example cURL Commands:

  1. GET Request
curl -X GET "<http://localhost:8080/api/get-data?param=value>" \\\\
     -H "Authorization: Bearer your_jwt_token"

  1. POST Request
curl -X POST "<http://localhost:8080/api/post-data>" \\\\
     -H "Authorization: Bearer your_jwt_token" \\\\
     -H "Content-Type: application/json" \\\\
     -d '{"key1": "value1", "key2": "value2"}'

Conclusion

This implementation ensures that all possible errors during external API calls are handled gracefully. It provides detailed logging for troubleshooting and returns clear, structured error responses to the API consumers. Additionally, by incorporating JWT Bearer authentication, it secures the external API requests. You can further enhance this setup by integrating circuit breakers, retries, and more advanced resilience patterns as needed.

Understanding Lost Updates in Spring’s @Transactional and How to Avoid Them: A Hotel Booking System Example

In modern web applications, transactions play a crucial role in ensuring data consistency and integrity, especially when there is concurrent access to the same data. For example, a booking system where users can book hotel rooms, flights, or events can experience problems like lost updates if proper transaction management is not implemented correctly. This can result in inaccurate data, leading to a poor user experience and potential revenue loss.

In this blog post, we will explore the issue of lost updates, how Spring’s default @Transactional behavior can lead to this problem, and how you can solve it using best practices to prevent data inconsistencies, especially in scenarios where bulk updates are involved.

The Problem: Lost Updates in a Booking System

Imagine you are working on a hotel booking system. The system allows users to book rooms at a hotel, but each room is available for booking by only one user at a time. Multiple users can view the available rooms, but if two users try to book the same room simultaneously, it can lead to a lost update if the system doesn't handle the concurrency properly.

Let’s take a concrete example: a scenario where an admin wants to update the status of multiple hotel rooms in bulk (e.g., marking them as "booked" after a successful reservation). If two admins or processes try to update the same rooms at the same time, without proper handling, one of the updates might be lost.

Steps:

  1. Admin A starts the process of marking a set of rooms as "booked".
  2. Admin B also starts marking the same set of rooms as "booked" at the same time.
  3. Both Admins read the current status of the rooms (which are available for booking).
  4. Both Admins proceed to mark the rooms as "booked".
  5. One of the updates is lost when Admin B’s changes overwrite Admin A’s changes, resulting in an inaccurate state.

This scenario is a classic case of lost updates, which is dangerous, especially in systems like hotel bookings, where users might unknowingly book a room that was already taken.

Spring’s Default @Transactional Behavior

In Spring, transactions are managed using the @Transactional annotation. By default, Spring uses the READ_COMMITTED isolation level, which means that:

  • Transactions only read committed data.
  • It does not prevent concurrent modifications to the same row in the database, which can lead to lost updates if two transactions are trying to modify the same data at the same time.

How Does READ_COMMITTED Affect Concurrency?

With READ_COMMITTED isolation:

  • Dirty reads are prevented, meaning that transactions cannot read uncommitted data.
  • Lost updates can still occur because while the transaction reads the data, there is no mechanism to prevent another transaction from modifying that data before the first one completes.

In our hotel booking example, if two administrators try to mark the same rooms as "booked" at the same time, both will read the same "available" status of the rooms, and both will attempt to mark them as "booked". Since no locking mechanism is in place, one of the updates will be lost when the second update overwrites the first.

Why Spring Defaults to READ_COMMITTED

Spring’s default behavior of using READ_COMMITTED is designed for systems where performance and concurrency are prioritized over strict consistency. This isolation level:

  • Offers good performance by allowing concurrent transactions.
  • Works well for systems where conflicts between transactions are relatively rare.

However, in high-concurrency systems, such as booking systems where users or administrators can act concurrently, this isolation level may not provide the required guarantees to prevent lost updates.

The Risk of Lost Updates in Bulk Updates

Now, let’s go back to the hotel booking example, but focus on the scenario where multiple rooms are updated in bulk. Let’s say we have an admin interface that allows administrators to mark 50 rooms as "booked". If two admins are trying to mark the same rooms as booked simultaneously, a lost update can occur.

Here’s how this can happen:

  1. Admin A starts the bulk update and reads the current status of the rooms (all rooms are "available").
  2. Admin B also starts a bulk update and reads the same rooms, which are also "available" in the database.
  3. Admin A proceeds to mark the rooms as "booked".
  4. Admin B, unaware that Admin A has already updated the status, also marks the rooms as "booked", overwriting Admin A’s updates.

After both admins have completed their actions, the result is that only one admin’s changes are reflected, and the other admin’s updates are lost, leading to inaccurate data in the system.

Solutions to Prevent Lost Updates in a Booking System

1. Use Higher Isolation Levels

One way to prevent lost updates is to increase the isolation level of the transaction. By setting the SERIALIZABLE isolation level, you ensure that the transaction is executed in such a way that it behaves as if the operations are being done sequentially (one at a time), even if they are being processed concurrently.

@Transactional(isolation = Isolation.SERIALIZABLE)
public void bulkUpdateRoomStatuses(List<Room> rooms) {
    // Business logic to mark rooms as booked
}

Pros of SERIALIZABLE:

  • Strong consistency: Guarantees that no two transactions can modify the same room at the same time.
  • No lost updates: Ensures that all updates are isolated and completed one after another.

Cons of SERIALIZABLE:

  • Performance overhead: It locks rows during the transaction, reducing concurrency and potentially leading to deadlocks or longer wait times.
  • Reduced scalability: In a high-traffic system, this can become a bottleneck.

2. Optimistic Locking

Optimistic locking is a less invasive approach that works by adding a version column to the table. Each time a row is updated, the version number is incremented. If the version number changes between the time it was read and the time it is updated, an exception is thrown, indicating a conflict.

@Entity
public class Room {
    @Id
    private Long id;

    @Version
    private Long version; // Version column for optimistic locking

    private String status; // Available or Booked
}

Before updating the room status, the system checks if the version number has changed. If it has, it means another transaction has modified the room status, and the system can throw an exception or retry the update.

Pros of Optimistic Locking:

  • Performance-friendly: It doesn’t involve locking rows in the database, allowing for higher concurrency.
  • Suitable for situations where conflicts are rare.

Cons of Optimistic Locking:

  • If conflicts are frequent, it can lead to many retries, which could frustrate users or admins.
  • The application needs to handle conflict resolution properly when an exception is thrown.

3. Pessimistic Locking

Pessimistic locking locks the rows when they are read, preventing other transactions from modifying the same data until the transaction is complete. This ensures that the data is not updated by another process.

@Lock(LockModeType.PESSIMISTIC_WRITE)
@Query("SELECT r FROM Room r WHERE r.id = :id")
Room findByIdForUpdate(@Param("id") Long id);

Pros of Pessimistic Locking:

  • Ensures strong consistency as it prevents other transactions from modifying the data while it is being processed.
  • Ideal for scenarios where data conflicts are frequent and need to be prevented.

Cons of Pessimistic Locking:

  • Performance cost: It can lead to slower performance due to the locking mechanism.
  • Risk of deadlocks if not handled carefully.
  • Reduced scalability, as it can block other transactions.

Best Practices to Avoid Lost Updates

To avoid lost updates in a booking system or any high-concurrency application, follow these best practices:

  1. Choose the Right Isolation Level:
    • For highly sensitive data like bookings, use SERIALIZABLE isolation to ensure the highest level of data consistency.
    • For lower-stakes data, READ_COMMITTED might be sufficient, but monitor your system for issues.
  2. Use Optimistic Locking:
    • Implement optimistic locking where feasible. It allows for high concurrency while still detecting conflicts when they arise.
    • Ensure your application gracefully handles optimistic lock exceptions by notifying users and possibly allowing them to retry their actions.
  3. Implement Pessimistic Locking Where Necessary:
    • Use pessimistic locking for critical operations where lost updates are unacceptable. However, be mindful of the performance impact and potential deadlocks.
  4. Test for Concurrency Issues:
    • Always test your system under load to simulate high concurrency and identify potential race conditions and conflicts.
    • Use stress testing and load testing to ensure that your solution can handle high traffic while maintaining data integrity.
  5. Handle Conflict Resolution:
    • Provide clear error messages or conflict resolution strategies to the user when a conflict occurs.
    • Consider retry mechanisms in case of optimistic lock failures, or allow users to manually resolve conflicts.

Conclusion

In a booking system, where multiple users or admins may be attempting to update the same data (like hotel room statuses) concurrently, lost updates can be a serious problem. By understanding how Spring’s default transaction management works and the risks involved, you can make informed decisions on how to manage concurrent updates and prevent data inconsistencies.

By carefully selecting the right transaction isolation level, implementing optimistic or pessimistic locking, and following best practices, you can avoid lost updates and ensure data integrity in your system.

Friday, December 6, 2024

Understanding `==` and `.equals()` for Strings in Java: The Role of the String Pool

When working with Strings in Java, understanding the difference between == and .equals() is crucial. These two seemingly similar operators serve distinct purposes, especially in the context of how Java manages strings using the String pool. Let’s dive into their differences and how the String pool plays a role.


== (Reference Equality)

What It Checks:

The == operator checks whether two references point to the same memory location.

Behavior for Strings:

  • Strings created without the new keyword (using literals) are stored in the String pool. If two strings have the same content and are created as literals, they refer to the same object in the pool, making == return true.
  • Strings created using the new keyword reside in the heap and are not pooled. In this case, == returns false, even if the content is the same.

.equals() (Content Equality)

What It Checks:

The .equals() method checks whether two objects have the same content, not whether they occupy the same memory location.

Behavior for Strings:

The String class overrides .equals() to compare the characters in the string. If the sequence of characters is the same, .equals() returns true, regardless of whether the strings are in the pool or heap.


Example: Comparing == and .equals()

String s1 = "hello";
String s2 = "hello"; // Same content, stored in the String pool
String s3 = new String("hello"); // New object in the heap

System.out.println(s1 == s2);    // true (both refer to the same object in the String pool)
System.out.println(s1.equals(s2)); // true (content is the same)

System.out.println(s1 == s3);    // false (different objects: one in pool, one in heap)
System.out.println(s1.equals(s3)); // true (content is the same)


The String Pool: What and Why?

What Is the String Pool?

The String pool is a special memory region in the Java heap where string literals are stored. It is designed to save memory and improve performance by reusing string instances.

How It Works:

  1. When a string literal is created, Java checks the pool for an identical string.
  2. If the string exists in the pool, the reference to the existing string is returned.
  3. If it doesn’t exist, a new string is added to the pool.

Example: Interning Strings

String s4 = new String("hello");
String s5 = s4.intern(); // Adds "hello" to the pool or returns existing reference
System.out.println(s1 == s5); // true (both refer to the pool object)


When to Use == vs .equals()

Use ==:

  • When you want to check if two references point to the same object.
  • This is useful for reference comparisons but can lead to bugs if mistakenly used for content comparison.

Use .equals():

  • When you want to check if two strings have the same content.
  • This is the most common scenario in business logic.

Real-World Example:

if (userInput.equals("yes")) {
    // Logical comparison of content, not memory location
}


Key Takeaway

While == checks reference equality, .equals() focuses on content equality. The String pool is an optimization mechanism that improves performance and memory usage. Always use .equals() for content comparison in your applications to avoid unexpected results.

Tuesday, April 30, 2019

Hackerrank Balanced Brackets Using Stack (Linked List Implementation)

#include <iostream>
/* #include <stack> */
using namespace std;

typedef char intt;

struct stkNode
{
    intt val;
    struct stkNode *nxtNode;
};

struct stkNode *stkHEAD = NULL;

void stkPush(intt newVal);
void stkPop();

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    string s;
    int n;
    cin >> n;

    while (n--)
    {
        stkHEAD = NULL;
        bool fl = 0;
        cin >> s;

        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] == '(' or s[i] == '[' or s[i] == '{')
            {
                stkPush(s[i]);
            }
            else
            {
                if (stkHEAD != NULL)
                {
                    char ch = stkHEAD->val;
                    if ((s[i] == ')' && ch == '(') ||
                            (s[i] == '}' && ch == '{') ||
                            (s[i] == ']' && ch == '['))
                    {
                        stkPop();
                    }
                    else
                    {
                        fl = 1;
                        break;
                    }
                }
                else
                {
                    fl = 1;
                    break;
                }
            }
        }

        if (stkHEAD != NULL)
            fl = 1;

        if (fl == 1)
            cout << "NO\n";
        else
            cout << "YES\n";
    }

    return 0;
}

void stkPush(intt newVal)
{
    struct stkNode *tmp = new stkNode;
    tmp->val = newVal;
    tmp->nxtNode = stkHEAD;

    stkHEAD = tmp;
}

void stkPop()
{
    if (stkHEAD == NULL)
    {
//        cout << "Stack Empty\n";
        return;
    }
    else
    {
        intt ret = stkHEAD->val;
        stkHEAD = stkHEAD->nxtNode;
        return;
    }
}

Wednesday, August 16, 2017

LightOJ 1122 - Digit Count

// Fix a position, put a letter in it. for first idx, try all of the letters, in the same manner for all possible first charcter, try out all possible second character.  Then go to next position try all of the available letters, try putting all of them by a loop inside . continue doing it until you get to the required size of string.

// aarifshuvo   ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define SZ(x) ((int)(x).size())
#define sci(x) scanf("%d", &x)
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define all(x) (x).begin(),(x).end()
#define mem(a,d) memset(a,d,sizeof a)
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

#define MOD 100007

int ar[30];
int dp[12][12];
int n, sz;

int solve(int i, int digit)
{
    if(i==sz+1) return 1;

    if(dp[i][digit]!=-1) return dp[i][digit];

    dp[i][digit] = 0;

    for(int j=1; j<=n; j++)
    {
        if(i==1)
        {
            dp[i][digit] += solve(i+1, ar[j]);
            continue;
        }
        if(abs(digit - ar[j]) <= 2) dp[i][digit] += solve(i+1, ar[j]);
    }
    return dp[i][digit];
}

int main()
{
    int t, cs=0;
    scanf("%d", &t);
    while(t--)
    {
        mem(dp,-1);
        scanf("%d%d", &n, &sz);
        for(int i=1; i<=n; i++) scanf("%d",&ar[i]);
        int res = solve(1,n+1);
        printf("Case %d: %d\n", ++cs, res);
    }
    return 0;
}

Lightoj 1038 - Race to 1 Again

Formualte the recurrance when you have the same state repeating over and over multiple times. move the same states to one side by pokkhantor and formulate a new recurrance relation.
E(n) = 1 + 1/D * Sum( n/di )  i=2 to D  + 1/D * E(n)
Formulate and Solve it to find the recurrance of E(n). Here D is the number of divisors of n;
 
// aarifshuvo   ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define SZ(x) ((int)(x).size())
#define sci(x) scanf("%d", &x)
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define all(x) (x).begin(),(x).end()
#define mem(a,d) memset(a,d,sizeof a)
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

#define MOD 100007

vector<int>divisors[MOD];

void divs()
{
    FOR(i,2,MOD)
    {
        for(int j=i; j<=MOD; j+=i) divisors[j].pb(i);
    }
}

double dp[MOD];
bool vis[MOD];

double solve(int n)
{
    if(n==1) return 0.0;

    if(vis[n]) return dp[n];
    vis[n] = 1;

    dp[n] = 0.0;

    int cnt = SZ(divisors[n])+1;

    REP(i,SZ(divisors[n]))
    {
        dp[n] += solve(n/divisors[n][i]);
    }

    return dp[n] = (cnt + dp[n]) * (double) (1.0/(cnt - 1.0));
}


int main()
{
    divs();

    int t,cs=0,n;
    scanf("%d", &t);
    while(t--)
    {
        mem(vis,0);
        scanf("%d", &n);
        double res = solve(n);
        printf("Case %d: %f\n", ++cs, res);
    }
    return 0;
}

Tuesday, August 15, 2017

CF 839B Journey

//Explanation

After going to each leaf node, calculate xi*pi i.e. len * probability at each level. from a node, multiple branch can be selected so, 1/branches probability needs to be multiplied at each level. so from node 1, we shall get the expected len of travelling to any leaf node after summing at the same level and multiple level also.

// aarifshuvo   ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define SZ(x) ((int)(x).size())
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define all(x) (x).begin(),(x).end()
#define mem(a,d) memset(a,d,sizeof a)
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

#define inf 12345678912

int vis[100007];
int d[100007];
vector<int> adj[100007];

double dfs(int u)
{
    vis[u] = 1;

    double levelsum= 0;
    int adjs = 0;

    REP(i,SZ(adj[u]))
    {
        int v = adj[u][i];
        if(vis[v]==0)
        {
            adjs++;
            d[v] = d[u] + 1;
            levelsum += dfs(v);
        }
    }
    if(adjs==0) return d[u];
    else
        return levelsum *(1.0/adjs) ;
}


int main()
{
    ll u,v,n,e,st;
    cin>>n;

    FOR(i,1,n-1)
    {
        cin>>u>>v;
        adj[u].pb(v);
        adj[v].pb(u);
    }

    double ans = dfs(1);

    printf("%.15f\n", ans);

    return 0;
}

Sunday, June 25, 2017

CSA 34C Max Or SubArray

Unsorted Ideas::

সবচেয়ে শরটেস্ট সাব অ্যাারে টা বের করতে বলেছে, যার মধ্যে আমরা ওই অ্যাারের মোট এলিমেন্ট গুলার মধ্যের সবচেয়ে ম্যাক্সিমাম অর সাম টা পেতে পারি ।

যেহেতু সাব অ্যাারে বের করতে বলছে, সাব সিকুয়েন্স না, তাই আমরা স্টারটিং এন্ড লিনিয়ারলি এক বাড়ায়ে বাড়ায়ে চেক করতে করতে যাব । এন্ড , সাব অ্যারের ফিনিশিং এন্ডটার যেহেতু ম্যাক্সিমাম আর সাম এর লোয়ার বাউন্ড টা আমাদের লাগতেসে তাই আমরা এইখানে যতক্ষন অর সাম, ম্যাক্স এর চাইতে বড় বা সমান থাকবে ততক্ষন hi এর মান এক এক করে কমিয়ে কমিয়ে চেক করে সাব এ্যারের ফিনিশিং এন্ডের লোয়ার বাউন্ড পেতে পারি ।

এখানে কোন অ্যাারের অর সাম একটা নন ডিক্রিজিং থিং... তাই এই প্রোপারটি তে আমরা বাইনারি সার্চ চালায়ে সাব অ্যারের নেক্সট এন্ড টা ফিক্স করে নিতেই পারি ।

আর তার মানে এক পাশ ফিক্স রেখে অন্য পাশ বাইনারি সার্চ করে অপটিমাল সাব অ্যাারে ফিক্স করতে পারি। কিন্তু এখন O(logn) টাইমে  যদি আমরা ওই লিনিয়ার এন্ড আর বাইনারি সার্চ করা পরের এন্ডের অর সাম পেতে চাই , তাহলে আমাদের অবশ্যই সেগমেন্ট ট্রি অথবা স্পারস টেবিল ডেটা স্ট্রাকচার ব্যবহার করতে পারি। তাহলেই হয়ে যাবে। এইতো আর কিছু লাগবে নাহ...। ওকেই ।

Code:



// aarifshuvo   ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define SZ(x) ((int)(x).size())
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define all(x) (x).begin(),(x).end()
#define mem(a,d) memset(a,d,sizeof a)
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

#define inf 12345678912
#define sz 100007

ll ar[sz], tr[sz*3];

void update(int node, int nb, int ne, int id, ll val)
{
    if(nb==ne)
    {
        ar[nb] = val;
        tr[node] = val;
        return;
    }

    int mid = (nb+ne)/2;
    int lft = 2*node;
    int rgt = lft + 1;

    if(id <= mid) update(lft, nb, mid, id, val);
    else if(id > mid) update(rgt, mid+1, ne, id, val);

    tr[node] = tr[lft] | tr[rgt];
}


ll query(int node, int nb, int ne, int i, int j)
{
    if(i>ne or j<nb) return 0;

    if(i<=nb and j>=ne) return tr[node];

    int mid = (nb+ne)/2;
    int lft = 2*node;
    int rgt = lft + 1;

    ll p1 = query(lft, nb, mid, i, j);
    ll p2 = query(rgt, mid+1, ne, i, j);

    return p1 | p2;
}

int main()
{
    ll n,x,y;
    scl(n);

    ll mx = 0;

    FOR(i,1,n)
    {
        scl(ar[i]);
        update(1,1,n,i,ar[i]);

        mx |= ar[i];
    }

    ll res = INT_MAX, ans = 0;

    FOR(i,1,n)
    {
        int lo = i, hi = n;
        while( lo <= hi)
        {
            int mid = (lo + hi)/2;

            if(query(1,1,n,i,mid) >= mx)
            {
                ans = mid;
                hi = mid-1;

                res = min(res, ans-i+1);
            }
            else
            {
                lo = mid + 1;
            }
        }
    }

    printf("%lld\n", res);

    return 0;
}

Codeforces 802AB - Heidi and Libray

Unsorted Ideas::

This is a paging/caching type problem.

Normally we see the online version of this problem, suppose while caching we have a maximum limit of web pages our cache can contain.
When a user submits query for a webpage, server first takes a look at the cache memory. if its there , server crawls the page from the cache. Hence, we dont need to undergo the cost of bringing the page from the server which is 1 chf according to the problem. :v

সেইমভাবে, আমাদের একটা লাইব্রেরি আছে, আরেকটা বুক স্টোর আছে । লাইব্রেরির নির্দিষ্ট ক্যাপাসিটি আছে। এর বেশি নিতে পারে না বই লাইব্রেরী ।
প্রতিদিন বিভিন্ন ইউজার আসবে এবং বিভিন্ন নাম্বার বইটা পড়তে চাইবে। ওই যে একটু আগের ওয়েব পেজ কোয়েরির মত, বই কোয়েরি করবে।
যদি লাইব্রেরি থাকে তাহলে লাইব্রেরিয়ান তোমাকে বইটা দিবে। এতে লাইব্রেরিয়ানের কোন খরচ পড়বে না।
আর যদি আগে থেকে লাইব্রেরি তে না থাকে বইটি, তবে পার্শ্ববর্তী দোকান থেকে বইটি কিনে আনতে হবে। এতে এক ডলার করে খরচ পড়বে।
ইনিশায়ালি লাইব্রেরি খালি থাকবে, কোন বই থাকবে। স্বাভাবিক, ইনিশিয়ালি ক্যাশ এ কোন ওয়েব পেজ ফেচ করে আনা থাকে না।

অরিজিনাল ওয়েব পেজ ক্যাশিং সিস্টেম এ, কোয়েরি থাকে অনলাইন। মানে কেউ জানে না ইউজার তারপর কি কোয়েরি করবে।
বাট নাও, লেট আস সি দ্য, অফলাইন ভারশান অফ দ্য প্রব্লবেম । মানে আমাদের একটা সিকুয়েন্স অফ নাম্বারস i.e. সিকুয়েন্স অফ কোয়েরিস অফলাইন, মানে মানে আগে থেকে দেয়া থাকবে।

তার সাথে ক্যাশের ম্যাক্স সাইজ মানে লাইব্রেরীর ম্যাক্স ধারণ ক্ষমতা দিয়ে দিবে।

আমাদের বলতে হবে, সবচেয়ে ইফশিয়েন্ট ওয়েতে কিভাবে ক্যাশিং করলে আ
মরা সবচেয়ে কম কস্টে সার্ভিস দিতে পারব।


Code ::

// aarifshuvo   ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define SZ(x) ((int)(x).size())
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
using namespace std;

#define inf 123456789
#define sz 400007

ll ar[sz], nx[sz];
map<ll,ll> mp;

int main()
{
    ll n,k;

    scll(n,k);

    REP(i,n)
    {
        scl(ar[i]);
        mp[ ar[i] ] = INT_MAX; 
        //ধরে নিচ্ছি সবগুলা নাম্বারের কোন রিপিটিশান হয় নি , সব INT_MAX দিয়ে আপডেট করছি । 
    }

    REV(i,n) //উলটা দিক থেকে আসছি 
    {
        nx[i] = mp[ ar[i] ]; 
        //শেষ থেকে শুরুতে যাচ্ছি যেহেতু, প্রথম এপিয়ারেন্স এ তাই এর নেক্সটে আর রিপিট
        // হবার কোন পসিবিলিটি নাই , তাই ইনফিনিটি দিয়ে দিচ্ছি। মানে রিপিট নাই পরে আর। 
        
        mp[ ar[i] ] = i;        
        //mp[ar[i]] কে লেটেস্ট এপিয়ারেন্স এর পজিশান অ্যাাসাইন করে দিচ্ছি ,
        // যাতে অ্যাারের আগের দিকে কোথাও এই নাম্বার আবার আসলে এইটা ইউজ করতে পারি।   
    }


        //প্রথমে nx[] নামে একটা অ্যাারে বানাতে হবে, ক্যাশ থেকে আমরা যখন জিনিসপত্র ডিলিট করে দিব,
        //  তখন জানা দরকার , ওই ইন্ডেক্সের রিকোয়েস্টড নাম্বারটি নেক্সট কখন রিপিট করছে 
        // সেই অনুযায়ী, আমরা নেক্সট রিপিটিং টাইম অনুযায়ী , প্রত্যেক ইন্ডেক্সের জন্য
        // নেক্সট রিপিটিং টাইমটা যদি সেট এ রেখে দিই, তাহলে আমরা যখনি ক্যাশ/সেট টা ফিল হয়ে যাবে
        // তখন সবচেয়ে বেশি দূরবর্তী রিপিটিং টাইম ওয়ালা রিকুয়েস্ট টি যেটা সেটের শেষে থাকবে স্বভাবতই,
        // আপাতত সেটি ডিলিট করে দিয়ে, কারেন্ট বই এর জন্য জায়গা করে দিতে পারি লাইব্রেরিতে :p 


    set<ll> st;  //ইনিশিয়ালিজিং দা ক্যাশ, ক্যাশেও কোন রিপিট থাকবে না, সেট ও থাকবে না তাই :V
    ll cnt = 0;

    REP(i,n)
    {
       //৫ ৩ 
       // ১ ২ ১০ ২ ১০   
       // প্রথম ১০ দ্বিতীয়  ১০ , দ্বিতীয় ১০ এ যখন যাব দেখবে যে এটি আগে থেকেই আছে। 
       //তো আমাদের এইটা আর আগেরটা নেক্সট টাইম এইটা আর দরকার নাই। আমাদের দরকার , দ্বিতীয় দশ এর 
       //নেক্সট পজিশান , তাই আগের দশের নেক্সট পজিশান মানে বর্তমান ১০ এর ইন্ডেক্স i কে রিমুভ করছি
       // আমরা ক্যাশ থেকে। পরে আবার নিচে nx[i] ইনসারট করছি কিন্তু । 
     
        if(st.count( i ))
        {
             st.erase( i ); 
             //রিমুভিং দ্য কারেন্ট পজিশান 
        }
        else
        {
            cnt ++ ; 
            //এডিং কস্ট ফর বায়িং দ্য বুক ইচ টাইম, ফ্রম বুক স্টোর টু লাইব্রেরি
        }

        if(SZ(st) == k)           //লাইব্রেরি ফুল হয়ে গ্যাছে , তাই 
        {
            st.erase( --st.end() ); 
            //ডিলিটিং দ্য লেট(দেরী) মোস্ট ওয়ান , রিকুয়েস্ট 
        }

        st.insert( nx[i] ); 
        // ইনসারটিং দ্য নেক্সট রিপিটিং টাইম অফ দ্য কারেন্ট রিকুয়েস্ট  
    }

    printf("%lld\n", cnt);

    return 0;
}


Clean Code :


// aarifshuvo   ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define SZ(x) ((int)(x).size())
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define all(x) (x).begin(),(x).end()
#define mem(a,d) memset(a,d,sizeof a)
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

#define inf 12345678912
#define sz 400007

ll ar[sz], nx[sz];
map<ll,ll> mp;

int main()
{
    ll n,k;

    scll(n,k);

    REP(i,n)
    {
        scl(ar[i]);
        mp[ ar[i] ] = INT_MAX;
    }

    REV(i,n)
    {
        nx[i] = mp[ ar[i] ];
        mp[ ar[i] ] = i;
    }

    set<ll> st;
    ll cnt = 0;

    REP(i,n)
    {
        if(st.count( i ))
        {
             st.erase( i );
        }
        else
        {
            cnt ++ ;
        }

        if(SZ(st) == k)
        {
            st.erase( --st.end() );
        }

        st.insert( nx[i] );
    }

    printf("%lld\n", cnt);

    return 0;
}