新鲜出炉巨硬哦阿

新鲜出炉oa。
一共三题，

debug题 新题
代码题 黎寇 妖耳伞舅
代码题 也是新题，找分数和等于一

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

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

codility的submit有些奇怪。click submit 好像是每一题都需要click submit。我匆匆只剩最后一分钟才知道，提交到两题就session ended了。。。不像亚麻能每一题都save，然后submit会submit全部三题。刚刚email了hr希望能确定第三题真的submit了。

求求大米。。。

我求分数和等于1的写法。把两个数的分母变成一样，保证分子的和和分母相等就可以了。然后用long保持不overflow。

1. public class FractionsSumToOne {
   
2.     private int solution(int[] X, int[] Y) {
   
3.         long count = 0;
   
4.         for (int i = 0; i < X.length - 1; i++) {
   
5.             for (int j = i + 1; j < X.length; j++) {
   
6.                 long divident = X[i] * Y[j] + X[j] * Y[i];
   
7.                 long divisor = Y[i] * Y[j];
   
8.                 if (divident == divisor) {
   
9.                     count++;
   
10.                 }
    
11.             }
    
12.         }
    
13. 
    
14.         return (int) (count % 1000000007);
    
15.     }
    
16. 
    
17.     public static void main(String[] args) {
    
18.         FractionsSumToOne solution = new FractionsSumToOne();
    
19.         System.out.println(solution.solution(new int[]{1, 1 , 1}, new int[]{2, 2, 2}));
    
20.         System.out.println(solution.solution(new int[]{1, 2 , 3, 1, 2, 12, 8, 4}, new int[]{5, 10, 15, 2, 4, 15, 10, 5}));
    
21.         System.out.println(solution.solution(new int[]{500000000, 500000000}, new int[]{1000000000, 1000000000}));
    
22.     }
    
23. }

复制代码

davechan813 发表于 2020-6-12 15:39
请问楼主是new grad还是experienced? 谢谢~

工作了三年。

djmiss 发表于 2020-6-12 16:28
我的理解是：
1.遍历一遍数组，用GCD把能约分的都约掉。由于约分之后，对于分母不一样的两个数一定不可 ...

不知道有没有遗漏，不过花了我几个小时去解，太虐了        

/*
                NOTE:
                - N is an integer within the range [0, 100,000] inclusive
                - Each element of arrays X, Y is an integer within the range
                  [1, 1,000,000,000]
        */
        class Solution
        {
        public:
                int getNumberOfPairs(vector<int>& numerators,
                                                         vector<int>& denominators)
                {
                        if (numerators.empty() ||
                                denominators.empty())
                        {
                                return 0;
                        }

                        if (numerators.size() != denominators.size())
                        {
                                return 0;
                        }

                        /*
                                Key = denominator
                                Value = a map of pair<numerator, frequency>
                        */
                        unordered_map<int, unordered_map<int,int>> frequency_map;
                        const int SIZE = numerators.size();

                        /*
                                Create the frequency map,
                                each pair of numerator and denominator has been simplified.
                        */
                        for (int i = 0; i < SIZE; ++i)
                        {
                                int denominator = denominators;
                                int numerator = numerators[i];

                                update_denominator_numerator(denominator, numerator);
                                ++frequency_map[denominator][numerator];
                        }

                        int numWays = 0;[/i][i]
                        // Denominator
                        // pair<denominator, numerator map>
                        for (pair<int, unordered_map<int,int>> denominator_entry : frequency_map)
                        {
                                int denominator = denominator_entry.first;
                                
                                // Numerator
                                // pair<numerator, frequency>                 
                                unordered_map<int, int>::iterator iter = frequency_map[denominator].begin();

                                while (!frequency_map[denominator].empty() &&
                                           iter != frequency_map[denominator].end())
                                {
                                        // (denominator - numerator)
                                        int cur_numerator = iter->first;
                                        int diff_numerator = (denominator - cur_numerator);

                                        /*
                                                NOTE:
                                                If the diff is found in the numerator map,
                                                that means we can find the pair that sum up to 1.
                                        */
                                        if (frequency_map[denominator].count(diff_numerator))
                                        {
                                                int cur_frequency = iter->second;
                                                
                                                /*
                                                        Special Case:
                                                        1/2 + 1/2 = 1.
                                                */
                                                if (cur_numerator == diff_numerator)
                                                {
                                                        int final_frequency = 0;

                                                        int count = (cur_frequency -1);

                                                        while (count > 0)
                                                        {
                                                                final_frequency += count;
                                                                --count;
                                                        }
                                                        // Update result.
                                                        numWays += final_frequency;

                                                        frequency_map[denominator].erase(cur_numerator);
                                                        continue;
                                                }

                                                int diff_frequency = frequency_map[denominator][diff_numerator];

                                                // Update both frequencies.
                                                int final_frequency = (cur_frequency * diff_frequency);
                                                frequency_map[denominator].erase(cur_numerator);
                                                frequency_map[denominator].erase(diff_numerator);

                                                // Update result.
                                                numWays += final_frequency;
                                        }
                                        else
                                        {
                                                ++iter;
                                        }
                                }
                        }
                        return numWays;
                }

        private:
                void update_denominator_numerator(int& denominator, int& numerator)
                {
                        int gcd = get_greatest_common_divisor(denominator, numerator);

                        denominator /= gcd;
                        numerator   /= gcd;
                }

                /*
                        Reference:
                        - https://www.geeksforgeeks.org/c-program-find-gcd-hcf-two-numbers/
                */
                int get_greatest_common_divisor(int denominator, int numerator)
                {
                        if (denominator == 0)
                        {
                                return numerator;
                        }
                        if (numerator == 0)
                        {
                                return denominator;
                        }

                        // Base Case
                        if (denominator == numerator)
                        {
                                return denominator;
                        }

                        if (denominator > numerator)
                        {
                                return get_greatest_common_divisor((denominator - numerator), numerator);
                        }
                        return get_greatest_common_divisor(denominator, (numerator - denominator));
                }
        };[/i]

请问什么组

JEM 发表于 2020-6-12 14:00
请问什么组

onedrive/sharepoint组

请问楼主是new grad还是experienced? 谢谢~

谢谢楼主！

请问下lz截图里面的第二题是debug题吗？ 这道题并不是妖耳伞舅啊。

oumizx 发表于 2020-6-12 20:12
请问下lz截图里面的第二题是debug题吗？ 这道题并不是妖耳伞舅啊。

上传截图次序乱了。截图全都是新题，一个是debug题，一个是代码题（数出全部合为一的分数组）。

ptopenny 发表于 2020-6-12 09:39
上传截图次序乱了。截图全都是新题，一个是debug题，一个是代码题（数出全部合为一的分数组）。

请问下debug题的截图是答案还是未改的状态？

麻倉枼 发表于 2020-6-13 04:22
请问下debug题的截图是答案还是未改的状态？

那是未改的时候，我把currentsum=0从 if 移出来。每一次只要遇到负数就要reset currentsum成零，而不是当currentsum大过maxsum时候