kpj
BAN USER
Comments (3)
Reputation 45
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 2 vote
Like some of the earlier comments, I believe this can be solved using dynamic programming. Assuming we can either go right or go down from [0][0], p[i][j], the # of paths from [i][j] to [N][M], can be computed as follows.
temp = 0;
if (i + 1 <= N && m[i + 1][j] == 0) temp += p[i + 1][j]; // down
if (j + 1 <= M && m[i][j + 1] == 0) temp += p[i][j + 1]; // right
p[i][j] = temp;
One special case is p[N][M]:
if (m[N][M] == 0) p[N][M] = 1; else p[N][M] = 0;
Then,
for (i = N; i >= 0; i--)
for (j = M; j >= 0; j--)
if (m[i][j] == 0) compute p[i][j] as mentioned above;
After the computation, p[0][0] should be the # of possible paths from [0][0] to [N][M].
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
I assume c_set is a set of characters and w_set is a set of words? And basically c_set covers w_set means that all the words in w_set contains at least one character from c_set?
- kpj March 01, 2013One solution I can think of (similar to some of the mentioned solutions) is:
1. create 26-bit (using 4 bytes) bit mask where i-th bit is set if i-th character of the alphabet is in c_set. For example, if c_set is {a, b, c, g}, it is like 11100010000.... let's call it cmask
2. For each word, create a similar mask. For "apple", bits for a, p, l, e are set. Let's call it wmask_i for w_i.
Then compute bitwise AND with cmask and each wmask_i. If any of them evaluates to 0, stop there and return false. If every cmask & wmask_i is non-zero, c_set covers w_set.
I can't really think of any good solutions for the second part. Small optimizations that I can think of are:
1. precompute wmask_i.
2. wmask_1 & wmask_2 & ... & wmask_n indicates characters that appear in all of the words. If cmask & this w_mask is non-zero, c_set covers w_set
3. wmask_1 | wmask_2 | ... | wmask_n indicates all the characters that appear in w_set. If cmask & this wmask is zero, c set doesn't cover w_set.