Infinite Possibilities
BAN USERContact class for key : - have overridden the equals and hashcode method accordingly
public class Contact {
public String name;
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int hashCode(){
return name.length();
}
public boolean equals(Object o){
if(o instanceof Contact){
Contact c = (Contact)o;
String name = this.getName();
if(c.getName().equals(name) || (c.getName().toLowerCase()).equals(name.toLowerCase())){
return true;
}
}
return false;
}
@Override
public String toString() {
// TODO Auto-generated method stub
return this.getName();
}
}
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
public class PhoneDirectory {
static Map<Contact, List<Integer>> phoneDirectory = new HashMap<Contact, List<Integer>>();
public static void main(String[] args) {
addToDirectory("ABc", 123);
addToDirectory("bcd", 345);
addToDirectory("cba", 523);
addToDirectory("abc", 678);
Iterator<Contact> it = phoneDirectory.keySet().iterator();
while (it.hasNext()) {
Contact contact = (Contact) it.next();
System.out.println(contact +" "+phoneDirectory.get(contact));
}
Contact c = new Contact();
c.setName("abc");
System.out.print(phoneDirectory.get(c));
}
public static void addToDirectory(String name,int number){
Contact contact = new Contact();
contact.setName(name);
if(phoneDirectory.get(contact) != null){
List<Integer> numberList = phoneDirectory.get(contact);
numberList.add(number);
}else{
List<Integer> numberList = new ArrayList<Integer>();
numberList.add(number);
phoneDirectory.put(contact, numberList);
}
}
}
import java.util.HashMap;
import java.util.Map;
public class CountWords {
public static void main(String[] args) {
String arr[] = {"Good","woRD","good","GOod","test","word"};
countWords(arr);
}
public static void countWords(String arr[]){
Map<String, Integer> map = new HashMap<String, Integer>();
String temp = null;
for (int i = 0; i < arr.length; i++) {
temp = arr[i];
temp = temp.toLowerCase();
if(map.get(temp) != null ){
Integer count = map.get(temp);
map.put(temp, ++count);
}else{
map.put(temp, 1);
}
}
System.out.print(map);
}
}
//We will use a tree map
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
public class EmployeeHierarchy {
/* Key = Manager ID
* Value = List of Employees under the manager
*/
static Map<Integer, List<String>> employeeMap = new TreeMap<Integer, List<String>>();
public static void main(String[] args)throws Exception {
populateEmployeeHierarchyMap();
//Getting all manager ID's
Iterator<Integer> it = employeeMap.keySet().iterator();
while(it.hasNext()){
Integer i = it.next();
List<String> list = employeeMap.get(i);
Iterator<String> employees = list.iterator();
while(employees.hasNext()){
System.out.print(employees.next() +" ");
}
System.out.println("");
}
}
public static void populateEmployeeHierarchyMap()throws Exception{
File file = new File("EmployeeData.txt");
file.createNewFile();
BufferedReader br = new BufferedReader(new FileReader(file));
String str;
List<String> temp;
int skipLine = 0;
while((str = br.readLine()) != null){
if(skipLine++ == 0)continue;
List<String> list = new ArrayList<String>();
String employeeData[] = str.split(" ");
if(employeeData[2] != null && !employeeData[2].equals("Null")){
//System.out.println(employeeData[2]);
Integer i = Integer.parseInt(employeeData[2]);
temp = employeeMap.get(i);
}else{
temp = employeeMap.get(0);
}
if( temp == null){
Integer managerId;
if(employeeData[2] == null || employeeData[2].equals("Null")){
managerId = new Integer(0);
}else{
managerId = new Integer(employeeData[2]);
}
list.add(employeeData[1]);
employeeMap.put(managerId,list);
}else{
temp.add(employeeData[1]);
}
}
}
}
/*
* This class represents intervals
* For eg : Car A start time 12:00 and end time 1:30
* Car B start time 2:50 and end time 3:30
* Car A start time 7:00 and end time 8:30
* There will be 3 interval objects two for Car A(as 2 different intervals) and one for Car B
*/
public class Interval {
public Interval(float startTimehrs,float startTimeMin,float endTimehrs,float endTimeMin,String carNumber) {
this.startTimehrs = startTimehrs;
this.startTimeMin = startTimeMin;
this.endTimehrs = endTimehrs;
this.endTimeMin = endTimeMin;
this.carNumber = carNumber;
}
public float startTimehrs;
public float startTimeMin;
public float endTimehrs;
public float endTimeMin;
public String carNumber;
}
public class CarRentalPlanner {
/*
* We will have a 2d array of 24 rows where each row represents time interval(we are following 24 hr format)
* and carRentalData[row][0] will store bookings
* carRentalData[row][0] will store returns
* carRentalData[row][1] will store time on road
*/
static float carRentalData[][] = new float[24][3];
public static void main(String[] args) {
Interval interval = new Interval(2,50,9,40,"XYZ");
pouplateCarRentalData(interval);
/*
* We can populate the CarRentalArray by iterating over the intervals
* we can find the max on road time from carRentalData[perios][2]
*/
}
public static void pouplateCarRentalData(Interval interval){
int startTime = (int)(interval.startTimehrs);
int endTime = (int)interval.endTimehrs;
float onRoadTime = 0;
int temp = startTime;
float bookings = carRentalData[startTime][0];
carRentalData[startTime][0] = ++bookings;
float returns = carRentalData[endTime][1];
carRentalData[endTime][1] = ++returns;
/*
* For calculating the on road time during a period i am using weighted time for a better solution
* eg : - Start Time - 4:30 , End Time - 8:15
* time periods impacted - 5
* 4 - 5 On road time : - (30/60)/5 - (min/60)/overlapping periods
* 5 - 6 1/5
* 6 - 7 1/5
* 7 - 8 1/5
* 8 - 9 (15/60)/5
*
*/
int timeIntervalsOverlap = endTime - startTime;
int timeIntervalsOverlapActual = timeIntervalsOverlap+1;
for (int i = 1; i < timeIntervalsOverlap; i++) {
onRoadTime = carRentalData[++temp][2];
onRoadTime += (1F/timeIntervalsOverlapActual);
carRentalData[temp][2] = onRoadTime;
}
onRoadTime = carRentalData[startTime][2];
onRoadTime += (interval.startTimeMin/60)/timeIntervalsOverlapActual;
carRentalData[startTime][2] = onRoadTime;
onRoadTime = carRentalData[endTime][2];
onRoadTime += (interval.endTimeMin/60)/timeIntervalsOverlapActual;
carRentalData[endTime][2] = onRoadTime;
}
}
public void printSecondLastNode(Link root){
Link current = root;
boolean flag = true;
while(current != null){
if(current.next != null && current.next.next == null){
System.out.print("Second Last Node is : ");
current.displayData();
flag = false;
break;
}
current = current.next;
}
if(flag)
System.out.print("List is too small");
}
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
public class SquareRoot {
public static int squareRoot ;
public static void main(String[] args) {
System.out.println(squareRoot(1009));
System.out.println(Math.sqrt(1009));
}
/*This method gives an approximation of square root
* Squareroot(number) = squareroot(nearest perfect square) + ( Difference between number and perfect square
* /(2*squareroot(nearest perfect square)))
* This formula has been derived using differentiation
*/
public static double squareRoot(int number){
int num = number;
while(!isPerfectSquare(num)){
num --;
}
double diff = number - (squareRoot*squareRoot);
double divisor = squareRoot*2;
return (squareRoot + (diff/divisor));
}
/*
* This method checks whether a number is a perfect square or not
*/
public static boolean isPerfectSquare(int number){
int quotient = number;
int divisor = 2;
int sqrt = 1;
Map<String, Integer> map = new HashMap<String, Integer>();
//Calculate the factors
while(quotient != 1){
if(quotient%divisor == 0){
quotient = quotient/divisor;
if(map.get(divisor+"") == null){
map.put(divisor+"",1);
}else{
int count = map.get(divisor+"");
map.put(divisor+"", ++count);
}
divisor = 2;
}else{
divisor++;
}
}
Iterator<String> it = map.keySet().iterator();
while(it.hasNext()){
String key = it.next();
int count = map.get(key);
Integer i = new Integer(key);
int k = 1;
for (int j = 0; j < count/2; j++) {
k *= i;
}
sqrt *= k;
if(count%2 != 0){
return false;
}
}
squareRoot = sqrt;
return true;
}
}
public class SpiralMatrix {
public static void main(String[] args) {
int arr[][] = {{1,2,3,4,5},{10,9,8,7,6},{11,12,13,14,15},{20,19,18,17,16},{21,22,23,24,25}};
int rowCount = arr.length;
int spiralLevel = arr.length -2;
int row = 1;
//Print first part
int count = arr[0].length;
for (int i = 0; i < count; i++) {
System.out.print(arr[0][i] + " ");
}
//Print second part
for (int i = 1; i < rowCount-1; i++) {
int index = arr[i].length;
System.out.print(arr[i][index-1] + " ");
}
//Print third part
int lastRowCol = arr[rowCount-1].length - 1;
while (lastRowCol >= 0) {
System.out.print(arr[rowCount -1][lastRowCol] +" ");
lastRowCol--;
}
//Print fourth part
int rowCount1 = rowCount - 2;
while(rowCount1 > 0){
System.out.print(arr[rowCount1][0] + " ");
rowCount1 --;
}
//print spiral
for (int i = 0; i < spiralLevel; i++) {
if(row%2 != 0){
for (int j = 1; j < arr[row].length-1; j++) {
System.out.print(arr[row][j]+ " ");
}
}else{
for (int j = arr[row].length-2; j >0; j--) {
System.out.print(arr[row][j]+ " ");
}
}
row++;
}
}
}
This is done in O(n) but uses extra space(HashMap)
public static void main(String[] args) {
int arr[] = {1,2,3,4,5,5,5,6,7,7};
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < arr.length; i++) {
if(map.get(arr[i]) == null){
map.put(arr[i], 1);
}else{
int count = map.get(arr[i]);
map.put(arr[i], ++count);
}
}
Iterator<Integer> it = map.keySet().iterator();
while (it.hasNext()) {
Integer integer = (Integer) it.next();
int count = map.get(integer);
if(count > 1){
System.out.println(integer + " is repeated "+ count+" times");
}
}
}
We can use a HashMap/HashTable with name as the key (since name is unique) and phone number as the value.
- Infinite Possibilities July 14, 2015This method taken in the number as the parameter and returns whether the number is of the power of two or not.
public static boolean isTwoPower(int num){
while(true){
int q = num/2;
int r = num%2;
if(r != 0){
return false;
}
if(q == 1){
return true;
}
num = q;
}
}
I am also not sure whether it is possible in O(n)
my solution will be in O(m*n) :-
import java.util.ArrayList;
import java.util.List;
public class Test {
public static void main(String args[]){
int arr[][]= {{10,11,12},{1,7,9},{11,12,12},{13,13,13}};
for (int i = 0; i < arr.length; i++) {
if(subArray(arr[i])){
for (int j = 0; j < arr[i].length; j++) {
System.out.print(arr[i][j] + " ");
}
}
System.out.println();
}
}
public static boolean subArray(int arr[]){
boolean unique = true;
List<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < arr.length; i++) {
if(list.contains(arr[i])){
return false;
}else {
list.add(arr[i]);
}
}
return unique;
}
}
import java.util.*;
public class CSV implements Comparable<CSV>{
private String name;
private int age;
public CSV(String name,int age){
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public int compareTo(CSV o) {
if(this.age > o.getAge()){
return 1;
}else if(this.age < o.getAge()){
return -1;
}
return 0;
}
@Override
public String toString() {
return this.name + " "+this.age;
}
public static void main(String[] args) {
CSV ob1 = new CSV("Alice",30);
CSV ob2 = new CSV("Bob",17);
CSV ob3 = new CSV("Clyde",49);
List<CSV> list = new ArrayList<CSV>();
list.add(ob1);
list.add(ob2);
list.add(ob3);
Collections.sort(list);
System.out.print(list);
}
}
Also if it mentions divisible by 1 u can directly return the number u take in as input since all numbers are divisible by 1.
- Infinite Possibilities October 03, 2014If the problem says divisible by 2 and 3 and 5 ..... then it is pretty straightforward.
Th code for it is :-
import java.util.Scanner;
public class UglyNumbers {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.println("Enter a Number ");
int n = in.nextInt();
System.out.print("Nth number of ugly series is : "+uglyNumber(n));
}
public static int uglyNumber(int n){
/* Since the LCM of 1,2,3,5 is 30
* The smallest ugly number is 30
* and all ugly numbers would be a
* multiple of 30
*/
return 30 * n;
}
}
O(n) using extra memory : -
- Infinite Possibilities October 10, 2015import java.util.HashSet;
import java.util.Set;
public class AllPairs {
public static void main(String[] args) {
int k = 3;
int arr[] = {1,2,3,5,6,8,9,11,12,13};
findPairs(arr,k);
}
public static void findPairs(int arr[],int k){
if(!(arr.length > 0))return;
Set<Integer> set = new HashSet<Integer>();
set.add(arr[0]);
for (int i = 1; i < arr.length; i++) {
if(set.contains(arr[i]-k)){
System.out.println(arr[i]-k + " , "+arr[i]);
}
set.add(arr[i]);
}
}
}