# Interview Questions 18

December 6, 2010 1 Comment

1. Given a unordered array of numbers, remove the fewest number of numbers to produce the longest ordered sequence. Print count of fewest numbers to be removed, and the remaining sequence.

For example, if input is 1 2 3 4 5 6 7 8 9 10, no (zero) numbers are removed, and input is the longest sequence.

If input is, 1 2 3 8 10 5 6 7 12 9 4 0, then fewest number of elements to be removed is 5 is the fewest number to be removed, and the longest sequence is 1 2 3 5 6 7 12.

2. Given a positive integer n, write a function to print the nth row of Pascal’s triangle.

3. Write a program to print out all valid tic-tac-toe game moves.

4. [**Design**] Design and implement APIs for caching web pages.

5.

Class B { int b; public: void disp(); void show(); }; Class D : public B { int d; public: void disp(); void show(D &); };

What is the size of the Base Class and Derived ?

6.

class Sample { public: Sample() { cout<<"const"<<endl; } ~Sample() {cout<<"destr"<<endl;delete this; } }; int main() { Sample *obj = new Sample; delete obj; return 0; }

what happens when u delete this in destructor?

7. Given two arrays A & B of length l, containing non negative integers, such that the sum of integers in A is the same as sum of integers in B.( The numbers need not be the same in both the arrays.)

Now if you start with an index ‘k’ in each array and do the following summation, SUMMATION (Ak-Bk), where Ak is the value at index k of array A, and Bk is the value at index k of array B, where ‘k’ increments and wraps back all the way to k-1, the final sum value will be zero.

Question: Find a suitable ‘k’ such that during any point in the summation, SUMMATION(Ak-Bk) is always non negative. Find such a ‘k’ in O(n) time.

8. Given set of n points (Xi, Yi), write a function to find k nearest points from origin.

9. How do you avoid dangling pointers and dangling references? Can you have a const reference to an object i.e. MyClass& const refToObj;? Does having a const* to an object guarantee safety from seg faults? What is the best alternative?

10. Write a code which return square of any number, but you can not use Star or carrot sign.

Q1 find the longest increasing subsequence in the array…the elts which are not the part of sequence has to remove…

Q5 size of base class = sizeof(int) , size of derived class = size of base class + sizeof(int).

Q8 calculate the distance of each point from the center .. keep the max-heap of first k points distance ..now for each point check it with the root of heap if the point distance is smaller replace it with the points distance…do heapify ..in the end the remaining points are the k points closer to the center.

please leave a comment if anything is wrong..