Informatica Test - Subjective Round

This year Informatica participated in the placement process at IIT-B. They invited applications for India as well as their US Office for software engineering profiles!

Their process for shortlisting for final rounds of interviews consisted of two Rounds of testing.

First round had very simple objective questions on Data structures, Algorithms, Operating Systems, Database Queries and some other questions on basic CS concepts.

Out of the 60-70 people who sat for the first round, 30 made it to the shortlist for the second round, which was subjective. The duration of subjective round was 1 hour and it had the following questions :-


1) You are given an array of integers, say a. Find i, j, k in the array such that a[i] < a[j] < a[k]. Expected time complexity is O(n), and space complexity is O(1).

2) You are given a pointer to a node in a graph. You have to create a copy of the graph. The node structure is as follows.

class Node {
      int id;
      vector<Node*> neighbors;
}

3) Write a program to compute fibonacci numbers. Improve its efficiency.

4) You have a set of jobs j1, j2, ..., jN. There are some restrictions on the way the jobs can be executed, eg. j1 has to be executed before j2, j3 has to be executed before j1 etc. Give an algorithm to to schedule the   jobs given the constraints.

5) Design a 2-way HashTable

6) Given 2 very large arrays A and B. Find the common elements given that you have
                                          a) Unlimited Space
                                          b) Limited Space

7) In a store there are a million distinct items. You have to list the k most sold items at the end of day. Give the data structure/algorithm you will use for the following cases
                  a) You have to list the items in sorted order of number items sold,
                  b) Sorted order is not necessary, so just print the items in any order

8) How many times will "hello" be printed on executing the following program.

int main() {
      int tmp;      
      for (int i=0; i<7; i++) {
           tmp = fork();
           if (tmp > 0) break;
           cout << "hello" << endl;
      }
}

9) I don't remember this one exactly, but you are given a program with several declarations/definitions of variables. You have to say where will the memory be allocated for all the declarations, eg. Heap, Stack, Text Segment, etc.



Out of the 30 people who appeared for the subjective round, only 15 odd people were able to clear it, and shortlisting for final interviews was purely based on your performance in the test.