求问个G家面试题# JobHunting - 待字闺中
P*d
1 楼
这道题本身就有点难懂,我要问了差不多5-10分钟才搞懂题意,输入是一个String
Array,比如{"dog","cat","mouse"},那么他就有以下六个permutation:
{"dog","cat","mouse"}
{"dog","mouse","cat"}
{"cat","mouse","dog"}
{"cat","dog","mouse"}
{"mouse","dog","cat"}
{"mouse","cat","dog"}
他要你实现serialize 和deseriallize两个方法
其中serialize的方法输入的第一个参数是输入String数组,输出是他的一个
permutation,至于是哪一个permutation,取决于serialize的方法的第二个参数。至
于第二个参数是什么,需要你自己设计
我当时设计的是第二个参数用一个int数组,int数组在每一个位置的数字,代表输入
String Array该位置上的String,在permutation数组中的位置,比如如果输入时{"dog
","cat","mouse"},辅助参数我设计的是{2,1,3},那么输出就是{"cat", "dog", "
mouse"},要求实现这个变换是in place 操作,就是说,对于输出数组,你不能新开一
个String Array作为输出数组,你也不能使用额外空间.
我当时就是这么设计的,但是还是有问题,比如认为规定,辅助参数数组里的数字是原
数String数组里的该位置的String在Permutation里的新位置
比如
{"cat", "dog", "mouse","bird"}
辅助参数是int 数组
{2, 3,1, 4},那么结果就应该是{"mouse", "cat", "dog", "bird"}
我一开始想的是只用一个tmp变量存储中间结果,(所以还是in place)
你第一个dog,把第二个cat改成 dog ,临时变量存储cat,然后查找 int array,第二
个,把第三个bird放到临时变量里,然后把cat写入到bird那个位置,然后看int array
3,然后把bird也到dog里,然后查看int array第一个位置,是2,然后看2已经是DOG
,这轮操作结束
然后面临一个问题,下一轮你要处理的元素是哪个元素?你这时候当然可以说前三个元
素你都处理了,那剩下的就是第4个元素,但程序运行到这个时候,计算机怎么知道你
前三个元素都处理了,我当时回答是用一个boolean array,然后处理过的位置就mark
成true,然后这个时候走到第二个位置,看到已经变成true了,然后走到第三个位置,
直到第四个位置
但用Bool数组这样就相当于用了额外空间了,就是错的
后来我又答:
还是用一个int数组做输入辅助变量,不过更改人为定义,这个时候数字不代表输入
String数组中String在permu中要去的位置,而是说输出数组该位置中,要用输入
String的里的哪个位置拿数,例子还是如上,
{"cat", "dog", "mouse","bird"}
辅助参数是int 数组
{2, 3,1, 4},
那么这样结果就应该是{"dog","mouse", "cat","bird"}
然后
因为位置1,permutation=2,把第一个cat存入temp,直接把位置2的dog赋值到第一个
位置,这个时候变成dog,dog,mouse,bird, temp=dog,第二个位置的时候,因为位置为
2,permutation=3,所以直接把mouse赋值到第二个位置,变成dog mouse mouse bird
,temp=dog,第三个位置为3,permutation=1,把temp赋给第三个位置,变成dog
mouse cat bird,
但这样还是有问题,因为在第三部的时候,无法知道Tmp里那个值就是从第一个位置来
的,而且在一个很长的输入String数组的时候,很可能用一个tmp变量记录根本不够,
当时算了一下,worse case需要 n/2个tmp变量,所以这样还是错的
最后没忍住问了面试官到底要怎么做,面试官说我这个辅助参数的设计本身就是错的,
用一个int数组表示permu的形式,you can do nothing better。
求问一下版上大牛,这题到底应该怎么做
谢啦
Array,比如{"dog","cat","mouse"},那么他就有以下六个permutation:
{"dog","cat","mouse"}
{"dog","mouse","cat"}
{"cat","mouse","dog"}
{"cat","dog","mouse"}
{"mouse","dog","cat"}
{"mouse","cat","dog"}
他要你实现serialize 和deseriallize两个方法
其中serialize的方法输入的第一个参数是输入String数组,输出是他的一个
permutation,至于是哪一个permutation,取决于serialize的方法的第二个参数。至
于第二个参数是什么,需要你自己设计
我当时设计的是第二个参数用一个int数组,int数组在每一个位置的数字,代表输入
String Array该位置上的String,在permutation数组中的位置,比如如果输入时{"dog
","cat","mouse"},辅助参数我设计的是{2,1,3},那么输出就是{"cat", "dog", "
mouse"},要求实现这个变换是in place 操作,就是说,对于输出数组,你不能新开一
个String Array作为输出数组,你也不能使用额外空间.
我当时就是这么设计的,但是还是有问题,比如认为规定,辅助参数数组里的数字是原
数String数组里的该位置的String在Permutation里的新位置
比如
{"cat", "dog", "mouse","bird"}
辅助参数是int 数组
{2, 3,1, 4},那么结果就应该是{"mouse", "cat", "dog", "bird"}
我一开始想的是只用一个tmp变量存储中间结果,(所以还是in place)
你第一个dog,把第二个cat改成 dog ,临时变量存储cat,然后查找 int array,第二
个,把第三个bird放到临时变量里,然后把cat写入到bird那个位置,然后看int array
3,然后把bird也到dog里,然后查看int array第一个位置,是2,然后看2已经是DOG
,这轮操作结束
然后面临一个问题,下一轮你要处理的元素是哪个元素?你这时候当然可以说前三个元
素你都处理了,那剩下的就是第4个元素,但程序运行到这个时候,计算机怎么知道你
前三个元素都处理了,我当时回答是用一个boolean array,然后处理过的位置就mark
成true,然后这个时候走到第二个位置,看到已经变成true了,然后走到第三个位置,
直到第四个位置
但用Bool数组这样就相当于用了额外空间了,就是错的
后来我又答:
还是用一个int数组做输入辅助变量,不过更改人为定义,这个时候数字不代表输入
String数组中String在permu中要去的位置,而是说输出数组该位置中,要用输入
String的里的哪个位置拿数,例子还是如上,
{"cat", "dog", "mouse","bird"}
辅助参数是int 数组
{2, 3,1, 4},
那么这样结果就应该是{"dog","mouse", "cat","bird"}
然后
因为位置1,permutation=2,把第一个cat存入temp,直接把位置2的dog赋值到第一个
位置,这个时候变成dog,dog,mouse,bird, temp=dog,第二个位置的时候,因为位置为
2,permutation=3,所以直接把mouse赋值到第二个位置,变成dog mouse mouse bird
,temp=dog,第三个位置为3,permutation=1,把temp赋给第三个位置,变成dog
mouse cat bird,
但这样还是有问题,因为在第三部的时候,无法知道Tmp里那个值就是从第一个位置来
的,而且在一个很长的输入String数组的时候,很可能用一个tmp变量记录根本不够,
当时算了一下,worse case需要 n/2个tmp变量,所以这样还是错的
最后没忍住问了面试官到底要怎么做,面试官说我这个辅助参数的设计本身就是错的,
用一个int数组表示permu的形式,you can do nothing better。
求问一下版上大牛,这题到底应该怎么做
谢啦