/*
* We use "last" to keep track of the maximum distance that has been reached
* by using the minimum steps "ret", whereas "curr" is the maximum distance
* that can be reached by using "ret+1" steps. Thus,
* curr = max(i+A[i]) where 0 <= i <= last.
*/
int jump(int A[], int n) {
int ret = 0;
int last = 0;
int curr = 0;
for (int i = 0; i < n; ++i) {
if (i > last) {
last = curr;
++ret;
}
curr = max(curr, i+A[i]);
}
return ret;
}
Author Archives: anirban0328
Check for Uppercase, Lowercase, Digits & Whitespace
for (char c : password.toCharArray()) {
if (Character.isUpperCase(password.charAt(i))){ upperCase++; }
if (Character.isLowerCase(password.charAt(i))){ lowerCase++; }
if (Character.isDigit(password.charAt(i))) { numberCount++;}
if (Character.isWhitespace(password.charAt(i))) { blankCount++;}
}
Counting integers in a string
String s = "abcd123";
int counter = 0;
for(char c : s.toCharArray())
{
if( c >= '0' && c<= '9')
{
++counter;
}
}
OR
String s = "abcd123";
int count = 0;
for (int i = 0, len = s.length(); i < len; i++)
{
if (Character.isDigit(s.charAt(i)))
{
count++;
}
}
Square of a number without using *, / ,+and pow()
If n is even, it can be written as
n = 2*x n2 = (2*x)2 = 4*x2
If n is odd, it can be written as
n = 2*x + 1 n2 = (2*x + 1)2 = 4*x2 + 4*x + 1
square(n) = 0 if n == 0 if n is even square(n) = 4*square(n/2) if n is odd square(n) = 4*square(floor(n/2)) + 4*floor(n/2) + 1
Examples
square(6) = 4*square(3)
square(3) = 4*(square(1)) + 4*1 + 1 = 9
square(7) = 4*square(3) + 4*3 + 1 = 4*9 + 4*3 + 1 = 49
CODE
int square(int n)
{
// Base case
if (n==0) return 0;
// Handle negative number
if (n < 0) n = -n;
// Get floor(n/2) using right shift
int x = n>>1;
// If n is odd
if (n&1)
return ((square(x)<<2) + (x<<2) + 1);
else // If n is even
return (square(x)<<2);
generate PDF in Java
public String generateLeaversReport(ArrayList<UserReportBean> leaversAList,String leaversFromDate,String leaversToDate,String filteredLocation) throws Exception
{
Document document = null;
File f= null;
try
{
document = new Document(PageSize.A4,10,10,10,10);
f = new File("Leavers.pdf");
FileOutputStream fos = new FileOutputStream(f);
PdfWriter.getInstance(document, fos );
document.open();
Table table=new Table(29);
table.setBorder(0);
table.setWidth(100f);
table.setWidths(new float[]{0.5f,1.2f,1.0f,0.6f,1.25f,1.25f,1.5f,1.25f,1.20f,0.75f,1f,1.20f,0.75f,0.75f,0.75f,1.5f,0.8f,1.10f,0.8f,0.8f,0.8f,0.8f,0.9f,0.6f,0.6f,0.6f,0.6f,0.6f,0.6f});
table.setCellsFitPage(true);
table.setPadding(2);
table.setSpacing(0);
Cell hdrCell = new Cell(new Chunk(StringUtils.trimToEmpty("Leavers Report For the Period : "+leaversFromDate+" To "+leaversToDate+" For "+filteredLocation),
FontFactory.getFont(FontFactory.HELVETICA_BOLD, 8, Font.BOLD, new Color(0, 0, 0))));
hdrCell.setColspan(29);
hdrCell.setHeader(true);
hdrCell.setBorder(Rectangle.NO_BORDER);
hdrCell.setHorizontalAlignment(Cell.ALIGN_CENTER);
table.addCell(hdrCell);
table.addCell(getHeaderCell_New("S.No.",1));
table.addCell(getHeaderCell_New("AssociateID",1));
table.addCell(getHeaderCell_New("First Name",1));
table.addCell(getHeaderCell_New("Middle Name",1));
table.addCell(getHeaderCell_New("Last Name",1));
for(int i=0;i<leaversAList.size();i++)
{
UserReportBean bean=leaversAList.get(i);
table.addCell(getCell_New(String.valueOf(i+1),1));
table.addCell(getCell_New(bean.getAssociateID(),1));
table.addCell(getCell_New(bean.getFirstName(),1));
table.addCell(getCell_New(bean.getMiddleName(),1));
table.addCell(getCell_New(bean.getLastName(),1));
}
document.add(table);
}
catch(Exception ex)
{
ex.printStackTrace();
}
finally
{
if(document!=null)
{
document.close();
}
}
return f!=null?f.getAbsolutePath():null;
}
Find word in dictionary
Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:
Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
For example,
Given:
start = “hit”
end = “cog”
dict = [“hot”,”dot”,”dog”,”lot”,”log”]
Answer
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;
}
Removing element from hashmap
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();
}
}
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
8 PEOPLE PUZZLE
There are 8 people, who need to cross a river in single boat. People are 1 Cop, 1 Thief, 1 Man and his 2 Daughters, 1 Women and her 2 sons. As usual the conditions that has to be satisfied while crossing the River are given below:
• When Police man is not on that river bank, Thief will beat all the people available on that river bank.
• When Women is Not on that river bank, Man will beat her 2 sons.
• When Man is Not on that river bank, Woman will beat his 2 daughters.
• Only Two people can travel in the boat at any given time.
• 2 Sons and 2 daughters doesn’t know to drive the boat.
ANSWER
Please follow Step by Step process as defined below:
Initial stage Cop, Thief, Men, Daughters, Women, Sons are at River Bank – 1
1. Pick up Cop-Thief pair and travel to River bank – 2
2. Drop the Thief at River bank – 2 and cop only will reach back River bank – 1
3. Cop will Pick up Daughter – 1 at river bank -1 and travels to River Bank -2
4. Cop will drop the daughter – 1 at river bank – 2 and picks thief along with him and reaches back to River bank – 1
5. Both Cop and thief pair will drop at River bank -1
6. Now Man along with his Daughter – 2 travels from River bank -1 to River Bank -2
7. Man will drop his Daughter -2 at river bank – 2 and reaches back River Bank – 1 single
8. Now Man will pick up Women at River bank -1 and reaches to River bank – 2
9. Man will get down at river bank-2 and Women alone will return back to River bank – 1
10. Women will get down at River bank -1 . Cop and Thief pair will travel from River bank – 1 to River bank – 2
11. Cop and Thief will get down at River bank – 2. Man alone will travel back to River bank -1
12. Man picks up woman at River bank -1 and reaches back to River bank -2
13. Man will get down at River bank – 2 and women alone will sail back to River bank -1
14. Women will pick up her Son – 1 at River bank – 1 and travels back to River bank – 2
15. Women along with her son – 1 will get down at River bank -2.
16. Cop and Thief pair will travel from River bank – 2 back to River bank – 1
17. Cop will drop Thief at River bank -1 and picks Son -2 and reaches River bank -2
18. Cop will drop son-2 at river bank -2 and sails back to River bank -1 to pick up thief
19. Both Cop an Thief pair will reach back River bank – 2 safely.
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++;
}
Learn By Coding 