Question: we have an array of 2n elements like "a1 a2...an b1 b2...bn". WAP to rearrange the array as "a1 b1 a2 b2...an bn"
time complexity is O(n) no extra array or memory can be taken...
Answer:
I have an answer but could not meet the complexity requirement.
C code:
Enter no of elements (max 100): 12
Enter numbers:
1 2 3 4 5 6 7 8 9 10 11 12
1 2 3 4 5 6 7 8 9 10 11 12
1 7 2 8 3 9 4 10 5 11 6 12
Output with intermediate steps:
Enter no of elements (max 100): 12
Enter numbers:
1 2 3 4 5 6 7 8 9 10 11 12
1 2 3 4 5 6 7 8 9 10 11 12
1 7 8 9 10 11 2 3 4 5 6 12
1 7 2 3 4 5 8 9 10 11 6 12
1 7 2 8 9 10 3 4 5 11 6 12
1 7 2 8 3 4 9 10 5 11 6 12
1 7 2 8 3 9 4 10 5 11 6 12
1 7 2 8 3 9 4 10 5 11 6 12
If you can suggest a better solution, please revert.
Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
Arranging sequence
Run-length encoding
Question: You are given a string like "aaaabbbcc", do an in place conversion which write frequency of each charater(which come continuosly) with that character. If character repeats only once don't write '1'.
#include<stdio.h>
#include<malloc.h>
#include<string.h>
char* strr;
char* itoax(int n)
{
char *temp;
int i;
strr = (char*)malloc(10*sizeof(char));
temp = strr;
for(i=n; i>0; i=i/10)
*strr++ = '0'+ i%10;
*strr = '\0';
temp = strrev(temp);
return temp;
}
void main()
{
char in[100], out[100] = {0};
char *countarr;
int i, j, len, count;
i=j=count=0;
printf("Enter string: ");
scanf("%s", in);
len = strlen(in);
out[i] = in[j];
count = 1;
for(i=1,j=1;i<len;i++,j++)
{
while(in[i] == in[i-1])
{
count ++;
i++;
}
if (count > 1)
{
countarr = itoax(count);
strcat(out,countarr);
j+=strlen(countarr);
count=1;
}
out[j] = in [i];
}
out[j] = '\0';
printf("\n%s\n",out);
}
Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
Kth Minimum element in a tree
#include<stdio.h>
#include<malloc.h>
struct treenode{
int data;
struct treenode * left;
struct treenode * right;
};
int no_of_nodes(struct treenode * node)
{
if(node == NULL)
return 0;
else
return(1 + no_of_nodes(node->left) + no_of_nodes(node->right));
}
int findkthmin(struct treenode * node, int k)
{
int no_nodes = no_of_nodes(node->left);
if (no_nodes == k-1)
return node->data;
if (no_nodes >= k)
return findkthmin(node->left,k);
else
return findkthmin(node->right, (k - no_nodes - 1));
}
void main()
{
struct treenode * tree;
int k, min;
tree = createtree(); /*create a BST*/
scanf("%d",&k);
if (no_of_nodes(tree) < k)
{
printf("Number of nodes in tree are less than %d \n",k);
return;
}
min = findkthmin(tree, k);
printf("kth min element = %d\n",min);
}
Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
HELP!!!
Dear Readers,
I need help of all of you. I have some more post drafted and ready to be posted. But the problem is that those posts have a lot of code and when I try to publish those blogger gives error or certain syntax of that code.
Please help me by providing a way to publish C/C++ code without lose of data.
One of the example is in my post of array sorting. There in my code when I tried to
So guys, please help me.
Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
Optimization
In most interviews, they ask questions to optimize your code. For example many times they ask to have a better way to multiply by 7. Answer is to right shift the number by 2,1 and 0 bits and add these results.
The question is that modern age compiler are so efficient that these things are taken care by compiler itself. Below is something I found in a linkedin forum about optimization by Alex Oren, Sr. Software Developer at a privately held software development company.
Some things to consider, in arbitrary order:
1. Optimizers have gotten pretty clever. Manual techniques that were considered code good optimizations a decade or two ago have been rendered obsolete and serve just to obfuscate code.
For example, dividing a variable by a constant power of two. If you look at the assembly emitted with optimizations turned on, you'll see that the compiler uses a (faster) right shift instead of a division.
2. Advances in processors cause some "common sense" techniques to become "pessimizations", as they may hinder code reordering, vectorization, branch prediction, etc., cause cache misses (or worse, page faults) and other performance-killing issues. Remember, you can no longer just count cycles as you could in the '70s.
In short, 99% of the time the compiler will do a better job than you optimizing code.
3. Don't optimize unless you have a reason to believe that there is a performance problem. Define what execution speed is "good enough" and don't waste time on trying to find ways to make it even faster.
For example, if you can shorten the running time of a process from 8 hours to 5, it is a worthwhile endeavor. Find a clever way of trimming another 5 minutes would be inefficient use of *YOUR* time.
4. If you do have a performance problem, find exactly where it occurs and concentrate your efforts there.
For example, shaving milliseconds from tight loops is ridiculous if your program spends most of its time in database queries.
5. Algorithmic optimizations are much more effective than micro-optimizations. Choosing different algorithm or data structures is key.
for example, the most efficient bubble sort will fall hopelessly behind mediocre implementations of Heapsort or Merge Sort as the data set grows. For some cases, a Radix sort can similarly top Quicksort.
To summarize:
“More computing sins are committed in the name of efficiency (without necessarily achieving it) than for any other single reason - including blind stupidity.” -- W.A. Wulf
"Premature optimization is the root of all evil" -- Donald Knuth
Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
Sort an array containing '0' and '1'
It seems easy, sum all the elements in the array and then reset the array with those many '1's in the end and rest '0's in the beginning. Time complexity is also O(n) with constant space. So it seems the best and easy one.
But if you are OK with this, please read the question again - MINIMUM TIME, it doesn't mean the minimum complexity. In the above solutions you are having 2 passes, one for taking sum and another for setting the array.
This can be done in a single pass:
just start two pointers, ptr1 from starting of the array(I should say from -1) and ptr2 from end of the array(I should say from length of the array).
while ptr2>ptr1
increment ptr1
if (array[ptr1] == 0) continue;
else
decrement ptr2 until array[ptr2] == 1;
if(ptr2> ptr1)
swap array[ptr1] with array[ptr2]
C code:
#include <stdio.h>#define MAXSIZE 100#define SWAP(a,b) a^=b^=a^=bvoid main(){int array[MAXSIZE], i, j, len=-1;printf("Enter array of 0 and 1, enter -1 to discontinue: ");do{len++;scanf("%d",&array[len]);}while(array[len] != -1);i= 0;j = len;while(j>i){if(array[i] == 0){i++;continue;}while(array[--j] == 1);if(j>i)SWAP(array[i],array[j]);} }
Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
Why?
I am staring this blog to discuss all types software interview questions and puzzles.
The questions those will feature here will be mainly related to algorithms, data structures, puzzles and general software knowledge.
Currently I'm not planning to put any language specific stuff.
Code will be presented in C/C++. I appreciate if someone put code in other programming languages in comments.
At times, I may post the questions/solutions I found while googling or searching and found them worth sharing.
Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
Find us on Facebook
I write about
- Algorithm (31)
- Amazon EC2 (3)
- Amazon Interview (9)
- Amazon S3 (5)
- Amazon SimpleDB (5)
- Amazon SQS (1)
- Architecture (3)
- Arrays/Strings (32)
- backtracking (1)
- Brain Teasers (8)
- C++ (3)
- Cloud Computing (14)
- Design Pattern (2)
- Dynamic programming (11)
- Facebook Interview (3)
- General (14)
- Git (2)
- Google Interview (6)
- Humour (1)
- Interviews (7)
- Link List (8)
- Mac (2)
- Mathematics (3)
- MIcrosoft Interview (4)
- Miscellany (1)
- python (3)
- queue (1)
- Ruby (9)
- tree (19)
- web development (1)