Print pascal's triangle

 Posted on January 5, 2012  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Pascal’s triangle is based on this formula : C(n, r) = C(n-1, r-1) + C(n-1, r) int Pascal(int n, int r) { if (r == 0) return 1; if (n == 0) return 0; return Pascal(n - 1, k - 1) + Pascal(n - 1, r); } In cpp, this recursive routine can use both memoization and recursion: public static long nCr(int n, int r){ static unsigned long table256256256256 = {0}; if(r == 0 || n == r) { return tablennrr = 1; } if(r == 1) { return tablennrr = n; } if(r > n / 2) { return tablennrr = ncr(n, n - r); } return tablennrr = tablen−1n - 1r−1r - 1 + tablen−1n - 1rr; } In java, you can use a class and maintain the array outside the function and just use the function similar to above to update that array and return the value in the end. [Read More]
memoization  kodeknight  Dynamic Programming  DP  recursion 

BFS (Breadth first search ) OR Level Order Traversal on tree

 Posted on December 31, 2011  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Algorithm Starting at some arbitrarily chosen vertex s (s stands for start vertex) , we mark v so that we know we’ve visited it, process v, and  then visit i.e. mark the vertex as visited and process all of v’s neighbors.  Now that we’ve visited and processed all of v’s neighbors,  we need to visit and process all of v’s neighbors neighbors Example So consider the tree: [Read More]
Graph  tree  kodeknight  dijkshtra  recursion  binary-search-tree  BST  graph-search  shortest-path  queue  BFS  traversal  level-order-traversal 

Find the minimum element in the rotated sorted sorted array

 Posted on December 29, 2011  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

def findMin(arr): print(“Finding min in a…

Anonymous - Sep 4, 2014

def findMin(arr):
print(“Finding min in a rotated sorted array of integers”)

low = 0
high = len(arr) - 1
while low < high:
mid = int((low + high)/2)
left = mid - 1
right = high

if arr[mid] > arr[left] and arr[mid] > arr[right]:
low = mid
elif arr[mid] > arr[left] and arr[mid] < arr[right]:
high = mid
else:
return arr[mid]

search  ArraySearch  kodeknight  recursion  array  binary search  rotated array  min  sorted-array 

Find the minimum element in the rotated sorted sorted array

 Posted on December 29, 2011  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Question : Find the minimum element in the rotated sorted array. So for example we have sorted array as - 2,3,6,12, 15, 18. Now suppose the array is rotated k times ( we don’t know k), such that array becomes 15, 18,2,3,6,12 Answer - The answer to this lies on the fact that if we can find the point on inflection and things will be simple. So if we can have 2 sub arrays A and B, [Read More]
search  ArraySearch  kodeknight  recursion  array  binary search  rotated array  min  sorted-array 

Search an element in the sorted rotated array

 Posted on December 29, 2011  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Question: Implement a search function for a sorted rotated array. Duplicates are allowed. Returning any one of the duplicates is acceptable. So for example we have sorted array as - 2,3,6,12, 15, 18. Now suppose the array is rotated k times ( we don’t know k), such that array becomes 15, 18,2,3,6,12 Answer: We can do a binary search with some modified checks. So lets take arr as array, start be start of the array, end be arr. [Read More]
ArraySearch  kodeknight  Amazon  recursion  array  binary search  rotated array  CrackingTheCodingInterview  sorted-array  sorting-and-searching  java 

Print a Binary Tree in Zig Zag Level Order or spiral order

 Posted on December 27, 2011  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

Question: Print a binary tree in zig-zag level order. Zig-zag means print 1st level from left to right, then 2nd level right to left and alternate thereafter. Example: zig-zag level order traversal of below tree will be 0 2 1 3 4 5 6 14 13 12 11 10 9 8 7 Solution1 - Iterative solution Answer: We usually use a queue for level order traversal of a queue. If we want to use the same here, how will we change direction of traversal on every alternate level? [Read More]
tree  Binary Tree  BT  kodeknight  recursion  binary-search-tree  BST  iterative  level-order-traversal 

XML Sequence Delimiter

 Posted on September 11, 2011  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

An XML sequence delimiter might be required for processing XML streams without the boiler plate code that comes with well known XML Parsers. A simple use case might be converting xml transformations on the fly like producing a partial output of the xml transformation as the user punches the script, etc. This one uses a simple pattern based filter and recursion to achieve it. The delimiter is assumed to be comma (,). [Read More]
kodeknight  recursion  xml  java 

All permutations of a string

 Posted on September 7, 2011  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

small trick ,but a very nice solution for duplicat…

nikhil - Feb 4, 2014

small trick ,but a very nice solution for duplicates!!!!

Thanks Nikhil. :)

can u please write the main function for duplicate program. I ran the duplicate program and it is not giving me the desired output

backtracking  Permutation and Combination  kodeknight  String  Permutation  Interview Question  recursion  CrackingTheCodingInterview  java 

All permutations of a string

 Posted on September 7, 2011  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Problem Write a method to compute all permutations of a string. Example For a string of length n, there are n! permutations. INPUT: “abc” OUTPUT: “abc” “acb” “bac” “bca” “cab” “cba” So, we have 3! = 6 items for string abc. Solution There are several ways to do this. Common methods use recursion, memoization, or dynamic programming. The basic idea is that you produce a list of all strings of length 1, then in each iteration, for all strings produced in the last iteration, add that string concatenated with each character in the string individually. [Read More]
backtracking  Permutation and Combination  kodeknight  String  Permutation  Interview Question  recursion  CrackingTheCodingInterview  java 

Given a BST, create a mirror of it.

 Posted on May 11, 2011  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem Change a tree so that the roles of the left and right pointers are swapped at every node. Example So the tree… 4 / \ 2 5 / \ 1 3 is changed to… 4 / \ 5 2 / \ 3 1 The solution is short, but very recursive. As it happens, this can be accomplished without changing the root node pointer, so the return-the-new-root construct is not necessary. [Read More]
tree  kodeknight  mirror  recursion  binary-search-tree  BST  iterative