Pair socks from pile

Question: How to find pair socks from a pile efficiently?

Resource: http://stackoverflow.com/questions/14415881/pair-socks-from-a-pile-efficiently

Question Owner: amit

ANSWER

Actually, you can do this by selecting one sock and searching all the pile. It is least efficient way I guess.

Try to think this problem like solving a puzzle. Before to solve a puzzl, first, we group all same colors like "yellows go this pile" or "blue ones go there". This method is called hashing(or maybe only I call this like that I do'nt know :))

After we grouped we can search easily them. Try to think this with letters from 'A' to 'Z'. We have 26 pairs as "A-A" or "J-J".

Consider them as colors and say: "First 13 letters are yellow, and last 13 are blue"

We search all socks(letters) and group them according to their colors.

Then, we can look more carefully and notice their patterns to find pairs.

(Algorithm) Find n'th Fibonacci nuber with complexity O(log(n)) and in O(1) space

Question: We have given number n. And it is asked that we have to find n'th Fibonacci number. However, we have two conditions.

1) Complexity should be O(log(n))

2)We should compute this in O(1) space

Resource: http://www.careercup.com/page?pid=algorithm-interview-questions

Question Owner: zr.roman

ANSWER

I think, maybe, Term which is "O(1) space" may confuse your mind.

"O(1) space" means you should use same memory for all kind of n's.

Let's try to catch the "regularity" from examples:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

You may think that you can store all Fibonacci numbers, and use binary search algorithm.

However this way is useless, because Fibonacci sequence is infinite. There always be greater Fibonacci number for your last number stored.

I will use formula to compute this by rounding with the help of golden ratio. You can find more about this in this link.

This computing is in O(1) space and has complexity O(1) too. If you have any extra solution pls contact me.