Algorithm interview questions – page 6

Square root of a perfect square in O(Logn) complexity

An array of size n has numbers from 1 to n. One number is missing and one number occurs twice. Find these two numbers

Given 2 billion numbers and 2 MB RAM, how will you sort the numbers.

How do you implement the dynamic memory allocation using heap

Zero Sum sub-array: You are given an array of integers.Find a sub-array whose sum of elements in zero in Linear time.

Given a string, find out the first non-repeating character.

Find out the smallest segment in a document containing all the given words. Desired Complexity is O nlogK ..n is the total no of words in the document and k is the number of input words

Check Number is perfect Square or Not Give Most Efficient Solution ? most eff. program shouldn't use any memory & variable amount of time followup Did you know what if Number is odd or even what if number can't fit in ...

Given a array A[] and a number x, find the subarray who's sum is equal to x. A[] contains both positive and negative numbers.

How to find if two arrays of size n are disjoint or not in O(n) time ? You can use only O(n) space... The elements are +ve in the range 0 to n power 100...

Given 3 arrays, pick 3 nos, one from each array, say a,b,c such that |a-b|+|b-c|+|c-a| is minimum.

Given an array containing red, green , blue coloured objects. design an algo to cluster these objects togetheri.e, one cluster for red, one for blue, one for green!!! Also design test cases to validate the algo!!!

Given a number, describe an algorithm to find the next number which is prime.

We are given 4 numbers say n1, n2, n3, n4. We can place them in any order and we can use mathematical operator +, -, *, / in between them to have final result as 24. Write an algorithm for this, it will take 4 numbers and return false or true whet...

Design an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list. The algorithm should run in linear time ( n >=0 )

Generate n random numbers in the range 0...n-1 without repetition (using something like drand48 which returns a fraction in the range [0...1).

Input an array of n numbers where each element is an integer in the range [0, N]. (N >> n). present an algorithm that runs in worst case in time O((nlogN)/log(n)) and checks whether all these n numbers are distinct. your algorithm should u...

There are set of coins of {50, 25, 10, 5, 1} paise in a box. Write a program to find the number of ways a 1 rupee can be created by grouping the paise.

Given an array of integers, each element represents the max number of jumps can make forward. What is the minimum number of element selections to reach the end of the array (starting from the first element). Example: arr = 1, 3, 5, 8, 9, 2, ...

Find the k-th Smallest Element in the Union of Two Sorted Arrays

Given a rand(N) a random generator 0 - N-1. now

Given an array, sort the array in such a way that the first part of the sorted array contains odd numbers, and the second part contains even numbers. The first part has to be sorted in descending order and the second part in ascending order. Not e...

An algorithm to print all the 10-digit nos such that first 1 digit is divisible by 1, first 2 digits by 2, first 3 digits by 3 and so on...first 9 digits by 9. I think the tenth digit can be anything from 0 to 9.

You are given an array of integers. You have to output the largest range so that all numbers in the range are present in the array. The numbers might be present in any order. Have to do it in linear time. May use extra memory. But Hashing is not t...

We have N element array with k distinct keys(No relation between k & N given so assume (k<N). What is the best method to sort this array without using any extra memory? Please elaborate.

Find maximum repeating number in a given array. optimize it for space then in time. Eg 5 is maximum repeated in array {12, 4, 5, 89, 5, 4, 12, 6, 5, 5}

There are N nuts and N bolts, all unique pairs of Nut and Bolt You cant compare Nut with Nut. You cant compare Bolt with Bolt You CAN compare Nut with Bolt Now how would you figure out matching pairs of nut and bolt from th...

Given an unsorted array of numbers. Find if the array consists of consecutive numbers after sorting. Do this in linear time.

Write prog to create skip list and search for nodes...

Given a number between 1 to 1000 convert it to words..example 235 should print as two hundred thirty five..