Interview Questions

Top Data Structure Interview Questions & Answers10 min read

January 5, 2020 7 min read
data structure interview questions

author:

Top Data Structure Interview Questions & Answers10 min read

Read­ing Time: 7 min­utes

Have you ever won­dered, how data is stored and orga­nized in the data­bas­es? It’s pos­si­ble only due to the data struc­ture. You can orga­nize the data and make it avail­able at any point in time. If you are look­ing to grab a job in the top prod­uct-based com­pa­nies like Google, Microsoft, Ama­zon, Apple Inc, etc, you need to have a strong data struc­ture foun­da­tion.

In this arti­cle, we will be dis­cussing var­i­ous data struc­ture inter­view ques­tions and answers to help you. In fact, these ques­tions and answers will help you get an overview of the inter­view. If you can mas­ter the basics, there will be enough oppor­tu­ni­ty to land into your dream job.

This blog will help you get an insight into the data struc­ture inter­view. Fur­ther­more, we have tried to give you an overview from basics to advanced lev­els to make you feel com­fort­able dur­ing the inter­view.

In addi­tion to this, we will give you a link to a brief overview of pro­gram­mat­ic ques­tions. They are also asked dur­ing the inter­view. To sum up, the main pur­pose of this blog is to guide you through every pos­si­ble stage of data struc­ture inter­view.

Also, find a list of C Pro­gram­ming Inter­view Ques­tions and answers with pro­gram­ming exam­ples for begin­ners and pro­fes­sion­als.

Data Structure Interview Questions:

    1. Describe Data Struc­ture.
    2. Explain how does a lin­ear data struc­ture dif­fers from a non-lin­ear data struc­ture?
    3. Tell us about var­i­ous oper­a­tions per­formed on the dif­fer­ent data struc­tures.
    4. Dis­cuss how array varies from a linked list.
    5. Dis­cuss the appli­ca­tion of Stack.
    6. How does a POP oper­a­tion dif­fer from a PUSH oper­a­tion?
    7. What is the basic dif­fer­ence between NULL and VOID?
    8. What is a queue and how is it dif­fer­ent from the stack?
    9. How does a vari­able dec­la­ra­tion affect mem­o­ry allo­ca­tion?
    10. Describe the types of linked lists.
    11. Dis­cuss in detail about Bina­ry Trees.
    12. How is a new item insert­ed in a bina­ry search tree?
    13. List the types of trees.
    14. Which Data Struc­ture suits most in tree con­struc­tion?
    15. What are the advan­tages of Heap over Stack?
    16. What is Data Abstrac­tion?
    17. How does a selec­tion sort work for an array?
    18. How do signed and unsigned num­bers affect mem­o­ry?
    19. What are the dynam­ic data struc­tures?
    20. What is a graph?
    21. Describe an AVL tree.
    22. How do you search for a tar­get key in a linked list?
    23. What are the dif­fer­ent Sort tech­niques in Data Struc­tures?
    24. What is the dif­fer­ence between File Struc­ture & Stor­age Struc­ture?
    25. Which Data Struc­ture is used in RDBMS, Net­work Data Mod­el, Hier­ar­chi­cal Data Struc­ture?

Data Structure Interview Questions and Answers: 

The answers here will boost your prepa­ra­tion in addi­tion to pro­vid­ing an overview.

1. Describe Data Structure?

Data Struc­ture is a process to orga­nize and manip­u­late data. In addi­tion to this, it also describes the rela­tion­ship between them. Fur­ther­more, it is a cen­tral part of many com­put­er sci­ence algo­rithms as pro­gram­mers find it easy to han­dle data in an effi­cient way.

2. Explain how does a linear data structure differs from a non-linear data structure?

If the ele­ments of a data struc­ture form a sequence or a lin­ear list then it is called a lin­ear data struc­ture. On the oth­er hand, non-lin­ear data struc­tures are those in which the tra­ver­sal of nodes is done in a non-lin­ear way.

Arrays, linked lists, stacks, and queues are exam­ples of lin­ear data struc­tures, while graphs and trees are those of non-lin­ear data struc­tures.

3. Tell us about various operations performed on different data structures?

The fol­low­ing oper­a­tions are per­formed on dif­fer­ent data struc­tures.

Inser­tion

Dele­tion

Tra­ver­sal

Search­ing

Sort­ing

Inser­tion is used to add a new data item where­as dele­tion is used to delete exist­ing data from a giv­en set. Sim­i­lar­ly, tra­ver­sal is used to access each data. More­over, search­ing is used to find out the loca­tion of an exist­ing data item in the set where­as sort­ing is used to arrange data in some order for its prop­er orga­ni­za­tion and usage.

4. Discuss how array varies from a linked list?

The array has a fixed size where­as the linked list varies in size. More­over, arrays have bet­ter cache local­i­ty which makes a big dif­fer­ence in per­for­mance. In fact, linked lists don’t allow ran­dom access. How­ev­er, one can eas­i­ly per­form inser­tion and dele­tion on a linked list where­as it is dif­fi­cult in an array.

5. Discuss the application of Stack?

A stack is a lin­ear data struc­ture based on order LIFO (Last In First Out) or FILO (First In Last Out).

The basic oper­a­tions car­ried out on Stack are Push, Pop & Peek.

Appli­ca­tion of Stack:

a. Infix to post­fix con­ver­sion.

b. Reverse a String.

c. Imple­ment two stacks an array

d. Check for bal­anced paren­the­ses in an expres­sion

6. How does a POP operation differ from a PUSH operation?

Both PUSH and POP oper­a­tions con­cern a stack. Data is added to the stack using the PUSH oper­a­tion, while it is recov­ered using the POP oper­a­tion.

7. What is the basic difference between NULL and VOID?

While NULL is a val­ue, VOID is a type of data iden­ti­fi­er. A vari­able assigned with a NULL val­ue rep­re­sents an emp­ty val­ue. The VOID is used for iden­ti­fy­ing point­ers that have no ini­tial size.

8. What is a queue and how is it different from the stack?

A queue is a kind of lin­ear struc­ture that fol­lows the First In First Out approach for locat­ing ele­ments. Dequeue, enqueue, front, and rear are basic oper­a­tions on a queue. Like a stack, a queue can be imple­ment­ed using arrays and linked lists.

How­ev­er, in a stack, the item that is most recent­ly added is elim­i­nat­ed first. Con­trary to this, the item least recent­ly added is elim­i­nat­ed first in case of a queue.

9. How does a variable declaration affect memory allocation?

The total amount of mem­o­ry to be allo­cat­ed in the case of a vari­able dec­la­ra­tion depends sole­ly on the data type used. For instance, declar­ing an inte­ger type vari­able reserves 4 bytes of mem­o­ry space while declar­ing a dou­ble vari­able saves 8 bytes of the avail­able mem­o­ry.

10. Describe the types of linked lists?

The linked list is a lin­ear data struc­ture where every ele­ment is a sep­a­rate object.

You may also like to watch the com­plete video on Data Struc­ture Inter­view Ques­tions:

Linked list Types:

a. Sin­gle linked lists:

Every node stores address or ref­er­ence of the next node in the list. Sim­i­lar­ly, the last node has the next address or ref­er­ence.

b. Dou­bly linked lists

There are two ref­er­ences asso­ci­at­ed with each node. One ref­er­ence points to the next node where­as the oth­er one points to the pre­vi­ous one.

c. Cir­cu­lar linked lists

Here all nodes are con­nect­ed to form a cir­cle. In fact, there is no NULL at the end. egs: 1->2->3->1 [The next point­er of the last node is point­ing to the first].

Relat­ed Post: Top 25 SQL Inter­view Ques­tions That You Must Pre­pare

11. Discuss in detail about Binary Trees?

It is a finite set of ele­ments that is either emp­ty or fur­ther divid­ed into sub-trees. In oth­er words, it is also called a non-lin­ear data struc­ture. One can call the child node on left as ‘left child node’ where­as the child node on right as ‘right child node’.

There are three types of Bina­ry Trees:

a. Full bina­ry tree

b. Com­plete bina­ry tree

c. Thread­ed bina­ry tree

12. How is a new item inserted in a binary search tree?

Since a bina­ry search tree does not allow dupli­ca­tion, the new item to be insert­ed must be unique. Then we will pro­ceed with check­ing whether the tree is emp­ty or not. If it is emp­ty, then the new item will be insert­ed in the root node.

How­ev­er, if the tree is not emp­ty, we will refer to the key of the new item. When it is small­er than the root item’s key, the new item will be added to the left sub­tree. If the new item’s key is greater than the root item’s key, then the new item is insert­ed into the right sub­tree.

13. List the types of trees?

Giv­en below is the list of the types of trees:

a. Gen­er­al Tree

b. Bina­ry Tree

c. Bina­ry Search Tree

d. Expres­sion Tree

14. Which Data Structure suits most in tree construction?

Queue data struc­ture suits most in tree con­struc­tion

15. What are the advantages of Heap over Stack?

Heap is more flex­i­ble than stack. Fur­ther­more, it is durable than the stack. How­ev­er, Stack allo­cates mem­o­ry very fast than the heap. There is a dynam­ic allo­ca­tion of mem­o­ry for the heap.

16. What is Data Abstraction?

Data abstrac­tion is a process to break down com­plex data prob­lems into man­age­able chunks. This helps in bet­ter oper­a­tion and stor­age of data.

17. How does a selection sort work for an array?

Here, sub­script zero con­tains the small­est ele­ment. In oth­er words, the small­est ele­ment gets the first posi­tion. Sim­i­lar­ly, the sec­ond small­est ele­ments get the sec­ond posi­tion and so on.

18. How do signed and unsigned numbers affect memory?

A signed 8‑bit num­ber has a range of (0–255) where­as an unsigned 8‑bit num­ber has a range of ‑128 to 127. Sim­i­lar­ly, the Unsigned 8‑bit num­ber has all the bits avail­able.

19. What are the dynamic data structures?

When a pro­gram runs, the dynam­ic data struc­tures expand and con­tract. In oth­er words, it can adjust as per the size of the data.

20. What is a graph?

A graph is a non-lin­ear data struc­ture that con­tains nodes and edges.

Graphs are used to rep­re­sent net­works which include path in a city or tele­phone net­works, etc. Sim­i­lar­ly, they are used in social net­works like Linked In, Face­book or Twit­ter, etc.

21. Describe an AVL tree?

AVL tree is used to bal­ance the exist­ing bina­ry search tree. In fact, it is always in a par­tial­ly bal­anced state.

22. How do you search for a target key in a linked list?

You can search for a tar­get key using a sequen­tial search in a linked list. First­ly, each node is tra­versed and com­pared with the tar­get key. Then, the dif­fer­ent one fol­lows the link to the next node.

23. What are the different Sort techniques in Data Structures?

The dif­fer­ent types of sort tech­niques in data struc­tures are list­ed below:

a. Buble sort

b. Selec­tion sort

c. Merge sort

d. Inser­tion sort

e. Quick­sort

f. Heap­sort

Data Structure Interview Questions and Answers on Files and Databases:

24. What is the difference between File Structure & Storage Structure?

File Struc­ture:

If you write a data in the file and save that file in the hard disk or any oth­er exter­nal device, the data will remain intact until it is delet­ed man­u­al­ly. To sum up, this act of sav­ing data in a file on an aux­il­iary mem­o­ry is called a file struc­ture.

Stor­age Struc­ture:

Every vari­able and con­stants have mem­o­ry allo­cat­ed in the main mem­o­ry called a stor­age struc­ture.

25. Which Data Structure is used in RDBMS, Network Data Model, Hierarchical Data Structure?

RDBMS uses an array data struc­ture where­as Net­work Data Mod­el uses graph and Hier­ar­chi­cal Data Struc­ture uses tree data struc­tures.

Data Struc­ture is the most impor­tant top­ic in com­put­er sci­ence. Almost all the prod­uct based com­pa­nies that pay you a high­er salary expect you to be pro­fi­cient in it. To sum up, you have to give more time.

In fact, a data struc­ture is the foun­da­tion of every pro­gram­ming lan­guage and soft­ware, as well as, hard­ware. Hence, if you can mas­ter it, crack­ing the data struc­ture inter­view will be a piece of cake.

Relat­ed Post: Man­u­al Test­ing Inter­view Ques­tions for Fresh­ers & Expe­ri­enced

Vikash Kumar Jha is a computer science graduate. He is interested in researching, reading, and writing on topics related to career & job search.