Good programming is all about data structures. As Linus Torvalds once said “Good programmers worry about data structures and their relationships”. Once you are working on actual projects in any organization, performance of your application depends a lot on data structures you will be using in the code. Choice of data structures is very important. That is why interviewers ask lot of questions from data structures topic.
What is a data structure:
A data structure is a specialized format for organizing and storing data. Every data structure is designed to organize data to suit specific purpose so that it can be accessed and worked with in appropriate ways.
For example a linked list is designed so that we do not require memory blocks at consecutive locations. While an array is beneficial when you need to access an element randomly. In linked list you can not access an element randomly. You have to move sequentially from one element to next.
What are different types of data structures:
Type of data structures available depends a lot on programming language. Few commonly available data structures are –
Read about these data structures in detail. Book by Yashwant Kanetkar is a good choice for covering basics of data structures.
Short answer questions:
Q: What is a linked list.
A: A linked list is a data structure in which data items are connected with pointers or references. Most of the recently developed languages do not support to access the memory locations directly hence linked lists are not supported.
Q: What is a stack.
A: Stack is an ADT (abstract data type) which is used to store and retrieve the data value in first in last out (FILO) or last in first out (LIFO) manner.
Q: What is Abstract Data Type?
A: Abstract data type is certain kind of data structure which is define by operations you can perform on it. For example Stack is an ADT which can be implemented using arrays but you can only perform push or pop (actually there are more operations, see next question) operations on stacks.
Q: What operations can be performed on a stack?
A: Below operations can be performed on stacks –
- push() – to add an item on top of stack.
- pop() – to remove one item from top of stack.
- peek() – to get value of item on top of stack without removing it.
- isempty() – to check if stack is empty or not.
- isfull() – to check if stack is full or not.
Q: What is a queue?
A: Queue is also an abstract data type. Unlike stacks it is open from both ends. Data is inserted from one end and can be retrieved from other end. Queue follows FIFO i.e. first in first out or LILO last in last out strategy.
Q: What operations can be performed on queue?
A: Operations performed on queue are similar to operations performed on stacks except to remove an item we use dequeue() and to insert we use enqueue() operation.
Q: What is a graph?
A: Graph is pictorial representation of data objects which are connected in pairs by links. These data objects are known as vertices while the links that connect them are known as edges.
Q: What is a tree?
A: A tree is a graph which is minimally connected and have no loops or circuits.
Q: What is the difference between walk, circuit, path, cycle, loop and trail in a graph?
A: Difference is given below
- Walk – When we start from one point, going to another point (and then another point) and may or may not return to starting point. In this process edges and vertices may be repeated. Open walk is one where starting and ending points are different. In closed walk staring and ending points are same.
- Trail – An open walk where vertices may be repeated by edges are not repeated.
- Circuit – Same as Trail but it is closed.
- Path – Open walk where neither vertices nor edges can be repeated.
- Cycle – A closed walk where neither vertices nor edges can be repeated.
- Loop – An edge connecting a data point to itself.
Q: What is a binary tree?
A: A special tree where each node can have at max two children.
Advance Data Structures:
- Memory efficient doubly linked list
- Suffix array and suffix tree
- AVL tree
- Splay tree
- B Tree
- Red black tree
Since these topics are bit advanced, we will not discuss them here. We will write articles in future to cover advanced data structures.
Programming questions asked from data structures:
We are listing few basic programming questions. We won’t be providing solution for these as we believe if you make programs for these questions on your own, you will learn more. Do not take help from the Internet. Try to code them on your own.
- Find the largest and second largest element in an array.
- Write a program to sort an array in descending order.
- Find the leaders in an array. A leader is the element which is largest of all the element on its right.
- Write a program to reverse a linked list.
- Write a program to find out if linked list is circular or not.
- Write a program to delete a node from linked list.
- Implement stack and its function using arrays.
- What is hashing.
Sorting algorithms are the algorithms which put elements of a list in certain order.
In-Place sorting :- Sorting algorithms which do not require any extra space (defining new array or variables in programming) are called in-place sorting algorithms. Example – bubble sort.
Not-In-Place sorting :- Sorting algorithms where extra memory space is required to sort the list. Example – merge sort.
Carnegie Mellon University have written a nice article on sorting algorithms along with code and complexity. Read at-least about Bubble, Insertion and selection sort.
Practice these questions and let us know if you have any issues. Comment for any query.