📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
楼主: moluren
跳转到指定楼层
上一主题 下一主题
收起左侧

[其他] 请大家分享一下大家觉得高大上且鬼父神工的算法实现

 
🔗
 楼主| moluren 2019-1-23 08:44:42 | 只看该作者
全局:
guid-uuid 发表于 2019-1-23 06:01
https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/49785/Java-solution-without-k ...

这道题真让我开了眼了,看了3遍才明白。除了计算长度和用Set外,又多了一种如此简洁的思路。
回复

使用道具 举报

🔗
guid-uuid 2019-1-23 08:59:25 | 只看该作者
全局:
pandami 发表于 2019-1-23 06:24
lc的discussion部分看高赞答案里面one liner two liner很多
但是这些对刚开始刷题找工作的人 大部分情况并 ...

有些算法之所以高赞,并不仅仅因为它是1 liner or 2 liner。因为它在时间复杂度,以及创意上都让人为之一惊。这个帖子的lz要的是鬼斧神工而不是basic算法。

此外面试过程中的follow up往往都是需要你去discussion里多了解的不同的算法。很有可能面试官给你个 intersection of two linked list原题,大家上来就通过算长度的差别给解出来了,但是这时候面试官非常有可能多问你一句不算长度差别或者代码如何优化之类的。如果面试的目标仅仅是答上来基本题,那flag基本不用去申请了。

我倒是强烈建议大家刷题的时候不仅要自己能做出来ac,还是去多看看讨论,了解一下不同的idea,归纳总结一下思路,做到知其所以然,才不会出现被各种follow up问倒的情况。而且答题不仅仅是看你有没有写出来,代码的整洁优美程度也是一个考量范围。我自己就是被g家hr告知代码可以写的更优美一些在hc之后被挂的。

补充内容 (2019-1-23 09:03):
p.s. 我挂在经典面经 汇率题,lc上我自己通过算出来每个新汇率组合会产生的所有update 这样的query 是o(1),update也不比用graph做出来的差,lc pass,然后我就没有仔细去研究其他解法,结果导致面试时磕绊写出bfs.

评分

参与人数 3大米 +52 收起 理由
arcovitcher + 1 赞一个
ts-elizabeth + 1 赞一个
Warald + 50

查看全部评分

回复

使用道具 举报

🔗
 楼主| moluren 2019-1-23 09:01:08 | 只看该作者
全局:
再提供一个微软以前某个时期经常考的热身题或者电面题,蠡口 168。我以前也被面过这道题,当时面是在A4纸上写的,写得乱七八糟的不是很好,后来回去总结了一下:

  1.     public String convertToTitle(int n) {
  2.         return n-- == 0 ? "" : convertToTitle(n / 26) + (char) (n % 26 + 'A');
  3.     }
复制代码

评分

参与人数 1大米 +30 收起 理由
admin + 30

查看全部评分

回复

使用道具 举报

🔗
bonta9613 2019-1-23 09:01:39 | 只看该作者
全局:
题目:从nums中找到两个integer,它们的和等于target。返回两个integer在nums中的位置。

自己写了一个特别慢的,找了leetCode Nathan_Fegard大神的python code:

def twoSum(nums, target):
    if len(nums) <= 1:
        return False
    buff_dict = {}
    for i in range(len(nums)):
        if nums[i] in buff_dict:
            return [buff_dict[nums[i]], i]
        else:
            buff_dict[target - nums[i]] = i

dict的运用已经神了

评分

参与人数 1大米 +40 收起 理由
admin + 40

查看全部评分

回复

使用道具 举报

🔗
 楼主| moluren 2019-1-23 09:08:01 | 只看该作者
全局:
guid-uuid 发表于 2019-1-23 08:59
有些算法之所以高赞,并不仅仅因为它是1 liner or 2 liner。因为它在时间复杂度,以及创意上都让人为之一 ...

是的,十分同意你的观点。

面试很多情况不是要把答案背出来,如果再没有动手写代码之前,可以把各种可能的实现和面试官交流完,分析其利弊。得到面试官允许后,最后根据时间空间复杂度的取舍提供了最简洁的代码,我相信肯定是最佳表现。
回复

使用道具 举报

🔗
EroicaCMCS 2019-1-23 09:09:13 | 只看该作者
全局:
Yao's Garbled Circuit,图灵奖名不虚传
回复

使用道具 举报

全局:
guid-uuid 发表于 2019/01/23 08:59:25


有些算法之所以高赞,并不仅仅因为它是1 liner or 2 liner。因为它在时间复杂度,以及创意上都让人为之一惊。这个帖子的lz要的是鬼斧神工而不是basic算法。

此外面试过程中的f...

所以你说的和我说的并没有什么冲突啊

高赞有两种 一种是“鬼斧神工” 就像前面一个帖子写的用bitset做dp 这种完全可以不看 就算你看了 保证讲不清楚 面试答出来 面试官也不一定懂

另外一种是高赞因为解法清晰 这种我不称为鬼斧神工 我称为标准解法

对于新人 一般要求是
1 能想到一种解法 最差brute force
2 有标准解法(比如大部分高赞)
3 有两种以上标准解法
4 知道大神级别解法 比如bit manipulation kmp morris segtree 等等

评分

参与人数 1大米 +40 收起 理由
admin + 40

查看全部评分

回复

使用道具 举报

全局:
guid-uuid 发表于 2019/01/23 08:59:25


有些算法之所以高赞,并不仅仅因为它是1 liner or 2 liner。因为它在时间复杂度,以及创意上都让人为之一惊。这个帖子的lz要的是鬼斧神工而不是basic算法。

此外面试过程中的f...

我没说高赞就一定是1line 2line。。。
我是说大神再给出标准解法之后往往会炫一下技
回复

使用道具 举报

全局:
初学者需要的不是每道题掌握一种独特的解法 而是用最少的解法解决最多的问题

切合这个帖子 我推荐一个算法

287. Find the Duplicate Number

请去博客园 grandyang查看完整答案

两种答案我都很喜欢

C++ Solution 1 :
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int low = 1, high = nums.size() - 1;
        while (low < high) {
            int mid = low + (high - low) * 0.5;
            int cnt = 0;
            for (auto a : nums) {
                if (a <= mid) ++cnt;
            }
            if (cnt <= mid) low = mid + 1;
            else high = mid;
        }
        return low;
    }
};
C++ Solution 2 :
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = 0, fast = 0, t = 0;
        while (true) {
            slow = nums[slow];
            fast = nums[nums[fast]];
            if (slow == fast) break;
        }
        while (true) {
            slow = nums[slow];
            t = nums[t];
            if (slow == t) break;
        }
        return slow;
    }
};

评分

参与人数 1大米 +40 收起 理由
admin + 40

查看全部评分

回复

使用道具 举报

全局:
guid-uuid 发表于 2019/01/23 08:59:25


有些算法之所以高赞,并不仅仅因为它是1 liner or 2 liner。因为它在时间复杂度,以及创意上都让人为之一惊。这个帖子的lz要的是鬼斧神工而不是basic算法。

此外面试过程中的f...

399 的dfs bfs unionfind算不上惊为天人吧。。。也就三个标准解法
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表