Find all 10 digit numbers which are perfect squares efficiently

Two players play the following game: they pick a random number N (less than 2 billion) then, starting from 1, take turns multiplying the number from the previous turn with either 2 or 9 (their choice). Whoever reaches N first wins. The candidate should write a function that given N decides who wins (first or second player)?

Design a function f, such that: f(f(n)) == -n Where n is a 32 bit signed integer; you can't use complex numbers arithmetic. If you can't design such a function for the whole range of numbers, design it for the largest range possible.

Two strings can be chained if the first one ends with the same character second one starts with. Given set of 'n' strings, how can we verify efficiently, whether they can be chained or not?

e.g. cat, dog, toad  answer is YES.
for    tape ate ass answer is NO.

A circular array A[1, . . . , n] is an array such that n ≥ 3 and A[1] and A[n] are considered to be adjacent elements just like A[1] and A[2], A[2] and A[3], etc., are adjacent. We are given a circular array A[1, . . . , n] of non-negative integers. For any i, j ∈ {1, 2, . . . , n} such that i != j, dist(i, j) = max {|i − j|, n − |i − j|}. Design a linear time algorithm that computes a maximum number t such that for some i, j ∈ {1, 2, . . . , n}, i != j, t = A[i] + A[j] + dist(i, j).