CareerCup

<round 2>
16. Find out largest common SEQUENCE

e.g:

1)
str1: ABCDEF
str2: ABC

LArgest Common sequence: ABC

2) str1: ABCDEF
str2: ACEG
LArgest Common sequence: ACE

3)

str1: ABCDEF
str2: ZACYEFX

Largest common sequence : ACEF

NOTE: SEQUENCE need not be consecutive .

<round 2>
15. We have a special tree, in which every node contains random number of child nodes.

Note : each node can contains no. of child nodes between ZERO to INFINITY

sub questions:

1) node structure definition ?
2) which traversal you use ?. Traversal code ?

<round 2>
14) How you will achieve encapsulation in C language ?.

<round 2>>
13. Different types of TYPECASTS in C++ ?

<round 2>
12. Iterative Binary Search Algorithm with Single comparison .

<round 2>

11. Explain PREORDER, POST OREDER, INORDER. ?. To construct tree which 2 ORDERS needed ?

<round 2>
10. How many ZERO s in 100! ?

<round 2>
9. How to check given number is prime or not ?

<round 2>

8. Number N is given to you. You have to print all Permutations between 1 to N.
e.g
1) N = 2
o/p: 1 2
2 1
2) N =1
O/p : 1

<round 2>

7. Quick Sort avg and Worst case complexity . write code for Quick sort ?

<round 1 >

6) what is fork()

sub questions

1) How many times "SIVA" will be printed

i = 0 ;
while (i < n )
{
    fork();
    printf("\n SIVA");
    i++;
}

2)How many times "SIVA" will be printed

i = 0 ;
while (i < n )
{
    printf("\n SIVA");
    fork();
    i++;
}

<round 1>

5) Explain about Thread Pool ?

<round 1>
4) Difference between Flip-FLOP ? Where we use flip flop ?

<round 1>
3) Unbalanced or Skewed binary tree root is given to you. You have balance tree by doing LEFT and RIGHT rotations.

<round 2 >
2) Write your own "cp" command to copy files.

<Round 1>
1) Iterative Single Linked List Reverse

5) Can we crash a process before entering Main() function ?

I said possible and I give following two examples

example 1:

int *i = 0;
int j = *i;  // I think here memory access violation since pointer 'i' pointing 0th address.

int main()
{
    return 0;
}

Example 2:

int i = 1 / 0; // here Float point exception or divided by zero exception.

int main()
{
    return 0;
}

Today I executed , above two examples and I am getting compile time error "Line 2: error: initializer element is not constant
" .

Can some one please tell me why I am getting compile time error ?

4) How to initialize Constant variables in class( or object).

example 1: throws error "uninitialized member 'myclass::i' with 'const' type 'const int'
"

#include <iostream>
using namespace std;

class myclass{
public:
       const int i;

       myclass()
       {
            i = 10;  // here throws error
       }
};

int main()
{
      myclass m;
      cout<<m.i<<endl;
      return 0;
}

example 2: below piece of code works fine .

#include <iostream>
using namespace std;

class myclass{
public:
       const int i;

       myclass() : i(10)
       {

       }
};

int main()
{

      myclass m;
      cout<<m.i<<endl;
      return 0;
}

Can some one please explain me , why second example works fine ? . why not first example ?

3) Littele Endian vs Big Endian ?

Sub questions:

1) which one decides endianess , Processor(CPU) or Operating System ?

2) There any standard ways to convert little endian data to big endian and vice versa .
My answer:
Linux is little endian and Solaris is big endian.

After that I said Processor(CPU) decides endianness of the machine. Intel processor supports little endian and SPARCV( Solaris) processor supports big endian.

He asked what about Solaris operating system with Intel processor ?. I said it is little endian.

Am I correct ?

2. write down Linux "grep" command code.

Input: file and a pattern
Eg.
$ Mygrep "siva*" names.txt

Output:
print entire line if it contains "Siva" word or prefix.

e.g:

"good bad siva is bad boy."
"sivabrtt gjfg"

After that asked me to write code to support regular expressions like "Siva*", "siva+venkat", "^siva".

1) Print tree in reverse Spiral Order .

Input:

1
         /  \
        2    3
       / \  / \
      4  5 6   7

Output: 4->5->6->7->3->2->1

int main()
{
   int i=10;

   {
       int i=100;
       printf("%d", i);
   }

}

1.what is the output ?
2. what signifies "{" "}" in above code .
"{" "}" will it create new "Activation Record" ( or Frame) in Stack ?

<round 3>

11. difference between Inline and macro functions.

sub question :

1) what happens if you apply inline on recursive function.

2) is there any Recursive Macro function ?

e.g

#define SUM(x, y)   do{
                        SUM(x,y);
                      }while(0);

is there any error ?

<round 3>
10. differences between

char *str = "SIVA" and char str1[]="SIVA"

sub questions:
1) where string literal i.e "SIVA" will be stored ( heap , stack, data or code segments) in above both cases.

2) char *str = "SIVA";
str[0] = 'f' ;
any error ? compile time error or run time error ?
3) char *p = (char *) str;
p[0] = 'f' ;
any error ? compile time error or run time error ?

<round 3>
9. Array A[n] it contains numbers from 1 to n but 1 number repeated. Find out missing number.

----------------------
I have not answered this question and manager not happy with my performance. THIS THE END OF THE BATTLE.

<round3 >
8.He asked me many Hashing questions.

Sub questions
1. What is hashing ?
2. you can write your own hash methods or you can use existing Hash methods in STL C++.

which one you prefer ? why ?

3. Write a Generic hash function & hash table , which should support all data types INT, FLOAT, STRINGS, and OBJECTS .

<round3> ( Manager round )
7. Check given tree is symmetric or not ?

e.g

1) Symmetric
      1
     / \
    2   2
   /     \
  3       3
2) non-symmetric
      1
     / \
     2  3

<round 2>
6. Quadrant contains N points and all are + ve points ( I mean both (X,Y) are +ve values).

sub questions:
1. How you will store( or Data structure) N points to make look up( or search) easy.

2. Find out closest point (Pj) for a entered point (Pi).

Note: He asked me time efficient solution.
User can add extra M points later point of time. So your solution should be Scalable.

<round 1>
5. Reverse single linked list .

<Round 1>
4. Grid[n][n] contains letters from 'A' to 'Z' randomly. You have to print all possible words from grid.

You are allowed to move Left, Right, Up and Down ( no diagonal move).

Sub Questions:

1. Write down Dictionary_Lookup() function prototype. ( I no need to implement Dictionary_Lookup() but I have to write down possible return value and its arguments ).

This help us to find out traversed characters forming word or not.

2. Write down complete code to print all possible words in Grid.

<written test >
3.check whether given single linked list is palindrome or not.
e.g: 1->2->1 palindrome
1->2->3 not a palindrome
Note: Time efficient and without using any other data structures.

<written test >
2. Two sorted arrays A[X] and B[Y+X]. in B array contains Y sorted elements and B can accommodate A[] X elements.

W.A.P to Merge two arrays and store resultant in B[] array.

Note: Time efficient and space efficient solution

I appeared for the Amazon( Bangalore) Interview on 05-Feb-2011. I cleared written test. After that I gave 3 rounds of interview.

Note: They are going conduct interviews on 13-Feb-2011 also. There is a chance to repeat following questions.
< written Test >
1. Preorder string"NNLLNLL" ( or similar string ) has given to you. You have to construct binary tree.

Here 'N' means non -leaf node.
Here 'L' means leaf node.

Note: every node contains 0 or 2 childrens.

write down String class copy constructor ?

find a bug in following code :

class A
{
public:
    static int i;
    void print()
    {
         cout<< i << endl ;
    }
};

int main()
{
 A a;
 a.print();
}

I run above code, and I am getting "ndefined reference to `A::i'" . Why I am getting this error ?

How can we generate all possibilities on braces ?

N value has given to us and we have to generate all possibilities.

**Examples:**

1) if N == 1, then only one possibility () .

2) if N==2, then possibilities are (()), ()()

3) if N==3, then possibilities are ((())), (())(),()()(), ()(()) ...

Note: left and right braces should match. I mean )( is INVALID for the N==1

How can we solve this problem by using recurrence approach ?

Question on Tree Data Structure: How can we fill all inorder successor pointer of all tree nodes ?

Tree node contains 3 pointers *left, *right and *Successor .

Struct node{
         int data;
         struct node *left;
         struct node *right;
         struct node *successor; 
    };

A
           /  \
          B    C
         / \  / \
        D   E F  G

INORDER Traversal: **DBEAFCG**
**Note:** A inorder successors are F,C and G.

**Function prototype:** void FillSuccessorNodes( struct node *root);
Tree's root node given to us and we need to fill successor pointer for all nodes.

case 1) some of the Successor pointers may be **NULL** . This case you have to fill that pointer with immediate Inorder Successor.

Example: if A->Successor == NULL, then fill A->Successor = F

case 2) some of the Successor pointers may already  points to correct successors. This case You no need to modify successor pointers.

Example: 1) A->successor = F is valid

2) A->successor = C is valid

3) A-successor = G is valid . All these three cases you no need to modify successor pointer since these already pointing to correct successor nodes.

case 3) Some of the successor pointers are **not NULL** but these pointers pointing to INVALID successors i.e it could be inorder successor or some garbage value. This case you have to fill these nodes with immediate successor nodes.

Example:

1) A->successor = B is invalid since B is not successor node , so we have to correct it to A->successor = F.

2) A->successor = 0x23237463478 is invalid since it is pointing to garbage value. So we we have to correct it to A->successor = F.

**1) Interviewer asked me time efficient solution in O(n) time complexity. Extra space allowed.
2) she gave some hint i.e we can use HASHing.**

**If you know the solution for this problem, please let me know .**