Algorithms & Coding Questions & Answers
1、Write a function to print the Fibonacci numbers.
-- int fib ( int n ){
if (n == 0) return 1;
else return fib(n-1) + fib(n-2);
}
-- int fibo (int n)
{
int i, current, one_back, two_back;
if (n <= 1)
return 1;
else {
one_back = 1;
two_back = 1;
for ( i = 2; i <= n; i++) {
current = one_back + two_back;
one_back = two_back;
two_back = current;
} /* end for loop */
} /* end else block */
return current;
}
-- There are better ways to find a solution to this problem instead of using Recursion. Recursion is a disaster as someone has already mentioned. Try giving 20 or more elements in your series and your program will take awful lot of time to compute. For every element in series you're finding the element before using recursion though you theoretically you would have computed it before!!!
2．Give a one-line C expression to test whether a number is a power of 2. Now implement it without using loops.
-- if (x > 0 && (x & (x-1)) == 0)
-- I think all the answers here are either wrong completely, partially, or too complex. The best answer so far, by jinaljhaveri, was if(!(x&(x-1))), which I believe works for all powers of 2, but also for 0, which is not a power of 2.
Basically, an integer which is the power of 2 will have one and only one bit set in its binary representation. If you subtract 1 from that, you will get all bits set (equal to 1) before the original 1 bit, and the rest are 0. Taking advantage of this, the answer is
if ((x << 1) == 1 + (x | (x - 1))) {}
The term x | (x - 1) makes an integer with all bits set starting from the original set bit. Adding 1 will set the next bit and clear all the previous bits, effectively doubling x, which is the same as x << 1.
It’s a pity that the second solutions work for 0 too, which is just what he/she wants to avoid.
3．Implement an algorithm to sort a linked list.
直接插入排序、直接选择排序、归并排序。
如果可以使用的额外的内存空间，会比较的简单；否则，则需要一点思考了。
4．Reverse a string.
void str_rev(char s[])
{
int len = strlen(s);
int i;
char temp;
for(i=0; i<len/2; i++)
{
temp = s[i];
s[i] = s[(len-1) - i];
s[(len-1) - i] = temp;
}
}
5．Given a linked list which is sorted, how will you insert in sorted way.
U have already very familiar with it if you did question 3 (sort a linked list) by direct insertion sort.
6．Implement an algorithm to insert in a sorted list.
7．Delete an element from a doubly linked list.
void deleteNode(node *n)
{
node *np = n->prev;
node *nn = n->next;
np->next = n->next;
nn->prev = n->prev;
delete n;
}
8．Implement an algorithm to sort an array.
An array can be sorted using any of the classic algorithms like quicksort , heapsort and the inefficient bubblesort.
9．Given a sequence of characters, how will you convert the lower case characters to upper case characters?
void ToUpper(char * S)
{
while (*S!=0)
{
*S=(*S>='a' && *S<='z')?(*S-'a'+'A'):*S;
S++;
}
}
10．Write a routine that prints out a 2-D array in spiral order.
int NumbersPerTime = SIZE; // 绕圈的边长
int tInit = 0; // 绕圈的起始值
for(int i = 0 ; i < (SIZE+1)/2; i++)
{
int t = tInit;
for(int j = 0; j < NumbersPerTime-1; j++)
{
// out here
printData(t);
t += SIZE;
}
for(j = 0; j < NumbersPerTime-1; j++)
{
// out here
printData(t);
t += 1;
}
for(j = 0; j < NumbersPerTime-1; j++)
{
// out here
printData(t);
t -= SIZE;
}
for(j = 0; j < NumbersPerTime-1; j++)
{
// out here
printData(t);
t -= 1;
}
NumbersPerTime -= 2;
tInit += SIZE + 1;
}
11．Give a fast way to multiply a number by 7.
int num = (n<<3) – n;
12．Write a function that takes in a string parameter and checks to see whether or not it is an integer, and if it is then return the integer value.
int str2int(const char *str)
{
int value = 0;
int sign = (str[0] == '-')?-1:1;
int i = (str[0] == '-')?1:0;
char ch;
while(ch = str[i++])
{
if ((ch >= '0')&&(ch <= '9'))
value = value*10 + (ch - '0');
else
return 0; // return 0 denotes error occurs
}
return value*sign;
}
13．How would you print out the data in a binary tree, level by level, starting at the top?
1) Put the root node into a queue;
2) while the queue is not empty, do as follows;
3) Get a node from the queue, print its value, and put its children into the queue;
14．Write a routine to draw a circle given a center coordinate (x, y) and a radius (r) without making use of any floating point computations.
In order to avoid floating point calculations, we can do two things:
1) Instead of fixing one co-ordinate and looking for another via the equation, search the whole co-ordinate space from x +- r and y +- r. Plot the point that is close. But this is a costly N*N algo.
2) To go for an efficient workhorse, go for Bresenham's circle drawing algo, found in any of the good graphics textbooks.
15．You are given two strings: S1 and S2. Delete from S2 all those characters which occur in S1 also and create a clean S2 with the relevant characters deleted.
#include<stdio.h>
#include<string.h>
main() {
char str1[5] = "abcd";
char str2[3] = "bc";
int len = strlen(str1);
int i =0;
char newstr[len];
int cntr = 0;
for ( i = 0; i<len; i++ ) {
if ( strchr(str2,str1[i]) == NULL ) {
newstr[cntr++] = str1[i];
}
}
newstr[cntr] = '\0';
printf("%s%s%s", "The new str is ", newstr, "\n");
}
16．Write a small lexical analyzer for expressions like "a*b" etc.
bool is_astarb(char* s)
{
if (*s++ != 'a') return false;
while(*s++);
if (*--s != 'b') return false;
return true;
}
17．Given an array t[100] which contains numbers between 1 and 99. Return the duplicated value. Try both O(n) and O(n-square).
-- Traverse array to compute sum, subtract 99*100/2, the sum of integers between 1 and 99.
-- Create a new array of b[100], elements initialized all to 0
int b[100];
for ( i=0;i<100;i++)
b[i]=0;
int tm;
for ( i=0;i<100;i++)
{
tm=t[i] ;
if b[tm]== 1;
return(tm); // return the duplicate number
else b[tm]=1;
}
printf(" there is no duplication");
return 0; // 0 indicates no duplication
O(n square ) ... just sort all numbers and check if two consecutive numbers are same by traversing the sorted array..
18．Write efficient code for extracting unique elements from a sorted list of array.
#include <stdio.h>
main()
{
int a[10] = {0,4,4,4,5,6,6,8,9,9};
int i;
for(i=0; i<10; i++)
{
if(a[i] == a[i+1] )
{
while(a[i] == a[i+1]) i++;
}
else
printf("%d ", a[i]);
}
printf("\n");
}
We do print the ununiqued numbers out, but we do not extract them!
19．Print an integer using only putchar. Try doing it without using extra storage.
1) void printInt(int a);
int b = a;
char *str;
int i = 1;
int len = 0;
while (b) {
b /= 10;
i *= 10;
len++;
}
i /= 10;
while (i > 0) {
putchar(a/i + 48);
a = a%i;
i /= 10;
}
}
2) This can be done by recursion. Since the number of recursive calls is not significant, it does not affect the performance much.
printnumber(int i)
{
if(i == 0)
return;
printnumber(i/10);
putchar('0' + i%10);
}
20．Write a function that allocates memory for a two-dimensional array of given size(parameter x & y)
--array=(int**)malloc(x*sizeof(int*));
for(i=0;i<y;i++)
array[i]=(int*)malloc(y*sizeof(int));
--I prefer this method because it uses less memory allocation calls and the memory is in a contiguous line. I used calloc.. which can easily be swaped out with malloc. Also, this makes a 2d array of integers but that is easily changed as well.
int x = 0, y = 0;
Array = (int **) calloc( Height, sizeof(int *));
*(Array) = (int *) calloc( Width * Height, sizeof(int));
for(y = 0; y < Height; y++)
{
Array[y] = &(Array[0][x]);
x += Width;
}
21．How would you do conditional compilation ?
#ifdef/ifndef
#else/elif
#endif
#pragma token-string // provide compiler or machine specific instructions and arguments
22．Write an algorithm to draw a 3D pie chart ?
23．Write a function that finds repeating characters in a string.
Maintain a character count table like -- int char_count[255];
//Initialize to 0 here
Keep adding the count of each characters.
Scan throughout the array and print the characters with count more than 1.
24．Write a routine to reverse a series of numbers without using an array.
-- int reverse(int i)
{
int rev=0, x=0;
if((i /10) ==0)
return i;
while((i /10) >0)
{
x = i %10;
i= i/10;
rev= (rev *10) +x;
}
rev= rev*10 +i;
return rev;
}
-- # include <iostream.h>
void main()
{
int i = 12345, y =0;
while(i !=0)
{
y = y *10 + i %10;
i /=10;
}
cout<<y;
}
25．Write a function to find the nth item from the end of a linked list in a single pass.
I would think keeping a gap is "n" between fptr and sptr would do. Then advance both together till fptr->next (fptr is the one in front) = NULL, the sptr is what we want.
26．Write a function to compute the factorial of a given integer.
27．Give me an algorithm for telling me the number I didn't give you in a given range of numbers. (Numbers are given at random)
1. say the range of numbers is 0 to n-1
2. Initialize an array say, seen[n] to 0
3. for every number i given set seen[i] to 1.
4. in the end, print all indices for which seen[index] = 0
28．Write a function that finds the last instance of a character in a string.
main() {
char *x= "acbcd";
char y = 'c';
int len = strlen(x);
int i=0,j=0;
for( i = len-1; i>= 0; i-- ) {
if ( x[i] == y ) {
break;
}
}
printf("%s%c%s%d%s","the # of last occur of ",y," is ",i+1,"\n");
}
