Google_CountIntegerPoinstInCircle [source code]

public class Google_CountIntegerPoinstInCircle {
static
/******************************************************************************/
class Solution {
    int count (int r) {
        if (r < 1)
            return 1;
        int res = 1 + 4 * r;
        for (int i = 1; i < r; i++) {
            res += 4 * (int) Math.sqrt (r * r - i * i);
        }
        return res;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        Google_CountIntegerPoinstInCircle.Solution tester = new Google_CountIntegerPoinstInCircle.Solution();
        int[] inputs = {
            3,
            1,
            4,
            20,
            932,
        };
        for (int i = 0; i < inputs.length; i++) {
            System.out.println (Printer.separator ());
            int r = inputs[i], ans = bruteCount (r), output = tester.count (r);
            System.out.printf ("%d -> %s, expected: %d\n", 
                r, Printer.wrap (output + "", output == ans ? 92 : 91), ans
            );
        }
    }

    static int bruteCount (int r) {
        int res = 0;
        for (int i = -r; i <= r; i++) {
            for (int j = -r; j <= r; j++) {
                if (i * i + j * j <= r * r)
                    res++;
            }
        }
        return res;
    }
}

假设不包含on circle的点;

Problem Description

Google面经

http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=352160&page=1#pid3631875

发一个google的电面面经，上周面的，这周还没有联系，估计是要跪
第一轮国人小哥，出的题很简单，关于hash table 的
第二轮，一个在google 7年的大哥，两道题，
1 given an integer r，find how many integer points are located in a circle with radius r
2 given a list of rectangles which are not intersect with others ,each rectangle has four points, write a method to choose a point uniformly for the list of rectangles