Собеседование в Apple: топ-30 вопросов и ответов

			bool find_sum_of_two(vector& 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 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 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;
}
		

			class Pair{
  public:
    int first, second;
    Pair(int x, int y){
      first = x;
      second = y; 
    }
};
vector merge_intervals(vector& v) {
if(v.size() == 0) {
    return v;
  }
vector 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 v {
                  Pair(1, 5),
                  Pair(3, 7),
                  Pair(4, 6),
                  Pair(6, 8),
                  Pair(10, 12),
                  Pair(11, 15)
                  };
vector result = merge_intervals(v);
  
  for(int i = 0; i < result.size(); i++){
    cout << "[" << result[i].first << ", " << result[i].second << "] ";
  }
}
		

			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);
}
// это неориентированный граф, то есть
// если есть ребро от x к y
// то должно быть ребро от y к x
// и не должно быть ребра от узла к нему самому
// тогда максимально может быть (nodes * nodes - nodes) / 2 рёбер в этом графе
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;
		

			// оба целых числа хранятся в связных списках
// например 415 хранится в виде 5->1->4
// 32 хранится в виде 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 v1 = {1, 2, 3}; // 321
  vector 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 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));
}
		

			typedef LinkedListNode* NodePtr;
NodePtr merge_sorted(NodePtr head1, NodePtr head2) {
  
  // если оба списка пусты, итоговый тоже будет пустой
  //если пустой только один, то результатом будет второй
  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& v1, vector& v2, vector& 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 v1 = {1, 3, 5, 6};
  vector v2 = {2, 4, 6, 20, 34};
  vector 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);
}
		

			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);
  
  if(are_identical(root1, root2)) {
    cout<< "Деревья идентичны" << endl;
  } else {
    cout<< "Деревья не идентичны" << endl;
  }
}
		

			void mirror_tree(BinaryTreeNode* root) {
  if (root == nullptr) {
    return;
  }
// Делаем обратный обход бинарного дерева.
if (root->left != nullptr) {
    mirror_tree(root->left);
  }
if (root->right != nullptr) {
    mirror_tree(root->right);
  }
// Меняем местами левый и правый узел.
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 << "Отзеркаленное дерево = " << endl;
  display_level_order(root);
}
		

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

			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) {
// sentence это C-строка заканчивающаяся символом '\0'.
if (sentence == nullptr) {
    return;
  }
// Сначала мы переворачиваем всю строку
  // Теперь всё слова на нужных местах, но их буквы в обратном порядке
  // "Hello World" -> "dlroW olleH".
int len = strlen(sentence);
  str_rev(sentence, len);
// Теперь переворачиваем каждое слово.
  // "dlroW olleH" -> "World Hello"
char * start = sentence;
  char * end;
  while (true) {
    // находим начало слова.
    while (start && * start == ' ') {
      ++start;
    }
if (start == nullptr || * start == '\0') {
      break;
    }
// находим конец слова.
    end = start + 1;
    while (end && * end != '\0' && * end != ' ') {
      ++end;
    }
// переворачиваем слово.
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;
}
		

			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 << "Наибольшая сумма подотрезка: " << find_max_sum_sub_array(v, sizeof(v) / sizeof(v[0])) << endl;
    return 0;
  }
		

			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
		

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

			void print(vector<vector> 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>& output,
    vector& 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> print_all_sum(int target) {
  vector<vector> output;
  vector result;
  print_all_sum_rec(target, 0, 1, output, result);
  return output;
}
int main(int argc, const char* argv[]) {
  int n = 4;
  vector<vector> result = print_all_sum(n);
  
  print (result);
}
		

			int binary_search(vector& arr, int start, int end, int key) {
  // предполагается что все ключи уникальны.
  
  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& arr, int key) {
  return binary_search(arr, 0, arr.size()-1, key);
}
int main(int argc, char* argv[]) {
    vector 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 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;    
}
		

			// 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)
// простой однопоточный LRUCache
class LRUCache {
unordered_set 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;
}