public class FirstWordUpperCase {
public static void main(String[] args) {
System.out.println(changeString("how are you man"));
}
private static String changeString(String str) {
StringBuffer sb = new StringBuffer();
String[] arr = str.split("\\s");
for (int i = 0; i < arr.length; i++) {
sb.append(Character.toUpperCase(arr[i].charAt(0))).
append(arr[i].substring(1)).append(" ");
}
return sb.toString();
}
}
Showing posts with label programs. Show all posts
Showing posts with label programs. Show all posts
Friday, 7 December 2018
Java program to capitalize first letter of each word in string
Wednesday, 26 September 2018
Odd Even switch using java multithreading
Consider there are two threads,
Even Thread
- Print only Even numbers
Odd Thread
- Print only Odd numbers
Print numbers from 1 to 50 by switching Odd and Even Threads,
Approach:
step 1. Create each threads with synchronized block
step 2. Create Monitor object with shared thread status and shared number
step 3. loop through mo.number and wait or execute based on the shared thread status
Even.java
public class Even implements Runnable {
private static MonitorObject mo = new MonitorObject();
public Even(MonitorObject mo) {
this.mo = mo;
}
public void run() {
try {
synchronized (mo) {
while (mo.number <= 50) {
if (!mo.isEven) {
mo.wait();
} else {
if (mo.number % 2 == 0) {
System.out.println(mo.number);
}
mo.number++;
mo.isEven = false;
mo.notifyAll();
}
}
}
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
Odd.java
public class Odd implements Runnable {
private static MonitorObject mo = new MonitorObject();
public Odd(MonitorObject mo) {
this.mo = mo;
}
public void run() {
try {
synchronized (mo) {
while (mo.number <= 50) {
if (mo.isEven) {
mo.wait();
} else {
if (mo.number % 2 != 0) {
System.out.println(mo.number);
}
mo.isEven = true;
mo.number++;
mo.notifyAll();
}
}
}
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
MonitorObject.java
public class MonitorObject {
public static boolean isEven = false;
public static int number = 0;
}
App.java
public class App {
private static MonitorObject mo = new MonitorObject();
public static void main(String[] args) {
mo.isEven = true;
Thread even = new Thread(new Even(mo));
even.start();
Thread odd = new Thread(new Odd(mo));
odd.start();
}
}
/*
****** OUTPUT ********
0,1,2,3,4,5,6,7,8,9...
******* OUTPUT ********
*/
Tuesday, 12 September 2017
Two Sum on arrays
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
Example:
Given nums = [ 3, 4, 5, 2, 10, 8, 9 ]
target = 19
Because nums[4] + nums[6] = 10 + 9 = 19, return [4, 6]
Approach:
step1. take 3 and then add 3 with all other elements
step2. take 4 and then add 4 with all other elements.Continue same till 9
TwoSum.java
public class TwoSum {
public static void main(String[] args) {
int[] arr = { 3, 4, 5, 2, 10, 8, 9 };
int target = 19;
TwoSum app = new TwoSum();
int[] rslt = app.twosum(arr, target);
System.out.print(rslt[0] + ", " + rslt[1]);
}
private int[] twosum(int[] arr, int target) {
int[] rslt = new int[2];
// take 3 and then add 3 with all other
// take 4 and then add 4 with all other elemnts.Continue same till 9
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length; j++) {
if (j != i) { // don't add the same indexes
int sum = arr[i] + arr[j];
if (sum == target) {
rslt[0] = i;
rslt[1] = j;
break;
}
}
}
}
return rslt;
}
}
/*
****** INPUT ********
{ 3, 4, 5, 2, 10, 8, 9 }
19
******* INPUT ********
****** OUTPUT ********
4, 6
******* OUTPUT ********
*/
Thursday, 7 September 2017
Find missing number between 1 to N with low time complexity
- Need to find missing number between 1 to N with low time complexity O(n).
- Step1: Get sum of natural numbers from 1 to N as N x(N+1)/2
- Step2: Get sum of array elements
- Step3: Missing number = natural numbers sum - array sum
public class FindMissingNumber {
private static final int END_NUMBER = 10;
private int getMissingNumber(int[] arr) {
int missingNum = 0;
int arrSum = 0;
for (int i = 0; i < arr.length; i++) {
arrSum += arr[i];
}
int naturalSum = END_NUMBER * (END_NUMBER + 1) / 2;
missingNum = naturalSum - arrSum;
return missingNum;
}
public static void main(String[] args) {
int[] arr = { 1, 2, 3, 0, 5, 6, 7, 8, 9, 10};
FindMissingNumber app = new FindMissingNumber();
int missingNum = app.getMissingNumber(arr);
System.out.println("Missing Number = " + missingNum);
}
}
****** OUTPUT ********
Missing Number = 4
******* OUTPUT ********
Set Implementation in Java
- Set conatins only unique elements.
- HashSet achieves uniqueness of its elements by using hashmap
- Whenever we create an object of hashset inernally it will create an object of hashmap.
- If we add an element into a set it will store as key for map. But same time we need a value for key. That value can be Object instance.So whenever we add an element to set it will create Hash map entry with key as added element and value as DUMMY Object.
-
There are two possible output we will get we put an entry into a hashmap
1. null: If the Key is unique and succussfully added to tha map. 2. Old Value of the Key: If the key is duplicate
package com.sk.custom_hashset;
import java.util.HashMap;
import java.util.Set;
public class SkHashSet {
private HashMap MAP = new HashMap();
private static final Object DUMMY = new Object();
public boolean add(E element) {
return MAP.put(element, DUMMY) == null;
}
public int size() {
return MAP.size();
}
public Set getAll() {
return MAP.keySet();
}
}
Wednesday, 6 September 2017
Java Hashmap Implementation
- Hashmap stores key value pairs
- HashMap uses hash to insert and get elements. hash = key.hashCode()%BUCKET_ARRAY_SIZE]
- Its an array of Entry LinkedList and each LinkedList identifies using hash. LinkedList will be stored in hash index of BUCKET_ARRAY
- Entries become LinkedList by keeping next entry in current entry.
Entry Class
It Make an Entry class to store the HashMap Entries.
Variable: key, value and next
All enties having the same hash[key.hashCode()%BUCKET_ARRAY_SIZE] linked together using next property having the type Entry. next will holds next entry.Always append new entry in last of linked List.
Put
Finding the bucket(Linked List) using hash[key.hashCode()%BUCKET_ARRAY_SIZE]
if entry is null in bucket then create new Entry and add to array with key.hashCode()%BUCKET_ARRAY_SIZE as key
if bucket already contains entry and key already existing then get entry and override value
if bucket already exists and key not contains then attach new entry at the end of the linkedList[looping till next become null]
Get
Finding the bucket(LinkedList) using hash[key.hashCode()%BUCKET_ARRAY_SIZE]
Loop entry till entry become and null and return value if key exists while looping
package com.sk.custom_hashmap;
public class Entry {
private final K key;
private V value;
private Entry next;
public Entry(K k, V v) {
key = k;
value = v;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
public Entry getNext() {
return next;
}
public void setNext(Entry next) {
this.next = next;
}
public K getKey() {
return key;
}
}
package com.sk.custom_hashmap;
import java.util.HashSet;
import java.util.Set;
public class SkHashMap {
private int BUKET_ARRAY_SIZE = 16;// initial capacity
private double LOAD_FACTOR = 0.75; // no.of entries/BUKET_ARRAY_SIZE
private Entry[] BUKET_ARRAY = new Entry[BUKET_ARRAY_SIZE];
@SuppressWarnings(value = { "unchecked" })
public void put(K key, V value) {
int hash = key.hashCode() % BUKET_ARRAY_SIZE; // finding bucket
Entry entry = BUKET_ARRAY[hash];
if (null == entry) {
/**
* creating a new Entry and add to array if the hash is not present
* in bucket array.
*/
BUKET_ARRAY[hash] = new Entry(key, value);
} else {
/**
* Overrides value if key already exists
*/
if (entry.getKey().equals(key)) {
entry.setValue(value);
} else {
/**
* need to append new Entry in the end.. So traverse across
* Entrys till Entry.next ==null
*/
while (entry.getNext() != null) {
entry = entry.getNext();
}
entry.setNext(new Entry(key, value));
}
}
}
@SuppressWarnings(value = { "unchecked", "unused" })
public V get(K key) {
V value = null;
int hash = key.hashCode() % BUKET_ARRAY_SIZE;
Entry entry = BUKET_ARRAY[hash];
while (null != entry) {
if (entry.getKey().equals(key)) {
return entry.getValue();
}
entry = entry.getNext();
}
return null;
}
@SuppressWarnings(value = { "unchecked" })
public Set> getEntrySet() {
Set> set = new HashSet>();
for (Entry enty : BUKET_ARRAY) {
Entry entrry = enty;
while (entrry != null) {
set.add(entrry);
entrry = entrry.getNext();
}
}
return set;
}
}
- Load Factor is a measure, which decides when exactly to increase the hashmap capacity(no.of buckets) to maintain get and put operation complexity of O(1).
- Default load factor of Hashmap is 0.75 (i.e 75% of current map size).
- Default capacity of Hashmap is 2^4 = 16 buckets.
- Let say we have well implemented hashcode() method, which make sure that key-value pair will be well distributed across 16 buckets equally.
- So, If there are 16 items in hashmap, then good hashcode method will distribute 1 item in each bucket. Searching for any item in this case will take only 1 look up.Now, If there are 32 items in hashmap, then good hashcode method will distribute 2 item in each bucket. Searching for any item in this case will take maximum 2 look up.Now, If there are 128 items in hashmap, then good hashcode method will distribute 8 item in each bucket. Searching for any item in this case will take maximum 8 look up.
- If the amount of item keeps on increasing and the number of buckets are fixed(16) then at one time, performance of hashmap will start degrading due to large number of items in each bucket.
- Now, say if there are 5,00,000 items in hashmap, then, good hashcode method will distribute 31,250 items in each bucket. Searching for any item in this case, will require maximum 31,250 look up. If we increase the total number of buckets, when total items in each bucket starts increasing, then we will be able to keep constant number of items in each bucket and maintain the time complexity of O(1) for get and put operation. The decision of "When to increase the number of buckets" is decided by Load Factor.
HashMap m = new HashMap(int initialCapacity, float loadFactor);
- Rehashing is the process of re-calculating the hashcode of already stored entries (Key-Value pairs), to move them to another bigger size hashmap when Load factor threshold is reached.
- When the number of items in map, crosses the Load factor limit at that time hashmap doubles its capacity and hashcode is re-calculated of already stored elements for even distribution of key-value pairs across new buckets.
HashMap Collision Occur
- There are several class in JDK which are based upon the hash table data structure
- HashMap,
- LinkedHashMap,
- Hashtable,
- WeakHashMap,
- IdentityHashMap,
- ConcurrentHashMap,
- TreeMap, and
- EnumMap.
- Underlying working of all these Map is pretty much same as discussed in How does HashMap internally works in Java, except some minor differences in their specific behaviors. Since hash table data structure is subject to collision all these implementations are required to handle the collision.
- A collision will occur when two different keys have the same hashCode, which can happen because two unequal objects in Java can have the same hashCode.
- HashMap handles collision by using linked list to store map entries ended up in same array location or bucket location
- From Java 8 onwards, HashMap, ConcurrentHashMap, and LinkedHashMap will use the balanced binary tree in place of linked list to handle frequently hash collisions. The idea is to switch to the balanced tree once the number of items in a hash bucket grows beyond a certain threshold. This will improve the worst case get() method performance from O(n) to O(log n).
- Legacy class Hashtable which exists in JDK from Java 1 will not use the balanced binary tree to handle frequent hash collision to keep its iteration order intact. This was decided to avoid breaking many legacy Java application which depends upon iteration order of Hashtable.
- Apart from Hashtable, WeakHashMap and IdentityHashMap will also continue to use the linked list for handling collision even in the case of frequent collisions.
- TreeMap
- Treemap class is like HashMap which stores key- value pairs . The major difference is that Treemap sorts the key in ascending order.
- It sorts the TreeMap object keys using Red-Black tree algorithm.
- We should read the pseudo code of Red Black algorithm in order to understand the internal implementation
- As the name of the algorithm suggests ,color of every node in the tree is either red or black.
- Root node must be Black in color.
- Red node can not have a red color neighbor node.
- All paths from root node to the null should consist the same number of black nodes
- Rotations maintains the inorder ordering of the keys(x,y,z).
- A rotation can be maintained in O(1) time.
- Why java's treemap does not allow an initial size ?
- HashMap reallocates its internals as the new one gets inserted while TreeMap does not reallocate nodes on adding new ones. Thus , the size of the TreeMap dynamically increases if needed , without shuffling the internals. So it is meaningless to set the initial size of the TreeMap .
- ConcurrentHashMap
- public ConcurrentHashMap (int initialCapacity, float loadFactor, int concurrencyLevel)
- So the above line creates a new, empty map with the specified initial capacity, load factor and concurrency level.
- initialCapacity - the initial capacity. The implementation performs internal sizing to accommodate this many elements.
- concurrencyLevel - the estimated number of concurrently updating threads. The implementation performs internal sizing to try to accommodate this many threads
- In the ConcurrentHashMap Api , you will find the following constants.
- static final int DEFAULT_INITIAL_CAPACITY = 16;
- static final int DEFAULT_CONCURRENCY_LEVEL = 16;
- Instead of a map wide lock, ConcurrentHashMap maintains a list of 16 locks by default ( number of locks equal to the initial capacity , which is by default 16) each of which is used to lock on a single bucket of the Map.
Wednesday, 30 August 2017
JUnit
- Unit testing is a process of testing a single unit in isolation by passing inputs to it. A unit can be a single method or a combination of methods.
- In Junit we will pass different inputs to a unit and checking whether we are getting expected output.
- The test files should be in a different folder. We don’t want to mix test and the src files. Because we are not going to deploy test classes.
- We can use any name to test classes. Usually we will create test class like “className+Test”.
- JUnit always success unless there is no condition. Junit Failure means we have condition in test method and it is failed.
- When a test method having multiple condition and the middle condition got failed. Then the remaining conditions will not process.
- If we made any changes in existing source code and we need to check whether it is working with all conditions. Then we just need to run JUnit and verify.
1.
Example
Class to be test(StringHelper.java)
public class StringHelper {
public String truncateInFIrst2Positions(String str) {
if (str.length() <= 2) {
return str.replaceAll("A", "");
}
String first2Charecters = str.substring(0, 2);
String stringMinusFirst2Charecters = str.substring(2);
return first2Charecters.replaceAll("A", "")
+ stringMinusFirst2Charecters;
}
public boolean areFirstAndLastTwoCharectersSame(String str) {
boolean output = false;
if (str.length() >= 4) {
String first2Chaecters = str.substring(0, 2);
String last2Charecters = str.substring(str.length() - 2);
if (first2Chaecters.equals(last2Charecters)) {
output = true;
}
}
return output;
}
} The Test Class
public class StringHelperTest {
private StringHelper helper=null;
@Before
public void before() {
helper = new StringHelper();
System.out.println("Executes Before");
}
@After
public void After() {
helper = null;
System.out.println("Executes After");
}
@BeforeClass
public static void beforeClass() {
System.out.println("Executes beforeClass");
}
@AfterClass
public static void AfterClass() {
System.out.println("Executes AfterClass");
}
@Test
public void truncateInFIrst2PositionsTest() {
System.out.println("truncateInFIrst2PositionsTest");
String expectedOutput = "RM";
String actualOutput = helper.truncateInFIrst2Positions("AARM");
Assert.assertEquals(expectedOutput, actualOutput);
Assert.assertEquals("WERT", helper.truncateInFIrst2Positions("WERT"));
Assert.assertEquals("WRM", helper.truncateInFIrst2Positions("AWRM"));
Assert.assertEquals("RM", helper.truncateInFIrst2Positions("ARM"));
Assert.assertEquals("AA", helper.truncateInFIrst2Positions("AAAA"));
}
@Test
public void areFirstAndLastTwoCharectersSameTest() {
System.out.println("areFirstAndLastTwoCharectersSameTest");
Assert.assertTrue(helper.areFirstAndLastTwoCharectersSame("WEERWE"));
Assert.assertFalse(helper.areFirstAndLastTwoCharectersSame("WEERUE"));
}
@Test
public void arraySortTest() {
int[] arr = {2,4,5,3,1};
Arrays.sort(arr);
int[] expectedOutput = {1,2,3,4,5};
Assert.assertArrayEquals(expectedOutput, arr);
}
@Test(expected=NullPointerException.class)
public void chkExceptionTest() {
int[] arr = null;
Arrays.sort(arr);
}
@Test(timeout=10)
public void arraySortPerformanceTest() {
for(int i=0; i<100000 arr="" arrays.sort="" code="" i-1="" i="" int="">Adding JUnit in Eclips
Right click your project in Package Explorer > click Properties
go to Java Build Path > Libraries tab
click on 'Add Library' button
select JUnit
click Next.
Annatations
@Test
It will tells the method is a test condition.
@Test(expected=NullPointerException.class)
Test will pass only if a NullPointerException has thrown.
@Test(timeout=10)
Test will pass only if the execution would complete within given timeout.
@Before
The void method which is annotated with @Before will execute before each test method.
@After
The void method which is annotated with @After will execute after each test method.
@BeforeClass
The void method which is annotated with @BeforeClass will execute before test class start execution.
@AfterClass
The void method which is annotated with @AfterClass will execute after test class execution.
Basic Asserts
Assert.assertEquals(expectedOutput, actualOutput)
Comparing expectedOutput vs actualOutput and pass only when both are equals.
Assert.assertArrayEquals(expectedOutput, actualOutput)
Comparing both arrays and pass only when both are equals.
Assert.assertTrue(boolean arg)
Pass condition only when the Boolean argument is true.
Assert.assertFalse(boolean arg)
Pass condition only when the Boolean argument is false.
Spy vs Mock
Mock
- Mock always returns default values. It cannot do anything what actual arraylist does.
- We can only stub the arrayList to some values.
- Mock is dummy implementation.
- No logics from object can be used.
- If we add one element then its size will not change.
@Test
public void mockTest() {
List mockList = Mockito.mock(ArrayList.class);
Assert.assertEquals(0, mockList.size());
Mockito.stub(mockList.size()).toReturn(5);
Assert.assertEquals(5, mockList.size());
}
Spy
- Spy will create an actual object and it will do all logical operations unlike mock does.
- We are able to add element and increase size. But this size can be change to mock size using stub.
- We can override actual values using stub.
- Spy will let the real logic to be done and also can be change real behavior when needed.
@Test
public void spyTest() {
List mockList = Mockito.spy(ArrayList.class);
mockList.add("SONU");
Assert.assertEquals(1, mockList.size());
Mockito.stub(mockList.size()).toReturn(5);
Assert.assertEquals(5, mockList.size());
}
Monday, 28 August 2017
Collections Scope
- Please go through this tutorial to understand the basic concept
- List returned by Arrays.asList(): it is documented not to support any removing or adding elements.
- If we update a list from a method X by calling another void method Y, list modification will be affected in the list object in the method X.
- Because the the same object memory is used when passing the reference. So java is Pass by value.
public class MemoryTest {
public static void main(String[] args) {
MemoryTest mt = new MemoryTest();
mt.scopeTest();
}
private void scopeTest() {
int numberInt = 2;
Integer numberInteger = 10;
List numberList = new ArrayList();
numberList.add(10);
numberList.add(20);
Student student = new Student();
student.setId(1);
student.setName("Sonu");
MemoryTest mt = new MemoryTest();
System.out.println("numberInt before = " + numberInt);
mt.modifyInt(numberInt);
System.out.println("numberInt after = " + numberInt);
System.out.println("numberInteger before = " + numberInteger);
mt.modifyInteger(numberInteger);
System.out.println("numberInteger after = " + numberInteger);
System.out.println("numberList before = " + numberList);
mt.modifyList(numberList);
System.out.println("numberList after = " + numberList);
System.out.println("student before = " + student);
mt.modifyStudent(student);
System.out.println("student after = " + student);
}
private void modifyInt(int i) {
i = 3;
}
private void modifyInteger(Integer i) {
i = 200;
}
private void modifyList(List list) {
list.add(100);
}
private void modifyStudent(Student student) {
student.setId(2);
student.setName("Sreenu");
}
}