h****y 发帖数: 137 | 1 leetcode原题, permutation II和permutation sequence, 就是把int换成了char, 45
分钟的面试老中面试官大哥迟到5分钟, 却要按时结束, 加上闲扯几句, 这两题一共就
32分钟时间, 我自己感觉除了一点小typo之外没有问题啊, 那几个typo还是因为第二题
完全没时间检查了, 有他迟到的5分钟肯定能检查出来. 6个小时后就收到拒信, 而且我
用的C++, 感觉面试官对C++一点都不熟, 基本不说话, 我说好了后他也不review, 不作
评价,第二题还冒了一句std::set的元素是无序的, 你这样遍历得到的结果是随机的,
还浪费我时间跟他解释, 我汗...
下面贴上我的代码, 想请大家评评, 真心不懂为啥被拒, 能不能跟recruiter complain
一下?
1. input : string
output : print all the permutation of the input
there are duplicates in the input, avoid print out the same string in the
output
void permute_helper(string& str, int idx, vector& res, unordered_set
& hash)
{
if (idx == str.size())
{
res.emplace_back(str);
return;
}
for (auto& c : hash)
{
if (c.second > 0)
{
str[idx] = c.first;
--c.second;
permute_helper(str, idx+1, res, hash);
++c.second;
}
}
}
vector permute(string& str)
{
vector res;
unordered_set hash;
for (auto& c : str)
++hash[c];
permute_helper(str, 0, res, hash);
return res;
}
2. n-th permutation in lexicographic order
string correspPermute(string& str, int index)
{
set table;
for (auto& c : str)
table.insert(c);
int nPermute = 1;
for (int i = 1; i < str.size(); ++i)
nPermute *= i;
string res;
--index;
for (int m = index; m >= 0; --m) // 这里不应该是index应该是str.size()
{
nPermute /= m;
int idx = index / nPermute;
auto iter = table.begin();
for (int i = 0; i < idx; ++i)
++iter;
res.emplace_back(*iter); // 这里应该是push_back
talbe.erase(iter); // 这里table打错了
index %= nPermute;
}
return res;
} | s********u 发帖数: 1109 | 2 额。。恕我愚昧,这种情况是应该用unordered_map还是unordered_set?怎么记得set的
模版是是单个元素而不是pair的。。 | h****y 发帖数: 137 | 3 额, 确实又多一个typo, 不过编译就能发现的错应该也不是big deal呀
【在 s********u 的大作中提到】 : 额。。恕我愚昧,这种情况是应该用unordered_map还是unordered_set?怎么记得set的 : 模版是是单个元素而不是pair的。。
| s********u 发帖数: 1109 | 4 可能是你的代码太fancy了。我平时都不用unordered_map或者unordered_set,因为是C
++11才有的东西,怕面试官不熟悉。只用map和vector。auto指针的也从来没搞清楚过。
甚至有时候能用for(i = 0;i < size();)解决的东西就不用iterator,怕面试一紧张就
容易写错
【在 h****y 的大作中提到】 : 额, 确实又多一个typo, 不过编译就能发现的错应该也不是big deal呀
| s********u 发帖数: 1109 | 5 关于第一个题目想讨论下,
题目基本上就是 careercup书 9.5,用recursion或者iteration都可以。不过对于重复
的处理,我直观感受是用一个map 来存所有已经遍历过的permutation,
然后如果是重复的,就不塞入vector的结果里面。。
不知道是否有更好的解法。lz好像是统计每个字符出现的次数,没太看懂。 | u*****o 发帖数: 1224 | 6 这人本身就是manager吗?不是面试完会report给manager经过讨论才会决定下一步吗。
怎么这么快。。
45
complain
【在 h****y 的大作中提到】 : leetcode原题, permutation II和permutation sequence, 就是把int换成了char, 45 : 分钟的面试老中面试官大哥迟到5分钟, 却要按时结束, 加上闲扯几句, 这两题一共就 : 32分钟时间, 我自己感觉除了一点小typo之外没有问题啊, 那几个typo还是因为第二题 : 完全没时间检查了, 有他迟到的5分钟肯定能检查出来. 6个小时后就收到拒信, 而且我 : 用的C++, 感觉面试官对C++一点都不熟, 基本不说话, 我说好了后他也不review, 不作 : 评价,第二题还冒了一句std::set的元素是无序的, 你这样遍历得到的结果是随机的, : 还浪费我时间跟他解释, 我汗... : 下面贴上我的代码, 想请大家评评, 真心不懂为啥被拒, 能不能跟recruiter complain : 一下? : 1. input : string
| h****y 发帖数: 137 | 7 统计次数之后就完全没有重复的问题了, 下一个字符的选择都只有剩下的unique
character那么多, 比产生所有permutation然后再去掉重复要efficient
【在 s********u 的大作中提到】 : 关于第一个题目想讨论下, : 题目基本上就是 careercup书 9.5,用recursion或者iteration都可以。不过对于重复 : 的处理,我直观感受是用一个map 来存所有已经遍历过的permutation, : 然后如果是重复的,就不塞入vector的结果里面。。 : 不知道是否有更好的解法。lz好像是统计每个字符出现的次数,没太看懂。
| h****y 发帖数: 137 | 8 取set的第n个元素只能用iterator吧?
我还跟他讲了stl的set没有提供API, 只好linear取第N个元素了,
boost里的set可以log(n)时间给第n个元素的, 不过我不记得API了,
不过看他没啥反应, 还在那纠结set的元素是不是排了序的, 感觉是鸡对鸭讲了...
是C
过。
【在 s********u 的大作中提到】 : 可能是你的代码太fancy了。我平时都不用unordered_map或者unordered_set,因为是C : ++11才有的东西,怕面试官不熟悉。只用map和vector。auto指针的也从来没搞清楚过。 : 甚至有时候能用for(i = 0;i < size();)解决的东西就不用iterator,怕面试一紧张就 : 容易写错
| s********u 发帖数: 1109 | 9 比如 set si; 直接取 *( si.begin() + n ) 不行么?
如果是unordered_map和unordered_set的话,元素存放的顺序是输入的
顺序么?这里好像确实有点混淆。
1.我查了下,unordered_map和unordered_set从内部结构上说,是“乱序“的,比如你
一个元素放在第5个位置,后面再加入一个元素后,原来那个元素就未必是第5个了。存
放的顺序由hashtable来确定,只是为了快速存取。
http://www.cplusplus.com/reference/unordered_set/unordered_set/
2.如果是map或者set,每次插入时会按照key的大小自动排序,实际上应该就是个二叉
树。
【在 h****y 的大作中提到】 : 取set的第n个元素只能用iterator吧? : 我还跟他讲了stl的set没有提供API, 只好linear取第N个元素了, : boost里的set可以log(n)时间给第n个元素的, 不过我不记得API了, : 不过看他没啥反应, 还在那纠结set的元素是不是排了序的, 感觉是鸡对鸭讲了... : : 是C : 过。
| a********m 发帖数: 15480 | 10 写的似乎有点乱,俺看了眼没看懂。。。。另外函数参数都是reference,似乎不太好。
【在 s********u 的大作中提到】 : 关于第一个题目想讨论下, : 题目基本上就是 careercup书 9.5,用recursion或者iteration都可以。不过对于重复 : 的处理,我直观感受是用一个map 来存所有已经遍历过的permutation, : 然后如果是重复的,就不塞入vector的结果里面。。 : 不知道是否有更好的解法。lz好像是统计每个字符出现的次数,没太看懂。
| | | h****y 发帖数: 137 | 11 set的iterator像list一样, 只能++, --的, 不可以+n
unordered_map是就是hash table, 乱序的
set和map是BST
【在 s********u 的大作中提到】 : 比如 set si; 直接取 *( si.begin() + n ) 不行么? : 如果是unordered_map和unordered_set的话,元素存放的顺序是输入的 : 顺序么?这里好像确实有点混淆。 : 1.我查了下,unordered_map和unordered_set从内部结构上说,是“乱序“的,比如你 : 一个元素放在第5个位置,后面再加入一个元素后,原来那个元素就未必是第5个了。存 : 放的顺序由hashtable来确定,只是为了快速存取。 : http://www.cplusplus.com/reference/unordered_set/unordered_set/ : 2.如果是map或者set,每次插入时会按照key的大小自动排序,实际上应该就是个二叉 : 树。
| g*********e 发帖数: 14401 | | w*********m 发帖数: 4740 | 13 对,全t家都不用c++,而用java,scala
【在 g*********e 的大作中提到】 : 因为面试官不懂C++ 你用JAVA估计就过了
| j********r 发帖数: 25 | 14 参考一下我的做题记录里提取出来的:
class Solution {
public:
vector > permuteUnique(vector &num) {
sort(num.begin(), num.end());
vector > ret;
int n = num.size();
bool *used = new bool[n];
vector index;
memset(used, 0, n*sizeof(bool));
permute(num, used, index, 0, ret);
delete[] used;
return ret;
}
void permute(const vector &num, bool used[], vector& candidate
, int pos, vector > &ret) {
int n = num.size();
if (pos == n) {
ret.push_back(candidate);
return;
}
for (int i = 0; i < n; ) {
if (used[i]) {i++; continue;}
used[i] = true;
candidate.push_back(num[i]);
permute(num, used, candidate, pos+1, ret);
used[i] = false;
candidate.pop_back();
i++;
while (i < n && num[i] == num[i-1])
i++;
}
}
};
class Solution {
public:
string getPermutation(int n, int k) {
int fact = 1;
for(int i = 1; i < n; i++) fact *= i;
vector chars;
for(int i = 1; i <=n; i++)
chars.push_back(i+'0');
string output;
k--;
for(int i = n-1;i >=0; i--) {
int index = k / fact;
output.push_back(chars[index]);
chars.erase(chars.begin()+index);
k = k%fact;
if (i >0)
fact /= i;
}
return output;
}
};
45
complain
【在 h****y 的大作中提到】 : leetcode原题, permutation II和permutation sequence, 就是把int换成了char, 45 : 分钟的面试老中面试官大哥迟到5分钟, 却要按时结束, 加上闲扯几句, 这两题一共就 : 32分钟时间, 我自己感觉除了一点小typo之外没有问题啊, 那几个typo还是因为第二题 : 完全没时间检查了, 有他迟到的5分钟肯定能检查出来. 6个小时后就收到拒信, 而且我 : 用的C++, 感觉面试官对C++一点都不熟, 基本不说话, 我说好了后他也不review, 不作 : 评价,第二题还冒了一句std::set的元素是无序的, 你这样遍历得到的结果是随机的, : 还浪费我时间跟他解释, 我汗... : 下面贴上我的代码, 想请大家评评, 真心不懂为啥被拒, 能不能跟recruiter complain : 一下? : 1. input : string
| f********4 发帖数: 988 | 15 你写的太fancy了,面书官水平不到,get不到里面的point
很多细节都是tinking in C++的人才能理解的,你看leetcode上贴的答案,他们写的都
是function,你写的是program
所以,面试官没法get到你水平高低。。。还有你背景可能不是那么match,coding还好
,没看对眼而已 | y**k 发帖数: 222 | 16 直说请你别生气呀:这有很好的算法的,如果,我是说如果,考查重点在算法的话,你
这两程序确实有可改进的地方。 | h****y 发帖数: 137 | 17 你能详细说说吗? 除了coding style, 从算法上还可以更优?
【在 y**k 的大作中提到】 : 直说请你别生气呀:这有很好的算法的,如果,我是说如果,考查重点在算法的话,你 : 这两程序确实有可改进的地方。
| T*******e 发帖数: 4928 | 18 楼主,不好意思说一句,我怎么觉得人家出简单的题给你,原本是想放你水的。
你好好想想,如果人家真想为难你,两道中也得出一道你根本没见过的。 | y**k 发帖数: 222 | 19 你搜索一下permutation 的算法吧。
当然,我𣎴知道这些算法是不是需要一般程序员掌握。
【在 h****y 的大作中提到】 : 你能详细说说吗? 除了coding style, 从算法上还可以更优?
| s********u 发帖数: 1109 | 20 我觉得lz的算法已经足够了。careercup的答案也就是这个层次的,面试还能指望更多
么?只是code写的太fancy,又没时间给面试官解释,面试官理解不了的话,自然没办
法了。 | | | f********4 发帖数: 988 | 21
其实简单的题真不一定是想放你,简单题没有区分度,你会我也会
当然难题肯定更不是想放你,直接出一道谁都没见过的,是真想测水平吧
总之我总结了一下:出简单的不对,出难的更不对,总之不让过就是不对:-D
【在 T*******e 的大作中提到】 : 楼主,不好意思说一句,我怎么觉得人家出简单的题给你,原本是想放你水的。 : 你好好想想,如果人家真想为难你,两道中也得出一道你根本没见过的。
| t*****s 发帖数: 416 | 22 我们公司的interview report没有题目和candidate的答案思路什么的。就几个rating
选项。
你说manager如果看到一水儿的最低rating会怎么做?
当然我不是T的,T是咋样我不知道。
LZ不要灰心,也许是面你的面试官自己其实有哥们推荐了这个职位在走流程,所以就瞬
间把你坑了。
当然如果你碰到的是烙印那就更不用说了。
面试还是很看RP的,LZ move on吧。不要这么纠结了。
【在 u*****o 的大作中提到】 : 这人本身就是manager吗?不是面试完会report给manager经过讨论才会决定下一步吗。 : 怎么这么快。。 : : 45 : complain
| h****y 发帖数: 137 | 23 也是, 面过那么多大公司还是第一次见面试官迟到的
不过我都是栽在国人手里的, 烙印还从没和我过不去
rating
【在 t*****s 的大作中提到】 : 我们公司的interview report没有题目和candidate的答案思路什么的。就几个rating : 选项。 : 你说manager如果看到一水儿的最低rating会怎么做? : 当然我不是T的,T是咋样我不知道。 : LZ不要灰心,也许是面你的面试官自己其实有哥们推荐了这个职位在走流程,所以就瞬 : 间把你坑了。 : 当然如果你碰到的是烙印那就更不用说了。 : 面试还是很看RP的,LZ move on吧。不要这么纠结了。
| h****y 发帖数: 137 | 24 what do you mean by function and program?
【在 f********4 的大作中提到】 : 你写的太fancy了,面书官水平不到,get不到里面的point : 很多细节都是tinking in C++的人才能理解的,你看leetcode上贴的答案,他们写的都 : 是function,你写的是program : 所以,面试官没法get到你水平高低。。。还有你背景可能不是那么match,coding还好 : ,没看对眼而已
| h****y 发帖数: 137 | 25 这个题本身不能算简单吧, 在leetcode里难度系数也是4和5了.
难道都默认大家leetcode烂熟了? 如果默认这道题你做过了那又考查啥呢
【在 T*******e 的大作中提到】 : 楼主,不好意思说一句,我怎么觉得人家出简单的题给你,原本是想放你水的。 : 你好好想想,如果人家真想为难你,两道中也得出一道你根本没见过的。
| h****y 发帖数: 137 | 26 你在vector里用erase这是很costly的操作啊,
我就是为了避免这个用的set, log(n)时间delete, 结果面试官不懂set
【在 j********r 的大作中提到】 : 参考一下我的做题记录里提取出来的: : class Solution { : public: : vector > permuteUnique(vector &num) { : sort(num.begin(), num.end()); : vector > ret; : int n = num.size(); : bool *used = new bool[n]; : vector index; : memset(used, 0, n*sizeof(bool));
| n*******0 发帖数: 34 | 27 这个很同意阿!刚刚被国人坑过。。很多时候还是觉得国人从骨子里学不会
professional..很轻易就有了bias!
【在 h****y 的大作中提到】 : 也是, 面过那么多大公司还是第一次见面试官迟到的 : 不过我都是栽在国人手里的, 烙印还从没和我过不去 : : rating
| m**********4 发帖数: 774 | 28 我大概看了眼LZ写的第一题的CODE,除了有个别TYPO还有小的错误(SET or MAP??? ),
我觉得写的挺SMART的(俺不是很懂C++,JAVA CODER)。我感觉LZ水平不错,老中面
试官SB. 自己的同胞写的哪怕比这个差都应该放水。 | j********r 发帖数: 25 | 29 I didn't like the erase part either! Any better idea?
The problem with Set is that you can't have duplicated char.
【在 h****y 的大作中提到】 : 你在vector里用erase这是很costly的操作啊, : 我就是为了避免这个用的set, log(n)时间delete, 结果面试官不懂set
| h****y 发帖数: 137 | 30 不管是leetcode的int还是我面的这道题改成char, 都是assume no duplicate的, 要是
还考虑duplicate难度又上升了, 而且你即便用vector的解法在duplicate的情况下也是
不对的
【在 j********r 的大作中提到】 : I didn't like the erase part either! Any better idea? : The problem with Set is that you can't have duplicated char.
| | | m******s 发帖数: 204 | 31 ??? Do you mean algorithms in http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations?
【在 y**k 的大作中提到】 : 直说请你别生气呀:这有很好的算法的,如果,我是说如果,考查重点在算法的话,你 : 这两程序确实有可改进的地方。
| a******e 发帖数: 710 | 32 我觉得30分钟做出这两道题很不简单啊。
不过这个循环的判断应该是小于等于号吧?
for (int i = 1; i <= str.size(); ++i)
nPermute *= i;
string correspPermute(string& str, int index)
{
set table;
for (auto& c : str)
table.insert(c);
int nPermute = 1;
for (int i = 1; i < str.size(); ++i)
nPermute *= i;
string res;
--index;
for (int m = index; m >= 0; --m) // 这里不应该是index应该是str.size()
{
nPermute /= m;
int idx = index / nPermute;
auto iter = table.begin();
for (int i = 0; i < idx; ++i)
++iter;
res.emplace_back(*iter); // 这里应该是push_back
talbe.erase(iter); // 这里table打错了
index %= nPermute;
}
return res;
}
45
complain
【在 h****y 的大作中提到】 : leetcode原题, permutation II和permutation sequence, 就是把int换成了char, 45 : 分钟的面试老中面试官大哥迟到5分钟, 却要按时结束, 加上闲扯几句, 这两题一共就 : 32分钟时间, 我自己感觉除了一点小typo之外没有问题啊, 那几个typo还是因为第二题 : 完全没时间检查了, 有他迟到的5分钟肯定能检查出来. 6个小时后就收到拒信, 而且我 : 用的C++, 感觉面试官对C++一点都不熟, 基本不说话, 我说好了后他也不review, 不作 : 评价,第二题还冒了一句std::set的元素是无序的, 你这样遍历得到的结果是随机的, : 还浪费我时间跟他解释, 我汗... : 下面贴上我的代码, 想请大家评评, 真心不懂为啥被拒, 能不能跟recruiter complain : 一下? : 1. input : string
| a******e 发帖数: 710 | 33 set不能做随机存取
http://www.cplusplus.com/reference/set/set/?kw=set
它的iterator只支持++和--
【在 s********u 的大作中提到】 : 比如 set si; 直接取 *( si.begin() + n ) 不行么? : 如果是unordered_map和unordered_set的话,元素存放的顺序是输入的 : 顺序么?这里好像确实有点混淆。 : 1.我查了下,unordered_map和unordered_set从内部结构上说,是“乱序“的,比如你 : 一个元素放在第5个位置,后面再加入一个元素后,原来那个元素就未必是第5个了。存 : 放的顺序由hashtable来确定,只是为了快速存取。 : http://www.cplusplus.com/reference/unordered_set/unordered_set/ : 2.如果是map或者set,每次插入时会按照key的大小自动排序,实际上应该就是个二叉 : 树。
| a***n 发帖数: 538 | | a****n 发帖数: 1887 | | a******e 发帖数: 710 | 36 楼主用的是第三种解法。比前两个都快。。。
【在 a***n 的大作中提到】 : nth permutation应该是这个吧 : http://swiyu.wordpress.com/2012/10/11/find-all-permutation-find : 楼主的太慢了。
| a******e 发帖数: 710 | 37 lz第一道题的解法有个问题就是helper里面的str数组没有初始化过,也就是没有预先
分配空间。运行的时候会出现访问数组越界的错误。
第二道题, n_permutation/=m的时候,m可能等于零。这个情况要单独处理。
45
complain
【在 h****y 的大作中提到】 : leetcode原题, permutation II和permutation sequence, 就是把int换成了char, 45 : 分钟的面试老中面试官大哥迟到5分钟, 却要按时结束, 加上闲扯几句, 这两题一共就 : 32分钟时间, 我自己感觉除了一点小typo之外没有问题啊, 那几个typo还是因为第二题 : 完全没时间检查了, 有他迟到的5分钟肯定能检查出来. 6个小时后就收到拒信, 而且我 : 用的C++, 感觉面试官对C++一点都不熟, 基本不说话, 我说好了后他也不review, 不作 : 评价,第二题还冒了一句std::set的元素是无序的, 你这样遍历得到的结果是随机的, : 还浪费我时间跟他解释, 我汗... : 下面贴上我的代码, 想请大家评评, 真心不懂为啥被拒, 能不能跟recruiter complain : 一下? : 1. input : string
| a******e 发帖数: 710 | 38 lz第二题还有个小bug
nPermute /= m;
这里m是可以是0的,这种情况要单独处理。
45
complain
【在 h****y 的大作中提到】 : leetcode原题, permutation II和permutation sequence, 就是把int换成了char, 45 : 分钟的面试老中面试官大哥迟到5分钟, 却要按时结束, 加上闲扯几句, 这两题一共就 : 32分钟时间, 我自己感觉除了一点小typo之外没有问题啊, 那几个typo还是因为第二题 : 完全没时间检查了, 有他迟到的5分钟肯定能检查出来. 6个小时后就收到拒信, 而且我 : 用的C++, 感觉面试官对C++一点都不熟, 基本不说话, 我说好了后他也不review, 不作 : 评价,第二题还冒了一句std::set的元素是无序的, 你这样遍历得到的结果是随机的, : 还浪费我时间跟他解释, 我汗... : 下面贴上我的代码, 想请大家评评, 真心不懂为啥被拒, 能不能跟recruiter complain : 一下? : 1. input : string
| h****y 发帖数: 137 | 39 对, 第二题应该是>=1,
第一题没有初始化的问题, str是input, 自然是初始化好了的
【在 a******e 的大作中提到】 : lz第一道题的解法有个问题就是helper里面的str数组没有初始化过,也就是没有预先 : 分配空间。运行的时候会出现访问数组越界的错误。 : 第二道题, n_permutation/=m的时候,m可能等于零。这个情况要单独处理。 : : 45 : complain
| a******e 发帖数: 710 | 40 第一题确实没错,我看错了。抱歉~
【在 h****y 的大作中提到】 : 对, 第二题应该是>=1, : 第一题没有初始化的问题, str是input, 自然是初始化好了的
|
|