Safenet Interview Question
Developer Program EngineersI'll try a heuristic,
the middle boxes are surrounded with more number boxes, our goal is to not to have neighbors. so lets take a number from 1 to 8 that has less neighbors which is either 1 or 8.
place it in the middle 4 boxes then alternatively place continuous elements
- 1 - - - 1 - 2 - 1 - 2 - 1 - 2
- - - - - - - - - 3 - - - 3 - 4
and then
5 1 - 2 5 1 6 2 5 1 6 2 5 1 6 2
- 3 - 4 - 3 - 4 7 3 - 4 7 3 8 4
you could try selecting different box for 1 as below:
- - - - - - - - - - 3 - 4 - 3 -
- - 1 - 2 - 1 - 2 - 1 - 2 - 1 -
and then
4 - 3 - 4 - 3 - 4 - 3 7 4 8 3 7
2 - 1 5 2 6 1 5 2 6 1 5 2 6 1 5
feel free to suggest advanced heuristics. thanks
Let me try to formalize it
1. Divide even and odd in halfs
Since any pair of consecutive number consists of an even and an odd
number hence these two cannot be in the same half.
2 Place 1 and 8 on the separation line between even and odd.
Since 1 and 8 have affinity for one number only hence solution is
possible.
Comments and inputs are welcome
7|1|6|4
- red-cheeks November 11, 2010-------
5|3|8|2