Expedia OA

刚做完的OA，75分钟三题，是地里出现过的题目：
1. Can you sort
2. 4th Bit
3. K subsequences

题目截图都在这个帖子：

第二题比较简单，第一题和第三题都有几个tes

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

补充内容 (2019-3-8 01:43):
收到邮件 挂了😂😂

lanluo_violet 发表于 2019-3-3 16:21
第一题我用了个counter，然后sort

第三题，挺巧妙的，求余数

我是用的java
第一题：
    static void customerSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>(
                (o1, o2) -> {
                    if (o1.getValue() == o2.getValue()) {
                        return o1.getKey() - o2.getKey();
                    }
                    return o1.getValue() - o2.getValue();
                });

        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < arr.length; i++) {
            if (map.containsKey(arr[i])) {
                map.put(arr[i], map.get(arr[i]) + 1);
            } else {
                map.put(arr[i], 1);
            }
        }

        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            pq.add(entry);
        }

        int point = 0;
        while (!pq.isEmpty()) {
            Map.Entry<Integer, Integer> entry = pq.poll();
            int frequency = entry.getValue();
            for (int i = 0; i < frequency; i++) {
                arr[point] = entry.getKey();
                point++;
            }
        }
    }


第三题 我用的方法和你应该一样的 也是LeetCode答案
    static long KSub(int k, int[] nums) {

        HashMap<Integer, Integer> map = new HashMap<>();
        int curMod = 0;
        int[] modCount = new int[k];

        for (int i = 0; i < nums.length; i++) {
            curMod = (curMod + (nums[i] % k) + k) % k;
            modCount[curMod]++;
        }

        int sum = 0;

        for (int i = 1; i < modCount.length; i++) {
            sum += (modCount[i] * (modCount[i] - 1)) / 2;
        }
        sum += (modCount[0] * (modCount[0] + 1)) / 2;
        return sum;
    }

第一题我用了个counter，然后sort

第三题，挺巧妙的，求余数

If (presum[j]-presum[i]) % K == 0, then sum(a[i+1 : j]) % K is equal to zero, which we need to count. It means presum[j] and presum[i] have the same reminder mod K.

def ksubsequence(inp, n, k):
    reminder = [0] * k
    reminder[0] = 1        #subsequence start from 0
    pres = 0
    for num in inp:
        pres + =num
        pres = pres % k
        reminder[pres] += 1
    sol=0
    for r in reminder:
        if (r < 2): continue
   # found at least 1 pair
   # count of combination is r*(r-1)/2
        sol += r*(r-1)/2
    print sol

ShadowWander 发表于 2019-3-3 16:34
谢谢 层主分享， 请问第一题解法不太理解意思，可以大概说下吗？ 请问你也是 3 号due的一批吗

python:

import collections
def sort(nums):
    counter = collections.Counter(nums)
    array = [ (count, num) for num, count in counter.items()]
    array.sort()
    res = []
    for count, num in array:
        res += [num] * count
    return res

是的

你怎么就三道题，我90分钟要写7道题。。。

pgrio004 发表于 2019-3-3 14:58
你怎么就三道题，我90分钟要写7道题。。。

请问层主 有做90min吗？ 可以说下面经吗 谢谢！

请问楼主是 SDE 1 new grad吗

ShadowWander 发表于 2019-3-3 15:14
请问楼主是 SDE 1 new grad吗

是的 字数字数字数

low910411 发表于 2019-3-3 16:00
是的 字数字数字数

很奇怪，为啥我的邮件里写的是 90min 是 3 号的due吗

lanluo_violet 发表于 2019-3-3 16:21
第一题我用了个counter，然后sort

第三题，挺巧妙的，求余数

谢谢 层主分享， 请问第一题解法不太理解意思，可以大概说下吗？ 请问你也是 3 号due的一批吗

pgrio004 发表于 2019/03/03 14:58:57
你怎么就三道题，我90分钟要写7道题。。。

不知道哎 😂😂😂😂