一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 1378|回复: 13
收起左侧

脸熟 电面经

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

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

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

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

x

45mins
印度小哥

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

abc
acb
bac. visit 1point3acres.com for more.
bca
cab. visit 1point3acres.com for more.
cba. 1point 3acres 璁哄潧

follow up 是 如果有重复的怎么去重, 我用的hashset, 他问有没有 不用额外空间的, 当时没想出来, 他提醒了可以sort, 就很快给了答案,没时间写这个。。
. from: 1point3acres.com/bbs
问了java pass by value/referecne,  recursion vs dfs , 这个基本问题。 关键是边写边解释。
.1point3acres缃

.鏈枃鍘熷垱鑷1point3acres璁哄潧

评分

1

查看全部评分

本帖被以下淘专辑推荐:

edyyy 发表于 2017-7-3 09:52:30 | 显示全部楼层
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {        
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        permuteDFS(nums, 0, res);. Waral 鍗氬鏈夋洿澶氭枃绔,
        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) {. from: 1point3acres.com/bbs
            if (i > start && nums[i] == nums[i - 1]) continue;. from: 1point3acres.com/bbs
            swap(nums[start], nums[i]);
            permuteDFS(nums, start + 1, res);
            swap(nums[start], nums[i]);
        }
    }. more info on 1point3acres.com
};
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
c++过不了 [00019] 的例子有重复
回复 支持 1 反对 0

使用道具 举报

edyyy 发表于 2017-7-2 03:58:09 | 显示全部楼层
谢谢分享 楼主问题好简单啊
回复 支持 反对

使用道具 举报

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. Waral 鍗氬鏈夋洿澶氭枃绔,
谢谢分享 楼主问题好简单啊

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

使用道具 举报

forteller 发表于 2017-7-2 13:13:53 | 显示全部楼层
porkbelly 发表于 2017-7-2 10:18
我用的java,  我感觉他的意思不考虑 recursion stack 上的空间。  我最开始用hashset,在每一层都有额外 ...

即使不考虑recursion stack上的空间,也没法不用额外空间去重吧。. more info on 1point3acres.com
leetcode里最好的也是用了O(n)的空间,一个全局的boolean[]。
求问lz怎么做到的
回复 支持 反对

使用道具 举报

 楼主| porkbelly 发表于 2017-7-3 00:49:57 | 显示全部楼层
forteller 发表于 2017-7-2 13:13. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
即使不考虑recursion stack上的空间,也没法不用额外空间去重吧。.鐣欏璁哄潧-涓浜-涓夊垎鍦
leetcode里最好的也是用了O(n)的空 ...

如果sorted的话,应该可以在for loop 去重吧?。。印度小哥说可以work。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
.鏈枃鍘熷垱鑷1point3acres璁哄潧
dfs (char[] array, int level){
if (level == array.length){
  result.add(new String(array));
return;
}
for (int i = level; i < array.length; i++){
  if (i != level && array != array[i-1]){
      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. From 1point 3acres bbs
如果sorted的话,应该可以在for loop 去重吧?。。印度小哥说可以work。

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

你确定这个能过oj?


补充内容 (2017-7-3 09:50):. 鍥磋鎴戜滑@1point 3 acres
class Solution {
public:. 1point 3acres 璁哄潧
    vector<vector<int> > permuteUnique(vector<int> &num) {
        sort(num.begin(), num.end());
        vector<vector<int> >res;. 1point 3acres 璁哄潧
        recursion(num, 0, num.size(), res)...
回复 支持 反对

使用道具 举报

forteller 发表于 2017-7-4 07:20:33 | 显示全部楼层
porkbelly 发表于 2017-7-3 00:49.鐣欏璁哄潧-涓浜-涓夊垎鍦
如果sorted的话,应该可以在for loop 去重吧?。。印度小哥说可以work。

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

这不能work。 不是很明显。
OJ上跑一下吧。
或者我给你个例子:aaabbbcccddd
回复 支持 反对

使用道具 举报

 楼主| porkbelly 发表于 2017-7-4 07:23:28 | 显示全部楼层
edyyy 发表于 2017-7-3 09:47
你确定这个能过oj?
. Waral 鍗氬鏈夋洿澶氭枃绔,
嗯。确实过不了oj。。 还是需要boolean 的array 才行。
回复 支持 反对

使用道具 举报

 楼主| porkbelly 发表于 2017-7-4 07:24:09 | 显示全部楼层
forteller 发表于 2017-7-4 07:20. From 1point 3acres bbs
这不能work。 不是很明显。
OJ上跑一下吧。. From 1point 3acres bbs
或者我给你个例子:aaabbbcccddd

对的。 这样还是不行。 好像还是需要boolean array 才行。
回复 支持 反对

使用道具 举报

forteller 发表于 2017-7-4 07:27:20 | 显示全部楼层
porkbelly 发表于 2017-7-4 07:24. 鍥磋鎴戜滑@1point 3 acres
对的。 这样还是不行。 好像还是需要boolean array 才行。

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-12-11 08:27

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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