fat_nerd's blog

WTF are these weird ass interview questions?
By fat_nerd, history, 2 years ago, In English

I have been practicing CP for a while, but this is the first time I have seen these types of weird problems. Can someone help me solve these?

  1. Given an array of numbers (a_i <= 1e18). Determine if each number is the sum of 2 Fibonacci numbers.
  2. Given a list of 4 <= N <= 1000 points on a Cartesian plane, count the number of squares such that all 4 corners of the square lie on the points. Note that the points don't repeat and -1000 <= xi, yi <= 1000, and the square does not need to be axis aligned.
  • Vote: I like it
  • -30
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why are they weird though?

→ Reply
»
2 years ago, # |
  Vote: I like it +23 Vote: I do not like it
  1. Fibonacci numbers grow really quickly. First compute all the Fibonacci numbers less than 1e18, there are probably <100 of them. Then perform a brute force method to try all pairs of Fibonacci numbers.
→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is this an ongoing interview? If it's already over, then I have an $$$O(N^2 logN)$$$ solution for the problem 2. Not that it's particularly difficult.

→ Reply
»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

1: Preompute all sum of pairs of fibonacci numbers because it's a low number and check for each element if it's a sum (hashmap).

2: go through all pairs of points in N² and notice that there are only three cases to check for each one.

Might be different from codeforces, but having done CP these questions are trivial.

→ Reply