# Interview Questions 9

August 3, 2010 Leave a comment

Some of the more recent programming problems asked in interviews. Enjoi 🙂

1. How to find two vertices of a polygon which are farthest from each other in linear time.

2. Given a string find the number of distinct substrings of the string.

ex:

input-> aaaa

output-> 4(a, aa, aaa, aaaa)

input->abcd

output->10(a, b, c, d, ab, bc, cd, abc, bcd, abcd)

3. Suppose you a have function which returns a word char* GetWord() from a document. Write a data structure which holds the words in the most efficient way. If the words are repeated, find the number of repeated words.

a)What data structure you used?

b) What algorithm you implemented?

c) What is the time complexity of the algorithm?

4. Find the maximum subsequence sum in a linked list. Consider the node as shown below.This node class has a extra item isvertex which determines whether the node is a vertex r not.

so find the longest distance between any 2 vertex in the linked list.

Node SLL{

int data;

Node n;

bool isVertex;

}

5. Given a singly linked list sorted in ascending order, convert it to a height balanced BST from this.

6. Given a text file, implement a solution to find out if a pattern similar to wild cards can be detected. Ex. find if a*b*cd*, or *win or *def* exists in the text.

7. Which is the best data structure to hold multiple keys for multiple objects i.e. each object have multiple keys.

8. Given a number line 1734, how to return the next higher permutation of its digits.

9. Sort the input array. Only following operations on array is allowed:

1)get(index) -gets the element at that index

2)reverse(int start,int end) – example reverse(1,3) for the array [1,2,3,4,5] will return [1,4,3,2,5]

10. Given a large set of balls say N such that these balls are identical if they are of the same color. We have to randomly pick one of the balls such that the probability of picking is the same. Find an efficient way of solving this in terms of space and running time complexity.

## Recent Activity