Naman - May 6, 2014
This comment has been removed by a blog administrator.
This comment has been removed by the author.
Median of 2 sorted arrays of equal size n
Question There are 2 sorted arrays A and B. Write an algorithm to find the median of the array obtained after merging the above 2 arrays(i.e. array of length 2n). The complexity should be O(log(n))
Solution Before going to solution what is the median.
What is Median? Median: In probability theory and statistics, a median is described as the number separating the higher half of a sample, a population, or a probability distribution, from the lower half.
[Read More]
Find median of a linked list or a Tree
This pseudo-code holds for a Double Linked list:
1. init two pointers one at the start of the list(p1) and the other at the end (p2)
2. if p1=null or p2==null return NONE
3. At each iteration, visit node p1.next and p2.previous
4. if p1.next==p2.previous !=p1 || p2 then middle is obtained for an odd number of nodes. Return result
5. if p1.next==p2.previous=p1|| p2 then middle is for an even number of nodes.
[Read More]
Find longest palindrome in a string.
The Algorithm that you mentioned to take the LCS o…
Anonymous - Jun 6, 2014
The Algorithm that you mentioned to take the LCS of S and S’ where S’ is the reverse of S is a flawed Algorithm, Please check this post
http://leetcode.com/2011/11/longest-palindromic-substring-part-i.html
Find longest palindrome in a string.
I cannot think of any that has a complexity less than O(n*n).
one of the ways would be :
1. Take the string (s1) and its direct reversal (s2)
2. Slide s2 over s1 per character and count the number of similar characters starting from s2′s last character
Hence, first:
———————— ABCDAMNMADGHJ
JHGDAMNMADCBA Count =1
Then,
————————ABCDAMNMADGHJ
–JHGDAMNMADCBA Count=0
.
.
.
————————ABCDAMNMADGHJ
————————JHGDAMNMADCBA Count=7
.
.
.
————————ABCDAMNMADGHJ Count= 0 We can exit at this point
[Read More]
Compare two string literals
public boolean compare(String text1, String text2){
if(text1\=\="" && text2!\="")
text1\=null;
if(text2\=\=""&&text1!\="")
text2 \= null;
if (text1\=\= null && text2\=\=null)
return true;
if (text1.length()\=\=0 && text2.length()\=\=0)
return true;
if (text1.length()\=\=0 || text2.length()\=\=0)
return false;
if (text2\=\=null || text2\=\=null)
return false;
return text1.compareTo(text2);
}
Anagram Checker–To check if 2 strings are anagrams
An anagram is a type of word, the result of rearra… Unknown - Jul 1, 2014An anagram is a type of word, the result of rearranging the letters of a word or phrase to produce a new word or phrase, using all the original letters exactly once.
For example: orchestra can be rearranged into carthorse or cat can be rearranged into act.
We can find out the anagram strings using below algorithm:
[Read More]
Anagram Checker–To check if 2 strings are anagrams
Problem Wap to find out if 2 strings are anagrams or not.
Anagrams
Two words are anagrams if one of them has exactly same characters as that of the another word.
Example : Anagram & Nagaram are anagrams (case-insensitive).Similarily, abcd and abdc are anagrams, but abcd and abdce is not.
Solution A simple way to check if two strings are anagrams is to find out if the numeric sum of the characters in the strings is equal.
[Read More]
Find nth largest value in a BST
Hi there I was just going through your this post a… bakwasscoder - Jun 5, 2012Hi there
I was just going through your this post and had a small doubt.
Shouldn’t we do a stack based iterative traversal to get the correct value in this code ? This recursive may give wrong result as it will start counting after the rightmost element has been found. This element won’t be the nth largest in BST.
[Read More]
Find nth largest value in a BST
Simplest solution is to do a reverse in order search and maintain a global counter.
ReverseInOrder(Tree T, n)
1. if (T->right != null ) ReverseInOrder(T->right)
2. if (count==n) return T. Else count++
3. if (T->left != null ) ReverseInOrder(T->left)