l********r
发帖数: 187 | 1 Hi,
I got an programming problem from Microsoft for screening purpose. Does
anyone has good idea about it? I am particularly puzzled by the second given
example. Thanks.
“bool F(string s, char ch1, char ch2, int n)”
The function determines whether or not there exists an occurrence of ch1 and
ch2 separated by a distance of no more than n in the given string s, where
s is ascii and user entered (your function needs to work on any input.) The
function must be efficient and **optimized** for both space and time. Please
state what the complexity of your solution is.
Examples:
“abcdefg”, ‘b’, ‘d’, 2 --> true
“abcdefg”, ‘b’, ‘d’, 20 --> true
“abcdefg”, ‘b’, ‘e’, 1 --> false |
l*****a
发帖数: 14598 | 2 1)经典题简化
2）职业杯150上有类似的
3）he asked no more than,why u confused?
any number above 1 will return true
Does
given
ch1 and
where
input.) The
Please
【在 l********r 的大作中提到】
: Hi,
: I got an programming problem from Microsoft for screening purpose. Does
: anyone has good idea about it? I am particularly puzzled by the second given
: example. Thanks.
: “bool F(string s, char ch1, char ch2, int n)”
: The function determines whether or not there exists an occurrence of ch1 and
: ch2 separated by a distance of no more than n in the given string s, where
: s is ascii and user entered (your function needs to work on any input.) The
: function must be efficient and **optimized** for both space and time. Please
: state what the complexity of your solution is.
|
j*****u
发帖数: 1133 | 3 对同一个input s要search单次还是多次？
单次，scan一遍s，得到ch1和ch2的index array
多次，build hash table of
然后就变成对两个sorted int array找最小差，用2个pointer iterate两个array同时
update min_diff
time O(n + k), space O(k)，k是同一个char的出现次数 |
j*****u
发帖数: 1133 | 4 bool F(string s, char ch1, char ch2, int n)
{
if (string.IsNullOrEmpty(s) || n <= 0 || ch1 == ch2)
throw new ArgumentException();
var index1 = new List();
var index2 = new List();
for (int i = 0; i < s.Length; i++)
{
if (s[i] == ch1)
index1.Add(i);
else if (s[i] == ch2)
index2.Add(i);
}
int minDist = int.MaxValue;
int i1 = 0, i2 = 0;
while (i1 < index1.Count && i2 < index2.Count)
{
int diff = index1[i1] - index2[i2];
minDist = Math.Min(Math.Abs(diff), minDist);
// if (minDist == 1) break;
if (diff < 0)
++i1;
else
++i2;
}
return minDist <= n;
} |
d*****o
发帖数: 28 | 5 Hi jerryju
your code is pretty nice, but there are bugs for boundary case |
p*******n
发帖数: 4824 | 6 This is somewhat too complicated... The space should be O(1), right?
【在 j*****u 的大作中提到】
: bool F(string s, char ch1, char ch2, int n)
: {
: if (string.IsNullOrEmpty(s) || n <= 0 || ch1 == ch2)
: throw new ArgumentException();
: var index1 = new List();
: var index2 = new List();
: for (int i = 0; i < s.Length; i++)
: {
: if (s[i] == ch1)
: index1.Add(i);
|
j********x
发帖数: 2330 | 7 字符很简单：
找到第一个出现的ch1，继续搜索，如果又碰到ch1，将ch1的位置更新到当前的位置，
如果找到ch2，看ch1出现过么，出现过比较位置，如果满足条件，返回true；如果不满
足条件，重新开始
one pass，constant space |
p*******n
发帖数: 4824 | 8 Right:
bool F(const string& s, char ch1, char ch2, int n) {
int i, j;
for (i = 0; i < s.size(); ++i) {
if (s[i] == ch1) {
for (j = 1, i = i+1; j <= n && i < s.size(); ++i, ++j) {
if (s[i] == ch2) {
return true;
} else if (s[i] == ch1) {
j = 0;
continue;
}
}
}
}
return false;
}
【在 j********x 的大作中提到】
: 字符很简单：
: 找到第一个出现的ch1，继续搜索，如果又碰到ch1，将ch1的位置更新到当前的位置，
: 如果找到ch2，看ch1出现过么，出现过比较位置，如果满足条件，返回true；如果不满
: 足条件，重新开始
: one pass，constant space
|
j*****u
发帖数: 1133 | 9 what boundary case? thanks!
我想复杂了，想着多次search结果给bias了
【在 d*****o 的大作中提到】
: Hi jerryju
: your code is pretty nice, but there are bugs for boundary case
|
d*****o
发帖数: 28 | 10 The Boundary case is here:
while (i1 < index1.Count && i2 < index2.Count)
for example:
i1 = 10, index1.count = 11, i2 = 11, index2.count = 16.
it is possible i2 - i1 < n (if n >= 2).
your code missed the case. |
|
|
d*****o
发帖数: 28 | 11 Sorry jerryju,
Please ignore my last comments, I miss-understood the code... |
l********r
发帖数: 187 | 12 thanks. I missed the "no more than" in the question. |
j*****u
发帖数: 1133 | 13 没考虑ch2可能在ch1前面。。
【在 p*******n 的大作中提到】
: Right:
: bool F(const string& s, char ch1, char ch2, int n) {
: int i, j;
: for (i = 0; i < s.size(); ++i) {
: if (s[i] == ch1) {
: for (j = 1, i = i+1; j <= n && i < s.size(); ++i, ++j) {
: if (s[i] == ch2) {
: return true;
: } else if (s[i] == ch1) {
: j = 0;
|
i*******s
发帖数: 558 | 14 I think so too.
【在 j*****u 的大作中提到】
: 没考虑ch2可能在ch1前面。。
|
m****v
发帖数: 84 | 15 这种情况把ch2和ch1换一下，再线性搜一遍？
【在 j*****u 的大作中提到】
: 没考虑ch2可能在ch1前面。。
|
c***2
发帖数: 838 | 16 int strdis(const char *str, char ch1, char ch2, int n)
{
const char *pf;
const char *p=str;
if(!str)
return 0;
while(*p){
while((*p)&&(*p!=ch1)&&(*p!=ch2)) p++;
if(!(*p)) return 0;
if(*p==ch1){
pf=p;
while(*p&&(*p!=ch2)) p++;
if(!(*p)) return 0;
if(p-pf<=n)
return 1;
//wind back
p=pf+1;
}
else{
pf=p;
while(*p&&(*p!=ch1)) p++;
if(!(*p)) return 0;
if(p-pf<=n)
return 1;
p=pf+1;
}
}
return 0;
} |
p*******n
发帖数: 4824 | 17 I see... I don't care :)
其实只要记住最后一个ch2的id, 然后在看到ch1的时候看看和尚一个ch2的距离是不是小于n就可以了, 多一条语句而已, 不用扫描两遍...
【在 j*****u 的大作中提到】
: 没考虑ch2可能在ch1前面。。
|
l********r
发帖数: 187 | 18 Hi,
I got an programming problem from Microsoft for screening purpose. Does
anyone has good idea about it? I am particularly puzzled by the second given
example. Thanks.
“bool F(string s, char ch1, char ch2, int n)”
The function determines whether or not there exists an occurrence of ch1 and
ch2 separated by a distance of no more than n in the given string s, where
s is ascii and user entered (your function needs to work on any input.) The
function must be efficient and **optimized** for both space and time. Please
state what the complexity of your solution is.
Examples:
“abcdefg”, ‘b’, ‘d’, 2 --> true
“abcdefg”, ‘b’, ‘d’, 20 --> true
“abcdefg”, ‘b’, ‘e’, 1 --> false |
l*****a
发帖数: 14598 | 19 1)经典题简化
2）职业杯150上有类似的
3）he asked no more than,why u confused?
any number above 1 will return true
Does
given
ch1 and
where
input.) The
Please
【在 l********r 的大作中提到】
: Hi,
: I got an programming problem from Microsoft for screening purpose. Does
: anyone has good idea about it? I am particularly puzzled by the second given
: example. Thanks.
: “bool F(string s, char ch1, char ch2, int n)”
: The function determines whether or not there exists an occurrence of ch1 and
: ch2 separated by a distance of no more than n in the given string s, where
: s is ascii and user entered (your function needs to work on any input.) The
: function must be efficient and **optimized** for both space and time. Please
: state what the complexity of your solution is.
|
j*****u
发帖数: 1133 | 20 对同一个input s要search单次还是多次？
单次，scan一遍s，得到ch1和ch2的index array
多次，build hash table of
然后就变成对两个sorted int array找最小差，用2个pointer iterate两个array同时
update min_diff
time O(n + k), space O(k)，k是同一个char的出现次数 |
|
|
j*****u
发帖数: 1133 | 21 bool F(string s, char ch1, char ch2, int n)
{
if (string.IsNullOrEmpty(s) || n <= 0 || ch1 == ch2)
throw new ArgumentException();
var index1 = new List();
var index2 = new List();
for (int i = 0; i < s.Length; i++)
{
if (s[i] == ch1)
index1.Add(i);
else if (s[i] == ch2)
index2.Add(i);
}
int minDist = int.MaxValue;
int i1 = 0, i2 = 0;
while (i1 < index1.Count && i2 < index2.Count)
{
int diff = index1[i1] - index2[i2];
minDist = Math.Min(Math.Abs(diff), minDist);
// if (minDist == 1) break;
if (diff < 0)
++i1;
else
++i2;
}
return minDist <= n;
} |
d*****o
发帖数: 28 | 22 Hi jerryju
your code is pretty nice, but there are bugs for boundary case |
p*******n
发帖数: 4824 | 23 This is somewhat too complicated... The space should be O(1), right?
【在 j*****u 的大作中提到】
: bool F(string s, char ch1, char ch2, int n)
: {
: if (string.IsNullOrEmpty(s) || n <= 0 || ch1 == ch2)
: throw new ArgumentException();
: var index1 = new List();
: var index2 = new List();
: for (int i = 0; i < s.Length; i++)
: {
: if (s[i] == ch1)
: index1.Add(i);
|
j********x
发帖数: 2330 | 24 字符很简单：
找到第一个出现的ch1，继续搜索，如果又碰到ch1，将ch1的位置更新到当前的位置，
如果找到ch2，看ch1出现过么，出现过比较位置，如果满足条件，返回true；如果不满
足条件，重新开始
one pass，constant space |
p*******n
发帖数: 4824 | 25 Right:
bool F(const string& s, char ch1, char ch2, int n) {
int i, j;
for (i = 0; i < s.size(); ++i) {
if (s[i] == ch1) {
for (j = 1, i = i+1; j <= n && i < s.size(); ++i, ++j) {
if (s[i] == ch2) {
return true;
} else if (s[i] == ch1) {
j = 0;
continue;
}
}
}
}
return false;
}
【在 j********x 的大作中提到】
: 字符很简单：
: 找到第一个出现的ch1，继续搜索，如果又碰到ch1，将ch1的位置更新到当前的位置，
: 如果找到ch2，看ch1出现过么，出现过比较位置，如果满足条件，返回true；如果不满
: 足条件，重新开始
: one pass，constant space
|
j*****u
发帖数: 1133 | 26 what boundary case? thanks!
我想复杂了，想着多次search结果给bias了
【在 d*****o 的大作中提到】
: Hi jerryju
: your code is pretty nice, but there are bugs for boundary case
|
d*****o
发帖数: 28 | 27 The Boundary case is here:
while (i1 < index1.Count && i2 < index2.Count)
for example:
i1 = 10, index1.count = 11, i2 = 11, index2.count = 16.
it is possible i2 - i1 < n (if n >= 2).
your code missed the case. |
d*****o
发帖数: 28 | 28 Sorry jerryju,
Please ignore my last comments, I miss-understood the code... |
l********r
发帖数: 187 | 29 thanks. I missed the "no more than" in the question. |
j*****u
发帖数: 1133 | 30 没考虑ch2可能在ch1前面。。
【在 p*******n 的大作中提到】
: Right:
: bool F(const string& s, char ch1, char ch2, int n) {
: int i, j;
: for (i = 0; i < s.size(); ++i) {
: if (s[i] == ch1) {
: for (j = 1, i = i+1; j <= n && i < s.size(); ++i, ++j) {
: if (s[i] == ch2) {
: return true;
: } else if (s[i] == ch1) {
: j = 0;
|
|
|
i*******s
发帖数: 558 | 31 I think so too.
【在 j*****u 的大作中提到】
: 没考虑ch2可能在ch1前面。。
|
m****v
发帖数: 84 | 32 这种情况把ch2和ch1换一下，再线性搜一遍？
【在 j*****u 的大作中提到】
: 没考虑ch2可能在ch1前面。。
|
c***2
发帖数: 838 | 33 int strdis(const char *str, char ch1, char ch2, int n)
{
const char *pf;
const char *p=str;
if(!str)
return 0;
while(*p){
while((*p)&&(*p!=ch1)&&(*p!=ch2)) p++;
if(!(*p)) return 0;
pf=p;
if(*p==ch1){
while(*p&&(*p!=ch2)) p++;
}
else{
while(*p&&(*p!=ch1)) p++;
}
if(!(*p)) return 0;
if(p-pf<=n)
return 1;
//wind back
p=pf+1;
}
return 0;
} |
p*******n
发帖数: 4824 | 34 I see... I don't care :)
其实只要记住最后一个ch2的id, 然后在看到ch1的时候看看和尚一个ch2的距离是不是小于n就可以了, 多一条语句而已, 不用扫描两遍...
【在 j*****u 的大作中提到】
: 没考虑ch2可能在ch1前面。。
|
s*******f
发帖数: 1114 | 35 bool F(char *s, char ch1, char ch2, int n){
if (!s || n < 1)
return false;
char *pre = s;
while (*s){
if (*s == ch1){
if (*pre == ch2){
if ((s - pre) <= n)
return true;
}
pre = s;
}else if (*s == ch2){
if (*pre == ch1){
if ((s - pre) <= n)
return true;
}
pre = s;
}
++s;
}
return false;
} |
d*******l
发帖数: 338 | 36 def F(s, ch1, ch2, n):
p1 = -1;
p2 = -1;
for i in xrange(len(s)):
if s[i] == ch1:
if p2 >= 0 and i - p2 <= n:
return True;
p1 = i;
if s[i] == ch2:
if p1 >= 0 and i - p1 <= n:
return True;
p2 = i;
return False; |
