Data Structures:
- Introduction to Data Structures
- Arrays
- Stacks
- Queues
- Lists
- Hash Data Structures
- Trees
- Sets
- Graphs Algorithms
Algorithms:
- General Concepts of Algorithms
- Sorting Algorithms
- Search Algorithms
- Huffman Coding
1) What are Data Structures? (Learn more: Introduction to Data Structures)
Data Structures are a method of structured or organized data storage which is easier to manage. Data usually has 2 aspects – the definition and its implementation. Data structures make sure they keep both the aspects separate. The definition is made available for different implementations for different programs or usages. A data structure, as the name suggests, stores the information in a structured way so that it can be easily created, viewed and managed. This involves creating complex data types which are a combination of various basic data types. One example can be a customer data type which will have a CustomerId of type Integer, Customer Name of type String and Address of type String.
2) What is an Array? (Learn more: Arrays)
An array is a set of values represented by a single variable. Arrays are usually stored sequentially which makes it possible to access each element by its index. An array will have a fixed number of elements that are accessible with their index. An array can store any type of data as allowed by the programming language or the platform used. You can have integer arrays or string arrays and even arrays of objects and structures. The maximum number of elements allowed in an array is mentioned in the array declaration so that the memory can be allocated together. This makes sure that the array elements are sequentially accessible using the index or pointer dynamically. In some languages like C, a string is represented by a character array.
Example:
|
int arr[5] = {2, 4, 6, 8, 10};
char alphabets[10] = {‘a’, ‘b’, ‘c’, ‘x’, ‘y’, ‘z’, ‘1’, ‘2’, ‘h’, ‘i’};
string names[3] = {“Smitha”, “Allen”, “Ritik”}; |
3) Why are stacks used to perform recursion? (Learn more: Stacks)
A Recursive function will call itself repeatedly. It is important to know who called the function with what value so that accordingly it will return the value to the right caller. Stacks function in the concept of LIFO or Last In First Out. For the same reason, it will recognize the last caller of the function that called it and will return the corresponding value to it. Recursion usually functions by stacking the caller addresses in the order in which the function is called.
Hence, it is important to use a separate stack every time the recursive function is called explicitly in the program. For example, if factorial(n) is a recursive function which is called twice in a program, for each call, a separate stack should be used. To be more specific, in the same program that calls factorial(x) and factorial(y), separate stacks should be used.
4) What are the basic features of a Queue? (Learn more: Queues)
Queues implement data structures that follow the First In First Out
concept. What is inserted first comes out first. This means that push operation happens at one end of the queue while pop operation happens at the other end. Even though the queue and stack operations are similar, in contrast to a stack which is open only at one end, the queue is open at both the ends.
5) What are the advantages of Linked Lists? (Learn more: Linked List)
Linked lists are a sequence of nodes connected to each other by a link to the next and or previous node. Linked lists are used to implement many real-time application requirements. One basic application of linked list is to create arrays dynamically. Since the linked lists contain the memory address to the next node, it need not be sequentially allocated. Each node will contain the address to the next node using which you can move to the next node. Linked lists allow easier implementation of stacks and queues. You implement insert and delete operations easily with linked lists.
6) What is a hashing? (Learn more: Hash Data Structures)
Hashing is converting a set of key-value pairs into indexed information or array which is easier to handle and retrieve. The information is always stored in key-value pairs with an index supporting a faster search. The size of the hash table is used for hashing the index. Hashing is done by method of the key % size where key is the key of a particular element in the key-value pair and the size is the size of the hash table. It is basically mapping where a particular item is stored in the hash table.
7) Explain the Tree data structure? (Learn more: Trees)
A tree has a root element with 1 or 2 nodes attached to each node. It is a hierarchical data structure used to store information in an ordered way. A binary tree can have zero to maximum 2 child nodes. The uppermost element or node is called the root and the lowermost element or node that has no child node is called a leaf node. The number of elements that connects a particular node from the root to that node determines the depth of a node. The height of a node is determined by the length of the node to its deepest leaf. A tree’s height is determined by the height of its root.
8) What is a set? (Learn more: Sets)
A set is a collection of unique elements, related to each other in some way and need not be in any order. You can consider a set of all football players of a team where none of the names are repeated and the names need not be stored in any order. But they are all related as players of the same team. We cannot add any other member or element in this set. A set of students who belong to a class is also another implementation. We cannot add another class student in one class set.
9) What is a Graph data structure? (Learn more: Graphs)
A Graph data structure contains a set of arrays called vertices and a set of edges. Every edge will have 2 vertices that point to a location of the edge. Graphs are used to implement images or networks wherein the edges or elements are related to each other in some way or the other. Every graph will have edges, vertices, path and adjacency. A graph can be represented as a tree data structure. The Vertex is the node. The Edge determines the path or the order in which other nodes are linked in the tree. Adjacency determines the nodes directly linked to another node by a path. A Path is the series of edges to traverse to reach a particular node.
10) What do you mean by Algorithm? (Learn more: General Concepts of Algorithms)
Algorithm is basically the step by step procedure involved in solving a computer problem. Once you have the login in place, clearly specified with the loops and ifs, you can easily implement it in any programming language. It is based on this algorithm that a more refined Flowchart is prepared which is used by the programmers to write it in a particular programming language. You can develop algorithms for the simplest processes to very complex procedures such as database programming. To understand an algorithm, it can be followed step by step simulating with possible values of input.
11) How do you classify sorting algorithms? (Learn more: sorting algorithms)
Sorting algorithms can be broadly classified comparison based & counting based, and in-place & not-in-place algorithms. Most of the sorting algorithms are based on comparison. The basic idea is to compare 2 elements and swap them or rearrange them based on the particular type of algorithm used.
Examples of comparison based algorithms are bubble sort, heap sort, selection sort, quick sort etc. The counting based algorithms like bucket sort and radix sort use the divide and rule algorithms to divide the entire collection and then sort the elements. The in-place algorithms are carried out without using any additional array or data structure. Examples of in-place algorithms are quick sort and heap sort. The not-in-place algorithms use an additional array or data structure for sorting. Examples of not-in-place algorithms are bucket sort and merge sort.
12) Explain the algorithm for linear search? (Learn more: Search Algorithm) (Learn more: Search Algorithm)
The linear search is the simplest of all search algorithms. The entire array is searched from the very first element till the element is found or till the end of array. The element is compared with all elements of the array till a match is found. Linear search can be done on a sorted or unsorted array.
13) What is Huffman Coding? (Learn more: Huffman Coding)
Huffman coding uses prefixes or weights to assign a code to the data being transmitted. More frequent codes get less weight and the rarely transmitted codes get more weight.
These codes are bit sequences assigned to the data which makes it a unique stream of data which can be easily decoded by the receiver without any vagueness. The codes or bit strings are assigned based on their probability or occurrence in the stream. This involves building a Huffman tree from the given data and to traverse the tree to assign the bit streams to the data.
Start Learning all the important concepts of DATA STRUCTURES & ALGORITHMS from an Interview Perspective with our tutorial Blog Series starting with Introduction to Data Structures.
Here is a list of some more questions that could be asked in your interview or written exam.
- Can you implement a queue using a stack?
- How to implement a queue using an array?
- How do you delete an element from an array?
- Explain collision resolution
- What is the difference between Chaining and Open addressing?
- Why is quicksort is preferred for arrays and merge sort for the linked list?
- How to find the length of a linked list?
- How do you convert a binary tree into a doubly-linked list?
- How to check if the given tree is a binary heap?
- What do you mean by shuffling?
Get one step closer to your dream job!
Prepare for your programming interview with Data Structures & Algorithms Interview Questions You’ll Most Likely Be Asked. This book has a whopping 200 technical interview questions on lists, queues, stacks, and algorithms and 77 behavioral interview questions crafted by industry experts and interviewers from various interview panels.