Amazon Interview Question
Senior Software Development Engineers Software Engineer / DevelopersCountry: India
No. If you understand the terms, this should be quite clear. Are you looking to get your homework done?
I agree this will work, basics of Group Theory. Good to see maths is finding it's way in different faces
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.
Look for elements that add up to 0. Build a table of all combinations that add up to 0. I think this would take at least O(n^2) time though, where n is size of the code space. From this table you could build your subsets by adding any remaining element to the 0 combination.
Pick the largest basis and consider the spaces generated by possible subsets of that basis.
- Anonymous April 02, 2013