推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

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

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

脸熟 电面经

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

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

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

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

x

45mins
印度小哥

1. all permutations , 给个 “ABC”--》. from: 1point3acres.com/bbs

abc
acb
bac
bca
cab
cba. visit 1point3acres.com for more.

follow up 是 如果有重复的怎么去重, 我用的hashset, 他问有没有 不用额外空间的, 当时没想出来, 他提醒了可以sort, 就很快给了答案,没时间写这个。。

问了java pass by value/referecne,  recursion vs dfs , 这个基本问题。 关键是边写边解释。. Waral 鍗氬鏈夋洿澶氭枃绔,
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷


评分

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);. more info on 1point3acres.com
        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);
. from: 1point3acres.com/bbs             swap(nums[start], nums[i]);
        }
    }
};
. visit 1point3acres.com for more.
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
谢谢分享 楼主问题好简单啊

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

使用道具 举报

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

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

使用道具 举报

 楼主| porkbelly 发表于 2017-7-3 00:49:57 | 显示全部楼层
forteller 发表于 2017-7-2 13:13
即使不考虑recursion stack上的空间,也没法不用额外空间去重吧。
leetcode里最好的也是用了O(n)的空 ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
如果sorted的话,应该可以在for loop 去重吧?。。印度小哥说可以work。

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
如果sorted的话,应该可以在for loop 去重吧?。。印度小哥说可以work。-google 1point3acres

. 1point 3acres 璁哄潧dfs (char[] array, int leve ...
. From 1point 3acres bbs
你确定这个能过oj?. 鍥磋鎴戜滑@1point 3 acres


补充内容 (2017-7-3 09:50):.1point3acres缃
class Solution {
public:
    vector<vector<int> > permuteUnique(vector<int> &num) {
        sort(num.begin(), num.end());
        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。

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

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

使用道具 举报

 楼主| porkbelly 发表于 2017-7-4 07:23:28 | 显示全部楼层
edyyy 发表于 2017-7-3 09:47
你确定这个能过oj?

嗯。确实过不了oj。。 还是需要boolean 的array 才行。
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

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

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-8-24 03:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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