Interview Questions:

- Given a Binary Search Tree, write a program to print the kth smallest element without using any static/global variable. You cant pass the value k to any function also.
- What are the 4 basics of OOP?
- Define Data Abstraction. What is its importance?
- 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.
- Given an array of size n. It contains numbers in the range 1 to n. Find the numbers which arenâ€™t present.
- Given a string,find the first un-repeated character in it? Give some test cases
- 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.)
- Given a cube of size n*n*n (i.e made up of n^3 smaller cubes), find the number of smaller cubes on the surface. Extend this to k-dimension.
- What is a C array and illustrate the how is it different from a list.
- What is the time and space complexities of merge sort and when is it preferred over quick sort?
- Write a function which takes as parameters one regular expression(only ? and * are the special characters) and a string and returns whether the string matched the regular expression.
- Given n red balls and m blue balls and some containers, how would you distribute those balls among the containers such that the probability of picking a red ball is maximized, assuming that the user randomly chooses a container and then randomly picks a ball from that.
- 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.
- Given an array of size n, containing every element from 1 to n+1, except one. Find the missing element.
- How do you convert a decimal number to its hexa-decimal equivalent.Give a C code to do the same
- Explain polymorphism. Provide an example.
- Given an array all of whose elements are positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7)
- You are given some denominations of coins in an array (int denom[])and infinite supply of all of them. Given an amount (int amount), find the minimum number of coins required to get the exact amount. What is the method called?
- Given an array of size n. It contains numbers in the range 1 to n. Each number is present at least once except for 1 number. Find the missing number.

- How would you eliminate and print duplicate elements of an array of 5 billion 32-bit signed integers
- Reverse K elements of a linked list.
- How to find popular cost of the books, say book1 $10, book2 $20, book3 $40, book4 $50, book5 $10, book6 $20. We can use any algorithm to find the popular cost.
- I know about the classic “Tortoise and Hair” algorithm to detect cycle in a LinkedList. What is a similar fast way (without using hashtables) for finding the node at which the cycle starts i.e. the node with 2 incoming edges and one outgoing edge?
- You are given a string. You need to find the longest substring with unique characters in O(n) time
- A file contains set of anagram. print the output as list of similar word one by one. e.g. plates stop staple pots meat not pot team. Output:- 1. Plates, staple 2. pots, stop …. etc
- In an unsorted array of first N natural numbers. The array contains a number which is dulicated and one is missing. Find both the numbers.
- Reverse K elements of a linked list.
- Find maximum number of distinct paths between two coordinates x1,y1 and x2,y2. where x2>=x1 and y2>=y1. and movement is allowed only in increasing direction, i.e. x1, y1 can move in (0, +1) means to the right and x1,y1 can move in (+1, 0) in the up direction.