Interview Questions 11

1. Given 10K of 16bit integers and unlimited memory, find most efficient algorithm that counts number of bits set to 1.

2. Print the pascal triangle. Don’t worry about formating.if i/p is 1 then print first line. if 2 then print 2 lines of triangle.see wiki about pascal triangle.

3. Print elements that are in a vertical column (per column) in a Binary tree

4. Given customer vs visited pages log for three days, find the customers who have visited for exactly 2 days and visited page count > 2. Customer can visit the same page any number of times.

5. How to represent a map of large nodes and edge in memory

6. Palindrome Date: A date is said to be a palindrome when it is expressed in MMDDYYYY format, it reads the same both ways. Given 2 years as input(ex: 2000, 2010), print out all the dates which are palindrome dates.

7. You are given a sets of words ,Write a C code which output the anagrams sets.
Eg for Input: algorithm testing asdfgh esttngi gorialmth
Output:
algorithm gorialmth
testing esttngi

8. Write a preorder traversal of a binary search tree w/o recursion / stack / extra memory storage. Hint – you can augment the node data structure. However, you can’t add a visited field to the node.

9. How will you remove white space from a string?

10. Prove that you can’t build a random number generator function that will output numbers 1 to 7 with uniform distribution and guaranteed to work in finite time using a random number generator that outputs either 1 or 2 with equal probability

11. An array is given like {1,4,5,2,3,6,7}. sort the odd elements in descending order and even numbers in ascending order. so result would be {7,5,3,1,2,4,6}.

Advertisements

Interview Questions 10

1. Given a set of schedules with Start and End times, cluster the ones which have a collision in time. The clusters can have more than two schedules and have to be unique. Do it efficiently.

2. You are given a set of n points in a XY plane. Suggest an algorithm to determine if every point is at least separated by every other point by a Manhattan distance of 5 units. Return should be true or false. Better than O(n^2).

3. You have an array like ar[]= {1,3,2,4,5,4,2}. You need to create
another array ar_low[] such that ar_low[i] = number of elements lower
than or equal to ar[i] in ar[i+1:n-1].
So the output of above should be {0,2,1,2,2,1,0}

4. Generate all strings of length ‘n’, from a given string, which do not contain another given string as a substring.

5. Given an array of size n wherein elements keep on increasing monotically upto a certain location after which they keep on decreasing monotically, then again keep on increasing, then decreasing again and so on. Sort the array in place (ie. using only O(1) extra memory).

6. Given a input string find the longest substring which appears more than once in the string?

7. Write a function that takes an array of five integers, each of which is between 1 and 10, and returns the number of combinations of those integers that sum to 15. For example, calling the function with the array [1, 2, 3, 4, 5] should return 1, while calling it with [5, 5, 10, 2, 3] should return 4 (5 + 10, 5 + 10, 5 + 5 + 2 + 3, 10 + 2 + 3). You may assume that the input has already been validated. Show how you would test this function.

8. Given a array, find k increasing numbers whose summation will be maximum.

9. You are given an amount of work load k, which can be partitioned among m workers. Generate all the partitions.

10. A string S can contain just two symbols X and Y. The number of X symbols in S must be equal to the number of Y symbols. For each prefix of S, the number of X must be less than the number of Y.
What is the intepretation of the problem?

Interview Questions 9

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.

%d bloggers like this: