Here is an elegant code I found.
string expandAroundCenter(string s, int c1, int c2) {
Posted by guptaradhesh on August 26, 2013
Here is an elegant code I found.
string expandAroundCenter(string s, int c1, int c2) {
Posted in java, puzzles/ algorithms, tech  Tagged: interviews, java, palindrome, tech  Leave a Comment »
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: algorithms, interview, java, programming, sprial  Leave a Comment »
Posted by guptaradhesh on May 16, 2013
void in_order_traversal_iterative(BinaryTree *root) {
Posted in puzzles/ algorithms  Tagged: binary search tree, bst, traversal  Leave a Comment »
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
}

Posted in puzzles/ algorithms, tech  Tagged: binary search tree, bst, lowest common ancestor, lsa, recursion  Leave a Comment »
Posted by guptaradhesh on April 18, 2013
Posted in puzzles/ algorithms, tech  Tagged: apple, interview, puzzles, tech  Leave a Comment »
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: algorithms, array, j>i, java, maximum difference  Leave a Comment »
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: algorithms, java, permutations, string  1 Comment »
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: de shaw, probability, puzzle, tennis puzzle  Leave a Comment »
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:
Nonrecursive :
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 »
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 »