Interview question from Yahoo# JobHunting - 待字闺中
a*h
1 楼
given a string, how to do a string rotation without using extra memory?
m*f
2 楼
什么叫做string rotation?
a*n
3 楼
reverse whole string
reverse first part
reverse second part
reverse first part
reverse second part
r*o
4 楼
问问，没有额外存储空间怎么reverse string?
【在 a****n 的大作中提到】
: reverse whole string
: reverse first part
: reverse second part
【在 a****n 的大作中提到】
: reverse whole string
: reverse first part
: reverse second part
m*f
5 楼
swap就可以拉
【在 r****o 的大作中提到】
: 问问，没有额外存储空间怎么reverse string?
【在 r****o 的大作中提到】
: 问问，没有额外存储空间怎么reverse string?
g*y
6 楼
两种方法
一种是swap(circularly)，利用到最小公约数
一种是flip 3次
【在 a******h 的大作中提到】
: given a string, how to do a string rotation without using extra memory?
一种是swap(circularly)，利用到最小公约数
一种是flip 3次
【在 a******h 的大作中提到】
: given a string, how to do a string rotation without using extra memory?
a*h
7 楼
Could you explain swap circularly?
【在 g*******y 的大作中提到】
: 两种方法
: 一种是swap(circularly)，利用到最小公约数
: 一种是flip 3次
【在 g*******y 的大作中提到】
: 两种方法
: 一种是swap(circularly)，利用到最小公约数
: 一种是flip 3次
n*r
8 楼
swap不需要额外空间？
【在 m*****f 的大作中提到】
: swap就可以拉
【在 m*****f 的大作中提到】
: swap就可以拉
g*y
9 楼
这个是无比经典的问题了。。。
假设前4个数和后6个数rotate，
最小公约数2
4/2=2
6/2=3
得到的2，3必然互质
再用一点点基本的数论，两个数p,q互质的话，{i*p%(p+q) | i=0...(p+q)-1} 刚好是
集合｛0...p+q-1}的一个循环遍历
【在 a******h 的大作中提到】
: Could you explain swap circularly?
假设前4个数和后6个数rotate，
最小公约数2
4/2=2
6/2=3
得到的2，3必然互质
再用一点点基本的数论，两个数p,q互质的话，{i*p%(p+q) | i=0...(p+q)-1} 刚好是
集合｛0...p+q-1}的一个循环遍历
【在 a******h 的大作中提到】
: Could you explain swap circularly?
r*o
10 楼
还是不明白，swap不用临时变量吗?
【在 m*****f 的大作中提到】
: swap就可以拉
【在 m*****f 的大作中提到】
: swap就可以拉
g*y
11 楼
两种方法空间差不多，都只要2，3个指针，后者最多再多用一个char temp。flip时间
慢个常数因子。
【在 n******r 的大作中提到】
: swap不需要额外空间？
慢个常数因子。
【在 n******r 的大作中提到】
: swap不需要额外空间？
a*h
12 楼
What is 前4个数和后6个数rotate ?
Suppose you have a string "abcdef" and right rotate 4.
How to apply your GCD in this case?
【在 g*******y 的大作中提到】
: 这个是无比经典的问题了。。。
: 假设前4个数和后6个数rotate，
: 最小公约数2
: 4/2=2
: 6/2=3
: 得到的2，3必然互质
: 再用一点点基本的数论，两个数p,q互质的话，{i*p%(p+q) | i=0...(p+q)-1} 刚好是
: 集合｛0...p+q-1}的一个循环遍历
Suppose you have a string "abcdef" and right rotate 4.
How to apply your GCD in this case?
【在 g*******y 的大作中提到】
: 这个是无比经典的问题了。。。
: 假设前4个数和后6个数rotate，
: 最小公约数2
: 4/2=2
: 6/2=3
: 得到的2，3必然互质
: 再用一点点基本的数论，两个数p,q互质的话，{i*p%(p+q) | i=0...(p+q)-1} 刚好是
: 集合｛0...p+q-1}的一个循环遍历
a*n
13 楼
不要临时变量的
swap(T& a, T& b)
{
a = a^b
b = a^b
a = a^b
}
【在 r****o 的大作中提到】
: 还是不明白，swap不用临时变量吗?
swap(T& a, T& b)
{
a = a^b
b = a^b
a = a^b
}
【在 r****o 的大作中提到】
: 还是不明白，swap不用临时变量吗?
g*y
14 楼
012345678 -> 4567890123
【在 a******h 的大作中提到】
: What is 前4个数和后6个数rotate ?
: Suppose you have a string "abcdef" and right rotate 4.
: How to apply your GCD in this case?
【在 a******h 的大作中提到】
: What is 前4个数和后6个数rotate ?
: Suppose you have a string "abcdef" and right rotate 4.
: How to apply your GCD in this case?
a*h
15 楼
This is string length of 9. So could you explain your gcd in this case?
【在 g*******y 的大作中提到】
: 012345678 -> 4567890123
【在 g*******y 的大作中提到】
: 012345678 -> 4567890123
r*o
16 楼
flip是什么意思？bit operation吗？
【在 g*******y 的大作中提到】
: 两种方法
: 一种是swap(circularly)，利用到最小公约数
: 一种是flip 3次
【在 g*******y 的大作中提到】
: 两种方法
: 一种是swap(circularly)，利用到最小公约数
: 一种是flip 3次
H*M
17 楼
we need AB ->BA
can use:
(A'B')' = BA
【在 r****o 的大作中提到】
: flip是什么意思？bit operation吗？
can use:
(A'B')' = BA
【在 r****o 的大作中提到】
: flip是什么意思？bit operation吗？
r*o
18 楼
能不能再详细说说阿，
遍历集合{0...p+q-1}之后再咋弄呢？
【在 g*******y 的大作中提到】
: 这个是无比经典的问题了。。。
: 假设前4个数和后6个数rotate，
: 最小公约数2
: 4/2=2
: 6/2=3
: 得到的2，3必然互质
: 再用一点点基本的数论，两个数p,q互质的话，{i*p%(p+q) | i=0...(p+q)-1} 刚好是
: 集合｛0...p+q-1}的一个循环遍历
遍历集合{0...p+q-1}之后再咋弄呢？
【在 g*******y 的大作中提到】
: 这个是无比经典的问题了。。。
: 假设前4个数和后6个数rotate，
: 最小公约数2
: 4/2=2
: 6/2=3
: 得到的2，3必然互质
: 再用一点点基本的数论，两个数p,q互质的话，{i*p%(p+q) | i=0...(p+q)-1} 刚好是
: 集合｛0...p+q-1}的一个循环遍历
g*y
19 楼
按这个次序挨个挪动数
比如 12345 -> 34512
1开始，
1挪到4的位置
4挪到2的位置
2挪到5的位置
5挪到3的位置
3挪到1的位置
然后你发现走了一圈走回1了，就结束了。
【在 r****o 的大作中提到】
: 能不能再详细说说阿，
: 遍历集合{0...p+q-1}之后再咋弄呢？
比如 12345 -> 34512
1开始，
1挪到4的位置
4挪到2的位置
2挪到5的位置
5挪到3的位置
3挪到1的位置
然后你发现走了一圈走回1了，就结束了。
【在 r****o 的大作中提到】
: 能不能再详细说说阿，
: 遍历集合{0...p+q-1}之后再咋弄呢？
a*h
20 楼
// only needs gcd(strLen, k) times circular swap
// this function supports right rotation only
public static String rotateStr(String str, int k) {
if (str == null)
return null;
if (k == 0 || str.length() == k)
return str;
if (k < 0)
throw new InvalidParameterException();
char [] arr = str.toCharArray();
int gcd = findGCD(str.length(), k);
for (int i = 0; i < gcd; i++) {
// this function supports right rotation only
public static String rotateStr(String str, int k) {
if (str == null)
return null;
if (k == 0 || str.length() == k)
return str;
if (k < 0)
throw new InvalidParameterException();
char [] arr = str.toCharArray();
int gcd = findGCD(str.length(), k);
for (int i = 0; i < gcd; i++) {
k*e
21 楼
唉 你怎么老是有保留呢
有三种方法
programming pearl chap 2 （如果没记错的话）
【在 g*******y 的大作中提到】
: 两种方法
: 一种是swap(circularly)，利用到最小公约数
: 一种是flip 3次
有三种方法
programming pearl chap 2 （如果没记错的话）
【在 g*******y 的大作中提到】
: 两种方法
: 一种是swap(circularly)，利用到最小公约数
: 一种是flip 3次
g*y
22 楼
我真的只知道有两种。。。你说说第三种是什么？pearl我看得很水。。。
【在 k***e 的大作中提到】
: 唉 你怎么老是有保留呢
: 有三种方法
: programming pearl chap 2 （如果没记错的话）
【在 k***e 的大作中提到】
: 唉 你怎么老是有保留呢
: 有三种方法
: programming pearl chap 2 （如果没记错的话）
相关阅读
opening for junior digital IP designer in a SF bay area companyHow to find a particular phone number among lots of filemonster网站很挫啊，怪不得江河日下了。关于H1B transfer的问题[转贴] full time Software QA engineer 湾区 可办h1b&绿卡 无需工作经验憋屈的要跳楼了 (转载)我这种情况跳槽工资要求涨多少为好?FY2011第三季度的h1b(LCA)数据出来了h1bwage.com的工资靠谱吗？phone interview的问题见recruiter的 interview需要穿什么？真心求教：关于绿卡how long h1transferh1b 申请郁闷了我明白了，高级recruiter都是work from home有多少学校的200～299字头的课是研究生课程的国内的硕士可以申请H-1B Premium 么？Amazon 二面 怎么筛选的？拿到北京的offer面试完了把manager的name card 留在conference room了咋个办？