Data Structure Interview Questions


Question 1:

What are the five important features of an algorithm?

Some of the important features of algorithm are -

  1. Finiteness
  2. Definiteness
  3. Input
  4. Output
  5. Effectiveness
Question 2:

In a linked list with n nodes, the time taken to insert an element after an element pointed by some pointer will be ?  

In a linked list with n nodes, the time taken to insert an element after an element pointed by some pointer will be O(1).

Question 3:

Anagrams are words that are composed of the same letters; for example, the words “eat,” “ate,” and “tea” are anagrams. Devise an algorithm to find all sets of anagrams in a large file of English words.

An efficient algorithm for this problem works in two stages. First, it assigns each word a "signature" obtained by sorting its letters and then sorts the file in alphabetical order of the signatures to put anagrams next to each other.

Question 4:

What do you understand by constant space complexity?

Constant space complexity means that the amount of space that your algorithm uses is independent of the input provided. 

For example:- If the size of input is 1000 and the space required by algorithm gets increased if the size of input is increased then space complexity of the algorithm is not constant. 

Constant space complexity is denoted as O(1).

Question 5:

What is abstract data type?

An abstract data type, also known as ADT, is a logical description for data types where data type is defined by its behaviour rather than its implementation.

For example:

Stack: Operations that are performed on stack are -  "push an item onto the stack", "pop an item from the stack", "check if the stack is empty"; implementation may be as array or linked list or user defined.


Question 6:

How 
can
 you
 determine
 whether
 a
 number
 is 
a
 power
 of 
2 efficiently?

Check
 whether 
x
 & (x
‐
1) 
is 
0.

 If
 x 
is
 not
 an 
even
 power
 of
 2,
 the
 highest 
position 
of 
x
 with 
a
 1
 will 
also 
have
 a
 1 
in
 x
‐
1;
 otherwise,
 x
 will 
be
 100...0
 and
 x
‐
1
 will 
be 
011...1; 
and'ing
 them 
together 
will
 return 
0.

Source -  http://courses.csail.mit.edu/iap/interview/Hacking_a_Google_Interview_Handout_3.pdf

Question 7:

What is the difference between null pointer and void pointer?

Null Pointer: Null Pointer is a special value of any pointer type. For example: each pointer type like int *, char * , has its own null-pointer value. If any pointer has null value it means that it is pointing nowhere.

Void Pointer: Void Pointer is a special type of pointer which point to some data/value but that data/value has no type.

For example:

void * data = NULL

Question 8:

What are the advantages of linked list over an array?

Size: As we all know the size of an array is fixed. Hence you cannot increase the size of array at runtime whereas if you are using linked list you can increase its size at runtime.

Insertion of Element: If you insert any element between array elements you have to shift all the elements and create the space for current element whereas using linked list you just need to point the current element by previous element and current element should point to next element.

Question 9:

Given an array integer which comprises of numbers 1 to 100, with one duplicate number. How will you find the duplicate number in array?

As we know sum of n natural numbers = n(n+1)/2

Hence first calculate the sum of given numbers and then subtract the sum  of n natural numbers from it. You will get the dulicate number in an array.

Question 10:

How to find the middle element of a linked list in one pass?

You can find the middle element of Linked list in one pass using below-mentioned logic:

For this you have to maintain two pointers lets say first and second. At the time of iteration increment the first pointer each time while increment the second pointer in every second iteration. When the first pointer reaches till end of the list, the second pointer will be pointing to the middle of the linked list.

For example: Given linked list has 5 elements as shown and we have first and second pointer. First pointer increments after each pass whereas second pointer increments after every second pass. When the first pointer reach to end of linked list, second pointer reach to middle of linked list.

Find Middle Element of List

Share interview questions

Comments

Comments
comments powered by Disqus

Navigation

Social Media