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