20+ Most Asked Data Structures Interview Questions with Answers

20+ Most Asked Data Structures Interview Questions with Answers

In this article, we will be discussing some of the most asked data structures interview questions by both IT-Service based & Product based companies.

Data Structures Interview Questions with Answers

Here are the 30+ most asked data structures interview questions.Data Structures & Algorithms is one of the most frequently tested subjects by a lot of companies. So make sure you have a quick look at these questions before the interview.

1) What do you mean by a Data structure?

Data structure is a format for storing data in a structured manner. For example, data like photos, videos are stored in gallery with the help of a data structure. It is not a separate programming language. It is just an implementation method and can be implemented using any one of the programming language like C, C++, Java, etc.

2) What are some of the applications of DS?

Some of the real-time applications of Data Structures are:

  1. For representing a city region telephone network.
  2. To implement back functionality in the internet web browser.
  3. To store dynamically growing data which is accessed very frequently, based upon a key value.
  4. To implement the undo function in a text editor.
  5. To store information about the directories and files in a system.

For more applications of each of the data structures, check out the below links:

  • Applications of a Stack
  • Applications of Priority Queue
  • Applications of Depth First Search
  • Applications of Breadth-First Search

3) What are the advantages of a Linked list over an array?

Consider a scenario, where we need to store large amount of data in an array. But, the memory to store that data is not available contiguously. In this case we cannot use array. Hence, we go for a linked list. Since each node is connected using link, it is not necessary that memory has to be contiguous.

Also, some of the major differences between a Linked List and an array are given belowFor more, click here.

Arrays
Linked List
Array elements can be accessed randomly using the array index.
Random accessing is not possible in linked lists. The elements will have to be accessed sequentially.
Data elements are stored in contiguous locations in memory.
New elements can be stored anywhere and a reference is created for the new element using pointers.

4) Write the syntax in C to create a node in the singly linked list.

struct node 
{
 int data; 
 struct node *next;
};
struct node *head, *ptr;
ptr = (struct node *)malloc(sizeof(struct node));

5) What is the use of a doubly-linked list when compared to that of a singly linked list?

data structures interview questions

In a singly linked list, we have only forward links. Hence, we cannot traverse the linked list in a backward manner. In order to overcome this, we go for a doubly linked list. In a doubly linked list, each node has three fields such as previous, data and next field and has two links such as a forward and backward link. The previous field of the first node and the address field of the last node is NULL. The previous field of the second node has the address of the first node and so on.

Also, accessing of elements can be done more efficiently in case of a doubly linked list.

6) What is the difference between an Array and Stack?

Stack Data Structure:

  • Size of the stack keeps on changing as we insert and delete the element
  • Stack can store elements of different data type

Array Data Structure:

  • Size of the array is fixed at the time of declaration itself
  • Array stores elements of similar data type

7) What are the minimum number of Queues needed to implement the priority queue?

Two queues are needed. One queue is used to store the data elements, and another is used for storing priorities. Check out the implementation of a Priority Queue.

8) What are the different types of traversal techniques in a tree?

There are three main traversals of a tree such as In-order, Pre-order, Post-order.

Algorithm of In-order traversal:

Traverse the left sub-tree
Visit the root
Traverse the right sub-tree

Algorithm of Pre-order traversal:

Visit the root
Traverse the left sub-tree
Traverse the right sub-tree

Algorithm of Post-order traversal:

Traverse the left sub-tree
Traverse the right sub-tree
Visit the root

9) Why it is said that searching a node in a binary search tree is efficient than that of a simple binary tree?

When searching any node in binary search tree, the value of the target node is compared with the parent node and accordingly either left sub tree or right sub tree is searched. So, one has to compare only particular branches. Thus searching becomes efficient.

10) What are the applications of Graph DS?

Graphs are used in circuit networks where points of connection are drawn as vertices and component wires become the edges of the graph, in transport networks where stations are drawn as vertices and routes become the edges of the graph, in maps that draw cities/states/regions as vertices and adjacency relations as edges, in program flow analysis where procedures or modules are treated as vertices and calls to these procedures are drawn as edges of the graph.

11) Can we apply Binary search algorithm to a sorted Linked list?

No, we cannot apply the binary search algorithm to a sorted linked list because finding the index of the middle element is difficult.

12) When can you tell that a Memory Leak will occur?

A memory leak occurs when a program does not free a block of memory allocated dynamically.

13) How will you check if a given Binary Tree is a Binary Search Tree or not?

To know that you need to check the inorder traversal of a binary tree. If it is sorted, then the binary tree is BST. Click here to know how to perform inorder traversal.

14) Which data structure is ideal to perform recursion operation and why?

Stack is the most ideal for recursion operation. This is mainly because of its LIFO (Last In First Out) property, it remembers the elements & their positions, so it exactly knows which one to return when a function is called.

15) What are some of the most important applications of a Stack?

Some of the important applications are given below. Check them out to know the detailed code & explanation.

  • Balanced parenthesis checker
  • Redundant braces
  • Infix to postfix using a stack
  • Infix to prefix using a stack

16) Convert the below given expression to its equivalent Prefix And Postfix notations.

((A + B) * C – (D – E) ^ (F + G))

Prefix Notation: ^  * +ABC  DE + FG

postfix Notation: AB + C * DE FG + ^

Important Data Structures Interview Programs

Here are some important programs based on the concepts of data structures which are important data structures interview questions for freshers.

17)Sorting a stack using a temporary stack

18)Program to reverse a queue

19) Program to reverse first k elements of a queue

20)Program to return the nth node from the end in a linked list

21)Reverse a linked list

22)Replace each element of the array by its rank in the array

23) Check if a given graph is a tree or not

24) Find out the Kth smallest element in an unsorted array

25) How to find the shortest path between two vertices

Practice more Data Structure questions

Tips to Get Hired Fast

Tips to Get Hired Fast

There is this strange relief that floods through a final year college student’s body as he/she walks out of a room with an offer letter in their hand. The happiness of being placed straight out of college is inexplicable. For one or two semesters, your grades don’t matter (or so you think) and you know exactly where life is headed once you are done with college. The certainty that awaits you in the big, bad world just makes the last few months in college a breeze.

However, receiving a job offer is not a walk in the park. To earn your offer, you must have the flawless résumé, ace the aptitude exam, assert yourself during the group discussion, and finally ace the final interview.

When it comes to attending an interview, the majority of people are nervous. For many students and professionals, the anxiety and stress that pervades their minds before entering an interview room is a reality. We offer a few tips to assist you combat anxiousness and get rid of the cold feet that haunt you before every interview.

1. Research The Company

We recognise that you are interested in the position, and that the organisation provides excellent chances for advancement. But how much do you know about the company? You must conduct detailed background investigation. Learn about your future employer’s vision, goal, and values. Your personal values must coincide with the values of the company. If you don’t, you can end up pretending interest in the firm, which is almost always deadly to your interview.

Furthermore, getting to know the organisation thoroughly allows you to determine whether or not you want to be a part of their culture. It also aids you in dealing with the one-in-a-million chance of any company-related enquiries. You will feel more secure in yourself now that you have a better understanding of the company.

2. Research The Job

Because there’s nothing worse than being stuck in a work you despise, it’s critical to understand the job profile thoroughly. If the firm is right for you, the job should be as well. It doesn’t help anyone to be in the perfect firm for the wrong job. If your academic background, as well as previous work experience, matches the job profile and your interests, you should absolutely apply. Otherwise, think about it again.

3. Be Confident

The majority of candidates, particularly freshers , are afraid of making mistakes during their interviews. They are frequently unclear of what is proper and incorrect, as well as what should be uttered in front of an interviewer. What most of us forget is that businesses are extremely fortunate to have the greatest prospects interested in working with them. You must be confident in what you can do for the organisation, and you must emphasise this in the interview as much as possible.

4. Rehearse the Interview

In any interview, there are a few standard questions that are asked. Answers to questions like “Tell me about yourself?” and “Why did you choose this company?” often contribute to the interviewer’s first impression. In this process, it’s important to practise and comprehend the context of your answers.

You can also try to anticipate what questions an interviewer would ask you based on your job profile and prepare relevant responses. You should also keep up with the most recent and serious issues in your line of work and be ready to answer queries about them. You will be more assured if you have a good understanding of the subject.

5. Have a Realistic CV

Creating a CV with false or unrealistic information is the greatest sacrilege you can commit in an interview. Your potential employer is very likely to have conducted a background check on you using social media platforms. A skewed CV isn’t going to benefit you.

Being open and honest about your talents and work experience will show them that you are serious about your job.

In the eyes of your employer, listing all of your experiences provides you a distinct advantage.

6. Be Honest and Flexible

You must not only be knowledgeable about your topic of interest, but you must also be honest and flexible in your work approach. Companies need employees that are dependable and prepared to adapt to the changing demands of the organisation and the tasks they must complete. If you demonstrate this mindset in your interview, you will have a significant advantage over other candidates who are not demonstrating these attributes.

7. Dress To Kill

Your posture and the clothes you’re wearing have already made an impact on your interviewers the moment you step through the door. If you are well-dressed and groomed, it demonstrates to your employer that you are serious about the interview and thus truly interested in the firm. Dressing sloppily indicates that you are unconcerned about yourself or your career.

8. Interview Etiquette

During an interview, there are some basic politeness rules to follow. You must enter gently and only take your seat after greeting your interviewers. It’s a good idea to shake hands with them, and make sure your grip is firm and confident. Keep a cheerful attitude and smile. You must be courteous to your interviewer and should never be impolite to them.

 

The majority of interviewers are looking for a candidate who they wish to hire. Getting the job will be a breeze if you have faith in your abilities and knowledge.

Informatica Placement Questions for Freshers

Informatica placement questions from Informatica placement papers will be discussed here. These will be very useful for students preparing for Informatica recruitment process.

Informatica Placement Questions with Answers

Informatica online test pattern consists of two rounds – Programming MCQs round & Coding round. Informatica placement questions for both these round are discussed below. Before you get starting with solving them, check out Informatica recruitment process.

Informatica Programming Questions

This is the first round of the Informatica recruitment process. This round consists of 30 programming MCQs which need to be solved in 45 minutes of time. Also, there is no negative marking involved. Informatica programming round syllabus is as given below.

Topic Expected number of questions
Operating System 5-8
Database Management (DBMS) 4-5
Data Structures 5-8
Algorithms 5-8

You can practice programming MCQs related to these topics here:

  • Operating System
  • Database Management
  • Data Structures
  • Algorithms

Informatica Coding Questions

Informatica coding round is the second round of Informatica recruitment process.Only students who clear the first round will be eligible for this round. This round consists of 4 coding questions which need to be solved in a duration of 90 mins.

Below are some of the sample Informatica coding questions taken from previous year Informatica placement papers.

1)Given an input island matrix, where 0 represents water and 1 represents land. Find the total number of islands that are formed by connected 1s.

2)Find the median of two sorted arrays of the same size.

3)Given an array and a value, find if there is a subset of the given set with the sum equal to the given sum.

4)Finding the non-repeating element in a given array

5)Given weights and values of n items, the task is to put these items in a knapsack of capacity W to get the maximum total value in the knapsack.In this problem, 0-1 means that we can either put the complete item in the knapsack or ignore it.

6)Find the height of a binary tree.

7)Given an input array arr = {5, 15, -30, 10, -5, 40, 10}.

The contiguous sub-array with maximum sum consists of elements 10, -5, 40, 10. Print their sum.

Output: 55

Java solution:

import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++)
        {
            arr[i] = sc.nextInt();
        }
        System.out.println(maxSubsequenceSum(arr));        
    }
    public static int maxSubsequenceSum(int[] X) {
        int max = X[0];
        int sum = X[0];
        for (int i = 1; i < X.length; i++) {
            sum = Math.max(X[i], sum + X[i]);
            max = Math.max(max, sum);
        }
        return max;
    }
}

8)Check if a number can be written as a sum of k prime numbers.

Here, the given number is 10 and the value of k is 2. We need to check whether 10 can be represented using the sum of 2 prime numbers or not.

Yes, 10 can be represented as 5 + 5, where 5 is a prime number.Hence, the output is Yes.If not, then the output is No.

Java solution:

import java.util.*;
public class Prime{
    public static boolean isprime(int x)
    {
        for (int i = 2; i * i <= x; i++)
            if (x % i == 0)
             
                return false;
        return true;
    }
    public static boolean isSum(int N, int K)
    {
        if (N < 2 * K)
            return false;
        if (K == 1)
            return isprime(N);
             
        if (K == 2)
        {
            if (N % 2 == 0)
                return true;
            return isprime(N - 2);
        }
        return true;
    }
     public static void main (String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        if (isSum(n, k))
            System.out.print("Yes");
        else
            System.out.print("No");
    }
}

9) Lexicographic rank of a string

Given a string, find its rank among all its permutations sorted lexicographically. For example, consider a string abc. Permutations of the given string after lexicographical order is:

  • abc
  • acb
  • bac
  • bca
  • cab
  • cba

From the above combinations, the rank of abc is 1, the rank of acb is 2, and rank of cba is 6.Another example, consider a string she. The rank of this string is 6.

One simple solution is to initialize rank as 1, generate all permutations in lexicographic order. After generating a permutation, check if the generated permutation is the same as a given string, if same, then return rank, if not, then increment the rank by 1.

In the input string, S is the first character. There are a total of 3 characters and 2 of them are smaller than S. So there can be 2 * 2! smaller strings where first character is smaller than S, like following

  • h x x
  • h x x
  • e x x
  • e x x

Repeat the same process for h, rank is 2 * 2! + 1 * 1! +..

Repeat the same process for e, rank is 2 * 2! + 1 * 1! + 0 * 0!

Rank = 2 * 2! + 1 * 1! + 0 * 0! = 5

Note that the above computations find count of smaller strings. Therefore rank of given string is count of smaller strings plus 1. The final rank = 1 + 5 = 6

C solution:

#include <stdio.h>#include <string.h>
int fact(int n)
{
    return (n <= 1) ? 1 : n * fact(n - 1);
}
int findSmaller(char* str, int low, int high)
{
    int countRight = 0, i;
 
    for (i = low + 1; i <= high; ++i)
        if (str[i] < str[low])
            ++countRight;
 
    return countRight;
}
int findRank(char* str)
{
    int len = strlen(str);
    int mul = fact(len);
    int rank = 1;
    int countRight;
 
    int i;
    for (i = 0; i < len; ++i) {
        mul /= len - i;
        countRight = findSmaller(str, i, len - 1);
        rank += countRight * mul;
    }
    return rank;
}
int main()
{
    char str[50];
    scanf("%s", str);
    printf("%d", findRank(str));
    return 0;
}

10)Find ceil value in a BST.

Ceil: Rounds x upward, returning the smallest integral value that is not less than x.

There are numerous applications where we need to find the floor (ceil) value of a key in a binary search tree. For example, consider designing a memory management system in which free nodes are arranged in BST.

Ceil Value Node: Node with smallest data larger than or equal to the key value.

Imagine we are moving down the tree, and assume we are at the root node. The comparison yields three possibilities,

  1. A)Root data is equal to key. We are done, root data is ceil value.
  2. B)Root data < key value, certainly the ceil value cant be in the left subtree. Proceed to search on right subtree as a reduced problem instance.
  3. C)Root data > key value, the ceil value may be in the left subtree. We may find a node with is larger data than the key value in the left subtree, if not the root itself will be ceil node.

Here is the code for cell value.

C solution:

#include <stdio.h>#include <stdlib.h>
struct node {
    int key;
    struct node* left;
    struct node* right;
};
struct node* newNode(int key)
{
    struct node* node = (struct node*)malloc(sizeof(struct node));
    node->key = key;
    node->left = NULL;
    node->right = NULL;
    return (node);
}
int Ceil(struct node* root, int input)
{
    if (root == NULL)
        return -1;
    if (root->key == input)
        return root->key;
    if (root->key < input)
        return Ceil(root->right, input);
    int ceil = Ceil(root->left, input);
    return (ceil >= input) ? ceil : root->key;
}
int main()
{
    struct node* root = newNode(8);
 
    root->left = newNode(4);
    root->right = newNode(12);
 
    root->left->left = newNode(2);
    root->left->right = newNode(6);
 
    root->right->left = newNode(10);
    root->right->right = newNode(14);
 
    for (int i = 0; i < 16; i++)
        printf("%d %d\n", i, Ceil(root, i));
 
    return 0;
}

Practice more coding questions

DBMS | Interview Questions

DBMS | Interview Questions

Interviews are the most important step that will help you land your dream job. Preparing for your interview will help you appear calm, cool and collected. Here are a few DBMS Interview Questions that will help you prepare for your interview.

DBMS Interview Questions

Q1. Explain the terms database and DBMS. Also, mention the different types of DBMS.

Ans 1. A database could be defined as a prearranged collection of figures known as data.

DBMS short for Database Management Systems refers to the applications that are designed which enable user interaction with other applications. In simpler words, it could also be defined as a software application which interacts with databases, applications, and users to capture and analyze the required data. The data stored in the database could be retrieved, deleted and modified based on the client’s needs.

The different types of DBMS are:

  • Relational DBMS (RDBMS): RDBMS uses a structure that allows the users to, access data with another piece of data in a database and data is stored in the form of tables in RDBMS
  • Hierarchical DBMS: Its structure resembles that of a tree, where the nodes represent records and the branches of the tree represent fields.
  • Network DBMS: Network DBMS supports many-to-many relations where multiple member records can be linked.
  • Object-oriented DBMS: An object is a small individual software that is used to store pieces of data and the instructions for the actions to be done with the data

Q2. What are the advantages of DBMS?

Ans 2. The advantages of DBMS are:

  • Data Independence: This feature helps enable to change the structure of the data without affecting the structure of any of the running application programs.
  • Sharing of Data: Multiple users can use data from the same database simultaneously which proves to be useful for larger organizations.
  • Integrity constraints: This allows the data to be stored in a database in a refined manner.
  • Redundancy control: DBMS has a mechanism that helps control the redundancy of data by integrating all the data into a single database.
  • Provide backup and recovery facility: DBMS has this feature of ‘backup and recovery’ that automatically creates the data backup and restore the data as and when required.

Q3. What are the various kinds of interactions catered by DBMS?

Ans 3. DBMS caters various kinds of interactions, they are:

  • Data definition
  • Update
  • Retrieval
  • Administration

Q4. What is SQL?

Ans 4. SQL stands for Structured Query Language is an ANSI standard language updates database and commands for accessing.

Q5. What do you understand by query optimization?

Ans 5. Query optimization could be defined as the phase which identifies a plan for evaluation query that has the least estimated cost and it comes into the picture when there are a lot of algorithms and methods to execute the same task.

The advantages of query optimization are:

  • Faster output
  • A larger number of queries can be executed in comparatively less time
  • Reduction in time and space complexity

Q6. What are the different levels of abstraction in the DBMS?

Ans 6. There are 3 levels of data abstraction, namely

  • Physical Level: This is the lowest level of the data abstraction and this shows how the data is stored in the database.
  • Logical Level: This is the next level of the data abstraction and this shows the type of the data and the relationship among the data that is stored in the database.
  • View Level: The view level is the highest in the data abstraction and this shows or states only a part of the database.

Q7. Define Normalization.

Ans 7. Normalization is the process of analyzing relational schemas which are based on their respective functional dependencies and the primary keys so that they fulfil certain properties.

Properties:

  • To minimize data redundancy.
  • To minimize the anomalies of Insert, Delete and Update.

Q8. Define Denormalization.

Ans 8. Denormalization could be defined by boosting up database performance, adding redundant data which in turn helps rid of complex data.

Q9. What do you understand by the terms Entity, Entity Type, and Entity Set in DBMS?

Ans 9.

  • Entity: An entity could be defined as a real-world object that has attributes, which are nothing but characteristics of that particular object. Consider, an employee can be an entity and this can have attributes such as empid, empname, etc.
  • Entity Type: Entity type is nothing but a collection of entities, having the same attributes. Generally, an entity type refers to one or more related tables in a particular database. Consider this, An employee can have attributes such as empid, empname, department, etc.
  • Entity Set: An entity set is the collection of all the entities of a particular entity type in a database. For example, a set of employees, a set of companies, and a set of people can come under an entity set.

 Q10. What are the different types of normalization?

Ans 10. There are many successive levels of normalization and they are known as normal forms. Each consecutive normal form is dependent on the previous one. Given below are the first three normal forms.

  • First Normal Form: In 1NF there are no repeating groups within rows
  • Second Normal Form: In 2NF every non-key (supporting) column value is dependent on the whole primary key.
  • Third Normal Form: In the 3NF, dependencies solely on the primary key and no other non-key (supporting) column value.

Q11. Explain the concepts of a Primary key and Foreign Key.

Ans 11. Primary Key uniquely identifies the records in a database table while Foreign Key, on the other hand, is used to link two or more tables together.

Example: Consider 2 tables – Employee and Department. Both have one common field/column as ‘ID’ where ID is the primary key of the Employee table while this happens to be the foreign key for the Department table.

 

Q12. Explain the concept of ACID properties in DBMS?

Ans 12. ACID properties are a combination of Atomicity, Consistency, Isolation, and Durability properties. These properties prove to be very helpful in allowing a safe and secure way of sharing the data amongst multiple users.

  • Atomicity: When changes are being done to the data it feels as though a single operation is performed. In other words, either all the changes are performed, or none of them is performed.
  • Consistency: Data must be in a consistent state at the beginning of the transaction as well as the end of the transaction.
  • Isolation: As the name itself suggests, this ensures that each transaction that occurs is in isolation with others. Simply put a transaction which has started but not yet completed should be in isolation with others, this is done so that the other transaction does not get impacted with this transaction.
  • Durability: In the event of system failure, after the transaction is completed, changes to the data persist and are not undone. Hence, due to this property data is always in a durable state.

 

Q13. What are the different types of joins in SQL?

 

Ans 13. There are 4 types of Joins in SQL. They are

  • Inner Join: The inner join is used to fetch the data among the tables which are common in both the tables.
  • Left Join: The left join returns all the rows from the table which is on the left side of the join but only the matching rows from the table which is on the right side of the join.
  • Right Join: The right join returns all the rows from the table which is on the right side of the join but only the matching rows from the table which is on the left side of the join.
  • Full Join: The full join returns the rows from all the tables on which the join condition has put and the rows which do not match hold null values.
Introduction to Cache Memory

Introduction to Cache Memory

Cache Memory          

Analysis of a large number of programs has shown that a number of instructions are executed repeatedly. This may be in the form of simple loops, nested loops, or a few procedures that repeatedly call each other.

It is observed that many instructions in each of a few localized areas of the program are repeatedly executed, while the remainder of the program is accessed relatively less. This phenomenon is referred to as locality of reference.

Cache memory between CPU and the main memory

Now, if it can be arranged to have the active segments of a program in a fast memory, then the total execution time can be significantly reduced. It is the fact that CPU is a faster device and memory is a relatively slower device. Memory access is the main bottleneck for the performance efficiency. If a faster memory device can be inserted between main memory and CPU, the efficiency can be increased. The faster memory that is inserted between CPU and Main Memory is termed as Cache memory. To make this arrangement effective, the cache must be considerably faster than the main memory, and typically it is 5 to 10 time faster than the main memory. This approach is more economical than the use of fast memory device to implement the entire main memory. This is also a feasible due to the locality of reference that is present in most of the program, which reduces the frequent data transfer between main memory and cache memory.

Operation of Cache Memory   

   

The memory control circuitry is designed to take advantage of the property of locality of reference. Some assumptions are made while designing the memory control circuitry:

  1. The CPU does not need to know explicitly about t
  2. he existence of the cache.
  3. The CPU simply makes Read and Write request. The nature of these two operations are same whether cache is present or not.
  4. The address generated by the CPU always refer to location of main memory.
  5. The memory access control circuitry determines whether or not the requested word currently exists in the cache.

Mapping Functions

The mapping functions are used to map a particular block of main memory to a particular block of cache. This mapping function is used to transfer the block from main memory to cache memory. Three different mapping functions are available:

Direct mapping:

A particular block of main memory can be brought to a particular block of cache memory. So, it is not flexible.

Associative mapping:

In this mapping function, any block of Main memory can potentially reside in any cache block position. This is much more flexible mapping method.

Block-set-associative mapping:

In this method, blocks of cache are grouped into sets, and the mapping allows a block of main memory to reside in any block of a specific set. From the flexibility point of view, it is in between to the other two methods.

All these three mapping methods are explained with the help of an example.

Consider a cache of 4096 (4K) words with a block size of 32 words. Therefore, the cache is organized as 128 blocks. For 4K words, required address lines are 12 bits. To select one of the blocks out of 128 blocks, we need 7 bits of address lines and to select one word out of 32 words, we need 5 bits of address lines. So the total 12 bits of the address is divided for two groups, lower 5 bits are used to select a word within a block, and higher 7 bits of the address are used to select any block of cache memory.

Let us consider the main memory system consisting 64K words. The size of the address bus is 16 bits. Since the block size of the cache is 32 words, so the main memory is also organized as block size of 32 words. Therefore, the total number of blocks in main memory is 2048 (2K x 32 words = 64K words). To identify any one block of 2K blocks, we need 11 address lines. Out of 16 address lines of main memory, lower 5 bits are used to select a word within a block and higher 11 bits are used to select a block out of 2048 blocks.

Number of blocks in the cache memory is 128 and number of blocks in main memory is 2048, so at any instant of time, only 128 blocks out of 2048 blocks can reside in cache menory. Therefore, we need mapping function to put a particular block of main memory into appropriate block of cache memory.

Direct Mapping Technique:

The simplest way of associating main memory blocks with cache block is the direct mapping technique. In this technique, block k of main memory maps into block k modulo m of the cache, where m is the total number of blocks in cache. In this example, the value of m is 128. In direct mapping technique, one particular block of main memory can be transferred to a particular block of cache which is derived by the modulo function.

Since more than one main memory block is mapped onto a given cache block position, contention may arise for that position. This situation may occurs even when the cache is not full. Contention is resolved by allowing the new block to overwrite the currently resident block. So the replacement algorithm is trivial.

The detail operation of direct mapping technique is as follows:

The main memory address is divided into three fields. The field size depends on the memory capacity and the block size of cache. In this example, the lower 5 bits of address is used to identify a word within a block. Next 7 bits are used to select a block out of 128 blocks (which is the capacity of the cache). The remaining 4 bits are used as a TAG to identify the proper block of main memory that is mapped to cache.

When a new block is first brought into the cache, the high order 4 bits of the main memory address are stored in four TAG bits associated with its location in the cache. When the CPU generates a memory request, the 7-bit block address determines the corresponding cache block. The TAG field of that block is compared to the TAG field of the address. If they match, the desired word specified by the low-order 5 bits of the address is in that block of the cache.

If there is no match, the required word must be accessed from the main memory, that is, the contents of that block of the cache is replaced by the new block that is specified by the new address generated by the CPU and correspondingly the TAG bit will also be changed by the high order 4 bits of the address.

Replacement Algorithms

When a new block must be brought into the cache and all the positions that it may occupy are full, a decision must be made as to which of the old blocks is to be overwritten. In general, a policy is required to keep the block in cache when they are likely to be referenced in near future. However, it is not easy to determine directly which of the block in the cache are about to be referenced. The property of locality of reference gives some clue to design good replacement policy.

Least Recently Used (LRU) Replacement policy:

Since program usually stay in localized areas for reasonable periods of time, it can be assumed that there is a high probability that blocks which have been referenced recently will also be referenced in the near future. Therefore, when a block is to be overwritten, it is a good decision to overwrite the one that has gone for longest time without being referenced. This is defined as the least recently used (LRU) block. Keeping track of LRU block must be done as computation proceeds.

Consider a specific example of a four-block set. It is required to track the LRU block of this four-block set. A 2-bit counter may be used for each block.

When a hit occurs, that is, when a read request is received for a word that is in the cache, the counter of the block that is referenced is set to 0. All counters which values originally lower than the referenced one are incremented by 1 and all other counters remain unchanged.

When a miss occurs, that is, when a read request is received for a word and the word is not present in the cache, we have to bring the block to cache.

There are two possibilities in case of a miss:

If the set is not full, the counter associated with the new block loaded from the main memory is set to 0, and the values of all other counters are incremented by 1.

If the set is full and a miss occurs, the block with the counter value 3 is removed , and the new block is put in its place. The counter value is set to zero. The other three block counters are incremented by 1.

It is easy to verify that the counter values of occupied blocks are always distinct. Also, it is trivial that highest counter value indicates least recently used block.

First In First Out (FIFO) replacement policy:

A reasonable rule may be to remove the oldest from a full set when a new block must be brought in. While using this technique, no updation is required when a hit occurs. When a miss occurs and the set is not full, the new block is put into an empty block and the counter values of the occupied block will be increment by one. When a miss occurs and the set is full, the block with highest counter value is replaced by new block and counter is set to 0, the counter value of all other blocks of that set is incremented by 1. The overhead of the policy is less since no upload is required during the hit.

Random replacement policy:

The simplest algorithm is to choose the block to be overwritten at random. Interestingly enough, this simple algorithm has been found to be very effective in practice.

Difference between Virtual Circuits and Datagram Networks

Difference between Virtual Circuits and Datagram Networks

There are a number of differences between Virtual circuits and Datagram networks. Virtual Circuits are computer networks that provide connection-oriented services, while those providing connection-less services are called as Datagram networks.

Examples: The Internet which we use is based on Datagram network. ATM (Asynchronous Transfer Mode) and frame relay – are virtual circuit networks and, therefore they use connections at the network layer.

 

Differences between Virtual Circuits and Datagram Networks

 

Virtual Circuits Datagram Networks
Virtual circuits are connection-oriented, which means that there is a reservation of resources like buffers, bandwidth, etc. for the time during which the newly setup VC is going to be used by a data transfer session. It is connectionless service. There is no need for reservation of resources as there is no dedicated path for a connection session.
A virtual circuit network uses a fixed path for a particular session, after which it breaks the connection and another path has to be set up for the next the next session. A Datagram based network is a true packet switched network. There is no fixed path for transmitting data.
All the packets follow the same path and hence a global header is required only for the first packet of connection and other packets will not require it. Every packet is free to choose any path, and hence all the packets must be associated with a header containing information about the source and the upper layer data.
Packets reach in order to the destination as data follows the same path. Data packets reach the destination in random order, which means they need not reach in the order in which they were sent out.
Virtual Circuits are highly reliable. Datagram networks are not as reliable as Virtual Circuits.
Implementation of virtual circuits is costly as each time a new connection has to be set up with reservation of resources and extra information handling at routers. But it is always easy and cost-efficient to implement datagram networks as there is no need of reserving resources and making a dedicated path each time an application has to communicate.
Get Access To Our Premium Courses
Install our application from PlayStore and get discounts on our new courses.

Pin It on Pinterest