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

2 comments:

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

    ReplyDelete


  2. افضل شركة تنظيف بالدمام افضل شركة تنظيف بالدمام
    شركة تنظيف خزانات بالدمام شركة تنظيف خزانات بالدمام
    شركة تسليك مجاري بالدمام شركة تسليك مجارى بالدمام
    شركة مكافحة حشرات بالاحساء شركة مكافحة حشرات بالاحساء

    شركة تنظيف شقق بالدمام شركة تنظيف شقق بالدمام

    ___-

    شركة تنظيف منازل بالدمام شركة تنظيف منازل بالدمام
    شركة تسليك مجاري بالاحساء شركة تسليك مجاري بالاحساء
    شركة تنظيف منازل بالخبر شركة تنظيف بالخبر
    افضل شركة نقل عفش بالاحساء افضل شركة نقل عفش بالاحساء
    شركة تنظيف منازل بالاحساء شركة تنظيف منازل بالاحساء

    ReplyDelete