Hey guys these are the two questions I was asked during my phone interview at Facebook. Duration: 45 mins.

Question 1:
You have a huge array of integers containing only 0's and 1's. Write an algorithm that finds the number of 1's found in the array in a specific range.

class Solution {
	
	public Solution(int[] arr) {
		// pre
	}

	/**
	* Returns number of 1's in the range [start, end].
	*/
	public int howManyOnesInRange(int start, int end) {
		// todo
	}

Example:

Solution s = new Solution([0, 1, 1, 1, 0, 0]);
s.howManyOnesInRange(0, 3); // should return 3
s.howManyOnesInRange(0, 0); // 0
s.howManyOnesInRange(3, 5); // 1

Can you do query better than O(n)?

Related problems:

• https://leetcode.com/problems/range-sum-query-immutable/
• https://leetcode.com/problems/range-sum-query-mutable/

Question 2:
https://leetcode.com/problems/decode-ways/

Good luck!