Searching and sorting in a 2-d array

Suppose you have a 2-d array with integers sorted both horizontally and vertically.
a) Search for the occurrence of a value in the array
b) Sort the array into a single-dimensional array

Find the number of negative elements in most efficient way

Given an n X n array with rows sorted and cols sorted, find the number of negative elements in most efficient way.

Sort a ordered linkedlist

A singly LL is given such that there is alternate ordering between the elements.

Ex: 1->2->13->14->11->5->4->null

Give an efficient O(n) algo to sort such a LL. There can be multiple such orderings in the given LL.

find height of a node in BST

Given a BST T and a node N in T such that all leaf nodes are connected in doubly linkedlist fashion, find height of the node N in T.

Given two strings, find the minimum no. of steps required to covert one to the other?

Birthday Calendar

Implement the birthday diary calendar to keep records of all birthdays of your friends
1) what underlying data structure(s) you will use so that the memory consumption should be optimum [i.e if you have only 12 birthday entries you should not hold memory for all 365 days of the year].

2) You should be able to view the data (birthdays) with closest birthday first [i.e 7th July should come before 11 Aug].

3) How will you keep this data sorted (for question 2), everytime you insert a new birthday entry. This sorting should be as optimum as possible [mergesort etc will not be very beneficial bcoz ideally you won't have thousands or millions of birthday]

4) How will you handle 2 or N number of birthdays on same day

Given a string of n characters, find the longest palindrome in the string.

O(n2) is simple, O(n) is nice

Given an undirected graph G(V,E), design an algo to detect whether there is a triangle in the graph?

Find the minimum substring containing all unique characters atleast once in the given string

Find pairs from the given array

Given an array X, find tuples (xi, xj) such that j>i and xj is the immediate number greater than xi in the given array?

Ex Problem: X: {5, 4, 1, 3, 7}
Solution:
{5, 7}
{4, 7}
{1, 3}
{3, 7}

Random Number Generation - II

Given a function rand5() which generates values between 0-5 with equal probablities, how would you create another function rand7() which generates values between 0-7?

For that matter given a function randM() which generates numbers between 0-M, how would you create another function randN() which generates numbers between 0-N with equal probabilities? Is it possible for every value of M,N?

PS: I'm calling this "Random Number Generation - II" because we already have another version of this problem here.

Think in terms of possible values being generated by the given randX() function and map to all the possible values to be generated by the target randY() function

Find union of two sets in O(1)

Use bit-map

Palindrome in LinkedList

Given a linked list with node as given below:

struct node
{
char info;
struct node *next;
}

Give an O(n) algorithm to find if its a palindrome or not? You can not use more than O(1) space.

Two pointers to explore the list, reach the mid-point reverse the first half and compare the two halves

Maze Searching

Given a 2-d maze of characters, find if there exists a word "Algorithms" in the maze. By exists we mean it exists in a row, a column or like snakes (diagonals prohibited though)?

By snakes, we mean like following

A . . . M S
L G . T H .
. O R I . .
Use DFS and explore the maze as and when letters are found

Generating Graphs

Given n nodes,

1. generate all possible directed subgraphs.
2. generate all possible undirected subgraphs.

Easier version:

Given n nodes,
1. generate all possible directed subgraphs of n nodes,
2. generate all possible undirected subgraphs of n nodes,

PubTrivia - a pub where algos are served alongwith drinks!

You and your friends have gotten together for a Trivia night at a local pub.There are N questions asked during the night.Each question is worth a number of points; the i-th element of the points array corresponds to the score received by you if you correctly answer the i-th question, but you lose that many points if you answer that incorrectly. The questions are given in the order specified and you must answer each question before the next is asked. In addition, after each correct answer you will receive a token. If you then have tokensNeeded tokens, the pub will immediately take all of your tokens and award you additional bonus points. However, if you get the question wrong, the pub will take away all of your tokens without giving you any bonuses. The element i of the bonuses array corresponds to the bonus you receive if you win the bonus on question i.
Note that it is possible to win multiple bonuses during the game.
You know the answer to all the questions and want to maximize the number of points you receive.
Give an algorithm to obtain the maximum points that you can receive if you correctly choose which questions to answer.

Inputs :
N
tokensNeeded
p - array of points
b - array of bonuses

Calendar Cubes

A corporate businessman has two cubes on his office desk. Every day he arranges both cubes so that the front faces show the current day of the month. What numbers are on the faces of the cubes to allow this?

I have come up with a solution which I would call "sly" and really "unfair"!

Difference between Singleton and Static implementations

(1) Static implementations cannot be extended(only static fields and methods can be extended) whereas Singleton implementations can be extended and its methods can be overridden.
(2) Static implementations cannot extend other class's instance fields/methods while Singleton implementations can.
(3) Static implementations must be initialized at the class loading time however Singleton implementations can be lazy initialized or asynchronously initialized.
(4) Static implementations cannot be initialized with a STATE (parameter), whereas Singleton implementations can be.
(5) Static implementations can still have instances (unwanted instances) whereas Singleton implementations prevents it.

Exchange problem

Its new year time and your company has sent T-Shirts of varying sizes from HQ (read US). The problem is that the sizes in US and the sizes in India don't really match. So a guy with L size in India would like to settle for M size in US, one with XXL in India would like to go for XL and so on. Employees in India are bugged up and want to exchange it with appropriate sized T-Shirt. Now that the management didn't take care of it before sending the T-Shirts to India, you have been assigned by the Indian management to arrange an exchange between the employees. How would you go about it? Also describe your algorithm. If all this information is stored in the database, write a query that would do the job.

Random Number Generation

Given a function random(0,1) which randomly generates 0 or 1 with equal probabilities, extend its functionality to generate random numbers for an interval [a,b], i.e. implement random(a,b), for all 0 =< a < b. Prove that the strategy is uniformly random or would you like to put some conditions on a and b?


Another version: Given a random function random() which generates 0,1 but with uneven probabilities, create a random function newrandom() which generates 0,1 with even probabilities. Uneven probabilities mean if probability of getting 0 from random is p, that of 1 is (1-p) but p!=(1-p)!=1/2