Apple Java Developer Interview Questions & Answers

I would first sort the intervals by their start value. Then I keep a merged list starting with the first interval. For each remaining interval, I compare its start with the end of the last merged interval. If they overlap, I extend the last end to the larger end. Otherwise, I append a new interval. Sorting makes possible overlaps adjacent. The total time is O(n log n), and the merged output uses O(n) auxiliary space.

The input is a list of closed intervals. Each interval has a start and an end. The goal is to combine ranges that overlap and return ranges that no longer overlap. I first sort the intervals by their start values. This puts possible overlaps next to each other. I then build a merged result from left to right. I only need to compare the current interval with the last interval already in the result. If they overlap, I extend that result interval. Otherwise, I add a new one.

1. Should touching closed intervals such as [1,4] and [4,5] be merged?
2. Is it acceptable to sort the input intervals by their start value?

The input is an array of closed intervals. For the example, the input is [[1,3],[2,6],[8,10],[15,18]]. The required output is a new set of non-overlapping intervals that covers exactly the same ranges. The expected result is [[1,6],[8,10],[15,18]]. Because the intervals are closed, touching intervals also overlap under the condition current.start <= lastMerged.end.

Sort the intervals by their start value. The example is already in sorted order: [[1,3],[2,6],[8,10],[15,18]]. If the input is empty, return an empty array. Otherwise, put a copy of the first interval, [1,3], into the merged list. Start processing at index 1. The invariant is that the merged list contains the correctly merged, non-overlapping intervals for the part of the input already processed.

At index 1, the current interval is [2,6]. The merged list before the step is [[1,3]]. Check 2 <= 3. This is true, so the intervals overlap. Update the end to max(3,6) = 6. The merged list becomes [[1,6]].

At index 2, the current interval is [8,10]. The state before the step is [[1,6]]. Check 8 <= 6. This is false, so there is no overlap. Append [8,10]. The state becomes [[1,6],[8,10]].

At index 3, the current interval is [15,18]. The state before the step is [[1,6],[8,10]]. Compare it with the last merged interval [8,10]. Check 15 <= 10. This is false. Append [15,18]. The final state is [[1,6],[8,10],[15,18]].

Sorting places possible overlaps next to each other. After earlier intervals have already been merged, the current interval cannot need to merge with an older result interval without also overlapping the last merged interval. So each current interval only needs one comparison with the last merged interval. We either extend that interval or append a new non-overlapping interval.

The invariant is that the processed prefix is represented by correctly merged, non-overlapping intervals. If current.start <= lastMerged.end, merging preserves the same covered range by extending the end to the maximum endpoint. If current.start > lastMerged.end, the current interval cannot overlap the previous merged ranges, so appending it preserves non-overlap. Therefore, the final result covers exactly the same ranges as the original input.

The Java code handles an empty input first. It sorts with Integer.compare on the start values. It stores merged intervals in an ArrayList<int[]>. During the loop, it reads the current interval and the last merged interval. On overlap, it updates the last end with Math.max. Otherwise, it adds a new interval. Finally, it converts the list to int[][]. Sorting costs O(n log n), the sweep costs O(n), and the merged output uses O(n) auxiliary space.

The key idea is to sort intervals by their start value before merging. After sorting, intervals that may overlap are next to each other. Keep a list called merged and compare each current interval only with the last interval in that list. If current[0] <= lastMerged[1], the ranges overlap, so set lastMerged[1] to Math.max(lastMerged[1], current[1]). Otherwise, append the current interval as a new merged block. The central invariant is that after each processed interval, merged contains the correctly merged, non-overlapping representation of the processed prefix.

Let n be the number of intervals. Sorting the intervals by start value takes O(n log n) time. After sorting, the algorithm makes one left-to-right sweep, which takes O(n) time. Sorting therefore dominates, so the total time is O(n log n). The merged result can contain up to n intervals, so the illustrated solution uses O(n) auxiliary space for the merged output.

A common mistake is trying to merge before sorting by start value. Then possible overlaps may not be adjacent. Another mistake is using current[0] < lastMerged[1] instead of current[0] <= lastMerged[1]. For closed intervals, [1,4] and [4,5] touch and must merge. Candidates may also compare the current interval with every earlier interval instead of only the last merged interval. Another mistake is mishandling fully contained intervals such as [1,10] and [2,3]. Finally, the complexity explanation must include the O(n log n) sorting cost.

State the invariant before coding: after processing each interval, the merged list is already correct and non-overlapping for the processed prefix. Then the merge-or-append decision is easy to explain.

I would use breadth-first search because every valid one-letter change has the same cost. I put the allowed words in a HashSet and process the queue one level at a time. For each word, I try every lowercase letter at every position. When a generated word is in the set, I remove it before enqueueing it, which marks it visited. The first time I dequeue endWord, that level is the shortest length. The expected time is O(NL²), with O(NL) worst-case auxiliary space.

We are given a starting word, an ending word, and a list of allowed words. We need the length of the shortest valid chain from the start to the end. Each step changes exactly one letter, and every new word must be allowed. In the diagram, the start is "hit" and the end is "cog". One shortest chain is hit → hot → dot → dog → cog, so the returned length is 5. Breadth-first search fits because it explores shorter transformation chains before longer ones.

1. Should I return the number of words in the shortest transformation sequence rather than the actual path?
2. Can I assume the words contain lowercase English letters, so each position has 26 possible letters to try?
3. Should I return 0 when endWord cannot be reached?

The inputs are beginWord, endWord, and wordList. The output is the number of words in the shortest valid transformation sequence. Each move changes exactly one character. Every newly reached word must exist in wordList. For the shown example, beginWord is "hit", endWord is "cog", and wordList is ["hot", "dot", "dog", "lot", "log", "cog"]. The answer is 5.

I use breadth-first search, or BFS. BFS processes states in increasing distance from the start. Here, distance means the number of transformations used. That is why the first time endWord is dequeued, the current level gives the shortest sequence length.

I copy wordList into a HashSet named dict. The set tells me whether a generated word is valid and still unseen. When I discover a valid word, I remove it from dict before enqueueing it. This marks the word visited at its earliest BFS level and prevents duplicate queue entries.

The central invariant is that the queue is processed one complete level at a time. Every word reached at an earlier level requires no more transformations than any word first reached at a later level.

If beginWord already equals endWord, the shown implementation returns 1. Otherwise, I build dict from wordList. If endWord is not present, I return 0.

I create an ArrayDeque, enqueue beginWord, and set level to 1 because the sequence already contains the starting word. In the example, the initial queue is [hit], level is 1, and dict contains hot, dot, dog, lot, log, and cog.

At level 1, I dequeue "hit". I try changing every position to each lowercase letter. The only valid unseen neighbor is "hot". I remove "hot" from dict and enqueue it. The queue becomes [hot].

At level 2, I dequeue "hot". The valid unseen neighbors are "dot" and "lot". I remove both from dict and enqueue them. The queue becomes [dot, lot].

At level 3, I process "dot" and then "lot". From "dot" I discover "dog". From "lot" I discover "log". Both are removed from dict before they are enqueued. The queue becomes [dog, log].

At level 4, I process "dog" and then "log". From "dog" I discover "cog", remove it from dict, and enqueue it. When "log" later generates "cog", that word has already been removed, so it is not enqueued again. The queue becomes [cog].

At level 5, I dequeue "cog". It equals endWord, so I return 5 immediately. One valid shortest sequence is hit → hot → dot → dog → cog. A sequence through lot → log also has length 5.

Every valid one-letter transformation has equal cost. BFS therefore explores all states at a smaller transformation distance before states at a larger distance. Removing a word from dict when it is first discovered prevents it from being rediscovered at the same or a later level. Therefore, when endWord is first dequeued, no shorter valid sequence can remain unexplored.

Before processing a BFS level, the code saves queue.size(). Only those words belong to the current level. New words added during that loop belong to the next level.

For each dequeued word, the code first checks whether it equals endWord. Otherwise, it converts the word to a char array. For each character position, it saves the original character, tries letters 'a' through 'z', skips the unchanged character, creates a candidate String, and calls dict.remove(next). If remove returns true, the candidate was valid and unseen, so it is enqueued. The original character is restored before moving to the next position. After the complete level is processed, level increases by one.

Let N be the number of words and L be the word length. For each reachable word, the code tries 26 letters at each of L positions. Creating and hashing each generated length-L String can cost O(L). The expected time is therefore O(26 × N × L²), commonly written as O(NL²). HashSet lookup and removal are O(1) on average after hashing.

The queue may hold O(N) generated Strings of length L, so worst-case auxiliary space is O(NL), plus O(N) HashSet references. Relevant edge cases are endWord missing from wordList, beginWord already equal to endWord, duplicate word-list entries collapsing in the HashSet, and no valid path, which returns 0.

Treat each valid word as a state in an implicit unweighted graph. Two states are connected when one letter can be changed to produce the other word. The algorithm does not build every edge in advance. Instead, when a word is dequeued, it generates candidate neighbors by changing one character at a time and checking the HashSet. BFS is appropriate because every transformation has equal cost. The key invariant is that states are processed level by level in nondecreasing transformation distance. Removing a valid word from dict when it is first discovered marks it visited at its earliest level. Therefore, the first dequeue of endWord gives the shortest transformation length.

Let N be the number of words and L be the length of each word. For each reachable word, the code examines L positions and tries 26 lowercase letters at every position. Creating a candidate String and hashing that length-L String can each take O(L), so the illustrated Java implementation takes O(26 × N × L²) expected time. Because 26 is constant, this is commonly written as O(NL²). HashSet lookup and removal are O(1) on average after hashing. The queue can hold O(N) generated Strings of length L, giving O(NL) worst-case auxiliary space, plus O(N) HashSet references.

One common mistake is marking a word visited only when it is dequeued. That can enqueue the same word more than once. Remove it from the HashSet when it is first discovered. Another mistake is processing newly enqueued words in the same BFS level instead of saving the current queue size first. Candidates may also forget to restore the original character after trying replacements at one position. Another mistake is claiming O(NL) time while ignoring the O(L) cost of creating and hashing each generated String. Finally, do not continue processing after endWord is dequeued and the shortest level is known.

Before coding, state the two rules that make the solution correct: process exactly one queue level at a time, and remove a valid word from the HashSet when it is first discovered. Then connect those rules directly to why the first dequeue of endWord gives the shortest length.

I would use a min heap with at most one current node from each list. First, I put every non-null list head into the heap. Then I repeatedly remove the smallest node, append that same node to the merged list, and add its next node to the heap if it exists. This keeps the result sorted because the heap always exposes a smallest remaining candidate. With N total nodes and k lists, the time is O(N log k) and the auxiliary space is O(k).

We are given k lists of connected nodes. Each list is already ordered from smaller values to larger values. We need to connect all of those existing nodes into one ordered list. At each step, we only need to decide which list has the smallest next value. I keep one current node from each non-empty list in a structure that can quickly give me the smallest one. After I take that node, I make its next node available. This repeats until no nodes remain.

1. Can some entries in the input array be null?
2. Should I reuse the existing ListNode objects instead of creating new nodes for every value?
3. Can duplicate values appear in different lists?

The input is an array of k sorted linked lists. The output is one linked list containing all nodes in ascending order. For the diagram example, the lists are L1 = 1 → 4 → 5, L2 = 1 → 3 → 4, and L3 = 2 → 6. There are 8 nodes in total. The final result is 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6. We reuse the existing nodes instead of copying their values into new result nodes.

I use a Java PriorityQueue as a min heap. Each heap item is a ListNode reference. The comparator orders nodes by node.val. The heap keeps at most one current candidate from each active list. The important invariant is that before each removal, the heap contains the smallest unmerged node from every non-empty list. Because of that, a minimum heap item is a correct next node for the merged output.

A simple alternative would be to scan all k current list heads every time we need the next node. That can require O(k) work for each of N nodes. The min heap reduces each selection to O(log k).

First, insert the head of every non-null list into the min heap. For the example, the initial heap candidates are (1,L1), (1,L2), and (2,L3). Then create a dummy node. The dummy node gives us a fixed starting point for the result. A tail pointer starts at dummy and always points to the last node in the merged list. The initial merged state is dummy → empty.

Step 1: the heap contains (1,L1), (1,L2), and (2,L3). In the diagram's shown trace, remove (1,L1). Append it after tail. The result is 1. Its successor is 4, so add (4,L1). The candidates are now (1,L2), (2,L3), and (4,L1).

Step 2: remove (1,L2). Append it. The result becomes 1 → 1. Add its successor (3,L2). The candidates become (2,L3), (3,L2), and (4,L1).

Step 3: remove (2,L3). The result becomes 1 → 1 → 2. Add its successor (6,L3). The candidates become (3,L2), (4,L1), and (6,L3).

Step 4: remove (3,L2). The result becomes 1 → 1 → 2 → 3. Add its successor (4,L2). The candidates become (4,L1), (4,L2), and (6,L3).

Step 5: in the diagram's shown trace, remove (4,L1). The result becomes 1 → 1 → 2 → 3 → 4. Add its successor (5,L1). The candidates become (4,L2), (5,L1), and (6,L3).

Step 6: remove (4,L2). The result becomes 1 → 1 → 2 → 3 → 4 → 4. This node has no successor, so nothing is added. The candidates are (5,L1) and (6,L3).

Step 7: remove (5,L1). The result becomes 1 → 1 → 2 → 3 → 4 → 4 → 5. It has no successor, so the heap now contains only (6,L3).

Step 8: remove (6,L3). The result becomes 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6. It has no successor. The heap becomes empty, so processing stops and we return dummy.next.

The diagram shows one valid order for nodes with equal values. Java PriorityQueue does not guarantee which equal-valued node is removed first when the comparator returns 0. Either tie order is valid here because the required merged values remain 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6.

Before every heap removal, each active input list contributes its smallest unmerged node. No node farther inside one of those sorted lists can be smaller than that list's current candidate. Therefore, a minimum heap candidate is globally smallest among the remaining nodes. Appending it keeps the merged prefix sorted. After removing a node, only its successor can become the next candidate from that same list. Adding that successor restores the invariant for the next iteration.

Java PriorityQueue is used as the min heap. A comparator orders ListNode references by node.val. We seed the heap with every non-null list head. The dummy node and tail pointer build the result without special handling for the first real node. Inside the loop, poll removes a smallest current node. We link that same node after tail and move tail forward. If that node has a successor, we offer the successor into the heap. When the heap becomes empty, dummy.next is the first real node of the completed merged list.

Let N be the total number of nodes across all lists and k be the number of lists. Every node enters the heap once and leaves the heap once. The heap contains at most k nodes, so each push or pop costs O(log k). The total time is O(N log k). The heap uses O(k) auxiliary space. The other working pointers use O(1) extra space.

If lists is null or has length 0, return null. Null lists are skipped during heap initialization. If all lists are empty, the heap starts empty and dummy.next is null. Duplicate values are valid and remain in sorted order. If k is 1, the same algorithm returns that single sorted list.

The key idea is to compare only the current smallest unmerged node from each list. Because every input list is already sorted, we do not need to look farther inside a list until its current node has been removed. A min heap stores these current candidates and exposes a smallest one efficiently. The central invariant is that the heap contains the smallest unmerged node from every active list. After a node is appended, only that node's successor needs to enter the heap. This keeps the heap size at most k and produces the merged values in ascending order.

Let N be the total number of nodes in all lists, and let k be the number of lists. Every node is added to the min heap once and removed once. The heap contains at most k nodes, so each add or remove operation costs O(log k). The total time is O(N log k). The auxiliary space is O(k) because the heap stores at most one current node from each list. The dummy node and pointer variables use only O(1) additional working space.

A common mistake is putting every node from every list into the heap. That works, but it grows the heap to O(N) instead of keeping at most O(k) candidates. Another mistake is forgetting to insert the popped node's successor, which causes the remaining nodes from that input list to be skipped. Candidates can also update linked-list pointers in an order that loses access to the remaining nodes. Another common mistake is claiming the heap uses O(N) auxiliary space or giving O(N log N) as the complexity of this exact implementation. Finally, do not assume Java PriorityQueue has a stable order for equal-valued nodes.

State the heap invariant before coding: the heap holds the smallest unmerged node from each active list. Then make every loop iteration restore that invariant by polling one node, appending it, and pushing only its successor.

At a high level, I would use the API Gateway as the single public entry point for backend APIs. The Web App, Mobile App, and Partner App send HTTPS requests with a JWT to the gateway. The gateway validates identity, checks authorization, applies rate limits, transforms requests when needed, and routes calls to the User, Order, or Inventory Service. Service responses return through the gateway to the client. The benefit is centralized control and hidden internal services. The trade-off is that the gateway becomes an important shared component that must be operated carefully.

This question asks why we place one controlled entry point between outside applications and many backend services. Without it, each client may need to know every internal service and repeat the same security and traffic rules. The goal is to make access simpler and keep common rules in one place. In this design, all client requests first reach the API Gateway. The gateway checks who is calling, decides whether the request is allowed, chooses the correct service, and sends the response back.

• Should all external clients use the same gateway policies?
• Which gateway responsibilities are most important: security, routing, rate limiting, or aggregation?
• Do backend services remain private and reachable only through the gateway?

I would first explain that the API Gateway is the single public entry point. The Web App, Mobile App, and Partner App do not call internal services directly. Each client sends an HTTPS API request with a JWT to the gateway. A JWT is a token that carries caller identity information and claims. This keeps the internal service layout hidden from external clients. It also gives the backend one place to apply common rules before requests reach business services.

The request next goes through security checks at the gateway. The gateway owns authentication and JWT validation in this diagram. It sends a JWT validation request, described as token introspection, to the Identity Provider (Auth Service). The identity system returns a validation result with token validity and claims. Authentication answers who the caller is. Authorization is a separate gateway responsibility that decides whether that caller may continue. The diagram does not show a separate failure path, so I would not invent one.

After security checks, the gateway applies shared API concerns. These include rate limiting, request transformation, routing, response aggregation, and centralized logging or monitoring. Rate limiting controls how much traffic a caller can send. Request transformation can adapt the incoming request before forwarding it. Response aggregation lets the gateway combine backend results when that behavior is needed. These controls reduce repeated work across clients and services.

The gateway then routes the request to the matching backend service. The diagram shows HTTPS routes to /users, /orders, and /inventory. The User Service handles user work. The Order Service handles order work. The Inventory Service handles inventory work. Each backend sends a separate service response back to the gateway. The services stay behind the Internal Backend System boundary, so external clients do not need to know their locations or topology.

The Order Service owns access to the Orders DB shown in the diagram. It sends an SQL query to the PostgreSQL database and receives the query result. The API Gateway does not query this database directly. This separation is important because the gateway handles cross-cutting API concerns, while the Order Service owns order business logic and order data access.

The service response returns to the API Gateway first. The gateway then sends a separate HTTPS response back to the original client. At the same time, the gateway sends logs, metrics, and traces to OBSERVABILITY using the shown OTLP or HTTPS flow. Observability is a side path. It helps operators understand traffic and behavior, but it does not own the business response. The main trade-off is centralization: the gateway simplifies clients and services, but it also becomes a shared component that needs careful reliability, security, and capacity planning.

The benefit of this design is that clients see one stable entry point instead of many internal services. Security, routing, rate limiting, request transformation, response aggregation, and logging can be applied consistently at the gateway. This reduces repeated work in every backend service. Keeping the Orders DB behind the Order Service also preserves clear data ownership. The downside is that the gateway becomes a very important shared component. More gateway logic can increase operational complexity and can affect many APIs at once if configured badly. Token validation also adds another dependency between the gateway and the Identity Provider (Auth Service). We accept this because central control makes the external API simpler, hides internal service topology, and gives one place to enforce common policies.