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

5 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
  3. أفضل شركة نقل في الطائف والنجارين في إعمار في تفكيك وتركيب الأثاث

    ReplyDelete
  4. Using the Images Background Remover service, you can get the best possible solutions. The photos will be livelier and you can use them anywhere. The importance of Background Remover Online is undeniable for every photo. Before we move to the benefits of having the service, it is better to know about the service.

    ReplyDelete
  5. Which Best Foot Massager To Buy – Which Foot Massager Is Right For You? If you ask which Foot Massager model is the finest this year, certainly I would recommend going through this guide to know which Best Foot Massager is actually market leaders.

    ReplyDelete