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, 自然是初始化好了的
|
|
