More than a Pathshala

What are the five important features of an algorithm?

Some of the important features of algorithm are -

- Finiteness
- Definiteness
- Input
- Output
- Effectiveness

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).

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.

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)`

.

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.

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

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 `

has its own null-pointer value. If any pointer has null value it means that it is pointing nowhere.**, *char * ,

**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`

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.

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.

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.

Share interview questions

Comments