coolguy
BAN USERBoth, Array and Map provides constant time access to the underline elements.
Truly speaking, a Map may very well be replace of an array at anytime, with index being the keys of the map.
However, if the focus is on exploring the data structures than we can use Tries.
Although, Tries works pretty much like a Map, it has a limitation that keys can only be Strings, which in this case should not be the problem as indices can easily be parsed into Strings.
public class Power{
public double power(int number, int n){
if(n < 0){
return 1 / powerUtil(number, n * -1);
}else if(n == 0){
return 1;
}else{
return powerUtil(number, n);
}
}
private double powerUtil(int number, int n){
if(n == 1){
return number;
}else if(n % 2 == 0){
return powerUtil(number * number, n / 2);
}else{
return number * powerUtil(number * number, n / 2);
}
}
public static void main(String[] args) {
Power p = new Power();
System.out.println(p.power(2,7));
}
}
import java.util.concurrent.locks.*;
import java.util.*;
public class MultiThread{
private static final Lock lock = new ReentrantLock();
private static final Condition isAvailable = lock.newCondition();
private static List<Integer> validNos = Arrays.asList(1,2,3);
private static int roundRobbin = 1;
private static int getNextNumber(int number){
if(number < 3){
return number + 1;
}else{
return 1;
}
}
private static boolean isValid(final Integer number){
return validNos.contains(number);
}
public static Runnable getRunnable(final Integer number){
if(!isValid(number)){
throw new IllegalArgumentException("Please provide a valid input: " + number);
}
return new Runnable(){
public void run(){
while(true){
try{
lock.lock();
while(roundRobbin != number){
isAvailable.await();
}
System.out.println(number);
roundRobbin = getNextNumber(number);
isAvailable.signalAll();
}catch(Exception e){
System.err.println("Error acquiring lock for : " + number);
}finally{
lock.unlock();
}
}
}
};
}
public static void main(String[] args) {
Thread t1 = new Thread(getRunnable(1));
Thread t2 = new Thread(getRunnable(2));
Thread t3 = new Thread(getRunnable(3));
t1.start();
t2.start();
t3.start();
}
}
We can optimize this further by adding swap before the increment or decrement begins.
To exemplify, imagine a = 100000, b = 1 ==> then we would increment b 100000 times, instead we can introduce a swap and instead increment a by 1.
public static int sum(int a, int b){
if(a > b){
int temp = a;
a = b;
b = temp;
}
while(a > 0) { --a; ++b; };
while(a < 0) { ++a; --b; };
return b;
}
Simple O(n^2) solution.
On a closure observation, this is a sub-quadratic solution
public Node contructIternary(List<Node> tickets){
if(tickets == null || tickets.isEmpty()){
return null;
}
Node startNode = tickets.get(0);
Node endNode = tickets.get(0);
tickets = tickets.subList(1, tickets.size());
while(!tickets.isEmpty()){
for(Iterator<Node> ticketsItr = tickets.iterator(); ticketsItr.hasNext()){
Node ticket = tickets.next();
if(startNode.start.equals(ticket.end)){
startNode.prev = ticket;
startNode = ticket;
ticketsItr.remove();
}else if(endNode.equals(ticket.start)){
endNode.next = ticket;
endNode = ticket;
ticketsItr.remove();
}
}
}
return startNode;
}
import java.util.*;
public class FirstAndLastNodeLevelTree<T>{
private Node<T> root;
private static class Node<T>{
T value;
Node left;
Node right;
Node(){}
Node(T value){
this.value = value;
}
Node(T value, Node left, Node right){
this.value = value;
this.left = left;
this.right = right;
}
public String toString(){
return this.value + "";
}
}
//S(n) = O(n)
Map<Integer, ArrayList<T>> map = new LinkedHashMap<Integer, ArrayList<T>>();
//T(n) = O(n)
public void printFirstAndLastNode(Node<T> root){
this.printFirstAndLastNodeUtil(1, root);
for(Integer level : map.keySet()){
ArrayList<T> elements = map.get(level);
if(elements.size() == 1){
System.out.println("root:" + elements.get(0));
}else{
System.out.println("Level:" + level + " First: " + elements.get(0) + " Last:" + elements.get(elements.size() - 1));
}
}
}
private void printFirstAndLastNodeUtil(Integer level, Node<T> root){
if(root == null){
return;
}
ArrayList<T> elements = map.get(level);
if(elements == null){
elements = new ArrayList<T>();
elements.add(root.value);
map.put(level, elements);
}else{
elements.add(root.value);
}
printFirstAndLastNodeUtil(level + 1, root.left);
printFirstAndLastNodeUtil(level + 1, root.right);
}
public static void main(String[] args) {
Node<Integer> rootNode = new Node<Integer>(50);
rootNode.left = new Node(30);
rootNode.right = new Node(90);
rootNode.left.left = new Node(20);
rootNode.left.right = new Node(40);
rootNode.right.left = new Node(85);
rootNode.right.right = new Node(100);
FirstAndLastNodeLevelTree<Integer> f = new FirstAndLastNodeLevelTree<Integer>();
f.printFirstAndLastNode(rootNode);
}
}
Output:
java FirstAndLastNodeLevelTree
root:50
Level:2 First: 30 Last:90
Level:3 First: 20 Last:100
import java.util.Arrays;
public class MaxArray{
// T(n) = O(N+1 * logN)
public int [] maximizeArray(int [] arr1, int [] arr2){
if(arr1 == null || arr2 == null || arr1.length == 0){
return null;
}
Arrays.sort(arr2);
int index2 = arr2.length - 1;
for(int i = 0; i < arr1.length; i++){
if(index2 >= 0 && arr1[i] < arr2[index2]){
arr1[i] = arr2[index2];
index2--;
}
}
return arr1;
}
public static void main(String[] args) {
MaxArray m = new MaxArray();
int [] arr1 = { 3, 1, 4, 5, 6};
int [] arr2 = { 2, 9 };
System.out.println(Arrays.toString(m.maximizeArray(arr1, arr2)));
}
}
import java.util.List;
import java.util.ArrayList;
public class FindConsecutiveRanges{
public List<String> findConsecutiveRanges(int [] arr){
if(arr == null || arr.length == 0){
return null;
}
int startIndex = 0;
int n = arr[startIndex];
List<String> results = new ArrayList<String>();
for(int i = 1; i < arr.length; i++){
if(arr[i] != n + 1){
if(i - startIndex < 2){
results.add(n + "");
}else{
results.add(arr[startIndex] + " - " + n);
}
startIndex = i;
}
n = arr[i];
}
if(arr[startIndex] != arr[arr.length - 1]){
results.add(arr[startIndex] + " - " + n);
}else{
results.add(n + "");
}
return results;
}
public static void main(String[] args) {
FindConsecutiveRanges f = new FindConsecutiveRanges();
int [] arr = {1, 2, 3, 7, 11, 21};
System.out.println(f.findConsecutiveRanges(arr));
}
}
public class Panagram{
//T(n) = O(n); // n is the length of the string
//S(n) = O(n);
//Assumes that input string has only ASCII characters
public static boolean isPanagram(String str){
int [] counts = new int[256];
char [] charArr = str.toCharArray();
for(int i = 0; i < charArr.length; i++){
if(charArr[i] >= 97 && charArr[i] <= 122){
charArr[i] -= 32;
}
counts[charArr[i]]++;
}
for(int i = 65; i <= 90; i++){
if(counts[i] < 1){
return false;
}
}
return true;
}
public static void main(String[] args) {
System.out.println(Panagram.isPanagram("The quiCk brown fox jumps over the little lazy dog"));
}
}
class MergeList{
private List<List<Integer>> listOfLists = new ArrayList<ArrayList<Integer>>();
private List<Integer> output = new ArrayList<Integer>();
public void readInput(){
this.listOfLists = intializeInput(); // TODOs
}
// T(n) = m * O(n); where m = # of sorted Lists
public List<List<Integer>> mergeAll(){
for(int i = 0; i < listOfLists.length(); i++){
this.output = merge(this.output, listOfLists.get(i));
}
return this.output;
}
// T(n) = O(n); where n is the length of the longest sortedList
private List<Integer> merge(List<Integer> list1, List<Integer> list2){
List<Integer> list = new ArrayList<Integer>();
int i = 0, int j = 0;
for(; i < list1.length() && j < list2.length();){
Integer element1 = list1.get(i);
Integer element2 = list2.get(j);
if(element1 < element2){
list.add(element1);
i++;
}else{
list.add(element2);
j++;
}
}
if(i == list1.length()){
// list1 is expended
for(; j < list2.length(); j++){
list.add(list2.get(j));
}
}
if(j == list2.length()){
// list2 is expended
for(; i < list1.length(); i++){
list.add(list1.get(i));
}
}
return list;
}
}
var clone = function(object){
var newObject = {};
for(var key in object){
newObject[key] = object[key];
}
return newObject;
}
var deepClone = function(object){
var newObject = {};
for(var key in object){
if(typeof object[key] === 'object'){
newObject[key] = deepClone(object[key]);
}else{
newObject[key] = object[key];
}
}
return newObject;
}
- coolguy November 14, 2015