tulip
BAN USER
Questions (3)
Comments (2)
Followers (3)
Reputation 80
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Page:
1
RepJeanSwest, Data Engineer at Achieve Internet
I am a nuclear power reactor operator who is responsible for the flow of energy at a power plant. I ...
RepBarbaraLocke, Android test engineer at ABC TECH SUPPORT
Hey, I'm a BarbaraLocke. And I love my work. Apart from this, I am doing some new experiments in ...
RepAahnaAllen, AT&T Customer service email at A9
I am a multilingual Judge with 5 years of combined experience in presiding over court proceedings, prosecuting cases, and tirelessly ...
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
All i could think of at that time is to store all the board configurations in a hash so that getting best position of move is a O(1) operation.
- tulip June 15, 2012Each board square can be either 0,1, or 2.
0 represents empty square. 1 represents a X & 2 represents 0.
So every square can be filled with either of the three. There are approx 3^9 board configurations.
In simple, we need a hash of size 3^9. For hashing,we can go for base 3 representation. Means each number in base 3 will be 9 digits long each digit corresponding to each square.
To search in hash, we need to find the decimal representation of this 9 digit number.
Now, each square can be associated with row number & column number. In order to identify each square uniquely, we can again make use of base 3 representation.
say SQ[1][2] will be 12 in base 3 which is equivalent to 5 in decimal.
Thus, we have effectively designed an algorithm which is fast enough to calculate the next move in O(1).
But, the interviewer insisted in reducing the space complexity as DOS system doesn't have that much amount of memory.
I couldn't think how we can reduce the space complexity with no change in time complexity.
I think symmetry can be used.