# 巨硬 OTS 7月

7月5日（周五），linkedin上HR联系说7月21日的hiring event Azure identity （两个星期不到？？）当时就说最后第二周周二前完成，因为他们review要大概一周时间。。。

1. reverse word in-place。 就是要 “how are you!" => “you! are how”。
2. 去除n个字符后组成的最小数字。 “4305123” n=4 输出应该是 “012”。
3. deep copy graph 没时间做。。。给的假设 Node { Node p1, Node p2 }

3题60分钟感觉还是有点紧张的。特别是editor 没有自动缩进，没有变量名提示，基本上都是手打。

Given a string what is the minimum number of adjacent swaps required to convert a string in palindrome. If not possible return -1.

example
Input:
asflkj
aabb
Output:
3
-1
2

Please Provide a solution faster than O(n^2)

Lexicographically smallest string formed by removing at most one character

input: 1234
output:
1
2
3
4

Print Unique Paths without backtracking

Given an NxM matrix of integers, find all paths from first cell to the last cell. You can only move down or to the right from the current cell (no backtracking). Also call out the time complexity of your solution and ways to optimise it further. E.g.

{1 2 3}
{4 5 6}
{7 8 9}

Output should be:

1,2,3,6,9
1,2,5,6,9
1,2,5,8,9
1,4,5,6,9
1,4,5,8,9
1,4,7,8,9

Alexa is given n piles of equal or unequal heights. In one step, Alexa can remove any number of boxes from the pile which has the maximum height and try to make it equal to the one which is just lower than the maximum height of the stack. Determine the minimum number of steps required to make all of the piles equal in height.

Example:

Input: piles = [5, 2, 1]
Output: 3
Explanation:
Step 1: reducing 5 -> 2 [2, 2, 1]
Step 2: reducing 2 -> 1 [2, 1, 1]
Step 3: reducing 2 -> 1 [1, 1, 1]
So final number of steps required is 3.

Given two lists `A` and `B` such that `A[i]` and `B[i]` form an undirected edge of the graph and number of nodes `N` , the function should return the maximum edge count present among all the connected components of the graph.

``````def max_roads(A, B, N):
# Code goes here
``````

Example 1:

``````Input: A = [1, 2, 3, 3], B = [2, 3, 1, 4], N = 4
Output: 4
Explanation:
The function should return 4 as the maximum conncted component has the edges (2, 1), (2, 3), (3, 1), (3, 4).
``````

Example 2:

``````Input: A = [1, 2, 4, 5], B = [2, 3, 5, 6], N = 6
Output: 2
Explanation:
The function should return 2 as the maximum conncted component has the edges (2, 1), (2, 3).
``````

Return the maximum sum formed by any 2 numbers that form the same digit sum in a given list of numbers. Return -1 if no 2 numbers have the same digit sum.

Example 1:

Input A: [51, 71, 17, 42, 33, 44, 24, 62]
Output: 133
Explanation: Max sum can be formed by 71 + 62 which has same digit sum of 8
Example 2:

Input A: [51, 71, 17, 42]
Output: 93
Explanation: Max sum can be formed by 51 + 42 which has same digit sum of 6
Example 3:

Input A: [42, 33, 60]
Output: 102
Explanation: Max sum can be formed by 42 + 60 which has same digit sum of 6
Example 4:

Input A: [51, 32, 43]
Output: -1
Explanation: There are no 2 numbers with same digit sum

``````class Solution {
public:
int findMaxSum(vector<int> nums) {
unordered_map<int, vector<int>> sumToNums; //maps digit sum to numbers with that digit sum
for (int i = 0; i < nums.size(); i++) {
int curNum = nums[i];
int dS = digitSum(curNum);
sumToNums[dS].push_back(curNum);
}
int maxSum = -1;
for (int i = 0; i < nums.size(); i++) {
int curNum = nums[i];
int dS = digitSum(curNum);
vector<int> matches = sumToNums[dS];
for (int num : matches) {
if (num == curNum) continue; //Can't add num to num
maxSum = max(maxSum, curNum+num);
}
}
return maxSum;
}

private:
int digitSum(int num) {
int sum = 0;
while (num > 0) {
sum += num%10;
num /= 10;
}
return sum;
}
};
int main() {
Solution s = Solution();
vector<int> nums = {51, 32, 43};
cout << s.findMaxSum(nums);
}
``````
``````import functools
import heapq

def maximum_sum_of_same_digit_sum(A):
digit_sum_map = {}
for num in A:
# Computing the sum of digits of the number
sum_of_digits = functools.reduce(lambda x, y: int(x) + int(y), str(num))
# Updating the obtained sum to the hash map and also pushing the corresponding number to the min heap
if sum_of_digits not in digit_sum_map or len(digit_sum_map[sum_of_digits]) < 2:
# Push the numbers to the heap until the numbers which form a sum are exactly 2
heapq.heappush(digit_sum_map.setdefault(sum_of_digits, []), num)

else:
# Once the numbers reach 2 push and pop the numbers to maintain the count to 2
heapq.heappushpop(digit_sum_map[sum_of_digits], num)

# Return the maximum sum of all the the 2 largest numbers that forms a particular sum
return max(map(lambda nums: functools.reduce(lambda x, y: x + y, nums) if len(nums) == 2 else -1, digit_sum_map.values()))
``````

8月5号的Hiring event，recruiter 发邮件找的我。我是在职跳槽。我发现巨硬的OA非常有规律，就是同一时间段的题目基本固定，比如我这次看了其他几个7月份的题目，我的题目也就是他们帖子里面的其中三道。一开始为了保险我还翻了好久以前的题目做

1. 给一个string，“aAbeedxXb”，只有a-z, A-Z. 找到一个字母的大小写同时出现在string里。比如这里是A, E, X。 然后X > E > A。 所以最后返回 X. O(N) 解决
2. 给一个string， 例如 “aaabceddd”, 找到一个最长的substring，使得substring里面没有连续的相同三个字母。那这个答案就是7. “aabcedd”。 用sliding window 的思路解决。 O(N)
3. 给一个string， 例如“aaabce”，求最少要删除多少个字符，能使string里面的字母出现评率都是unique的。String只包含az。比如这个需要删除 2. bce其中两个。 因为a有三个，bce各有一个，我需要删除其中两个才能使一个字母的评率是unique的。我用了PQ排序频率解决，但是因为最多26个频率，所以最后O(n) + O(26log26) = O(N)

1. Given a string containing only ‘a’s and ‘b’s, it is valid if it contains not more than 2 contigous occurences of a and b. For example “aabbababaabb” is valid but “aaabbaabbb” is not. Find minimum number of characters you need to replace to make a string valid.
Note that once you replace a character, it can became invalid. You can replace only one character in one iteration.
2. Given a string s containing only ‘a’s and ‘b’s, find longest substring of s such that s does not contain more than two contigous occurences of ‘a’ and ‘b’
Example: 1) Given “aabbaaaaabb” result is “aabbaa” 2) Given “aabbaabbaabbaa” result is “aabbaabbaabbaa”
3. Given an array containing integers, find two integers a, b such that sum of digits of a and b is equal. Return maximum sum of a and b. Return -1 if no such numbers exist.
Example : [42, 60, 33] - 42 and 60 have same sum of digits. Return 102.