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..

Cisco Campus Selection

WRITTEN TEST

No. of Questions : 50
Time Limit           : 60 mins
Question type      : MCQ

-No negative marking


The aptitude was 20 questions Qunt an reasoning and 30 questions technical.

Subject Covered in Aptitude Test:

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

Sample Questions :

-nyquest rate
-reset lower bit instruction Ans - ANI 0F;
-8085 instruction
-time division multiplexing
-simple digital questions (refer K maps)
-prefix/postfix
-in 8085 ALE signal is to the demultiplexe address and data.
-1 simple dbms query
-time division multiplexing/career signal

Personal Interviews:

Total 3 rounds.

Questions on :

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

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..