programming interview questions 1

programming interview questions

Problem 1 Write an efficient C function f to count the number of bits set in an unsigned integer. For example: f(0) = 0, f(1) = 1, f(2) = 1, f(3) = 2.

Problem 2 Write a small C program, which while compiling takes another program from input terminal, and on running gives the result for the second program. (Hint: Think UNIX.) Suppose the program is 1.c; then compiling and executing the program should have the following effect:

# cc -o 1 1 .c

int main()

{ printf("Hello World\n");

}

^D

# ./1

Hello World

Problem 3 Given strings s1 and s2, write a snippet to say whether s2 is a rotation of s1 using only one call to the strstr function. For example, given s1 = "ABCD" and s2 = "CDAB", return true; given s1 = "ABCD", and s2 = "ACBD", return false.

Problem 4 What should be the <condition> so that the following code snippet prints ”HelloWorld”?

if(<condition>)

printf ( "Hello"); else

printf("World");

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

[Note: These numbers are also known as “Hamming numbers” or 5-smooth numbers.]

Problem 6 Write a C program which when compiled and run, prints out a message indicating whether the compiler that it is compiled with allows /* */ comments to nest.

Problem 7 Write a C function that will take an int parameter n and print on stdout numbers 1 to n, one per line. The function must not use while, for, do-while loops, goto statement, recursion, or switch statement.

Problem 8 Change/add only one character so that the following program prints * exactly

20 times. (There are atleast 3 solutions to this problem.)

int main()

{

int i, n = 20 ; for (i = 0; i < n; i--) printf("*");

return 0 ;

}

Problem 9 You are given have a datatype, say X in C. Determine the size of the datatype, without declaring a variable or a pointer variable of that type, and, of course without using the sizeof operator!

Problem 10 Find the midpoint of a singly-linked list in a single pass through the list. Changing the list elements or links is not allowed.

Problem 11 Given a circular singly-linked list of sufficiently large number of nodes ( say more than 1), delete the node P given the pointer to it. Suggest the most efficient algorithm to delete the node, without going around the list.

Problem 12 Write a C Program to reverse a stack in place using recursion. You can only use the following ADT functions on stack: IsEmpty, IsFull, Push, Pop, Top.

Problem 13 You are provided with two stacks, as well as Pop and Push functions over them. Implement queue i.e. Enqueue and Dequeue using the available operations.

Problem 14 Describe an algorithm for reversing the words in a string; for example ”My name is Amit Agarwal” becomes ”Agarwal Amit is name My”. An O(n) and in-place solution is appreciable.

Problem 15 You are given a sequence of numbers from 1 to n−1 with one of the numbers repeating only once; e.g. 1 2 3 3 4 5.

•    How can you find the repeating number?

•    What if given the constraint that you can use only a fixed amount of memory ( i.e. independent of n) ?

•    What if there are two repeating numbers instead of one (with the same memory constraint)?

[Note: The problem is a bit vague. I think that the sequence should contain n numbers in range [1,n − 1], and that it is not sorted in the general case (the example could be

misleading).]

Problem 16 In an integer array all numbers occur exactly twice, except for a single number which occurs exactly once. Give an O(n) algorithm to find the number occuring only once.

Problem 17 There is a sequence of increasing numbers that have the same number of binary 1s in them. Given n, the number of 1 bits set in each number, write an algorithm or C program to find the n’th number in the series.

Problem 18 Given a stack S, write a C program to sort the stack (in ascending order). You are not allowed to make any assumptions about how the stack is implemented; the only functions allowed to be used are: Push, Pop, Top, IsEmpty, IsFull.

Problem 19 Given a singly-linked list and an integer n, find the n’th element from the end of the list.

Problem 20 The numbers are represented with linked-list where each node represents a digit; for example: 123 = 1 → 2 → 3 → ∅, 999 = 9 → 9 → 9 → ∅ (where ∅ denotes the

NULL pointer).

Write a C program to add two numbers; e.g. 9 → 9 → 9 →∅ + 1 →∅ = 1 → 0 → 0 → 0 →∅

Problem 21 There is a 100-story building and you are given two eggs. The eggs have an interesting property that if you throw the egg from a floor number < x, it will not break, and it will always break if the floor number is ≥ x. Assuming that you can reuse the eggs which didn’t broke, give an algorithm to find x in minimal number of throws.

Problem 22 You are given a singly link-list such that each node of this list is also a head of another link list of the same type:

struct node {

void *data; /* could be anything */ struct node *next; struct node *down;

} ;

Describe an algorithm for flattening the list.

Problem 23 Given two unsorted singly-linked lists, find the most efficient way to make a single sorted list.

24 Given numbers x and n, where n is a power of 2, write (in C) a function f(x,n) which gives the [least] multiple of n that is greater than or equal to x. For example:

f(13, 8) == 16, f(17,16) == 32.

For “bonus points”: do not use division or modulo operator.

Problem 25 In C, copying of array as follows is not possible:

int a[10],b[10];

a = b;

a = GetAnArrayOfTenElements();

Can you think of a simple hack, which would enable you to get this effect?