Algorithms And Programming #6

51. An array of characters. Reverse the order of words in it.
ANS. Write a routine to reverse a character array. Now call it for the given array and for each word in it.

* 52. An array of integers of size n. Generate a random permutation of the array, given a function rand_n () that returns an integer between 1 and n, both inclusive, with equal probability. What is the expected time of your algorithm?

ANS. "Expected time" should ring a bell. To compute a random permutation, use the standard algo of scanning array from n downto 1, swapping i-th element with a uniformly random element <= i-th. To compute a uniformly random integer between 1 and k (k < n), call rand_n () repeatedly until it returns a value in the desired range.

53. An array of pointers to (very long) strings. Find pointers to the (lexicographically) smallest and largest strings.

ANS. Scan array in pairs. Remember largest-so-far and smallest so far. Compare the larger of the two strings in the current pair with largest-so-far to update it. And the smaller of the current pair with the smallest so far to update it. For a total of <= 3n/2 strcmp () calls. That's also the lower bound.

54. Write a program to remove duplicates from a sorted array.

ANS. int remove_duplicates (int * p, int size)
{
int current, insert = 1;
for (current=1; current < size; current++)
if (p [current] != p [insert-1])
{
p [insert] = p[current];
current++;
insert++;
} else
current++;
return insert;
}

55. C++ (what is virtual function? what happens if an error occurs in constructor or destructor. Discussion on error handling, templates, unique features of C++. What is different in C++, (compare with Unix).

56. Given a list of numbers (fixed list) Now given any other list, how can you efficiently find out if there is any element in the second list that is an element of the first list (fixed list).

57. Given 3 lines of assembly code: find it is doing. IT was to find absolute value.

58. If you are on a boat and you throw out a suitcase, Will the level of water increase?

59. Print an integer using only putchar. Try doing it without using extra storage.

60. Write C code for (a) deleting an element from a linked list (b) traversing a linked list

NEXT
BACk