Data structure and algorithm with JAVA

• What is data structure?

→ A data structure is a specialized format for organizing and storing data. General data structure types include the array, the file, the record, the table, the tree, and so on. Any data structure is designed to organize data to suit a specific purpose so that it can be accessed and worked with in appropriate ways.

• Why is Big Oh notation used?

→ Big Oh notation is used to find the best case

• Why are link list preferred over arrays?

→ Link list are preferred over arrays because we can store in any memory location

• What is linear queue?

→ Linear queue is a queue in which we should put data on front and the data which we put first extract at first. I.e. first in first out

• Define activation record.

→ An activation record is another name for Stack Frame. It’s the data structure that composes a call stack. It is generally composed of: Locals to the called. Return address to the caller.

• What is binary tree?

→ A data structure in which a record is linked to two successor records, usually referred to as the left branch when greater and the right when less than the previous record.

• What is B tree?

→ An organizational structure for information storage and retrieval in the form of a tree in which all terminal nodes are the same distance from the base, and all non-terminal nodes have between n and 2 n sub trees or pointers (where n is an integer).

• List out the method that can be used to represent graph in memory.

→ The method that can be used to represent graph in memory

• What is sorting?

→ The process of arranging data from ascending to descending or vice-versa is known as sorting

• For which purpose Kruskal’s algorithm is used?

→ For finding minimal spinning tree we use Kruskal’s algorithm

→ An abstract data type (ADT) is a mathematical model for data types, where a data type is defined by its behavior (semantics) from the point of view of a user of the data, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations.

• How can you measure time complexity of an algorithm? Explain.

→ We can time complexity of an algorithm by using Big Oh notation

• Differentiate between recursive and non-recursive function.

→ The function which call it’s self is recursive function where as other iteration are non-recursive function

• What is heap? Explain the types of heap in DSA.

→ A heap is a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of node P is greater than the key of node C. A heap can be classified further as either a “max heap” or a “min heap”.

• Define expression tree with example.

→ A binary expression tree is a specific kind of a binary tree used to represent expressions. Two common types of expressions that a binary expression tree can represent are algebraic and boolean. These trees can represent expressions that contain both unary and binary operators.

• What is AVL tree?

→ AVL tree is a self-balancing binary search tree. It was the first such data structure to be invented. In an AVL tree, the heights of the two child sub trees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property.

• Give the working principles of binary search algorithm.

→ A BST is a binary tree of nodes ordered in the following way:

1. Each node contains one key (also unique)
2. The keys in the left sub tree are < (less) than the key in its parent node
3. The keys in the right sub tree > (greater) than the key in its parent node
4. Duplicate node keys are not allowed.

• Define traversal in graph and tree.

• What is minimum spanning tree?

→ A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight

• What is divided and conquer paradigm? Give the name of algorithm that follows this paradigm.

→ Divide and conquer (D&C) is an algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly.

• List the various types of binary trees.

→ The various types of binary trees are

• Strictly binary tree
• Complete binary tree
• Almost complete binary tree
• Define tail and non-tail with example

• List out the different types of hash function.

1. Division
2. Folding
3. Mid-square
4. Extraction
6. Universal

• Define coalesced chaining.

→ Coalesced hashing, also called coalesced chaining, is a strategy of collision resolution in a hash table that forms a hybrid of separate chaining and open addressing.

• What difference do you find between directed graph and undirected graph?

→ Directed graph has source vertex and sink vertex whereas undirected graph do not have. Directed graph has direction to specific path whereas undirected graph do not have

• What is cut vertex?

→ A cut vertex is a vertex that when removed (with its boundary edges) from a graph creates more components than previously in the graph. A cut edge is an edge that when removed (the vertices stay in place) from a graph creates more components than previously in the graph.

• What do you understand by topological sort?

→ A topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.

• How would you differentiate between deletion by merging and deletion by copying?

• What is searching difficult in a heap compared to binary search tree?

→ Min-heap is searching difficult in a heap compared to binary search tree

• Why does external sorting requires more time than internal sorting?

• Define expression tree.

→ A binary expression tree is a specific kind of a binary tree used to represent expressions. Two common types of expressions that a binary expression tree can represent are algebraic and boolean. These trees can represent expressions that contain both unary and binary operators.

• Why are linked lists preferred over arrays?

→ Link list are preferred over arrays because we can store in any memory location

• Differentiate between linear search and binary search.

→ Linear search or sequential search is a method for finding a target value within a list. It sequentially checks each element of the list for the target value until a match is found or until all the elements have been searched.

A binary search, also called a dichotomizing search, is a digital scheme for locating a specific object in a large set. Each object in the set is given a key. The number of keys is always a power of 2. If there are 32 items in a list, for example, they might be numbered 0 through 31 (binary 00000 through 11111).

• What is coalesced chaining?

→ Coalesced hashing, also called coalesced chaining, is a strategy of collision resolution in a hash table that forms a hybrid of separate chaining and open addressing.

• How does graph differ from a tree?

→ Graph has cycle but tree do not have it

• Define articulation point.

→ For a disconnected undirected graph, an articulation point is a vertex removing which increases number of connected components.

• What is a minimum spanning tree?

→A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight

• Why searching is the key process in a binary search tree?

→ Searching is the key process in a binary search tree because data are in hybrid structure

• Why is balancing done in a tree?

→ Balancing done in a tree because in order to make data structure in system

• Differentiate between internal sorting and external sorting.

1. What are elementary searching algorithm?

• What do you understand by time and space complexity?

→ We can time complexity of an algorithm by using Big Oh notation

• What do you mean by computational complexities

→ Computational complexity theory is a branch of the theory of computation in theoretical computer science that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other.

→ a doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes

Singly Linked Lists are a type of data structure. It is a type of list. In a singly linked list each node in the list stores the contents of the node and a pointer or reference to the next node in the list. It does not store any pointer or reference to the previous node.

Singly Linked Lists are a type of data structure. It is a type of list. In a singly linked list each node in thelist stores the contents of the node and a pointer or reference to the next node in the list. It does not store any pointer or reference to the previous node.

• What is indirect recursion?

→ Indirect recursion occurs when a method invokes another method, eventually resulting in the original method being invoked again.

• Define a binary search tree.

→ A binary search tree (BST), also known as an ordered binary tree, is a node-based data structure in which each node has no more than two child nodes. Each child must either be a leaf node or the root of another binary search tree.

• How B+-tree differ from B-tree?

• What is a minimum spanning tree?

→A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight

• What do you mean by  tree traversal?

→  tree traversal (also known as tree search) is a form of graph traversal and refers to the process of visiting (checking and/or updating) each node in a tree data structure, exactly once. Such traversals are classified by the order in which the nodes are visited

• Define Splay tree.

→ A splay tree is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal in O(log n) amortized time.

• What is topological sort?

→ A topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.

• What is a priority queue?

• What is theta notation?

→ First let’s understand what big O, big Theta and big Omega are. They are all sets of functions. Big O is giving upper asymptotic bound, while big Omega is giving a lower bound. Big Theta gives both.

• How does linear queue differs from priority queue?

→ Linear queue is based on FIFO but priority queue is based on priority

• What is nontail recursion?

→ A tail call [tail recursion] is a kind of goto dressed as a call. A tail call happens when a function calls another as its last action, so it has nothing else to do. For instance, in the following code, the call to g is a tail call: function f (x) return g(x) end.

• Define an AVL tree.

→ AVL tree is a self-balancing binary search tree. It was the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property.

• How B*-tree differ from B+-tree?

• Define hashing.

→ a hash table (hash map) is a data structure which implements an associative array abstract data type, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

• What is pre-order tree traversal?

• Define DSW algorithm.

→ The Day–Stout–Warren (DSW) algorithm is a method for efficiently balancing binary search trees — that is, decreasing their height to O(log n) nodes, where n is the total number of nodes. … First, the tree is turned into a linked list by means of an in-order traversal, reusing the pointers in the (threaded) tree’s nodes.

• What is a decision tree?

→ A decision tree is a decision support tool that uses atree-like graph or model of decisions and their possible consequences, including chance event outcomes, resource costs, and utility. It is one way to display an algorithm.

• What is a network in graph?

→ A graph in this context is made up of vertices, nodes, or points which are connected by edges, arcs, or lines. …Graphs are one of the prime objects of study in discrete mathematics. Refer to the glossary of graph theory for basic definitions in graph theory.

• What is BST?

→ A binary search tree (BST), also known as an ordered binary tree, is a node-based data structure in which each node has no more than two child nodes. Each child must either be a leaf node or the root of another binary search tree.

→ A splay tree is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal in O(log n) amortized time.

• What are the characteristics of an algorithm?

• What is the underflow condition of stack?

→ When this happens it often causes the program to crash. … If the stack is empty and yet a POP operation is attempted, this is called an ‘stack underflow’ and can cause a program to crash.

→ a doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes

Singly Linked Lists are a type of data structure. It is a type of list. In a singly linked list each node in the list stores the contents of the node and a pointer or reference to the next node in the list. It does not store any pointer or reference to the previous node.

• What is the degree of a node?

→ The number of children is the degree of a node

• What is splaying?

→ A splay tree is a self-adjusting binary search treewith the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal in O(log n) amortized time.

• What is excessive recursion?

• What is strictly binary tree?

→ If every non-leaf node in a binary tree has nonempty left and right sub trees, the tree is termed a strictly binary tree. Or, to put it another way, all of the nodes in a strictly binary tree are of degree zero or two, never degree one. A strictly binary tree with N leaves always contains 2N – 1 nodes.

• Arrange the following complexity function from slower to faster: n2.5, n , n , nn.

→ nn, n2.5, n, n

→ An abstract data type (ADT) is a mathematical model for data types, where a data type is defined by its behavior (semantics) from the point of view of a user of the data, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations.

• What is Big-O notation?

→ Big O notation is used in Computer Science to describe the performance or complexity of an algorithm. Big O specifically describes the worst-case scenario, and can be used to describe the execution time required or the space used (e.g. in memory or on disk) by an algorithm

• Differentiate between direct recursion and indirect recursion.

• Differentiate between linear queue and circular queue.

→ In linear queue the start node and end node are empty but there is no provision of it in circular queue

→ a doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes

Singly Linked Lists are a type of data structure. It is a type of list. In a singly linked list each node in the list stores the contents of the node and a pointer or reference to the next node in the list. It does not store any pointer or reference to the previous node.

• What is skip list?

→ a skip list is a data structure that allows fast search within an ordered sequence of elements. Fast search is made possible by maintaining a linked hierarchy of subsequences, with each successive subsequence skipping over fewer elements than the previous one

• Define an AVL tree with suitable example.

→ AVL tree is a self-balancing binary search tree. It was the first such data structure to be invented. In an AVL tree, the heights of the two child sub trees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property.

• Define adjacency matrix with example.

→ an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertice0s are adjacent or not in the graph. In the special case of a finite simple graph, the adjacency matrix is a (0,1)-matrix with zeros on its diagonal

• List any three application of graph.

1. What is splaying?

→ A splay tree is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal in O(log n) amortized time.