Hi,
I was going through a site and found a few interview questions. I believe they are worth sharing. I will be putting answers to them as well.
1. Given a Binary Search Tree, write a program to print the kth smallest element ? Now can you do it without using any static/global variable. You can't pass the value k to any function also.
2. Given an array of size n. It contains numbers in the range 1 to n. Each number is present at least once except for 2 numbers. Find the missing numbers.
3. Given a string,find the first un-repeated character in it? Give some test cases
4. You are given a dictionary of all valid words. You have the following 3 operations permitted on a word: delete a character, insert a character, replace a character. Now given two words - word1 and word2 - find the minimum number of steps required to convert word1 to word2. (one operation counts as 1 step.)
5. What is the time and space complexities of merge sort and when is it preferred over quick sort?
6. Find the second largest element in an array with minimum no of comparisons and give the minimum no of comparisons needed on an array of size N to do the same.
7. Given an array of size n, containing every element from 1 to n+1, except one. Find the missing element.
8. You have 50,000 html files, some of which contain phone numbers. How would you create a list of all the files which contain phone numbers?
9. Given two sets, Write a function to provide the union of them.
10. Design an algorithm to calculate the most user viewed pages
11. Design an algorithm to find duplicates in an array.
12. Design an algorithm and write code to serialize a binary tree.
13. Design an algorithm and write code to find two numbers in an array whose sum equals a given value
14. Given two binary trees, find whether or not they are similar.
15. Assume your computer is reading characters one by one from a stream (you don't know the length of the stream before ending). Note that you have only one character of storage space (so you cann't save the characters you've read to a something like a strong). When you've finished reading you should return a character out of the stream with equal probability.
16. You are provided with a stream of numbers, design a data structure to store the numbers in the stream along with their no. of occurrences.
17. Given two sorted arrays A1 and A2, of lengths L1 and L2 , L1 < L2 and the last L1 slots in A2 are vacant, get me all the numbers in A2, sorted in the most efficient manner without using extra space. This was a written test question in which I blabbered quick sort will do..
18. In a array of size n , there is one number missing and one number repeated twice. Find them.
Subscribe to:
Post Comments (Atom)
1 comment:
2. if all numbers were present
sum = n(n+1)/2 = S
product = n! = P
lets say numbers are x (missing) and y(repeated)
sum of array = S1
product = P1
therefore we can say
S1-y +x = S
(P/y)*x = P
We have two equations and two variables.
e.g
1,2,3,5,5
so missing is 4.
S = 15
P = 120
S1 = 16
P1 = 150
so
16 -y + x = 15 => x-y = -1=> y = x+1 (i)
(150/y)*x = 120=>
150*x = 120(x+1) => 30x = 120 =>
x= 4
y = 5
Post a Comment