Problem #1
Consider the Following Problem:
Write a short program that prints each number from 1 to 100 on a new line.
For each multiple of 3, print "Fizz" instead of the number.
For each multiple of 5, print "Buzz" instead of the number.
For numbers which are multiple of both 3 and 5, print "FizzBuzz" instead of the number.
Solution:
public static void printFizzBuzz(int n) {
for(int i=1;i<=n;i++) {
if((i%3==0) && (i%5==0)) {
System.out.println("FizzBuzz");
}else if(i%3==0) {
System.out.println("Fizz");
}else if(i%5==0) {
System.out.println("Buzz");
}else {
System.out.println(i);
}
}
}
---------------------------------------------------------------------------------------------------------
Problem #2
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2,7,11,15], target = 9,
Because nums[0] + nums[1] = 2 + 7 =9,
return [0,1]
Solution:
public class GetTwoSum{
protected static int[] getTwoSum(int[] numbers, int target) {
//create a Map
Map<Integer, Integer>visitedNumbers = new HashMap<>();
for(int i = 0; i < numbers.length; i++) {
int delta = target - numbers[i];
if(visitedNumbers.containsKey(delta)) {
return new int[] {i, visitedNumbers.get(delta) };
}
visitedNumbers.put(numbers[i], i);
}
return new int[] {-1, -1};
}
public static void main(String[] args) {
printFizzBuzz(100);
int[] numbers = new int[] {2,3,7,4,8};
int target = 6;
int[] result = getTwoSum(numbers, target);
System.out.println(result[0] +" "+result[1]);
}
}
===============================================================
Problem # 3
ReverseString
public class Ch03ReverseString {
public static void main(String[] args) {
String str = "Hello World!";
System.out.println(reverseWithStringBuilder(str));
System.out.println(reverseManually(str));
}
private static String reverseManually(String str) {
// Create object fir StringBuilder
StringBuilder sb = new StringBuilder();
for(int i = str.length() - 1; i >= 0; i--) {
sb.append(str.charAt(i));
}
return sb.toString();
}
private static String reverseWithStringBuilder(String str) {
return new StringBuilder(str)
.reverse()
.toString();
}
}
----------------------------------------------------------------------------------------------------------------------
Problem #4
Implement a Stack in java
public class Stack {
private int array[];
private int top;
private int capacity;
Stack(int capacity){
this.array=new int[capacity];
this.capacity=capacity;
this.top=-1;
}
public void push(int item) {
if(isFull()) {
throw new RuntimeException("Stack is full");
}
array[++top]=item;
}
public boolean isFull() {
return top == capacity - 1;
}
/**
* Pop will return top item and remove from the stack and update the stack
* @return
*/
public int pop() {
if(isEmpty()) {
throw new RuntimeException("Stack is empty");
}
return array[top--];
}
/**
* peek will return the top item and wont remvoe the item from stack
* @return
*/
public int peek() {
if(isEmpty()) {
throw new RuntimeException("Stack is empty");
}
return array[top];
}
public boolean isEmpty() {
return top==-1;
}
}
-------------------------------------------------------------------------------------------------------------------
Problem # 5
Reverse an Integer
public class ReverseInteger {
public int reverse(int input) {
int reversed=0;
while(input!=0) {
reversed = reversed*10 + input % 10;
input /=10;
if(reversed > Integer.MAX_VALUE || reversed < Integer.MIN_VALUE) {
return 0;
}
}
return reversed;
}
public static void main(String[] args) {
System.out.println(new ReverseInteger().reverse(123));
}
}
-------------------------------------------------------------------------------------------------------------
Problem #6
Convert from Integer to Roman numeral
I -->1
II -->2
III -->3
IV -->4
V -->5
VI -->6
X -->10
L -50
C- 100
D -500
M -1000
public class IntegerToRoman {
public static String intToRoman(int num) {
String[] thousands = new String[]{"","M","MM","MMM"};
String[] hundreds = {"","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"};
String[] tens = {"","X","XX","XXX","XL","L","LX","LXX","LXXX","XC"};
String[] units = {"","I","II","III","IV","V","VI","VII","VIII","IX"};
return thousands[num / 1000] +
hundreds[(num%1000)/100] +
tens[(num % 100) / 10] +
units[num % 10];
}
public static void main(String[] args) {
System.out.println(intToRoman(124));
}
-----------------------------------------------------------------------------------------------------------------------
Problem # 7
Convert Roman numeral to Integer
public int romanToInt(String s) {
Map<Character,Integer>map = new HashMap();
map.put('I', 1);
map.put('V', 5);
map.put('X', 10);
map.put('L', 50);
map.put('C', 100);
map.put('D', 500);
map.put('M', 1000);
int result = 0;
for(int i=0;i<s.length();i++) {
if(i>0 && map.get(s.charAt(i)) >map.get(s.charAt(i-1))){
result += map.get(s.charAt(i)) - 2 *map.get(s.charAt(i-1));
} else {
result +=map.get(s.charAt(i));
}
}
return result;
}
=================================================================
Problem # 8
Longest Palindrome Substring
public class LongestPalindromeSubstring {
int resultStart;
int resultLength;
public String longestPalindrome(String s) {
int strLength = s.length();
if(strLength < 2) {
return s;
}
for(int start = 0; start < strLength -1; start++) {
expandRange(s,start,start);
expandRange(s,start,start + 1);
}
return s.substring(resultStart,resultStart + resultLength);
}
private void expandRange(String str, int begin, int end) {
while(begin >= 0 && end < str.length() && str.charAt(begin) == str.charAt(end)) {
begin--;
end++;
}
if(resultLength < end -begin -1) {
resultStart = begin +1;
resultLength = end - begin -1;
}
}
}
----------------------------------------------------------------------------------------------------------------------
Problem # 9:
Detect Capital
Given a word, you need to judge whether the usage of capitals in it is right or not.
Right Usage:
- All letters in this word are capitals
- All letters in this word are not capitals
- Only the first letter in this word is capital
public class DetectCapital {
/**
* Approach 1 : The "clever" solution
* Count the number of uppercase letters
* if it is zero or length of string, return true
* if it is not 1, return false
* if it is 1 and the first letter is uppercase, return true
* Time Complexity -- O(N)
* can we do better?
* Disadvantage:
* Quit at the first wrong character
* valid --AAAAA
* Valid : aaaa
* valid : Aaaaa
* @param word
* @return
*/
public static boolean detectCapitalUse(String word) {
int numberOfCapitals = 0;
for(int i = 0; i < word.length(); i++) {
if(Character.isUpperCase(word.charAt(i))) {
numberOfCapitals++;
}
}
if(numberOfCapitals == word.length() || numberOfCapitals == 0) return true;
return numberOfCapitals == 1 && Character.isUpperCase(word.charAt(0));
}
/**
* Approach 2:
*
*/
public static boolean detectCapitalUse2(String word) {
//Case 1 : All Capitals
int n = word.length();
if(Character.isUpperCase(word.charAt(0)) && Character.isUpperCase(word.charAt(1))) {
for(int i = 2; i< n; i++) {
if(Character.isLowerCase(word.charAt(i))) {
return false;
}
}
}else {
for(int i = 1; i<n;i ++) {
if(Character.isUpperCase(word.charAt(i))) {
return false;
}
}
}
return true;
}
/**
* Approach using LAMBDA
* Time Complexity - O(N)
* @param args
*/
public boolean detectCapitalUse3(String word) {
if(word.length() <= 1) return true;
Predicate<Character> correctCase = Character::isLowerCase;
if(Character.isUpperCase(word.charAt(0)) && Character.isUpperCase(word.charAt(1))) {
correctCase = Character::isUpperCase;
}
for(int i = 1; i < word.length(); i++) {
if(!correctCase.test(word.charAt(i))) return false;
}
return true;
}
