g********t
发帖数: 39 | 1 今天刚和博通的一个印印经理面试，寒暄了几分钟，然后要求用邮件的方式立马回复给
他，基本都是c的题，题目是这样的：
Q1. void wait( int* p, int n )
{
while ((*p & (1 << n)) == 0);
}
1. What is the intention of the above code?
2. How could it be improved?
Q2. int test( int a )
{
return ((a - 1) & a) == 0;
}
Comment on its portability.
Q3.
char* func( char* a, const char* b )
{
while( *a )
{
char *s = a, *t = b;
while( (*s++ == *t++) && *s && *t );
if( *t == 0 )
return a;
a++;
}
return 0;
}
The above code was written to search for the first instance
of string "b" inside of string "a."
1.. Does the code work as written? Why or why not?
2. How would you improve it?
3. How could it be made more efficient?
大家来讨论一下吧~ |
s*****y
发帖数: 897 | 2 Which group?
fulltime or intern?
【在 g********t 的大作中提到】
: 今天刚和博通的一个印印经理面试，寒暄了几分钟，然后要求用邮件的方式立马回复给
: 他，基本都是c的题，题目是这样的：
: Q1. void wait( int* p, int n )
: {
: while ((*p & (1 << n)) == 0);
: }
: 1. What is the intention of the above code?
: 2. How could it be improved?
: Q2. int test( int a )
: {
|
g********t
发帖数: 39 | |
s*****y
发帖数: 897 | 4 which group?
【在 g********t 的大作中提到】
: full-time :)
|
g********t
发帖数: 39 | 5 for test engineer position. what's up
【在 s*****y 的大作中提到】
: which group?
|
i**********e
发帖数: 1145 | 6 Q3.
char* func( char* a, const char* b )
{
while( *a )
{
char *s = a, *t = b;
while( (*s++ == *t++) && *s && *t );
if( *t == 0 )
return a;
a++;
}
return 0;
}
Not sure if this
(*s++ == *t++) && *s && *t
is undefined behavior, since it is considered as one expression.
Even if we assume then second part of expression is evaluated as s and t are
both incremented, then if the last character in *t doesn't match with *s,
it quits the loop, but *t == 0 is evaluated as true (while it should not be
a match).
【在 g********t 的大作中提到】
: 今天刚和博通的一个印印经理面试，寒暄了几分钟，然后要求用邮件的方式立马回复给
: 他，基本都是c的题，题目是这样的：
: Q1. void wait( int* p, int n )
: {
: while ((*p & (1 << n)) == 0);
: }
: 1. What is the intention of the above code?
: 2. How could it be improved?
: Q2. int test( int a )
: {
|
i**********e
发帖数: 1145 | 7 Not sure what Q1 is asking?
Busy wait until the nth bit of *p is 1?
Q2 test is it a power of two? Problem with signed int? And 0 by the way
should not be power of two. |
s*****y
发帖数: 897 | 8 should be
Q1. void wait( volatile int* p, int n )
{
while ((*p & (1 << n)) == 0);
}
p point to hardware register memory address.
Software call this function to poll the hardware status.
【在 i**********e 的大作中提到】
: Not sure what Q1 is asking?
: Busy wait until the nth bit of *p is 1?
: Q2 test is it a power of two? Problem with signed int? And 0 by the way
: should not be power of two.
|
g********t
发帖数: 39 | 9 agree with you~
【在 s*****y 的大作中提到】
: should be
: Q1. void wait( volatile int* p, int n )
: {
: while ((*p & (1 << n)) == 0);
: }
: p point to hardware register memory address.
: Software call this function to poll the hardware status.
|
g********t
发帖数: 39 | 10 今天刚和博通的一个印印经理面试，寒暄了几分钟，然后要求用邮件的方式立马回复给
他，基本都是c的题，题目是这样的：
Q1. void wait( int* p, int n )
{
while ((*p & (1 << n)) == 0);
}
1. What is the intention of the above code?
2. How could it be improved?
Q2. int test( int a )
{
return ((a - 1) & a) == 0;
}
Comment on its portability.
Q3.
char* func( char* a, const char* b )
{
while( *a )
{
char *s = a, *t = b;
while( (*s++ == *t++) && *s && *t );
if( *t == 0 )
return a;
a++;
}
return 0;
}
The above code was written to search for the first instance
of string "b" inside of string "a."
1.. Does the code work as written? Why or why not?
2. How would you improve it?
3. How could it be made more efficient?
大家来讨论一下吧~ |
|
|
s*****y
发帖数: 897 | 11 Which group?
fulltime or intern?
【在 g********t 的大作中提到】
: 今天刚和博通的一个印印经理面试，寒暄了几分钟，然后要求用邮件的方式立马回复给
: 他，基本都是c的题，题目是这样的：
: Q1. void wait( int* p, int n )
: {
: while ((*p & (1 << n)) == 0);
: }
: 1. What is the intention of the above code?
: 2. How could it be improved?
: Q2. int test( int a )
: {
|
g********t
发帖数: 39 | |
s*****y
发帖数: 897 | 13 which group?
【在 g********t 的大作中提到】
: full-time :)
|
g********t
发帖数: 39 | 14 for test engineer position. what's up
【在 s*****y 的大作中提到】
: which group?
|
i**********e
发帖数: 1145 | 15 Q3.
char* func( char* a, const char* b )
{
while( *a )
{
char *s = a, *t = b;
while( (*s++ == *t++) && *s && *t );
if( *t == 0 )
return a;
a++;
}
return 0;
}
Not sure if this
(*s++ == *t++) && *s && *t
is undefined behavior, since it is considered as one expression.
Even if we assume then second part of expression is evaluated as s and t are
both incremented, then if the last character in *t doesn't match with *s,
it quits the loop, but *t == 0 is evaluated as true (while it should not be
a match).
【在 g********t 的大作中提到】
: 今天刚和博通的一个印印经理面试，寒暄了几分钟，然后要求用邮件的方式立马回复给
: 他，基本都是c的题，题目是这样的：
: Q1. void wait( int* p, int n )
: {
: while ((*p & (1 << n)) == 0);
: }
: 1. What is the intention of the above code?
: 2. How could it be improved?
: Q2. int test( int a )
: {
|
i**********e
发帖数: 1145 | 16 Not sure what Q1 is asking?
Busy wait until the nth bit of *p is 1?
Q2 test is it a power of two? Problem with signed int? And 0 by the way
should not be power of two. |
s*****y
发帖数: 897 | 17 should be
Q1. void wait( volatile int* p, int n )
{
while ((*p & (1 << n)) == 0);
}
p point to hardware register memory address.
Software call this function to poll the hardware status.
【在 i**********e 的大作中提到】
: Not sure what Q1 is asking?
: Busy wait until the nth bit of *p is 1?
: Q2 test is it a power of two? Problem with signed int? And 0 by the way
: should not be power of two.
|
g********t
发帖数: 39 | 18 agree with you~
【在 s*****y 的大作中提到】
: should be
: Q1. void wait( volatile int* p, int n )
: {
: while ((*p & (1 << n)) == 0);
: }
: p point to hardware register memory address.
: Software call this function to poll the hardware status.
|
L***Q
发帖数: 508 | 19 这儿有两个问题。
第一，编译错，t = b;const pointer不能assign给non-const pointer，破坏了
constness。
第二，就是大牛您说的，(*s++ == *t++)存在问题，即便*s != *t，++操作也会执行，
至少gcc编译的是这样。old style的c programmer最喜欢把这种一堆东西写在一个语句
里面，显得很牛叉，但是既不好读，又容易出bug。老老实实把++操作写在while里面更
清晰明了。
【在 i**********e 的大作中提到】
: Q3.
: char* func( char* a, const char* b )
: {
: while( *a )
: {
: char *s = a, *t = b;
: while( (*s++ == *t++) && *s && *t );
: if( *t == 0 )
: return a;
: a++;
|
b*****k
发帖数: 26 | 20 Q3.
char* func( char* a, const char* b )
{
char *s, *t;
while( *a )
{
while(*a != *b && *a ) a++;
if(*a==0)
return 0;
s = a+1;
t = b+1;
while( (*s++ == *t++) && *s && *t );
if( *t == 0 )
return a;
a++;
}
return 0;
} |
|
|
v**n
发帖数: 951 | 21 个人觉得除了volatile的那个问题，（1<
evaluate.
void wait( volatile int* p, int n )
{
int bitmask;
bitmask = 1 << n;
while ((*p & (bitmask)) == 0);
}
当然现代牛叉compiler应该可以优化这个 1<
更进一步的话，应该说如果这段代码用非优化的参数编译的话，是正确的代码，但是效
率低。
如果用优化的参数编译的话，很有可能是错误的代码。
【在 s*****y 的大作中提到】
: should be
: Q1. void wait( volatile int* p, int n )
: {
: while ((*p & (1 << n)) == 0);
: }
: p point to hardware register memory address.
: Software call this function to poll the hardware status.
|
t****t
发帖数: 6806 | 22 Q1:
wait for n-th bit to become 1 (by hardware or other thread).
problem: should make p point to volatile, otherwise may go deadloop.
multiple evaluation of (1<
if atomic is supported, better use atomic. polling efficiency is low, but
this depends on situation, for example in firmware, or in spinlock, this is
quite ok. if it is used to for multithreads, you may want to use thread
communication functions instead.
Q2: test whether a is 2^n. if that is indeed the intention, better exclude 0.
Q3: quite the opposite to ihasleetcode said, "*s++ == *t++ && *s && *t" is
NOT undefined, since && makes a sequence point. This makes the expression
three subexpression that will be evaluated in left-to-right order. and *t==0
is not a problem; since at the evaluation of *t, t already point to the
next character which has not been compared yet.
The only problem is, when b is empty string (""), the function is undefined,
since "*s++ == *t++" will move t beyond \0, then the next compare (*t) is
undefined.
of course, you may not assign const char* b to char* t. that won't compile.
as for readability, i think it is quite ok. everyone has different tolerance
though. old-fashioned c programmers usually have higher tolerance; since
this is c test anyway, i will let it pass.
in fact, the correct (standard) function is simply change the condition
order:
while (*s && *t && *s++ === *t++);
【在 g********t 的大作中提到】
: 今天刚和博通的一个印印经理面试，寒暄了几分钟，然后要求用邮件的方式立马回复给
: 他，基本都是c的题，题目是这样的：
: Q1. void wait( int* p, int n )
: {
: while ((*p & (1 << n)) == 0);
: }
: 1. What is the intention of the above code?
: 2. How could it be improved?
: Q2. int test( int a )
: {
|
l******y
发帖数: 17 | 23 那Q2的移植性有什么考虑
us.
is
0.
【在 t****t 的大作中提到】
: Q1:
: wait for n-th bit to become 1 (by hardware or other thread).
: problem: should make p point to volatile, otherwise may go deadloop.
: multiple evaluation of (1<: if atomic is supported, better use atomic. polling efficiency is low, but
: this depends on situation, for example in firmware, or in spinlock, this is
: quite ok. if it is used to for multithreads, you may want to use thread
: communication functions instead.
: Q2: test whether a is 2^n. if that is indeed the intention, better exclude 0.
: Q3: quite the opposite to ihasleetcode said, "*s++ == *t++ && *s && *t" is
|
l**********1
发帖数: 415 | |
y*****n
发帖数: 243 | 25 = =Q2. should we give up the CPU if it is in busy loop? Just like the lock
do.. .. |
t****t
发帖数: 6806 | 26 i don't think that a problem, unless you are not using 2-compliment for
integer. that is extremely rare.
【在 l******y 的大作中提到】
: 那Q2的移植性有什么考虑
:
: us.
: is
: 0.
|
t****t
发帖数: 6806 | 27 you meant Q1?
normally spin-lock give up CPU after a while, but that's in complex modern
OS. for simple system, waiting is OK. simple system may not even support
thread anyway.
keep in mind what broadcom do ---- they deal with hardware.
【在 y*****n 的大作中提到】
: = =Q2. should we give up the CPU if it is in busy loop? Just like the lock
: do.. ..
|
y*****n
发帖数: 243 | 28 Yeah, Q1. It not limited in threads, I think.
The function name is wait, I though it looks like it is busy waiting
something. It will be better for CPU content switch to other process if the
condition is not fulfilled. it is better than Keep busy waiting until
content switch, I think.
【在 t****t 的大作中提到】
: you meant Q1?
: normally spin-lock give up CPU after a while, but that's in complex modern
: OS. for simple system, waiting is OK. simple system may not even support
: thread anyway.
: keep in mind what broadcom do ---- they deal with hardware.
|
t****t
发帖数: 6806 | 29 context (not content) switching is usually expensive. if you expect the wait
period is pretty short, it's better to just wait. that's why spin-lock and
spin-wait exist. the original program is exactly how you implement a spin-
wait (with volatile or atomic, of course).
the real world is more complex than theoretical "you think". there is no one
-solution-fits-all. spin-wait and interrupt driven wait both has its usage,
and there is no general "one is better than other" judgement without context.
the
【在 y*****n 的大作中提到】
: Yeah, Q1. It not limited in threads, I think.
: The function name is wait, I though it looks like it is busy waiting
: something. It will be better for CPU content switch to other process if the
: condition is not fulfilled. it is better than Keep busy waiting until
: content switch, I think.
|
y*****n
发帖数: 243 | 30 So you mean in the question 1, the wait period could be pretty short so
that it is better do not context switch?
wait
one
,
context.
【在 t****t 的大作中提到】
: context (not content) switching is usually expensive. if you expect the wait
: period is pretty short, it's better to just wait. that's why spin-lock and
: spin-wait exist. the original program is exactly how you implement a spin-
: wait (with volatile or atomic, of course).
: the real world is more complex than theoretical "you think". there is no one
: -solution-fits-all. spin-wait and interrupt driven wait both has its usage,
: and there is no general "one is better than other" judgement without context.
:
: the
|
|
|
t****t
发帖数: 6806 | 31 that's right. usually for several hundreds cycles wait time, spinlock is
faster than heavy-weight mutex.
【在 y*****n 的大作中提到】
: So you mean in the question 1, the wait period could be pretty short so
: that it is better do not context switch?
:
: wait
: one
: ,
: context.
|
y*****n
发帖数: 243 | 32 Oh, You mean, in this situation, the wait period could be very short so that
the context switch will lead to inefficiency.
wait
one
,
context.
【在 t****t 的大作中提到】
: context (not content) switching is usually expensive. if you expect the wait
: period is pretty short, it's better to just wait. that's why spin-lock and
: spin-wait exist. the original program is exactly how you implement a spin-
: wait (with volatile or atomic, of course).
: the real world is more complex than theoretical "you think". there is no one
: -solution-fits-all. spin-wait and interrupt driven wait both has its usage,
: and there is no general "one is better than other" judgement without context.
:
: the
|
L***Q
发帖数: 508 | 33 这儿有两个问题。
第一，编译错，t = b;const pointer不能assign给non-const pointer，破坏了
constness。
第二，就是大牛您说的，(*s++ == *t++)存在问题，即便*s != *t，++操作也会执行，
至少gcc编译的是这样。old style的c programmer最喜欢把这种一堆东西写在一个语句
里面，显得很牛叉，但是既不好读，又容易出bug。老老实实把++操作写在while里面更
清晰明了。
【在 i**********e 的大作中提到】
: Q3.
: char* func( char* a, const char* b )
: {
: while( *a )
: {
: char *s = a, *t = b;
: while( (*s++ == *t++) && *s && *t );
: if( *t == 0 )
: return a;
: a++;
|
b*****k
发帖数: 26 | 34 Q3.
char* func( char* a, const char* b )
{
char *s, *t;
while( *a )
{
while(*a != *b && *a ) a++;
if(*a==0)
return 0;
s = a+1;
t = b+1;
while( (*s++ == *t++) && *s && *t );
if( *t == 0 )
return a;
a++;
}
return 0;
} |
v**n
发帖数: 951 | 35 个人觉得除了volatile的那个问题，（1<
evaluate.
void wait( volatile int* p, int n )
{
int bitmask;
bitmask = 1 << n;
while ((*p & (bitmask)) == 0);
}
当然现代牛叉compiler应该可以优化这个 1<
更进一步的话，应该说如果这段代码用非优化的参数编译的话，是正确的代码，但是效
率低。
如果用优化的参数编译的话，很有可能是错误的代码。
【在 s*****y 的大作中提到】
: should be
: Q1. void wait( volatile int* p, int n )
: {
: while ((*p & (1 << n)) == 0);
: }
: p point to hardware register memory address.
: Software call this function to poll the hardware status.
|
t****t
发帖数: 6806 | 36 Q1:
wait for n-th bit to become 1 (by hardware or other thread).
problem: should make p point to volatile, otherwise may go deadloop.
multiple evaluation of (1<
if atomic is supported, better use atomic. polling efficiency is low, but
this depends on situation, for example in firmware, or in spinlock, this is
quite ok. if it is used to for multithreads, you may want to use thread
communication functions instead.
Q2: test whether a is 2^n. if that is indeed the intention, better exclude 0.
Q3: quite the opposite to ihasleetcode said, "*s++ == *t++ && *s && *t" is
NOT undefined, since && makes a sequence point. This makes the expression
three subexpression that will be evaluated in left-to-right order. and *t==0
is not a problem; since at the evaluation of *t, t already point to the
next character which has not been compared yet.
The only problem is, when b is empty string (""), the function is undefined,
since "*s++ == *t++" will move t beyond \0, then the next compare (*t) is
undefined.
of course, you may not assign const char* b to char* t. that won't compile.
as for readability, i think it is quite ok. everyone has different tolerance
though. old-fashioned c programmers usually have higher tolerance; since
this is c test anyway, i will let it pass.
in fact, the correct (standard) function is simply change the condition
order:
while (*s && *t && *s++ === *t++);
【在 g********t 的大作中提到】
: 今天刚和博通的一个印印经理面试，寒暄了几分钟，然后要求用邮件的方式立马回复给
: 他，基本都是c的题，题目是这样的：
: Q1. void wait( int* p, int n )
: {
: while ((*p & (1 << n)) == 0);
: }
: 1. What is the intention of the above code?
: 2. How could it be improved?
: Q2. int test( int a )
: {
|
l******y
发帖数: 17 | 37 那Q2的移植性有什么考虑
us.
is
0.
【在 t****t 的大作中提到】
: Q1:
: wait for n-th bit to become 1 (by hardware or other thread).
: problem: should make p point to volatile, otherwise may go deadloop.
: multiple evaluation of (1<: if atomic is supported, better use atomic. polling efficiency is low, but
: this depends on situation, for example in firmware, or in spinlock, this is
: quite ok. if it is used to for multithreads, you may want to use thread
: communication functions instead.
: Q2: test whether a is 2^n. if that is indeed the intention, better exclude 0.
: Q3: quite the opposite to ihasleetcode said, "*s++ == *t++ && *s && *t" is
|
l**********1
发帖数: 415 | |
y*****n
发帖数: 243 | 39 = =Q2. should we give up the CPU if it is in busy loop? Just like the lock
do.. .. |
t****t
发帖数: 6806 | 40 i don't think that a problem, unless you are not using 2-compliment for
integer. that is extremely rare.
【在 l******y 的大作中提到】
: 那Q2的移植性有什么考虑
:
: us.
: is
: 0.
|
|
|
t****t
发帖数: 6806 | 41 you meant Q1?
normally spin-lock give up CPU after a while, but that's in complex modern
OS. for simple system, waiting is OK. simple system may not even support
thread anyway.
keep in mind what broadcom do ---- they deal with hardware.
【在 y*****n 的大作中提到】
: = =Q2. should we give up the CPU if it is in busy loop? Just like the lock
: do.. ..
|
y*****n
发帖数: 243 | 42 Yeah, Q1. It not limited in threads, I think.
The function name is wait, I though it looks like it is busy waiting
something. It will be better for CPU content switch to other process if the
condition is not fulfilled. it is better than Keep busy waiting until
content switch, I think.
【在 t****t 的大作中提到】
: you meant Q1?
: normally spin-lock give up CPU after a while, but that's in complex modern
: OS. for simple system, waiting is OK. simple system may not even support
: thread anyway.
: keep in mind what broadcom do ---- they deal with hardware.
|
t****t
发帖数: 6806 | 43 context (not content) switching is usually expensive. if you expect the wait
period is pretty short, it's better to just wait. that's why spin-lock and
spin-wait exist. the original program is exactly how you implement a spin-
wait (with volatile or atomic, of course).
the real world is more complex than theoretical "you think". there is no one
-solution-fits-all. spin-wait and interrupt driven wait both has its usage,
and there is no general "one is better than other" judgement without context.
the
【在 y*****n 的大作中提到】
: Yeah, Q1. It not limited in threads, I think.
: The function name is wait, I though it looks like it is busy waiting
: something. It will be better for CPU content switch to other process if the
: condition is not fulfilled. it is better than Keep busy waiting until
: content switch, I think.
|
y*****n
发帖数: 243 | 44 So you mean in the question 1, the wait period could be pretty short so
that it is better do not context switch?
wait
one
,
context.
【在 t****t 的大作中提到】
: context (not content) switching is usually expensive. if you expect the wait
: period is pretty short, it's better to just wait. that's why spin-lock and
: spin-wait exist. the original program is exactly how you implement a spin-
: wait (with volatile or atomic, of course).
: the real world is more complex than theoretical "you think". there is no one
: -solution-fits-all. spin-wait and interrupt driven wait both has its usage,
: and there is no general "one is better than other" judgement without context.
:
: the
|
t****t
发帖数: 6806 | 45 that's right. usually for several hundreds cycles wait time, spinlock is
faster than heavy-weight mutex.
【在 y*****n 的大作中提到】
: So you mean in the question 1, the wait period could be pretty short so
: that it is better do not context switch?
:
: wait
: one
: ,
: context.
|
y*****n
发帖数: 243 | 46 Oh, You mean, in this situation, the wait period could be very short so that
the context switch will lead to inefficiency.
wait
one
,
context.
【在 t****t 的大作中提到】
: context (not content) switching is usually expensive. if you expect the wait
: period is pretty short, it's better to just wait. that's why spin-lock and
: spin-wait exist. the original program is exactly how you implement a spin-
: wait (with volatile or atomic, of course).
: the real world is more complex than theoretical "you think". there is no one
: -solution-fits-all. spin-wait and interrupt driven wait both has its usage,
: and there is no general "one is better than other" judgement without context.
:
: the
|
N****p
发帖数: 1691 | 47 Q1和Q3都是好题目啊
都是可以test 不同 level的理解
【在 g********t 的大作中提到】
: 今天刚和博通的一个印印经理面试，寒暄了几分钟，然后要求用邮件的方式立马回复给
: 他，基本都是c的题，题目是这样的：
: Q1. void wait( int* p, int n )
: {
: while ((*p & (1 << n)) == 0);
: }
: 1. What is the intention of the above code?
: 2. How could it be improved?
: Q2. int test( int a )
: {
|
