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.

Source

 

  • 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.

Source