Working at Apple is a dream for many developers, but preparing for coding interviews is no easy task. To make your life easier, we’ve compiled the top 30 interview questions you can expect during a technical interview with Apple.
We start with an overview of the interview process for software engineering and then break down the top Apple interview questions with in-depth code solutions and complexity measures. We’ll offer our solutions in C++.
This guide at a glance:
- Apple interview process overview
- Arrays and graphs questions
- Linked Lists questions
- Trees questions
- Strings questions
- Dynamic programming questions
- Math, stats, and backtracking
- Searching and design questions
- Behavioral questions
- Tips for preparing for interviews
Apple interview process overview
Apple’s software engineer interview process differs from other larger tech companies, like Amazon, due to the number of interviews they hold and their on-site process.
If you are asked to interview at Apple, the process generally looks like this:
Prescreen with Recruiter: It will take about a week from resume submission to first contact. A recruiter will usually reach out over LinkedIn or email to set up a time for a phone call. This phone screen will last from 15-30 minutes, and the questions will not be overly technical. You could expect questions like Why do you want to work for Apple? or What’s your favorite Apple product or service?
Technical phone interview: Usually a week later, they will schedule your next technical phone interview. There will be one or two technical phone screens with questions about your resume and a coding question on data structures and algorithms. The coding interviews are about 45-60 minutes, with 30 minutes to complete the challenge.
On-site interview: The onsite interview will last about 6 hours. You'll meet with 8-12 Apple employees, and interviews will be a mix of behavioral, domain knowledge, and coding challenges. Each interview is about 45 minutes to an hour where you will be posed with technical problems. Behavioral questions are also very important for hiring managers.
Data structures you should know: Arrays, Linked Lists, Stacks, Queues, Trees, Graphs, Heaps, Hash sets, Hash maps
Algorithms you should know: Depth first search, Breadth first search, Binary search, Quicksort, Mergesort, Dynamic programming, Divide and conquer
Arrays and graphs questions
Determine sum of three integers
The goal of this exercise is to determine if the sum of three integers is equal to the given value.
Problem statement: Given an array of integers and a value, determine if there are any three integers in the array whose sum equals the given value.
Consider this array and the target sums.
bool find_sum_of_two(vector<int>& A, int val,
size_t start_index) {
for (int i = start_index, j = A.size() - 1; i < j;) {
int sum = A[i] + A[j];
if (sum == val) {
return true;
}
if (sum < val) {
++i;
} else {
--j;
}
}
return false;
}
bool find_sum_of_three_v3(vector<int> arr,
int required_sum) {
std::sort(arr.begin(), arr.end());
for (int i = 0; i < arr.size() - 2; ++i) {
int remaining_sum = required_sum - arr[i];
if (find_sum_of_two(arr, remaining_sum, i + 1)) {
return true;
}
}
return false;
}
int main(){
vector<int> arr = {-25, -10, -7, -3, 2, 4, 8, 10};
cout<<"-8: " <<find_sum_of_three_v3(arr, -8)<<endl;
cout<<"-25: "<<find_sum_of_three_v3(arr, -25)<<endl;
cout<<"0: " <<find_sum_of_three_v3(arr, 0)<<endl;
cout<<"-42: " <<find_sum_of_three_v3(arr, -42)<<endl;
cout<<"22: " <<find_sum_of_three_v3(arr, 22)<<endl;
cout<<"-7: " <<find_sum_of_three_v3(arr, -7)<<endl;
cout<<"-3: " <<find_sum_of_three_v3(arr, -3)<<endl;
cout<<"2: " <<find_sum_of_three_v3(arr, 2)<<endl;
cout<<"4: " <<find_sum_of_three_v3(arr, 4)<<endl;
cout<<"8: " <<find_sum_of_three_v3(arr, 8)<<endl;
cout<<"7: " <<find_sum_of_three_v3(arr, 7)<<endl;
cout<<"1: " <<find_sum_of_three_v3(arr, 1)<<endl;
return 0;
}
In this solution, we sort the array. Then, fix one element e and find a pair (a, b) in the remaining array so that required_sum - e is a + b.
Start with first element e in the array and try to find such a pair (a, b) in the remaining array (i.e A[i + 1] to A[n - 1]) that satisfies the condition: a+b = required_sum - e. If we find the pair, we have found the solution: a, b and e. Now we can stop the iteration.
Otherwise, we repeat the above steps for all elements e at index i = 1 to n - 3 until we find a pair that meets the condition.
Runtime Complexity: Quadratic, O(n^2)
Memory Complexity: Constant, O(1)
Merge overlapping intervals
The goal of this exercise is to merge all the overlapping intervals of a given list to produce a list that has only mutually exclusive intervals.
Problem statement: You have an array (list) of interval pairs as input where each interval has a start and end timestamp, sorted by starting timestamps. Merge the overlapping intervals and return a new output array.
Consider an input array below. Intervals (1, 5), (3, 7), (4, 6), (6, 8) are overlapping so they should be merged to one interval (1, 8). Similarly, intervals (10, 12) and (12, 15) are also overlapping and should be merged to (10, 15).
class Pair{
public:
int first, second;
Pair(int x, int y){
first = x;
second = y;
}
};
vector<Pair> merge_intervals(vector<Pair>& v) {
if(v.size() == 0) {
return v;
}
vector<Pair> result;
result.push_back(Pair(v[0].first, v[0].second));
for(int i = 1 ; i < v.size(); i++){
int x1 = v[i].first;
int y1 = v[i].second;
int x2 = result[result.size() - 1].first;
int y2 = result[result.size() - 1].second;
if(y2 >= x1){
result[result.size() - 1].second = max(y1, y2);
}
else{
result.push_back(Pair(x1, y1));
}
}
return result;
}
int main() {
vector<Pair> v {
Pair(1, 5),
Pair(3, 7),
Pair(4, 6),
Pair(6, 8),
Pair(10, 12),
Pair(11, 15)
};
vector<Pair> result = merge_intervals(v);
for(int i = 0; i < result.size(); i++){
cout << "[" << result[i].first << ", " << result[i].second << "] ";
}
}
This problem can be solved with a linear scan algorithm. The list of input intervals is given, and we’ll keep merged intervals in the output list. For each interval in the input list:
- If the input interval is overlapping with the last interval in the output list, merge these two intervals and update the last interval of the output list with the merged interval.
- Otherwise, add an input interval to the output list.
Runtime complexity: Linear, O(n)
Memory complexity: Linear, O(n)
Clone a Directed Graph
The goal of this exercise is to clone a directed graph and print an output graph using hash table and depth first traversal.
Problem statement: Given the root node of a directed graph, clone the graph by creating a deep copy. The cloned graph will have the same vertices and edges.
struct Node {
int data;
list<Node*> neighbors;
Node(int d) : data(d) {}
};
Node* clone_rec(Node* root,
unordered_map<Node*,
Node*>& nodes_completed) {
if (root == nullptr) {
return nullptr;
}
Node* pNew = new Node(root->data);
nodes_completed[root] = pNew;
for (Node* p : root->neighbors) {
auto x = nodes_completed.find(p);
if (x == nodes_completed.end()){
pNew->neighbors.push_back(clone_rec(p, nodes_completed));
} else {
pNew->neighbors.push_back(x->second /*value*/);
}
}
return pNew;
}
Node* clone(Node* root) {
unordered_map<Node*, Node*> nodes_completed;
return clone_rec(root, nodes_completed);
}
// this is un-directed graph i.e.
// if there is an edge from x to y
// that means there must be an edge from y to x
// and there is no edge from a node to itself
// hence there can maximim of (nodes * nodes - nodes) / 2 edgesin this graph
void create_test_graph_undirected(int nodes, int edges, vector<Node*>& vertices) {
for (int i = 0; i < nodes; ++i) {
vertices.push_back(new Node(i));
}
vector<pair<int, int>> all_edges;
for (int i = 0; i < vertices.size(); ++i) {
for (int j = i + 1; j < vertices.size(); ++j) {
all_edges.push_back(pair<int, int>(i, j));
}
}
std::random_shuffle(all_edges.begin(), all_edges.end());
for (int i = 0; i < edges && i < all_edges.size(); ++i) {
pair<int, int>& edge = all_edges[i];
vertices[edge.first]->neighbors.push_back(vertices[edge.second]);
vertices[edge.second]->neighbors.push_back(vertices[edge.first]);
}
}
void print_graph(vector<Node*>& vertices) {
for (Node* n : vertices) {
cout << n->data << ": {";
for (Node* t : n->neighbors) {
cout << t->data << " ";
}
cout << "}" << endl;
}
}
void print_graph(Node* root, unordered_set<Node*>& visited_nodes) {
if (root == nullptr || visited_nodes.find(root) != visited_nodes.end()) {
return;
}
visited_nodes.insert(root);
cout << root->data << ": {";
for (Node* n : root->neighbors) {
cout << n->data << " ";
}
cout << "}" << endl;
for (Node* n : root->neighbors) {
print_graph(n, visited_nodes);
}
}
void print_graph(Node* root) {
unordered_set<Node*> visited_nodes;
print_graph(root, visited_nodes);
}
int main() {
vector<Node*> vertices;
create_test_graph_undirected(7, 18, vertices);
print_graph(vertices[0]);
Node* cp = clone(vertices[0]);
cout << endl << "After copy" << endl;
print_graph(cp);
return 0;
}
We use depth first traversal and create a copy of each node while traversing the graph. Use a hashtable to store each completed node so we won’t revisit nodes that exist in that hashtable. The hashtable key will be a node in the original graph, and its value will be the corresponding node in the cloned graph.
Runtime Complexity: Linear, O(n)
Memory Complexity: Logarithmic, O(n), where n is the number of vertices in the graph.
To see the solution to any of these problems in Java, Python, Ruby, or JavaScript, go to our sister-site, Coding Interview.
Linked Lists questions
Add two integers
The goal of this exercise is to add two integers of two linked lists.
Problem statement: You are given the head pointers of two linked lists where each linked list represents an integer number (i.e. each node is a digit). Add them and return the new linked list.
// assuming both integers are stored in a linked list
// e.g. 415 is stored as 5->1->4
// 32 is stored as 2->3
LinkedListNode* add_integers(
LinkedListNode* integer1,
LinkedListNode* integer2) {
LinkedListNode* result = nullptr;
LinkedListNode* last = nullptr;
int carry = 0;
while (
integer1 != nullptr ||
integer2 != nullptr ||
carry > 0) {
int first =
(integer1 == nullptr ? 0 : integer1->data);
int second =
(integer2 == nullptr ? 0 : integer2->data);
int sum = first + second + carry;
LinkedListNode* pNew =
new LinkedListNode(sum % 10);
carry = sum / 10;
if (result == nullptr) {
result = pNew;
} else {
last->next = pNew;
}
last = pNew;
if (integer1 != nullptr) {
integer1 = integer1->next;
}
if (integer2 != nullptr) {
integer2 = integer2->next;
}
}
return result;
}
int main(int argc, char* argv[]) {
vector<int> v1 = {1, 2, 3}; // 321
vector<int> v2 = {1, 2}; // 21
LinkedListNode* first = LinkedList::create_linked_list(v1);
LinkedListNode* second = LinkedList::create_linked_list(v2);
// sum should be 321 + 21 = 342 => 2->4->3
LinkedListNode* result = add_integers(first, second);
vector<int> r = {2, 4, 3}; // 342
LinkedListNode* expected = LinkedList::create_linked_list(r);
assert(LinkedList::is_equal(result, expected));
cout << endl << "First:";
LinkedList::display(first);
cout << endl << "Second:";
LinkedList::display(second);
cout << endl << "Result:";
LinkedList::display(result);
result = add_integers(first, nullptr);
assert(LinkedList::is_equal(result, first));
result = add_integers(nullptr, second);
assert(LinkedList::is_equal(result, second));
}
To understand this better, let’s consider an example. Say we want to add the integers 9901 and 237. The result of this addition would be 10138.
The integers are stored inverted in the linked lists to make this easier. The most significant digit of the number is the last element of the linked list. To start adding, we start from the heads of the two linked lists.
At each iteration, we add the current digits of the two lists and insert a new node with the resulting digit at the tail of the result linked list. We’ll also need to maintain carry for each step.
We do this for all digits in both the linked lists. If one of the linked lists ends sooner, we’ll continue with the other linked list. Once both of the linked lists are done and no carry is left to be added, the algorithm will terminate.
Runtime Complexity: Linear, O(n)
Memory Complexity: Linear, O(n)
Merge two sorted linked lists
The goal of this exercise is to merge two sorted linked lists.
Problem statement: Given two sorted linked lists, merge them so the resulting linked list is also sorted.
typedef LinkedListNode* NodePtr;
NodePtr merge_sorted(NodePtr head1, NodePtr head2) {
// if both lists are empty then merged list is also empty
// if one of the lists is empty then other is the merged list
if (head1 == nullptr) {
return head2;
} else if (head2 == nullptr) {
return head1;
}
NodePtr mergedHead = nullptr;
if (head1->data <= head2->data) {
mergedHead = head1;
head1 = head1->next;
} else {
mergedHead = head2;
head2 = head2->next;
}
NodePtr mergedTail = mergedHead;
while (head1 != nullptr && head2 != nullptr) {
NodePtr temp = nullptr;
if (head1->data <= head2->data) {
temp = head1;
head1 = head1->next;
} else {
temp = head2;
head2 = head2->next;
}
mergedTail->next = temp;
mergedTail = temp;
}
if (head1 != nullptr) {
mergedTail->next = head1;
} else if (head2 != nullptr) {
mergedTail->next = head2;
}
return mergedHead;
}
void test(vector<int>& v1, vector<int>& v2, vector<int>& expected) {
LinkedListNode* list_head1 = LinkedList::create_linked_list(v1);
cout<<"List 1: "<<LinkedList::getList(list_head1)<<endl;
LinkedListNode* list_head2 = LinkedList::create_linked_list(v2);
cout<<"List 2: "<<LinkedList::getList(list_head2)<<endl;
LinkedListNode* merged = merge_sorted(list_head1, list_head2);
cout<<"Result: "<<LinkedList::getList(merged)<<endl;
LinkedListNode* expected_list = LinkedList::create_linked_list(expected);
assert(LinkedList::is_equal(merged, expected_list));
}
int main(int argc, char* argv[]) {
vector<int> v1 = {1, 3, 5, 6};
vector<int> v2 = {2, 4, 6, 20, 34};
vector<int> expected = {1, 2, 3, 4, 5, 6, 6, 20, 34};
test(v1, v2, expected);
v1 = {1, 3, 5, 6};
v2 = {};
expected = {1, 3, 5, 6};
test(v1, v2, expected);
v1 = {1, 3, 5, 6};
v2 = {2, 4, 6, 20};
expected = {1, 2, 3, 4, 5, 6, 6, 20};
test(v1, v2, expected);
v1 = {4, 4};
v2 = {4, 4, 4};
expected = {4, 4, 4, 4 ,4};
test(v1, v2, expected);
}
Maintain a head and a tail pointer on the merged linked list. Choose the head of the merged linked list by comparing the first node of both linked lists.
For all subsequent nodes, choose the smaller current node and link it to the tail of the merged list. Move the current pointer of that list one step forward.
If there are still some elements in only one of the lists, link this remaining list to the tail of the merged list. Initially, the merged linked list is NULL.
Compare the value of the first two nodes and make the node with the smaller value the head node of the merged linked list. In this example, it is 4 from head1. Since it’s the first and only node in the merged list, it will be the tail. Then move head1 one step forward.
Runtime Complexity: Linear, O(m + n), where m and n are lengths of our linked lists
Memory Complexity: Constant, O(1)
Trees questions
Determine if two binary trees are identical
The goal of this exercise is to compare two binary trees to determine if they are identical or not.
Problem statement: You are given the roots of two binary trees and must determine if these trees are identical. Identical trees have the same layout and data at each node.
Tip: Trees that have the same data aren’t necessarily identical. What’s important is their structure.
bool are_identical(
BinaryTreeNode* root1,
BinaryTreeNode* root2) {
if (root1 == nullptr && root2 == nullptr) {
return true;
}
if (root1 != nullptr && root2 != nullptr) {
return ((root1->data == root2->data) &&
are_identical(root1->left, root2->left) &&
are_identical(root1->right, root2->right));
}
return false;
}
int main() {
BinaryTreeNode *root1 = new BinaryTreeNode(100);
insert_bst(root1, 50);
insert_bst(root1, 200);
insert_bst(root1, 25);
insert_bst(root1, 125);
insert_bst(root1, 350);
display_level_order(root1);
BinaryTreeNode *root2 = create_random_BST(15);
display_level_order(root2);
// Try changing the roots being passed
if(are_identical(root1, root2)) {
cout<< " the trees are identical" << endl;
} else {
cout<< "the trees are not identical" << endl;
}
}
This problem can be solved recursively. The base case of recursion for this solution is if two compared nodes are null or one of them is null.
Two trees A and B are identical if:
- Data on their roots is the same or both roots are null
- The left subtree of
Ais identical to the left sub-tree ofB - The right subtree of
Ais identical to the right subtree ofB
Use a depth-first traversal on both trees simultaneously and keep comparing the data at each level to solve this problem.
Runtime Complexity: Linear, O(n)
Memory Complexity: O(h) in best case, or it will be O(log n) for a balanced tree and in the worst case can be O(n).
Mirror binary tree nodes
The goal of this exercise is to use depth first traversal and bottom up mirroring to mirror the nodes of a binary tree.
Problem statement: You are given the root node of a binary tree and must swap the left and right children for each node.
void mirror_tree(BinaryTreeNode* root) {
if (root == nullptr) {
return;
}
// We will do a post-order traversal of the binary tree.
if (root->left != nullptr) {
mirror_tree(root->left);
}
if (root->right != nullptr) {
mirror_tree(root->right);
}
// Let's swap the left and right nodes at current level.
BinaryTreeNode* temp = root->left;
root->left = root->right;
root->right = temp;
}
int main(int argc, char* argv[]) {
BinaryTreeNode* root = create_random_BST(15);
display_level_order(root);
mirror_tree(root);
cout << endl << "Mirrored tree = " << endl;
display_level_order(root);
}
We do a post order traversal of the binary tree. For every node, swap its left child with its right child. We use DFS on the tree, so that before returning from a node, all its children have been visited (and mirrored).
Runtime complexity: Linear, O(n)
Memory Complexity: Linear, O(n) in the worst case
To see the solution to any of these problems in Java, Python, Ruby, or JavaScript, go to our sister-site, Coding Interview.
Strings questions
Find all palindrome substrings
The goal of this exercise is to find the palindrome substrings of a given string.
Problem statement: Given a string, find all non-single letter substrings that are palindromes. The string given is "aabbbaa".
Try it yourself below before checking the solution.
int find_palindromes_in_sub_string(const string& input, int j, int k) {
int count = 0;
for (; j >= 0 && k < input.length(); --j, ++k) {
if (input[j] != input[k]) {
break;
}
cout << input.substr(j, k - j + 1) << endl;
++count;
}
return count;
}
int find_all_palindrome_substrings(const string& input) {
int count = 0;
for (int i = 0; i < input.length(); ++i) {
count += find_palindromes_in_sub_string(input, i - 1, i + 1);
count += find_palindromes_in_sub_string(input, i, i + 1);
}
return count;
}
int main() {
string str = "aabbbaa";
cout << "Total palindrome substrings: " << find_all_palindrome_substrings(str) << endl;
}
For each letter in the input string, start expanding to the left and right while checking for even and odd length palindromes. Move to the next letter if we know a palindrome doesn’t exist there.
We expand one character to the left and right and compare. If both are equal, we print out the palindrome substring.
Runtime complexity: Polynomial, O(n^2)
Memory complexity: Constant, O(1)
Reverse words in a sentence
The goal of this exercise is to reverse the words in a given string. Be sure to note how the words are separated by whitespaces.
Problem statement: Reverse the order of words in a given sentence (an array of characters). The words given are "Hello World!".
void str_rev(char * str, int len) {
if (str == nullptr || len < 2) {
return;
}
char * start = str;
char * end = str + len - 1;
while (start < end) {
if (start != nullptr && end != nullptr) {
char temp = * start;
* start = * end;
* end = temp;
}
start++;
end--;
}
}
void reverse_words(char * sentence) {
// Here sentence is a null-terminated string ending with char '\0'.
if (sentence == nullptr) {
return;
}
// To reverse all words in the string, we will first reverse
// the string. Now all the words are in the desired location, but
// in reverse order: "Hello World" -> "dlroW olleH".
int len = strlen(sentence);
str_rev(sentence, len);
// Now, let's iterate the sentence and reverse each word in place.
// "dlroW olleH" -> "World Hello"
char * start = sentence;
char * end;
while (true) {
// find the start index of a word while skipping spaces.
while (start && * start == ' ') {
++start;
}
if (start == nullptr || * start == '\0') {
break;
}
// find the end index of the word.
end = start + 1;
while (end && * end != '\0' && * end != ' ') {
++end;
}
// let's reverse the word in-place.
if (end != nullptr) {
str_rev(start, (end - start));
}
start = end;
}
}
int main() {
string str = "Hello World!";
char* a = const_cast<char*>(str.c_str());
cout << a << endl;
reverse_words(a);
cout << a << endl;
}
There are two steps to this problem. First, reverse the string. Then, traverse the string and reverse each word in place.
Runtime complexity: Linear, O(n)
Memory complexity: Constant, O(1)
Dynamic programming questions
Largest Sum Subarray
The goal of this exercise is to use your dynamic programming skills and Kadane’s algorithm to find the largest sum subarray.
Problem statement: Find the largest sum subarray. In the array below, the largest sum subarray starts at index 3 and ends at 6, and with the largest sum being 12.
int find_max_sum_sub_array(int A[], int n) {
if (n < 1) {
return 0;
}
int curr_max = A[0];
int global_max = A[0];
for (int i = 1; i < n; ++i) {
if (curr_max < 0) {
curr_max = A[i];
} else {
curr_max += A[i];
}
if (global_max < curr_max) {
global_max = curr_max;
}
}
return global_max;
}
int main() {
int v[] = {-4, 2, -5, 1, 2, 3, 6, -5, 1};
cout << "Sum of largest subarray: " << find_max_sum_sub_array(v, sizeof(v) / sizeof(v[0])) << endl;
return 0;
}
We use Kadane’s algorithm to solve this. The basic idea of this algorithm is to scan the entire array and at each position find the maximum sum of the subarray ending there. This is achieved by keeping a current_max for the current array index and a global_max.
The algorithm is as follows:
current_max = A[0]
global_max = A[0]
for i = 1 -> size of A
if current_max is less than 0
then current_max = A[i]
otherwise
current_max = current_max + A[i]
if global_max is less than current_max
then global_max = current_max
Runtime complexity: Linear, O(n)
Memory complexity: Constant, O(1)
Math and stats
Power of a number
The goal of this exercise is to use divide and conquer and write a function that calculates the raised to the power of a number.
Problem statement: You are given a double, x and an integer n, write a function to calculate x raised to the power n.
power (2, 5) = 32
power (3, 4) = 81
power (1.5, 3) = 3.375
power (2, -2) = 0.25
double power_rec(double x, int n) {
if (n == 0) return 1;
if (n == 1) return x;
double temp = power_rec(x, n/2);
if (n % 2 == 0) {
return temp * temp;
} else {
return x * temp * temp;
}
}
double power(double x, int n) {
bool is_negative = false;
if (n < 0) {
is_negative = true;
n *= -1;
}
double result = power_rec(x, n);
if (is_negative) {
return 1 / result;
}
return result;
}
bool test_power(double x, int n) {
double r1 = power(0.753, n);
double r2 = pow(0.753, n);
double diff = r1 - r2;
if (diff < 0) {
diff = diff * -1;
}
if (diff > 0.00000000001) {
cout << "Failed for " << x << ", " << n << endl;
return false;
}
return true;
}
int main(int argc, char* argv[]) {
bool pass = true;
for (int n = -5; n <= 5; ++n) {
bool temp_pass = test_power(0.753, n);
pass &= temp_pass;
}
pass &= test_power(0, 0);
cout << "Power(0, 0) = " << pow(0, 0) << endl;
if (pass) {
cout << "Passed." << endl;
} else {
cout << "Failed." << endl;
}
}
We can use the divide and conquer approach to solve this problem most efficiently. In the dividing step, we keep dividing n by 2 recursively until we reach the base case.
In the combining step, we get the result r of the sub-problem and compute the result of the current problem using the two rules below:
- If
nis even, the result isr * r(whereris the result of sub-problem) - If
nis odd, the result isx * r * r(whereris the result of sub-problem)
Runtime Complexity: Logarithmic, O(logn)
Memory Complexity: Logarithmic, O(log n)
Find all sum combinations
The goal of this exercise is to use your backtracking skills to find all sum combinations.
Problem statement: Given a positive integer, target, print all possible combinations of positive integers that add to the target number.
The output will be in the form a list of lists or an array of arrays, as each element in the list will be another list containing a possible sum combination.
For example, if you are given input 5, these are the possible sum combinations.
1, 4
2, 3
1, 1, 3
1, 2, 2
1, 1, 1, 2
1, 1, 1, 1, 1
void print(vector<vector<int>> output){
for(int i = 0; i < output.size(); i++){
cout << "[ ";
for(int j = 0; j < output[i].size(); j++){
cout << output[i][j] << ", ";
}
cout << "]" << endl;
}
}
void print_all_sum_rec(
int target,
int current_sum,
int start, vector<vector<int>>& output,
vector<int>& result) {
if (target == current_sum) {
output.push_back(result);
}
for (int i = start; i < target; ++i) {
int temp_sum = current_sum + i;
if (temp_sum <= target) {
result.push_back(i);
print_all_sum_rec(target, temp_sum, i, output, result);
result.pop_back();
} else {
return;
}
}
}
vector<vector<int>> print_all_sum(int target) {
vector<vector<int>> output;
vector<int> result;
print_all_sum_rec(target, 0, 1, output, result);
return output;
}
int main(int argc, const char* argv[]) {
int n = 4;
vector<vector<int>> result = print_all_sum(n);
print (result);
}
We recursively go through all possible sum combinations, and when the running sum equals the target, print that combination.
The algorithm will recursively check all the numbers that can sum up to the target.
In each recursive call, there is a for loop that runs from start to target, where start is initially 1. current_sum is the variable that is incremented with every recursive call.
Every time a value is added to the current_sum, it is also added to the result list. Whenever current_sum equals target, we know that the result list contains a possible combination for target, and this list is then appended to the final output list.
Base condition of recursion:
if current_sum equals target
print the output contents
Before each recursive call, an element is added to result. However, after each call, this element is also removed from the list to reset the list.
Runtime Complexity: Exponential, O^2
Memory Complexity: Linear, O(n)
Searching and design questions
Search in rotated array
The goal of this exercise is to search in a rotated array for a given number in a sorted array. Try to solve the problem using binary search.
Problem statement: Search for a given number in a sorted array, with unique elements, that has been rotated by some arbitrary number, assuming that the array does not contain duplicates. Return -1 if the number does not exist.
Below is an original array before rotation:
After performing rotation on this array 6 times it changes to:
int binary_search(vector<int>& arr, int start, int end, int key) {
// assuming all the keys are unique.
if (start > end) {
return -1;
}
int mid = start + (end - start) / 2;
if (arr[mid] == key) {
return mid;
}
if (arr[start] <= arr[mid] && key <= arr[mid] && key >= arr[start]) {
return binary_search(arr, start, mid-1, key);
}
else if (arr[mid] <= arr[end] && key >= arr[mid] && key <= arr[end]) {
return binary_search(arr, mid+1, end, key);
}
else if (arr[end] <= arr[mid]) {
return binary_search(arr, mid+1, end, key);
}
else if (arr[start] >= arr[mid]) {
return binary_search(arr, start, mid-1, key);
}
return -1;
}
int binary_search_rotated(vector<int>& arr, int key) {
return binary_search(arr, 0, arr.size()-1, key);
}
int main(int argc, char* argv[]) {
vector<int> v1 = {6, 7, 1, 2, 3, 4, 5};
cout<<"Key(3) found at: "<<binary_search_rotated(v1, 3)<<endl;
cout<<"Key(6) found at: "<<binary_search_rotated(v1, 6)<<endl;
vector<int> v2 = {4, 5, 6, 1, 2, 3};
cout<<"Key(3) found at: "<<binary_search_rotated(v2, 3)<<endl;
cout<<"Key(6) found at: "<<binary_search_rotated(v2, 6)<<endl;
}
The solution is like a binary search with some modifications. Notice that at least one half of the array is always sorted. If the number n lies within the sorted half of the array, then our problem is a basic binary search. Otherwise, discard the sorted half and examine the unsorted half.
Runtime complexity: Logarithmic, O(log n)
Memory complexity: Logarithmic, O(log n)
Implement a LRU cache
The goal of this design exercise is to implement Least Recently Used (LRU), a common caching strategy, using a doubly linked list and hashing.
Problem statement: Least Recently Used (LRU) defines the policy to evict elements from the cache to make room for new elements when the cache is full, meaning it discards the least recently used items first.
Take an example of a cache that has a capacity of 4 elements. We cache the elements 1, 2, 3, and 4. This diagram below represents the cache state after first access of all four elements.
We now need to cache another element 5.
Let’s see what happens when 2 is accessed again. Now 3 becomes the next in line to be evicted from the cache.
// Linked list operations
// void add_at_tail(int val)
// void delete_node(ListNode* node)
// void delete_from_head()
// void delete_from_tail()
// ListNode* get_head()
// void set_head(ListNode* node)
// ListNode* get_tail()
// void set_tail(ListNode* node)
// simple single threaded LRUCache
class LRUCache {
unordered_set<int> cache;
// each entry in linked list is the value of the element
LinkedList cache_vals;
int capacity; // total capacity
public:
LRUCache(int capacity) {
this->capacity = capacity;
}
~LRUCache() {
cache.clear();
}
ListNode* get(int val) {
auto p = cache.find(val);
if (p == cache.end()) {
return nullptr;
}
else{
ListNode* i = cache_vals.get_head();
while(i != nullptr){
if (i->value == val){
return i;
}
i = i->next;
}
}
}
void set(int value) {
ListNode* check = get(value);
if(check == nullptr){
if(cache.size() >= capacity){
cache_vals.add_at_tail(value);
int head_val = cache_vals.get_head()->value;
cache.erase(head_val);
cache_vals.delete_from_head();
}
else{
cache_vals.add_at_tail(value);
cache.insert(value);
}
}
else{
if(check == cache_vals.get_tail()){
return;
}
if(check == cache_vals.get_head()){
cache_vals.add_at_tail(check->value);
cache_vals.delete_from_head();
return;
}
if(check->prev != nullptr){
check->prev->next = check->next;
}
if(check->next != nullptr){
check->next->prev = check->prev;
}
cache_vals.add_at_tail(check->value);
delete check;
}
}
void print() {
ListNode* i = cache_vals.get_head();
while(i != nullptr){
cout << i->value << ", ";
i = i ->next;
}
cout << endl;
}
};
int main(int argc, char const *argv[])
{
LRUCache cache(4);
cache.set(1);
cache.print();
cache.set(2);
cache.print();
cache.set(3);
cache.print();
cache.set(4);
cache.print();
cache.set(5);
cache.print();
cache.set(2);
cache.print();
return 0;
}
Caching is a technique to store data in a faster storage (usually RAM) to serve future requests faster. Cache stores are usually not big enough to store a full data set. We need to evict data from the cache when it becomes full.
LRU is very simple and a commonly used algorithm for this process. We evict the oldest data from the cache to accommodate new data.
To implement an LRU cache we use two data structures: a hashmap and a doubly linked list. A doubly linked list helps in maintaining the eviction order and a hashmap helps with $O(1)$ lookup of cached keys. Here is the algorithm:
If the element exists in hashmap
move the accessed element to the tail of the linked list
Otherwise,
if eviction is needed i.e. cache is already full
Remove the head element from doubly linked list and delete its hashmap entry
Add the new element at the tail of linked list and in hashmap
Get from Cache and Return
Note: The doubly linked list is for tracking the most recently accessed elements. The element at the tail of the doubly linked list is the most recently accessed element.
All newly inserted elements go to the tail, and any element accessed goes to the tail.
Runtime Complexity:
-
get (hashset): Constant, O(1) -
set (hashset): Constant, O(1) - Deletion at head when adding a new element: Constant, O(1)
- Search for deleting and adding to tail: Linear, O(n)
Memory Complexity: Linear, O(n), where n is the size of cache
Behavioral questions
Now that we’ve discussed the top technical questions, let’s look at the most common behavioral interview questions you can expect at an Apple interview, which are arguably just as important for your success.
As you’ll see from this list, Apple wants to understand what kind of thinker you are, how you handle conflict, and what investments you bring to the table.
- What were some of your best and worst days over the last four years?
- What is your favorite Apple product or service, and why?
- Describe an achievement you are particularly proud of.
- Have you ever disagreed with your manager about a decision at work? What happened? How did you handle the situation?
- How have you overcome failure? What did you learn from it?
- Why do you want to work for Apple?
- What is the first thing you notice when walking into an Apple store?
- Describe the most challenging software development problem you faced. How did you solve it?
- If you accept a job at Apple, what will you miss most about your current role? What will you miss least?
- Do you take any steps to enhance your skills outside of work?
- Describe a time you went above and beyond for a customer
- Explain to a 8 year old what a modem/router is and its functions.
- How does this role fit into your 5 year career or life plan?
- If we hired you, what would you want to work on?
- How would you test your favorite app?
- If a person called for tech support but had a dinosaur or legacy product, how would you handle it?
Tip: Regardless of the question or position, it is always recommended to use STAR method for answering their behavioral-based interview questions:
- Describe the situation.
- Describe the task.
- Describe the action(s) taken to handle the task.
- Explain the results you achieved.
Tips for preparing for interviews
Practicing for interviews takes tons of time and patience, and there is no golden ticket to cracking the coding interview. But there are some best practices we've learned over the years.
Practice with different tools. It's a good idea to combine whiteboard practice, online courses, and mock interviews to get the most out of your time. It's crucial that you practice talking aloud as you solve problems, so use different kinds of tolls to get practice.
Create a study plan. It is also recommended to create a detailed preparation plan for anywhere between 3-6 months. This way, you have a structure to follow and avoid missing essential concepts.
Avoid rote memorization. It is also recommended to avoid memorizing questions. Instead, practice by building real products that Apple might use. This is the ideal way to prepare for interviews: you learn the same concepts, practice problem-solving, and gain confidence actually building for Apple.
To get hands-on practice with 100+ real product features, check out Educative's interview prep series Decode the Coding Interview. Our team of experts has combed through the top interview questions and incorporated them into a carefully crafted set of scenarios for you to learn from.
After each project, we’ll show you what kinds of interview problems you’ll now be able to solve using the techniques you just applied.
Happy learning!
Top comments (2)
Great article ❤️
Thanks and great job.