..MindWrite..

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


http://www.businessinsider.com/apple-brain-busting-interview-questions-answers-2012-6?op=1

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 »