Placement Prep Q&A

Why do we need a data structure?

For efficient access to data, we need DS. DS is a specialized format for organizing, processing, retrieving and storing data.

What are primitive data types?

Integer, float, char, double, boolean etc.

What is the No-Primitive data type?

The data type can store more than 1 type of data. Ex: String, Array, Class, Interface.

List out Non-primitive DS.

Array, LL, Stack, Queue, Tree, Graph.

What are the features of the C language?

It is simple and efficient.
C language is portable or Machine Independent.
C is a mid-level Programming Language.
It is a structured Programming Language.
It has a function-rich library.
Dynamic Memory Management.
We can use pointers in C.

What are the basic data types associated with C?

Char – It can hold a single character. A character may be an alphabet, digit or special character
Int – It can hold an integer value. By default it ranges from -32768 to +32767
Float – Number with a fraction part. Its value ranges from -3.4 X 10-38 to + 3.4 X 1038.
Double – Double-precision floating-point value. Its value ranges from -1.7 X 10-308 to 1.7 X 10308
Void – Special purpose type without any value.

What is token?

The individual elements of a program that is meaningful to the compiler are called Tokens. Some Examples are

1. Identifiers

2. Keywords

3. Constants

4. Operators

5. Special Characters

6. Strings

What are Keywords in C Language?

Some of the words are reserved to do some specific task at the time of designing the compiler. These words are called keywords or reserve words. There are 32 keywords in C language.

Why is C called the Mother of all Languages?

C introduced many core concepts and data structures like arrays, linked lists, functions, strings, etc. Many languages designed after C are designed on the basis of C Language. Hence, it is considered as the mother of all languages.

What are the different storage class specifiers in C?

The different storage specifiers available in C Language are as follows:

auto
register
static
Extern

What is typecasting?

Typecasting is a process of converting one data type into another is known as typecasting.

The two types of type casting in C are:

Implicit Typecasting
Explicit Typecasting.

What is typedef in C?

In C programming, typedef is a keyword that defines an alias for an existing type.

What is a preprocessor?

The preprocessor for ‘C’ is a collection of special statements, called directives, which are executed at the beginning of the program compilation. The commands for the preprocessor are inserted in C source code and are called Compiler Directives. Each compiler directive is prefixed by a hash sign (#).

What do you mean by Memory Leak?

Memory Leak can be defined as a situation where a programmer allocates dynamic memory to the program but fails to free or delete the used memory after the completion of the code.

What are Enumerations?

Enumeration, also known as Enum in C, is a user-defined data type. It is used to create the user defined data type where we have a set of possible values to store. These are particularly useful while using an ordered list like Months, Weekdays etc. Using an enum makes the program more readable.

What is the difference between a++ and ++a?

a++ is a single machine instruction used to increment the value of a by 1. (Post increment). ++a is used to carry out pre-increment.

What is the use of '==' symbol?

The ‘==’ symbol or “equivalent to” or “equal to” symbol is a relational operator, i.e., it is used to compare two values or variables.

Differentiate between getch() and getche().

getch() reads characters from the keyboard but it does not use any buffers. Hence, data is not displayed on the screen.

getche() reads characters from the keyboard and it uses a buffer. Hence, data is displayed on the screen.

What is the difference between declaring a header file with < > and ” “?
The compiler looks for the header file in the Built-in Path if the header file is defined using < >. If the Header File is specified with the " " the compiler will first look in the current working directory for the file and if not found then it searches for the file in other locations.

Which statement is efficient and why? x=x+1; or x++; ?

x++; is the most efficient statement as it just a single instruction to the compiler while the other is not.

What are the limitations of scanf() and how can it be avoided?

scanf() cannot work with the string of characters.
It is not possible to enter a multi word string into a single variable using scanf().

Specify different types of decision control statements?

1. If-else statement.

2. normal if-else statement.

3. Else-if statement

4. nested if-else statement.

5. Switch statement.

What are static variables and functions?
Static variables and static functions are those that have the keyword "Static" in their declarations. The scope of variables declared with the Static keyword is limited to the function in which they are used.

What is the difference between = and == symbols in C programming?
When comparing a value or expression on the left with a value or expression on the right, the comparison operator '==' is used. The assignment operator "=" is used to assign the right-hand side value to the left-hand side variable.

When should we use the register storage specifier?
We use Register Storage Specifier if a certain variable is used very frequently. This helps the compiler to locate the variable as the variable will be declared in one of the CPU registers.

What is an auto keyword in C?

In C, every local variable of a function is known as an automatic (auto) variable. Variables which are declared inside the function block are known as a local variable. The local variables are also known as an auto variable.

What is the difference between const char* p and char const* p?

const char* p is a pointer to a const char.

char const* p is a pointer to a char const.

Write a program to print "hello world" without using a semicolon?

#include<stdio.h>

void main(){

if(printf("hello world")){}

}

What does the sprintf() function do?

The sprintf() stands for "string print." The sprintf() function does not print the output on the console screen. It transfers the data to the buffer. It returns the total number of characters present in the string.

What is a pointer?

A pointer is a special variable that holds the memory address of another variable. The storage retrieval of data using the memory address of a variable is faster than that of using the variable's name.

C provides a special operator * which is called ‘pointer operator’.

What is stray pointers?

It is a pointer whose memory has been deallocated after use, but it is used later in the code by some fault or logical error.

Describe Wild Pointers in C?

Uninitialized pointers in the C code are known as Wild Pointers.

Differentiate between calloc() and malloc()

calloc() and malloc() are memory dynamic memory allocation functions. The only difference between them is that calloc() will load all the assigned memory locations with value 0 but malloc() will not.

What is pointer to pointer in C?

A pointer that stores the address of another pointer is called a pointer to a pointer.A pointer to a pointer has one more ‘*’ than the pointer whose address it is going to store.

What is an array in C?

An array is a collection of elements with the same name and same data type. The identification of each element is done by its index value. Index value begins from 0(zero) and it is unique. All these elements are contiguous memory locations that are accessed with the same name with their index. There are three types of arrays, namely,

1. One Dimensional Array
2. Two Dimensional Array
3. Multi-Dimensional Array

Dangling Pointer Variable in C Programming?

It is a pointer that stores the value of another pointer that was previously allocated some memory and later deallocated.

What do you understand by calloc()?

calloc() is a dynamic memory allocation function that loads all the assigned memory locations with 0 value.

What is recursion in C?

When a function calls itself, this process is known as recursion. The function that calls itself is known as a recursive function.

What is a union?

‘union’ is also a derived data type like structure that means it is also used to define custom data types with the help of combinations of primitive data types.

One different thing in union as compared to structure is that the memory occupied by an object of union is the memory occupied by the largest member of the union. Another thing is that a union object can store only one value at a time.

What is command line argument?

Like a normal function, arguments can also be passed to main(). Values to these arguments can be passed to main() on command prompt (Command Line). So these arguments are called Command Line Arguments

What do you mean by the Scope of the variable?

Scope of the variable can be defined as the part of the code area where the variables declared in the program can be accessed directly. Examples of scope are local and global.

What is function?

A function is a small block of code which can perform a specific task. When the program passes the control to a function, the function performs the task and returns the control to the instruction following the calling instruction.

What is call by value and call by reference ?

A function can be called using following two methods –

1. Call by value

2. Call by reference

Call by value- In call by value method of function calling the copy of actual arguments is passed to ‘formal arguments’. So if we make any changes in formal arguments, actual arguments are not affected.

Call by Reference- In call by value method of function calling the address of actual arguments is passed to the function. So if we make any changes in formal arguments, the actual arguments are also changed.

What is pointer to functions ?

A pointer to a function points to the address of the executable code of the function. You can use pointers to call functions and to pass functions as arguments to other functions. The type of a pointer to a function is based on both the return type and parameter types of the function

What do you mean by a Nested Structure?
When a data member of one structure is referred by the data member of another function, then the structure is called a Nested Structure.

What is the difference between struct and union in C?

A structure is a group of elements stored in a block of memory where each member on the block gets a separate memory location to make them accessible at once
Whereas in the union, all the member variables are stored at the same location on the memory. memory occupied by an object of union is the memory occupied by the largest member of the union. Another thing is that a union object can store only one value at a time.

What is pointer to a structure?

Like, for a normal variable we can also make a pointer to a structure which can be used to store the address of another normal structure variable.

What information is given to the compiler while declaring a prototype function?

Name of the function
Parameters list of the function
Return type of the function

What is Data Structure?

The data structure is a way that specifies how to organise and manipulate the data. It also defines the way different sets of data relate to one another.

Describe the types of 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 the 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.

What are some applications of Data Structures?

Numerical analysis, operating system, AI, compiler design, database management, graphics, statistical analysis, and simulation.

What is Self Referential Structure?

When a member of a structure is a pointer to the same structure then the structure is called a self referential structure. Generally it contains two sections one for storing data elements and another one for storing the address of that structure.
struct node { int data; struct node *next; };

What is a multidimensional array?

A multidimensional array is a multidimensional array with more than one dimension. Multi-dimensional arrays are an extended form of one-dimensional arrays and are frequently used to store data for mathematical computations, image processing, and record management.

How the elements of a 2D array are stored in the memory?

Row-Major Order: In row-major ordering, all the rows of the 2D array are stored into the memory contiguously. First, the 1st row of the array is stored into the memory completely, then the 2nd row of the array is stored into the memory completely and so on till the last row. Column-Major Order: In column-major ordering, all the columns of the 2D array are stored into the memory contiguously. First, the 1st column of the array is stored into the memory completely, then the 2nd row of the array is stored into the memory completely and so on till the last column of the array.

Calculate the address of a random element present in a 2D array, given base address as BA.

Row-Major Order: If array is in a[m][n] form where m is the number of rows while n is the number of columns, then address of an element a[i][j] of the array stored in row major order.

Address(a[i][j]) = B. A. + (i * n + j) * size

B.A. is the base address.

Size – size of an array element

Column-Major Order: If array is declared as a[m][n] where m is the number of rows while n is the number of columns, then address of an element a[i][j] of the array stored in column major order. Address(a[i][j]) = ((j*m)+i)*Size + BA.

What is a Linked List?

A linked list is a collection of records and all the records are connected via pointers. It is a chain of data items connected by pointers and each item contains the address of the next item in the list. We can also say that a linked list is a collection of self referential structure nodes.

Types of Linked List

There are three types of linked list such as-

1) Singly Linked List

2) Doubly Linked List

3) Circular Linked List

Singly Linked List : In this type of linked list, every node stores the address or reference of the next node in the list and the last node has next address or reference as 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.

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.

What are the advantages of Linked List over an array?

The size of a linked list can be changed at runtime which is impossible in the case of the array.
The List is not required to be contiguously present in the main memory, the nodes can be stored anywhere in the memory connected through the links.
The List is dynamically stored in the main memory and grows as per the program demand while the array is statically stored in the main memory, size of which must be declared at compile time.
The number of elements in the linked list are limited to the available memory space while the number of elements in the array is limited to the size of an array.

Operations performed on linked lists

a) Creation of Linked List

b) Insertion of an Item in the list

c) Deletion of an item from the list

d) Traversing the list

e) Search an item from the list

What is Stack?

Stack is a data structure in which data items are inserted at one end called Top and can be removed from the same end. The insertion operation in a stack is called push operation and the deletion operation is called pop operation. Stack is LIFO(Last In First Out) or FILO(First In Last Out) Structure.

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 are different operations available in stack data structure?

Push – This adds an item to the top of the stack. The overflow condition occurs if the stack is full.

Pop – This removes the top item of the stack. Underflow condition occurs if the stack is empty.

What are different terms associated with stack data structure?

Push – This adds an item to the top of the stack. The overflow condition occurs if the stack is full.

Pop – This removes the top item of the stack. Underflow condition occurs if the stack is empty.

Top – This returns the top item from the stack.

is Empty – This returns true if the stack is empty else false.

Size – This returns the size of the stack.

What is a queue data structure?

A queue is an ordered collection of data items in which new elements can be added at one end called ‘Rear’ and can be deleted from another end called ‘Front’. It is a FCFS (First Come First Served) type of list in which the data item that comes first, is the first item to be removed from the queue. It is also called a FIFO (First in First Out) list.

Applications of queue data structure?

Breadth-first search algorithm in graphs
Job scheduling operations
Disk scheduling
CPU scheduling
Call management in call centers

What are different terms associated with queue data structure?
enqueue: This adds an element to the rear end of the queue. Overflow conditions occur if the queue is full.

dequeue: This removes an element from the front end of the queue. Underflow conditions occur if the queue is empty.

is Empty: This returns true if the queue is empty or else false.

rear: This returns the rear end element without removing it.

front: This returns the front-end element without removing it.

size: This returns the size of the queue

Types of queue

There are some variations of queues which are as following-

Circular Queue
Double ended queue (D-queue)
Priority Queue

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

The queue is a linear structure that follows the order First In First Out (FIFO) to access elements. Enqueue, Dequeue are basic operations on queue. 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 -- Operators are written in between their operands. (x+y)

Postfix notation (Reverse Polish notation) -- Operators are written after their operands. (xy+)

Prefix notation (Polish notation) -- Operators are written before their operands. (+xy)

Define the tree data structure.

The Tree is a recursive data structure made up of a set of one or more data nodes, with one node serving as the tree's root and the others serving as the root's children.

List the types of tree

General Tree
Forests
Binary Tree
Binary Search Tree
AVL Binary Tree
B Tree

What are Binary trees?

A binary Tree is a special type of tree in which each node can have at most two children. Binary tree is generally partitioned into three disjoint subsets, i.e. the root of the node, left sub-tree and Right binary sub-tree.

Binary Tree Traversal

In Order Traversal (Left,Root,Right)
Pre Order Traversal (Root,Left,Right)
Post Order Traversal (Left,Right,Root)

List some applications of Tree-data structure?

The manipulation of Arithmetic expression
Symbol Table construction
Syntax analysis
Hierarchical data model

What is a binary search tree?

A binary search tree is a binary tree in which each node's left child has a value lower than that of its parent and each node's right child has a value higher than that of its parent.

What is an AVL Tree?

Binary search trees that balance height are called AVL trees. The AVL tree ensures that the height difference between the left and right sub-trees is no greater than 1. This difference is called the Balance Factor.

Define the graph data structure?

Graphs in data structures are non-linear data structures made up of a finite number of nodes or vertices and the edges that connect them. A graph can be seen as a cyclic tree, where the vertices (Nodes) maintain any complex relationship among them instead of having parent-child relations.

Differentiate among cycle, path, and circuit?

Path: A Path is the sequence of adjacent vertices connected by the edges with no restrictions. Cycle: A Cycle can be defined as the closed path where the initial vertex is identical to the end vertex. Any vertex in the path cannot be visited twice Circuit: A Circuit can be defined as the closed path where the initial vertex is identical to the end vertex. Any vertex may be repeated.

Types of Graphs in Data Structures

1. Finite Graph

2. Infinite Graph

3. Trivial Graph

4. Simple Graph

5. Multi Graph

6. Null Graph

7. Complete Graph

8. Pseudo Graph

9. Regular Graph

10. Weighted Graph

Operations on Graphs in Data Structures

Creating graphs
Insert vertex
Delete vertex
Insert edge
Delete edge

What are the graph traversal algorithms?
There are two techniques to implement a graph traversal algorithm:

Breadth-first search
Depth-first search

What are the applications of Graph data structure?

The graph has the following applications:
Graphs are used in circuit networks,
Graphs are used in transport networks.
Graphs are used in maps that draw cities/states/regions as vertices and adjacency relations as edges.
Graphs are used in computer science to depict the flow of computation.
Users on Facebook are referred to as vertices, and if they are friends, there is an edge connecting them. The Friend Suggestion system on Facebook is based on graph theory.

Mention the data structures which are used in graph implementation?

In sequential representation, Adjacency matrix is used.

In Linked representation, Adjacency list is used.

Which data structures are used in BFS and DFS algorithm?

In the BFS algorithm, Queue data structure is used.

In the DFS algorithm, Stack data structure is used.

What is an algorithm?

An algorithm is a step by step method of solving a problem or manipulating data. It defines a set of instructions to be executed in a certain order to get the desired output.

Which data structure is used to perform recursion?

Stack data structure is used in recursion due to its LIFO(Last In First Out) nature.

What are the advantages of Binary search over linear search?

Comparatively fewer comparisons are made in binary search than in linear search. While binary search often takes O(log n) time to search a list of n elements, linear search typically takes O(n) time.

What are the advantages of Selection Sort?

It is simple and easy to implement.
It can be used for small data sets.
It is scalable.
It requires no additional storage space.
It is faster than any other sorting technique.

What is the difference between NULL and VOID?

Void is a data type identifier, Null is actually a value.

A void pointer is one that has no starting size, while a null variable simply shows an empty value.

Why is algorithm analysis necessary?

Multiple approaches can be used to solve a problem. As a result, for a given problem, numerous solution algorithms can be generated. To choose and implement the most appropriate algorithm. Algorithm analysis is necessary.

What standards are used in algorithm analysis?

Time and space are typically used to study algorithms. Specifically, how much more space and execution time the algorithm needs.

Give some examples of greedy algorithms.

Prim's Minimal Spanning Tree Algorithm
Kruskal's Minimal Spanning Tree Algorithm
Dijkstra's Minimal Spanning Tree Algorithm
Graph - Map Coloring
Graph - Vertex Cover
Job Scheduling Problem

What are some examples of divide and conquer algorithms?

Merge Sort
Quick Sort
Binary Search
Strassen's Matrix Multiplication
Closest pair (points)

What is linear searching?

Linear search tries to find an item in a sequentially arranged data type. These sequentially arranged data items are known as array or list. Linear search compares expected data items with each of data items in a list or array. The average case time complexity of linear search is O(n) and worst case complexity is Ο(n2). Data in target arrays/lists need not to be sorted.

What is binary search?

Only sorted lists or arrays can be used for binary searches. The middle is chosen in this search, which divides the full list into two pieces. The middle is compared first. The target value and the middle of the list are initially compared in this search.

What is bubble sort and how bubble sort works?

Each pair of adjacent items in a bubble sort algorithm are compared to each other and, if necessary, elements are exchanged to restore order. Because of its O(n2) time complexity, it is not appropriate for large data sets.

What exactly is an "insertion sort"?

The list is split into two sub-lists by insertion sort: sorted and unsorted. It inserts each element one at a time in the proper place in the sorted sub-list. The output after insertion is a sorted sub-list. It inserts each element from the unsorted sub-list into the sorted sub-list one at a time; repeatedly working on each element.

What is the selection sort?

Selection sort separates the data collection into sorted and unsorted sub-lists. The Minimum element is then chosen from the unsorted sub-list and added to the sorted list. This iterates unless all the elements from unsorted sub-list are stored into the sorted sub-list.

What is merge sort and how does it work?

Merge sort is a sorting algorithm based on divide and conquer programming approach. The list is continuously divided into smaller sub-lists until each sub-list has just one element. Once all of the sub-lists have been digested, they are then combined in a sorted order. It has a run-time complexity of Ο(n log n) and it needs Ο(n) auxiliary space.

What is shell sort?

Shell sort can be said to be a variant of insertion sort. Shell sort divides the list into smaller sublists based on some gap variable and then each sub-list is sorted using insertion sort. In best cases, it can perform upto Ο(n log n).

How does quick sort work?

Quick sort uses divide and conquer approach. It picks an element as a pivot and partitions the given array around the picked pivot. The values which are smaller than the pivot are arranged in the left partition and greater values are arranged in the right partition. Each partition is recursively sorted using quick sort.

What is a heap in data structure?

Heap is a unique balanced binary tree data structure in which the children of the root node are compared to the root node's key and arranged accordingly. A parent node in a min-heap has a key value that is less than that of its children, whereas a parent node in a max-heap has a key value that is greater than its childs.

What is hashing?