Tester
BAN USERImplement BFS
1. verify given number is 1 if yes then return true.
2. If if it not then put 1 into queue
3. In while (true) pop queue item, Lets say it is "X"
4. if(INT_MAX/10 < X) return false
5. Multiply X by 10 mod by given number if remainder is zero then return true
6. else add the number to queue.
7. if((INT_MAX-1)/10 > X) return false
8. Multiply X by 10 and add 1 mod by given number if remainder is zero then return true
9. else add the number to queue.
1. Convert tree to doubly linklist . [this is poss in in O(1) memory]
2. Keep one pointer is at begining and other at the end.
3. Now treat like array and find if there is any pair which sum to k. [if start+end is higher than k then move end to previous else if start+ end sum is lower than k then move start foward else display current pair]
4. conver doubly linklist to tree.
1. Convert Binary tree itself to DoublyLink list
[https] leetcode.com/2010/11/convert-binary-search-tree-bst-to.html
2. Since it is BST it is sorted then keep pointers one at start and one at tail.
3. Now its easy, add element at head and tail if sum is equal then print this two element.
if sum is less than sum asked then move head pointer else move tail pointer to left.
4. optional - convert back to BST from doubly- linklist
Complexity O(N)
This should work...
- Edit distance one means, there is one character which is different.
- We have to address following 4 cases.
Lets call two strings as s1 and s2.
Case 1 : - if(s1.firstchar!= s2.firstchar && s1.lastchar!= s2.lastchar)
which means there are two differences thus. return false.
case 2 :- if(s1.firstchar==s2.firstchar && s1.lastchar!= s2.lastchar)
which means there is differnce at end already(keep track of end indices), start from first char then keep on comparing until you find a difference. If you find and its not tracked indices then return false
case 3:- if(s1.firstchar!=s2.firstchar && s1.lastchar== s2.lastchar)
which means there is differnce at start already(keep track of start indices), start from last char then keep on comparing until you find a difference. If you find and its not tracked indices then return false
case 4 :- if(s1.firstchar==s2.firstchar && s1.lastchar== s2.lastchar)
which means there is difference in between somewhere, start comparing from first character keep moving forward until you find a difference. once you found a difference (keep note of current indices) start comparing char from end. if you again found difference at same different indices return false , but if any of the previously tracked indices are same as current difference indices then edit distance is one.
For eg. s1 ="abcde" s2="acde"
step1 :- compare "a" then there is conflict at "b" and "c"
step2 :- so we went to end again start from there we found conflict with "b" and "a"
step3 :- both "b" do have same index so it has edit distance of one.
Note:- we can add more bound checking like comparing length of string. Please let me know, if it won't work any test case.
We need to two stacks
1. For Iterative in order traversal ( which will traverse tree in increasing order)
2. For Iterative reverse in order traversal ( which will traverse tree in reverse order)
3. Now its simple just add two elements one from in order and other from reverse in-order if sum = required number this two are number
else if sum > required number then move reverse in-order for next number.
else move in- order traversal for next number.
Since Question itself says. Check for every pair. My approach is take every out every pair store in hashmap along with index it uses and then look for if there exist same pair with different indices.
For eg:-
abab
1. ab in hashmap {{ab-> 0-1}} here key is ab and 0-1 is indices range
2. aa in hash map {{aa-> 0-2}}
3. ab in hash map. here you will see it is already in in hashmap. and if you look at the value it has same index as current index so we ignore this pair.
4. ba in hashmap {{ba->1-2 }}
5. bb in hashmap {{bb-> 1-3}}
6. ab here we again find it in hashmap. so we check if both indices differ they do. we found our solution.
This problem is basically [matchine Nuts and bolts].
Solution to this problem is with help of quicksort.
1. pick any object A randomly, then compare it all B to find the exact match for it. This pivot in quicksort.
2. While searching for match divide B into two part with respect to pivot so this will make
all small object (of type B) than pivot on left side and all large object (of type B ) on right.. same as quicksort.
3. So at this point we find exact match for B as well as we aligend B. Now we can do the same thing on array of object A . Then repeat the process for on both halves.
Complexity will be (n lg n)
Note:-
We are doing this way we cant directly compare two A type of objects.
Ref:-
[http] www wisdom weizmann ac il/~naor/PUZZLES/nuts_solution.html
public void transform(BinaryTree root){
if(root==null) return;
transform(root.getLeft());
transform(root.getRight());
if(root.getLeft()==null&&root.getRight()==null)
return;
if(root.getLeft()==null){
root.setLeft(root.getRight());
root.setRight(null);
}
else if(root.getRight()!=null)
{
root.getLeft().setRight(root.getRight());
root.setRight(null);
}
}
Your code is right. It only fails when faulty number is next is at the end.
for example Instead of 18684 u get input as
a. 1868488 - result for this should be true
b. 1868466 - result for this should be false
with your code for both input you will get false. You just have to add extra check so additional code will be:
while(i<expected.length()&& expected.at(i)==faultyKey )
{
i++;
}
It can be done in following way but I don't know its minimal wastage or not...
I am assuming we can only use two jar not 3
5,3,9.5
-------------------
0,3,6.5
3,0,6.5
3,3,3.5
5,1,3.5
1,0,3.5
1,3,0.5
4,0,0.5
done
I understand wastage is 9L..., but this the only way I could think of using two jars
Can you please explain, why you need Hashset as value?
- Tester February 11, 2015I think we know, how many emails are there [even if its not given we can keep a counter]. We can add all email address present in first mail into HashMap<String,Integer> and set all values to 1.
Then from second mail onwards we will first check if that mail address is present or not. If its present then increment the value by one. else we wont add that into hashmap. Then at end we can just iterate the hashmap
and whose value is equal to count we display only those.