More than a Pathshala
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 *, 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
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.
What is best case, average case and worst case time complexity of binary search algorithm?
The best case, average case and worst case time complexity of binary search is listed below:
Best Case | Average Case | Worst Case | |
Binary Search | O(1) | O(logn) | O(logn) |
What is binary search tree?
Binary Search Tree is a binary tree which has the holds properties:
For example:
How many nodes does a perfect binary tree of level n has?
A perfect binary tree of level n has 2^{n+1} - 1 nodes.