微软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.

微软的OA,跪经

上周五2019.09.27,一共三道题

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

第一天intern的员工编号是5000*k,比如第一天第一个进来的intern,他的员工编号就是5000,第一天第二个进来的就是1000,

以此类推

从第二天开始,D(i) = D(i - 1) + 5000 + i,注意第二天的i=1

问题是给一个员工编号,求出这个员工是第几个员工。(这里我可能理解的有问题,之后会解释)

例子:25002

5000 * 3 = 15000

15000 + 5000 + 1 = 20001

20001 + 5000 + 2 = 25002

所以是第三天的第一个员工,输出的是3,可能是我理解有问题,如果输出是3的话可能求的是第几天的员工?

因为这个理解的出入导致一个test case没过,我的写法是Backtracking,就是暴力解出各种可能性,最后sum==0的时候我就返回结果。

当然Backtracking是暴力解,感觉肯定有更好的方法。。

  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的最短步数

我的答案:感觉可以用dp做,但是考试的时候太紧张了就用了Backtracking,基础的test case过了但是之后的好几个corner case

没过

关于prime factor,我用的是Sieve of Eratosthenes,求出所有到这个数之前的prime number,然后看看其中有没有他的因子

(当然可能也有更好的做法。)

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.


image

image



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.




image