Mayank Jain
BAN USERThis does not works for "2)(3+4)(5"
- Mayank Jain September 24, 2017Shouldn't we just use a LinkedHashSet<Object> set instead ?
1. For ever insert : check if set.contains(o1)
=> if true : remove it (since it is no longer unique now).
=> if false : add to the set using set.add(o1)
2. To get first unique , Iterator i = set.iterator; print(i.next())
/*
* Traverse Tree
* Keep Track of MaxSoFar and MaxDiff
*
*/
public class BinaryTreeMaxDiffBetweenAndNodeAncestor {
public static int getMaxDiffNodeAndAncestor(Node root, int maxSoFar, int maxDiff){
if(root==null){
return maxDiff;
}else{
maxDiff=Math.max(maxDiff, maxSoFar-root.data);
maxSoFar=Math.max(maxSoFar, root.data);
return Math.max(getMaxDiffNodeAndAncestor(root.leftChild,maxSoFar,maxDiff),
getMaxDiffNodeAndAncestor(root.rightChild, maxSoFar, maxDiff));
}
}
public static void main(String[] args) {
Node root = new Node(8);
root.rightChild=new Node(10);
root.rightChild.rightChild=new Node(14);
root.rightChild.rightChild.leftChild=new Node(13);
root.leftChild=new Node(3);
root.leftChild.leftChild=new Node(1);
root.leftChild.rightChild=new Node(6);
root.leftChild.rightChild.rightChild=new Node(7);
root.leftChild.rightChild.leftChild=new Node(4);
int maxDiff = getMaxDiffNodeAndAncestor(root,0,0);
System.out.println(maxDiff);
}
static class Node{
int data;
Node leftChild;
Node rightChild;
Node(int data){
this.data = data;
}
}
}
1. Keep adding elements to the array/Queue until its full
[1,4,6,7] front =0, rear=3
2. When full, delete one element and add a new element
[4,6,7,8(this is the 0th index if circular)] front =1, rear=0
3. If now, the rear index < front index, Queue is circular
rear =0 < front =1
public class HexaDecimalToInteger {
public static void convertToDecimal(String hexStr){
int maxPower = hexStr.length()-1;
int sum=0;
for(int i=0;i<=hexStr.length()-1;i++){
int digit=0;
if(hexStr.charAt(i) >= '0' && hexStr.charAt(i) <= '9'){ // between 0 and 9
digit = hexStr.charAt(i) - '0';
}else{ // between A and E
digit = 10 + (hexStr.charAt(i) - 'A');
}
sum = sum*16 + digit; // optimized way to convert
}
System.out.println("Decimal : " + sum);
}
public static void main(String[] args) {
String hexStr ="23AE";
convertToDecimal(hexStr);
}
}
deadlock can be detected by analyzing thread dumps. We can us
jstack -l PID > file.txt
To get the thread dump.
Or use utility called jvisualvm on mac
1. Make a HashMap of word,count
2. Create a WordObject class as [word, count]
3. Create a Max heap (Priority Queue), which is fort sorted by count and then by word alphabetically
4. One by one add from Map to PQ
5. One by One remove from PQ to get the result
import java.util.*;
public class WordCount {
public static void getWordCount(List<String> list){
HashMap<String,Integer> wordToCountMap = new HashMap<String,Integer>();
//Build word,count map
for(String word : list){
if(wordToCountMap.containsKey(word)){
int count = wordToCountMap.get(word);
wordToCountMap.put(word, count+1);
}else{
wordToCountMap.put(word, 1);
}
}
//Make max count Priority Queue which is sorted by counts and then by string alphabetically
PriorityQueue<WordObject> maxPQ = new PriorityQueue<WordObject>(new Comparator<WordObject>(){
public int compare(WordObject o1, WordObject o2){
// sort on count and the alphabetically
if(o1.count > o2.count){
return -1;
}else if(o1.count < o2.count){
return 1;
}else{
return o1.word.compareTo(o2.word); // sort alphabetically
}
}
});
//add one by one to Max PQ
for(String word : wordToCountMap.keySet()){
maxPQ.add(new WordObject(word, wordToCountMap.get(word)));
}
//Build the result
List<String> result = new ArrayList<String>();
while(!maxPQ.isEmpty()){
result.add(maxPQ.remove().word);
}
//Print
System.out.println(result.toString());
}
public static void main(String[] args) {
List<String> wordList = new ArrayList<String>();
wordList.add("Dinesh");
wordList.add("Poornesh");
wordList.add("Rahul");
wordList.add("Dinesh");
wordList.add("Moezhi");
wordList.add("Rahul");
getWordCount(wordList);
}
}
//Occurrences
class WordObject{
String word;
int count;
WordObject(String word , int count){
this.word = word;
this.count = count;
}
}
/* // O(n) and no extra space
* Solution is same as in case when we have 0 to n-1 element in size n array
* In here if any arr[i] > size of arr ,we do not mark its index as negative since that
* index is not in array. but mark of others.
* Also, shift all negative numbers to the right of array and clip the array
*
*
*/
import java.util.*;
public class MinMissingInteger {
public static void findMinMissing(int[] arr){
//Move -ve number to end of array either shift or just remove
int ctr=0;
for(int i=0;i<=arr.length-1;i++){
if(arr[i]>0){
arr[ctr] = arr[i];
ctr++;
}
}
//array with positive numbers is till ctr-1
int maxEndLength=ctr-1; // max length of positive numbers
//Mark kth index where k=arr[i] and is in array's range
//Since +ve numbers start from 1 and array index from 0, we mark k-1 index as negative
for(int i=0;i<=maxEndLength;i++){
int index = Math.abs(arr[i])-1; // minus 1, element may be marked negative so check abs value
if(index <= maxEndLength){
arr[index] = -1*arr[index];
}
}
//find the first missing positive number
int firstMissingIndex=0;
for(int i=0;i<=maxEndLength;i++){
if(arr[i]>0){
firstMissingIndex=i+1; // since we subtracted 1
break;
}
}
System.out.println("Missing value = " + firstMissingIndex);
}
public static void main(String[] args) {
int[] arr = {1,9,2,5,7};
findMinMissing(arr);
}
}
1. Keep a counter i which tells the position from where we should look for two character and find their conversion. Eg; ABCB, i=0 means we will loop for (i)th and (i+1)th chars i.e AB and get the movement as AB->C , so result is "C"CB.
2. When we cannot convert from current ith posistion i.e in CCB if i=0, "CC" cannot to converted to a valid move , so call recursively for i+1 i.e i=1 and now we can convert 1th and 2th chars (CB) to A, hence result is C"A" and so on.
3. keep checking in every step if str does not contains all same chars, here is string is invalid now and cannot be further reduced like .. AAA , BB , CCC etc.
import java.util.*;
public class StringSequenceToChar {
static HashMap<String,String> map = new HashMap<String,String>();
static {
map.put("AB","C");
map.put("BA","C");
map.put("AC","B");
map.put("CA","B");
map.put("BC","A");
map.put("CB","A");
}
public static String convert(String str){
if(map.containsKey(str)){
return map.get(str);
}else{
return null;
}
}
public static int getPath(String str, int i , int steps){
//Conversion done
if(str.length()==1){
return steps;
}
//Check if all chars are same, cannot convert // Imp
int ctr=0;
for(int k=1;k<=str.length()-1;k++){
if(str.charAt(k-1) != str.charAt(k)){
break; // Optimization
}else{
ctr++;
}
}
if(ctr==str.length()-1){
return -1;
}
//we kept increasing i and it is beyond length-1
if(i> (str.length()-1)-1){
i=0;
}
String result = convert(str.substring(i, i+2));
int res=0;
if(result!=null){
res = getPath(str.substring(0,i)+result+str.substring(i+2,str.length()) ,i,steps+1);
}else{
res = getPath(str ,i+1,steps);
}
if(res < 0){
return -1;
}else{
return res;
}
}
public static void main(String[] args) {
System.out.println(getPath("ABACB",0,0));
System.out.println(getPath("AAA",0,0));
System.out.println(getPath("AAC",0,0));
System.out.println(getPath("BB",0,0));
}
}
II. Someone put distribute Random()*ID in a Hive script to prevent data skew. What would be the problem here?
Problem here is , same id will get different partition number if using Random()*ID and hence will go to different reducers. Aggregation functions based on ID will result in incorrect results.
- Mayank Jain August 20, 2017Steps:
1. Iterate over the given String dictionary, sort each word, and add the sorted word as key and original word as List of values . Since sorted sequence of many words(car,arc) can be same , all those values are added to the same key(sorted string , acr) and values will be list of string(car,arc).
2. Iterate over the given string and keep building string of lengh 0,1 , 2.... for each such substring , sort it and check if it is in the map we constructed
3. If yes, the check for the left over String and result=no of elements(list size) in the values for the current substring as key *(multiply) no of elements(list size) in the values for the result obtained from left over String
4. If no, continue to build the string and repeat step 3
import java.util.*;
public class StringSegmentationShuffle {
static String[] dict = {"car","arc","hello","hi"};
public static int findPossibleCombinations2(String str, HashMap<String,List<String>> map){
if(str.length()==0){
return 1;
}
for(int i=1;i<=str.length();i++){
String subString=str.substring(0,i);
char[] subStringCharArray = subString.toCharArray();
Arrays.sort(subStringCharArray);
String subStringSorted = new String(subStringCharArray);
if(map.containsKey(subStringSorted)){
String leftOver = str.substring(i,str.length());
int result = findPossibleCombinations2(leftOver,map);
if(result != -1){
return map.get(subStringSorted).size() * result;
}
}
}
return -1;
}
public static void main(String[] args) {
String str ="ymcra"; // my car , my arc : each word is shuffled first individually ( my=>ym and car=> cta) and then added to string
HashMap<String,List<String>> map = new HashMap<String,List<String>>();
for(int i=0;i<str.length()-1;i++){
String s = dict[i];
char[] sCharArray = s.toCharArray();
Arrays.sort(sCharArray);
String sortedString = new String(sCharArray);
if(map.containsKey(sortedString)){
map.get(sortedString).add(s);
}else{
List<String> list = new ArrayList<String>();
list.add(s);
map.put(sortedString,list);
}
}
System.out.println(findPossibleCombinations2(str,map));
}
}
keep calculating currentSum until :
1. Either currentSum = desired sum
2. or if currentSum > desired sum , reset currentSum= value of current element(i.e we are starting out check sub-sequence from here)
3. or if currentSum < desired sum , keep adding next element
public class FindSumContinousArray {
public static void findContinuousSubArray(int[] arr , int sum){
int iCuurent=0;
int jCurrent=0;
int curSum=0;
while(iCuurent <= arr.length-1 && jCurrent <= arr.length-1){
curSum = curSum + arr[jCurrent]; // find new sum including current element
if(curSum == sum){
System.out.println("Sum found from elemen : " + iCuurent +" " +jCurrent);
return;
}else if(curSum > sum){
iCuurent = jCurrent; // start from current element new sum
curSum = arr[jCurrent];
jCurrent++;
}else{ // continue to include next element
jCurrent++;
}
}
}
public static void main(String[] args) {
int[] arr = {1,3,5,2,4};
findContinuousSubArray(arr,6);
}
}
public static void permute(String[] arr , int depth , String result){
if(depth==arr.length){
System.out.println(result);
return;
}
for(int i=0;i<=arr[depth].length()-1;i++){
permute(arr, depth+1, result+arr[depth].substring(i,i+1));
}
}
public static void main(String[] args) {
String[] arr = {"red", "fox", "super" };
permute(arr,0,"");
}
/* Algo:
* 1. Start constructing the seed string such that each char in seed matches the char in dict and that too at the right position.
* Assuming the machine function(matchStr) tells the count of chars in given string which are at the right index of dict word.
* If char at 0th index is matched , try for the 1st index. To know if the char is matched, matchedCount > matchedSoFar
* 2. If mactchedSoFar == dictWordLengt. We have guessed the word
*/
public class WordGameMachine2 {
static String dictWord = "daddy";
public static int matchStr(String str){
int cnt=0;
for(int i=0;i<=str.length()-1;i++){
if(dictWord.charAt(i) == str.charAt(i)){
cnt++;
}
}
return cnt;
}
public static void guessWord(){
int guessWordLen = dictWord.length();
// Find a seed of chars containing same chars in the same order as in the dict string
String seed="";
int maxMatchedSoFar=0;
for(char c='a';c<='z';c++){
if(maxMatchedSoFar==guessWordLen){
System.out.println("Guessed word : " + seed);
break;
}
String tmpSeed = seed+c;
int matchedCount = matchStr(tmpSeed); // get no of times character c is present in the dict word
if(matchedCount > maxMatchedSoFar ){
maxMatchedSoFar=matchedCount;
seed = tmpSeed;
c='a'-1; // so that c= 'a' in next iteration
}
}
}
public static void main(String[] args) {
guessWord();
}
}
I like this approach, re-written in a simple code
/*
* 1. For each alphabet find how many occurrences of it are present in the word by calling machine function
* 2. Now we have an jumbles characters word of same length and containing same no of charaters as in the target word
* 3. Try all the permutations to see if its the right word
*
*/
public class WordGameMachine {
static String dictWord = "daddy";
public static int matchChar(Character c){
int cnt=0;
for(int i=0;i<=dictWord.length()-1;i++){
if(dictWord.charAt(i) == c){
cnt++;
}
}
return cnt;
}
public static boolean isCorrectWord(String str){
return dictWord.equals(str) ? true:false;
}
public static void permuteSeed(String str, String result){
if(str.length()==0){
if(isCorrectWord(result) == true){
System.out.println("Guessed word : " + result);
return;
}
}
for(int i=0;i<=str.length()-1;i++){
permuteSeed(str.substring(0,i)+str.substring(i+1,str.length()) , result+str.charAt(i));
}
}
public static void guessWord(){
// Find a seed of chars containing same number of chars as in the dict string
String seed="";
for(char c='a';c<='z';c++){
int matchedCount = matchChar(c); // get no of times character c is present in the dict word
while(matchedCount > 0){
seed = seed + c;
matchedCount--;
}
}
System.out.println("seed="+ seed);
//For all permutations of this seed and check if its the right word
permuteSeed(seed,"");
}
public static void main(String[] args) {
guessWord();
}
}
Implemented above algo and using binary search
public static int getHIndex2(Integer[] arr){
Arrays.sort(arr,Collections.reverseOrder()); // O(nLog(n))
int h = 0;
int low=0;
int high=arr.length-1;
//log(n)
while(low<=high){
int mid = (low+high)/2;
if(arr[mid] >= mid+1){
h=mid+1;
low=mid+1;
}else{
high=mid-1;
}
}
return h;
}
// O(n*m) where n is the no of consumer and m is the no of producers
1. Sort consumers
2. Sort producers on X and then on Y for the ones that has the same X
for each consumer
3. calculate the distance from consumer to producer. c^2=a^2+b^2 ( since the points for a triangle) unless consumer and producer have the same x-coordinate and in such case "distance = y-coordinate of producer"
import java.util.*;
/* P
* |\
* b| \c => c^2 = a^2 + b^2 i.e c =
* | \
* 0,0|____\C
* a
*
*/
public class ConsumerProducer {
//Integer = consumer , HashMap<Integer,List<Integer> => distance from the nearset producer List<Integer>
static HashMap<Integer,HashMap<Integer,Integer[]>> resultMap = new HashMap<Integer,HashMap<Integer,Integer[]>>();
static List<Integer[]> producer = new ArrayList<Integer[]>(); // Integer[] x,y
static List<Integer> consumer = new ArrayList<Integer>(); // Consumer x
public static int getDistance(Integer[] producer, int consumer){
if(producer[0] == consumer){ // both have same x coordinate , return y
return producer[1];
}else{
int a = Math.abs(consumer-producer[0]);
int b = producer[1];
int c = (int)Math.sqrt(a*a + b*b);
return c;
}
}
public static void getNearestPorducer(){
for(int i=0;i<=producer.size()-1;i++){
for(int j=0;j<=consumer.size()-1;j++){
Integer[] currProducer = producer.get(i);
Integer currConsumer = consumer.get(j);
Integer newDistance = getDistance(currProducer,currConsumer);
if(resultMap.containsKey(currConsumer)){ // if that consumer was already calculated via other producer
Integer oldDistance = (int)resultMap.get(currConsumer).keySet().toArray()[0];
if(newDistance < oldDistance){
resultMap.get(currConsumer).remove(oldDistance); // remove that key
resultMap.get(currConsumer).put(newDistance, currProducer); // add current producer
}
}else{
HashMap<Integer,Integer[]> newMap = new HashMap<Integer,Integer[]>();
newMap.put(newDistance,currProducer);
resultMap.put(currConsumer, newMap); // new current producer
}
}
}
for(int key : resultMap.keySet()){
System.out.println("Conumer : "+ key);
int nearestProducerDistance = (int)resultMap.get(key).keySet().toArray()[0];
System.out.println("Nearest Producer with distance : " + nearestProducerDistance + " -> " + Arrays.toString(resultMap.get(key).get(nearestProducerDistance)));
System.out.println();
}
}
public static void main(String[] args) {
producer.add(new Integer[]{0, 3});
producer.add(new Integer[]{1, 1});
producer.add(new Integer[]{3, 2});
producer.add(new Integer[]{8, 10});
producer.add(new Integer[]{9, 100});
consumer.add(1);
consumer.add(7);
consumer.add(5);
Collections.sort(consumer);
Collections.sort(producer, new Comparator<Integer[]>(){
public int compare(Integer[] o1, Integer[] o2) {
Integer o1x = o1[0];
Integer o1y = o1[1];
Integer o2x = o2[0];
Integer o2y = o2[1];
if(o1x < o2x){ // Sort on x and if x is same , on y
return -1;
}else if(o2x < o1x){
return 1;
}else{
return o1y.compareTo(o2y);
}
}
});
getNearestPorducer();
}
}
Implementation of above algo.
1. Build un-directed graph
2. Scan in DFS Direction and while scanning , create a new graph( adjacency Map) with vertex and edges in reverse direction of scan
import java.util.*;
public class UnDirectedToDirectedGraph {
//Input Bi-directional graph
HashMap<Integer,LinkedList<Integer>> adjInputUnDirectedMap = new HashMap<Integer,LinkedList<Integer>>();
//Uni-directional graph in reverse-direction of DFS scan
HashMap<Integer,LinkedList<Integer>> adjOutputDirectedMap = new HashMap<Integer,LinkedList<Integer>>();
// Bi-directional Graph
public void addEdgeBiDirectional(int a , int b){
// add a -> b
if(adjInputUnDirectedMap.containsKey(a)){
adjInputUnDirectedMap.get(a).add(b);
}else{
LinkedList<Integer> newList = new LinkedList<Integer>();
newList.add(b);
adjInputUnDirectedMap.put(a, newList);
}
// add b -> a
if(adjInputUnDirectedMap.containsKey(b)){
adjInputUnDirectedMap.get(b).add(a);
}else{
LinkedList<Integer> newList = new LinkedList<Integer>();
newList.add(a);
adjInputUnDirectedMap.put(b, newList);
}
}
//Unidirectional add
public void addEdgeUniDirectional(int a , int b, HashMap<Integer,LinkedList<Integer>> map){
// add a -> b
if(map.containsKey(a)){
map.get(a).add(b);
}else{
LinkedList<Integer> newList = new LinkedList<Integer>();
newList.add(b);
map.put(a, newList);
}
}
//DFS scan
public void DFS(int startPoint , HashSet<Integer> visited, int from ){
// vertex "from" to "startPoint" is the scan direction
// for the first node, from=-1 (i.e we are starting from nowhere)
if(visited.contains(startPoint)){
return;
}
visited.add(startPoint); // mark it as visited
if(from != -1){
System.out.println("Scan direction :" + from +" -> "+ startPoint);
System.out.println(" Reverse Scan direction(added to output) :" + startPoint +" -> "+ from);
addEdgeUniDirectional( startPoint,from, adjOutputDirectedMap); // add in reverse direction of scan. Important
}
LinkedList<Integer> neighbours = adjInputUnDirectedMap.get(startPoint);
for(int neighbour : neighbours){
DFS(neighbour,visited, startPoint);
}
}
public static void main(String[] args) {
UnDirectedToDirectedGraph obj = new UnDirectedToDirectedGraph();
/*
*
* * 3 <--> 4 <--> 5
* | \
* | \
* 1 2
* \
* \
* 6
*/
// Build bi-directional Map
obj.addEdgeBiDirectional(1,3);
obj.addEdgeBiDirectional(3,1);
obj.addEdgeBiDirectional(3,2);
obj.addEdgeBiDirectional(2,3);
obj.addEdgeBiDirectional(2,6);
obj.addEdgeBiDirectional(6,2);
obj.addEdgeBiDirectional(3,4);
obj.addEdgeBiDirectional(4,3);
obj.addEdgeBiDirectional(4,5);
obj.addEdgeBiDirectional(5,4);
System.out.println("Undirected Graph " + obj.adjInputUnDirectedMap.toString()+"\n");
// Convert bi-directional Graph to Directed Graph in reverse-direction of DFS Scan. leading to element 6
obj.DFS(6, new HashSet<Integer>(),-1);
System.out.println("\nDirected Graph (leading to element 6 : " + obj.adjOutputDirectedMap.toString());
}
}
I think the Time Complexity is O(Nlog(k)) instead of O(Klog(k))
// O(N) * log(k) = O(Nlog(k))
for(int i=k; i<array.length; i++){ // loop through n-k times hence O(n) considering k is very small
if(array[i] > queue.peek()){
queue.remove();
queue.add(array[i]); // log(k)
}
}
We can use bubble sort technique.
Look for adjacent elements and swap i.e for each i , if arr[i] < arr[i-1] , call moveToFront(i)
Keep doing until on each pass we have atleast one moveToFront calls ( use boolean flag to know that).
//Complete code
public class SortArrayMoveFront {
public static void moveToFront(int[] arr , int pos){
int tmp = arr[pos];
for(int j=pos;j>0;j--){
arr[j] = arr[j-1]; // shift
}
arr[0] = tmp;
}
//bubbles sort technique O(N^2)
public static void sortArray(int[] arr){
boolean moved = true;
while(moved){
moved=false;
for(int i=1;i<=arr.length-1;i++){
if(arr[i] < arr[i-1]){
moveToFront(arr,i); // moved
moved=true; // a move was made
}
}
}
}
public static void main(String[] args) {
//int[] arr = {11,4,5,4,7};
int[] arr = {12,3,4,3,24,22,4,224,453,232};
sortArray(arr);
//moveToFront(arr,0);
System.out.println(Arrays.toString(arr));
}
}
Recursive solution for upto million. Can be easily extended to billion ... and further
public class NumberToWords {
static String[] ones = {
"",
" one",
" two",
" three",
" four",
" five",
" six",
" seven",
" eight",
" nine",
" ten",
" Eleven",
" Twelve",
" Thriteen",
" Fourteen",
" Fifteen",
" Sixteen",
" Seventeen",
" Eighteen",
" Ninetween"};
static String[] tens = {
"", // zero
"", // two
" Twenty",
" Thirty",
" Fourty",
" Fifty",
" Sixty",
" Seventy",
" Eighty",
" Ninety"};
public static String convertNumberToWords(int num){
String str = Integer.toString(num);
int len = str.length();
String result = "";
if(len == 1){
result = ones[num];
}else if(len==2){
if(num<20){
result = ones[num];
}else{
result = tens[num/10] + ones[num%10];
}
}else if(len == 3){
result += ones[num/100];
result += " Hundered";
result += convertNumberToWords(num%100);
}else if(len > 3 && len <=6 ){ // thousands . million = 6 zeros hence 1 million = 7 digits
result += convertNumberToWords(num/1000); // say 200,000 , 200 can be converted to string by calling same fun for 200
result += " Thousand";
result += convertNumberToWords(num%1000);
} else if(len > 6 && len <=9){ // until 999 million = 9 digits
result += convertNumberToWords(num/1000000);
result += " Million";
result += convertNumberToWords(num%1000000);
}
return result;
}
public static void main(String[] args) {
System.out.println(convertNumberToWords(200080680));
}
}
Solution:
1. keep pushing into stack<string> each character ( as string) until "]" is found.
2. When "]" is found , keep looking back into stack and keep appending words until "[" is found.
3. When "[" is found in step 2, keep looking back until digits are being seen ( the number could be 23 , 456 etc , hence keep looking back into stack". This no is "ctr"
4. Now build the comboString say bd and loop through ctr times while pushing into stack this comboString
public static String decode(String str){
Stack<String> stack = new Stack<String>();
for(int i=0;i<=str.length()-1;i++){
String s = str.substring(i,i+1);
if(!s.equals( "]") ){
stack.push(s);
}else{
String comboStr = "";
while(!stack.peek().equals("[")){
comboStr = stack.pop() + comboStr;
}
stack.pop(); // remove "["
int ctr= 0;
String ctrStr = "";
while(!stack.isEmpty() && stack.peek().charAt(0) >= '0' && stack.peek().charAt(0) <='9'){
ctrStr = stack.pop() + ctrStr;
}
ctr=Integer.parseInt(ctrStr);
//Integer.parseInt(stack.pop());
System.out.println("ctr="+ctr);
while(ctr>0){ // repeat the string
stack.push(comboStr);
ctr--;
}
System.out.println("comboStr="+comboStr);
}
}
str="";
for(String s : stack){ // stack navigates from bottom to top
str = str + s;
}
return str;
}
This is what i came up with. Why was it downvoted ?
import java.util.*;
public class TvOnInterval {
public static int getTvOnInterval(int[][] arr){
int[] arrival = new int[arr.length]; // arrival times array
int[] exit = new int[arr.length]; // exit times array
for(int i=0;i<=arr.length-1;i++){
arrival[i] = arr[i][0];
exit[i] = arr[i][1];
}
Arrays.sort(arrival); // sort
Arrays.sort(exit); //sort
int i=0;
int j=0;
int iStart = -1; // tv start time (first time on or when switched on after off)
int guestCount=0; // guests in room at any point of time
int tvOnTime=0; // total time Tv is ON
while(i<=arr.length-1 && j <= arr.length-1){
if(arrival[i] < exit[j]){
if(guestCount == 0){
iStart=i; // Tv is first turned on pr turned on after an off - after guestCount was 0
}
guestCount++;
i++;
}else if(exit[j] < arrival[i]){
guestCount--;
if(guestCount == 0){ // Tv is turned off
System.out.println("iStart="+arrival[iStart]+" jEnd="+exit[j]);
tvOnTime = tvOnTime + (exit[j]-arrival[iStart]);
}
j++;
} else{
// else one arrival one exist no change
i++;
j++;
}
}
// last exit time of j
System.out.println("iStart="+arrival[iStart]+" jEnd="+exit[exit.length-1]);
tvOnTime = tvOnTime + (exit[exit.length-1] - arrival[iStart]);
return tvOnTime;
}
public static void main(String[] args) {
int[][] arr = {{1,4}, {6,8}, {2,4}, {7,9}, {10, 15}};
System.out.println("Total Tv On time : "+ getTvOnInterval(arr));
}
}
/*
*Steps:
* 1. Sort the intervals based on start time
* 2. Use dynamic program to calculate weight by including current meeting and skipping current meeting
* Use max from above two to get weight
*
*/
public class MaximumWeightMeeting {
public static List<Meeting> getMaxWeightMeeting(List<Meeting> list ,int i, int sumOfWeights, List<Meeting> result){
//System.out.println("weight="+sumOfWeights);
if(i >= list.size()){
//return sumOfWeights; // don't return 0. Return what has been calculated yet
List<Meeting> ret = result;
ret.add(new Meeting(0,0,sumOfWeights)); // create dummy meeting with 0 start , end and sumOfWesights as sum
return ret;
}
int nextMeetingIndex = nextPossibleMeeting(list,i);
List<Meeting> newResult = new ArrayList<Meeting>(result); // newresult when we attend current meeting
newResult.add(list.get(i));
// Max of (attending current meeting and call for next Possible meeting that can be attended,
// skip currentMeeting and call for next meeting (i+1)
//return Math.max(getMaxWeightMeeting(list,nextMeetingIndex,sumOfWeights+list.get(i).weight, newResult),
// getMaxWeightMeeting(list, i+1, sumOfWeights, result));
List<Meeting> result1 = getMaxWeightMeeting(list,nextMeetingIndex,sumOfWeights+list.get(i).weight, newResult);
List<Meeting> result2 = getMaxWeightMeeting(list, i+1, sumOfWeights, result);
int sumWeight1 = result1.get(result1.size()-1).weight;
int sumWeight2 = result2.get(result2.size()-1).weight;
if(sumWeight1 > sumWeight2){
return result1;
}else{
return result2;
}
}
public static int nextPossibleMeeting(List<Meeting> list , int k){
for(int i=k+1;i<=list.size()-1;i++){
if(list.get(i).startTime >= list.get(k).endTime){ // find next meeting that can be attended by after kth meeting
return i;
}
}
return Integer.MAX_VALUE; // very last meeting index
}
public static void main(String[] args) {
List<Meeting> list = new ArrayList<Meeting>();
list.add(new Meeting(1,4,100));
list.add(new Meeting(1,3,200));
list.add(new Meeting(4,6,150));
list.add(new Meeting(4,6,50));
list.add(new Meeting(2,6,10));
// Sort Meetings by Start time
Collections.sort(list,new MeetingComparator());
for(Meeting m : list){
System.out.println(m.toString());
}
List<Meeting> result = getMaxWeightMeeting(list,0,0 ,new ArrayList<Meeting>());
System.out.println("Max sum of weights = " + result.get(result.size()-1).weight);
System.out.println("Max sum Meeting Intervals : " + result.toString());
}
}
class Meeting{
int startTime;
int endTime;
int weight;
Meeting(int startTime, int endTime, int weight){
this.startTime = startTime;
this.endTime = endTime;
this.weight = weight;
}
public String toString(){
return this.startTime + "," + this.endTime + "," + this.weight;
}
}
class MeetingComparator implements Comparator<Meeting>{
public int compare(Meeting m1, Meeting m2){
// return the one with smaller startTime
return (m1.startTime < m2.startTime)?-1:((m1.startTime > m2.startTime)?1:0);
}
}
@Loler is the best algo i could think of. Re-writing in a simple to understand but longer code
public class DisjointContinguosSubArray {
public static void getTwoDisjointArrays(int[] arr){
List<List<Integer>> maxDiffList = new ArrayList<List<Integer>>();
int maxDiffSoFar = Integer.MIN_VALUE;
// O(N*N)
for(int i=0;i<=arr.length-2;i++){ // till -2, so we have one element the rightmost array // O(N)
//Combo1
List<Integer> leftMin = getMinSubsetArray(arr,0,i); // O(N) // get Min sub-array to the left of i(including) i.e 0 to i
List<Integer> rightMax = getMaxSubsetArray(arr,i+1,arr.length-1); // O(N) // get Max sub-array to the right of i(excluding)
//Combo2
List<Integer> leftMax = getMaxSubsetArray(arr,0,i); // O(N) //get Max sub-array to the left of i(including)
List<Integer> rightMin = getMinSubsetArray(arr,i+1,arr.length-1); // O(N) // get Min sub-array to the right of i(excluding)
int diff1 = Math.abs(rightMax.get(0) - leftMin.get(0)); // Combo1's diff
int diff2 = Math.abs(leftMax.get(0) - rightMin.get(0)); // Combo2's diff
if(diff1>diff2){ // diff1 is bigger
if(diff1 > maxDiffSoFar){
maxDiffSoFar=diff1; // update maxSoFar
maxDiffList.clear();
maxDiffList.add(leftMin);
maxDiffList.add(rightMax);
}
}else{
if(diff2 > maxDiffSoFar){ // diff2 is bigger
maxDiffSoFar=diff2; // update maxSoFar
maxDiffList.clear();
maxDiffList.add(rightMin);
maxDiffList.add(leftMax);
}
}
}
System.out.println("Two disjoint arrays : " + maxDiffList.get(0).toString() + " " + maxDiffList.get(1).toString());
System.out.println("Max Diff : " + ( maxDiffList.get(1).get(0) - maxDiffList.get(0).get(0) ));
}
//get Min sub-array between points // O(N)
public static List<Integer> getMinSubsetArray(int[] arr , int i , int j){
int iMin = -1;
int jMin = -1;
int minSum = Integer.MAX_VALUE;
int iCurrent= -1;
int jCurrent = -1;
int currentSum=0;
for(int k=i;k<=j;k++){
currentSum = Math.min(currentSum+arr[k], arr[k]);
if(currentSum == arr[k]){
iCurrent = k;
jCurrent = k;
}else{
jCurrent = k;
}
minSum = Math.min(minSum,currentSum);
if(minSum == currentSum){
iMin = iCurrent;
jMin = jCurrent;
}
}
// This List which is the result stored 0thIndex(min sum) 1thPosition(fromIndex of min sub-array) 2ndPosition(toIndex of min sub-array)
List<Integer> list = new ArrayList<Integer>();
list.add(minSum);
list.add(iMin);
list.add(jMin);
return list;
}
//get Max sub-array between points // O(N)
public static List<Integer> getMaxSubsetArray(int[] arr , int i , int j){
int iMax = -1;
int jMax= -1;
int maxSum = Integer.MIN_VALUE;
int iCurrent = -1;
int jCurrent = -1;
int currentSum = 0;
for(int k=i;k<=j;k++){
currentSum = Math.max(currentSum+arr[k], arr[k]);
if(currentSum==arr[k]){
iCurrent = k;
jCurrent = k;
}else{
jCurrent = k;
}
maxSum = Math.max(maxSum, currentSum);
if(maxSum == currentSum){
iMax = iCurrent;
jMax = jCurrent;
}
}
// This List which is the result stored 0thIndex(max sum) 1thPosition(fromIndex of max sub-array) 2ndPosition(toIndex of max sub-array)
List<Integer> list = new ArrayList<Integer>();
list.add(maxSum);
list.add(iMax);
list.add(jMax);
return list;
}
public static void main(String[] args) {
int[] arr = {2,-1,-2,1,-4,2,8}; // Works as expected
//int[] arr = {-1,-2,-3}; // Works as expected
getTwoDisjointArrays(arr);
}
}
Time O(N)
Space O(1)
Steps:
1) Loop through to find Max of the array and the maxIndex(which will be the last MaxIndex, but doesn't matters which one)
2) Loop through again to find index(called currentMaxIndex) containing maxElement and make maxIndex = Random(maxIndex , currentMaxIndex)
Print maxIndex -> This is the random Index of the max value element
//Time is O(N) , Space is O(1)
public static void getMaxValueIndexEvenly2(int[] arr){
int maxValue = Integer.MIN_VALUE;
int maxIndex = -1;
for(int i=0;i<=arr.length-1;i++){ // O(N)
if(arr[i] > maxValue){
maxValue=arr[i];
maxIndex=i;
}
}
int currentMaxIndex = -1;
Random random = new Random();
for(int i=0;i<=arr.length-1;i++){ // O(N)
if(arr[i] == maxValue){
currentMaxIndex = i;
int randomIndex = random.nextInt(2); // random between maxIndex and currentMaxIndex i.e 2 elements. It returns 0 or 1
if(randomIndex == 0){
maxIndex=maxIndex; // keep maxIndex as maxIndex
}else{
maxIndex=currentMaxIndex; // update maxIndex as currentMaxIndex
}
}
}
System.out.println("Random O(1) Max Index = " + maxIndex);
}
This is awesome , except a minor change
for(Person p : list) {
if(!isKnow(p, a))
return null;
}
to
for(Person p : list) {
if(p!=a){ // celebrity doesn't know itself , so we should not check isKnow
if(!isKnow(p, a))
return null;
}
}
1.2 Consider the input as arrival and departure time of guests and we have to find at which time there were max number of guests
public class PointOfMaxOverlapOfInterval {
public static void findMaxOverlapInterval(int[][] arr){
int[] entry = new int[arr.length];
int[] exits = new int[arr.length];
for(int i=0;i<=arr.length-1;i++){
entry[i] = arr[i][0];
exits[i] = arr[i][1];
}
Arrays.sort(entry);
Arrays.sort(exits);
//use merge of MergeSort
int i=0; // arrival
int j=0; // exits
int maxGuests=0; // max guests at a single time
int maxGuestsTime=0; // point in time with max no of guests i.e overlap
int totalGuestsSoFar=0; // running record of total guests present at any point
while(i<=entry.length-1 && j<=exits.length-1){
if(entry[i] <= exits[j]){ // guest entry less than equal ( if one enters and one leaves ,
// still we have more overlap at this point
totalGuestsSoFar++;
if(totalGuestsSoFar > maxGuests){
maxGuests=totalGuestsSoFar;
maxGuestsTime=entry[i];
}
i++; // Increment index of arrival
}else{ // guest exit
totalGuestsSoFar--;
j++; // Increment index of exists
}
}
System.out.println("maxGuests="+maxGuests+" maxGuestsTime="+maxGuestsTime);
}
public static void main(String[] args) {
int[][] arr = { {1,4}, {2,5} , {9,12} , {5,9} , {5,12},{4,12} };
findMaxOverlapInterval(arr);
}
}
public static void divideNumbers(int a , int b){
int result = 0;
int remainder = 0;
while(a-b > 0){
result++;
remainder = a-b;
a = remainder;
}
System.out.println("Result = "+ result);
System.out.println("Remainder = "+ remainder);
}
Let say
Small array size = m
Large array size = n
Steps: Loop through each element of small array(O(m)) and do binary search on large array O(log(n)) = O(mlog(n))
public class InterSectionOfSortedArrays {
//O(mlog(n))
public static void getIntersection(int[] arr1 , int[] arr2){
for(int i=0;i<=arr2.length-1;i++){ //O(m)
if(findInSmallArray(arr1,arr2[i])){ // O(log(n))
System.out.println(arr2[i]);
}
}
}
//O(log(n)) Binary Search
public static boolean findInSmallArray(int[] arr , int value){ // serachArray, valueTobeSearched
int low=0;
int high=arr.length-1;
while(low<=high){
int mid = (low+high)/2;
if(arr[mid] == value){
return true;
}else if(arr[mid] < value){
low=mid+1;
}else{
high=mid-1;
}
}
return false;
}
public static void main(String[] args) {
int [] arr1 = {1, 3, 4, 5, 7,8,9,10,11}; // very large
int [] arr2 = {2, 3, 5, 6, 9, 10}; // small
getIntersection(arr1,arr2);
}
}
import java.util.Arrays;
import java.util.Random;
public class create2DArray {
public static int[][] createArray(int rows, int cols,int a , int b){
int[][] arr = new int[rows][cols];
Random random = new Random();
//generate random random between a and b inclusive
for(int i=0;i<=arr.length-1;i++){
for(int j=0;j<=arr[0].length-1;j++){
arr[i][j] = random.nextInt(b-a + 1) + a;
}
}
return arr;
}
public static boolean checkColumn(int[][] arr,int col, int min , int max){
System.out.println("MIN MAX : " + min + " " + max);
boolean minFlag = false;
boolean maxFlag = false;
for(int i=0;i<=arr.length-1;i++){
if(arr[i][col] == min){
minFlag=true;
}
if(arr[i][col] == max){
maxFlag=true;
}
}
return minFlag && maxFlag;
}
public static void main(String[] args) {
int arr[][] = createArray(3,2,25,40);
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for(int i=0;i<=arr.length-1;i++){
for(int j=0;j<=arr[0].length-1;j++){
System.out.print(arr[i][j]+" ");
min=Math.min(min, arr[i][j]); // MIN
max=Math.max(max, arr[i][j]); // MAX
}
System.out.println();
}
System.out.println(checkColumn(arr,0,min,max));
}
}
public static void finMaxDrop(int[] arr)
{
int minSofar = arr[0];
int maxDrop = 0;
for(int i = 1 ; i < arr.length ; i++)
{
if(arr[i] > minSofar)
{
int currentDrop = arr[i] - minSofar;
maxDrop = Math.max(maxDrop,currentDrop);
minSofar = Math.min(minSofar, arr[i]);
}
else{
minSofar = Math.min(minSofar, arr[i]);
}
}
System.out.println(maxDrop);
}
If we ignore the second condition that no two sub-arrays can be duplicate, below is the solution
- Mayank Jain June 09, 2019