Target Software Engineer

Q: Write a function to reverse a singly linked list. Provide both an iterative solution (using O(1) space) and a recursive solution. Analyze the complexity of both.

Functional Requirements: - Input: Head of a singly linked list. - Output: New head of the reversed list. - Constraints: Handle empty list and single-node list. Non-Functional Requirements: - Iterative: O(N) Time, O(1) Space. - Recursive: O(N) Time, O(N) Space (Stack). Key Design Decisions: - Iterative: Use three pointers: - prev : Tracks the previous node (initially null). - curr : Tracks the current node. - nextTemp : Stores the next node before breaking the link. - Recursive: The reverse of a

Overview

This guide features 10 challenging Software Engineer interview questions for Target (L4-L6 levels), covering algorithms, system design (inventory, caching, order processing), scalability, microservices architecture, API design, real-time data pipelines, distributed systems, performance optimization, and retail-specific technical challenges encountered at Target's scale.

1. “Find Number Divisible by sqrt(n) in Range [L, R]” – Stack-Based Solution

Difficulty Level: Medium

Engineering Level: L4 (Senior Software Engineer)

Source: CodingKaro (September 2025 - Backend Engineer L4 Interview, Online Assessment)

Team: Backend/Infrastructure

Interview Round: Online Assessment

Technology Focus: Data Structures (Stack), Range Queries

Question: “Given an array of integers A and multiple queries of the form [L, R], find the first number in the subarray A[L...R] that is divisible by k, where k = sqrt(n) (and n is the size of the array or a given parameter). The solution must be efficient and avoid a brute force O(N) scan per query. The problem hint suggests a stack-based approach.”

Answer Framework

Requirements Clarification

Functional Requirements:
- Input: Array A of size N, integer k (derived from sqrt(n)), list of queries [L, R].
- Output: For each query, return the index or value of the first element in A[L...R] divisible by k. If none exists, return -1.
- Constraints: N up to 10^5, Q up to 10^5.
- Time Complexity: Better than O(N) per query. Target O(1) or O(log N) per query after preprocessing.

Non-Functional Requirements:
- Efficiency: Preprocessing time should be O(N) or O(N log N). Query time should be fast.
- Space: O(N) auxiliary space allowed.

Key Design Decisions:
- Interpretation of “Stack-Based”: The problem likely asks for the “Next Element with Property X” (in this case, divisibility). This is a variation of the Next Greater Element problem, which is classically solved using a Monotonic Stack.
- Alternative Interpretation (Square Root Decomposition): The mention of sqrt(n) often implies Square Root Decomposition (Mo’s Algorithm) for range queries, but since the prompt explicitly specifies “Stack-Based”, we will focus on the Precomputed Next Occurrence method which can be implemented using a stack or a simple backward pass.

Algorithm & Logic

Approach: Precomputed “Next Divisible” Index
To answer queries in O(1), we can precompute the index of the next element divisible by k for every position i.

Preprocessing:
- Create an array next_divisible[N].
- Iterate from right to left (index N-1 to 0).
- Keep track of the last_seen_index of a number divisible by k.
- For each i, next_divisible[i] = last_seen_index.
- If A[i] itself is divisible, next_divisible[i] = i.
- This is a simplification of the “Next Greater Element” stack logic. If the condition was more complex (e.g., “Next Greater AND Divisible”), we would strictly need a Monotonic Stack.

Query Processing:
- For a query [L, R]:
- Check index = next_divisible[L].
- If index != -1 and index <= R, then A[index] is the answer.
- Otherwise, no such number exists in [L, R].

Why Stack?
If the problem was “Find the first element in A[L...R] that is greater than X and divisible by k”, we would use a Monotonic Stack to find the “Next Greater Element” for every i, and then check divisibility. The “Stack-Based” label in the prompt likely refers to this class of “Next Element” problems.

Code

Solution (Java):

import java.util.*;public class DivisibleInRange {    // Precomputed array to store the index of the next divisible element    private int[] nextDivisible;    private int[] arr;    private int k;    public DivisibleInRange(int[] arr, int n) {        this.arr = arr;        // Assuming k = sqrt(n) as per problem description        this.k = (int) Math.sqrt(n);        this.nextDivisible = new int[arr.length];        preprocess();    }    // Preprocessing: O(N)    // Uses a backward pass (conceptually similar to stack-based Next Element)    private void preprocess() {        int lastIndex = -1;        for (int i = arr.length - 1; i >= 0; i--) {            if (arr[i] % k == 0) {                lastIndex = i;            }            nextDivisible[i] = lastIndex;        }    }    // Query: O(1)    public int query(int L, int R) {        if (L < 0 || R >= arr.length || L > R) {            throw new IllegalArgumentException("Invalid Range");        }        int index = nextDivisible[L];        // Check if the found index is within the range [L, R]        if (index != -1 && index <= R) {            return arr[index];        } else {            return -1; // No number divisible by k found in range        }    }    // Alternative: Explicit Stack-Based Approach (For "Next Greater/Divisible" patterns)    // If the problem was "Find next element > X and divisible by K", we would use this:    public void preprocessStack() {        Stack<Integer> stack = new Stack<>();        for (int i = arr.length - 1; i >= 0; i--) {            // Maintain stack property (e.g., increasing order)            // For simple divisibility, stack isn't strictly needed, but this pattern            // is what the "Stack-Based" hint usually refers to.            while (!stack.isEmpty() && arr[stack.peek()] % k != 0) {                stack.pop();            }            nextDivisible[i] = stack.isEmpty() ? -1 : stack.peek();            if (arr[i] % k == 0) stack.push(i);        }    }    public static void main(String[] args) {        int[] data = {10, 3, 5, 7, 9, 25, 8, 4}; // n = 8, k = 2 (sqrt(8) floor)        DivisibleInRange solver = new DivisibleInRange(data, 4); // k=2        // Query [0, 2]: Range {10, 3, 5}. 10 is div by 2. Index 0 <= 2. Return 10.        System.out.println(solver.query(0, 2));
        // Query [1, 3]: Range {3, 5, 7}. Next div by 2 is 8 at index 6. 6 > 3. Return -1.        System.out.println(solver.query(1, 3));
    }}

Complexity Analysis:
- Time Complexity: O(N) for preprocessing, O(1) per query.
- Space Complexity: O(N) for the nextDivisible array.

2. “Minimum Distance String Variation” – Dynamic Programming Solution

Difficulty Level: Medium-Hard

Engineering Level: L4 (Senior Software Engineer)

Source: CodingKaro (September 2025 - Backend Engineer L4, Online Assessment)

Team: Backend/Infrastructure

Interview Round: Online Assessment (Second DSA Question)

Technology Focus: Dynamic Programming, String Algorithms

Question: “Given two strings word1 and word2, find the minimum number of operations required to convert word1 to word2. The allowed operations are Insert, Delete, and Replace a character. The solution should use Dynamic Programming to optimize the process.”

Answer Framework

Requirements Clarification

Functional Requirements:
- Input: Two strings word1 (length M) and word2 (length N).
- Output: Integer representing the minimum edit distance.
- Operations: Insert, Delete, Replace (all cost 1).
- Constraints: M, N <= 500 (typical for O(M*N) DP).

Non-Functional Requirements:
- Time Complexity: O(M * N).
- Space Complexity: O(M * N) or O(min(M, N)) with space optimization.

Key Design Decisions:
- DP State: dp[i][j] represents the minimum edit distance between the first i characters of word1 and the first j characters of word2.
- Transitions:
- If word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1] (No op).
- Else: dp[i][j] = 1 + min(Insert, Delete, Replace).
- Insert: dp[i][j-1]
- Delete: dp[i-1][j]
- Replace: dp[i-1][j-1]

Code

Solution (Java):

public class EditDistance {    public int minDistance(String word1, String word2) {        int m = word1.length();        int n = word2.length();        // dp[i][j] : min operations to convert word1[0..i-1] to word2[0..j-1]        int[][] dp = new int[m + 1][n + 1];        // Base cases        for (int i = 0; i <= m; i++) {            dp[i][0] = i; // Deleting all characters from word1        }        for (int j = 0; j <= n; j++) {            dp[0][j] = j; // Inserting all characters into word1        }        // Fill DP table        for (int i = 1; i <= m; i++) {            for (int j = 1; j <= n; j++) {                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {                    dp[i][j] = dp[i - 1][j - 1]; // Characters match, no new op                } else {                    dp[i][j] = 1 + Math.min(                        dp[i - 1][j - 1],    // Replace                        Math.min(                            dp[i - 1][j],    // Delete                            dp[i][j - 1]     // Insert                        )                    );                }            }        }        return dp[m][n];    }}

Complexity Analysis:
- Time Complexity: O(M * N) where M and N are lengths of the strings.
- Space Complexity: O(M * N) for the DP table. (Can be optimized to O(min(M, N))).

3. “Zig-Zag Traversal in Binary Tree or Matrix”

Difficulty Level: Medium

Engineering Level: L4 (Senior Software Engineer)

Source: CodingKaro (September 2025 - Backend Engineer L4, Technical Interview Round 1)

Team: Backend/Infrastructure

Interview Round: Technical Round 1 (60 minutes)

Technology Focus: Tree Traversal, Level-Order Traversal

Question: “Given the root of a binary tree, return the zigzag level order traversal of its nodes’ values. (i.e., from left to right, then right to left for the next level and alternate between). Alternatively, perform a similar zigzag traversal on a 2D Matrix.”

Answer Framework

Requirements Clarification

Functional Requirements:
- Input: Root node of a binary tree.
- Output: A list of lists of integers, where each inner list represents a level.
- Order: Level 0: Left -> Right, Level 1: Right -> Left, Level 2: Left -> Right, etc.
- Constraints: Number of nodes up to 2000.

Non-Functional Requirements:
- Time Complexity: O(N) where N is the number of nodes.
- Space Complexity: O(N) (or O(W) where W is max width) for the queue.

Key Design Decisions:
- Traversal: Breadth-First Search (BFS) is ideal for level-order traversal.
- Zig-Zag Logic: Use a boolean flag leftToRight that toggles at each level.
- Data Structure: Use a Deque (LinkedList) for the current level’s values. If leftToRight is true, add to the end (addLast). If false, add to the beginning (addFirst). This avoids explicit reversal O(W) cost, though Collections.reverse is also acceptable.

Code

Solution (Java):

import java.util.*;public class ZigZagTraversal {    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {        List<List<Integer>> result = new ArrayList<>();        if (root == null) return result;        Queue<TreeNode> queue = new LinkedList<>();        queue.offer(root);        boolean leftToRight = true;        while (!queue.isEmpty()) {            int levelSize = queue.size();            LinkedList<Integer> currentLevel = new LinkedList<>();            for (int i = 0; i < levelSize; i++) {                TreeNode currentNode = queue.poll();                // Add to current level based on direction                if (leftToRight) {                    currentLevel.addLast(currentNode.val);                } else {                    currentLevel.addFirst(currentNode.val);                }                if (currentNode.left != null) queue.offer(currentNode.left);                if (currentNode.right != null) queue.offer(currentNode.right);            }            result.add(currentLevel);            leftToRight = !leftToRight; // Toggle direction        }        return result;    }    // Definition for a binary tree node.    public static class TreeNode {        int val;        TreeNode left;        TreeNode right;        TreeNode(int val) { this.val = val; }    }}

Complexity Analysis:
- Time Complexity: O(N), as we visit each node once.
- Space Complexity: O(N) (or O(W)) to store the queue and result.

4. “Find Longest Common Prefix in Array of Strings”

Difficulty Level: Easy-Medium

Engineering Level: L3-L4

Source: Taro Interview Platform (March 2024 - Target Engineer Role)

Team: General Engineering

Interview Round: Coding Interview

Technology Focus: String Algorithms, Trie Data Structure

Question: “Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string.”

Answer Framework

Requirements Clarification

Functional Requirements:
- Input: Array of strings strs.
- Output: A string representing the longest common prefix.
- Edge Cases: Empty array, array with empty strings, no common prefix.

Non-Functional Requirements:
- Time Complexity: O(S), where S is the sum of all characters in all strings.
- Space Complexity: O(1) (excluding result storage).

Key Design Decisions:
- Approach:
1. Horizontal Scanning: Take the first string as the initial prefix. Compare it with the second string and update prefix. Repeat for all strings. If prefix becomes empty, stop.
2. Sorting: Sort the array of strings. The longest common prefix must be a prefix of the first and the last string (since sorting groups similar prefixes). This is O(NLlog N).
3. Vertical Scanning: Compare column 0 of all strings, then column 1, etc.
- Selection: Horizontal Scanning is efficient (O(S)) and easy to implement.

Code

Solution (Java - Horizontal Scanning):

public class LongestCommonPrefix {    public String longestCommonPrefix(String[] strs) {        if (strs == null || strs.length == 0) {            return "";        }        // Start with the first string as the prefix        String prefix = strs[0];        for (int i = 1; i < strs.length; i++) {            // While the current string (strs[i]) does not start with the prefix            while (strs[i].indexOf(prefix) != 0) {                // Shorten the prefix from the end                prefix = prefix.substring(0, prefix.length() - 1);                // If prefix becomes empty, there is no common prefix                if (prefix.isEmpty()) {                    return "";                }            }        }        return prefix;    }}

Complexity Analysis:
- Time Complexity: O(S), where S is the sum of all characters in all strings. In the worst case (all strings identical), we compare every character.
- Space Complexity: O(1), as we only modify the prefix in place (or create substrings which is minimal overhead in modern Java).

5. “Dutch Flag Problem: Sort Array of 0s, 1s, and 2s In-Place”

Difficulty Level: Medium

Engineering Level: L3-L4

Source: Taro Interview Platform (March 2024 - Target Engineer Role)

Team: General Engineering

Interview Round: Coding Challenge

Technology Focus: Array Sorting, Two-Pointer Technique

Question: “Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue. We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively. You must solve this problem without using the library’s sort function and in a single pass.”

Answer Framework

Requirements Clarification

Functional Requirements:
- Input: Array nums containing only 0, 1, 2.
- Output: Sorted array in-place.
- Constraints: Single pass (O(N)), Constant space (O(1)).

Non-Functional Requirements:
- Time Complexity: O(N).
- Space Complexity: O(1).

Key Design Decisions:
- Algorithm: The Dutch National Flag Algorithm (by Dijkstra).
- Pointers:
- low: The boundary for 0s (all elements < low are 0).
- mid: The current element being considered.
- high: The boundary for 2s (all elements > high are 2).
- Logic:
- If nums[mid] == 0: Swap nums[mid] and nums[low]. Increment low and mid.
- If nums[mid] == 1: Just increment mid.
- If nums[mid] == 2: Swap nums[mid] and nums[high]. Decrement high. (Do not increment mid because the swapped element from high needs to be checked).

Code

Solution (Java):

public class SortColors {    public void sortColors(int[] nums) {        int low = 0;        int mid = 0;        int high = nums.length - 1;        while (mid <= high) {            if (nums[mid] == 0) {                swap(nums, low, mid);                low++;                mid++;            } else if (nums[mid] == 1) {                mid++;            } else { // nums[mid] == 2                swap(nums, mid, high);                high--;            }        }    }    private void swap(int[] nums, int i, int j) {        int temp = nums[i];        nums[i] = nums[j];        nums[j] = temp;    }}

Complexity Analysis:
- Time Complexity: O(N), as we process each element at most once.
- Space Complexity: O(1), in-place modification.

6. Behavioral & System Design: “Omnichannel Inventory Management and Order Sourcing System”

Difficulty Level: Hard

Engineering Level: L4-L5 (Senior Engineer)

Source: Blind Community (November 2025 - Senior Engineer, Pair Programming Interview)

Team: Order Management / Supply Chain Technology

Interview Round: Pair Programming + System Design Round

Technology Focus: Distributed Systems, System Design, Omnichannel Retail

Question: “Design an Omnichannel Inventory Management and Order Sourcing System. The system must handle real-time inventory updates from thousands of stores and distribution centers. It needs to support customer-facing features like ‘Drive Up’, ‘Order Pickup’, and ‘Same Day Delivery’ (Shipt). Key challenges include ensuring inventory accuracy to prevent cancellations and optimizing order sourcing (deciding which store/DC fulfills an order) to minimize shipping costs and time.”

Answer Framework

Requirements Clarification

Functional Requirements:
- Inventory Visibility: Real-time view of stock at every node (Store/DC).
- Order Sourcing: Algorithm to select the best node to fulfill an order based on distance, stock level, and capacity.
- Reservation: Soft reserve inventory when an order is placed.
- Updates: Handle high-throughput updates from POS (Point of Sale) and Warehouse systems.

Non-Functional Requirements:
- Availability: High availability (99.99%) is critical for sales.
- Consistency: Eventual consistency is acceptable for search, but Strong Consistency (or optimistic locking) required for Reservation.
- Latency: Sourcing decision < 200ms.
- Scale: Millions of items, thousands of nodes, peak traffic (Black Friday).

Key Design Decisions:
- Database: NoSQL (Cassandra/DynamoDB) for Inventory (high write throughput). Relational (PostgreSQL) for Orders (complex state transitions).
- Sourcing Logic: Geohashing to find nearby stores. Cost function to minimize split shipments.
- Concurrency: Distributed Locking (Redis) or Database Versioning for inventory reservation.

System Architecture

High-Level Design:

┌─────────────────────────────────────────────────────────────────┐
│                         CLIENT LAYER                             │
│  [Target App] [Target.com] [Store POS] [Handheld Devices (Zebra)]│
└─────────────────────────────────────────────────────────────────┘
                              │
                              ▼
┌─────────────────────────────────────────────────────────────────┐
│                      API GATEWAY LAYER                           │
│           [Load Balancer] → [API Gateway Cluster]                │
│         Auth (OAuth2) | Rate Limiting | Request Routing         │
└─────────────────────────────────────────────────────────────────┘
                              │
                ┌─────────────┼─────────────┐
                ▼             ▼             ▼
    ┌──────────────┐  ┌──────────────┐  ┌──────────────┐
    │    Order     │  │  Inventory   │  │   Sourcing   │
    │   Service    │  │   Service    │  │    Engine    │
    └──────────────┘  └──────────────┘  └──────────────┘
            │                 │                 │
            └─────────────────┼─────────────────┘
                              ▼
        ┌────────────────────────────────────────────┐
        │         MESSAGE QUEUE (Kafka)              │
        │   Topics: order-created, inventory-update  │
        └────────────────────────────────────────────┘
                              │
            ┌─────────────────┼─────────────────┐
            ▼                 ▼                 ▼
    ┌──────────────┐  ┌──────────────┐  ┌──────────────┐
    │ Reservation  │  │ Fulfillment  │  │   Store      │
    │   Service    │  │   Service    │  │  Ops API     │
    └──────────────┘  └──────────────┘  └──────────────┘
                              │
                              ▼
        ┌────────────────────────────────────────────┐
        │          DATA PERSISTENCE LAYER            │
        │  [Cassandra - Inventory (High Write)]      │
        │  [PostgreSQL - Orders (ACID)]              │
        │  [Redis - Distributed Locks & Cache]       │
        └────────────────────────────────────────────┘

Scalability & Performance:
- Inventory Updates: Use Cassandra for high write throughput (thousands of POS updates/sec). Shard by Store_ID + SKU.
- Sourcing Latency: Cache store inventory snapshots in Redis (Geo-sharded) to allow the Sourcing Engine to make sub-200ms decisions without hitting the DB.
- Concurrency: Use Redis Distributed Locks (Redlock algorithm) in the Reservation Service to prevent overselling during high-concurrency events (e.g., PS5 drops).
- Async Processing: Order fulfillment steps (picking, packing, shipping) are decoupled via Kafka to handle spikes in order volume.

Code (Pair Programming - Sourcing Logic Snippet)

Sourcing Service (Java):

@Servicepublic class SourcingService {    @Autowired    private InventoryClient inventoryClient;    @Autowired    private StoreDistanceService distanceService;    public SourcingResponse sourceOrder(Order order) {        List<Store> candidateStores = distanceService.findStoresNear(order.getCustomerLocation(), 50.0); // 50 miles radius        Store bestStore = null;        double minCost = Double.MAX_VALUE;        for (Store store : candidateStores) {            if (canFulfill(store, order.getItems())) {                double cost = calculateFulfillmentCost(store, order);                if (cost < minCost) {                    minCost = cost;                    bestStore = store;                }            }        }        if (bestStore == null) {            return SourcingResponse.failed("No store found with sufficient inventory");        }        return SourcingResponse.success(bestStore.getId());    }    private boolean canFulfill(Store store, List<OrderItem> items) {        // Batch check inventory        Map<String, Integer> stock = inventoryClient.getStock(store.getId(), items.stream().map(OrderItem::getSku).collect(Collectors.toList()));        for (OrderItem item : items) {            if (stock.getOrDefault(item.getSku(), 0) < item.getQuantity()) {                return false;            }        }        return true;    }    private double calculateFulfillmentCost(Store store, Order order) {        // Simplified cost function: Distance + Handling Cost        double distance = distanceService.getDistance(store.getLocation(), order.getCustomerLocation());        return (distance * 0.5) + store.getBaseHandlingCost();    }}@Servicepublic class ReservationService {    @Autowired    private RedisTemplate<String, String> redisTemplate;    // Distributed Locking for Inventory Reservation    public boolean reserveInventory(String storeId, String sku, int quantity) {        String lockKey = "lock:inventory:" + storeId + ":" + sku;        String inventoryKey = "inventory:" + storeId + ":" + sku;        try {            // Acquire Lock (100ms TTL to prevent deadlocks)            Boolean locked = redisTemplate.opsForValue().setIfAbsent(lockKey, "LOCKED", Duration.ofMillis(100));            if (Boolean.TRUE.equals(locked)) {                int currentStock = Integer.parseInt(redisTemplate.opsForValue().get(inventoryKey));                if (currentStock >= quantity) {                    redisTemplate.opsForValue().decrement(inventoryKey, quantity);                    return true;                }            }            return false;        } finally {            redisTemplate.delete(lockKey);        }    }}

7. Java Spring Boot & Microservices Architecture Questions

Difficulty Level: Medium

Engineering Level: L3-L4

Source: Taro (July 2025 - Target Engineer Role, India)

Team: Backend / Microservices Platform

Interview Round: Round 1 (Screening Round)

Technology Focus: Spring Boot, REST API, Microservices

Question: “A series of technical questions focused on Spring Boot fundamentals, REST API design, and Microservices architecture. Key topics include API signatures, Request/Response handling, Dependency Injection, and communication patterns between microservices.”

Answer Framework

Key Concepts & Sample Answers

1. @RestController vs @Controller:
* @Controller: Used for traditional Spring MVC controllers that return a view (JSP/Thymeleaf).
* @RestController: A convenience annotation that combines @Controller and @ResponseBody. It indicates that the return value of methods should be bound to the web response body (typically JSON).

2. Global Exception Handling:
* Use @ControllerAdvice or @RestControllerAdvice to handle exceptions across the whole application.
* Define methods annotated with @ExceptionHandler to catch specific exceptions and return custom error responses (e.g., 404 Not Found, 400 Bad Request).

3. Dependency Injection (DI) & Inversion of Control (IoC):
* IoC: The principle where the control of object creation and lifecycle is transferred from the programmer to the container (Spring ApplicationContext).
* DI: The design pattern used to implement IoC. Dependencies are “injected” into a class (via Constructor, Setter, or Field) rather than the class creating them itself. Constructor injection is preferred for testability and immutability.

4. Microservices Communication:
* Synchronous: REST (RestTemplate/WebClient) or gRPC. Good for real-time requests but couples services.
* Asynchronous: Message Queues (Kafka/RabbitMQ). Decouples services, better for scalability and resilience.

Code

Example: Clean Spring Boot REST Controller:

@RestController@RequestMapping("/api/v1/products")public class ProductController {    private final ProductService productService;    // Constructor Injection (Best Practice)    public ProductController(ProductService productService) {        this.productService = productService;    }    @GetMapping("/{id}")    public ResponseEntity<ProductResponse> getProduct(@PathVariable String id) {        Product product = productService.getProductById(id);        return ResponseEntity.ok(ProductResponse.from(product));    }    @PostMapping    public ResponseEntity<ProductResponse> createProduct(@Valid @RequestBody ProductRequest request) {        Product created = productService.createProduct(request);        URI location = ServletUriComponentsBuilder
            .fromCurrentRequest()            .path("/{id}")            .buildAndExpand(created.getId())            .toUri();        return ResponseEntity.created(location).body(ProductResponse.from(created));    }    // Global Exception Handler (Snippet)    @ExceptionHandler(ProductNotFoundException.class)    public ResponseEntity<ErrorResponse> handleNotFound(ProductNotFoundException ex) {        return ResponseEntity.status(HttpStatus.NOT_FOUND)            .body(new ErrorResponse("PRODUCT_NOT_FOUND", ex.getMessage()));    }}

8. Fibonacci Series with Dynamic Programming Optimization & Complexity Analysis

Difficulty Level: Easy

Engineering Level: Entry-Level / Fresher

Source: GeeksForGeeks (October 2020 - Campus Hiring, Technical Interview)

Team: General Engineering

Interview Round: Technical Interview (Virtual)

Technology Focus: Recursion, Dynamic Programming, Complexity Analysis

Question: “Implement a function to calculate the Nth Fibonacci number. Start with a recursive solution, then optimize it using Dynamic Programming. Explain the time and space complexity of each approach.”

Answer Framework

Requirements Clarification

Functional Requirements:
- Input: Integer n.
- Output: The n-th Fibonacci number.
- Definition: F(0)=0, F(1)=1, F(n) = F(n-1) + F(n-2).

Non-Functional Requirements:
- Optimization: Must move from exponential to linear time complexity.
- Space: Optimize space if possible.

Key Design Decisions:
- Naive Recursion: Simple but inefficient (O(2^n)).
- Memoization (Top-Down): Caches results of subproblems. O(N) time, O(N) space (recursion stack + map).
- Tabulation (Bottom-Up): Iterative approach. O(N) time, O(N) space.
- Space Optimization: We only need the last two numbers. O(N) time, O(1) space.

Code

Solution (Java - Evolution of Approaches):

public class Fibonacci {    // 1. Naive Recursive (O(2^n)) - DO NOT USE IN PRODUCTION    public int fibRecursive(int n) {        if (n <= 1) return n;        return fibRecursive(n - 1) + fibRecursive(n - 2);    }    // 2. Top-Down DP (Memoization) - O(N) Time, O(N) Space    private Map<Integer, Integer> memo = new HashMap<>();    public int fibMemo(int n) {        if (n <= 1) return n;        if (memo.containsKey(n)) return memo.get(n);        int result = fibMemo(n - 1) + fibMemo(n - 2);        memo.put(n, result);        return result;    }    // 3. Bottom-Up DP (Space Optimized) - O(N) Time, O(1) Space    public int fibOptimized(int n) {        if (n <= 1) return n;        int a = 0; // F(i-2)        int b = 1; // F(i-1)        int c;     // F(i)        for (int i = 2; i <= n; i++) {            c = a + b;            a = b;            b = c;        }        return b;    }}

Complexity Analysis:
- Recursive: Time O(2^N) because each call branches into two. Space O(N) for stack depth.
- DP (Memo/Tabulation): Time O(N) because each subproblem is solved once. Space O(N).
- Optimized: Time O(N). Space O(1) as we only store two variables.

9. “Detect Loop in Linked List” Using Floyd’s Cycle Detection Algorithm

Difficulty Level: Easy-Medium

Engineering Level: Fresher/Entry-Level

Source: GeeksForGeeks (October 2020 - Campus Hiring)

Team: General Engineering

Interview Round: Technical Interview

Technology Focus: Linked List, Two-Pointer Technique

Question: “Given the head of a linked list, determine if the linked list has a cycle in it. Explain the logic behind Floyd’s Cycle Detection Algorithm and analyze its complexity.”

Answer Framework

Requirements Clarification

Functional Requirements:
- Input: Head node of a singly linked list.
- Output: Boolean (true if cycle exists, false otherwise).
- Constraints: O(1) memory is preferred.

Non-Functional Requirements:
- Time Complexity: O(N).
- Space Complexity: O(1).

Key Design Decisions:
- Algorithm: Floyd’s Cycle-Finding Algorithm (Tortoise and Hare).
- Logic:
- Use two pointers: slow (moves 1 step) and fast (moves 2 steps).
- If there is no cycle, fast will reach the end (null).
- If there is a cycle, fast will eventually lap slow and they will meet inside the loop.
- Analogy: Two runners on a circular track; the faster runner will eventually catch up to the slower one from behind.

Code

Solution (Java):

public class DetectCycle {    public boolean hasCycle(ListNode head) {        if (head == null || head.next == null) {            return false;        }        ListNode slow = head;        ListNode fast = head;        while (fast != null && fast.next != null) {            slow = slow.next;       // Move 1 step            fast = fast.next.next;  // Move 2 steps            if (slow == fast) {                return true; // Cycle detected            }        }        return false; // Reached end of list    }    // Definition for singly-linked list.    class ListNode {        int val;        ListNode next;        ListNode(int x) {            val = x;            next = null;        }    }}

Complexity Analysis:
- Time Complexity: O(N). If there is no cycle, we traverse the list once. If there is a cycle, the fast pointer catches the slow pointer in roughly the number of nodes in the cycle.
- Space Complexity: O(1), as we only use two pointers.

10. “Reverse a Linked List” – Iterative and Recursive Approaches

Difficulty Level: Easy

Engineering Level: Fresher/Entry-Level

Source: GeeksForGeeks (October 2020 - Campus Hiring)

Team: General Engineering

Interview Round: Technical Interview

Technology Focus: Linked List Manipulation, Recursion

Question: “Write a function to reverse a singly linked list. Provide both an iterative solution (using O(1) space) and a recursive solution. Analyze the complexity of both.”

Answer Framework

Requirements Clarification

Functional Requirements:
- Input: Head of a singly linked list.
- Output: New head of the reversed list.
- Constraints: Handle empty list and single-node list.

Non-Functional Requirements:
- Iterative: O(N) Time, O(1) Space.
- Recursive: O(N) Time, O(N) Space (Stack).

Key Design Decisions:
- Iterative: Use three pointers:
- prev: Tracks the previous node (initially null).
- curr: Tracks the current node.
- nextTemp: Stores the next node before breaking the link.
- Recursive: The reverse of a list head -> ... is the reverse of head.next followed by head.

Code

Solution (Java):

public class ReverseLinkedList {    // Approach 1: Iterative (O(1) Space) - PREFERRED    public ListNode reverseListIterative(ListNode head) {        ListNode prev = null;        ListNode curr = head;        while (curr != null) {            ListNode nextTemp = curr.next; // Save next            curr.next = prev;              // Reverse link            prev = curr;                   // Move prev            curr = nextTemp;               // Move curr        }        return prev; // New head    }    // Approach 2: Recursive (O(N) Stack Space)    public ListNode reverseListRecursive(ListNode head) {        // Base case: empty list or single node        if (head == null || head.next == null) {            return head;        }        // Recursive step: reverse the rest of the list        ListNode newHead = reverseListRecursive(head.next);        // Fix the current node's connection        head.next.next = head; // Make next node point back to current        head.next = null;      // Break old forward link        return newHead;    }    class ListNode {        int val;        ListNode next;        ListNode(int x) { val = x; }    }}

Complexity Analysis:
- Iterative: Time O(N), Space O(1). Most efficient.
- Recursive: Time O(N), Space O(N) due to recursion stack depth.