Algorithm interview questions – page 5

Convert a number given in base B1 to a number in base B2 without using any intermediate base

Given an sorted array, what is the complexity of finding weather a number is present n/2 times or not. a)O(lgn) b)O(n) c)O((lgn)^2) d)O(1)

Given a number, generate all the strings that can be obtained with that number on a telephone keypad

Given a sequence of integers, find a continuous subsequence which maximizes the sum of its elements, that is, the elements of no other single subsequence add up to a value larger than this one. An empty subsequence is considered ...

If the letters of the word "rachit" are arranged in all possible ways and these words are written out as in a dictionary, what is the rank of the word "rachit".

There is a matrix of 1 and 0. 1 is a island and 0 is water. 1-1 together makes one island. calculate total no of islands

Longest increaing subsequence in ana array

You are given a function printMostFrequentWords which takes in an array of strings. You are required to print a list of all the letters that occurred with the highest frequency in each line of the array, followed by the frequency. The list o...

Design an algorithm to sort an array whose first n-sqrt(n) elements are already sorted. What is the complexity of the algorithm

If given a 15 digit number whats the best way to find the next palindrome?

Write code for minimal spanning tree

What is the best way to find k largest elements in an unsorted array? and what is it's time complexity?

Given an array of integers, find Pythagorean triplets.

There are n different machines, each having n numbers. Find median of these n*n numbers, but you can load only 2n integers at a time in memory

Explain Fibonacci search and compare it with Bianry search

Given a Binary Tree and its depth d find the number of leaf nodes in that tree.

A sorting algorithm which can prove to be a best time algorithm in one case and a worst time algorithm in worst case is

An array A[1...n] contains all the integers from 0 to n except for one number which is missing. In this problem, we cannot access an entire integer in A with a single operation. The elements of A are represented in binary, and the only operation ...

Given an undirected graph, design a O(V+E) algo to detect whether there is a triangle in the graph ot not.

Write a function to compare two xml files

A C++ code was given and was asked to debug. The bug was, an array of a derived class object was declared. Base class pointer was made to point to the array. But to traverse the array, base_ptr++ was done which gives wrong output.

Suggest Data structure and algo to implement undo and redo operations in MS Word.

Imagine you have a special keyboard with the following keys:

Given an array of elements and an integer x, rearrange the array such that all the elements greater than or equal to x should be in descending order and all the elements less than x should be in ascending order in most efficient manner.

Write a program for displaying the ten most frequent words in a file such that your program should be efficient in all complexity measures.

Game of master mind: you have four balls, and four different colors, as a solution. The user tries to guess the solution. If they guess the right color for the right spot, it counts as a 'hit'. If it's the right color, but the wr...

You are given a string which contains some special characters. You also have set of special characters. You are given other string (call it as pattern string). Your job is to write a program to replace each special characters in given string by pa...

WAP to count no of 1's occuring in a string? EX:if strinf is 1111 then it should return 4

Given a function which returns true 60% time and false 40% time.

Input is a NxN matrix which contains only 0's and 1's. The condition is no 1 will occur in a row after 0. Find the index of the row which contains maximum number of zeros. Example: lets say 5x5 matrix 1 0 0 0 0 1 1 0 0 0 1 ...