# 微软OA

Given a String S consisting og N Lowercase letters that must be deleted to obtain a word in which every letter occurs
a unique number of times. We Only care about the occurrences of letters that appear at least once in result

Examples:

1. Given S=‘eeeeffff’, the function should return 1. We can delete one occurence of e or one occurence of f.
Then one letter will occur four times and the other three times
2. Given S = ‘aabbffddeaee’ the function should return 6. For example, we can delete all occurences of e and f and one occurence of d to obtain the word ‘aabbda’ Note that both e and f will occur zero times in the new word, but that’s fine, since we only care about the letter that appear at least once
3. Given S = ‘llll’ the function should return 0( there is no need to delete any character)
4. Given S = ‘example’ the function should return 4

Mark is fan of logic based games. However he is bored of the basic ones, like Sudoku and Mastermind, since he has solved so many of them. Recently he found a new game in which one is given a string with some question marks in it. The objective is to replace all of the question marks with letters(one letter per question mark) in such a way that no letters appears next to another letter of the same kind.

Write a function:

``````def replaceQuestionMark(puzzle):
pass
""" Your code goes here """
``````

that given a string puzzle, returns a copy of the string with all the question marks replaced by lowercase letters(a-z) in such a way that the same letters do not occur next to each other. The result can be any of the possible answers as long as it fulfils the above requirements.

Examples:

Given puzzle = ‘xy?xz?’, your function might return ‘xycxza’. Some other possible results are ‘xyzxzd’, ‘xyfxzf’.

Given puzzle = ‘ab?e?mr??’. Your function might return ‘abveamrab’

Given puzzle = ‘???’. Your function might return ‘league’

Write an efficient algorithm for the following assumptions:

String puzzle contains only of lowercase letters(a-z) or ‘?’
It is always possible to turn string ‘puzzle’ into a string without two identical consecutive letters

Write a function:

class Solution { public int solution(int[] A);}

that, given an array A consisting of N integers, returns the maximum sum of two numbers whose digits add upto an equal sum.If there are no two numbers whose digits have an equal sum, the function should return -1.

Example:

Given A = [51,71,17,42], the function should return 93. There are two pairs of numbers whose digits add upto an equal sum (51,42) and (17,71).The first pair sums up to 93.
Given A = [43,33,60],the function should return 102. The digits of all numbers add upto same sum and choosing to add 42 and 60 gives the result 102.
Given A=[51,32,43] the function should return -1, since all numbers in A have digits that add upto different unique sums.

1. 题目描述是一个公司要招50个intern（0-49个）

5000 * 3 = 15000

15000 + 5000 + 1 = 20001

20001 + 5000 + 2 = 25002

1. 题目描述是一个破案什么的，但其实本质就是constrcut tree from preorder traversal and inorder traversal

tree reconstruction结束之后是要从最底层到root这样的一个level-order traversal

1. 题目要求是给一个数字，可以由两种选择：（1）将它替换成它最大的prime factor，比如9最大的prime factor就是3，因为3是9的因子，并且3是质数。（2）现在的这个数字-1 求让这个数字变成1的最短步数

（当然可能也有更好的做法。）

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

``````public int solution(String s) {
int moves = 0;
for (int i = 0 ; i < s.length(); i++) {
int runLength = 1;
for (; i + 1 < s.length() && s.charAt(i) == s.charAt(i + 1); i++) {
runLength++;
}
moves += runLength / 3;
}
return moves;
}
``````

Given a string s containing only as and bs, find longest substring of s such that s does not contain more than two contigous occurences of a and b.

Example 1:

Input: “aabbaaaaabb”
Output: “aabbaa”
Example 2:

Input: “aabbaabbaabbaa”
Output: “aabbaabbaabbaa”

Ships are aligned in layers, with following conditions:
Each ship has value(v)
Each ship in a layer is followed by [v^2+1]%M ships,with values from 0 to ([v^2+1]%M)-1
The first ship has value v=2
M is constant given as argument
Find The Total number of ships %M in all layers
Ex:
L=1
M=4
Output:1 //One layer thus only 1 ship

Given a string s consisting of lowercase characters, you have to delete the minimum number of characters from s so that every letter in s appears a unique number of times.

Example 1:

Input: “aaaabbbb”
Output: 1
Explanation: Both ‘a’ and ‘b’ occur 4 times if the first character is deleted then ‘a’ occurs 3 times and ‘b’ occurs 4 times.

Given a string s and an integer k. Break the string in such a way that:

The resulting string should not contain parts of a word.
The resulting string should not contain spaces.
If the size of k is greater than length of given string then return the given string as it is.

Example 1:

Input: s = “Codility We test coders”, k = 14
Output: “Codility We”
Explaination: If we split until 14 characters then output will be “Codility We te”, but since “te” is part of a word so ignore that.
Also notice we ignore the space after “We” and “test” in our output.

Example 2:

Input: s = “The quick brown fox jumps over the lazy dog”, k = 39
Output: “The quick brown fox jumps over the lazy”

Example 3:

Input: s = “Why not”, k = 39
Output: “Why not”
Explanation: Since the size of ‘k’ is greater than the length of given string so we return the string as it is.