NVIDIA 九月底新鮮实习电面

Job Hunting Interview
, , , , , ,
1

九月初 Nvidia 校招，提供了网路连结，在线上做两题coding题以及一些 OS, Virtual Memory, Thread… 等等选择题，做完OA后，约一週收到电面邀请

3

能对上呀
就是找当前数后面第一个比该数大的数…
比如6后面第一个比6大的是34…

4

看不懂这个题目是什么意思，是返回下一个最大值吗，answer和input对不上啊

5

啊， 明白了，next greater element啊

6

是的 next greater

7

请问楼主什么岗位呢

8

我應徵的是 software engineer summer intern

9

可以请教一下楼主这题的思路吗，没想出来诶

10

我也没想出来啊~~~~~~~~~~~

11

可以用一个stack做，存放index和value组成的pair。每次一直pop直到栈顶的value比当前值大（pop出来的index的next greatest element就是当前index）。这样这个stack其实就是一个递减序列。由于pop总次数不超过总元素个数，并且只要遍历一遍，所以时间复杂度为O(n)

typedef pair<int, int> Pair;
class Interview {
  public:
  vector<int> nextGreatest(vector<int>& nums) {
    stack<Pair> s;
    vector<int> result(nums.size(), -1);
    for (int i = 0; i < nums.size(); i++) {
      while (!s.empty()) {
        Pair top = s.top();
        if (top.second < nums[i]) {
          result[top.first] = nums[i];
          s.pop();
        }
        else break;
      }
      s.push(Pair(i, nums[i]));
    }
   return result;
  }
};