GOOGLE PAPER IIT ROORKEE 2011
SECTION A
1. Some problems were given. And they asked that which algorithm strategy (greedy, dynamic programming...) u can apply. Problem name is as-
(i). krushkal algorithm
(ii). Elucid GCD algorithm
(iii). All pair shortest path problem
(iv). Binary search
(v). tower of Hanoi
(vi). Dijakshtra algorithm
(vii). Travelling sales man problem
2. Some problem is given below. We need to write worst case complexity of best solution for these algorithm-
(i). searching in min heap
(ii). Find top 5 % element in an array
(iii). Find whether two NFA are equivalent
(iv). Find whether two graphs are isomorphic
(v). comparision sorting
3. Which networking protocol is used for the following
(i). video streaming RTSP
(ii). HTTP
(iii). DNS
SECTION B
Apart from the correctness of the code. We will see that ur code should be modular, easily readable, follow all rule of software engineering-
1. The anagrams of a set {1, 2, 3 ….n} are the arrangement of the numbers in the set in some order. If we represent each permutation by a signature (string) such that each number in permutation is represented by ‘I’ (increasing) if next number in the sequence is greater than the previous one. otherwise represented by’D’(decreasing). For example- {23416875} is represented by signature “IIDIIDD”. Note that the length of the signature is N-1.
But our task is to do the reverse computing. That is if suppose the signature is given, we need to find the lexicographic minimum permutation of the set if it is there in the set. otherwise return false.
Vector <int>* permutation (const string &signature);
2. A set of strings is anagram (permutation) free if no two strings in the set are anagram of each other. Example -‘abab’, ‘abba’,’bbaa’,’baab’ all are anagram of ‘aabb’.
A set of string is given, then write the code to find maximal subset of the given that is anagram free.
