txy

记一次腾讯实习面试

面试

• c++11 智能指针

• 进程和线程切换的区别
  切换进程空间，TLB失效

• tcp三次握手协商内容

• brk和mmap

  #include <unistd.h>
  #include <stdio.h>
  
  void main()
  {
          char *p = sbrk(0);
          p[4096] = 1; // segment fault
  }

• 引用和指针的区别

• epoll/poll/select的区别 （IO多路复用）
  https://segmentfault.com/a/1190000003063859

  笔试

  找到数组中某一个元素第一次出现的位置，没有出现返回-1

  #include <iostream>
  #include <vector>
  
  using namespace std;
  
  /**
   * find first location of an element in an array, return -1 if not found;
   * 
   */
  int find(vector<int>& nums, int target, int start, int end) {
      int len = end - start;
      if (len <= 0) return -1;
      int mid = start + len / 2;
      if ( nums[mid] == target ) {
          int res = mid;
          for ( int i = mid - 1; i >= start ; i -- ) {
              if (nums[i] == target) res = i;
          }
          return res;
      } else if ( nums[mid] > target ) {
          return find(nums, target, start , mid - 1);
      } else {
          return find(nums, target, mid + 1 , end);
      }
  }
  
  int main() {
      vector<int> nums = {0, 1, 1, 1, 3, 5, 6, 6};
      std::cout << find(nums, 1, 0, nums.size() - 1) << "\n";
  }

射箭游戏，一次分数在0-10之间，输出10次射击最后分数为90的所有结果

#include <iostream>
#include <vector>

using namespace std;

/**
 * find all possible combination of 0 ~ 10 with specific size to get specific score 
 *  
 */

void calculate(int score, int size, vector<vector<int>>& result, vector<int>& cur) {
    if ( size == 1) {
        if ( score <= 10 ) {
            vector<int> v(cur);
            v.push_back(score);
            result.push_back(v);
        }
    } else {
        for ( int i = 0 ; i <= 10 ; i ++ ) {
            if ( i > score ) break;
            cur.push_back(i);
            calculate(score - i , size - 1, result , cur);
            cur.pop_back();
        }
    }
    return;
}


int main() {
    vector<vector<int>> result;
    vector<int> cur;
    calculate(90, 10, result, cur);
    for ( auto& res: result) {
        for ( auto& elem : res) {
            std::cout << elem << " ";
        }
        std::cout << "\n";
    }
}

逆转单向链表最后k个元素

#include <iostream>
#include <deque>

using namespace std;

/**
 * reverse last k elements of a linked list
 *  
 */

struct LinkedList {
    LinkedList* next;
    int val;
};

void reverse(LinkedList* head, int size, deque<LinkedList*>& queue) {
    while (head != nullptr ) {
        if (queue.size() == size + 1) {
            queue.pop_front();
        }
        queue.push_back(head);
        head = head->next;
    }
    auto node = queue.front();
    queue.pop_front();
    for ( int i = size - 1 ; i >= 0 ; i -- ) {
        auto elem = queue.back();
        node->next = elem;
        node = elem;
        elem->next = nullptr;
        queue.pop_back();
    }
}

int main() {
    LinkedList node1 = {nullptr, 1};
    LinkedList node2 = {nullptr, 2};
    LinkedList node3 = {nullptr, 3};
    LinkedList node4 = {nullptr, 4};
    LinkedList node5 = {nullptr, 5};
    LinkedList node6 = {nullptr, 6};
    LinkedList node7 = {nullptr, 7};
    node1.next = &node2;
    node2.next = &node3;
    node3.next = &node4;
    node4.next = &node5;
    node5.next = &node6;
    node6.next = &node7;
    node7.next = nullptr;
    deque<LinkedList*> d; 
    reverse(&node1, 4, d);
    LinkedList* head = &node1;
    while ( head != nullptr) {
        std::cout << head ->val << " ";
        head = head -> next;
    }
    std::cout << "\n";
}