jannatint
BAN USER- -1of 1 vote
AnswersYou are given with space of binary codewords, and you have to come up with an algo to generate all subspace of size 2^1 , 2^2 ,2^3 . . .2^n of that set.
- jannatint in India
subspace is defined as:
1. it should have the 00..000 code word.
2. it should satisfy closure property. ie if we add any 2 codewords then result shud lie in the subspace.
Note: code words are to be added simply under modulo 2. no concept of carry is there.
ie. 1111 + 1010 = 0101| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
AnswersGiven a set of array of size n, return all possible subset of size k.
- jannatint in United States
example: if arr = { 1,2,3,4,5,6} , k=2;
return result is: {1,2};{1,3};{1,4};{2,3};{2,4};{3,4}
or a single array {1,2,1,3,1,4,2,3,2,4,3,4}| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
AnswersI was given a space of binary codewords containing 2^k codewords of word length n. And I was asked to generate all possible subspace of size 2^1, 2^2, 2^3 . . . . .,2^k.
- jannatint in India
Definition of subspace: It should have zero codeword, and it should satisfy additive closure property under modulo 2.
example: say given space of codeword is {0000,0001,1110,1111}. Then subspace of size 2^1 are D1{0000,0001} , D2{0000,1110}, D3{0000,1111}. and subspace of size 2^2 is {0000,0001,1110,1111}.
note: the additive closure is checked under modulo 2. ie. example1 1100 + 1010 = 0110 example2 111100 + 111111 = 000011
(no concert of carry was there, bits are added and modulo 2 is taken)| Report Duplicate | Flag | PURGE
Amazon Senior Software Development Engineer Software Engineer / Developer Algorithm
first of all what do you mean by largest basis??
this method is not working i guess.
say we have a space of codeword of size 2^n where n=3. {0000000,0010111,0101110,0111001,1011100,1001011,1110010,1100101 }
it has basis {1011100,0101110,0010111}.
now possible subset of size 2 are: {1011100,0101110} , {0101110,0010111} and {1011100,0010111}.
that means we have only 3 subspace of size 2^2 in this case. which is actually not true. there are even more.
correct me if am wrong.
All codewords are of same length.
- jannatint April 11, 2013