30 самых популярных вопросов на собеседовании по программированию в Apple (с решениями)

Пройдите техническое интервью Apple с помощью вопросов о дизайне, поведении, графиках и т. Д.

Работа в Apple - мечта многих разработчиков, но подготовка к собеседованию по кодированию - непростая задача. Чтобы облегчить вам жизнь, мы собрали 30 самых популярных вопросов для собеседований, которые вы можете ожидать во время технического собеседования с Apple.

Мы начнем с обзора процесса собеседования по разработке программного обеспечения, а затем разберем основные вопросы собеседования Apple с подробными кодовыми решениями и мерами сложности. Мы предложим свои решения на C ++.

Краткий обзор этого руководства:

• Обзор процесса собеседования в Apple
• Вопросы о массивах и графиках
• Вопросы о связанных списках
• Вопросы о деревьях
• Вопросы о строках
• Вопросы по динамическому программированию
• Математика, статистика и возврат
• Поисковые и дизайнерские вопросы
• Поведенческие вопросы
• Советы по подготовке к собеседованию

Обзор процесса собеседования в Apple

Процесс собеседования с инженером-программистом в Apple отличается от других крупных технологических компаний количеством собеседований, которые они проводят, и процессом на месте.

Если вас попросят пройти собеседование в Apple, процесс обычно выглядит следующим образом:

• Предварительная проверка с рекрутером: от отправки резюме до первого контакта пройдет около недели. Рекрутер обычно связывается через LinkedIn или по электронной почте, чтобы назначить время для телефонного звонка. Этого экрана телефона хватит на 15–30 минут, и вопросы не будут излишне техническими. Вы могли бы ожидать таких вопросов, как Почему вы хотите работать в Apple? или Какой ваш любимый продукт или услуга Apple?
• Техническое собеседование по телефону. Обычно на неделю позже они назначают ваше следующее техническое собеседование по телефону. Будет один или два технических экрана телефона с вопросами о вашем резюме и вопросом кодирования о структурах данных и алгоритмах. Интервью по кодированию длится примерно 45–60 минут, из них 30 минут на выполнение задания.
• Собеседование на месте: собеседование на месте продлится около шести часов. Вы встретитесь с 8–12 сотрудниками Apple, и собеседования будут включать в себя вопросы поведения, знания предметной области и проблемы программирования. Каждое собеседование длится от 45 минут до часа, и вам будут предложены технические проблемы. Поведенческие вопросы также очень важны для менеджеров по найму.

Структуры данных, которые вы должны знать: массивы, связанные списки, стеки, очереди, деревья, графики, кучи, хеш-наборы, хеш-карты.

Алгоритмы, которые вам следует знать: поиск в глубину, поиск в ширину, двоичный поиск, быстрая сортировка, сортировка слиянием, динамическое программирование, разделяй и властвуй.

Вопросы о массивах и графиках

Определите сумму трех целых чисел

Цель этого упражнения - определить, равна ли сумма трех целых чисел заданному значению.

Постановка задачи. Учитывая массив целых чисел и значение, определите, есть ли в массиве какие-либо три целых числа, сумма которых равна заданному значению.

Рассмотрим этот массив и целевые суммы:

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) в оставшемся массиве так, чтобы required_sum - e было a + b.

Начните с первого элемента e в массиве и попытайтесь найти такую ​​пару (a, b) в оставшемся массиве (то есть от A[i + 1] до A[n - 1]), которая удовлетворяет условию: a+b = required_sum - e. Если мы найдем пару, значит, мы нашли решение: a, b и e. Теперь мы можем остановить итерацию.

В противном случае мы повторяем вышеуказанные шаги для всех элементов e с index i = 1 по n - 3, пока не найдем пару, удовлетворяющую условию.

Сложность выполнения: квадратичный, 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 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;
}

Мы используем обход в глубину и создаем копию каждого узла при обходе графа. Используйте хеш-таблицу для хранения каждого завершенного узла, чтобы мы не пересматривали узлы, существующие в этой хеш-таблице. Ключ хэш-таблицы будет узлом в исходном графе, а его значением будет соответствующий узел в клонированном графе.

Сложность выполнения: линейный, 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->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));
}

Чтобы лучше понять это, давайте рассмотрим пример. Допустим, мы хотим сложить целые числа 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.

Сравните значения первых двух узлов и сделайте узел с меньшим значением головным узлом объединенного связанного списка. В этом примере это 4 из head1. Поскольку это первый и единственный узел в объединенном списке, он будет хвостом. Затем продвиньтесь head1 на один шаг вперед.

Сложность выполнения: линейный, O (m + n), где m и n - длины наших связанных списков

Сложность памяти: константа, O (1)

Вопросы о деревьях

Определите, идентичны ли два двоичных дерева

Цель этого упражнения - сравнить два бинарных дерева, чтобы определить, идентичны они или нет.

Постановка задачи: вам даны корни двух двоичных деревьев, и вы должны определить, идентичны ли эти деревья. Идентичные деревья имеют одинаковую структуру и данные на каждом узле.

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

Эту проблему можно решить рекурсивно. Базовый случай рекурсии для этого решения - если два сравниваемых узла равны нулю или один из них равен нулю.

Два дерева A и B идентичны, если:

• Данные об их корнях совпадают или оба корня равны нулю.
• Левое поддерево A идентично левому поддереву B
• Правое поддерево A идентично правому поддереву B

Используйте обход в глубину одновременно для обоих деревьев и продолжайте сравнивать данные на каждом уровне, чтобы решить эту проблему.

Сложность выполнения: линейный, O (n)

Сложность памяти: O (h) в лучшем случае или будет O (logn ) для сбалансированного дерева и в худшем случае может быть O (n).

Зеркальное отражение узлов двоичного дерева

Цель этого упражнения - использовать обход в глубину и восходящее зеркальное отображение для зеркалирования узлов двоичного дерева.

Формулировка проблемы: вам дан корневой узел двоичного дерева, и вы должны поменять местами left и right дочерние элементы для каждого узла.

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) в худшем случае.

Вопросы о строках

Найти все подстроки палиндрома

Цель этого упражнения - найти подстроки палиндрома заданной строки.

Постановка задачи. Для данной строки найдите все не однобуквенные подстроки, которые являются палиндромами. Дана строка "aabbbaa".

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

Для каждой буквы во входной строке начните расширяться влево и вправо, проверяя палиндромы четной и нечетной длины. Переходите к следующей букве, если мы знаем, что палиндрома там не существует.

Раскладываем по одному символу влево и вправо и сравниваем. Если оба равны, мы распечатываем подстроку палиндрома.

Сложность выполнения: многочлен, O (n²)

Сложность памяти: константа, O (1)

Обратные слова в предложении

Цель этого упражнения - перевернуть слова в заданной строке. Обязательно обратите внимание на то, как слова разделяются пробелами.

Постановка проблемы: измените порядок слов в данном предложении (массив символов). Приведены слова "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;
}

Есть два шага к этой проблеме. Сначала переверните струну. Затем переместите строку и переверните каждое слово на месте.

Сложность выполнения: линейный, O (n)

Сложность памяти: постоянная, O (1)

Вопросы по динамическому программированию

Подмассив наибольшей суммы

Цель этого упражнения - использовать ваши навыки динамического программирования и алгоритм Кадане, чтобы найти подмассив с наибольшей суммой.

Постановка проблемы. Найдите подмассив с наибольшей суммой. В приведенном ниже массиве подмассив наибольших сумм начинается с индекса 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;
  }

Мы используем алгоритм Кадане, чтобы решить эту проблему. Основная идея этого алгоритма состоит в том, чтобы сканировать весь массив и в каждой позиции находить максимальную сумму подмассива, заканчивающегося там. Это достигается за счет сохранения current_max для текущего индекса массива и global_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.

мощность (2,5) = 32

мощность (3,4) = 81

мощность (1,5,3) = 3,375

мощность (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)

Найдите все комбинации сумм

Цель этого упражнения - использовать свои навыки поиска с возвратом, чтобы найти все комбинации сумм.

Постановка задачи: для положительного целого числа target выведите все возможные комбинации положительных целых чисел, которые складываются с числом target.

Вывод будет в форме списка списков или массива массивов, поскольку каждый элемент в списке будет другим списком, содержащим возможную комбинацию сумм. Например, если вам дан ввод 5, это возможные комбинации сумм:

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

Мы рекурсивно перебираем все возможные комбинации сумм и, когда текущая сумма равна цели, выводим эту комбинацию. Алгоритм рекурсивно проверяет все числа, суммирующие target.

В каждом рекурсивном вызове есть цикл for, который выполняется от start до target, где start изначально равно 1. current_sum - это переменная, которая увеличивается при каждом рекурсивном вызове.

Каждый раз, когда значение добавляется в current_sum, оно также добавляется в список result. Когда current_sum равно target, мы знаем, что список result содержит возможную комбинацию для target, и этот список затем добавляется к окончательному списку output. Вот пример кода:

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

Перед каждым рекурсивным вызовом в result добавляется элемент. Однако после каждого вызова этот элемент также удаляется из списка для сброса списка.

Сложность выполнения: экспоненциальная, 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;    
}

Решение похоже на двоичный поиск с некоторыми изменениями. Обратите внимание, что по крайней мере половина массива всегда сортируется. Если число n находится в пределах отсортированной половины массива, то наша проблема заключается в базовом двоичном поиске. В противном случае отбросьте отсортированную половину и изучите неотсортированную половину.

Сложность выполнения: логарифмический, O (logn)

Сложность памяти: логарифмический, O (logn)

Реализовать кеш LRU

Целью этого упражнения по проектированию является реализация общепринятой стратегии кэширования Least Recently Used (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 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;
}

Кэширование - это метод хранения данных в более быстром хранилище (обычно в ОЗУ) для более быстрого обслуживания будущих запросов. Кэш-хранилища обычно недостаточно велики для хранения полного набора данных. Нам нужно удалить данные из кеша, когда он заполнится.

LRU - очень простой и часто используемый алгоритм для этого процесса. Мы удаляем самые старые данные из кеша, чтобы разместить новые.

Для реализации кэша LRU мы используем две структуры данных: хэш-карту и двусвязный список. Двусвязный список помогает поддерживать порядок выселения, а хэш-карта помогает при поиске кэшированных ключей O (1) O (1). Вот алгоритм:

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

Примечание. Двусвязный список предназначен для отслеживания элементов, к которым осуществлялся последний доступ. Элемент в конце двусвязного списка - это элемент, к которому последний раз осуществлялся доступ.

Все вновь вставленные элементы переходят в хвост, а любой доступный элемент - в хвост.

Сложность выполнения:

• get (hashset): Константа, O (1)
• set (hashset): Константа, O (1)
• Удаление в заголовке при добавлении нового элемента: Константа, O (1)
• Искать удаление и добавление в хвост: Linear, O (n)

Сложность памяти: линейная, O (n), где n - размер кеша.

Поведенческие вопросы

Теперь, когда мы обсудили основные технические вопросы, давайте рассмотрим наиболее распространенные вопросы поведенческого собеседования, которые вы можете ожидать на собеседовании с Apple, которые, возможно, не менее важны для вашего успеха.

Как вы увидите из этого списка, Apple хочет понять, какой вы мыслитель, как вы справляетесь с конфликтами и какие инвестиции вы приносите.

1. Какие были твои лучшие и худшие дни за последние четыре года?
2. Какой ваш любимый продукт или услуга Apple и почему?
3. Опишите достижение, которым вы особенно гордитесь.
4. Вы когда-нибудь спорили со своим руководителем по поводу решения на работе? Что случилось? Как вы справились с ситуацией?
5. Как вы преодолели неудачу? Что вы узнали из этого?
6. Почему вы хотите работать в Apple?
7. Что вы в первую очередь замечаете, заходя в магазин Apple?
8. Опишите самую сложную проблему разработки программного обеспечения, с которой вы столкнулись. Как вы ее решили?
9. Если вы соглашаетесь на работу в Apple, чего вам больше всего будет не хватать в своей нынешней должности? Что вы будете упускать меньше всего?
10. Предпринимаете ли вы какие-либо шаги для повышения своих навыков вне работы?
11. Опишите время, когда вы сделали все возможное для клиента.
12. Объясните 8-летнему ребенку, что такое модем / маршрутизатор и его функции.
13. Как эта роль вписывается в вашу пятилетнюю карьеру или жизненный план?
14. Если бы мы наняли вас, над чем бы вы хотели работать?
15. Как бы вы протестировали свое любимое приложение?
16. Если бы человек обратился в техподдержку, но у него был динозавр или устаревший продукт, как бы вы с этим справились?

Совет. Независимо от вопроса или должности, всегда рекомендуется использовать метод STAR для ответов на вопросы собеседования, основанные на поведении:

• Опишите ситуацию.
• Опишите задачу.
• Опишите действия, предпринятые для выполнения задачи.
• Объясните достигнутые результаты.

Советы по подготовке к интервью

Подготовка к собеседованию требует кучу времени и терпения, и не существует золотого билета для взлома собеседования по кодированию. Но есть некоторые передовые методы, которые мы усвоили за эти годы.

• Практикуйтесь с помощью различных инструментов. Рекомендуется сочетать практику с использованием доски, онлайн-курсы и имитационные собеседования, чтобы максимально эффективно использовать свое время. Крайне важно, чтобы вы тренировались говорить вслух при решении задач, чтобы вы могли использовать различные инструменты для практики.
• Составьте учебный план. Также рекомендуется составить подробный план подготовки на срок от 3 до 6 месяцев. Таким образом, у вас будет структура, которой нужно следовать, и вы не упустите важные концепции.
• Избегайте заучивания наизусть. Также рекомендуется избегать заучивания вопросов. Вместо этого практикуйтесь, создавая реальные продукты, которые Apple могла бы использовать. Это идеальный способ подготовиться к собеседованию: вы изучаете одни и те же концепции, практикуетесь в решении проблем и обретаете уверенность, которая действительно укрепляет Apple.

Спасибо за чтение.

Удачного интервью!