Monday, 7 January 2013

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

1 comment:

  1. Hey Can you help me with the algorithm of longest permutation cycle question here?? I am kinda stuck in it!!

    ReplyDelete