iRageCapital Placement Written 2014

Read More..

BrowserStack Interview 2014

Attempt the following question in a maximum of 5 hours

IIT Roorkee

Question 1

Tree with grep support

The program will be given a folder named (optional, if not passed assume cwd). The program will print something like this:

$ tree
.
|-- README.md
|-- closure
|   |-- currencySymbols.js
|   |-- datetimeSymbolsExt.js
|   |-- datetimesymbols.js
|   |-- numberSymbols.js
|   `-- pluralRules.js
|-- e2e
|   |-- i18n-e2e.js
|   |-- localeTest_cs.html
|   |-- localeTest_de.html
|   |-- localeTest_en.html
|   |-- localeTest_es.html
|   |-- localeTest_sk.html
|   |-- localeTest_zh.html
|   `-- runner.html
|-- generate.sh
|-- run-tests.sh
|-- spec
|   |-- closureI18nExtractorSpec.js
|   |-- converterSpec.js
|   |-- parserSpec.js
|   `-- utilSpec.js
|-- src
|   |-- closureI18nExtractor.js
|   |-- closureSlurper.js
|   |-- converter.js
|   |-- parser.js
|   `-- util.js
`-- update-closure.sh

4 directories, 26 files

An optional second parameter supports filtering the tree with grep like filter, only matching nodes. Eg:

$ tree . src
.
`-- src
    |-- closureI18nExtractor.js
    |-- closureSlurper.js
    |-- converter.js
    |-- parser.js
    `-- util.js
It should be possible to use arbitrary regex expression for filtering.

Question 2

Write a Key Server which is capable of accepting three calls: /generate, /validate and /delete.

The /validate and /delete accept a single http parameter "key" each, and return the response in plain-text.
Once generated a key is valid for only 60 seconds.

Output:
/generate call:
{NEW_KEY}

/validate call:
Response for valid key:
{KEY}:VALID

Response for invalid key:
{KEY}:INVALID

/delete call:
{KEY}:DELETED

IIT Delhi

Question 1

You will need to poll an HTTP endpoint (provided to you) and log the response code in a log file, with the date and corresponding response code. In case of error response code, the date and response code should be pushed to a UDP server in same format as logged in the file.

Health check URL should be configurable via a command line argument.
Ex: ./monitor http://www.google.com/

File log format:
Date: Fri Oct 28 18:59:24 IST 2014 Response: 200

Error push format:
Date: Fri Oct 28 18:59:24 IST 2014 Response: 500

Question 2

Program a UDP server that reads string data in following format:
Kind: “valid", Data: "Awesome Data"
Kind: “invalid", Data: "Bad Data"

If "Kind" is equal to "valid" you accept and push the data in the valid.log file, otherwise push into the invalid.log file.

Note: 

You are free to use the Internet to research the problems. In case you face any issues, please don't hesitate to ask.

Upload your answers below
Before uploading please ensure that you follow the scheme below:

Please include a README file with details like compiler used, libraries required and instructions on how to run the code.
You can upload answer to any of the questions any time within 5 hours
Create a directory with name as "your_name-DDMMYY_Qnumber" where DDMMYY is the date and Qnumber is question number.
Put your solution in this directory and include a readme file.
Zip/tar the diretory "your_name-DDMMYY_Qnumber" and upload the entire zip here.
Please note that other than zip and tar.gz all other formats of archiving will be rejected

Example: For someone named Aragorn, Aragorn-31122012_Q1.zip, Aragorn-31122012_Q2.tar, Aragorn-31122012_Q3.tar.gz are valid answer archives. 

Read More..

Citicorp Written Test

Written Test

Section-1 : C programming 25 Questions 35 mins.
Section-2 : Quants 16 Questions 16 min.
Section-3 : Logical Aptitude 15 Questions 14 min
Section-4 : C Programming 2 Questions 80 min

NOTE : Different question set for each student,programming questions are also different. No switching is allowed between the question.

Sample Programming Questions

Question-1

You are given a string and u need to encrypt it

for eg:
01234 0123 012 0123456
hello dere and welcome (given string)
hfnos dfth .. ..       (output string)

So you need to add the index of character to itself. Also if the character is 'z' and you have to add say 3 to it then it should wrap around and be 'c'. If it is 'Z' then it should be 'C'

Question-2

you are given a matrix (m x n) of which elements in its first row and col are 0 rest of them are 1 except one, and that one element is 9 you have to find location of that 9. It should be done with dynamic programming.

Question-3

A adjacency matrix is given and  you need to find whether it represents Graph or Tree?

Question-4

To traverse the link list and find if there is a cycle in that link list.

All The Best.

Read More..

Cisco Campus Selection

WRITTEN TEST

No. of Questions : 50(20 Qunt + 30 Technical)
Time Limit : 60 Mins
Question type : MCQ

-No negative marking. Mark all answers luck matters :P

Subject Covered in Aptitude Test:

-Digital Logic Desing
-Number Representation
-Flip Flops
-Virtual Memory
-Microprocessor
-DBMS
-OS

Sample Questions :

1. 8 queens problem Recursive

2. Venn diagram ques

3. Area of a circle ques

4. One ques on semaphore

5. Diff between PAM and AM

6. JK flip flop

7. hamming code

8. Boolean function

9. SUB B instruction of 8085

10. RST of 8085

11. minimum number of NAND gates required in Y=A+AB’+AB’C

12. If 423 is multiplied by x and answer is 45569, and 55 are wrong digits, find the right product.
Answer : 35

13. What is a numb that leaves remainder 3 when divided by 5, 6, 7, 8 but 0 when divided by 9.

14. Address of RST6 in 8085

15. No of binary trees possible with n nodes?

16. A goat is tied to a corner of u square, with 7m rope. find the area of grazing?

17. Why Avalanche diode preferred to PIn diodel?

18. One question on flipflop

19. What is Zener diode?


-Two aptitude questions on averages.

-Three on ordering(A can come before B blah blah blah)

-One heights and distances(pythagorean)

-One directions.

Personal Interviews:

-Questions on Processors (core2duo , i3 etc)
-OS (multi-processor scheduling)
-DBMS (transactions)
-Networks(internet super server, TCP, Ping command etc)
-Compilers (phases of compilation)
-A puzzle.

All The Best.

Read More..

Microsoft Campus Selection Guide

Selection Procedure

Written Test

Number of Questions : 15 + 2 Coding
Time : 30 Minutes + 1 hour for Coding

Area Cover :
C, C++(Questions from "Test Your C++ skill"), OS(Pagging), COA(Caching)

Note : Given answer of the following questions may or may not correct.

Sample Questions:

1. 48 bit architecture , what is size of virtual address space? 2^48 bytes

2. 1 rabbit couple. Couple will start producing other couple only when their age is one month.Initially in first month one couple is there.
how many couples will be at the end of year.

Hint : fibonacci series

3. Some cpp codes and asked output. (i.e. Virtual Functions from "Test your C++ skill")

4. C codes and output.

5. Find bugs in given code.

6. Complexity of BFS if adjacency list is given.

7. What is used in Demand paging

a) sequential search b) binary search

8. If pointer to function is declared then how to call that function.

9. In a tree every node has 2 children or 0 children. if there are 'n' nodes with 2 children then
how many with 0 children? ans: n+1

10. If we add a constant weight to each edge in a graph will the shortest path “between any two
vertices” change ?

Ans: (May or may not change) //*this will be Depends, not NO, consider a graph whose one
path from A to B has 4 edges of 1 and other path with 2 and 3, now add 1 to all edges..now
shortest path becomes 2 and 3*

11. how many '0' in 100! ? ans: 24 (/5+⅘)100/5+20

12. For recursive fibonacci , what is its complexity ? ans : O(2 pow n)

13.
i=2,
printf("%d%d",++i,++i)

Ans : May be depend on compiler. Check it.

14.
int c[]={2,3,4,5,6},
int *p=c, int *q=c,
(1)for(i=1 to 5){printf("%d",*c); q++}
(2)for(i=1 to 5){printf("%d",*p); p++}


15. x=4|3<<4 ; x= ? ans : 52

16. x= 2, y= 4, z=10 ; if (x<y<z) {printf("abc")} else {printf("pqr")} ?  Ans : abc

17. x=1; mask = ~(x<<5 1)

18. What is
(1) mask & 48
(2) mask & 64
(3) mask & 121

Ans: 32 64 105

19. In an page fault system implementation , what is “good” way to access pages ?
(1) Linear search
(2) Arithmetic indirection
(3) Binary search .
(4) Vector Operation


Ans : 4)and (1)..it was a multiple correct type

20. which of the foll gives most efficient way to access elements sequentially?
(1) LL
(2) DLL
(3) vectors

21. what is the output ?

class A {public: void foo(){printf("a");}};
class B : public A { public: void foo(){printf("b")}};
class C : public B { public: void foo(){printf("c")}};

void foo(B &b){
b.foo();
}

main(){
C c;
foo(c);
}

output : b

22. What is the data structure that has O(log n)complexity on averaging for the operations:
search, insert, delete.

Ans : AVL Tree correct?

23. Find the output:

#include<stdio.h>
int fun(int num) {
while(num > 0) {
num=num*fun(num1);
}
return num;
}
void main() {
x = fun(8);
printf(“%d”,x);
}

Ans : 0

24. Find the output:

int fun(int num)
{
if(num<3)
return 3;
return num+fun(num2);
}
main()
{
int x=fun(12);
int y=fun(13);
printf(“%d %d”,x,y);
}

Ans : 43 51

25.
unsigned int i = 1<<10;
for(; i>=0; i)
printf(“%d\n”, i);

Ans: Infinite loop

26. how to call pointer to a function:
Ans:(*foo)(2) , foo(2) (both are correct)

27.
unsigned int a=1;
unsigned int b=~1;
int z=a*b;
printf(“%d”,z);

Ans: 2

28.
int n = 1000, c = 5;
do{
n/=c;
}while(c);
printf(“%d”, n);

Ans: Arithmetic error (divide by 0)

29.
class A{
public: A()
{
cout <<”AC ”;
}
~A()
{
cout <<”AD “;
}
};

class B: public A
{
public: B()
{ cout<<”BC “;
}
~B(){cout <<”BD “;}
};

main()
{
B *b1 = new B();
B b2;
}

Ans: AC BC AC BC BD AD

30.
int fun(int num){
if(num < 3) return 3;
return num + fun(num2);
}

main(){
printf(“%d %d\n”, fun(12), fun(13));
}

Ans: 43,51

31.
void swap(int *a, int *b)
(a) call by name
(b) call by value
(c) call by reference
(d) call by pointer

Ans: Call By Pointer becoz in C++ we have both CBR and CBP and in C++ for CBR we dont
use * in operation we refer object only just by their name in CBR

32.
int fun(int num){
int val = num<<3;
val += num;
return val;
}
main(){
printf(“%d %d %d\n”, fun(0), fun(1), fun(3));
}

Ans: 0 9 27

33.
int MAX=1000;
int a[MAX][MAX];
for(i=0;i<MAX;i++)
for(j=0;j<MAX;j++)
a[j]=i*j;Q.1.
code 1:
code 2:
int MAX=1000;
int a[MAX][MAX];
for(i=0;i<MAX;i++)
for(j=0;j<MAX;j++)
a[i]=i*j;
Which is correct?
a. code 1 is faster
b. code 2 is faster
c. both are same in RISC architecture
d. both are about same

Hint : Caching Mechanism; Refer COA/OS class note of ACE

34. What is the output:

unsigned int x = 1;
int y = ~0;
printf(“%u,%d”,x,)y;
if(x==y)
printf(“same”);
else
printf(“not same”);
a. compilation error.
b. 45….,1
same
c. 45….,1
not same
d. i don’t remember

Ans : B

Sample Coding Questions

Question-1

With a specific color denoted by single character eg. for blue ‘B’. If one position is clicked
(x,y), colour present at that position would be deleted. If the same colour is present in
neighbourhood (up/down/left/right) then it would also be deleted. After deletion blank spaces
will be replaced by the value present in the cell above that. In case no value present above the1.
Given a 2D matrix. Each cell was filled cell then blank entry will be replaced by 0.

Input
x:1 y:1
BGB
BGG
BBB

Output
B00
B0B
BBB

Question-2

Given a linkedlist swap the alternative nodes (assume list have even number of nodes.)
Input : 11>12>13>14
Output : 12>11>14>13

Question-3

Given 2 strings, check if they are anagrams of each other.

Question-4

Delete every nth node in a linkedlist.

Let the LL be, 1>2>3>4>5 and n = 2, then resultant list will be: 1>3>5

Question-5

print last 10 lines of given very large string

Question-6

prune all the nodes from a BST which are not in the range minValue and maxValue

Question-7

In a TicTacToi game two players are playing where player 0 is denoted as 0 and player 1 is denoted as 1. Given a linked list of moves made by the players determine who is the winner and in how many moves he required for winning.

Struct Move{
int p; //Player number
int x; //x and y pos in the tictactoi
int y;
struct Move *next;
};
The sample function to write is:
void playGame(struct Move *move, int N)

Question-8

Given an array if in a position let a[i][j] =1 then print all it’s row and column 1. You should not
consider a position 1 after you made it 1 in your past computation.
sample(input):
(i)00100
(ii)10 00000 01
output:
(i)11111
(ii)11 00100 11


Refer GeekForGeeks for solution of the above coding questions.

Courtesy : Inter IIT Placement Group.

All The Best

Read More..

Oracle Coding Skill

Coding Skills (Advanced)

Please read all instructions very carefully before you begin.

This is the PAC – Coding Skills (Advanced Level) assessment.

It is composed of 20 questions.

You will have 40 minutes to complete this assessment. Please note that once you have completed a question you will NOT be able to return to it in order to make changes.

No points will be deducted for wrong answers.

This assessment incrementally develops an implementation of a certain kind of tree structure. (Its definition and an example will be presented with each question.) Along the way you will be asked questions to test your understanding of the implementation and ability to think about its design. The code presented will be in Java, but will not use any advanced features of the language and should be easily understood by someone more familiar with C++.

Wherever a question shows a class definition assume that the class contains other methods that are omitted for the purposes of the question. When a question shows methods for some classes but not others it means the other classes do not define those methods.

Assume that all code is syntactically correct. The questions are not intended to test your knowledge of language details.

Assume that all methods are public; the questions have nothing to do with access restrictions.

Assessment Breakdown

Section 1 :  20 Minutes : 10 Questions
Section 2 : 20 Minutes : 10 Questions

Totals 40 Minutes :  20 Questions

Question Number 1

The subject of these questions is an unusually simple kind of binary tree, defined by these properties:

Terminal nodes contain a string.
Internal nodes have one or two children, called "left" and "right".
Either child of an internal node may be null, but not both.
Internal nodes contain no other information.
By "tree" we simply mean a node and all of its descendants.
A tree rooted at a node having left child A and right child B is a different tree than one rooted at a node having left child B and right child A.
Here's an example, with plus signs (+) used to indicate internal nodes:

                                +
                               / \
                              /   \
                             /     \
                            +       +
                           /       / \
                          /       /   \
                         /       /     \
                       "A"      +      "D"
                               / \
                              /   \
                             /     \
                           "B"     "C"
class InternalNode extends Node {
    Node left, right;

    InternalNode(node l, node r) {
        left = l;
        right = r;
    }
}
What should be done to modify the constructor to handle the case when both l and r are null?

(a) Nothing—it’s OK
(b) Assert that they can’t both be null
(c) Throw an exception if both are null
(d) Create terminal nodes for left and right with null values

Question Number 2

The subject of these questions is an unusually simple kind of binary tree, defined by these properties:

Terminal nodes contain a string.
Internal nodes have one or two children, called "left" and "right".
Either child of an internal node may be null, but not both.
Internal nodes contain no other information.
By "tree" we simply mean a node and all of its descendants.
A tree rooted at a node having left child A and right child B is a different tree than one rooted at a node having left child B and right child A.
Here's an example, with plus signs (+) used to indicate internal nodes:

                                +
                               / \
                              /   \
                             /     \
                            +       +
                           /       / \
                          /       /   \
                         /       /     \
                       "A"      +      "D"
                               / \
                              /   \
                             /     \
                           "B"     "C"
abstract class Node {
}

class TerminalNode extends Node {
    String value;
    String getValue() {
        return value;
    }
}

class InternalNode extends Node {
}

What constructors should TerminalNode have according to the specifications for the tree structure?

TerminalNode(String)

TerminalNode(Node)


(a) A
(b) B
(c) Both
(d) Neither

Question Number 3

The subject of these questions is an unusually simple kind of binary tree, defined by these properties:

Terminal nodes contain a string.
Internal nodes have one or two children, called "left" and "right".
Either child of an internal node may be null, but not both.
Internal nodes contain no other information.
By "tree" we simply mean a node and all of its descendants.
A tree rooted at a node having left child A and right child B is a different tree than one rooted at a node having left child B and right child A.
Here's an example, with plus signs (+) used to indicate internal nodes:

                                +
                               / \
                              /   \
                             /     \
                            +       +
                           /       / \
                          /       /   \
                         /       /     \
                       "A"      +      "D"
                               / \
                              /   \
                             /     \
                           "B"     "C"
class InternalNode extends Node {
    %%% left, right;
}
What type should replace %%% in the above?


(a) Object
(b) Node
(c) InternalNode
(d) TerminalNode

Question Number 4

The subject of these questions is an unusually simple kind of binary tree, defined by these properties:

Terminal nodes contain a string.
Internal nodes have one or two children, called "left" and "right".
Either child of an internal node may be null, but not both.
Internal nodes contain no other information.
By "tree" we simply mean a node and all of its descendants.
A tree rooted at a node having left child A and right child B is a different tree than one rooted at a node having left child B and right child A.
Here's an example, with plus signs (+) used to indicate internal nodes:

                                +
                               / \
                              /   \
                             /     \
                            +       +
                           /       / \
                          /       /   \
                         /       /     \
                       "A"      +      "D"
                               / \
                              /   \
                             /     \
                           "B"     "C"
class InternalNode extends Node {
    Node left, right;
}
What constructors should InternalNode have according to the specifications for the tree structure?


InternalNode(String)

InternalNode(Node)

InternalNode(Node, Node)


(a) A
(b) B
(c) C
(d) More than one of the choices

Question Number 5

Given a code snippet answer the following question.

struct AVLTree
{
  AVLTree * left;
  AVLTree * right;
  int element;
  int height;
};
int MAX(int a, int b){
    if(a>=b)
        return a;
    if(a<b)
        return b;
}
int height(AVLTree *node)
{
  if (node == NULL)
  {
    return -1;
  }
  else
  {
    return node->height;
  }
}
AVLTree * single_rotation_with_left(AVLTree *k2)//Func1
{
  AVLTree *k1;
  k1 = k2->left;
  k2->left = k1->right;
  k1->right = k2;
  k2->height = MAX(height(k2->left), height(k2->right)) + 1;
  k1->height = MAX(height(k1->left), height(k2->right)) + 1;
  return k1;
}

AVLTree * single_rotation_with_right(AVLTree *k2)//Func2
{
  AVLTree *k1;
  k1 = k2->right;
  k2->right = k1->left;
  k1->left = k2;
  k2->height = MAX(height(k2->left), height(k2->right)) + 1;
  k1->height = MAX(height(k1->right), height(k2->left)) + 1;
  return k1;
}
AVLTree *double_rotation_with_left(AVLTree *k3)
{
  k3->left = single_rotation_with_right(k3->left);
  return single_rotation_with_left(k3);
}

AVLTree *double_rotation_with_right(AVLTree *k3)
{
  k3->right = single_rotation_with_left(k3->right);
  return single_rotation_with_right(k3);
}
void insert(int value, AVLTree **node)
{
  if (*node == NULL)
  {
    *node = new AVLTree;
    if (*node == NULL)
    {
        return;
    }
    (*node)->element = value;
    (*node)->height = 0;
    (*node)->left = (*node)->right = NULL;
    return;
  }
  else if (value < (*node)->element)
  {
    insert(value, &((*node)->left));
    if (height((*node)->left) - height((*node)->right) == 2)
    {
      if (value < (*node)->left->element)
      {
        *node = single_rotation_with_left(*node);
      }
      else
      {
        *node = double_rotation_with_left(*node);
      }
    }
  }
  else if (value > (*node)->element)
  {
    insert(value, &((*node)->right));
    if (height((*node)->right) - height((*node)->left) == 2)
    {
      if (value > (*node)->right->element)
      {
        *node = single_rotation_with_right(*node);
      }
      else
      {
        *node = double_rotation_with_right(*node);
      }
    }
   }

  (*node)->height = MAX(height((*node)->left), height((*node)->right)) + 1;
}
AVLTree *searchmin(AVLTree *node)
{
  if (node == NULL)
  {
    return NULL;
  }
  else if (node->left == NULL)
  {
    return node;
  }
  else
  {
    return searchmin(node->left);
  }
}
AVLTree *searchmax(AVLTree *node)
{
  if (node == NULL)
  {
    return NULL;
  }
  else if (node->right == NULL)
  {
    return node;
  }
  else
  {
    return searchmax(node->right);
  }
}

void Search(AVLTree **parent,AVLTree **node,int i){
    while((*node!=NULL)&&((*node)->element != i)){
        parent = node;
        if((*node)->element >i)
            *node = (*node)->left;
        else
            *node = (*node)->right;
    }
}

AVLTree * del(int value, AVLTree **node)
{
  AVLTree * x;
  AVLTree *tmp_cell;

  if (*node ==NULL) return NULL;

  if (value < (*node)->element)
  {
    (*node)->left = del(value, &((*node)->left));

    if (height((*node)->right) - height((*node)->left) >= 2)
    {
      if ((*node)->left && (value < (*node)->left->element))
      {
        (*node) = double_rotation_with_right((*node));
      }
      else
      {
        (*node) = single_rotation_with_right((*node));
      }
    }
  }
  else if (value > (*node)->element)
  {
    (*node)->right = del(value, &((*node)->right));

    if (height((*node)->left) - height((*node)->right) >= 2)
    {
      if ((*node)->right && (value > (*node)->right->element))
      {
        (*node) = double_rotation_with_left((*node));
      }
      else
      {
        (*node) = single_rotation_with_left((*node));
      }
    }

  }
  else if ((*node)->left && (*node)->right)
  {
    tmp_cell = searchmin((*node)->right);
    (*node)->element = tmp_cell->element;
    (*node)->right = del((*node)->element, &((*node)->right));
  }
  else
  {
    tmp_cell = (*node);
    if ((*node)->left == NULL)
      (*node) = (*node)->right;
    else if ((*node)->right == NULL)
      (*node) = (*node)->left;
    free(tmp_cell);
    tmp_cell = NULL;
  }
  return (*node);
}

int numofnode(AVLTree **p)
{
    if ((*p!=0)&&((*p)->element != 13))
        return numofnode (&(*p)->right) + numofnode (&(*p)->left) + 1;
    else
        return 0;
}
Consider an input sequence that is provided as an input to the insert method
20,50,45,30,35,55,10,100,90,70,5,99,8,96
Give the resulting tree and 45 as input to the method called Del. After Del gets executed, use the insert method to insert 45.
What would be the height of the node 45 in the resulting tree?


(a) 0
(b) 3
(c) 4
(d) 2

Question Number 6

Given a code snippet answer the following question.

struct AVLTree
{
  AVLTree * left;
  AVLTree * right;
  int element;
  int height;
};
int MAX(int a, int b){
    if(a>=b)
        return a;
    if(a<b)
        return b;
}
int height(AVLTree *node)
{
  if (node == NULL)
  {
    return -1;
  }
  else
  {
    return node->height;
  }
}
AVLTree * single_rotation_with_left(AVLTree *k2)//Func1
{
  AVLTree *k1;
  k1 = k2->left;
  k2->left = k1->right;
  k1->right = k2;
  k2->height = MAX(height(k2->left), height(k2->right)) + 1;
  k1->height = MAX(height(k1->left), height(k2->right)) + 1;
  return k1;
}

AVLTree * single_rotation_with_right(AVLTree *k2)//Func2
{
  AVLTree *k1;
  k1 = k2->right;
  k2->right = k1->left;
  k1->left = k2;
  k2->height = MAX(height(k2->left), height(k2->right)) + 1;
  k1->height = MAX(height(k1->right), height(k2->left)) + 1;
  return k1;
}
AVLTree *double_rotation_with_left(AVLTree *k3)
{
  k3->left = single_rotation_with_right(k3->left);
  return single_rotation_with_left(k3);
}

AVLTree *double_rotation_with_right(AVLTree *k3)
{
  k3->right = single_rotation_with_left(k3->right);
  return single_rotation_with_right(k3);
}
void insert(int value, AVLTree **node)
{
  if (*node == NULL)
  {
    *node = new AVLTree;
    if (*node == NULL)
    {
        return;
    }
    (*node)->element = value;
    (*node)->height = 0;
    (*node)->left = (*node)->right = NULL;
    return;
  }
  else if (value < (*node)->element)
  {
    insert(value, &((*node)->left));
    if (height((*node)->left) - height((*node)->right) == 2)
    {
      if (value < (*node)->left->element)
      {
        *node = single_rotation_with_left(*node);
      }
      else
      {
        *node = double_rotation_with_left(*node);
      }
    }
  }
  else if (value > (*node)->element)
  {
    insert(value, &((*node)->right));
    if (height((*node)->right) - height((*node)->left) == 2)
    {
      if (value > (*node)->right->element)
      {
        *node = single_rotation_with_right(*node);
      }
      else
      {
        *node = double_rotation_with_right(*node);
      }
    }
   }

  (*node)->height = MAX(height((*node)->left), height((*node)->right)) + 1;
}
AVLTree *searchmin(AVLTree *node)
{
  if (node == NULL)
  {
    return NULL;
  }
  else if (node->left == NULL)
  {
    return node;
  }
  else
  {
    return searchmin(node->left);
  }
}
AVLTree *searchmax(AVLTree *node)
{
  if (node == NULL)
  {
    return NULL;
  }
  else if (node->right == NULL)
  {
    return node;
  }
  else
  {
    return searchmax(node->right);
  }
}

void Search(AVLTree **parent,AVLTree **node,int i){
    while((*node!=NULL)&&((*node)->element != i)){
        parent = node;
        if((*node)->element >i)
            *node = (*node)->left;
        else
            *node = (*node)->right;
    }
}

AVLTree * del(int value, AVLTree **node)
{
  AVLTree * x;
  AVLTree *tmp_cell;

  if (*node ==NULL) return NULL;

  if (value < (*node)->element)
  {
    (*node)->left = del(value, &((*node)->left));

    if (height((*node)->right) - height((*node)->left) >= 2)
    {
      if ((*node)->left && (value < (*node)->left->element))
      {
        (*node) = double_rotation_with_right((*node));
      }
      else
      {
        (*node) = single_rotation_with_right((*node));
      }
    }
  }
  else if (value > (*node)->element)
  {
    (*node)->right = del(value, &((*node)->right));

    if (height((*node)->left) - height((*node)->right) >= 2)
    {
      if ((*node)->right && (value > (*node)->right->element))
      {
        (*node) = double_rotation_with_left((*node));
      }
      else
      {
        (*node) = single_rotation_with_left((*node));
      }
    }

  }
  else if ((*node)->left && (*node)->right)
  {
    tmp_cell = searchmin((*node)->right);
    (*node)->element = tmp_cell->element;
    (*node)->right = del((*node)->element, &((*node)->right));
  }
  else
  {
    tmp_cell = (*node);
    if ((*node)->left == NULL)
      (*node) = (*node)->right;
    else if ((*node)->right == NULL)
      (*node) = (*node)->left;
    free(tmp_cell);
    tmp_cell = NULL;
  }
  return (*node);
}

int numofnode(AVLTree **p)
{
    if ((*p!=0)&&((*p)->element != 13))
        return numofnode (&(*p)->right) + numofnode (&(*p)->left) + 1;
    else
        return 0;
}
Consider an input sequence that is provided as an input to the insert method
20,50,45,30,35,55,10,100,90,70,5,99,8,96
The resulting tree is given as input to the following code snippet

int nol(AVLNode **p)
{
    if (*p==0)
        return 0;  
    if ((*p)->left==0 && (*p)->right ==0)
        return 1;
    else
        return (nol(&(*p)->right)+nol(&(*p)->left) + 1);
}

Which one of the following would be the output of above code snippet?

(a) 8
(b) 7
(c) 6
(d) 14

Question Number 7

Given a code snippet answer the following question.

struct AVLTree
{
  AVLTree * left;
  AVLTree * right;
  int element;
  int height;
};
int MAX(int a, int b){
    if(a>=b)
        return a;
    if(a<b)
        return b;
}
int height(AVLTree *node)
{
  if (node == NULL)
  {
    return -1;
  }
  else
  {
    return node->height;
  }
}
AVLTree * single_rotation_with_left(AVLTree *k2)//Func1
{
  AVLTree *k1;
  k1 = k2->left;
  k2->left = k1->right;
  k1->right = k2;
  k2->height = MAX(height(k2->left), height(k2->right)) + 1;
  k1->height = MAX(height(k1->left), height(k2->right)) + 1;
  return k1;
}

AVLTree * single_rotation_with_right(AVLTree *k2)//Func2
{
  AVLTree *k1;
  k1 = k2->right;
  k2->right = k1->left;
  k1->left = k2;
  k2->height = MAX(height(k2->left), height(k2->right)) + 1;
  k1->height = MAX(height(k1->right), height(k2->left)) + 1;
  return k1;
}
AVLTree *double_rotation_with_left(AVLTree *k3)
{
  k3->left = single_rotation_with_right(k3->left);
  return single_rotation_with_left(k3);
}

AVLTree *double_rotation_with_right(AVLTree *k3)
{
  k3->right = single_rotation_with_left(k3->right);
  return single_rotation_with_right(k3);
}
void insert(int value, AVLTree **node)
{
  if (*node == NULL)
  {
    *node = new AVLTree;
    if (*node == NULL)
    {
        return;
    }
    (*node)->element = value;
    (*node)->height = 0;
    (*node)->left = (*node)->right = NULL;
    return;
  }
  else if (value < (*node)->element)
  {
    insert(value, &((*node)->left));
    if (height((*node)->left) - height((*node)->right) == 2)
    {
      if (value < (*node)->left->element)
      {
        *node = single_rotation_with_left(*node);
      }
      else
      {
        *node = double_rotation_with_left(*node);
      }
    }
  }
  else if (value > (*node)->element)
  {
    insert(value, &((*node)->right));
    if (height((*node)->right) - height((*node)->left) == 2)
    {
      if (value > (*node)->right->element)
      {
        *node = single_rotation_with_right(*node);
      }
      else
      {
        *node = double_rotation_with_right(*node);
      }
    }
   }

  (*node)->height = MAX(height((*node)->left), height((*node)->right)) + 1;
}
AVLTree *searchmin(AVLTree *node)
{
  if (node == NULL)
  {
    return NULL;
  }
  else if (node->left == NULL)
  {
    return node;
  }
  else
  {
    return searchmin(node->left);
  }
}
AVLTree *searchmax(AVLTree *node)
{
  if (node == NULL)
  {
    return NULL;
  }
  else if (node->right == NULL)
  {
    return node;
  }
  else
  {
    return searchmax(node->right);
  }
}

void Search(AVLTree **parent,AVLTree **node,int i){
    while((*node!=NULL)&&((*node)->element != i)){
        parent = node;
        if((*node)->element >i)
            *node = (*node)->left;
        else
            *node = (*node)->right;
    }
}

AVLTree * del(int value, AVLTree **node)
{
  AVLTree * x;
  AVLTree *tmp_cell;

  if (*node ==NULL) return NULL;

  if (value < (*node)->element)
  {
    (*node)->left = del(value, &((*node)->left));

    if (height((*node)->right) - height((*node)->left) >= 2)
    {
      if ((*node)->left && (value < (*node)->left->element))
      {
        (*node) = double_rotation_with_right((*node));
      }
      else
      {
        (*node) = single_rotation_with_right((*node));
      }
    }
  }
  else if (value > (*node)->element)
  {
    (*node)->right = del(value, &((*node)->right));

    if (height((*node)->left) - height((*node)->right) >= 2)
    {
      if ((*node)->right && (value > (*node)->right->element))
      {
        (*node) = double_rotation_with_left((*node));
      }
      else
      {
        (*node) = single_rotation_with_left((*node));
      }
    }

  }
  else if ((*node)->left && (*node)->right)
  {
    tmp_cell = searchmin((*node)->right);
    (*node)->element = tmp_cell->element;
    (*node)->right = del((*node)->element, &((*node)->right));
  }
  else
  {
    tmp_cell = (*node);
    if ((*node)->left == NULL)
      (*node) = (*node)->right;
    else if ((*node)->right == NULL)
      (*node) = (*node)->left;
    free(tmp_cell);
    tmp_cell = NULL;
  }
  return (*node);
}

int numofnode(AVLTree **p)
{
    if ((*p!=0)&&((*p)->element != 13))
        return numofnode (&(*p)->right) + numofnode (&(*p)->left) + 1;
    else
        return 0;
}
Consider an input sequence that is provided as an input to the insert method
20,50,45,30,35,55,10,100,90,70,5,99,8,96
What would be the height of the node 55 in the resulting tree?


(a) 4
(b) 3
(c) 0
(d) None of these

Question Number 8

The subject of these questions is an unusually simple kind of binary tree, defined by these properties:

Terminal nodes contain a string.
Internal nodes have one or two children, called "left" and "right".
Either child of an internal node may be null, but not both.
Internal nodes contain no other information.
By "tree" we simply mean a node and all of its descendants.
A tree rooted at a node having left child A and right child B is a different tree than one rooted at a node having left child B and right child A.
Here's an example, with plus signs (+) used to indicate internal nodes:

                                +
                               / \
                              /   \
                             /     \
                            +       +
                           /       / \
                          /       /   \
                         /       /     \
                       "A"      +      "D"
                               / \
                              /   \
                             /     \
                           "B"     "C"
The height of a tree is defined as follows:
The height of a terminal node is 0.
The height of an internal node is 1 + the maximum of the heights of its children.
Suppose it is specified that height() will only be called on InternalNodes.
Consider the following a implementation of InternalNode.height(), with no implementation in either Node or TerminalNode?

    int height() {
        int lheight = (left == null) ? 0 : left.height();
        int rheight = (right == null) ? 0 : right.height();
        return (lheight > rheight ? lheight : rheight);
    }

Which, if any, of the following are problems that will cause the above code to fail:

It won’t compile because there is no definition (concrete or abstract) in Node.

1 should be added to the value of the return


(a) The code is correct as is.
(b) A: it won’t compile, but if that were fixed it would work and produce the correct result.
(c) B: it will compile but produce the wrong result.
(d) Both: it won’t compile, and even if that were fixed, it would produce the wrong result.

Question Number 9

The subject of these questions is an unusually simple kind of binary tree, defined by these properties:

Terminal nodes contain a string.
Internal nodes have one or two children, called "left" and "right".
Either child of an internal node may be null, but not both.
Internal nodes contain no other information.
By "tree" we simply mean a node and all of its descendants.
A tree rooted at a node having left child A and right child B is a different tree than one rooted at a node having left child B and right child A.
Here's an example, with plus signs (+) used to indicate internal nodes:

                                +
                               / \
                              /   \
                             /     \
                            +       +
                           /       / \
                          /       /   \
                         /       /     \
                       "A"      +      "D"
                               / \
                              /   \
                             /     \
                           "B"     "C"
Which of the following is the first to correctly define methods for counting the empty subtrees of a tree? (Only the relevant methods are shown for each class, and if the class isn’t shown in the answer it doesn’t contain a countEmptySubtrees member.)



class InternalNode extends Node {
    int countEmptySubtrees() {
        return left.countEmptySubtrees()) + right.countEmptySubtrees());
    }
}


class InternalNode extends Node {
    int countEmptySubtrees() {
        return
            ((left == null) ? 1 : left. countEmptySubtrees()) +
            ((right == null) ? 1 : right. countEmptySubtrees());
    }
}


abstract class Node {
    abstract int countEmptySubtrees();
}

class TerminalNode extends Node {
    int countEmptySubtrees() {
        return 0;
    }
}

class InternalNode extends Node {
    int countEmptySubtrees() {
        return
            ((left == null) ? 1 : left. countEmptySubtrees()) +
            ((right == null) ? 1 : right. countEmptySubtrees());
    }
}


(a) A
(b) B
(c) C
(d) None of them provide a correct implementation.

Question Number 10

The subject of these questions is an unusually simple kind of binary tree, defined by these properties:

Terminal nodes contain a string.
Internal nodes have one or two children, called "left" and "right".
Either child of an internal node may be null, but not both.
Internal nodes contain no other information.
By "tree" we simply mean a node and all of its descendants.
A tree rooted at a node having left child A and right child B is a different tree than one rooted at a node having left child B and right child A.
Here's an example, with plus signs (+) used to indicate internal nodes:

                                +
                               / \
                              /   \
                             /     \
                            +       +
                           /       / \
                          /       /   \
                         /       /     \
                       "A"      +      "D"
                               / \
                              /   \
                             /     \
                           "B"     "C"
We want to define Boolean contains(String str) to return True if the tree contains a node with str as its value and False otherwise. Here are definitions for two of the three classes:

abstract class Node {
    abstract boolean contains(String str);
}

class TerminalNode extends Node {
    boolean contains(String str) {
        return value.equals(str);
    }
}

Which of the following methods is the first to correctly implement contains for InternalNode?


class InternalNode extends Node {
    boolean contains(String str) {
        if (left.contains(str))
            return true;
        if (right.contains(str))
            return true;
    }
}


class InternalNode extends Node {
    boolean contains(String str) {
        if (left != null)
            return left.contains(str);
        if (right != null)
            return right.contains(str);
    }
}


class InternalNode extends Node {
    boolean contains(String str) {
        return
            ((left != null) && left.contains(str)) ||
            ((right != null) && right.contains(str));
    }
}


(a) A
(b) B
(c) C
(d) None of them is a correct implementation.

Read More..

Amazon Campus Selection

WRITTEN TEST

Aptitude Test : 45 Minutes
Technical          : 45 Minutes

Aptitude Test :

The aptitude was 20 questions general/technical MCQs and 2 coding questions on interviewstreet.com

Subject Covered in Aptitude Test:

-Computer Networks
-Operating System
-Language Processors
-Data Structure and Algorithms

Few questions from previous GATE papers.

The coding questions were quite easy.But do not get carried away if ur code works for the given few test cases. There are probably more cases for which it might fail to work.

Sample Questions :

1. Given the post-order traversal of a Binary Search Tree (BST), choose the correct pre-order traversal.

2. Consider a memory system where only one frame is there and it has the capacity to hold 100 records. In a pure demand paging system, how many page faults will occur for the following record access:
100 200 180 220 340 560 540 600 340

3. In UNIX, what happens to a child process if its parent dies?

4. A DFA was given and in the choices regular expressions were listed. We were supposed to choose those regular expressions that corresponded to the DFA.

5. Four regular expressions were given, and we were supposed to choose those that would accept a palindrome string.

6. What is the value of 'sum' in the following program excerpt?

int sum = 0;
for(int i=0;i<12;i++)
for(int j=i+1;j<10;j++)
for(int k=j+1;k<8;k++)
sum++;

7. A person observes that on a particular road, the probability of a car passing by is 0.85 in 30 minutes. What is the probability of a car passing bye in 10 minutes, provided constant average probability?

Technical :

Time Alloted (in minutes) : 45
No. of Questions : 2
Type of Questions : Programming

Sample Questions :

1. Given a sentence and a word, remove all occurrences of the word in the sentence.
For example, removing "is" from the sentence "This is a boy." becomes "Th a boy."

2. Given two sorted linked lists, merge them.

3. Given an string str and substring subs, if matching substring is found on the str, return the index otherwise return -1;

4. Given top(x,y) and bottom(x,y) of two rectangles, find if two rectangles have some common area return 1 otherwise return 0;

5. Given set of coins {1, 3, 4 ,5 }  find min number of coins required to get sum amount.

6. removeLoop() if loop exists and give the length of the linled list.

7. Given a (decimal - e.g. 21.125) number N that is passed in as a string, print the binary

8. Given an array of N elements, A[0 .. N - 1], Produce an array B such that: B[i] = min (A[i],A[i+1], ..., A[i+K-1]). (The array B will have exactly (N-k+1) elements.

9. http://www.geeksforgeeks.org/sum-of-two-linked-lists/ at nitw 2013

10. http://www.geeksforgeeks.org/check-if-a-given-binary-tree-is-sumtree/ at nitw 2013

11. find number of pairs in an array with difference k. Array has unique elements at IITD 2013

12. Second questions was same ashttp://www.geeksforgeeks.org/forums/topic/directi-coding-round-2/ at IITD 2013

Personal Interviews:

There are 4 rounds of interviews held each lasting anywhere from 30 min to an hour. Following were the questions asked.

1. Reverse a linked list using no extra memory or recursion (a very easy one to begin with)

2. Given a linked list, construct a tree whose inorder traversal would be the contents of the linked list.

3. With three files, each containing a day's data on the customers' page visiting pattern on a site, determine all customers that visited the site on exactly 2 days and viewed more that 3 distinct pages. The data was available as key-value pairs of customer IDs and page numbers.

4. Given a string of the form "aaabcc", convert it to the form "a3b1c2" without using any extra memory.

5. Given inorder and postorder traversal of a binary tree, trace the construction of the tree. Comment on the complexity if this construction is performed non-recursively.

6. Given a binary tree, pre-process it to be able to determine any node's inorder successor in constant time.

7. Design your own data structure that implements the following three functions in O(1) time:
a. push()
b. pop()
c. min() - returns the min element


At all times, the interviewer stressed on writing the code that not only handles the general cases but any of the special or edge cases. Lastly and most important of all, the biggest criterion for evaluation was the complexity of the algorithm proposed.

Read More..

Oracle Campus Selection Guide Part-2

Coding Skills (Advanced)

instructions 

It is composed of 20 questions.

You will have 40 minutes to complete this assessment. Please note that once you have completed a question you will NOT be able to return to it in order to make changes.

No points will be deducted for wrong answers.

This assessment incrementally develops an implementation of a certain kind of tree structure. (Its definition and an example will be presented with each question.) Along the way you will be asked questions to test your understanding of the implementation and ability to think about its design. The code presented will be in Java, but will not use any advanced features of the language and should be easily understood by someone more familiar with C++.

Wherever a question shows a class definition assume that the class contains other methods that are omitted for the purposes of the question. When a question shows methods for some classes but not others it means the other classes do not define those methods.

Assume that all code is syntactically correct. The questions are not intended to test your knowledge of language details.

Assume that all methods are public; the questions have nothing to do with access restrictions.

Assessment Breakdown

Section	Questions	Time
Section 1	10	Minutes 20
Section 2	10	Minutes 20
Total	19	Miinutes 40

Question Number 1

The subject of these questions is an unusually simple kind of binary tree, defined by these properties:

Terminal nodes contain a string.

Internal nodes have one or two children, called "left" and "right".

Either child of an internal node may be null, but not both.

Internal nodes contain no other information.

By "tree" we simply mean a node and all of its descendants.

A tree rooted at a node having left child A and right child B is a different tree than one rooted at a node having left child B and right child A.

Here's an example, with plus signs (+) used to indicate internal nodes:

                                +

                               / \

                              /   \

                             /     \

                            +       +

                           /       / \

                          /       /   \

                         /       /     \

                       "A"      +      "D"

                               / \

                              /   \

                             /     \

                           "B"     "C"

class InternalNode extends Node {

    Node left, right;

    InternalNode(node l, node r) {

        left = l;

        right = r;

    }

}

What should be done to modify the constructor to handle the case when both l and r are null?

(a) Nothing—it’s OK

(b) Assert that they can’t both be null

(c) Throw an exception if both are null

(d) Create terminal nodes for left and right with null values

Question Number 2

The subject of these questions is an unusually simple kind of binary tree, defined by these properties:

Terminal nodes contain a string.

Internal nodes have one or two children, called "left" and "right".

Either child of an internal node may be null, but not both.

Internal nodes contain no other information.

By "tree" we simply mean a node and all of its descendants.

A tree rooted at a node having left child A and right child B is a different tree than one rooted at a node having left child B and right child A.

Here's an example, with plus signs (+) used to indicate internal nodes:

                                +

                               / \

                              /   \

                             /     \

                            +       +

                           /       / \

                          /       /   \

                         /       /     \

                       "A"      +      "D"

                               / \

                              /   \

                             /     \

                           "B"     "C"

abstract class Node {

}

class TerminalNode extends Node {

    String value;

    String getValue() {

        return value;

    }

}

class InternalNode extends Node {

}

What constructors should TerminalNode have according to the specifications for the tree structure?

TerminalNode(String)

TerminalNode(Node)

           

(a) A

(b) B

(c) Both

(d) Neither

Question Number 3

The subject of these questions is an unusually simple kind of binary tree, defined by these properties:

Terminal nodes contain a string.

Internal nodes have one or two children, called "left" and "right".

Either child of an internal node may be null, but not both.

Internal nodes contain no other information.

By "tree" we simply mean a node and all of its descendants.

A tree rooted at a node having left child A and right child B is a different tree than one rooted at a node having left child B and right child A.

Here's an example, with plus signs (+) used to indicate internal nodes:

                                +

                               / \

                              /   \

                             /     \

                            +       +

                           /       / \

                          /       /   \

                         /       /     \

                       "A"      +      "D"

                               / \

                              /   \

                             /     \

                           "B"     "C"

class InternalNode extends Node {

    %%% left, right;

}

What type should replace %%% in the above?

           

(a) Object

(b) Node

(c) InternalNode

(d) TerminalNode

Question Number 4

The subject of these questions is an unusually simple kind of binary tree, defined by these properties:

Terminal nodes contain a string.

Internal nodes have one or two children, called "left" and "right".

Either child of an internal node may be null, but not both.

Internal nodes contain no other information.

By "tree" we simply mean a node and all of its descendants.

A tree rooted at a node having left child A and right child B is a different tree than one rooted at a node having left child B and right child A.

Here's an example, with plus signs (+) used to indicate internal nodes:

                                +

                               / \

                              /   \

                             /     \

                            +       +

                           /       / \

                          /       /   \

                         /       /     \

                       "A"      +      "D"

                               / \

                              /   \

                             /     \

                           "B"     "C"

class InternalNode extends Node {

    Node left, right;

}

What constructors should InternalNode have according to the specifications for the tree structure?

InternalNode(String)

InternalNode(Node)

InternalNode(Node, Node)

           

(a) A

(b) B

(c) C

(d) More than one of the choices

Question Number 5

Given a code snippet answer the following question.

struct AVLTree

{

  AVLTree * left;

  AVLTree * right;

  int element;

  int height;

};

int MAX(int a, int b){

    if(a>=b)

        return a;

    if(a<b)

        return b;

}

int height(AVLTree *node)

{

  if (node == NULL)

  {

    return -1;

  }

  else

  {

    return node->height;

  }

}

AVLTree * single_rotation_with_left(AVLTree *k2)//Func1

{

  AVLTree *k1;

  k1 = k2->left;

  k2->left = k1->right;

  k1->right = k2;

  k2->height = MAX(height(k2->left), height(k2->right)) + 1;

  k1->height = MAX(height(k1->left), height(k2->right)) + 1;

  return k1;

}

AVLTree * single_rotation_with_right(AVLTree *k2)//Func2

{

  AVLTree *k1;

  k1 = k2->right;

  k2->right = k1->left;

  k1->left = k2;

  k2->height = MAX(height(k2->left), height(k2->right)) + 1;

  k1->height = MAX(height(k1->right), height(k2->left)) + 1;

  return k1;

}

AVLTree *double_rotation_with_left(AVLTree *k3)

{

  k3->left = single_rotation_with_right(k3->left);

  return single_rotation_with_left(k3);

}

AVLTree *double_rotation_with_right(AVLTree *k3)

{

  k3->right = single_rotation_with_left(k3->right);

  return single_rotation_with_right(k3);

}

void insert(int value, AVLTree **node)

{

  if (*node == NULL)

  {

    *node = new AVLTree;

    if (*node == NULL)

    {

        return;

    }

    (*node)->element = value;

    (*node)->height = 0;

    (*node)->left = (*node)->right = NULL;

    return;

  }

  else if (value < (*node)->element)

  {

    insert(value, &((*node)->left));

    if (height((*node)->left) - height((*node)->right) == 2)

    {

      if (value < (*node)->left->element)

      {

        *node = single_rotation_with_left(*node);

      }

      else

      {

        *node = double_rotation_with_left(*node);

      }

    }

  }

  else if (value > (*node)->element)

  {

    insert(value, &((*node)->right));

    if (height((*node)->right) - height((*node)->left) == 2)

    {

      if (value > (*node)->right->element)

      {

        *node = single_rotation_with_right(*node);

      }

      else

      {

        *node = double_rotation_with_right(*node);

      }

    }

   }

  (*node)->height = MAX(height((*node)->left), height((*node)->right)) + 1;

}

AVLTree *searchmin(AVLTree *node)

{

  if (node == NULL)

  {

    return NULL;

  }

  else if (node->left == NULL)

  {

    return node;

  }

  else

  {

    return searchmin(node->left);

  }

}

AVLTree *searchmax(AVLTree *node)

{

  if (node == NULL)

  {

    return NULL;

  }

  else if (node->right == NULL)

  {

    return node;

  }

  else

  {

    return searchmax(node->right);

  }

}

void Search(AVLTree **parent,AVLTree **node,int i){

    while((*node!=NULL)&&((*node)->element != i)){

        parent = node;

        if((*node)->element >i)

            *node = (*node)->left;

        else

            *node = (*node)->right;

    }

}

AVLTree * del(int value, AVLTree **node)

{

  AVLTree * x;

  AVLTree *tmp_cell;

  if (*node ==NULL) return NULL;

  if (value < (*node)->element)

  {

    (*node)->left = del(value, &((*node)->left));

    if (height((*node)->right) - height((*node)->left) >= 2)

    {

      if ((*node)->left && (value < (*node)->left->element))

      {

        (*node) = double_rotation_with_right((*node));

      }

      else

      {

        (*node) = single_rotation_with_right((*node));

      }

    }

  }

  else if (value > (*node)->element)

  {

    (*node)->right = del(value, &((*node)->right));

    if (height((*node)->left) - height((*node)->right) >= 2)

    {

      if ((*node)->right && (value > (*node)->right->element))

      {

        (*node) = double_rotation_with_left((*node));

      }

      else

      {

        (*node) = single_rotation_with_left((*node));

      }

    }

  }

  else if ((*node)->left && (*node)->right)

  {

    tmp_cell = searchmin((*node)->right);

    (*node)->element = tmp_cell->element;

    (*node)->right = del((*node)->element, &((*node)->right));

  }

  else

  {

    tmp_cell = (*node);

    if ((*node)->left == NULL)

      (*node) = (*node)->right;

    else if ((*node)->right == NULL)

      (*node) = (*node)->left;

    free(tmp_cell);

    tmp_cell = NULL;

  }

  return (*node);

}

int numofnode(AVLTree **p)

{

    if ((*p!=0)&&((*p)->element != 13))

        return numofnode (&(*p)->right) + numofnode (&(*p)->left) + 1;

    else

        return 0;

}

Consider an input sequence that is provided as an input to the insert method

20,50,45,30,35,55,10,100,90,70,5,99,8,96

Give the resulting tree and 45 as input to the method called Del. After Del gets executed, use the insert method to insert 45.

What would be the height of the node 45 in the resulting tree?

           

(a) 0

(b) 3

(c) 4

(d) 2

Question Number 6

Given a code snippet answer the following question.

struct AVLTree

{

  AVLTree * left;

  AVLTree * right;

  int element;

  int height;

};

int MAX(int a, int b){

    if(a>=b)

        return a;

    if(a<b)

        return b;

}

int height(AVLTree *node)

{

  if (node == NULL)

  {

    return -1;

  }

  else

  {

    return node->height;

  }

}

AVLTree * single_rotation_with_left(AVLTree *k2)//Func1

{

  AVLTree *k1;

  k1 = k2->left;

  k2->left = k1->right;

  k1->right = k2;

  k2->height = MAX(height(k2->left), height(k2->right)) + 1;

  k1->height = MAX(height(k1->left), height(k2->right)) + 1;

  return k1;

}

AVLTree * single_rotation_with_right(AVLTree *k2)//Func2

{

  AVLTree *k1;

  k1 = k2->right;

  k2->right = k1->left;

  k1->left = k2;

  k2->height = MAX(height(k2->left), height(k2->right)) + 1;

  k1->height = MAX(height(k1->right), height(k2->left)) + 1;

  return k1;

}

AVLTree *double_rotation_with_left(AVLTree *k3)

{

  k3->left = single_rotation_with_right(k3->left);

  return single_rotation_with_left(k3);

}

AVLTree *double_rotation_with_right(AVLTree *k3)

{

  k3->right = single_rotation_with_left(k3->right);

  return single_rotation_with_right(k3);

}

void insert(int value, AVLTree **node)

{

  if (*node == NULL)

  {

    *node = new AVLTree;

    if (*node == NULL)

    {

        return;

    }

    (*node)->element = value;

    (*node)->height = 0;

    (*node)->left = (*node)->right = NULL;

    return;

  }

  else if (value < (*node)->element)

  {

    insert(value, &((*node)->left));

    if (height((*node)->left) - height((*node)->right) == 2)

    {

      if (value < (*node)->left->element)

      {

        *node = single_rotation_with_left(*node);

      }

      else

      {

        *node = double_rotation_with_left(*node);

      }

    }

  }

  else if (value > (*node)->element)

  {

    insert(value, &((*node)->right));

    if (height((*node)->right) - height((*node)->left) == 2)

    {

      if (value > (*node)->right->element)

      {

        *node = single_rotation_with_right(*node);

      }

      else

      {

        *node = double_rotation_with_right(*node);

      }

    }

   }

  (*node)->height = MAX(height((*node)->left), height((*node)->right)) + 1;

}

AVLTree *searchmin(AVLTree *node)

{

  if (node == NULL)

  {

    return NULL;

  }

  else if (node->left == NULL)

  {

    return node;

  }

  else

  {

    return searchmin(node->left);

  }

}

AVLTree *searchmax(AVLTree *node)

{

  if (node == NULL)

  {

    return NULL;

  }

  else if (node->right == NULL)

  {

    return node;

  }

  else

  {

    return searchmax(node->right);

  }

}

void Search(AVLTree **parent,AVLTree **node,int i){

    while((*node!=NULL)&&((*node)->element != i)){

        parent = node;

        if((*node)->element >i)

            *node = (*node)->left;

        else

            *node = (*node)->right;

    }

}

AVLTree * del(int value, AVLTree **node)

{

  AVLTree * x;

  AVLTree *tmp_cell;

  if (*node ==NULL) return NULL;

  if (value < (*node)->element)

  {

    (*node)->left = del(value, &((*node)->left));

    if (height((*node)->right) - height((*node)->left) >= 2)

    {

      if ((*node)->left && (value < (*node)->left->element))

      {

        (*node) = double_rotation_with_right((*node));

      }

      else

      {

        (*node) = single_rotation_with_right((*node));

      }

    }

  }

  else if (value > (*node)->element)

  {

    (*node)->right = del(value, &((*node)->right));

    if (height((*node)->left) - height((*node)->right) >= 2)

    {

      if ((*node)->right && (value > (*node)->right->element))

      {

        (*node) = double_rotation_with_left((*node));

      }

      else

      {

        (*node) = single_rotation_with_left((*node));

      }

    }

  }

  else if ((*node)->left && (*node)->right)

  {

    tmp_cell = searchmin((*node)->right);

    (*node)->element = tmp_cell->element;

    (*node)->right = del((*node)->element, &((*node)->right));

  }

  else

  {

    tmp_cell = (*node);

    if ((*node)->left == NULL)

      (*node) = (*node)->right;

    else if ((*node)->right == NULL)

      (*node) = (*node)->left;

    free(tmp_cell);

    tmp_cell = NULL;

  }

  return (*node);

}

int numofnode(AVLTree **p)

{

    if ((*p!=0)&&((*p)->element != 13))

        return numofnode (&(*p)->right) + numofnode (&(*p)->left) + 1;

    else

        return 0;

}

Consider an input sequence that is provided as an input to the insert method

20,50,45,30,35,55,10,100,90,70,5,99,8,96

The resulting tree is given as input to the following code snippet

int nol(AVLNode **p)

{

    if (*p==0)

        return 0;   

    if ((*p)->left==0 && (*p)->right ==0)

        return 1;

    else

        return (nol(&(*p)->right)+nol(&(*p)->left) + 1);

}

Which one of the following would be the output of above code snippet?

           

(a) 8

(b) 7

(c) 6

(d) 14

Question Number 7

Given a code snippet answer the following question.

struct AVLTree

{

  AVLTree * left;

  AVLTree * right;

  int element;

  int height;

};

int MAX(int a, int b){

    if(a>=b)

        return a;

    if(a<b)

        return b;

}

int height(AVLTree *node)

{

  if (node == NULL)

  {

    return -1;

  }

  else

  {

    return node->height;

  }

}

AVLTree * single_rotation_with_left(AVLTree *k2)//Func1

{

  AVLTree *k1;

  k1 = k2->left;

  k2->left = k1->right;

  k1->right = k2;

  k2->height = MAX(height(k2->left), height(k2->right)) + 1;

  k1->height = MAX(height(k1->left), height(k2->right)) + 1;

  return k1;

}

AVLTree * single_rotation_with_right(AVLTree *k2)//Func2

{

  AVLTree *k1;

  k1 = k2->right;

  k2->right = k1->left;

  k1->left = k2;

  k2->height = MAX(height(k2->left), height(k2->right)) + 1;

  k1->height = MAX(height(k1->right), height(k2->left)) + 1;

  return k1;

}

AVLTree *double_rotation_with_left(AVLTree *k3)

{

  k3->left = single_rotation_with_right(k3->left);

  return single_rotation_with_left(k3);

}

AVLTree *double_rotation_with_right(AVLTree *k3)

{

  k3->right = single_rotation_with_left(k3->right);

  return single_rotation_with_right(k3);

}

void insert(int value, AVLTree **node)

{

  if (*node == NULL)

  {

    *node = new AVLTree;

    if (*node == NULL)

    {

        return;

    }

    (*node)->element = value;

    (*node)->height = 0;

    (*node)->left = (*node)->right = NULL;

    return;

  }

  else if (value < (*node)->element)

  {

    insert(value, &((*node)->left));

    if (height((*node)->left) - height((*node)->right) == 2)

    {

      if (value < (*node)->left->element)

      {

        *node = single_rotation_with_left(*node);

      }

      else

      {

        *node = double_rotation_with_left(*node);

      }

    }

  }

  else if (value > (*node)->element)

  {

    insert(value, &((*node)->right));

    if (height((*node)->right) - height((*node)->left) == 2)

    {

      if (value > (*node)->right->element)

      {

        *node = single_rotation_with_right(*node);

      }

      else

      {

        *node = double_rotation_with_right(*node);

      }

    }

   }

  (*node)->height = MAX(height((*node)->left), height((*node)->right)) + 1;

}

AVLTree *searchmin(AVLTree *node)

{

  if (node == NULL)

  {

    return NULL;

  }

  else if (node->left == NULL)

  {

    return node;

  }

  else

  {

    return searchmin(node->left);

  }

}

AVLTree *searchmax(AVLTree *node)

{

  if (node == NULL)

  {

    return NULL;

  }

  else if (node->right == NULL)

  {

    return node;

  }

  else

  {

    return searchmax(node->right);

  }

}

void Search(AVLTree **parent,AVLTree **node,int i){

    while((*node!=NULL)&&((*node)->element != i)){

        parent = node;

        if((*node)->element >i)

            *node = (*node)->left;

        else

            *node = (*node)->right;

    }

}

AVLTree * del(int value, AVLTree **node)

{

  AVLTree * x;

  AVLTree *tmp_cell;

  if (*node ==NULL) return NULL;

  if (value < (*node)->element)

  {

    (*node)->left = del(value, &((*node)->left));

    if (height((*node)->right) - height((*node)->left) >= 2)

    {

      if ((*node)->left && (value < (*node)->left->element))

      {

        (*node) = double_rotation_with_right((*node));

      }

      else

      {

        (*node) = single_rotation_with_right((*node));

      }

    }

  }

  else if (value > (*node)->element)

  {

    (*node)->right = del(value, &((*node)->right));

    if (height((*node)->left) - height((*node)->right) >= 2)

    {

      if ((*node)->right && (value > (*node)->right->element))

      {

        (*node) = double_rotation_with_left((*node));

      }

      else

      {

        (*node) = single_rotation_with_left((*node));

      }

    }

  }

  else if ((*node)->left && (*node)->right)

  {

    tmp_cell = searchmin((*node)->right);

    (*node)->element = tmp_cell->element;

    (*node)->right = del((*node)->element, &((*node)->right));

  }

  else

  {

    tmp_cell = (*node);

    if ((*node)->left == NULL)

      (*node) = (*node)->right;

    else if ((*node)->right == NULL)

      (*node) = (*node)->left;

    free(tmp_cell);

    tmp_cell = NULL;

  }

  return (*node);

}

int numofnode(AVLTree **p)

{

    if ((*p!=0)&&((*p)->element != 13))

        return numofnode (&(*p)->right) + numofnode (&(*p)->left) + 1;

    else

        return 0;

}

Consider an input sequence that is provided as an input to the insert method

20,50,45,30,35,55,10,100,90,70,5,99,8,96

What would be the height of the node 55 in the resulting tree?

           

(a) 4

(b) 3

(c) 0

(d) None of these

Question Number 8

The subject of these questions is an unusually simple kind of binary tree, defined by these properties:

Terminal nodes contain a string.

Internal nodes have one or two children, called "left" and "right".

Either child of an internal node may be null, but not both.

Internal nodes contain no other information.

By "tree" we simply mean a node and all of its descendants.

A tree rooted at a node having left child A and right child B is a different tree than one rooted at a node having left child B and right child A.

Here's an example, with plus signs (+) used to indicate internal nodes:

                                +

                               / \

                              /   \

                             /     \

                            +       +

                           /       / \

                          /       /   \

                         /       /     \

                       "A"      +      "D"

                               / \

                              /   \

                             /     \

                           "B"     "C"

The height of a tree is defined as follows:

The height of a terminal node is 0.

The height of an internal node is 1 + the maximum of the heights of its children.

Suppose it is specified that height() will only be called on InternalNodes.

Consider the following a implementation of InternalNode.height(), with no implementation in either Node or TerminalNode?

    int height() {

        int lheight = (left == null) ? 0 : left.height();

        int rheight = (right == null) ? 0 : right.height();

        return (lheight > rheight ? lheight : rheight);

    }

Which, if any, of the following are problems that will cause the above code to fail:

It won’t compile because there is no definition (concrete or abstract) in Node.

1 should be added to the value of the return

           

(a) The code is correct as is.

(b) A: it won’t compile, but if that were fixed it would work and produce the correct result.

(c) B: it will compile but produce the wrong result.

(d) Both: it won’t compile, and even if that were fixed, it would produce the wrong result.

Question Number 9

The subject of these questions is an unusually simple kind of binary tree, defined by these properties:

Terminal nodes contain a string.

Internal nodes have one or two children, called "left" and "right".

Either child of an internal node may be null, but not both.

Internal nodes contain no other information.

By "tree" we simply mean a node and all of its descendants.

A tree rooted at a node having left child A and right child B is a different tree than one rooted at a node having left child B and right child A.

Here's an example, with plus signs (+) used to indicate internal nodes:

                                +

                               / \

                              /   \

                             /     \

                            +       +

                           /       / \

                          /       /   \

                         /       /     \

                       "A"      +      "D"

                               / \

                              /   \

                             /     \

                           "B"     "C"

Which of the following is the first to correctly define methods for counting the empty subtrees of a tree? (Only the relevant methods are shown for each class, and if the class isn’t shown in the answer it doesn’t contain a countEmptySubtrees member.)

class InternalNode extends Node {

    int countEmptySubtrees() {

        return left.countEmptySubtrees()) + right.countEmptySubtrees());

    }

}

class InternalNode extends Node {

    int countEmptySubtrees() {

        return

            ((left == null) ? 1 : left. countEmptySubtrees()) +

            ((right == null) ? 1 : right. countEmptySubtrees());

    }

}

abstract class Node {

    abstract int countEmptySubtrees();

}

class TerminalNode extends Node {

    int countEmptySubtrees() {

        return 0;

    }

}

class InternalNode extends Node {

    int countEmptySubtrees() {

        return

            ((left == null) ? 1 : left. countEmptySubtrees()) +

            ((right == null) ? 1 : right. countEmptySubtrees());

    }

}

           

(a) A

(b) B

(c) C

(d) None of them provide a correct implementation.

Question Number 10

The subject of these questions is an unusually simple kind of binary tree, defined by these properties:

Terminal nodes contain a string.

Internal nodes have one or two children, called "left" and "right".

Either child of an internal node may be null, but not both.

Internal nodes contain no other information.

By "tree" we simply mean a node and all of its descendants.

A tree rooted at a node having left child A and right child B is a different tree than one rooted at a node having left child B and right child A.

Here's an example, with plus signs (+) used to indicate internal nodes:

                                +

                               / \

                              /   \

                             /     \

                            +       +

                           /       / \

                          /       /   \

                         /       /     \

                       "A"      +      "D"

                               / \

                              /   \

                             /     \

                           "B"     "C"

We want to define Boolean contains(String str) to return True if the tree contains a node with str as its value and False otherwise. Here are definitions for two of the three classes:

abstract class Node {

    abstract boolean contains(String str);

}

class TerminalNode extends Node {

    boolean contains(String str) {

        return value.equals(str);

    }

}

Which of the following methods is the first to correctly implement contains for InternalNode?

class InternalNode extends Node {

    boolean contains(String str) {

        if (left.contains(str))

            return true;

        if (right.contains(str))

            return true;

    }

}

class InternalNode extends Node {

    boolean contains(String str) {

        if (left != null)

            return left.contains(str);

        if (right != null)

            return right.contains(str);

    }

}

class InternalNode extends Node {

    boolean contains(String str) {

        return

            ((left != null) && left.contains(str)) ||

            ((right != null) && right.contains(str));

    }

}

           

(a) A

(b) B

(c) C

(d) None of them is a correct implementation.

Read More..