c****e
发帖数: 398 | 1 虽然才工作一年，但是最近组里要招一个senior software engineer，所以也面试了不
少人
工作十年以上的码工基本都有很多东西可以侃，而作为新人我也很少去质疑他们
不过每次我都会出同样的一个编程题，一来很多人都声称自己在写code，而且我也不要
求他们写，只是要听一下他们的思路，看问题的角度
我的问题是Leetcode上的原题叫next permutation，找一个比当前数字大的最小数
好像面到现在十来个人，没有一个的答案是让我觉得满意的，思路都很混乱
我之所以上来发帖是因为刚刚面的这个老印真的是差到极点，直接摊手说不会，给什么
提示都不行
这个问题是太难了？还是我问的不对？还是说作软件十年以上就靠侃了，我不应该再问
这个？
有点疑惑 |
d**e
发帖数: 6098 | 2 坦白说，这题我觉得偏数学多过码工。反正我也不会，是我我就不会考这些很tricky的
题。
【在 c****e 的大作中提到】
: 虽然才工作一年，但是最近组里要招一个senior software engineer，所以也面试了不
: 少人
: 工作十年以上的码工基本都有很多东西可以侃，而作为新人我也很少去质疑他们
: 不过每次我都会出同样的一个编程题，一来很多人都声称自己在写code，而且我也不要
: 求他们写，只是要听一下他们的思路，看问题的角度
: 我的问题是Leetcode上的原题叫next permutation，找一个比当前数字大的最小数
: 好像面到现在十来个人，没有一个的答案是让我觉得满意的，思路都很混乱
: 我之所以上来发帖是因为刚刚面的这个老印真的是差到极点，直接摊手说不会，给什么
: 提示都不行
: 这个问题是太难了？还是我问的不对？还是说作软件十年以上就靠侃了，我不应该再问
|
w****r
发帖数: 15252 | 3 难道不是扫一边，找个差最小的，你题目能具体点不
【在 c****e 的大作中提到】
: 虽然才工作一年，但是最近组里要招一个senior software engineer，所以也面试了不
: 少人
: 工作十年以上的码工基本都有很多东西可以侃，而作为新人我也很少去质疑他们
: 不过每次我都会出同样的一个编程题，一来很多人都声称自己在写code，而且我也不要
: 求他们写，只是要听一下他们的思路，看问题的角度
: 我的问题是Leetcode上的原题叫next permutation，找一个比当前数字大的最小数
: 好像面到现在十来个人，没有一个的答案是让我觉得满意的，思路都很混乱
: 我之所以上来发帖是因为刚刚面的这个老印真的是差到极点，直接摊手说不会，给什么
: 提示都不行
: 这个问题是太难了？还是我问的不对？还是说作软件十年以上就靠侃了，我不应该再问
|
c****e
发帖数: 398 | 4 的确，我只是想看看思路，没想真让人写code
我再看看别的题吧
【在 d**e 的大作中提到】
: 坦白说，这题我觉得偏数学多过码工。反正我也不会，是我我就不会考这些很tricky的
: 题。
|
c****e
发帖数: 398 | 5 Implement “next permutation”, which rearranges numbers into the
lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest
possible order (ie, sorted in ascending order).
The replacement must be in-place, do not allocate extra memory.
Here are some examples. Inputs are in the left-hand column and its
corresponding outputs are in the right-hand column.
7495 -> 7945
9584 -> 9845
1234 -> 1243
【在 w****r 的大作中提到】
: 难道不是扫一边，找个差最小的，你题目能具体点不
|
w****r
发帖数: 15252 | 6 第一位肯定不会变的，如果后面都是0,那就是没有，问题是后面的数字有重复的可能吗
，如果没有，最傻的办法就是从最后一位往前扫描，如果后一位比前一位大的话，那么
就直接swap一下，然后继续往前，如果没有一个符合要求，就是说数字本生是从大到小
的就是找不到这样的数，返回原书数
忘了一个条件，如果有swap发生，swap后的数字要升序排一下，其实就是沉淀，把swap
后的数字沉淀到符合排序的最后位置， bingo
【在 c****e 的大作中提到】
: Implement “next permutation”, which rearranges numbers into the
: lexicographically next greater permutation of numbers.
: If such arrangement is not possible, it must rearrange it as the lowest
: possible order (ie, sorted in ascending order).
: The replacement must be in-place, do not allocate extra memory.
: Here are some examples. Inputs are in the left-hand column and its
: corresponding outputs are in the right-hand column.
: 7495 -> 7945
: 9584 -> 9845
: 1234 -> 1243
|
q********c
发帖数: 1774 | 7 请问是啥公司啊？这题挺好。
【在 c****e 的大作中提到】
: 虽然才工作一年，但是最近组里要招一个senior software engineer，所以也面试了不
: 少人
: 工作十年以上的码工基本都有很多东西可以侃，而作为新人我也很少去质疑他们
: 不过每次我都会出同样的一个编程题，一来很多人都声称自己在写code，而且我也不要
: 求他们写，只是要听一下他们的思路，看问题的角度
: 我的问题是Leetcode上的原题叫next permutation，找一个比当前数字大的最小数
: 好像面到现在十来个人，没有一个的答案是让我觉得满意的，思路都很混乱
: 我之所以上来发帖是因为刚刚面的这个老印真的是差到极点，直接摊手说不会，给什么
: 提示都不行
: 这个问题是太难了？还是我问的不对？还是说作软件十年以上就靠侃了，我不应该再问
|
c****e
发帖数: 398 | 8 对啊，很简单啊，从低住高，碰到低位比高位大的就swap一下
然后下面那一个sort一下就好
这个logic没有很过份吧，为啥都不会。。。
swap
【在 w****r 的大作中提到】
: 第一位肯定不会变的，如果后面都是0,那就是没有，问题是后面的数字有重复的可能吗
: ，如果没有，最傻的办法就是从最后一位往前扫描，如果后一位比前一位大的话，那么
: 就直接swap一下，然后继续往前，如果没有一个符合要求，就是说数字本生是从大到小
: 的就是找不到这样的数，返回原书数
: 忘了一个条件，如果有swap发生，swap后的数字要升序排一下，其实就是沉淀，把swap
: 后的数字沉淀到符合排序的最后位置， bingo
|
c****e
发帖数: 398 | 9 一个很小的R&D部门，在波士顿，你有兴趣吗？
【在 q********c 的大作中提到】
: 请问是啥公司啊？这题挺好。
|
w****r
发帖数: 15252 | 10 我能申请你们公司不
【在 c****e 的大作中提到】
: 对啊，很简单啊，从低住高，碰到低位比高位大的就swap一下
: 然后下面那一个sort一下就好
: 这个logic没有很过份吧，为啥都不会。。。
:
: swap
|
|
|
c****e
发帖数: 398 | 11 能啊，我们有一个潜在的candidate，但是面试还在继续
所以，你要是有兴趣把简历发给我看看吧
【在 w****r 的大作中提到】
: 我能申请你们公司不
|
l**********a
发帖数: 3 | |
c******w
发帖数: 1108 | 13 7495的下一个难道不应该是7549吗?
应该是从右往左扫,如果是单调增或者不变就继续.直到出现xdcba (假设第五位就出现)
满足x=c>=b>=a
然后把dcba...里面>x的第一个数提上来,剩下的数升序sort.
假设 d>=c>=b>x>=a 那么应该变成baxcd
另外剩下的数不用再sort,因为原本就是sorted降序的.先把x和b互换,然后dcxa前后
swap就好了
【在 c****e 的大作中提到】
: Implement “next permutation”, which rearranges numbers into the
: lexicographically next greater permutation of numbers.
: If such arrangement is not possible, it must rearrange it as the lowest
: possible order (ie, sorted in ascending order).
: The replacement must be in-place, do not allocate extra memory.
: Here are some examples. Inputs are in the left-hand column and its
: corresponding outputs are in the right-hand column.
: 7495 -> 7945
: 9584 -> 9845
: 1234 -> 1243
|
I**********s
发帖数: 441 | 14 这个问题的解法在离散数学的教材里可以找到. 手头有一本Rosen的Discrete Math and
Its Applications 4th edition, 在298页Algorithm 1.
STL的next_permutation函数可能就是这么实现的. |
p***y
发帖数: 637 | 15 cc150里有一题二进制的好像
【在 c****e 的大作中提到】
: Implement “next permutation”, which rearranges numbers into the
: lexicographically next greater permutation of numbers.
: If such arrangement is not possible, it must rearrange it as the lowest
: possible order (ie, sorted in ascending order).
: The replacement must be in-place, do not allocate extra memory.
: Here are some examples. Inputs are in the left-hand column and its
: corresponding outputs are in the right-hand column.
: 7495 -> 7945
: 9584 -> 9845
: 1234 -> 1243
|
c****e
发帖数: 398 | 16 对，应该就是像这样的，这个Logic不难吧
现)
【在 c******w 的大作中提到】
: 7495的下一个难道不应该是7549吗?
: 应该是从右往左扫,如果是单调增或者不变就继续.直到出现xdcba (假设第五位就出现)
: 满足x=c>=b>=a
: 然后把dcba...里面>x的第一个数提上来,剩下的数升序sort.
: 假设 d>=c>=b>x>=a 那么应该变成baxcd
: 另外剩下的数不用再sort,因为原本就是sorted降序的.先把x和b互换,然后dcxa前后
: swap就好了
|
c****e
发帖数: 398 | 17 不招，除非是做UI的，刚才已经帮一位版上的仁兄试过了
【在 l**********a 的大作中提到】
: LZ要new grad不？
|
c******w
发帖数: 1108 | 18 我认为不难.主要是对数字要敏感吧
大牛哪个公司?把我要过去吧~~ :P
【在 c****e 的大作中提到】
: 对，应该就是像这样的，这个Logic不难吧
:
: 现)
|
c****e
发帖数: 398 | 19 发简历？
【在 c******w 的大作中提到】
: 我认为不难.主要是对数字要敏感吧
: 大牛哪个公司?把我要过去吧~~ :P
|
c*******e
发帖数: 19 | 20 这题我会，但是我是CS fresh master, 你们要吗？ |
|
|
P**********r
发帖数: 755 | 21 既然lz不招new grad 那我就歪个楼。。
你的头像好萌啊。我最喜欢这么点大的猫猫了 |
c****e
发帖数: 398 | 22 虽然才工作一年，但是最近组里要招一个senior software engineer，所以也面试了不
少人
工作十年以上的码工基本都有很多东西可以侃，而作为新人我也很少去质疑他们
不过每次我都会出同样的一个编程题，一来很多人都声称自己在写code，而且我也不要
求他们写，只是要听一下他们的思路，看问题的角度
我的问题是Leetcode上的原题叫next permutation，找一个比当前数字大的最小数
好像面到现在十来个人，没有一个的答案是让我觉得满意的，思路都很混乱
我之所以上来发帖是因为刚刚面的这个老印真的是差到极点，直接摊手说不会，给什么
提示都不行
这个问题是太难了？还是我问的不对？还是说作软件十年以上就靠侃了，我不应该再问
这个？
有点疑惑 |
d**e
发帖数: 6098 | 23 坦白说，这题我觉得偏数学多过码工。反正我也不会，是我我就不会考这些很tricky的
题。
【在 c****e 的大作中提到】
: 虽然才工作一年，但是最近组里要招一个senior software engineer，所以也面试了不
: 少人
: 工作十年以上的码工基本都有很多东西可以侃，而作为新人我也很少去质疑他们
: 不过每次我都会出同样的一个编程题，一来很多人都声称自己在写code，而且我也不要
: 求他们写，只是要听一下他们的思路，看问题的角度
: 我的问题是Leetcode上的原题叫next permutation，找一个比当前数字大的最小数
: 好像面到现在十来个人，没有一个的答案是让我觉得满意的，思路都很混乱
: 我之所以上来发帖是因为刚刚面的这个老印真的是差到极点，直接摊手说不会，给什么
: 提示都不行
: 这个问题是太难了？还是我问的不对？还是说作软件十年以上就靠侃了，我不应该再问
|
w****r
发帖数: 15252 | 24 难道不是扫一边，找个差最小的，你题目能具体点不
【在 c****e 的大作中提到】
: 虽然才工作一年，但是最近组里要招一个senior software engineer，所以也面试了不
: 少人
: 工作十年以上的码工基本都有很多东西可以侃，而作为新人我也很少去质疑他们
: 不过每次我都会出同样的一个编程题，一来很多人都声称自己在写code，而且我也不要
: 求他们写，只是要听一下他们的思路，看问题的角度
: 我的问题是Leetcode上的原题叫next permutation，找一个比当前数字大的最小数
: 好像面到现在十来个人，没有一个的答案是让我觉得满意的，思路都很混乱
: 我之所以上来发帖是因为刚刚面的这个老印真的是差到极点，直接摊手说不会，给什么
: 提示都不行
: 这个问题是太难了？还是我问的不对？还是说作软件十年以上就靠侃了，我不应该再问
|
c****e
发帖数: 398 | 25 的确，我只是想看看思路，没想真让人写code
我再看看别的题吧
【在 d**e 的大作中提到】
: 坦白说，这题我觉得偏数学多过码工。反正我也不会，是我我就不会考这些很tricky的
: 题。
|
c****e
发帖数: 398 | 26 Implement “next permutation”, which rearranges numbers into the
lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest
possible order (ie, sorted in ascending order).
The replacement must be in-place, do not allocate extra memory.
Here are some examples. Inputs are in the left-hand column and its
corresponding outputs are in the right-hand column.
7495 -> 7945
9584 -> 9845
1234 -> 1243
【在 w****r 的大作中提到】
: 难道不是扫一边，找个差最小的，你题目能具体点不
|
w****r
发帖数: 15252 | 27 第一位肯定不会变的，如果后面都是0,那就是没有，问题是后面的数字有重复的可能吗
，如果没有，最傻的办法就是从最后一位往前扫描，如果后一位比前一位大的话，那么
就直接swap一下，然后继续往前，如果没有一个符合要求，就是说数字本生是从大到小
的就是找不到这样的数，返回原书数
忘了一个条件，如果有swap发生，swap后的数字要升序排一下，其实就是沉淀，把swap
后的数字沉淀到符合排序的最后位置， bingo
【在 c****e 的大作中提到】
: Implement “next permutation”, which rearranges numbers into the
: lexicographically next greater permutation of numbers.
: If such arrangement is not possible, it must rearrange it as the lowest
: possible order (ie, sorted in ascending order).
: The replacement must be in-place, do not allocate extra memory.
: Here are some examples. Inputs are in the left-hand column and its
: corresponding outputs are in the right-hand column.
: 7495 -> 7945
: 9584 -> 9845
: 1234 -> 1243
|
q********c
发帖数: 1774 | 28 请问是啥公司啊？这题挺好。
【在 c****e 的大作中提到】
: 虽然才工作一年，但是最近组里要招一个senior software engineer，所以也面试了不
: 少人
: 工作十年以上的码工基本都有很多东西可以侃，而作为新人我也很少去质疑他们
: 不过每次我都会出同样的一个编程题，一来很多人都声称自己在写code，而且我也不要
: 求他们写，只是要听一下他们的思路，看问题的角度
: 我的问题是Leetcode上的原题叫next permutation，找一个比当前数字大的最小数
: 好像面到现在十来个人，没有一个的答案是让我觉得满意的，思路都很混乱
: 我之所以上来发帖是因为刚刚面的这个老印真的是差到极点，直接摊手说不会，给什么
: 提示都不行
: 这个问题是太难了？还是我问的不对？还是说作软件十年以上就靠侃了，我不应该再问
|
c****e
发帖数: 398 | 29 对啊，很简单啊，从低住高，碰到低位比高位大的就swap一下
然后下面那一个sort一下就好
这个logic没有很过份吧，为啥都不会。。。
swap
【在 w****r 的大作中提到】
: 第一位肯定不会变的，如果后面都是0,那就是没有，问题是后面的数字有重复的可能吗
: ，如果没有，最傻的办法就是从最后一位往前扫描，如果后一位比前一位大的话，那么
: 就直接swap一下，然后继续往前，如果没有一个符合要求，就是说数字本生是从大到小
: 的就是找不到这样的数，返回原书数
: 忘了一个条件，如果有swap发生，swap后的数字要升序排一下，其实就是沉淀，把swap
: 后的数字沉淀到符合排序的最后位置， bingo
|
c****e
发帖数: 398 | 30 一个很小的R&D部门，在波士顿，你有兴趣吗？
【在 q********c 的大作中提到】
: 请问是啥公司啊？这题挺好。
|
|
|
w****r
发帖数: 15252 | 31 我能申请你们公司不
【在 c****e 的大作中提到】
: 对啊，很简单啊，从低住高，碰到低位比高位大的就swap一下
: 然后下面那一个sort一下就好
: 这个logic没有很过份吧，为啥都不会。。。
:
: swap
|
c****e
发帖数: 398 | 32 能啊，我们有一个潜在的candidate，但是面试还在继续
所以，你要是有兴趣把简历发给我看看吧
【在 w****r 的大作中提到】
: 我能申请你们公司不
|
l**********a
发帖数: 3 | |
c******w
发帖数: 1108 | 34 7495的下一个难道不应该是7549吗?
应该是从右往左扫,如果是单调增或者不变就继续.直到出现xdcba (假设第五位就出现)
满足x=c>=b>=a
然后把dcba...里面>x的第一个数提上来,剩下的数升序sort.
假设 d>=c>=b>x>=a 那么应该变成baxcd
另外剩下的数不用再sort,因为原本就是sorted降序的.先把x和b互换,然后dcxa前后
swap就好了
【在 c****e 的大作中提到】
: Implement “next permutation”, which rearranges numbers into the
: lexicographically next greater permutation of numbers.
: If such arrangement is not possible, it must rearrange it as the lowest
: possible order (ie, sorted in ascending order).
: The replacement must be in-place, do not allocate extra memory.
: Here are some examples. Inputs are in the left-hand column and its
: corresponding outputs are in the right-hand column.
: 7495 -> 7945
: 9584 -> 9845
: 1234 -> 1243
|
I**********s
发帖数: 441 | 35 这个问题的解法在离散数学的教材里可以找到. 手头有一本Rosen的Discrete Math and
Its Applications 4th edition, 在298页Algorithm 1.
STL的next_permutation函数可能就是这么实现的. |
p***y
发帖数: 637 | 36 cc150里有一题二进制的好像
【在 c****e 的大作中提到】
: Implement “next permutation”, which rearranges numbers into the
: lexicographically next greater permutation of numbers.
: If such arrangement is not possible, it must rearrange it as the lowest
: possible order (ie, sorted in ascending order).
: The replacement must be in-place, do not allocate extra memory.
: Here are some examples. Inputs are in the left-hand column and its
: corresponding outputs are in the right-hand column.
: 7495 -> 7945
: 9584 -> 9845
: 1234 -> 1243
|
c****e
发帖数: 398 | 37 对，应该就是像这样的，这个Logic不难吧
现)
【在 c******w 的大作中提到】
: 7495的下一个难道不应该是7549吗?
: 应该是从右往左扫,如果是单调增或者不变就继续.直到出现xdcba (假设第五位就出现)
: 满足x=c>=b>=a
: 然后把dcba...里面>x的第一个数提上来,剩下的数升序sort.
: 假设 d>=c>=b>x>=a 那么应该变成baxcd
: 另外剩下的数不用再sort,因为原本就是sorted降序的.先把x和b互换,然后dcxa前后
: swap就好了
|
c****e
发帖数: 398 | 38 不招，除非是做UI的，刚才已经帮一位版上的仁兄试过了
【在 l**********a 的大作中提到】
: LZ要new grad不？
|
c******w
发帖数: 1108 | 39 我认为不难.主要是对数字要敏感吧
大牛哪个公司?把我要过去吧~~ :P
【在 c****e 的大作中提到】
: 对，应该就是像这样的，这个Logic不难吧
:
: 现)
|
c****e
发帖数: 398 | 40 发简历？
【在 c******w 的大作中提到】
: 我认为不难.主要是对数字要敏感吧
: 大牛哪个公司?把我要过去吧~~ :P
|
|
|
c*******e
发帖数: 19 | 41 这题我会，但是我是CS fresh master, 你们要吗？ |
P**********r
发帖数: 755 | 42 既然lz不招new grad 那我就歪个楼。。
你的头像好萌啊。我最喜欢这么点大的猫猫了 |
b********r
发帖数: 620 | 43 个人觉得这题比较考基本功。不是偏题怪题。3个步骤缺一不可，得一环扣一环。老印
光说不练这有什么奇怪的。
【在 c****e 的大作中提到】
: 虽然才工作一年，但是最近组里要招一个senior software engineer，所以也面试了不
: 少人
: 工作十年以上的码工基本都有很多东西可以侃，而作为新人我也很少去质疑他们
: 不过每次我都会出同样的一个编程题，一来很多人都声称自己在写code，而且我也不要
: 求他们写，只是要听一下他们的思路，看问题的角度
: 我的问题是Leetcode上的原题叫next permutation，找一个比当前数字大的最小数
: 好像面到现在十来个人，没有一个的答案是让我觉得满意的，思路都很混乱
: 我之所以上来发帖是因为刚刚面的这个老印真的是差到极点，直接摊手说不会，给什么
: 提示都不行
: 这个问题是太难了？还是我问的不对？还是说作软件十年以上就靠侃了，我不应该再问
|
b*****p
发帖数: 117 | 44 第一句错了。8900就得变成9008
应该是最先判断是不是4321这种由左到右降序。如果是，直接判断没有。如果不是，进
入下一步。
然后是先个位十位swap，如果十位比个位小的话。如果不是，那就得考虑个十百三位。
但是还是两两对比swap。
然后还得回去个十位swap.
(可以递归？)
swap
【在 w****r 的大作中提到】
: 第一位肯定不会变的，如果后面都是0,那就是没有，问题是后面的数字有重复的可能吗
: ，如果没有，最傻的办法就是从最后一位往前扫描，如果后一位比前一位大的话，那么
: 就直接swap一下，然后继续往前，如果没有一个符合要求，就是说数字本生是从大到小
: 的就是找不到这样的数，返回原书数
: 忘了一个条件，如果有swap发生，swap后的数字要升序排一下，其实就是沉淀，把swap
: 后的数字沉淀到符合排序的最后位置， bingo
|
s**x
发帖数: 7506 | 45
其实好多人搞不明白 写 code 和 算法的关系， 二者几乎没有任何关系。 现在大部
分公司都在考算法。
【在 c****e 的大作中提到】
: 虽然才工作一年，但是最近组里要招一个senior software engineer，所以也面试了不
: 少人
: 工作十年以上的码工基本都有很多东西可以侃，而作为新人我也很少去质疑他们
: 不过每次我都会出同样的一个编程题，一来很多人都声称自己在写code，而且我也不要
: 求他们写，只是要听一下他们的思路，看问题的角度
: 我的问题是Leetcode上的原题叫next permutation，找一个比当前数字大的最小数
: 好像面到现在十来个人，没有一个的答案是让我觉得满意的，思路都很混乱
: 我之所以上来发帖是因为刚刚面的这个老印真的是差到极点，直接摊手说不会，给什么
: 提示都不行
: 这个问题是太难了？还是我问的不对？还是说作软件十年以上就靠侃了，我不应该再问
|
