# Archive for the ‘puzzles/ algorithms’ Category

## Finding longest palindrome in a string

Posted by guptaradhesh on August 26, 2013

Here is an elegant code I found.

string expandAroundCenter(string s, int c1, int c2) {

int l = c1, r = c2;
int n = s.length();
while (l >= 0 && r <= n-1 && s[l] == s[r]) {
l–;
r++;
}
return s.substr(l+1, r-l-1);
}
string longestPalindromeSimple(string s) {
int n = s.length();
if (n == 0) return “”;
string longest = s.substr(0, 1);  // a single char itself is a palindrome
for (int i = 0; i < n-1; i++) {
string p1 = expandAroundCenter(s, i, i);
if (p1.length() > longest.length())
longest = p1;
string p2 = expandAroundCenter(s, i, i+1);
if (p2.length() > longest.length())
longest = p2;
}
return longest;
}
source: here

Posted in java, puzzles/ algorithms, tech | Tagged: , , , | Leave a Comment »

## Print matrix in a sprial order

Posted by guptaradhesh on August 22, 2013

Recursive Solution (Java):

```public class PrintMatrixSpiral
{
public static void main(String[] args)
{
int[][] matrix =
{
{ 2, 4, 6, 2, 5, 7 },
{ 2, 5, 7, 8, 9, 3 },
{ 6, 4, 7, 3, 5, 7 } };

printSpiral(matrix);
}

public static void printSpiral(int[][] matrix)
{
printSpiral(matrix, 0);
}

private static void printSpiral(int[][] matrix, int depth)
{
if (matrix == null && matrix.length == 0)
return;
int rows = matrix.length;
int cols = matrix[0].length;
if (2 * depth > Math.min(rows, cols))
return;
for (int i = depth; i < cols - depth - 1; ++i)
{
System.out.print(matrix[depth][i] + ",");
}
for (int i = depth; i < rows - depth - 1; ++i)
{
System.out.print(matrix[i][cols - depth - 1] + ",");
}
for (int i = rows - depth; i > depth; --i)
{
System.out.print(matrix[rows - depth - 1][i] + ",");
}
for (int i = rows - depth - 1; i > depth; --i)
{
System.out.print(matrix[i][depth] + ",");
}
printSpiral(matrix, ++depth);
}
}

```

Posted in java, puzzles/ algorithms, tech | Tagged: , , , , | Leave a Comment »

## In-order traversal of a Binary Search Tree without recursion

Posted by guptaradhesh on May 16, 2013

void in_order_traversal_iterative(BinaryTree *root) {

stack<BinaryTree*> s;
BinaryTree *current = root;
while (!s.empty() || current) {
if (current) {
s.push(current);
current = current->left;
} else {
current = s.top();
s.pop();
cout << current->data << ” “;
current = current->right;
}
}
}
reference: here

Posted in puzzles/ algorithms | Tagged: , , | Leave a Comment »

## Lowest common ancestor of a Binary Search Tree

Posted by guptaradhesh on May 16, 2013

Worst case O(n

 1. 2 3 4 5 6 7 8 Node *LCA(Node *root, Node *p, Node *q) {   if (!root) return NULL;   if (root == p || root == q) return root;   Node *L = LCA(root->left, p, q);   Node *R = LCA(root->right, p, q);   if (L && R) return root;  // if p and q are on both sides   return L ? L : R;  // either one of p,q is on one side OR p,q is not in L&R subtrees }
—
reference: here

Posted in puzzles/ algorithms, tech | Tagged: , , , , | Leave a Comment »

## Some Interview puzzles by Apple

Posted by guptaradhesh on April 18, 2013

Posted in puzzles/ algorithms, tech | Tagged: , , , | Leave a Comment »

## Find the index i and j of an array where j>i and a[j] – a[i] is maximum

Posted by guptaradhesh on March 27, 2013

Given an unsorted array, find the index i and j such that, j>i and (a[j] – a[i]) is maximum?

A linear time solution which I find pretty elegant:

``````       private void MaxDiff(int[] a)
{
int min = a[0]; // assume first element as minimum
int maxdiff = 0;
int posi = -1, posj = -1, minpos = 0;

for (int i = 1; i < a.Length; i++)
{
if (a[i] < min)
{
min = a[i];
minpos = i;
}
else
{
int diff = a[i] - min;
if (diff > maxdiff)
{
maxdiff = diff;
posi = minpos;
posj = i;
}
}
}
System.out.format("i=%d, j=%d",posi,posj);
}``````

Posted in puzzles/ algorithms | Tagged: , , , , | Leave a Comment »

## Permutations of a String

Posted by guptaradhesh on February 4, 2013

``````public  static void permutation(String str) {
permutation("", str);
}

private static void permutation(String prefix, String str) {
int n = str.length();
if (n == 0) System.out.println(prefix);
else {
for (int i = 0; i < n; i++)
permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
}
}``````

Posted in java, puzzles/ algorithms | Tagged: , , , | 1 Comment »

## For a 3 sets tennis game, would you bet on it finishing in 2 sets or 3 sets?

Posted by guptaradhesh on September 19, 2012

This question was asked to a friend of mine as a part of interview process for DE Shaw & Co. I liked the question. Pretty basic probability question to test ones thinking process.

My two cents:

If the two players have equal probability of winning, the chance that the game will finish in 2 sets or 3 sets is same.

If one of the players is better then other, the chances of game finishing in 2 sets is more then chances of game finishing in 3 sets.

Say, p is probability of Player A winning a set ; q is the probability of Player B winning a set

and lets assume p > q

If game ends in 2 sets => Player A wins first two games or player B wins first two games;  P1 = p*p + q*q

If game ends in 3 sets => Player A and B win first or the second game; P2 = p*q + q*p

And we know that,   p^2 + q^2 >= 2 p*q  [with minima when p=q]

Posted in puzzles/ algorithms | Tagged: , , , | Leave a Comment »

## Reverse a Linked List

Posted by guptaradhesh on February 23, 2011

here is the simple snippet I would consider dumping for anyone’s anytime reference..

The two approaches are as:

Non-recursive :

```Node * reverse( Node * ptr )
{
Node * temp;
Node * previous = NULL;
while(ptr != NULL) {
temp = ptr->next;
ptr->next = previous;
previous = ptr;
ptr = temp;
}
return previous;
}```

Recursive approach:

```Node * reverse( Node * ptr , Node * previous)
{
Node * temp;
if(ptr->next == NULL) {
ptr->next = previous;
return ptr;
} else {
temp = reverse(ptr->next, ptr);
ptr->next = previous;
return temp;
}
}
reversedHead = reverse(head, NULL);```

Posted in puzzles/ algorithms, tech | 1 Comment »

## Finding path between a specific node and the root

Posted by guptaradhesh on February 3, 2011

void findPath(Node root, Node node){
Stack->push(root);
if(node == root){
print stack data;
return;
}
if(root->left != null){
findPath(root->left, node);
}
if(root->right!=null){
findPath(root.right, node);
}
Stack->pop();
}

Posted in puzzles/ algorithms, tech | 1 Comment »