【通知】7月22,工业界资深数据科学家教你破解各大公司面试!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 953|回复: 13
收起左侧

脸熟 电面经

[复制链接] |试试Instant~ |关注本帖
porkbelly 发表于 2017-7-2 02:11:50 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 硕士 全职@Facebook - 猎头 - 技术电面 |Pass在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x

45mins
印度小哥

1. all permutations , 给个 “ABC”--》

abc
acb
bac
bca. 鍥磋鎴戜滑@1point 3 acres
cab
cba
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
follow up 是 如果有重复的怎么去重, 我用的hashset, 他问有没有 不用额外空间的, 当时没想出来, 他提醒了可以sort, 就很快给了答案,没时间写这个。。

问了java pass by value/referecne,  recursion vs dfs , 这个基本问题。 关键是边写边解释。


. From 1point 3acres bbs

评分

1

查看全部评分

本帖被以下淘专辑推荐:

edyyy 发表于 2017-7-3 09:52:30 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {        
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());.鐣欏璁哄潧-涓浜-涓夊垎鍦
        permuteDFS(nums, 0, res);
        return res;
    }
    void permuteDFS(vector<int> &nums, int start, vector<vector<int>> &res) {
        if (start >= nums.size()) {res.push_back(nums);return;}
        for (int i = start; i < nums.size(); ++i) {
            if (i > start && nums[i] == nums[i - 1]) continue;
            swap(nums[start], nums[i]);
            permuteDFS(nums, start + 1, res);
            swap(nums[start], nums[i]);. Waral 鍗氬鏈夋洿澶氭枃绔,
        }
    }. 1point3acres.com/bbs
};

c++过不了 [00019] 的例子有重复
回复 支持 1 反对 0

使用道具 举报

edyyy 发表于 2017-7-2 03:58:09 | 显示全部楼层
关注一亩三分地微博:
Warald
谢谢分享 楼主问题好简单啊
回复 支持 反对

使用道具 举报

forteller 发表于 2017-7-2 04:58:36 | 显示全部楼层
楼主用的的是C++还是Java,亦或是其他语言? 不用额外空间,做all permutation,好像Java做不到。(除了nested for loop法)
回复 支持 反对

使用道具 举报

 楼主| porkbelly 发表于 2017-7-2 10:18:47 | 显示全部楼层
forteller 发表于 2017-7-2 04:58
楼主用的的是C++还是Java,亦或是其他语言? 不用额外空间,做all permutation,好像Java做不到。(除了nes ...

我用的java, 我感觉他的意思不考虑 recursion stack 上的空间。  我最开始用hashset,在每一层都有额外空间,所以他才这个问题吧。
回复 支持 反对

使用道具 举报

 楼主| porkbelly 发表于 2017-7-2 10:19:52 | 显示全部楼层
edyyy 发表于 2017-7-2 03:58
谢谢分享 楼主问题好简单啊

是啊,运气好...准备昂赛特压力更大
回复 支持 反对

使用道具 举报

forteller 发表于 2017-7-2 13:13:53 | 显示全部楼层
porkbelly 发表于 2017-7-2 10:18
我用的java,  我感觉他的意思不考虑 recursion stack 上的空间。  我最开始用hashset,在每一层都有额外 ...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
即使不考虑recursion stack上的空间,也没法不用额外空间去重吧。
leetcode里最好的也是用了O(n)的空间,一个全局的boolean[]。
求问lz怎么做到的
回复 支持 反对

使用道具 举报

 楼主| porkbelly 发表于 2017-7-3 00:49:57 | 显示全部楼层
forteller 发表于 2017-7-2 13:13. 1point 3acres 璁哄潧
即使不考虑recursion stack上的空间,也没法不用额外空间去重吧。
leetcode里最好的也是用了O(n)的空 ...

如果sorted的话,应该可以在for loop 去重吧?。。印度小哥说可以work。
. 鍥磋鎴戜滑@1point 3 acres
dfs (char[] array, int level){
if (level == array.length){.鏈枃鍘熷垱鑷1point3acres璁哄潧
  result.add(new String(array));
return;
}
for (int i = level; i < array.length; i++){
  if (i != level && array != array[i-1]){.1point3acres缃
      swap(array, level ,i)
      dfs(array, i+1);
      swap(array, level, i);
  }
}
}
回复 支持 反对

使用道具 举报

熟狗脸 发表于 2017-7-3 01:16:40 来自手机 | 显示全部楼层
dfs 和 recursion 啥区别?
回复 支持 反对

使用道具 举报

edyyy 发表于 2017-7-3 09:47:30 | 显示全部楼层
porkbelly 发表于 2017-7-3 00:49
如果sorted的话,应该可以在for loop 去重吧?。。印度小哥说可以work。

dfs (char[] array, int leve ...

你确定这个能过oj? 鏉ユ簮涓浜.涓夊垎鍦拌鍧.


补充内容 (2017-7-3 09:50):. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
class Solution {
public:
    vector<vector<int> > permuteUnique(vector<int> &num) {
        sort(num.begin(), num.end());. more info on 1point3acres.com
        vector<vector<int> >res;
        recursion(num, 0, num.size(), res)...
回复 支持 反对

使用道具 举报

forteller 发表于 2017-7-4 07:20:33 | 显示全部楼层
porkbelly 发表于 2017-7-3 00:49
如果sorted的话,应该可以在for loop 去重吧?。。印度小哥说可以work。.1point3acres缃
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
dfs (char[] array, int leve ...

这不能work。 不是很明显。.鐣欏璁哄潧-涓浜-涓夊垎鍦
OJ上跑一下吧。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
或者我给你个例子:aaabbbcccddd
回复 支持 反对

使用道具 举报

 楼主| porkbelly 发表于 2017-7-4 07:23:28 | 显示全部楼层
edyyy 发表于 2017-7-3 09:47
你确定这个能过oj?
. 1point 3acres 璁哄潧
嗯。确实过不了oj。。 还是需要boolean 的array 才行。
回复 支持 反对

使用道具 举报

 楼主| porkbelly 发表于 2017-7-4 07:24:09 | 显示全部楼层
forteller 发表于 2017-7-4 07:20
这不能work。 不是很明显。
OJ上跑一下吧。
或者我给你个例子:aaabbbcccddd
. visit 1point3acres.com for more.
对的。 这样还是不行。 好像还是需要boolean array 才行。
回复 支持 反对

使用道具 举报

forteller 发表于 2017-7-4 07:27:20 | 显示全部楼层
porkbelly 发表于 2017-7-4 07:24
对的。 这样还是不行。 好像还是需要boolean array 才行。

对对。不过印度小哥没看出来
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-7-21 19:10

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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