Wednesday, July 14, 2004

 

Some C++ interview questions - 4

1.
Combinations in C++
By CBasicNet
From http://www.codeproject.com/cpp/CombC.asp

2.
Implementing Permutation Variations
By Zuoliu Ding
From http://www.codeproject.com/cpp/permute.asp

Permutations in C++
By CBasicNet
http://www.codeproject.com/cpp/cppperm1.asp

3.
【 以下文字转载自 JobHunting 讨论区,原文如下 】
: : : 发信人: dudu (神奇主), 信区: JobHunting
: : : 标 题: 微软的新面试题
: : : 发信站: The unknown SPACE (Sat Jan 6 11:22:53 2001) WWW-POST
: : : 给定一个32比特整形数,以最快速度实现按byte的有符号移位。
: : : 例如:
: : : 11111100 00001010 11011101 00000011 =〉
: : : 11111110 00000101 11011110 00000001
: : : 需要考虑数据从memeory from/to register的传送时间。
: : : (我理解也就是说要尽量在register上操作。)

发信人: Cloud (Cloud), 信区: Programming
标 题: Re: [转载] 微软的新面试题
发信站: The unknown SPACE (Sat Jan 6 20:20:27 2001) WWW-POST

b= a & 10000000 10000000 10000000 10000000;
a >>1
a =a & ~(10000000 10000000 10000000 10000000)
a = a | b;

4.
发信人: xjb (bb), 信区: Programming
标 题: Re: 这样的算法存在吗?
发信站: The unknown SPACE (Thu Jun 27 14:57:16 2002) WWW-POST

【 在 duz (duz) 的大作中提到: 】
: 【 在 aaapple (qinger) 的大作中提到: 】
: : 我没有想出来,可是又不感肯定是否存在,请各位指点一下。
: : 输入: 一组n个无序正数
: :
: : 如果在这些数中,a0>=a1>=a2>=...ai...>=an
: :
: : 求: max{ai+i}
: :
: : 要求时间复杂度是O(n).
: : 谢谢
: :
: :

If the problem is like this. Just find max and use hash function.
Let the max denote the maximum value of a0---an.
Build n buckets: b0=[max,max-1],b1=[max-1,max-2],...
Then put this n+1 numbers into the abovementioned buckets.
Let num(j) denote the number of elements in the first j buckets.
Find the bucket bj such that num(j)-j is max, then the minimal
element in this bucket is what you want.
: :
: 我想你是向求下面的问题:
: 给定n个无序数a1,a2,...,an
: 如果将它们从到小排序后,ai将排在第k(i)个,
: 求max{a(i)+k(i)}
:
: 问问题首先要将自己的问题表达好,不要让人家取猜测。
:
: 这个问题感觉应该无法再O(n)内完成,不过O(nlog(n))同O(n)也没有多少差别呀?
:
:

--
※ 来源:.The unknown SPACE bbs.mit.edu.[FROM: 129.97.79.111]

5.
发信人: BigWhite (25号), 信区: Programming
标 题: how to perform atomic operations on integers?
发信站: Unknown Space - 未名空间 (Mon Dec 1 00:27:11 2003), 转信

OS: linux
compiler: gcc

question: suppose I have an variable defined as an integer, which could
be increased/decreased by several threads simutaneously. I don't want to
use additional mutexes or locking mechanisms to guarantee atomic increment/
decrement. Is there any macro doing this?

--
※ 来源:.Unknown Space - 未名空间 mitbbs.com.[FROM: 155.69.]

发信人: ayanami (横着爬的螃蟹/见坑就跳), 信区: Programming
标 题: Re: how to perform atomic operations on
发信站: Unknown Space - 未名空间 (Mon Dec 1 11:51:14 2003), 转信


#ifndef __ARCH_I386_ATOMIC__
#define __ARCH_I386_ATOMIC__

/*
* Atomic operations that C can't guarantee us. Useful for
* resource counting etc..
*/

/* Always be SMP safe, on single CPU lock can be define as : LOCK "" */

#define LOCK "lock ; "

/*
* Make sure gcc doesn't try to be clever and move things around
* on us. We need to use _exactly_ the address the user gave us,
* not some alias that contains the same information.
*/
typedef struct { volatile int counter; } atomic_t;

#define ATOMIC_INIT(i) { (i) }

/**
* atomic_read - read atomic variable
* @v: pointer of type atomic_t
*
* Atomically reads the value of @v. Note that the guaranteed
* useful range of an atomic_t is only 24 bits.
*/
#define atomic_read(v) ((v)->counter)

/**
* atomic_set - set atomic variable
* @v: pointer of type atomic_t
* @i: required value
*
* Atomically sets the value of @v to @i. Note that the guaranteed
* useful range of an atomic_t is only 24 bits.
*/
#define atomic_set(v,i) (((v)->counter) = (i))

/**
* atomic_add - add integer to atomic variable
* @i: integer value to add
* @v: pointer of type atomic_t
*
* Atomically adds @i to @v. Note that the guaranteed useful range
* of an atomic_t is only 24 bits.
*/
static __inline__ void atomic_add(int i, atomic_t *v)
{
__asm__ __volatile__(
LOCK "addl %1,%0"
:"=m" (v->counter)
:"ir" (i), "m" (v->counter));
}

/**
* atomic_sub - subtract the atomic variable
* @i: integer value to subtract
* @v: pointer of type atomic_t
*
* Atomically subtracts @i from @v. Note that the guaranteed
* useful range of an atomic_t is only 24 bits.
*/
static __inline__ void atomic_sub(int i, atomic_t *v)
{
__asm__ __volatile__(
LOCK "subl %1,%0"
:"=m" (v->counter)
:"ir" (i), "m" (v->counter));
}

/**
* atomic_sub_and_test - subtract value from variable and test result
* @i: integer value to subtract
* @v: pointer of type atomic_t
*
* Atomically subtracts @i from @v and returns
* true if the result is zero, or false for all
* other cases. Note that the guaranteed
* useful range of an atomic_t is only 24 bits.
*/
static __inline__ int atomic_sub_and_test(int i, atomic_t *v)
{
unsigned char c;

__asm__ __volatile__(
LOCK "subl %2,%0; sete %1"
:"=m" (v->counter), "=qm" (c)
:"ir" (i), "m" (v->counter) : "memory");
return c;
}

/**
* atomic_inc - increment atomic variable
* @v: pointer of type atomic_t
*
* Atomically increments @v by 1. Note that the guaranteed
* useful range of an atomic_t is only 24 bits.
*/
static __inline__ void atomic_inc(atomic_t *v)
{
__asm__ __volatile__(
LOCK "incl %0"
:"=m" (v->counter)
:"m" (v->counter));
}

/**
* atomic_dec - decrement atomic variable
* @v: pointer of type atomic_t
*
* Atomically decrements @v by 1. Note that the guaranteed
* useful range of an atomic_t is only 24 bits.
*/
static __inline__ void atomic_dec(atomic_t *v)
{
__asm__ __volatile__(
LOCK "decl %0"
:"=m" (v->counter)
:"m" (v->counter));
}

/**
* atomic_dec_and_test - decrement and test
* @v: pointer of type atomic_t
*
* Atomically decrements @v by 1 and
* returns true if the result is 0, or false for all other
* cases. Note that the guaranteed
* useful range of an atomic_t is only 24 bits.
*/
static __inline__ int atomic_dec_and_test(atomic_t *v)
{
unsigned char c;

__asm__ __volatile__(
LOCK "decl %0; sete %1"
:"=m" (v->counter), "=qm" (c)
:"m" (v->counter) : "memory");
return c != 0;
}

/**
* atomic_inc_and_test - increment and test
* @v: pointer of type atomic_t
*
* Atomically increments @v by 1
* and returns true if the result is zero, or false for all
* other cases. Note that the guaranteed
* useful range of an atomic_t is only 24 bits.
*/
static __inline__ int atomic_inc_and_test(atomic_t *v)
{
unsigned char c;

__asm__ __volatile__(
LOCK "incl %0; sete %1"
:"=m" (v->counter), "=qm" (c)
:"m" (v->counter) : "memory");
return c != 0;
}

/**
* atomic_add_negative - add and test if negative
* @v: pointer of type atomic_t
* @i: integer value to add
*
* Atomically adds @i to @v and returns true
* if the result is negative, or false when
* result is greater than or equal to zero. Note that the guaranteed
* useful range of an atomic_t is only 24 bits.
*/
static __inline__ int atomic_add_negative(int i, atomic_t *v)
{
unsigned char c;

__asm__ __volatile__(
LOCK "addl %2,%0; sets %1"
:"=m" (v->counter), "=qm" (c)
:"ir" (i), "m" (v->counter) : "memory");
return c;
}

/* These are x86-specific, used by some header files */
#define atomic_clear_mask(mask, addr) \
__asm__ __volatile__(LOCK "andl %0,%1" \
: : "r" (~(mask)),"m" (*addr) : "memory")

#define atomic_set_mask(mask, addr) \
__asm__ __volatile__(LOCK "orl %0,%1" \
: : "r" (mask),"m" (*addr) : "memory")

#endif

发信人: junfeng (somewhere), 信区: Programming
标 题: Re: how to perform atomic operations on
发信站: Unknown Space - 未名空间 (Wed Dec 3 04:37:10 2003) WWW-POST

There are reasons why inc/dec has to be synchronized.

1. On single CPU, this defines a write barrier so that compiler won't try to
re-order instructions involving that variable.

2. On SMP, this invalidates caches in other CPUs.

发信人: junfeng (somewhere), 信区: Programming
标 题: Re: how to perform atomic operations on
发信站: Unknown Space - 未名空间 (Sat Dec 6 05:48:02 2003) WWW-POST

I think the two points I made are actually the same thing. But anyway, This
MSDN link explains why you need a write barrier:

http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dllproc/base/
synchronization_and_multiprocessor_issues.asp

Memory Caching

When a processor writes to a memory location, the value is cached to improve
performance. Similarly, the processor attempts to satisfy read requests from
the cache to improve performance. Furthermore, processors begin to fetch
values from memory before they are requested by the application. This can
happen as part of speculative execution or due to cache line issues.

As a result, multiple processors can have different views of the system memory
state because their caches are out of synch. For example, the following code
is not safe on a multiprocessor system:

int iValue;
BOOL fValueHasBeenComputed = FALSE;
extern int ComputeValue();

void CacheComputedValue()
{
if (!fValueHasBeenComputed)
{
iValue = ComputeValue();
fValueHasBeenComputed = TRUE;
}
}

BOOL FetchComputedValue(int *piResult)
{
if (fValueHasBeenComputed)
{
*piResult = iValue;
return TRUE;
}
else
return FALSE;
}
There is a race condition in this code on multiprocessor systems because the
processor that executes CacheComputedValue the first time may write
fValueHasBeenComputed to main memory before writing iValue to main memory.
Consequently, a second processor executing FetchComputedValue at the same time
reads fValueHasBeenComputed as TRUE, because the new value of iValue is still
in the first processor's cache.

Processors can be instructed to force their memory caches to agree with main
memory with special instructions. Such instructions ensure that previous read
and write requests have completed and are made visible to other processors,
and to ensure that that no subsequent read or write requests have started.
Examples are:


Functions which enter or leave critical sections.
Functions which signal synchronization objects.
Wait functions.
Interlocked functions
Consequently, the multiprocessor race condition above can be repaired as
follows:

void CacheComputedValue()
{
if (!fValueHasBeenComputed) {
iValue = ComputeValue();
InterlockedExchange((LONG*)&fValueHasBeenComputed, TRUE);
}
}
The InterlockedExchange function ensures that the value of iValue is updated
for all processors before the value of fValueHasBeenComputed is set to TRUE.

6.
发信人: ms (shaoye), 信区: Programming
标 题: [转载] Re: Answer for Microsoft questions?
发信站: Unknown Space - 未名空间 (Tue Feb 17 05:10:51 2004) WWW-POST

Can anyone comment on this interview question?
: 4. Implemente x ? y : z using only ~, !, ^, &, +, |, <<, >> no if
: statements,
: or loops or anything else, just those operators, and the function should
: correctly return y or z based on the value of x.

--
※ 修改:·ms 於 Feb 17 05:10:51 修改本文·[FROM: 24.4.]
※ 来源:.Unknown Space - 未名空间 mitbbs.com.[FROM: 24.4.]

发信人: NecroMancer (神秘人), 信区: Programming
标 题: Re: [转载] Re: Answer for Microsoft questions?
发信站: Unknown Space - 未名空间 (Tue Feb 17 08:18:45 2004), 转信

assuming all unsigned 32-bit int :

unsigned int cond_op_32( unsigned int x, unsigned int y, unsigned int z )
{
x = x << 16 | x >> 16 ;
x = x << 8 | x >> 8 ;
x = x << 4 | x >> 4 ;
x = x << 2 | x >> 2 ;
x = x << 1 | x >> 1 ;
return x & y | ~x & z ;
}

for non-integral types, reinterpret-cast (or using an union to cast) to
unsigned integral types of same size, e.g.

float cond_op_f( float x, float y, float z )
{
unsigned int r = cond_op_32( *(unsigned int*)&x, *(unsigned int*)&y,
*(unsigned int*)&z );
return *(float *)&r ;
}

7.
发信人: SnowLotus (雪中莲), 信区: Programming
标 题: why l = b<<24 + b<<16 + b<<8 + b =>l=0
发信站: Unknown Space - 未名空间 (Tue Feb 24 20:30:57 2004) WWW-POST

int b= 2;
long l;
l = b<<24 + b<<16 + b<<8 + b;

发现l = 0.为什么会这样?应该没有overflow.

I tried the below code. l6 !=0. why?
l1 = b<<24;
l2 = b<<16;
l3 = b<<8;
l6 = l1+l2+l3+b;

--
※ 来源:.Unknown Space - 未名空间 mitbbs.com.[FROM: 35.12.]

发信人: SnowLotus (雪中莲), 信区: Programming
标 题: Re: why l = b<<24 + b<<16 + b<<8 + b =>l=0
发信站: Unknown Space - 未名空间 (Tue Feb 24 20:51:10 2004) WWW-POST

So it will be l = b <<(24+b) << (16+b) << (8+b)?

我怎么就想不到?太笨了!

【 在 BigWhite (25号) 的大作中提到: 】
: precedence

8.
#include
void main()
{
union
{
struct
{
unsigned short s1:3;
unsigned short s2:3;
unsigned short s3:3;
}x;
char c;
}v;
v.c=100;
printf("%d\n",v.x.s3);
}
A:4 B:0 C:3 D:6

答案是A

v.c= 100 (01100100) -->low:0100 high:0110
union 后的存储分布是这样:
char c: 0 1 0 0 0 1 1 0
struct: x.s1 x.s2 x.s3
value : 010 001 10(0)
由于char 是8 位长度.x 是9位.union 显示x比c要多一位.s3的位域是3位的.所以后面被0 取出的结果为100,即十进制的4.



<< Home

This page is powered by Blogger. Isn't yours?