r*******g 发帖数: 1335 | 1 hi
考古发现以前题似乎更难一些,不知道是不是错觉
1,从一个string 变到另一个,比如"study"->"world" (字数相等),要求
每次变一个字母,每次改变后的string必须是一个词典里面能查到的英语单词,比如你
不能把study变
成atudy
由于加了个条件,不知道最后讨论出来什么办法更好,似乎还是没有定论?
2, Given an integer, print the closest number to it that is a palindrome
input: 1224
return: 1221.
这个题仔细一想一点都不简单,关键是,最closet的数可能和原来的数完全不一样,怎
么弄?
3, In our indexes, we have millions of URLs each of which has a link to the
page content, now, suppose a user type a query with wild cards *, which
represent 0 or multiple occcurrences of any characters, how to build the
index such that such a type of query can be executed efficiently and the
contents of all correpsonding URLs can be displayed to the users? For
example, given a query http://www.*o*ve*ou.com. You man need to find iloveyou.com, itveabcu.com, etc.
这个题,不是拿pattern去匹配一个wildcarded单词,而是总体的,感觉很不容易想。
4,Given a 3x3 square:
1 2 3
4 5 6
7 8 9
You are allowed to do circular shift on any row, and
circular shift on any column, as many times as you
please. Question: can you switch position of 1 and 2 with
the allowed circular shifts?
这个不就是魔方么。。。原来还有算法的。。。
5, Given an array, find the longest subarray which the sum of the subarray
less or equal then the given MaxSum.
int[] FindMaxSumArray(int[] array, int maxsum)
for example, given array: {1, -2, 4, 5, -2, 6, 7}
maxsum=7
the result would be: {1,-2, 4, -2, 6}
貌似是max sum subarry的变型,但是显然不是那个思路,一下子没想起来。
多谢。 |
l*****a 发帖数: 14598 | 2 1.谁说没定论?
用字典中所有与你输入单词相同长度的单词生成一个matrix
if there is only one letter difference between word[m] and word[n]
then matrix[m][n]=1
then just find whether there is a path from word[input] to word[output]
use BFS to do traverse will be enough
【在 r*******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : hi : 考古发现以前题似乎更难一些,不知道是不是错觉 : 1,从一个string 变到另一个,比如"study"->"world" (字数相等),要求 : 每次变一个字母,每次改变后的string必须是一个词典里面能查到的英语单词,比如你 : 不能把study变 : 成atudy : 由于加了个条件,不知道最后讨论出来什么办法更好,似乎还是没有定论? : 2, Given an integer, print the closest number to it that is a palindrome : input: 1224 : return: 1221.
|
l*****a 发帖数: 14598 | 3 3.整体跟部分有什么区别
if u want to match
http://www.*o*ve*ou.com
match http://www and ou.com at first
then u just need to judge the pattern
【在 r*******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : hi : 考古发现以前题似乎更难一些,不知道是不是错觉 : 1,从一个string 变到另一个,比如"study"->"world" (字数相等),要求 : 每次变一个字母,每次改变后的string必须是一个词典里面能查到的英语单词,比如你 : 不能把study变 : 成atudy : 由于加了个条件,不知道最后讨论出来什么办法更好,似乎还是没有定论? : 2, Given an integer, print the closest number to it that is a palindrome : input: 1224 : return: 1221.
|
l*****a 发帖数: 14598 | 4 5.
find the sum of longest array <= given value
transfer it to
find the sum of shortest array >= given value
the two parts will start from the beginning of the array and
the tail of the array.
then...
【在 r*******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : hi : 考古发现以前题似乎更难一些,不知道是不是错觉 : 1,从一个string 变到另一个,比如"study"->"world" (字数相等),要求 : 每次变一个字母,每次改变后的string必须是一个词典里面能查到的英语单词,比如你 : 不能把study变 : 成atudy : 由于加了个条件,不知道最后讨论出来什么办法更好,似乎还是没有定论? : 2, Given an integer, print the closest number to it that is a palindrome : input: 1224 : return: 1221.
|
f*******t 发帖数: 7549 | 5 第二题一点都不难。如果原数本身不是回文的话,设它长度是x,改变后(x/2)个数字,
使之与前半对应成为回文,与原数的差距肯定在10^(x/2+1)之间。
比如1234,变成1221,差距不超过100。
不过还有另一种选择,就是将第(x/2+1)个数字加1或减1,再构成回文。例:1299,如
果变成1221,差是78,但如果变成1331,差就只有32了。
我觉得就只有这两种情况,所以其实不难。。。 |
r*******g 发帖数: 1335 | 6 我不确定的是1999->2002这种怎么处理,貌似就是你说的第二种情况单独去试?要对各
个位都试?
【在 f*******t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第二题一点都不难。如果原数本身不是回文的话,设它长度是x,改变后(x/2)个数字, : 使之与前半对应成为回文,与原数的差距肯定在10^(x/2+1)之间。 : 比如1234,变成1221,差距不超过100。 : 不过还有另一种选择,就是将第(x/2+1)个数字加1或减1,再构成回文。例:1299,如 : 果变成1221,差是78,但如果变成1331,差就只有32了。 : 我觉得就只有这两种情况,所以其实不难。。。
|
y*******g 发帖数: 6599 | |
r*******g 发帖数: 1335 | 8 thanks
这个题其实比原来题还简单些,因为限定了只能每次改一个字母。
这样的话其实就是做递归做bfs,不用生成matrix也可以,不过空间开销肯定不会小。
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 1.谁说没定论? : 用字典中所有与你输入单词相同长度的单词生成一个matrix : if there is only one letter difference between word[m] and word[n] : then matrix[m][n]=1 : then just find whether there is a path from word[input] to word[output] : use BFS to do traverse will be enough
|
d*******l 发帖数: 338 | 9 我觉得楼上说的是对的,只要考虑前半部分和前半部分加减一之后构成的3个回文串,
分别试试就行。
你说的这个情况就试1991 2002 1881这三个就行。
【在 r*******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我不确定的是1999->2002这种怎么处理,貌似就是你说的第二种情况单独去试?要对各 : 个位都试?
|
r*******g 发帖数: 1335 | 10 我看你前面回的,如果单个pattern,生成状态转换表,然后对输入
比方说 a*b
initial state s[0],
f(s[0],a)=s[1]
f(s[1],a...)=s[1]
f(s[1],b)=s[2]
现在这里所有已有链接生成一个状态转换表?
如果用suffixtree似乎也不大好。
你说的match一头一尾,难道要单独存储所有pattern的头和尾?
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 3.整体跟部分有什么区别 : if u want to match : http://www.*o*ve*ou.com : match http://www and ou.com at first : then u just need to judge the pattern
|
|
|
f*******t 发帖数: 7549 | 11 1999->1991
1991 < 1999
所以第三位加1,变成2099
2099->2002
2002 - 1999 < 1999 - 1991
第一步生成的数如果小于原数,说明小于原数的最接近回文数肯定是它了(大于同理)。这样再求大于
原数的最接近回文数,通过把(x/2+1)位加1生成另一个回文数(大于时就是减1)。
【在 r*******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我不确定的是1999->2002这种怎么处理,貌似就是你说的第二种情况单独去试?要对各 : 个位都试?
|
r*******g 发帖数: 1335 | 12 貌似是对的,thanks
)。这样再求大于
【在 f*******t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 1999->1991 : 1991 < 1999 : 所以第三位加1,变成2099 : 2099->2002 : 2002 - 1999 < 1999 - 1991 : 第一步生成的数如果小于原数,说明小于原数的最接近回文数肯定是它了(大于同理)。这样再求大于 : 原数的最接近回文数,通过把(x/2+1)位加1生成另一个回文数(大于时就是减1)。
|
r*******g 发帖数: 1335 | 13 依然不明白,求详细解答?每次怎么遍历的?都是从左到右?他们之间什么关系???
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 5. : find the sum of longest array <= given value : transfer it to : find the sum of shortest array >= given value : the two parts will start from the beginning of the array and : the tail of the array. : then...
|
g*****i 发帖数: 2162 | 14 很巧妙的思路,赞一个
【在 f*******t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第二题一点都不难。如果原数本身不是回文的话,设它长度是x,改变后(x/2)个数字, : 使之与前半对应成为回文,与原数的差距肯定在10^(x/2+1)之间。 : 比如1234,变成1221,差距不超过100。 : 不过还有另一种选择,就是将第(x/2+1)个数字加1或减1,再构成回文。例:1299,如 : 果变成1221,差是78,但如果变成1331,差就只有32了。 : 我觉得就只有这两种情况,所以其实不难。。。
|
e***s 发帖数: 799 | 15 第一题还是不清楚,有没有link可以看一下,谢谢! |
r*******g 发帖数: 1335 | 16 hi
考古发现以前题似乎更难一些,不知道是不是错觉
1,从一个string 变到另一个,比如"study"->"world" (字数相等),要求
每次变一个字母,每次改变后的string必须是一个词典里面能查到的英语单词,比如你
不能把study变
成atudy
由于加了个条件,不知道最后讨论出来什么办法更好,似乎还是没有定论?
2, Given an integer, print the closest number to it that is a palindrome
input: 1224
return: 1221.
这个题仔细一想一点都不简单,关键是,最closet的数可能和原来的数完全不一样,怎
么弄?
3, In our indexes, we have millions of URLs each of which has a link to the
page content, now, suppose a user type a query with wild cards *, which
represent 0 or multiple occcurrences of any characters, how to build the
index such that such a type of query can be executed efficiently and the
contents of all correpsonding URLs can be displayed to the users? For
example, given a query http://www.*o*ve*ou.com. You man need to find iloveyou.com, itveabcu.com, etc.
这个题,不是拿pattern去匹配一个wildcarded单词,而是总体的,感觉很不容易想。
4,Given a 3x3 square:
1 2 3
4 5 6
7 8 9
You are allowed to do circular shift on any row, and
circular shift on any column, as many times as you
please. Question: can you switch position of 1 and 2 with
the allowed circular shifts?
这个不就是魔方么。。。原来还有算法的。。。
5, Given an array, find the longest subarray which the sum of the subarray
less or equal then the given MaxSum.
int[] FindMaxSumArray(int[] array, int maxsum)
for example, given array: {1, -2, 4, 5, -2, 6, 7}
maxsum=7
the result would be: {1,-2, 4, -2, 6}
貌似是max sum subarry的变型,但是显然不是那个思路,一下子没想起来。
多谢。 |
l*****a 发帖数: 14598 | 17 1.谁说没定论?
用字典中所有与你输入单词相同长度的单词生成一个matrix
if there is only one letter difference between word[m] and word[n]
then matrix[m][n]=1
then just find whether there is a path from word[input] to word[output]
use BFS to do traverse will be enough
【在 r*******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : hi : 考古发现以前题似乎更难一些,不知道是不是错觉 : 1,从一个string 变到另一个,比如"study"->"world" (字数相等),要求 : 每次变一个字母,每次改变后的string必须是一个词典里面能查到的英语单词,比如你 : 不能把study变 : 成atudy : 由于加了个条件,不知道最后讨论出来什么办法更好,似乎还是没有定论? : 2, Given an integer, print the closest number to it that is a palindrome : input: 1224 : return: 1221.
|
l*****a 发帖数: 14598 | 18 3.整体跟部分有什么区别
if u want to match
http://www.*o*ve*ou.com
match http://www and ou.com at first
then u just need to judge the pattern
【在 r*******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : hi : 考古发现以前题似乎更难一些,不知道是不是错觉 : 1,从一个string 变到另一个,比如"study"->"world" (字数相等),要求 : 每次变一个字母,每次改变后的string必须是一个词典里面能查到的英语单词,比如你 : 不能把study变 : 成atudy : 由于加了个条件,不知道最后讨论出来什么办法更好,似乎还是没有定论? : 2, Given an integer, print the closest number to it that is a palindrome : input: 1224 : return: 1221.
|
l*****a 发帖数: 14598 | 19 5.
find the sum of longest array <= given value
transfer it to
find the sum of shortest array >= given value
the two parts will start from the beginning of the array and
the tail of the array.
then...
【在 r*******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : hi : 考古发现以前题似乎更难一些,不知道是不是错觉 : 1,从一个string 变到另一个,比如"study"->"world" (字数相等),要求 : 每次变一个字母,每次改变后的string必须是一个词典里面能查到的英语单词,比如你 : 不能把study变 : 成atudy : 由于加了个条件,不知道最后讨论出来什么办法更好,似乎还是没有定论? : 2, Given an integer, print the closest number to it that is a palindrome : input: 1224 : return: 1221.
|
f*******t 发帖数: 7549 | 20 第二题一点都不难。如果原数本身不是回文的话,设它长度是x,改变后(x/2)个数字,
使之与前半对应成为回文,与原数的差距肯定在10^(x/2+1)之间。
比如1234,变成1221,差距不超过100。
不过还有另一种选择,就是将第(x/2+1)个数字加1或减1,再构成回文。例:1299,如
果变成1221,差是78,但如果变成1331,差就只有32了。
我觉得就只有这两种情况,所以其实不难。。。 |
|
|
r*******g 发帖数: 1335 | 21 我不确定的是1999->2002这种怎么处理,貌似就是你说的第二种情况单独去试?要对各
个位都试?
【在 f*******t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第二题一点都不难。如果原数本身不是回文的话,设它长度是x,改变后(x/2)个数字, : 使之与前半对应成为回文,与原数的差距肯定在10^(x/2+1)之间。 : 比如1234,变成1221,差距不超过100。 : 不过还有另一种选择,就是将第(x/2+1)个数字加1或减1,再构成回文。例:1299,如 : 果变成1221,差是78,但如果变成1331,差就只有32了。 : 我觉得就只有这两种情况,所以其实不难。。。
|
y*******g 发帖数: 6599 | |
r*******g 发帖数: 1335 | 23 thanks
这个题其实比原来题还简单些,因为限定了只能每次改一个字母。
这样的话其实就是做递归做bfs,不用生成matrix也可以,不过空间开销肯定不会小。
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 1.谁说没定论? : 用字典中所有与你输入单词相同长度的单词生成一个matrix : if there is only one letter difference between word[m] and word[n] : then matrix[m][n]=1 : then just find whether there is a path from word[input] to word[output] : use BFS to do traverse will be enough
|
d*******l 发帖数: 338 | 24 我觉得楼上说的是对的,只要考虑前半部分和前半部分加减一之后构成的3个回文串,
分别试试就行。
你说的这个情况就试1991 2002 1881这三个就行。
【在 r*******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我不确定的是1999->2002这种怎么处理,貌似就是你说的第二种情况单独去试?要对各 : 个位都试?
|
r*******g 发帖数: 1335 | 25 我看你前面回的,如果单个pattern,生成状态转换表,然后对输入
比方说 a*b
initial state s[0],
f(s[0],a)=s[1]
f(s[1],a...)=s[1]
f(s[1],b)=s[2]
现在这里所有已有链接生成一个状态转换表?
如果用suffixtree似乎也不大好。
你说的match一头一尾,难道要单独存储所有pattern的头和尾?
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 3.整体跟部分有什么区别 : if u want to match : http://www.*o*ve*ou.com : match http://www and ou.com at first : then u just need to judge the pattern
|
f*******t 发帖数: 7549 | 26 1999->1991
1991 < 1999
所以第三位加1,变成2099
2099->2002
2002 - 1999 < 1999 - 1991
第一步生成的数如果小于原数,说明小于原数的最接近回文数肯定是它了(大于同理)。这样再求大于
原数的最接近回文数,通过把(x/2+1)位加1生成另一个回文数(大于时就是减1)。
【在 r*******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我不确定的是1999->2002这种怎么处理,貌似就是你说的第二种情况单独去试?要对各 : 个位都试?
|
r*******g 发帖数: 1335 | 27 貌似是对的,thanks
)。这样再求大于
【在 f*******t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 1999->1991 : 1991 < 1999 : 所以第三位加1,变成2099 : 2099->2002 : 2002 - 1999 < 1999 - 1991 : 第一步生成的数如果小于原数,说明小于原数的最接近回文数肯定是它了(大于同理)。这样再求大于 : 原数的最接近回文数,通过把(x/2+1)位加1生成另一个回文数(大于时就是减1)。
|
r*******g 发帖数: 1335 | 28 依然不明白,求详细解答?每次怎么遍历的?都是从左到右?他们之间什么关系???
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 5. : find the sum of longest array <= given value : transfer it to : find the sum of shortest array >= given value : the two parts will start from the beginning of the array and : the tail of the array. : then...
|
g*****i 发帖数: 2162 | 29 很巧妙的思路,赞一个
【在 f*******t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第二题一点都不难。如果原数本身不是回文的话,设它长度是x,改变后(x/2)个数字, : 使之与前半对应成为回文,与原数的差距肯定在10^(x/2+1)之间。 : 比如1234,变成1221,差距不超过100。 : 不过还有另一种选择,就是将第(x/2+1)个数字加1或减1,再构成回文。例:1299,如 : 果变成1221,差是78,但如果变成1331,差就只有32了。 : 我觉得就只有这两种情况,所以其实不难。。。
|
e***s 发帖数: 799 | 30 第一题还是不清楚,有没有link可以看一下,谢谢! |
|
|
r*******g 发帖数: 1335 | |
g**********y 发帖数: 14569 | 32 第四题是说只交换1,2,而其它不变。那个用奇偶性可以证明,应该是不可能。
【在 r*******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第四和第五题怎么做,求解答。
|
g**********y 发帖数: 14569 | 33 从你的例子看:第5题允许不连续?从大到小把数字去掉? |
r*******g 发帖数: 1335 | 34 汗,应该例子给错了,我晕,否则岂不是很简单了。。。
【在 g**********y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 从你的例子看:第5题允许不连续?从大到小把数字去掉?
|
r*******g 发帖数: 1335 | 35 very clever, this question might not ask for algorithm....
you are so clever. .....
【在 g**********y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第四题是说只交换1,2,而其它不变。那个用奇偶性可以证明,应该是不可能。
|
f*******t 发帖数: 7549 | 36 第4题原来是这个意思,面试时候想反应过来真不容易。。 |