Apple Data Scientist Interview Questions & Answers

I would model the courses as a directed graph and use Kahn’s topological sort. For each prerequisite pair [a, b], I add an edge from b to a and count how many prerequisites each course still has. I start a queue with courses whose count is zero. As I finish a course, I reduce the counts of courses that depend on it. If I process all courses, I return True. The time is O(V+E), with O(V+E) auxiliary space.

We have a number of courses and a list that tells us which course must come before another course. We need to decide whether there is some valid order in which every course can be finished. For example, with three courses and the pairs [[2,1],[1,0]], course 0 must come before 1, and 1 must come before 2. So all three can be finished. The main idea is to repeatedly take a course that currently has nothing left before it. If we eventually take every course, the answer is True.

1. Should zero courses return True? The stated contract says yes.
2. Can I assume every course number is valid and duplicate prerequisite pairs are absent? The stated contract says yes.
3. Should I avoid changing the input lists? The stated contract says yes.

The function receives num_courses and prerequisites. Courses are numbered from 0 to num_courses - 1. Each pair [a, b] means course b must be completed before course a. We return True only when every course can be completed. For zero courses, we also return True. The solution only reads the inputs and does not mutate them.

I represent each prerequisite as a directed edge from the prerequisite to the dependent course. So [a, b] becomes b → a. I store these edges in an adjacency list. I also keep an in-degree count for every course. In-degree means how many prerequisite edges are still pointing into that course.

I use Kahn’s topological-sort algorithm. The key rule is simple: a course can enter the queue only when its in-degree is 0. That means all of its prerequisites have already been handled.

For the diagram example, num_courses = 3 and prerequisites = [[2,1],[1,0]]. The edges are 0 → 1 and 1 → 2. The adjacency list is 0:[1], 1:[2], 2:[]. The initial in-degree array is [0,1,1]. Only course 0 has in-degree 0, so the queue starts as [0]. The processed count starts at 0.

Step 1: The queue is [0]. I remove course 0 and increase processed to 1. Course 0 points to course 1, so I reduce course 1's in-degree from 1 to 0. Course 1 is now available, so I add it to the queue. The queue becomes [1], and the in-degree array becomes [0,0,1].

Step 2: I remove course 1 and increase processed to 2. Course 1 points to course 2, so I reduce course 2's in-degree from 1 to 0. I add course 2 to the queue. The queue becomes [2], and the in-degree array becomes [0,0,0].

Step 3: I remove course 2 and increase processed to 3. Course 2 has no outgoing edges, so nothing else changes. The queue becomes empty.

The processed count changed from 0 to 1 to 2 to 3. Since processed == num_courses == 3, the function returns True.

A course is processed only after its in-degree reaches 0. So when we take a course from the queue, every prerequisite that must come before it has already been handled. If all V courses are processed, the graph has no directed cycle blocking progress. If a directed cycle exists, the courses in that cycle never become available, so some courses remain unprocessed.

The code first builds the adjacency list and the in-degree array. It then puts every course with in-degree 0 into a deque. The while loop removes available courses from the left side of the deque. For each dependent course, it decreases the in-degree by 1. When that value becomes 0, the dependent course is added to the queue. Finally, the code checks whether the number of processed courses equals num_courses.

Let V be the number of courses and E be the number of prerequisite pairs. Building the graph takes O(V+E) time. During processing, every course is removed from the queue at most once and every edge is examined once, so the total time is O(V+E). The adjacency list, in-degree array, and queue use O(V+E) auxiliary space. Important cases are zero courses, disconnected acyclic groups of courses, and directed cycles.

The key insight is to keep track of which courses are currently available. A course is available when its in-degree is 0, meaning it has no remaining prerequisite edges pointing into it. We build a directed adjacency list from prerequisite to dependent course and an in-degree array. Kahn’s algorithm repeatedly removes an available course, decreases the in-degree of its dependents, and adds any dependent whose in-degree becomes 0. The central invariant is that a course enters the queue only after all of its prerequisites have been processed. If the processed count reaches V, every course can be completed.

Let V be the number of courses and E be the number of prerequisite pairs. Building the adjacency list and in-degree array takes O(V+E) time. During the main loop, each course is removed from the queue at most once, and each prerequisite edge is examined once. So the total time is O(V+E). The adjacency list stores up to E edges. The in-degree array and queue can each hold up to V entries. Therefore the auxiliary space is O(V+E).

A common mistake is reversing the edge and storing course → prerequisite instead of prerequisite → dependent course. Another mistake is forgetting to increase the dependent course's in-degree when building the graph. Some candidates add a course to the queue before its in-degree actually reaches 0. Another mistake is using list.pop(0) for the queue, which can add unnecessary shifting cost in Python. It is also incorrect to return True only because the queue becomes empty. The correct final check is whether processed equals num_courses.

State the invariant before coding: a course enters the queue only when its in-degree is 0, so all of its prerequisites have already been handled. Then make the code follow that sentence directly.

I would model this as an unweighted graph and use breadth-first search because BFS visits words in increasing number of changes. I build pattern buckets from the words so I can find one-letter neighbors without assuming a fixed alphabet. The queue stores each word with its minimum distance, and I mark words visited before enqueueing them. I discard each processed bucket to avoid rescanning it. The expected time is O(N·L²), and auxiliary space is O(N·L²).

We need the smallest number of one-character changes from begin_word to end_word. Every word used after the start must come from word_list. If both words are already equal, the answer is 0. If the destination is missing from word_list, there is no valid transformation. I use breadth-first search because it explores transformations in increasing number of changes. Pattern buckets connect words that are equal everywhere except one position, so we can find valid next words without guessing which characters may appear.

1. Can I rely on the guarantee that all valid words have the same length?
2. Do you only need the minimum number of operations, not the actual transformation path?
3. Should matching use Python's normal exact string comparison, including character case?

The function receives begin_word, end_word, and word_list. One operation changes exactly one character. Every intermediate word and the destination must be in word_list. We return the minimum number of operations. We return 0 when begin_word equals end_word. We return None when no transformation exists. The function must not change its inputs.

Think of each valid word as a node in an unweighted graph. Two words are neighbors when they differ in exactly one position. BFS is a good fit because every change costs one operation. The queue therefore processes reachable words in nondecreasing distance order.

To find neighbors efficiently, I build pattern buckets. For a word and position i, the key is (i, word[:i], word[i + 1:]). Words with the same key differ only at position i, apart from the same word appearing in its own bucket. The visited set skips the current word and any word already discovered. For example, "hit" and "hot" share the key for position 1 because both have "h" before that position and "t" after it.

First, if begin_word == end_word, return 0. Next, copy word_list into word_set. This does not mutate the input list. If end_word is not in the set, return None.

Then build the pattern dictionary from all words in word_set. Each key points to the words that match that pattern. Start the queue as deque([(begin_word, 0)]). The number is the minimum number of changes used to reach that word. Start visited as {begin_word}. Marking a word visited before enqueueing it prevents duplicate queue entries.

For begin_word = "hit", end_word = "cog", and word_list = ["hit", "hot", "dot", "dog", "cog"], the queue starts with ("hit", 0).

From "hit", the matching pattern bucket discovers "hot". Mark "hot" visited and enqueue ("hot", 1). After that bucket is processed, discard it.

Next, dequeue ("hot", 1). Its matching bucket discovers "dot". Mark "dot" visited and enqueue ("dot", 2).

Next, dequeue ("dot", 2). Its matching bucket discovers "dog". Mark "dog" visited and enqueue ("dog", 3).

Next, dequeue ("dog", 3). Its matching bucket discovers "cog". Because this is end_word, return steps + 1, which is 4. Processing stops immediately. The shown path is "hit" → "hot" → "dot" → "dog" → "cog".

The key invariant is that the BFS queue processes states in nondecreasing distance order. A word is marked visited when it is first discovered, so its first discovered distance is its minimum distance. Therefore, when "cog" is first discovered from "dog" at distance 3, the returned distance 4 is the minimum possible number of changes.

Discarding a processed pattern bucket does not remove a shorter future path. When a bucket is first processed, every unvisited word in that bucket is discovered from the earliest BFS level that can reach the bucket. A later scan of the same bucket cannot give any member a smaller distance.

The code uses collections.deque for FIFO queue behavior. It creates word_set as a copy for membership checks. It creates pattern keys with Python string slices and stores matching words in a dictionary. During BFS, it forms each pattern for the current word, reads candidates from that bucket, skips already visited words, returns immediately when end_word is found, and otherwise marks each new word visited before adding it to the queue. After scanning a bucket, patterns.pop(key, None) removes it so it is never scanned again.

Let N be the number of words and L be the word length. Building each pattern key uses string slicing, which costs O(L), and there are L patterns for each word. With average O(1) Python dictionary and set operations, the expected running time is O(N·L²). Each pattern bucket is scanned at most once. The pattern keys and buckets use O(N·L²) auxiliary space, with another O(N) for visited and the queue.

Important edge cases are begin_word == end_word, which returns 0, end_word missing from word_list, which returns None, and a disconnected transformation graph, which also returns None. The visited set prevents cycles or repeated reachability from causing duplicate processing.

The key idea is to treat valid words as nodes in an unweighted graph and run BFS. Instead of trying possible replacement characters, build pattern buckets from the actual words. A pattern key stores the position, prefix, and suffix around one character. Words in the same bucket can differ only at that position. The central invariant is that the BFS queue processes words in nondecreasing distance order. The first time a word is discovered, its stored distance is minimal. Each processed pattern bucket is discarded, so the same bucket is not scanned repeatedly.

Let N be the number of words and L be the length of each word. Creating one pattern key uses Python string slices, so it costs O(L). We create L keys for each of N words. That gives O(N·L²) preprocessing work. During BFS, every pattern bucket is scanned at most once. Python dictionary and set operations are O(1) on average, so the expected total time is O(N·L²). Auxiliary space is O(N·L²) for pattern keys and buckets, plus O(N) for visited and the queue.

A common mistake is using DFS and assuming the first path found is the shortest. Another is marking a word visited only when it is dequeued, which can add the same word to the queue multiple times. A third mistake is generating neighbors from a hard-coded alphabet even though the stated contract does not limit characters that way. Candidates may also forget to return None when end_word is absent or unreachable. Finally, if pattern buckets are not discarded after processing, the code can repeatedly scan the same bucket and no longer match the stated O(N·L²) expected-time bound.

Explain the invariant before writing the loop: the queue processes words in increasing number of changes, so the first time end_word is discovered its distance is minimal. Then explain that pattern buckets only make neighbor lookup faster. They do not change the BFS correctness argument.