Ace苹果技术面试通过设计，行为，图表问题等等

> Image by author

在Apple工作是许多开发人员的梦想 - 但准备变成面试并不容易完成任务。为了使您的生活更轻松，我们编制了在与Apple技术采访中可以期待的前30的编程问题。

我们首先概述软件工程的面试过程，然后通过深入的代码解决方案和复杂性措施分解顶级苹果面试问题。我们将在C ++中提供我们的解决方案。

本指南一目了然：

Apple面试过程概述数组和图表问题链接列表问题树木问题字符串问题动态编程问题数学，统计和回溯搜索和设计问题行为问题准备面试的提示Apple面试过程概述

由于他们持有的访谈数量及其现场流程，Apple的软件工程师面试过程与其他较大的技术公司不同。

如果您被要求在Apple面试，此过程通常如此如此：

预招员预算：恢复提交将需要一周时间，以便首次联系。招聘人员通常会在LinkedIn或电子邮件中伸出来设置一个电话的时间。这款手机屏幕将持续15-30分钟，问题不会过于技术。你可以期待你为什么要为苹果工作的问题？或者您最喜欢的Apple产品或服务是什么？电话技术面试：通常一周后，他们将安排下一个技术面试。将有一个或两个技术屏幕，有关您的简历问题以及关于数据结构和算法的编码问题。编码访谈约45-60分钟 - 30分钟才能完成挑战。现场面试：现场面试将持续大约六个小时。您将遇到8-12名苹果员工，面试将是行为，领域知识和编码挑战的混合。每次面试约45分钟到一个小时，你将与技术问题开始。行为问题对招聘经理来说也非常重要。

您应该知道的数据结构：数组，链接列表，栈，队列，树，图，堆，哈希集合，哈希图表

您应该知道的算法：深度优先搜索，广度优先搜索，二进制搜索，Quicksoror，Mergeort，动态编程。

数组和图表问题确定三个整数的总和

本练习的目标是确定三个整数的总和是否等于给定值。

问题陈述：给定阵列的整数和值，确定数组中是否有三个整数，其总和等于给定值。

考虑此数组和目标uM：

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;}

在此解决方案中，我们对数组进行排序。然后，修复一个元素E并在剩余阵列中找到一对（a，b），以便需要_sum - e是a + b。

从阵列中的第一个元素E开始，并尝试在满足条件的剩余阵列中（即[i + 1]到[n-1]）中找到这样的对（a，b），该条件是：a + b= Resegand_sum - e。如果我们找到这对，我们已经找到了解决方案：A，B和E。现在我们可以停止迭代。

否则，我们对索引i = 1到n - 3的所有元素e重复上述步骤，直到我们找到符合条件的一对。

运行时复杂性：二次，O（n²）

记忆复杂性：常数，o（1）

合并重叠间隔

本练习的目标是合并给定列表的所有重叠间隔，以生成仅具有互斥间隔的列表。

问题陈述：将间隔对的数组（列表）为输入，其中每个间隔都有一个开始和结束时间戳，通过启动时间戳进行排序。合并重叠间隔并返回新的输出阵列。

考虑下面的输入数组。间隔（1,5），（3,7），（4,6），（6,8）是重叠的，因此它们应该合并到一个间隔（1,8）。类似地，间隔（10,12）和（12,15）也是重叠的并且应该合并为（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 << "] ";  }}

用线性扫描算法可以解决这个问题。给出了输入间隔列表，我们将在输出列表中保持合并的间隔。对于输入列表中的每个间隔：

如果输入间隔与输出列表中的最后一个间隔重叠，请合并这两个间隔并使用合并的间隔更新输出列表的最后一个间隔。否则，将输入间隔添加到输出列表中。

运行时复杂性：线性，o（n）

内存复杂性：线性，o（n）

克隆一个定向的图表

本练习的目标是克隆定向图，并使用散列和深度首先遍历打印输出图。

问题陈述：给定针向图的根节点，通过创建深度副本来克隆图形。克隆图将具有相同的顶点和边缘。

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 graphvoid 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;}

我们使用深度首先遍历并在遍历图的同时创建每个节点的副本。使用Hashtable来存储每个已完成的节点，以便我们不会重新寄出那个哈希表中存在的节点。Hashtable键将是原始图中的节点，其值将是克隆图中的相应节点。

运行时复杂性：线性，o（n）

内存复杂性：对数，O（n），其中n是图中的顶点数。

链接列表问题加两个整数

本练习的目标是添加两个链接列表的两个整数。

问题陈述：给出两个链接列表的头指针，其中每个链接列表表示整数号码（即每个节点是数字）。添加它们并返回新链接列表。

// assuming both integers are stored in a linked list// e.g. 415 is stored as 5->1->4// 32 is stored as 2->3LinkedListNode* 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));}

要了解更好，让我们考虑一个例子。假设我们想加整数9901和237. 此加法的结果将是10138。

整数存储在链接列表中反转以使其更容易。该数字最有效的数字是链表的最后一个元素。要开始添加，我们从两个链接列表的头部开始。

在每次迭代时，我们添加了两个列表的当前数字，并在结果链接列表的尾部插入新节点。我们还需要维持每一步的携带。

我们为所有连接列表中的所有数字都这样做。如果其中一个链接列表即将结束，我们将继续使用其他链接列表。一旦完成了两个链接列表并且没有添加携带，算法将终止。

运行时复杂性：线性，o（n）

内存复杂性：线性，o（n）

合并两个排序链接列表

本练习的目标是合并两个排序的链接列表。

问题陈述：给定两个排序的链接列表，合并它们，以便也排序生成的链接列表。

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);}

在合并的链接列表中维护一个头部和尾部指针。通过比较两个链接列表的第一个节点来选择合并链接列表的头部。

对于所有后续节点，请选择较小的电流节点并将其链接到合并列表的尾部。将该列表的当前指针移动到前一步。

如果只有其中一个列表中仍有一些元素，则将此剩余列表链接到合并列表的尾部。最初，合并的链接列表为null。

比较前两个节点的值，并使用合并链表的Head节点的较小值进行节点。在这个例子中，它是来自head1的4。由于它是合并列表中的第一个也是唯一节点，因此它将是尾部。然后向前移动一个阶梯。

运行时复杂性：线性，o（m + n），其中m和n是我们链接列表的长度

记忆复杂性：常数，o（1）

树问题确定两个二进制树是否相同

本练习的目标是比较两个二元树以确定它们是否相同。

问题陈述：给出了两个二叉树的根源，并且必须确定这些树是否相同。相同的树木在每个节点处具有相同的布局和数据。

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;  }}

这个问题可以递归解决。对该解决方案的递归的基本情况是如果两个比较节点为NULL，或者其中一个是NULL。

A和B的两棵树是相同的，如果：

其根部的数据是相同的，或者两个根都是nullA的左子树与B的左子树相同A的右子树与B的右子树相同

同时在两棵树上使用深度第一遍历并继续将数据进行比较，以解决此问题。

运行时复杂性：线性，o（n）

内存复杂性：O（h）在最佳情况下，或者它将用于平衡树的O（logn），并且在最坏的情况下可以是O（n）。

镜像二叉树节点

本练习的目标是使用深度 - 首先遍历和自下而上镜像来镜像二叉树的节点。

问题陈述：您给出了二进制树的根节点，并且必须为每个节点交换左侧和右侧。

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);}

我们做了二叉树的遍历遍历。对于每个节点，将其左子子与其合适的孩子交换。我们在树上使用DFS - 以便在从节点返回之前，已访问其所有子项（并镜像）。

运行时复杂性：线性，o（n）

内存复杂性：最坏情况下的线性，o（n）

字符串问题查找所有回文的子串

本练习的目标是找到给定字符串的回文子字符串。

问题陈述：给定字符串，查找是polindromes的所有非单字母子字符串。给定的字符串是“aabbaa”。

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;}

对于输入字符串中的每个字母，在检查均匀和奇数的Palindromes时开始向左和向右扩展。如果我们知道那里不存在，请转到下一个信件。

我们将一个字符扩展到左右并比较。如果两者都相等，我们打印出回文的子字符串。

运行时复杂性：多项式，o（n²）

记忆复杂性：常数，o（1）

句子中的逆词

本练习的目标是在给定字符串中扭转单词。请务必记录单词的单词是如何用空格分隔的。

问题陈述：在给定句子中反转单词的顺序（字符数组）。给出的话是“你好世界！”。

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;}

这个问题有两个步骤。首先，反转字符串。然后，遍历串并将每个单词反转到位。

运行时复杂性：线性，o（n）

记忆复杂性：常数，o（1）

动态编程问题最大的Sum Subarray

本练习的目标是使用您的动态编程技巧和卡达的算法来找到最大的Sum array。

问题陈述：找到最大的Sum Subarray。在下面的数组中，最大和子阵列在索引3开始，并以6结束，最大的总和为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;  }

我们使用卡达的算法来解决这个问题。该算法的基本思想是扫描整个阵列，并在每个位置找到结束时的子阵列的最大总和。这是通过保持当前数组索引和全局_max的Current_Max来实现的。

该算法如下：

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

运行时复杂性：线性，o（n）

记忆复杂性：常数，o（1）

数学和统计数据数量

本练习的目标是使用鸿沟并征服并编写计算升高到数字的幂的函数。

问题陈述：给出双重，x和整数n，写一个函数来计算x升到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;  }}

我们可以使用鸿沟和征服方法最有效地解决这个问题。在分割步骤中，我们将n递归除以2，直到我们到达基本情况。

在结合步骤中，我们得到了子问题的结果r，并使用下面的两个规则计算当前问题的结果：

如果n是偶数，结果是r * r（其中r是子问题的结果）如果n是奇数，结果是x * r * r（其中r是子问题的结果）

运行时复杂性：对数，o（logn）

内存复杂性：对数，O（logn）

查找所有总和组合

本练习的目标是使用您的回溯技能来查找所有金额组合。

问题陈述：给定正整数，目标，打印添加到目标号码的正整数的所有可能组合。

输出将以列表列表或数组数组的形式，因为列表中的每个元素将是包含可能总和组合的另一个列表。例如，如果您提供输入5，则这些是可能的总和组合：

1, 42, 31, 1, 31, 2, 21, 1, 1, 21, 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);}

我们递归地通过所有可能的总和组合，并且当运行和等于目标时，打印该组合。该算法将递归地检查可以总结到目标的所有数字。

在每个递归调用中，有一个for循环从头到目标运行，其中开始最初1. current_sum是递增每个递归调用的变量。

每次将值添加到Current_sum时，它也会添加到结果列表中。每当Current_Sum等于目标时，我们都知道结果列表包含可能的目标组合，然后将此列表附加到最终输出列表。这是一些示例代码：

Base condition of recursion: if current_sum equals target  print the output contents

在每个递归调用之前，添加一个元素以产生结果。但是，在每个调用之后，此元素也会从列表中删除以重置列表。

运行时复杂性：指数，o²

内存复杂性：线性，o（n）

搜索和设计问题在旋转数组中搜索

本练习的目标是在排序阵列中搜索旋转阵列。尝试使用二进制搜索解决问题。

问题陈述：搜索排序阵列中的给定数字，具有唯一的元素，该元素已被一些任意数字旋转，假设数组不包含重复项。返回-1如果数字不存在。

以下是旋转前的原始数组：

在此阵列上执行旋转六次后，它会更改为：

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;    }

解决方案就像一个有一些修改的二进制搜索。请注意，总是排序的至少一半数组。如果Number n位于数组的排序部分内，则我们的问题是基本的二进制搜索。否则，丢弃排序的一半并检查未分类的一半。

运行时复杂性：对数，o（logn）

内存复杂性：对数，O（logn）

实现LRU缓存

这种设计练习的目标是使用双链列表和散列来实现最近使用最近使用的（LRU），共同的缓存策略。

问题声明：最近使用最少（LRU）定义了策略，以便在缓存已满时为新元素逐个授予新元素的策略，这意味着它首先丢弃最少使用的项目。

占据具有四个元素的容量的缓存示例。我们缓存元素1,2,3和4.下面的图表表示所有四个元素的首次访问后的缓存状态：

我们现在需要缓存另一个元素5。

让我们看看再次访问2时会发生什么。现在3成为从缓存中逐行驱逐的下一个。

// 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 LRUCacheclass LRUCache {unordered_set<int> cache;// each entry in linked list is the value of the element  LinkedList cache_vals;  int capacity; // total capacitypublic: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;}

缓存是一种在更快的存储（通常RAM）中存储数据以更快地提供未来请求的技术。缓存存储通常不足以存储完整的数据集。我们需要在变得满满时从缓存中撤消数据。

LRU是一个非常简单常用的算法，用于此过程。我们从缓存中逐出最旧的数据以适应新数据。

要实现LRU缓存，我们使用两个数据结构：HashMap和双链接列表。双重链接列表有助于维护驱逐秩序，并且HASHMAP有助于使用o（1）o（1）查找缓存键。这是算法：

If the element exists in hashmap    move the accessed element to the tail of the linked listOtherwise,    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 hashmapGet from Cache and Return

注意：双链接列表用于跟踪最近访问的元素。双重链接列表尾部的元素是最近访问的元素。

所有新插入的元素都转到尾部，并且访问的任何元素都进入尾部。

运行时复杂性：

GET（HASHSET）：常数，o（1）SET（HASHSET）：常数，o（1）添加新元素时删除头部：常量，o（1）搜索删除和添加到尾部：线性，O（n）

内存复杂性：线性，o（n），其中n是缓存的大小

行为面试问题

现在我们已经讨论了最高的技术问题，让我们看看你可以在苹果面试中获得最常见的行为面试问题，这可以对您的成功表示重要。

正如您从这个列表中看到的那样，Apple希望了解您是什么样的思想家，您如何处理冲突，以及您带来的投资。

过去四年中最好和最糟糕的日子是什么？您最喜欢的Apple产品或服务是什么？为什么？描述你特别为其感到骄傲的成就。您是否对您的经理同意了解工作的决定？发生了什么？你是如何处理这种情况的？你是如何克服失败的？你从中学到了什么？你为什么要为苹果工作？走进Apple商店时，你注意到的第一件事是什么？描述您面临的最具挑战性的软件开发问题。你是怎么解决的？如果您在Apple接受工作，您最想念您当前的角色？你会错过什么？您是否采取任何措施来提高工作之外的技能？描述您以上的时间和超越客户。解释为8岁的调制解调器/路由器是其功能。这种角色如何适应您的五年职业或生命计划？如果我们雇用了你，你想打算什么？您如何测试您最喜欢的应用程序？如果一个人呼吁技术支持但有恐龙或遗留产品，你会如何处理它？

提示：无论问题或位置如何，始终建议使用星形方法回答其行为的面试问题：

描述情况。描述任务。描述所采取的行动来处理任务。解释您实现的结果。准备面试的提示

面试练习需要大量的时间和耐心，并且没有万能钥匙破解编码面试。但是多年来有一些最好的做法。

用不同的工具练习。结合白板实践，在线课程和模拟访谈是一个好主意，以充分利用您的时间。在解决问题时练习大声说话是至关重要的，因此您可以使用不同类型的工具来获得练习。创建一个学习计划。还建议在3-6个月之间为任何地方创建详细的准备计划。这样，您有一个结构要遵循并避免缺少基本概念。避免判决记忆。还建议避免纪念问题。相反，通过建立苹果可能使用的真实产品来练习。这是准备面试的理想方式：您学习相同的概念，练习解决问题，并获得苹果的建立建设的信心。

谢谢阅读。

祝你好运！

(本文由闻数起舞翻译自Mike Skaife的文章《Top 30 Apple Coding Interview Questions (With Solutions)》，转载请注明出处，原文链接：)