ProTechMulti
BAN USERThe solution:
Create a reverse map that will store Map<String, Set<String>>.
The reverse map will be used for quick access of removing course dependencies.
The main idea is that we start with the courses that doesn't have dependencies, registering them for the 1st semester. Next we will remove the assigned courses from the dependencies and run again the loop and follow the same rules, register courses without dependencies. Until we will register all courses to semesters.
I tried to write more readable code:
package com.tech.yriaznov;
import java.util.*;
public class Main {
public static void main(String[] args) {
int semesters = MinSemsToFinishAllCourses(GetMockData());
System.out.print("Total semesters: " + semesters);
}
public static int MinSemsToFinishAllCourses(Map<String,List<String>> courses) {
Map<String,Set<String>> reverseMap = ReverseMap(courses);
int totalCourses = courses.size();
int registeredCourses = 0;
int currentSemester = 1;
Set<String> registredCoursesSet = new HashSet<>();
while(registeredCourses < totalCourses) {
Set<String> forClear = new HashSet<>();
for(String key : courses.keySet()) {
if(courses.get(key).size() > 0 || registredCoursesSet.contains(key)) continue;
registredCoursesSet.add(key);
registeredCourses++;
forClear.add(key);
System.out.println("Course: " + key + " on semester " + currentSemester);
}
for(String key : forClear) {
ClearDependencies(key,courses,reverseMap);
}
currentSemester++;
}
return currentSemester-1;
}
public static void ClearDependencies(String course,Map<String,List<String>> courses,
Map<String,Set<String>> reverseMap) {
Set<String> depCourses = reverseMap.get(course);
if(depCourses == null) return;
for(String key : depCourses) {
courses.get(key).remove(course);
}
}
public static Map<String,Set<String>> ReverseMap(Map<String,List<String>> courses) {
Map<String,Set<String>> reverseMap = new HashMap<>();
for(String key : courses.keySet()) {
List<String> list = courses.get(key);
for(int i=0; i<list.size();i++) {
String course = list.get(i);
Set<String> subList = reverseMap.getOrDefault(course,null);
if(subList == null) reverseMap.put(course,new HashSet<>());
reverseMap.get(course).add(key);
}
}
return reverseMap;
}
public static Map<String,List<String>> GetMockData() {
Map<String,List<String>> mockData = new HashMap<>();
List<String> Calculus = new ArrayList<>();
Calculus.add("English");
Calculus.add("Math2");
mockData.put("Calculus",Calculus);
List<String> Math2 = new ArrayList<>();
Math2.add("Math1");
Math2.add("Arabic");
Math2.add("English");
mockData.put("Math2",Math2);
List<String> Math1 = new ArrayList<>();
Math1.add("English");
mockData.put("Math1",Math1);
mockData.put("English",new ArrayList<>());
mockData.put("Arabic",new ArrayList<>());
return mockData;
}
}
Output:
Course: English on semester 1
Course: Arabic on semester 1
Course: Math1 on semester 2
Course: Math2 on semester 3
Course: Calculus on semester 4
Total semesters: 4
The idea is to count for each string the characters and store them in a counters array.
After that consolidate all counters into a total counter.
Last step is to convert the total counter into a string
Run time complexity is O(n*m) n - number of strings , m - size of longest string.
Java implementation:
package com.cracking.facebook;
public class ConsulidateStrings {
public static final int CHARS = 26;
public static void main(String[] args) {
String[] strings = GetMockStrings();
int[][] counters = CountStringsLetters(strings);
int[] total = Consulidate(counters);
String conStr = ToString(total);
System.out.println("Shortest string that covers all = " + conStr);
}
public static String ToString(int[] counter) {
StringBuilder builder = new StringBuilder();
for(int i=0; i<CHARS; i++) {
int count = counter[i];
while(count-- > 0) {
builder.append( (char)('a'+i) );
}
}
return builder.toString();
}
public static int[] Consulidate(int[][] counters) {
int[] total = new int[CHARS];
for(int i=0;i<counters.length; i++) {
Consulidate(total,counters[i]);
}
return total;
}
public static void Consulidate(int[] arr1, int[] arr2) {
for(int i=0;i<CHARS; i++) {
if(arr2[i] > arr1[i]) arr1[i] = arr2[i];
}
}
public static int[][] CountStringsLetters(String[] strings) {
int[][] counters = new int[strings.length][];
for(int i=0; i<strings.length; i++) {
counters[i] = CountLetters(strings[i]);
}
return counters;
}
public static int[] CountLetters(String str) {
int[] counters = new int[CHARS]; //26 letters
str = str.toLowerCase();
for(int i=0; i<str.length(); i++) {
int pos = str.charAt(i) - 'a';
counters[pos]++;
}
return counters;
}
public static String[] GetMockStrings() {
String[] arr = new String[] {
"aab",
"aabb",
"bc"
};
return arr;
}
}
Output:
Shortest string that covers all = aabbc
Java implementation O(n^2):
package com.cracking.vmware;
import java.util.ArrayList;
public class ProductOfTwoStrings {
public static void main(String[] args) {
int sumInt = Multiple_RetInt("123456789", "987654321");
System.out.println("Int calculation: " + sumInt);
String sumStr = Multiple_RetStr("123456789", "987654321");
System.out.println("Str calculation: " + sumStr);
}
public static String Multiple_RetStr(String str1, String str2) {
char[] arr1 = str1.toCharArray();
char[] arr2 = str2.toCharArray();
if(str1.length() > str2.length()) {
return Multiple_RetStr(arr2,arr1);
}
return Multiple_RetStr(arr1,arr2);
}
public static String Multiple_RetStr(char[] arr1, char[] arr2) {
int startPos = 0;
ArrayList<ArrayList<Character>> calculations = new ArrayList<ArrayList<Character>>();
for(int i=arr1.length-1; i>=0; i--) {
char a = arr1[i];
int carry = 0;
ArrayList<Character> calculation = new ArrayList<Character>();
AddToArray('0', startPos++, calculation);
for(int j=arr2.length-1; j>=0; j--) {
char b = arr2[j];
int res = Multiple(a,b);
res+= carry;
int value = res%10;
carry = res/10;
calculation.add( (char)(value+'0') );
}
calculation.add( (char)(carry+'0') );
calculations.add(calculation);
}
return Sum(calculations);
}
public static String Sum(ArrayList<ArrayList<Character>> calculations) {
ArrayList<Character> sum = new ArrayList<Character>();
for(int i=0;i<calculations.size();i++) {
sum = Sum(sum,calculations.get(i));
}
return GetReverseStr(sum);
}
public static String GetReverseStr(ArrayList<Character> arr) {
StringBuilder builder = new StringBuilder();
for(int i=arr.size()-1; i>=0; i--) {
builder.append(arr.get(i));
}
return builder.toString();
}
public static ArrayList<Character> Sum(ArrayList<Character> arr1, ArrayList<Character> arr2) {
if(arr1.isEmpty()) return arr2;
if(arr2.isEmpty()) return arr1;
ArrayList<Character> sum = new ArrayList<Character>();
int carry = 0;
int i = 0;
while( i<arr1.size() && i<arr2.size() ) {
char a = arr1.get(i);
char b = arr2.get(i);
int res = Sum(a,b) + carry;
int val = res%10;
carry = res/10;
sum.add( (char)(val+'0') );
i++;
}
while(i<arr1.size()) {
char ch = arr1.get(i++);
int res = (ch-'0') + carry;
int val = res%10;
carry = res/10;
sum.add( (char)(val+'0') );
i++;
}
while(i<arr2.size()) {
char ch = arr2.get(i++);
int res = (ch-'0') + carry;
int val = res%10;
carry = res/10;
sum.add( (char)(val+'0') );
i++;
}
return sum;
}
public static int Multiple(char a,char b) {
return (a-'0')*(b-'0');
}
public static int Sum(char a, char b) {
return (a-'0') + (b-'0');
}
public static boolean AddToArray(char ch,int count,ArrayList<Character> arr) {
while(count-- > 0) {
arr.add(ch);
}
return true;
}
public static int Multiple_RetInt(String str1, String str2) {
char[] arr1 = str1.toCharArray();
char[] arr2 = str2.toCharArray();
if(str1.length() > str2.length()) {
return Multiple_RetInt(arr2,arr1);
}
return Multiple_RetInt(arr1,arr2);
}
public static int Multiple_RetInt(char[] arr1, char[] arr2) {
int totalSum=0;
for(int topWeight=1, i=arr1.length-1; i>=0; i--) {
int sum = 0;
int value,carry = 0;
int weight=topWeight;
for(int j=arr2.length-1; j>=0; j--) {
int res = (arr1[i] - '0' )*(arr2[j] - '0' ) + carry;
value = res%10;
int calc = value*weight;
sum += calc;
carry = res/10;
weight *= 10;
}
sum += carry*weight;
totalSum += sum;
topWeight*=10;
}
return totalSum;
}
}
Output:
Int calculation: -67153019
Str calculation: 121932631112635269
Java implementation O(n^2) :
package com.cracking.google;
import java.util.ArrayList;
import java.util.HashSet;
public class RectangleFindLargestOptimized {
public static void main(String[] args) {
ArrayList<Point> points = GetMockPoints();
HashSet<Long> points_hash = ConvertIntoSet(points);
Rectangle maxRect = GetLargestRectangle(points, points_hash);
System.out.println(maxRect.toString());
}
public static Rectangle GetLargestRectangle(ArrayList<Point> points, HashSet<Long> points_hash) {
Rectangle maxRectangle = new Rectangle();
for(int i=0; i<points.size()-1; i++) {
Point a = points.get(i);
for(int j=i+1; j<points.size(); j++) {
Point d = points.get(j);
int currArea = Math.abs(d.x - a.x) * Math.abs(d.y - a.y);
long pointB = GetPointKey(d.x, a.y);
long pointC = GetPointKey(a.x, d.y);
boolean containPoints = points_hash.contains(pointB) && points_hash.contains(pointC);
if(currArea > maxRectangle.getArea() && containPoints) {
maxRectangle.SetData(a, new Point(d.x, a.y), new Point(a.x, d.y), d, currArea);
}
}
}
return maxRectangle;
}
public static long GetPointKey(int x, int y) {
return ((long)x<<32)| (long)y;
}
public static class Point {
public Point(int x, int y) {
this.x = x;
this.y = y;
}
public int x;
public int y;
@Override
public String toString() {
String msg = String.format("%d,%d", this.x,this.y);
return msg;
}
}
public static class Rectangle {
public Rectangle() {
this.area = 0;
}
public void SetData(Point a,Point b,Point c, Point d, int area) {
this.a = a;
this.b = b;
this.c = c;
this.d = d;
this.area = area;
}
private Point a,b,c,d;
private int area;
public int getArea() {
return this.area;
}
@Override
public String toString() {
String msg = String.format("C(%s)\t\tD(%s)\n\nA(%s)\t\tB(%s)\nArea = %d",
this.c.toString(),
this.d.toString(),
this.a.toString(),
this.b.toString(),
this.area);
return msg;
}
}
public static HashSet<Long> ConvertIntoSet(ArrayList<Point> points) {
HashSet<Long> set = new HashSet<Long>();
for(Point p:points) {
set.add( GetPointKey(p.x, p.y) );
}
return set;
}
public static ArrayList<Point> GetMockPoints() {
ArrayList<Point> points = new ArrayList<Point>();
points.add(new Point(1, 4));
points.add(new Point(2, 4));
points.add(new Point(1, 2));
points.add(new Point(2, 2));
points.add(new Point(3, 4));
points.add(new Point(5, 4));
points.add(new Point(2, 6));
points.add(new Point(2, 1));
points.add(new Point(5, 1));
points.add(new Point(3, 3));
points.add(new Point(5, 3));
return points;
}
}
Output:
C(2,1) D(5,1)
A(2,4) B(5,4)
Area = 9
Hierarchical data structure:
package com.cracking.google;
public class EnumParentChild {
static enum Vehicle {
car(null,1),
toyota(car,11),
camry(toyota,111),
coroloa(toyota,112),
honda(car,12),
track(null,2),
GMC(track,21);
Vehicle(Vehicle parent,int value) {
this.parent = parent;
this.value = value;
}
public Vehicle parent;
public int value;
}
public static void main(String[] args) {
System.out.println(Vehicle.GMC + " " + Vehicle.GMC.value);
System.out.println(Vehicle.GMC.parent + " " + Vehicle.GMC.parent.value);
}
}
Output:
GMC 21
track 2
The question can be translated into several ways.
From looking on the function definition, it returns a list of integers:
public List<Integer> countCoverLength(Iterator<Interval> stream);
The total cover length calculation... is it from min to max? or is it the sum of all length calculations?
The next code will calculate all covers and then sum them:
package com.cracking.facebook;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.List;
public class TotalLengthCover {
public static void main(String[] args) {
Iterator<Interval> stream = MockIntervalStream();
List<Integer> coverList = CountCoverLength(stream);
System.out.println("Cover List: " + Arrays.toString(coverList.toArray()) );
System.out.println("Total: " + TotalCoverLength(coverList) );
}
public static int TotalCoverLength(List<Integer> list) {
int sum = 0;
for(int i=0; i<list.size(); i++) {
sum += list.get(i);
}
return sum;
}
public static List<Integer> CountCoverLength(Iterator<Interval> stream) {
ArrayList<Integer> list = new ArrayList<Integer>();
while(stream.hasNext()) {
Interval interval = stream.next();
list.add(interval.covered());
}
return list;
}
public static class Interval {
public int start;
public int end;
public Interval(int start, int end) {
this.start = start;
this.end = end;
}
public int covered() {
return Math.abs(this.start - this.end);
}
}
public static Iterator<Interval> MockIntervalStream() {
Hashtable<Integer, Interval> table = new Hashtable<Integer, Interval>();
table.put(1, new Interval(5, 12));
table.put(2, new Interval(20, 12));
table.put(3, new Interval(189, 260));
table.put(4, new Interval(0, -10));
return table.values().iterator();
}
}
Output:
Cover List: [10, 71, 8, 7]
Total: 96
Solution for the follow up:
1. Use array of int[26] as a character counters.
2. Sum the character instances of the input list.
3. Search to build a list of words with the equal counters.
package com.cracking.facebook;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
public class FindEqualListOfWords {
public static void main(String[] args) {
HashMap<String,String> dict = GetDictionary();
PrintEqualList(dict, new String[]{
"DEBIT",
"CARD"
});
}
public static void PrintEqualList(HashMap<String,String> dict, String[] list) {
String inputStr = String.join("", list);
int[] inputCounter = GetWordCount(inputStr);
ArrayList<String> equalList = GetEqualList(dict, inputCounter);
System.out.println("Input List: " + Arrays.toString(list) );
System.out.println("Equal List: " + equalList.toString() );
}
public static ArrayList<String> GetEqualList(HashMap<String,String> dict,int[] inputCounter) {
ArrayList<String> equalList = new ArrayList<String>();
ArrayList<String> words = new ArrayList<String>(dict.keySet());
for(int i=0; i<words.size(); i++) {
String word = words.get(i);
int[] testCount = GetWordCount(word);
if(IsLessOrEqual(testCount, inputCounter)) {
equalList.add(word);
int j= 0;
while(j<words.size() && !IsEqual(testCount, inputCounter)) {
word = words.get(j++);
if(equalList.indexOf(word) != -1) continue; //word already in the list
int[] subTestCount = AddCounters(testCount, GetWordCount(word));
if(IsLessOrEqual(subTestCount, inputCounter)) {
equalList.add(word);
testCount = subTestCount;
}
}//End While
if( IsEqual(testCount, inputCounter) ) break;
equalList.clear();
}//Big If
}//For Loop
return equalList;
}
public static int[] GetWordCount(String input) {
int[] counters = new int[26]; //default values of 0 for each element
for(int i=0;i<input.length();i++) {
int pos = input.charAt(i)-'A';
counters[pos]++;
}
return counters;
}
public static int[] AddCounters(int[] counter1, int[] counter2) {
int[] total = new int[26];
for(int i=0; i<total.length; i++) {
total[i] = counter1[i] + counter2[i];
}
return total;
}
public static boolean IsLessOrEqual(int[] test,int[] source) {
for(int i=0;i<test.length; i++) {
if(test[i] > source[i]) return false;
}
return true;
}
public static boolean IsEqual(int[] test,int[] source) {
for(int i=0;i<test.length; i++) {
if(test[i] != source[i]) return false;
}
return true;
}
public static HashMap<String,String> GetDictionary() {
HashMap<String,String> dict = new HashMap<String,String>();
dict.put("A", "A");
dict.put("AAA", "AAA");
dict.put("ACA", "ACA");
dict.put("ART", "ART");
dict.put("BAR", "A place with alcohol");
dict.put("BAD", "Not good");
dict.put("CAR", "Have 4 wheels and an engine");
dict.put("CREDIT", "Bank information");
dict.put("RAC", "RAC");
return dict;
}
}
Output:
Input List: [DEBIT, CARD]
Equal List: [BAD, CREDIT]
Solution for the first part of the question:
1. Create a dictionary - HashMap
2. Create HashSet with all possible subsets of the input string.
3. Loop the HashSet and look in the dictionary if the key exists.
package com.cracking.facebook;
import java.util.HashMap;
import java.util.HashSet;
public class FindSubsetWords {
public static void main(String[] args) {
HashMap<String,String> dict = GetDictionary();
HashSet<String> subSets = GetSubSets("ACRAT");
PrintMatchingWords(dict, subSets);
}
public static void PrintMatchingWords(HashMap<String,String> dict,HashSet<String> subSets) {
for(String key:subSets) {
if( dict.containsKey(key) ) {
System.out.println(key);
}
}
}
public static HashSet<String> GetSubSets(String input) {
HashSet<String> subSets = new HashSet<String>();
GetSubSets(input, subSets);
return subSets;
}
public static void GetSubSets(String input,HashSet<String> subSets) {
for(int i=0;i<input.length(); i++) {
String left = Character.toString(input.charAt(i));
String right = input.substring(0,i) + input.substring(i+1);
GetSubSets(left, right, subSets);
}
}
public static void GetSubSets(String left,String right,HashSet<String> subSets) {
subSets.add(left);
subSets.add(right);
for(int i=0;i<right.length();i++) {
String newLeft = left + Character.toString(right.charAt(i));
String newRight = right.substring(0,i) + right.substring(i+1);
GetSubSets(newLeft, newRight, subSets);
}
}
public static HashMap<String,String> GetDictionary() {
HashMap<String,String> dict = new HashMap<String,String>();
dict.put("A", "A");
dict.put("AAA", "AAA");
dict.put("ACA", "ACA");
dict.put("ART", "ART");
dict.put("BAR", "A place with alcohol");
dict.put("BAD", "Not good");
dict.put("CAR", "Have 4 wheels and an engine");
dict.put("CREDIT", "Bank information");
dict.put("RAC", "RAC");
return dict;
}
}
Output:
A
ART
ACA
CAR
RAC
package com.cracking.olap_vision;
public class DecodeString {
public static void main(String[] args) {
System.out.printf("String = %s , Value = %d\n","A",Decode("A"));
System.out.printf("String = %s , Value = %d\n","AA",Decode("AA"));
System.out.printf("String = %s , Value = %d\n","AZ",Decode("AZ"));
System.out.printf("String = %s , Value = %d\n","BA",Decode("BA"));
System.out.printf("String = %s , Value = %d\n","BZ",Decode("BZ"));
System.out.printf("String = %s , Value = %d\n","CA",Decode("CA"));
System.out.printf("String = %s , Value = %d\n","AAA",Decode("AAA"));
System.out.printf("String = %s , Value = %d\n","AAZ",Decode("AAZ"));
System.out.printf("String = %s , Value = %d\n","ABA",Decode("ABA"));
System.out.printf("String = %s , Value = %d\n","ABZ",Decode("ABZ"));
}
public static int Decode(String str) {
final int interval = 26;
char[] arr = str.toCharArray();
int len = arr.length;
int sum = 0;
for(int posInterval=0, i=len-1; i>=0; i--,posInterval++) {
char ch = arr[i];
int value = (ch - 'A') +1;
value *= Math.pow(interval, posInterval);
sum += value;
}
return sum;
}
}
Output:
String = A , Value = 1
String = AA , Value = 27
String = AZ , Value = 52
String = BA , Value = 53
String = BZ , Value = 78
String = CA , Value = 79
String = AAA , Value = 703
String = AAZ , Value = 728
String = ABA , Value = 729
String = ABZ , Value = 754
General solution for number of math operations:
package com.cracking.facebook;
public class CalculateMappedStringEquation {
public final static String Equation = "1234567 abc+efg";
public static void main(String[] args) {
String translatedEquation = TranslateEquation(Equation);
int result = CalculateEquation(translatedEquation);
System.out.println("Input = " + Equation);
System.out.println("Translated = " + translatedEquation);
System.out.println("Result = " + result);
}
public static String TranslateEquation(String equation) {
char[] values = equation.substring(0, equation.indexOf(" ")).toCharArray();
char[] result = equation.substring(equation.indexOf(" ") + 1).toCharArray();
for(int i=0, j=0; i<result.length; i++) {
if( Character.isLetter(result[i]) ) {
result[i] = values[j++];
}
}
return new String(result);
}
public static int CalculateEquation(String equation) {
int result = 0;
int opIndex = IndexOfOperation(equation);
int left = Integer.parseInt( equation.substring(0,opIndex) );
int right = Integer.parseInt( equation.substring(opIndex+1) );
char opChar = equation.charAt(opIndex);
switch(opChar) {
case '+':
result = left + right;
break;
case '-':
result = left - right;
break;
case '*':
result = left * right;
break;
case '/':
result = left / right;
break;
default:
break;
}
return result;
}
public static int IndexOfOperation(String equation) {
int i=0;
while( Character.isDigit(equation.charAt(i)) ) {
i++;
}
return i;
}
}
Output:
Input = 1234567 abc+efg
Translated = 123+456
Result = 579
ackage com.cracking.nutanix;
public class BuildPyramid {
public static void main(String[] args) {
System.out.println( String.format("Input: %d, Possible: %s", 4,isPyramidPossible(4)) );
System.out.println( String.format("Input: %d, Possible: %s", 9,isPyramidPossible(9)) );
System.out.println( String.format("Input: %d, Possible: %s", 6,isPyramidPossible(6)) );
}
public static boolean isPyramidPossible(int bricks) {
int rowBricks = 1;
while(bricks > 0) {
bricks -= rowBricks;
rowBricks += 2;
}
return bricks == 0;
}
}
Output:
Input: 4, Possible: true
Input: 9, Possible: true
Input: 6, Possible: false
The most important thing is to know what are the exact rules of using the wildcard character.
Assumptions:
1. wildcard max count sequentially is 2.
2. wildcard can open, close or be inside parenthesis.
3. if a wildcard is used to close parenthesis then it should be used twice, like in the example.
package com.cracking.amazon;
import java.util.EmptyStackException;
import java.util.Stack;
public class ValidateParenthesisStr {
public static enum Parenthesis {
REGULAR( '(', ')' ),
SQUARE( '[', ']' ),
CURLED( '{', '}' ),
WILDCARD( '*', '*');
Parenthesis(char openChar, char closeChar) {
this.openChar = openChar;
this.closeChar = closeChar;
}
public char openChar;
public char closeChar;
public boolean isParenthesis(char ch) {
return this.openChar == ch || this.closeChar == ch;
}
}
public static final String input = "(*)(*)(*){**";
public static void main(String[] args) {
String output = String.format("Input = %s\nValidation = %s\n", input,validate(input));
System.out.println(output);
}
public static boolean validate(String input) {
Stack<Parenthesis> parenthesisStack = new Stack<Parenthesis>();
for(int i=0; i<input.length(); i++) {
char ch = input.charAt(i);
Parenthesis ps = getParenthesis(ch);
if(ps == null) return false;
if(ps == Parenthesis.WILDCARD && !parenthesisStack.isEmpty() && parenthesisStack.peek() == Parenthesis.WILDCARD) {
// 2 wildcards sequentially
parenthesisStack.pop(); //pop wildcard
if(!parenthesisStack.isEmpty()) parenthesisStack.pop(); //pop open char if exist
continue;
}
if(ch == ps.openChar) {
parenthesisStack.push(ps);
continue;
}
try {
Parenthesis openP = parenthesisStack.pop();
if(openP == ps) {
//No action needed
}else if(openP == Parenthesis.WILDCARD && parenthesisStack.isEmpty()) {
//No action needed
}else if(openP == Parenthesis.WILDCARD && parenthesisStack.peek() == ps) {
openP = parenthesisStack.pop();
}else {
return false;
}
}catch(EmptyStackException e) {
return false;
}
}
return parenthesisStack.isEmpty();
}
public static Parenthesis getParenthesis(char ch) {
if( Parenthesis.REGULAR.isParenthesis(ch) ) {
return Parenthesis.REGULAR;
}
if( Parenthesis.SQUARE.isParenthesis(ch) ) {
return Parenthesis.SQUARE;
}
if( Parenthesis.CURLED.isParenthesis(ch) ) {
return Parenthesis.CURLED;
}
if( Parenthesis.WILDCARD.isParenthesis(ch) ) {
return Parenthesis.WILDCARD;
}
return null;
}
}
Hi,
Assumptions:
1. There will always be 2 arrays that will describe the connection and they will always be in the same length.
2. The arrays arranged in the correct order, the next pair of connection will be the continue of the previous.
For more professional way of detection I think that creating the structure of network in linked list data structure is a better way.
package com.cracking.starup;
public class DetectNetwrokTopology {
public static enum TopologyType {
BUS("Bus"),
CIRCULAR("Circular"),
STAR("Star"),
UNKNOWN("Unknown");
TopologyType(String description) {
this.description = description;
}
public String description;
}
public static final int[] srcNodes = {2,3,4,5};
public static final int[] destNodes = {1,1,1,1};
public static void main(String[] args) {
TopologyType type = getTopolgyType(srcNodes, destNodes);
System.out.println("Topolgy = " + type.description);
}
public static TopologyType getTopolgyType(int[] srcNodes, int[] destNodes) {
if(isTopologyStar(srcNodes, destNodes)) return TopologyType.STAR;
if(isTopologyCircular(srcNodes, destNodes)) return TopologyType.CIRCULAR;
if(isTopologyBus(srcNodes, destNodes)) return TopologyType.BUS;
return TopologyType.UNKNOWN;
}
public static boolean isTopologyBus(int[] srcNodes, int[] destNodes) {
for(int i=0;i<srcNodes.length && i<destNodes.length; i++) {
if( (i+1)<srcNodes.length && (i+1)<destNodes.length ) {
int expected = srcNodes[i+1];
int actual = destNodes[i];
if(actual!=expected) return false;
}
}
return true;
}
public static boolean isTopologyCircular(int[] srcNodes, int[] destNodes) {
int first = srcNodes[0];
int last = destNodes[destNodes.length-1];
return first == last && isTopologyBus(srcNodes,destNodes);
}
public static boolean isTopologyStar(int[] srcNodes, int[] destNodes) {
for(int i=1; i<destNodes.length; i++) {
if(destNodes[0] != destNodes[i]) return false;
}
return true;
}
}
The main idea is to implement the Observable architecture.
We need to create OrderManager Class that observe Order Class for status changes.
package com.cracking.amazon;
import java.util.ArrayList;
import java.util.Calendar;
import java.util.Date;
public class AmazonOrders {
public static interface Observer<T> {
public void onChange(T subject);
}
public static interface Subject<T>{
public boolean registerObserver(Observer<T> observer);
public void notifyAllObservers();
public boolean deleteObserver(Observer<T> observer);
}
public static enum OrderStatus {
Received("Received"),
Assigned("Assigned"),
Delivered("Delivered"),
PickedUp("PickedUp");
public String description;
OrderStatus(String description) {
this.description = description;
}
}
public static class DeliveryBoy {
private int id;
private String name;
public DeliveryBoy(int id, String name){
this.id = id;
this.name = name;
}
}
public static class Order implements Subject<Order> {
private ArrayList<Observer<Order>> observers;
private int id;
private Date expectedTime;
private OrderStatus status;
private DeliveryBoy deliveryBoy;
public Order(int id, Date expectedTime){
this.observers = new ArrayList<Observer<Order>>();
this.id = id;
this.expectedTime = expectedTime;
}
public int getId(){
return this.id;
}
public void assignDeliveryBoy(DeliveryBoy deliveryBoy) {
this.deliveryBoy = deliveryBoy;
this.setStatus(OrderStatus.Assigned);
}
public void setStatus(OrderStatus status) {
this.status = status;
this.notifyAllObservers();
}
@Override
public boolean registerObserver(Observer<Order> observer) {
if(!this.observers.contains(observer)) {
this.observers.add(observer);
return true;
}
return false;
}
@Override
public boolean deleteObserver(Observer<Order> observer) {
return this.observers.remove(observer);
}
@Override
public void notifyAllObservers() {
for(Observer<Order> observer:this.observers) {
observer.onChange(this);
}
}
}
public static class OrderManager implements Observer<Order> {
private ArrayList<Order> orders;
public OrderManager() {
this.orders = new ArrayList<Order>();
}
public boolean addOrder(Order order) {
if(!this.orders.contains(order)){
this.orders.add(order);
order.registerObserver(this);
order.setStatus(OrderStatus.Received);
return true;
}
return false;
}
@Override
public void onChange(Order subject) {
// TODO Auto-generated method stub
String msg = String.format("Order #%d status changed - %s",
subject.getId(),
subject.status.description);
System.out.println(msg);
}
}
public static void main(String[] args) {
OrderManager orderManager = new OrderManager();
DeliveryBoy mainDeliveryBoy = new DeliveryBoy(100, "Main Delivery Boy");
Calendar cal = Calendar.getInstance();
cal.setTime(new Date());
cal.add(Calendar.DATE, 2);
Date date1 = cal.getTime();
Order order1 = new Order(1, date1);
//Order Received
orderManager.addOrder(order1);
//Order Assigned
order1.assignDeliveryBoy(mainDeliveryBoy);
//Order Delivered
order1.setStatus(OrderStatus.Delivered);
//Picked Up
order1.setStatus(OrderStatus.PickedUp);
}
}
***In the onChange method of the OrderManager you can switch between status cases and print custom messages for each case.
Output:
Order #1 status changed - Received
Order #1 status changed - Assigned
Order #1 status changed - Delivered
Order #1 status changed - PickedUp
The idea is to sort the table by UID (In the example the table is sorted by StartTime so we will take this as assumption if not we need to sort it)
After the table is sorted we can loop the table and calculate Max Total for each record.
package com.cracking.amazon;
import java.util.Arrays;
import java.util.Comparator;
public class ResourceConsumption {
public static class LogRecord {
public int UID,PID,StartTime,EndTime,Consumption,Total;
public LogRecord(int UID,int PID,int StartTime,int EndTime,int Consumption) {
this.UID = UID;
this.PID = PID;
this.StartTime = StartTime;
this.EndTime = EndTime;
this.Consumption = Consumption;
this.Total = 0;
}
@Override
public String toString() {
String msg = String.format("\nUID = %d\tPID = %d\tStart = %d\tEnd = %d\tConsumption = %d\t Total = %d\n",
this.UID,
this.PID,
this.StartTime,
this.EndTime,
this.Consumption,
this.Total);
return msg;
}
}
public static LogRecord[] logRecords = {
new LogRecord(1, 1, 200, 300, 100),
new LogRecord(2, 2, 230, 340, 80),
new LogRecord(1, 3, 245, 315, 50),
new LogRecord(1, 4, 305, 330, 20)
};
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println("Data");
System.out.println(Arrays.toString(logRecords));
Arrays.sort(logRecords, new Comparator<LogRecord>() {
@Override
public int compare(LogRecord o1, LogRecord o2) {
// TODO Auto-generated method stub
if(o1.UID < o2.UID) {
return -1; //small
}
if(o1.UID == o2.UID) {
return 0; //equal
}
return 1; //big
}
});
System.out.println("Sorted");
System.out.println(Arrays.toString(logRecords));
System.out.println("Calculate Totals");
calculateTotal(logRecords);
System.out.println(Arrays.toString(logRecords));
int maxInd = getMaxTotal(logRecords);
LogRecord maxRecord = logRecords[maxInd];
System.out.println("Max Totals");
String totalMsg = String.format("UID#%d\nBetween: %d - %d\nMax-Consumption: %d\n",
maxRecord.UID,
maxRecord.StartTime,
maxRecord.EndTime,
maxRecord.Total);
System.out.println(totalMsg);
}
public static void calculateTotal(LogRecord[] logRecords) {
int len = logRecords.length;
for(int i=0; i<len; i++) {
LogRecord rec = logRecords[i];
rec.Total = rec.Consumption;
for(int j=i+1;j<len;j++) {
LogRecord subRec = logRecords[j];
if(subRec.StartTime >= rec.EndTime) {
break;
}
if( (rec.StartTime <= subRec.StartTime) && (rec.EndTime > subRec.StartTime) ) {
rec.Total += subRec.Consumption;
continue;
}
break;
}
}
}
public static int getMaxTotal(LogRecord[] logRecords) {
int maxInd = 0;
int maxVal = logRecords[maxInd].Total;
int len = logRecords.length;
for(int i=1;i<len;i++) {
if(maxVal < logRecords[i].Total) {
maxInd = i;
maxVal = logRecords[i].Total;
}
}
return maxInd;
}
}
Output:
=====
Data
[
UID = 1 PID = 1 Start = 200 End = 300 Consumption = 100 Total = 0
,
UID = 2 PID = 2 Start = 230 End = 340 Consumption = 80 Total = 0
,
UID = 1 PID = 3 Start = 245 End = 315 Consumption = 50 Total = 0
,
UID = 1 PID = 4 Start = 305 End = 330 Consumption = 20 Total = 0
]
Sorted
[
UID = 1 PID = 1 Start = 200 End = 300 Consumption = 100 Total = 0
,
UID = 1 PID = 3 Start = 245 End = 315 Consumption = 50 Total = 0
,
UID = 1 PID = 4 Start = 305 End = 330 Consumption = 20 Total = 0
,
UID = 2 PID = 2 Start = 230 End = 340 Consumption = 80 Total = 0
]
Calculate Totals
[
UID = 1 PID = 1 Start = 200 End = 300 Consumption = 100 Total = 150
,
UID = 1 PID = 3 Start = 245 End = 315 Consumption = 50 Total = 70
,
UID = 1 PID = 4 Start = 305 End = 330 Consumption = 20 Total = 20
,
UID = 2 PID = 2 Start = 230 End = 340 Consumption = 80 Total = 80
]
Max Totals
UID#1
Between: 200 - 300
Max-Consumption: 150
Great solution... I thought about some thing similar but found some problem. How do you treat nodes that are floating without relation. Let's say I have a general course that isn't a pre-requisite to any other course. Would you connect it to the graph in some way? Or you store it in another data structure?
- ProTechMulti November 25, 2018