Yahoo Interview Question
Software Engineer / DevelopersCan you please explain how you arrived at this decision??
The question itself is not very clear to me. Help appreciated.
i cant see why the answer is stupid? The sensor can read and output. So the rotation direction can be identified by output BW or WB.
Am i missing something?
Problem with BWWBBB:
BWWBBB can be produced both clockwise and anticlockwise. Start from 4th B and go right to left.
/// Assume Result is : a1a2a3...an
/// Satisfy the condition: a1a2a3...an , a2a3a4....ana1, ...., ana1a2....an-1 Not Match Any
/// anan-1...a1, ..., a1anan-1...a2
/// Using BruteForce
int shift(int m[], int n)
{
int t = m[0];
for(int i = 0; i < n - 1; i ++) m[i] = m[i + 1];
m[n - 1] = t;
return 0;
}
bool equal_arr(int a[], int b[], int n)
{
int i = 0;
for(i = 0; i < n; i ++) if(a[i] != b[i]) break;
return (i == n);
}
bool is_match(int a[], int b[], int n)
{
bool ok = true;
for(int i = 0; i < n; i ++)
{
shift(a, n);
for(int j = 0; j < n; j ++)
{
shift(b, n);
if(equal_arr(a, b, n)) {ok = false; break;}
}
if(!ok) break;
}
return ok;
}
int gen_arr(int a[], int x)
{
for(int i = 0; i < 32; i ++)
{
a[i] = (x & (1 << i)) ? 1 : 0;
}
return 0;
}
int run()
{
int a[100], b[100];
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
int N = 3;
bool ok = false;
while(1)
{
if(N > 100) break;
int x = (1 << N) - 1;
for(int i = 0; i <= x; i ++)
{
gen_arr(a, i);
for(int j = 0; j < N; j ++) b[j] = a[N - j - 1];
if(is_match(a, b, N)) {
ok = true; break;
}
if(ok) break;
}
if(ok) break;
N ++;
}
for(int i = 0; i < N; i ++) {
printf("%c ", a[i] ? 'B' : 'W');
}
printf("\n");
return 0;
}
I think
- Anonymous September 12, 2010BWBBWW should be the order...