# 亚麻 SDE1 西雅图面经

OA 2 小时

Given a list of positive integers nums and an int target, return indices of the two numbers such that they add up to a target - 30.

Conditions:

You will pick exactly 2 numbers.
You cannot pick the same element twice.
If you have muliple pairs, select the pair with the largest number.
Example 1:

Input: nums = [1, 10, 25, 35, 60], target = 90
Output: [2, 3]
Explanation:
nums + nums = 25 + 35 = 60 = 90 - 30
Example 2:

Input: nums = [20, 50, 40, 25, 30, 10], target = 90
Output: [1, 5]
Explanation:
nums + nums = 20 + 40 = 60 = 90 - 30
nums + nums = 50 + 10 = 60 = 90 - 30
You should return the pair with the largest number.

``````public class Main {

public static List<Integer> findPair(List<Integer> nums, int target) {
target -= 30;
Map<Integer, Integer> map = new HashMap<>();
List<Integer> result = Arrays.asList(-1, -1);
int largest = 0;
for (int i = 0; i < nums.size(); i++) {
int complement = target - nums.get(i);
if ((nums.get(i) > largest || complement > largest) && map.containsKey(complement)) {
result.set(0, map.get(complement));
result.set(1, i);
largest = Math.max(nums.get(i), complement);
}
map.put(nums.get(i), i);
}
return result;
}

public static void main(String[] args) {
test(Arrays.asList(1, 10, 25, 35, 60), 90);
test(Arrays.asList(20, 50, 40, 25, 30, 10), 90);
test(Arrays.asList(5, 55, 40, 20, 30, 30), 90);
}

private static void test(List<Integer> nums, int target) {
System.out.println(findPair(nums, target));
}
}
``````

Time complexity: O(n).
Space complexity: O(n).

Related problems:

Onsite 4 轮 每轮 45 分钟

• BQ
• Return the root of the subtree whose sum is equal to given target (including the root value)

• BQ
• Write a method that does find a file in given directory
• Follow-up: search for file in all subdirectories
• search for file with size greater than given size
• search for a file with variable number of constraints(like size>80kb, date created =“08-20-2019”…etc)

• BQ
• Have you ever not delivered the work promised?
• Have you ever improved anything thinking from the consumer’s perspective? Was this delivered? What was the consumer feedback?
• Have you ever had a conflict with your manager? How did you resolve it?
• Design hangman with a given helper function that returns the array of indices for given character, return the string if guessed properly
`public String guessWord(int length, int numWrongGuesses)`
`pubic int[] helper(char c)`
Follow-up: how can we improve it? My ideas-(maintain a hashmap of <character,numOfWords> start by guessing letters with max count, but this approach occupies more space. We can also use Trie in some manner to make this easy)

• CellPhone Billing System
• Follow-up: Object Orieneted Design

Notes:

• There was a 15 mins break after 2 rounds
• I was being interviewed for SDE2 but had no experience on system design. So they said they would interview for SDE2 and consider for SDE1 based on how the interview goes for system design.