Twitter Interview Questions

I came across some Twitter's personal interview questions asked for it's Software Engineering position during some discussion:

1) Find whether a string contains a contiguous palindromic substring in O(n) time. Can you solve the problem in O(1) time?

2) In an array, find the element which appears more than 50% of the time. Find element which appears more than 33% of the time in the array.

3) What is a distributed hashtable? How to make data persistent, prevent data loss, and still keep the access efficient?

4) What are the key differences between the data structures: Hashtable, Array, LinkedList, BST. For what kind of queries would a BST perform better than Hashtable?

5) How will you find the most frequently searched queries on Google in the last minute/last hour/last day from among a dynamic stream of queries?

Twitter Programming Test

Twitter conducted an online programming test at IIT-Bombay. Following questions were asked:

1) Given a string, check if there exists some anagram of the string which is a palindrome.
Function Signature: bool anagramPalindrome(string word)

Sample Testcases:
a) anagramPalindrome("rotate") returns false, no anagram of "rotate" is a palindrome
b) anagramPalindrome("hanna") returns true, since using letters from "hanna", we can form the palindrome "nahan"

2) Given a permutation which contains numbers in the range [1, N], return the length of the largest cycle in the permutation. Function Signature: int longestCycle(vector<int> perm)

Sample Testcases:
a) longestCycle([2 3 1]) returns 3, since only cycle is (1 2 3) whose length is 3
b) longestCycle([5 4 3 2 1]) returns 2, since the permutation can be decomposed into (1 5), (2 4), (3)



Somehow, I was also able to get hold of the questions asked at IIT-Delhi's twitter programming test:

1) Find the number of "visible" nodes in a binary tree. A node is a "visible" node if the path from root to that node does not encounter any node of value higher than that node.

2) In a 2D matrix of dimensions M*N, find number of "equilibrium" points.  A point (i, j) is said to be an "equilibrium" point only if all following conditions hold:
a) sum of rows 1...(i-1) =  sum of rows (i+1)...M
b) sum of columns 1...(j-1)  = sum of columns (j+1)...N