Algorithm interview questions – page 20

An array contain +ve and -ve element, find subarray whose sum =0;

Suppose we have N companies, and we want to eventually merge them into one big company. How many ways are there to merge?

There are 2 types of bricks 1*2 and 1*3, in how many ways can u build a wall of length n and height 1. i.e for wall of length 7 and height 1 ans - 223, 232, 322 for wall of size 8 ans - 2222, 233, 323, 332

Implement thread-safe version of stack[Microsoft] implement synchronize access for a stack.You do not want to use locking to implement synchronization.Implement a thread-safe version of the stack.

Without using /, % and * operators. Write a function to divide a number by 3. itoa() function is available.

Given an array A[i..j] find out maximum j-i such that A[i]<a[j] in O(n) time.

Find the largest palindrome in a string efficiently.. Do not even try to use bruteforce. I have paid the price using it :(...

Given an array of 51 playing cards, write code to find the missing card.

There is a portal with two billion users registered. If you store all the 2 billion users in a conventional databases it will take more time to retrieve the data about a particular user when that user tries to login. How do you handle this situati...

3. Polynomial A+Bx+Cx^2+...+Nx^(n-1) this representation is more suitable for which data structure. Then P and Q are two such polynomial and how to add that two using that data structure. WAP for that.

Get the depth of a tree without using recursion

Design OOP constructs for the following functinoarlity. There are multiple types of phones (android, iphone etc). Each phone has a subset of features (voice, text, etc). How would you write the classes and inheritance esp. in C++?

Implement Queue using stack. How many stacks you need? Note that you can only use following functions on a queue.

2-d array sorted both row wise and column wise. Find the search element - (logn complexity)

Google has many visitors to its site. And it tracks what pages the customers visited, etc and other stuff. Lets say you store the data of customer id and the page id as a record in a log-file. Now assuming that you have created one log file for e...

An array of integers of size n. Generate a random permutation of the array, given a function rand_n() that returns an integer between 1 and n, both inclusive, with equal probability. What is the expected time of your algorithm?

You are given a game of Tic Tac Toe. You have to write a function in which you pass the whole game and name of a player. The function will return whether the player has won the game or not. First you to decide which data structure you will use for...

N a plane, n points are given i.e. the input is (x1,y1), (x2,y2)... (xn,yn). Now given these n points.Find the maximum number of collinear points. If anybody could suggest an algorithm based on Duality Concept then it is better... Let me know w...

Write your own strtok(sting,token) function..O(n^2).

Convert a double-precision number to rational, i.e.:

Given a function RAND5 that genrates random numbers in the range 0 t0 5 write afunction that RAND7?

7. An array given Arr[] which is in decreasing order. How many swapping required in

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

Let f(n, k) be the # of ways of choosing k integers without replacement from n consecutive integers so that no two selected are consecutive. a. give a recurrence for f(n, k) b. efficient implementation of f(n, k)

Describe recursive mergesort and its run-time. Write an iterative version in C++/Java/Python.

Find the median of two sorted arrays

You are given a function char* getword(int index) and a sorted dictionary of unknown size. How would you find a word in the dictionary.

Given a file containing 4,300,000,000 integers, how can you find one that appears at least twice?

You are given an expression like (a+((b+c))). Here extra brackets are provided on b+c... i mean like (b+c) is ok... but ((b+c)) isn't as it is redundant. So for a given expression, provide algorithm to find out whether the expression contains redu...

Find the point of intersection of two rectangles