Optimus Information ( call based 2016 , 2017 batch though amcat )

**********************************
Optimus Information ( call based 2016 , 2017 batch though amcat )

drive date 21 april

Address: 7th Floor, Pinnacle Tower, A-42/6, Block A, Sector 62, Noida, Uttar Pradesh 201301

******************************************************************
READ THESE QUESTION FOR INTERVIEW
*******************************************************************

Commonly Asked Data Structure Interview Questions | Set 1
What is a Data Structure?
A data structure is a way of organizing the data so that the data can be used efficiently. Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks. For example, B-trees are particularly well-suited for implementation of databases, while compiler implementations usually use hash tables to look up identifiers. (Source: Wiki Page)

What are linear and non linear data Structures?

Linear: A data structure is said to be linear if its elements form a sequence or a linear list. Examples: Array. Linked List, Stacks and Queues
Non-Linear: A data structure is said to be non-linear if traversal of nodes is nonlinear in nature. Example: Graph and Trees.

What are the various operations that can be performed on different Data Structures?

Insertion − Add a new data item in the given collection of data items.
Deletion − Delete an existing data item from the given collection of data items.
Traversal − Access each data item exactly once so that it can be processed.
Searching − Find out the location of the data item if it exists in the given collection of data items.
Sorting − Arranging the data items in some order i.e. in ascending or descending order in case of numerical data and in dictionary order in case of alphanumeric data.

How is an Array different from Linked List?

The size of the arrays is fixed, Linked Lists are Dynamic in size.
Inserting and deleting a new element in an array of elements is expensive, Whereas both insertion and deletion can easily be done in Linked Lists.
Random access is not allowed in Linked Listed.
Extra memory space for a pointer is required with each element of the Linked list.
Arrays have better cache locality that can make a pretty big difference in performance.

What is Stack and where it can be used?

Stack is a linear data structure which the order LIFO(Last In First Out) or FILO(First In Last Out) for accessing elements. Basic operations of stack are : Push, Pop , Peek

Applications of Stack:

Infix to Postfix Conversion using Stack
Evaluation of Postfix Expression
Reverse a String using Stack
Implement two stacks in an array
Check for balanced parentheses in an expression

What is a Queue, how it is different from stack and how is it implemented?

Queue is a linear structure which follows the order is First In First Out (FIFO) to access elements. Mainly the following are basic operations on queue: Enqueue, Dequeue, Front, Rear
The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added. Both Queues and Stacks can be implemented using Arrays and Linked Lists.

What are Infix, prefix, Postfix notations?

Infix notation: X + Y – Operators are written in-between their operands. This is the usual way we write expressions. An expression such as
A * ( B + C ) / D
Postfix notation (also known as “Reverse Polish notation”): X Y + Operators are written after their operands. The infix expression given above is equivalent to
A B C + * D/
Prefix notation (also known as “Polish notation”): + X Y Operators are written before their operands. The expressions given above are equivalent to
/ * A + B C D
Converting between these notations: Click here

What is a Linked List and What are its types?

A linked list is a linear data structure (like arrays) where each element is a separate object. Each element (that is node) of a list is comprising of two items – the data and a reference to the next node.Types of Linked List :

Singly Linked List : In this type of linked list, every node stores address or reference of next node in list and the last node has next address or reference as NULL. For example 1->2->3->4->NULL
Doubly Linked List : Here, here are two references associated with each node, One of the reference points to the next node and one to the previous node. Eg. NULL<-1<->2<->3->NULL
Circular Linked List : Circular linked list is a linked list where all nodes are connected to form a circle. There is no NULL at the end. A circular linked list can be a singly circular linked list or doubly circular linked list. Eg. 1->2->3->1 [The next pointer of last node is pointing to the first]

Which data structures are used for BFS and DFS of a graph?

Queue is used for BFS
Stack is used for DFS. DFS can also be implemented using recursion (Note that recursion also uses function call stack).

Can doubly linked be implemented using a single pointer variable in every node?
Doubly linked list can be implemented using a single pointer. See XOR Linked List – A Memory Efficient Doubly Linked List

How to implement a stack using queue?

A stack can be implemented using two queues. Let stack to be implemented be ‘s’ and queues used to implement be ‘q1’ and ‘q2’. Stack ‘s’ can be implemented in two ways:

Method 1 (By making push operation costly)
Method 2 (By making pop operation costly) See Implement Stack using Queues

How to implement a queue using stack?

A queue can be implemented using two stacks. Let queue to be implemented be q and stacks used to implement q be stack1 and stack2. q can be implemented in two ways:

Method 1 (By making enQueue operation costly)
Method 2 (By making deQueue operation costly) See Implement Queue using Stacks

Which Data Structure Should be used for implementiong LRU cache?

We use two data structures to implement an LRU Cache.

Queue which is implemented using a doubly linked list. The maximum size of the queue will be equal to the total number of frames available (cache size).The most recently used pages will be near front end and least recently pages will be near rear end.
A Hash with page number as key and address of the corresponding queue node as value. See How to implement LRU caching scheme? What data structures should be used?

How to check if a given Binary Tree is BST or not?
If inorder traversal of a binary tree is sorted, then the binary tree is BST. The idea is to simply do inorder traversal and while traversing keep track of previous key value. If current key value is greater, then continue, else return false. See A program to check if a binary tree is BST or not for more details.

Linked List Questions

Linked List Insertion
Linked List Deletion
middle of a given linked list
Nth node from the end of a Linked List

Tree Traversal Questions

Inorder
Preorder and Postoder Traversals
Level order traversal
Height of Binary Tree

Convert a DLL to Binary Tree in-place
See In-place conversion of Sorted DLL to Balanced BST

Convert Binary Tree to DLL in-place
See Convert a given Binary Tree to Doubly Linked List | Set 1, Convert a given Binary Tree to Doubly Linked List | Set 2

Delete a given node in a singly linked list
Given only a pointer to a node to be deleted in a singly linked list, how do you delete it?

Reverse a Linked List
Write a function to reverse a linked list

Detect Loop in a Linked List
Write a C function to detect loop in a linked list.

************************************************************************************************************************************
1. What is database?

A database is a collection of information that is organized. So that it can easily be accessed, managed, and updated.

2. What is DBMS?

DBMS stands for Database Management System. It is a collection of programs that enables user to create and maintain a database.

3. What is a Database system?

The database and DBMS software together is called as Database system.

4. What are the advantages of DBMS?

I. Redundancy is controlled.

II. Providing multiple user interfaces.

III. Providing backup and recovery

IV. Unauthorized access is restricted.

V. Enforcing integrity constraints.

5. What is normalization?

It is a process of analysing the given relation schemas based on their Functional Dependencies (FDs) and primary key to achieve the properties
(1).Minimizing redundancy, (2). Minimizing insertion, deletion and update anomalies.

6. What is Data Model?
A collection of conceptual tools for describing data, data relationships data semantics and constraints.

7. What is E-R model?

This data model is based on real world that consists of basic objects called entities and of relationship among these objects. Entities are described in a database by a set of attributes.

8. What is Object Oriented model?

This model is based on collection of objects. An object contains values stored in instance variables with in the object. An object also contains bodies of code that operate on the object. These bodies of code are called methods. Objects that contain same types of values and the same methods are grouped together into classes.

9. What is an Entity?
An entity is a thing or object of importance about which data must be captured.

10. What is DDL (Data Definition Language)?

A data base schema is specifies by a set of definitions expressed by a special language called DDL.

11. What is DML (Data Manipulation Language)?

This language that enable user to access or manipulate data as organised by appropriate data model. Procedural DML or Low level: DML requires a user to specify what data are needed and how to get those data. Non-Procedural DML or High level: DML requires a user to specify what data are needed without specifying how to get those data

12. What is DML Compiler?

It translates DML statements in a query language into low-level instruction that the query evaluation engine can understand.

13. What is Query evaluation engine?

It executes low-level instruction generated by compiler.

14. What is Functional Dependency?

Functional Dependency is the starting point of normalization. Functional Dependency exists when a relation between two attributes allows you to uniquely determine the corresponding attribute’s value.

15. What is 1 NF (Normal Form)?

The first normal form or 1NF is the first and the simplest type of normalization that can be implemented in a database. The main aims of 1NF are to:

1. Eliminate duplicative columns from the same table.

2. Create separate tables for each group of related data and identify each row with a unique column (the primary key).

16. What is Fully Functional dependency?

A functional dependency X Y is full functional dependency if removal of any attribute A from X means that the dependency does not hold any more.

17. What is 2NF?

A relation schema R is in 2NF if it is in 1NF and every non-prime attribute A in R is fully functionally dependent on primary key.

18. What is 3NF?

A relation is in third normal form if it is in Second Normal Form and there are no functional (transitive) dependencies between two (or more) non-primary key attributes.

19. What is BCNF (Boyce-Codd Normal Form)?

A table is in Boyce-Codd normal form (BCNF) if and only if it is in 3NF and every determinant is a candidate key.

20. What is 4NF?

Fourth normal form requires that a table be BCNF and contain no multi-valued dependencies.

21. What is 5NF?

A table is in fifth normal form (5NF) or Project-Join Normal Form (PJNF) if it is in 4NF and it cannot have a lossless decomposition into any number of smaller tables.

22. What is a query?

A query with respect to DBMS relates to user commands that are used to interact with a data base.

23. What is meant by query optimization?

The phase that identifies an efficient execution plan for evaluating a query that has the least estimated cost is referred to as query optimization.

24. What is an attribute?
It is a particular property, which describes the entity.

25. What is RDBMS?

Relational Data Base Management Systems (RDBMS) are database management systems that maintain data records and indices in tables.

26. What’s difference between DBMS and RDBMS?

DBMS provides a systematic and organized way of storing, managing and retrieving from collection of logically related information. RDBMS also provides what DBMS provides but above that it provides relationship integrity.

27. What is SQL?

SQL stands for Structured Query Language. SQL is an ANSI (American National Standards Institute) standard computer language for accessing and manipulating database systems. SQL statements are used to retrieve and update data in a database.

28. What is Stored Procedure?

A stored procedure is a named group of SQL statements that have been previously created and stored in the server database.

29. What is a view?

A view may be a subset of the database or it may contain virtual data that is derived from the database files but is not explicitly stored.

30. What is Trigger?

A trigger is a SQL procedure that initiates an action when an event (INSERT, DELETE or UPDATE) occurs.

31. What is Index?

An index is a physical structure containing pointers to the data.

32. What is extension and intension?

Extension -It is the number of tuples present in a table at any instance. This is time dependent.

Intension -It is a constant value that gives the name, structure of table and the constraints laid on it.

33. What do you mean by atomicity and aggregation?

Atomicity-Atomicity states that database modifications must follow an “all or nothing” rule. Each transaction is said to be “atomic.” If one part of the transaction fails, the entire transaction fails.

Aggregation – A feature of the entity relationship model that allows a relationship set to participate in another relationship set. This is indicated on an ER diagram by drawing a dashed box around the aggregation.

34. What is RDBMS KERNEL?

Two important pieces of RDBMS architecture are the kernel, which is the software, and the data dictionary, which consists of the system- level data structures used by the kernel to manage the database.

35. Name the sub-systems of a RDBMS?

I/O, Security, Language Processing, Process Control, Storage Management, Logging and Recovery, Distribution Control, Transaction Control, Memory Management, Lock Management.

36. How do you communicate with an RDBMS?

You communicate with an RDBMS using Structured Query Language (SQL)

37. Disadvantage in File Processing System?

· Data redundancy & inconsistency.

· Difficult in accessing data.

· Data isolation.

· Data integrity.

· Concurrent access is not possible.

· Security Problems.

38. What is VDL (View Definition Language)?

It specifies user views and their mappings to the conceptual schema.

39. What is SDL (Storage Definition Language)?

This language is to specify the internal schema. This language may Specify the mapping between two schemas.

40. Describe concurrency control?

Concurrency control is the process managing simultaneous operations against a database so that database integrity is no compromised. There are two approaches to concurrency control.

The pessimistic approach involves locking and the optimistic approach involves versioning.

41. Describe the difference between homogeneous and heterogeneous distributed database?

A homogenous database is one that uses the same DBMS at each node. A heterogeneous database is one that may have a different DBMS at each node.

42. What is a distributed database?

A distributed database is a single logical database that is spread across more than one node or locations that are all connected via some communication link.

43. Explain the difference between two and three-tier architectures?

Three-tier architecture includes a client and two server layers.

The application code is stored on the application server and the database is stored on the database server. A two-tier architecture includes a client and one server layer. The database is stored on the database server.

44. Briefly describe the three types of SQL commands?

Data definition language commands are used to create, alter, and drop tables. Data manipulation commands are used to insert, modify, update, and query data in the database. Data control language commands help the DBA to control the database.

45. List some of the properties of a relation?

Relations in a database have a unique name and no multivalued attributes exist. Each row is unique and each attribute within a relation has a unique name. The sequence of both columns and rows is irrelevant.

46. Explain the differences between an intranet and an extranet?

An Internet database is accessible by everyone who has access to a Web site. An intranet database limits access to only people within a given organization.

47. What is SQL Deadlock?

Deadlock is a unique situation in a multi user system that causes two or more users to wait indefinitely for a locked resource.

48. What is a Catalog?

A catalog is a table that contains the information such as structure of each file, the type and storage format of each data item and various constraints on the data .The information stored in the catalog is called Metadata.

49. What is data ware housing & OLAP?

Data warehousing and OLAP (online analytical processing) systems are the techniques used in many companies to extract and analyze useful information from very large databases for decision making .

50. Describe the three levels of data abstraction?

Physical level: The lowest level of abstraction describes how data are stored.

Logical level: The next higher level of abstraction, describes what data are stored in database and what relationship among those data.

View level: The highest level of abstraction describes only part of entire database.

51. What is Data Independence?

Data independence means that the application is independent of the storage structure and access strategy of data.

52. How many types of relationship exist in database designing?

There are three major relationship models:-

One-to-one

One-to-many

Many-to-many

53. What is order by clause?

ORDER BY clause helps to sort the data in either ascending order to descending

54. What is the use of DBCC commands?

DBCC stands for database consistency checker. We use these commands to check the consistency of the databases, i.e., maintenance, validation task and status checks.

55. What is Collation?

Collation refers to a set of rules that determine how data is sorted and compared.

56. What is difference between DELETE & TRUNCATE commands?

Delete command removes the rows from a table based on the condition that we provide with a WHERE clause. Truncate will actually remove all the rows from a table and there will be no data in the table after we run the truncate command.

57. What is Hashing technique?

This is a primary file organization technique that provides very fast access to records on certain search conditions.

58. What is a transaction?

A transaction is a logical unit of database processing that includes one or more database access operations.

59. What are the different phases of Transaction?

Analysis phase

Redo phase

Undo phase

60. What is “transparent dbms”?

It is one, which keeps its physical structure hidden from user.

61. What are the primitive operations common to all record management System?

Addition, deletion and modification.

62. Explain the differences between structured data and unstructured data.

Structured data are facts concerning objects and events. The most important structured data are numeric, character, and dates.

Structured data are stored in tabular form. Unstructured data are multimedia data such as documents, photographs, maps, images, sound, and video clips. Unstructured data are most commonly found on Web servers and Web-enabled databases.

63. What are the major functions of the database administrator?

Managing database structure, controlling concurrent processing, managing processing rights and responsibilities, developing database security, providing for database recovery, managing the DBMS and maintaining the data repository.

64. What is a dependency graph?

A dependency graph is a diagram that is used to portray the connections between database elements.

65. Explain the difference between an exclusive lock and a shared lock?

An exclusive lock prohibits other users from reading the locked resource; a shared lock allows other users to read the locked resource, but they cannot update it.

66. Explain the “paradigm mismatch” between SQL and application programming languages.

SQL statements return a set of rows, while an application program works on one row at a time. To resolve this mismatch the results of SQL statements are processed as pseudofiles, using a cursor or pointer to specify which row is being processed.

67. Name four applications for triggers.

(1)Providing default values, (2) enforcing data constraints,

(3) Updating views and (4) enforcing referential integrity

68. What are the advantages of using stored procedures?

The advantages of stored procedures are (1) greater security, (2) decreased network traffic, (3) the fact that SQL can be optimized and (4) code sharing which leads to less work, standardized processing, and specialization among developers.

69. Explain the difference between attributes and identifiers.

Entities have attributes. Attributes are properties that describe the entity’s characteristics. Entity instances have identifiers. Identifiers are attributes that name, or identify, entity instances.

70. What is Enterprise Resource Planning (ERP), and what kind of a database is used in an ERP application?

Enterprise Resource Planning (ERP) is an information system used in manufacturing companies and includes sales, inventory, production planning, purchasing and other business functions. An ERP system typically uses a multiuser database.

71. Describe the difference between embedded and dynamic SQL?

Embedded SQL is the process of including hard coded SQL statements. These statements do not change unless the source code is modified. Dynamic SQL is the process of generating SQL on the fly.The statements generated do not have to be the same each time.

72. Explain a join between tables

A join allows tables to be linked to other tables when a relationship between the tables exists. The relationships are established by using a common column in the tables and often uses the primary/foreign key relationship.

73. Describe a subquery.

A subquery is a query that is composed of two queries. The first query (inner query) is within the WHERE clause of the other query (outer query).

74. Compare a hierarchical and network database model?

The hierarchical model is a top-down structure where each parent may have many children but each child can have only one parent. This model supports one-to-one and one-to-many relationships.

The network model can be much more flexible than the hierarchical model since each parent can have multiple children but each child can also have multiple parents. This model supports one-to-one, one-to-many, and many-to-many relationships.

75. Explain the difference between a dynamic and materialized view.

A dynamic view may be created every time that a specific view is requested by a user. A materialized view is created and or updated infrequently and it must be synchronized with its associated base table(s).

76. Explain what needs to happen to convert a relation to third normal form.

First you must verify that a relation is in both first normal form and second normal form. If the relation is not, you must convert into second normal form. After a relation is in second normal form, you must remove all transitive dependencies.

77. Describe the four types of indexes?

A unique primary index is unique and is used to find and store a row. A nonunique primary index is not unique and is used to find a row but also where to store a row (based on its unique primary index). A unique secondary index is unique for each row and used to find table rows. A nonunique secondary index is not unique and used to find table rows.

78. Explain minimum and maximum cardinality?

Minimum cardinality is the minimum number of instances of an entity that can be associated with each instance of another entity. Maximum cardinality is the maximum number of instances of an entity that can be associated with each instance of another entity.

79. What is deadlock? How can it be avoided? How can it be resolved once it occurs?

Deadlock occurs when two transactions are each waiting on a resource that the other transaction holds. Deadlock can be prevented by requiring transactions to acquire all locks at the same time; once it occurs, the only way to cure it is to abort one of the transactions and back out of partially completed work.

80. Explain what we mean by an ACID transaction.

An ACID transaction is one that is atomic, consistent, isolated, and durable. Durable means that database changes are permanent. Consistency can mean either statement level or transaction level consistency. With transaction level consistency, a transaction may not see its own changes.Atomic means it is performed as a unit.

81. Under what conditions should indexes be used?

Indexes can be created to enforce uniqueness, to facilitate sorting, and to enable fast retrieval by column values. A good candidate for an index is a column that is frequently used with equal conditions in WHERE clauses.

82. What is difference between SQL and SQL SERVER?

SQL is a language that provides an interface to RDBMS, developed by IBM. SQL SERVER is a RDBMS just like Oracle, DB2.

83. What is Specialization?

It is the process of defining a set of subclasses of an entity type where each subclass contain all the attributes and relationships of the parent entity and may have additional attributes and relationships which are specific to itself.

******************************************************************************************************************************************
data structure
*************************************************************************************

Linked List | Set 2 (Inserting a node)
We have introduced Linked Lists in the previous post. We also created a simple linked list with 3 nodes and discussed linked list traversal.

All programs discussed in this post consider following representations of linked list .
// Linked List Class
class LinkedList
{
Node head; // head of list

/* Node Class */
class Node
{
int data;
Node next;

// Constructor to create a new node
Node(int d) {data = d; next = null; }
}
}
Run on IDE
In this post, methods to insert a new node in linked list are discussed. A node can be added in three ways
1) At the front of the linked list
2) After a given node.
3) At the end of the linked list

/* This function is in LinkedList class.
Inserts a new node after the given prev_node. This method is
defined inside LinkedList class shown above */
public void insertAfter(Node prev_node, int new_data)
{
/* 1. Check if the given Node is null */
if (prev_node == null)
{
System.out.println(“The given previous node cannot be null”);
return;
}

/* 2. Allocate the Node &
3. Put in the data*/
Node new_node = new Node(new_data);

/* 4. Make next of new Node as next of prev_node */
new_node.next = prev_node.next;

/* 5. make next of prev_node as new_node */
prev_node.next = new_node;
}
Run on IDE

Time complexity of insertAfter() is O(1) as it does constant amount of work.
Add a node at the end: (6 steps process)
The new node is always added after the last node of the given Linked List. For example if the given Linked List is 5->10->15->20->25 and we add an item 30 at the end, then the Linked List becomes 5->10->15->20->25->30.
Since a Linked List is typically represented by the head of it, we have to traverse the list till end and then change the next of last node to new node.

linkedlist_insert_last

Following are the 6 steps to add node at the end.

/* Appends a new node at the end. This method is
defined inside LinkedList class shown above */
public void append(int new_data)
{
/* 1. Allocate the Node &
2. Put in the data
3. Set next as null */
Node new_node = new Node(new_data);

/* 4. If the Linked List is empty, then make the
new node as head */
if (head == null)
{
head = new Node(new_data);
return;
}

/* 4. This new node is going to be the last node, so
make next of it as null */
new_node.next = null;

/* 5. Else traverse till the last node */
Node last = head;
while (last.next != null)
last = last.next;

/* 6. Change the next of last node */
last.next = new_node;
return;
}
Run on IDE

Time complexity of append is O(n) where n is the number of nodes in linked list. Since there is a loop from head to end, the function does O(n) work.
This method can also be optimized to work in O(1) by keeping an extra pointer to tail of linked list/
Following is a complete program that uses all of the above methods to create a linked list.

/* Appends a new node at the end. This method is
defined inside LinkedList class shown above */
public void append(int new_data)
{
/* 1. Allocate the Node &
2. Put in the data
3. Set next as null */
Node new_node = new Node(new_data);

/* 4. If the Linked List is empty, then make the
new node as head */
if (head == null)
{
head = new Node(new_data);
return;
}

/* 4. This new node is going to be the last node, so
make next of it as null */
new_node.next = null;

/* 5. Else traverse till the last node */
Node last = head;
while (last.next != null)
last = last.next;

/* 6. Change the next of last node */
last.next = new_node;
return;
}
Run on IDE

Time complexity of append is O(n) where n is the number of nodes in linked list. Since there is a loop from head to end, the function does O(n) work.
This method can also be optimized to work in O(1) by keeping an extra pointer to tail of linked list/
Following is a complete program that uses all of the above methods to create a linked list.