Algorithm interview questions – page 21

Find a missing 32bit integer among a unsorted array containing at most 4 billion ints

Given two arrays, determine if they match. Order of elements does not matter. Number of occurrences does matter. Return true for match, false for no match Computational complexity is important.

Given an array of random numbers and -1 placed in-between, compact that array ie., all the -1s are to be removed and the final output should be the last valid index with the fresh array.

Write an algorithm for multiplication of two polynomials in nlogn complexity

Given an integer array A, find the length of the longest subarray of A that is first striclty increasing then strictly decreasing. There must be at least 3 elements in such an array. eg. for the array {1, 8, 7, 29, 22, 45, 90, 50, 30, 60} the lo...

There are n sorted array and u are required to merge these to form a new single sorted array...Write complete code for this. First write ur program considering arrays of same length, and then do for different lengths.

When people search at Google, they often type two words without space. For example, instead of typing "binary tree", someone can type "binarytree". Given an input, what is a good way of finding if it is a combination of two valid words?

Given a set of 1 Trillion integers on hard disk, find the smallest 1 million of them. You can fit at most 1 million integers in memory at a time. State the fastest solution you can think of.

Multiply all the elements of A[] and store the output in an aray out[], and the element at out[i] should be the output of all elements of A[] except A[i]

Write ftoa() procedure. i/p: float no. o/p: string representation.

We all knw hw to find a loop in a singly linked list (Using hare and tortoise method)..what if the linked list is a doubly linked list?can we do it smthn better than hare n tortoise method using the advantage of the doubly linked list?

How to count number of unique music titles downloaded from a log file which contains an entry of all music title downloaded?

Convert number in to its complement, efficiently in less then O(n)

You are given a small sorted list of numbers, and a very very very long sorted list of numbers - so long that it had to be put on a disk in different blocks. How would you find those ( short list) numbers in the bigger list?

2. Number of times multiplication is required:

How to remove the duplicates in a sorted array and return the number of unique elements in linear time and constant space.

Given an array of Integers,if u are on ith element u can make max arr[i] jumps. If i am at an element with value zero, i cannot move forward. Find the least selection to reach end of the array. ex: 1 3 5 8 9 2 6 7 6 8 9 starting with a...

Jig saw puzzle, What are the data structures? Assume you have some method which can tell you if two pieces fit together. How would you solve the puzzle, minimizing the number of times you have to call that function?

Given an unsorted array of integers containing both negative and positive number, find all the pairs that sum to a given value say 'total'.

Write a code which will receive as input a matrix (int[][] matrix) and which should find all local maximum from the matrix. A local maximum is such a number in the matrix that is greater than all its immediate neighbors. The method should return t...

There is a straight roads with 'n' number of milestones. You are given an array with the distance between all the pairs of milestones in some random Order. Find the position of milestones. Example: Consider a road with 4 milestones(a,b...

Write a program to find Pythagorean triples in an unsorted array in write program so that have minimum time complexity.

You can place weights on both side of weighing balance and you need to measure all weights between 1 and 1000. For example if you have weights 1 and 3,now you can measure 1,3 and 4 like earlier case, and also you can measure 2,by placing 3 on one ...

Given an array of n numbers where numbers could also be negative. Give an algorithm that should find index i and index j such that sum of numbers from index i to index j in that array is maximum over all possible values of i and j. Give an algorit...

You have one big unsorted file in hard disk, which is bigger than your RAM size. Now WAP to sort this file

Let f(k) = y where k is the y-th number in the increasing sequence of non-negative integers with the same number of ones in its binary representation as y, e.g. f(0) = 1, f(1) = 1, f(2) = 2, f(3) = 1, f(4) = 3, f(5) = 2, f(6) = 3 and so on...

Given two character arrays, find the common characters.

Given three arrays A, B and C. The arrays are not sorted. Find x from A, y from B and z from c such that the values in set(x-y, y-z, z-x) are minimum

Write an efficient algorithm to find the largest rectangle in a histogram.

Write a recursive algo to print all permutations of 'n' consecutive integers in lexicographic order