Iterator<Map.Entry<String,String>> iter = TestMap.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry<String,String> entry = iter.next();
if("Sample".equalsIgnoreCase(entry.getValue())){
iter.remove();
}
}
Category Archives: Algorithms
FINDING NTH HIGHEST NUMBER
EmpID Name Salary 1 A 100 2 B 800 3 C 300 4 D 400 5 E 500 6 F 200 7 G 600 SELECT * FROM Employee E1 WHERE (N-1) = ( SELECT COUNT(DISTINCT(E2.Salary)) FROM Employee E2 WHERE E2.Salary > E1.Salary )
Explanation
Suppose you want to find 5th highest salary, which means there are total 4 employees who have salary greater than 5th highest employee. So for each row from the outer query check the total number of salaries which are greater than current salary. Outer query will work for 100 first and check for number of salaries greater than 100. It will be 6, do not match (5-1) = 6 where clause of outerquery. Then for 800, and check for number of salaries greater than 800, 4=0 false then work for 300 and finally there are totally 4 records in the table which are greater than 300. Therefore 4=4 will meet the where clause and will return 3 C 300.
Another way
SELECT * FROM( SELECT BONUSMONTHID, dense_rank() over (ORDER BY BONUSMONTHID DESC) AS DenseRank FROM REFERRALBONUS ) where DenseRank = 2
Finding Vowels in a string
int count = 0;
String str = "Abcdefg";
if (str.length() > 0) {
Pattern vowelPattern = Pattern.compile("[a/Ae/Ei/Io/Ou/U]");
Matcher vowelMatcher = vowelPattern.matcher(str);
while (vowelMatcher.find())
count++;
}
Add numbers from a string
String str = "12 hi when 8 and 9";
str=str.replaceAll("[\\D]+"," "); // returns 12 8 9
String[] numbers=str.split(" ");
int sum = 0;
for(int i=0;i<numbers.length;i++){
sum+=Integer.parseInt(numbers[i]);
}
\\d* matches 0 or more digits, and so it even matches an empty string.
Use \\d+ to match only 1 and more digits
Greedy quantifiers
X? X, once or not at all
X* X, zero or more times
X+ X, one or more times
Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end
Given:
start = "hit" end = "cog" dict = ["hot","dot","dog","lot","log"]
As one shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”, the program should return its length 5.
Note:
Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
CODE
public int ladderLength(String start, String end, HashSet<String> dict) {
if (dict.size() == 0)
return 0;
dict.add(end);
LinkedList<String> wordQueue = new LinkedList<String>();
LinkedList<Integer> distanceQueue = new LinkedList<Integer>();
wordQueue.add(start);
distanceQueue.add(1);
//track the shortest path
int result = Integer.MAX_VALUE;
while (!wordQueue.isEmpty()) {
String currWord = wordQueue.pop();
Integer currDistance = distanceQueue.pop();
if (currWord.equals(end)) {
result = Math.min(result, currDistance);
}
for (int i = 0; i < currWord.length(); i++) {
char[] currCharArr = currWord.toCharArray();
for (char c = 'a'; c <= 'z'; c++) {
currCharArr[i] = c;
String newWord = new String(currCharArr);
if (dict.contains(newWord)) {
wordQueue.add(newWord);
distanceQueue.add(currDistance + 1);
dict.remove(newWord);
}
}
}
}
if (result < Integer.MAX_VALUE)
return result;
else
return 0;
}
Reverse words
public static String reverseWords2(String sentence) {
StringBuilder sb = new StringBuilder(sentence.length() + 1);
String[] words = sentence.split(" ");
for (int i = words.length - 1; i >= 0; i--) {
sb.append(words[i]).append(' ');
}
sb.setLength(sb.length() - 1); // Strip trailing space
return sb.toString();
}
Josephus problem
There are n people standing in a circle waiting to be executed. The counting out begins at some point in the circle and proceeds around the circle in a fixed direction. In each step, a certain number of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom. Given the total number of persons n and a number k which indicates that k-1 persons are skipped and kth person is killed in circle. The task is to choose the place in the initial circle so that you are the last one remaining and so survive.
CODE
int josephus(int n, int k)
{
if (n == 1)
return 1;
else
/* The position returned by josephus(n - 1, k) is adjusted because the
recursive call josephus(n - 1, k) considers the original position
k%n + 1 as position 1 */
return (josephus(n - 1, k) + k-1) % n + 1;
}
Rotate array matrix by 90deg
void rotateMatrix(int a[][]) {
int n = a.length;
if (n <= 1) {
return; // nothing to do
}
/* layers */
for (int i = 0; i < n / 2; i++) {
/* elements */
for (int j = i; j < n - i - 1; j++) {
int saved = a[i][j];
a[i][j] = a[n - j - 1][i];
a[n - j - 1][i] = a[n - 1 - i][n - 1 - j];
a[n - 1 - i][n - 1 - j] = a[j][n - 1 - i];
a[j][n - 1 - i] = saved;
}
}
}
Median in a stream of integers
After reading 1st element of stream – 5 -> median – 5
After reading 2nd element of stream – 5, 15 -> median – 10
After reading 3rd element of stream – 5, 15, 1 -> median – 5
After reading 4th element of stream – 5, 15, 1, 3 -> median – 4, so on…
Making it clear, when the input size is odd, we take the middle element of sorted data. If the input size is even, we pick average of middle two elements in sorted stream.
public class RunningMedian
{
PriorityQueue<Integer> upperQueue;
PriorityQueue<Integer> lowerQueue;
public RunningMedian()
{
lowerQueue=new PriorityQueue<Integer>(
20,new Comparator<Integer>()
{
@Override
public int compare(Integer o1, Integer o2)
{
return (o2-o1);
}
});
upperQueue=new PriorityQueue<Integer>();
upperQueue.add(Integer.MAX_VALUE);
lowerQueue.add(Integer.MIN_VALUE);
}
public double getMedian(int num)
{
//adding the number to proper heap
if(num>=upperQueue.peek())
upperQueue.add(num);
else
lowerQueue.add(num);
//balancing the heaps
if(upperQueue.size()-lowerQueue.size()==2)
lowerQueue.add(upperQueue.poll());
else if(lowerQueue.size()-upperQueue.size()==2)
upperQueue.add(lowerQueue.poll());
//returning the median
if(upperQueue.size()==lowerQueue.size())
return(upperQueue.peek()+lowerQueue.peek())/2.0;
else if(upperQueue.size()>lowerQueue.size())
return upperQueue.peek();
else
return lowerQueue.peek();
}
public static void main(String[] args)
{
Random random=new Random();
RunningMedian runningMedian=new RunningMedian();
System.out.println("num\tmedian");
for(int i=0;i<50;++i)
{
int num=random.nextInt(100);
System.out.print(num);
System.out.print("\t");
System.out.println(
runningMedian.getMedian(num));
}
}
}
Longest Common Subsequence
int lcs( char *X, char *Y, int m, int n )
{
if (m == 0 || n == 0)
return 0;
if (X[m-1] == Y[n-1])
return 1 + lcs(X, Y, m-1, n-1);
else
return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
}
Learn By Coding 