Nvidia计算机科学面试真题

职位分类
全部
数据科学
数据分析
计算机科学
人工智能
产品经理
BQ
面试题
全部(12)
Coding(1)
System Design(0)
Algorithm(11)
Ood(0)
高频题(0)
全部(12)
Coding(1)
System Design(0)
Algorithm(11)
Ood(0)
高频题(0)
1.LeetCode 128
2.LeetCode 227
3.LeetCode 1871
4.Find a unique integer in a list of duplicates
5.Fibonacci number
6.Pow
7.nth Fibonacci
8.Code review
9.最短路径
10.Tree Travesal
11.LeetCode 772
12.shortest distance to 1
1. LeetCode 128
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

 

Example 1:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

 

Constraints:

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
2. LeetCode 227
Given a string s which represents an expression, evaluate this expression and return its value

The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 - 1].

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

 

Example 1:

Input: s = "3+2*2"
Output: 7

Example 2:

Input: s = " 3/2 "
Output: 1

Example 3:

Input: s = " 3+5 / 2 "
Output: 5

 

Constraints:

  • 1 <= s.length <= 3 * 105
  • s consists of integers and operators ('+', '-', '*', '/') separated by some number of spaces.
  • s represents a valid expression.
  • All the integers in the expression are non-negative integers in the range [0, 231 - 1].
  • The answer is guaranteed to fit in a 32-bit integer.
3. LeetCode 1871
You are given a 0-indexed binary string s and two integers minJump and maxJump. In the beginning, you are standing at index 0, which is equal to '0'. You can move from index i to index j if the following conditions are fulfilled:

  • i + minJump <= j <= min(i + maxJump, s.length - 1), and
  • s[j] == '0'.
Return true if you can reach index s.length - 1 in s, or false otherwise.

 

Example 1:

Input: s = "011010", minJump = 2, maxJump = 3
Output: true
Explanation:
In the first step, move from index 0 to index 3. 
In the second step, move from index 3 to index 5.

Example 2:

Input: s = "01101110", minJump = 2, maxJump = 3
Output: false

 

Constraints:

  • 2 <= s.length <= 105
  • s[i] is either '0' or '1'.
  • s[0] == '0'
  • 1 <= minJump <= maxJump < s.length
4. Find a unique integer in a list of duplicates
Given a list of integers where each integer, except one, appears twice. Find the one integer that only appears once.
最后希望O(n) time, O(1) space
5. Fibonacci number
实现Fibonacci number
 
会叫你一直优化到只使用兩個element的dp方式
6. Pow
Im‍‍‌‌‌‌‍‍‍‍‍‌‌‌‌‍‍‌‍‌plement a function that computes pow() in O(logN) time
7. nth Fibonacci
Implement a function that computes the nth Fibonacci element in O(logN) time
8. Code review
What is the output of the following code?
 
int main()
 
{
 
int a, b, c;
 
a = 9;
 
c = a + 1 + 1 * 0;
 
b = c++;
 
printf("a: %d, b: %d, c: %d\n", a, b, c);
 
return 0;
 
}
9. 最短路径
Find a shortest vertical path from the first row to bottom row in a 2D matrix
 
DP解决
10. Tree Travesal
Level order traversal
 
BST解决
11. LeetCode 772
Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, '+', '-', '*', '/' operators, and open '(' and closing parentheses ')'. The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 - 1].

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

 

Example 1:

Input: s = "1+1"
 Output: 2 

Example 2:

Input: s = "6-4/2" 
Output: 4 

Example 3:

Input: s = "2*(5+5*2)/3+(6/2+8)"
 Output: 21 

 

Constraints:

1 <= s <= 104

s consists of digits, '+', '-', '*', '/', '(', and ')'.

s is a valid expression.
12. shortest distance to 1
"给一个input array eg:[1,0,0,1,0,1,0,0,1]
output [0,1,1,0,1,0,1,1,0]
找每个element 他离1最近的距离"