| SORTING | BEST CASE | AVERAGE CASE | WORST CASE |
| Insertion Sort | O(n) | O(n2) | O(n2) |
| Bubble Sort | O(n) | O(n2) | O(n2) |
| Selection Sort | O(n2) | O(n2) | O(n2) |
| Quick Sort | O(n log n) | O(n log n) | O(n2) |
| Merge Sort | O(n log n) typically , O(n) | O(n log n) | O(n log n) |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) |
| Radix Sort | O(kn) | O(kn) | O(kn) |
| Counting Sort | O(n+k) | O(n+k) | O(n+k) |
Here I post some of the placement questions. These are very simple..
Question 1 : Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ... shows the first 11 ugly numbers. By convention, 1 is included. Write a program to find and print the 1500'th ugly number.
Question 2 : int main()
{
int i, n = 20;
for (i = 0; i < n; i--)
printf("*");
return 0;
}
Change/add only one character and print '*' exactly 20 times.
(there are atleast 3 solutions to this problem)Question 3 : You are provided with two stacks, and pop() and push() functions for them. You have to implement queue i.e. enqueue() and dequeue() using the available operations.
Question 4 : How do you reverse the words in a string? "My name is Ajit Agarwal" to "Agarwal Ajit is name My" A O(n) and 'in space' solution is appreciable.
Question 5 : Given an array of numbers, except for one number all the others, occur twice. Give an algorithm to find that number which occurs only once in the array.
Question 6 : There is a series of numbers in ascending order. All these numbers have the same number of binary 1s in them. Given the number of 1 bits set in the numbers, write an algorithm/C program to find the nth number in the series.
Question 7 : Given a string s1 and a string s2, write a snippet to say whether s2 is a rotation of s1 using only one call to strstr routine? (eg given s1 = ABCD and s2 = CDAB, return true, given s1 = ABCD, and s2 = ACBD , return false)
Question 8 :
What's the "condition" so that the following code
snippet prints both HelloWorld !
if "condition"
printf ("Hello");
else
printf("World");
1. Given two trees, return true if they are
structurally identical.
int sameTree(struct node* a, struct node* b) {
// 1. both empty -> true
if (a==NULL && b==NULL) return(true);
// 2. both non-empty -> compare them
else if (a!=NULL && b!=NULL) {
return(
a->data == b->data &&
sameTree(a->left, b->left) &&
sameTree(a->right, b->right)
);
}
// 3. one empty, one not -> false
else return(false);
}
2. code to count number of leaves in the tree
void count_leaf(mynode *root)
{
if(root!=NULL)
{
count_leaf(root->left);
if(root->left == NULL && root->right==NULL)
{
// This is a leaf!
count++;
}
count_leaf(root->right);
}
}
3. code to create copy of tree
mynode *copy(mynode *root)
{
mynode *temp;
if(root==NULL)return(NULL);
temp = (mynode *) malloc(sizeof(mynode));
temp->value = root->value;
temp->left = copy(root->left);
temp->right = copy(root->right);
return(temp);
}
4. code to create mirror copy of tree
mynode *copy(mynode *root)
{
mynode *temp;
if(root==NULL)return(NULL);
temp = (mynode *) malloc(sizeof(mynode));
temp->value = root->value;
temp->left = copy(root->right);
temp->right = copy(root->left);
return(temp);
}
5. Implementing level order traversal of a tree
If this is the tree,
1
2 3
5 6 7 8
its level order traversal would be
1 2 3 5 6 7 8
void levelOrderTraversal(mynode *root)
{
mynode *queue[100] = {(mynode *)0}; // Important to initialize!
int size = 0;
int queue_pointer = 0;
while(root)
{
printf("[%d] ", root->value);
if(root->left)
{
queue[size++] = root->left;
}
if(root->right)
{
queue[size++] = root->right;
}
root = queue[queue_pointer++];
}
}