Roblox New Grad 2021 OA

第二题：
public class AncestralName {

    public String[] ancestralName(String[] input){
        Map<Integer, String> map = new TreeMap<>();
        Arrays.sort(input);
        Arrays.sort(input, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                for(int i = 0; i < o1.length(); i++){
                    for(int j = 0; j < o2.length(); j++){
                        if(o1.charAt(i) == ' ' && o2.charAt(j) == ' '){
                            if(o1.substring(0, i-1).equals(o2.substring(0, j-1))){
                                return Integer.valueOf(romanToInt(o1.substring(i+1, o1.length())))
                                        .compareTo(Integer.valueOf(romanToInt(o2.substring(j+1, o2.length()))));
                            }

                        }
                    }
                }
                return 0;
            }
        });
        return input;
    }
    public int romanToInt(String s) {

        int number = 0;
        HashMap<Character,Integer> map = new HashMap<>();
        map.put('I',1);
        map.put('V',5);
        map.put('X',10);
        map.put('L',50);
        map.put('C',100);
        map.put('D',500);
        map.put('M',1000);

        if(s.length()<2)
            return map.get(s.charAt(0));

        for(int i=0;i<s.length();i++) {
            if(i<s.length()-1 && map.get(s.charAt(i+1)) > map.get(s.charAt(i))) {
                number+=map.get(s.charAt(i+1)) - map.get(s.charAt(i));
                i++;
            }
            else
                number+=map.get(s.charAt(i));
        }
        return number;
    }
}

第三题
public class CommonPrefix {
    public int[] commonPrefix(String input){
        int[] result = new int[input.length()];

        String[] memo = new String[input.length()];
        String[] prefixArray = new String[input.length()];
        String[] suffixArray = new String[input.length()];
        for(int i = 0; i < input.length(); i++){
            prefixArray[i] = input.substring(0, i);
            suffixArray[i] = input.substring(i, input.length());
        }
        for(int i = 0; i < prefixArray.length; i++){
            if(prefixArray[i].isEmpty()){
                result[i] = input.length();
            }else {
                int length = 0;
                for(int j = 0; j < prefixArray[i].length(); j++){
                    if(prefixArray[i].length() <= suffixArray[i].length()){
                        if(prefixArray[i].charAt(j) == suffixArray[i].charAt(j)){
                            length++;
                        }
                    }
                }
                result[i] = length;
            }
        }


        return result;
    }
}

Actuant 发表于 2020-9-19 08:06
可以搜一下kmp algorithm，或者看LC1392

第三题跟LC1392不一样的，再仔细看下，这里的suffix只是和原始string求一个common prefix的，不需要全部match

lyden999 发表于 2020-09-19 02:35:14
第三题跟LC1392不一样的，再仔细看下，这里的suffix只是和原始string求一个common prefix的，不需要全部match

1392也只需要match suffix和prefix吧，就是kmp的lps array

Actuant 发表于 2020-9-19 18:37
1392也只需要match suffix和prefix吧，就是kmp的lps array

common prefix的意思是suffix的prefix和string s的prefix进行match，一个for loop然后遇到于首字母相同的字母就进行extension然后取最大值，就是此时match的长度加到总和里

Roblox这**公司配出这个难度的题吗？

Actuant 发表于 2020-9-16 12:49
1. Sort + greedy 2. Roman to int 3. Kmp 第三题超纲了吧

第一题像是个多重背包问题？感觉可以用dp做

lyden999 发表于 2020-09-19 04:15:07
common prefix的意思是suffix的prefix和string s的prefix进行match，一个for loop然后遇到于首字母相同的字母就进行extension然后取最大值，就是此时

噢是我看错题了😂 原来数据量只有10，我看是10^5第一反应要kmp

joshuali1997 发表于 2020-09-19 16:14:17
第一题像是个多重背包问题？感觉可以用dp做

没有，想太复杂了。它的trucksize不是capacity，就是能装几个boxes，所以大的优先放就行了

亲测第三题不用kmp（感觉也没法用），直接暴力解就可以过。用o(n^2)的match来计算sum。注意不要提取substring进行比较，直接用index在同一个string上比较：比如一个string，for i = 0 to n - 1{ for j = i to n - 1 {compare characters by characters here}}。