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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 第二题一点都不难。如果原数本身不是回文的话，设它长度是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 的大作中提到】
: 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 的大作中提到】
: 我不确定的是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 的大作中提到】
: 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 的大作中提到】
: 我不确定的是1999->2002这种怎么处理，貌似就是你说的第二种情况单独去试？要对各
: 个位都试？
|
r*******g
发帖数: 1335 | 12 貌似是对的，thanks
）。这样再求大于
【在 f*******t 的大作中提到】
: 1999->1991
: 1991 < 1999
: 所以第三位加1，变成2099
: 2099->2002
: 2002 - 1999 < 1999 - 1991
: 第一步生成的数如果小于原数，说明小于原数的最接近回文数肯定是它了（大于同理）。这样再求大于
: 原数的最接近回文数，通过把(x/2+1)位加1生成另一个回文数（大于时就是减1）。
|
r*******g
发帖数: 1335 | 13 依然不明白，求详细解答？每次怎么遍历的？都是从左到右？他们之间什么关系？？？
【在 l*****a 的大作中提到】
: 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 的大作中提到】
: 第二题一点都不难。如果原数本身不是回文的话，设它长度是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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 第二题一点都不难。如果原数本身不是回文的话，设它长度是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 的大作中提到】
: 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 的大作中提到】
: 我不确定的是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 的大作中提到】
: 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 的大作中提到】
: 我不确定的是1999->2002这种怎么处理，貌似就是你说的第二种情况单独去试？要对各
: 个位都试？
|
r*******g
发帖数: 1335 | 27 貌似是对的，thanks
）。这样再求大于
【在 f*******t 的大作中提到】
: 1999->1991
: 1991 < 1999
: 所以第三位加1，变成2099
: 2099->2002
: 2002 - 1999 < 1999 - 1991
: 第一步生成的数如果小于原数，说明小于原数的最接近回文数肯定是它了（大于同理）。这样再求大于
: 原数的最接近回文数，通过把(x/2+1)位加1生成另一个回文数（大于时就是减1）。
|
r*******g
发帖数: 1335 | 28 依然不明白，求详细解答？每次怎么遍历的？都是从左到右？他们之间什么关系？？？
【在 l*****a 的大作中提到】
: 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 的大作中提到】
: 第二题一点都不难。如果原数本身不是回文的话，设它长度是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 的大作中提到】
: 第四和第五题怎么做，求解答。
|
g**********y
发帖数: 14569 | 33 从你的例子看：第5题允许不连续？从大到小把数字去掉？ |
r*******g
发帖数: 1335 | 34 汗，应该例子给错了，我晕，否则岂不是很简单了。。。
【在 g**********y 的大作中提到】
: 从你的例子看：第5题允许不连续？从大到小把数字去掉？
|
r*******g
发帖数: 1335 | 35 very clever, this question might not ask for algorithm....
you are so clever. .....
【在 g**********y 的大作中提到】
: 第四题是说只交换1，2，而其它不变。那个用奇偶性可以证明，应该是不可能。
|
f*******t
发帖数: 7549 | 36 第4题原来是这个意思，面试时候想反应过来真不容易。。 |
