# Interview Questions 3

January 16, 2010 4 Comments

1. Given and Array of A[1..n] bits, find the length of longest consecutive substring of 0 and 1 such that number of 0s and 1s are equal.

2. Given an array of integers where some numbers repeat 1 time, some numbers repeat 2 times and only one number repeats 3 times, how do you find the number that repeat 3 times.

3. In a 1D rotated (about an unknown index) sorted array, an element is local minimum if a[i-1] < a[i] < a[i+1]. How to find an index where local minimum exists in O(logn). Similar question in a 2D array where a local minimum is the number which is smaller than all its 4 neighbours.

4. How will you find nth fibonacci in log(n) time?

5. You are given a character array say "aabcdadabc"-you have to generate all unique patterns(subarrays) containing 2 or more chars? Minimize time and space complexity.

6. Given an array of 'n' random integers. Given an integer 1<=n. Find the k numbers such that the minimum difference of all the possible pairs of k numbers is maximum (maximum among other minimum differences for various possible selections of k numbers ).

7. Each leaf node has a boolean value associated with it, 1 or 0. In addition, each interior node has either an "AND" or an "OR" gate associated with it. The value of an "AND" gate node is given by the logical AND of its two children's values. The value of an "OR" gate likewise is given by the logical OR of its two children's values. The value of all of the leaf nodes will be given as input so that the value of all nodes can be calculated up the tree.

It's easy to find the actual value at the root using level order traversal and a stack(internal if used recursion).

Given V as the desired result i.e we want the value calculated at the root to be V(0 or 1) what is the minimum number of gates flip i.e. AND to OR or OR to AND be required at internal nodes to achieve that?

Also for each internal node you have boolean associated which tells whether the node can be flipped or not. You are not supposed to flip a non flippable internal node.

Please post an O(n) time complexity and O(1) space complexity solution for question 2.

Hashing or sorting solution is not required.

Thanks in advance.

Are you sure that an O(n) time O(1) space algorithm for this exists?

Actually i am not sure. I have searched it on many websites, none could give a proper solution according to the constraints. But this has been asked by Amazon and Abode in interviews and they specifically mentioned that they dont want hashing or sorting solutions to this problem. Either they want the interviewees to prove that it is impossible or some solution surely exits.

yaa a O(n) complexity and O(1) soln exist for this question (2) .

THanks,