guilhebl
BAN USERIn Scala:
object Main {
def main(args: Array[String]): Unit = {
println(getClosestYear(99))
println(getClosestYear(15))
println(getClosestYear(0))
println(getClosestYear(18))
println(getClosestYear(10))
println(getClosestYear(6))
println(getClosestYear(2))
println(getClosestYear(1))
}
def getClosestYear(input:Int): Int = {
val currentYear = Calendar.getInstance().get(Calendar.YEAR)
val last2Digits = currentYear % 100
if (input > last2Digits) currentYear - 100 - last2Digits + input
else currentYear - last2Digits + input
}
}
1. build a Trie from words of dictionary
2. test if string is present in Trie (without removing any chars from string). if so return string.
3. if not traverse string from left to right removing one char at a time and testing if resulting substring is present in Trie, repeat this loop removing from end to start (reverse order).
4. If still not found for 1 char, now increase number of chars to 2, and keep removing 2 at a time, and so on checking if word is present in Trie, do the same from end to start (reverse order).
5. keep increasing the number of chars to removed doing this until there's no chars left in String.
public class DictionaryWordCheck {
public static void main(String[] args) {
char[] arr = {'e','o','b', 'a','m','g', 'l'};
List<String> strs = new ArrayList<>();
strs.add("go");
strs.add("bat");
strs.add("me");
strs.add("eat");
strs.add("goal");
strs.add("boy");
strs.add("run");
printList(getDictWordsInArray(arr, strs));
}
private static void printList(List<String> dictWordsInArray) {
for (String string : dictWordsInArray) {
System.out.println(string);
}
}
private static List<String> getDictWordsInArray(char[] arr, List<String> strs) {
List<String> results = new ArrayList<>();
HashSet<Character> setChars = new HashSet<>();
for (int i = 0; i < arr.length; i++) {
setChars.add(arr[i]);
}
for (String string : strs) {
char[] chars = string.toCharArray();
int i = 0;
while(i < chars.length && setChars.contains(chars[i])) {
i++;
}
if (i == chars.length) {
results.add(string);
}
}
return results;
}
}
/*
output:
go
me
goal
*/
Using min-max approach:
public static boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
// int min, int max version
public static boolean isValidBST(TreeNode root, long min, long max) {
if (root == null) {
return true;
}
if (root.val <= min || root.val >= max) {
return false;
}
return isValidBST(root.left, min, root.val) &&
isValidBST(root.right, root.val, max);
}
Solution:
1. convert hour String in int minutes. 1 day = 24 * 60 = 1440 min - Intervals from 0 to 1440. e.g - Interval from 1PM to 1:30PM would be
1 PM = 13 * 60 = 780, 1:30 PM = 13 * 60 + 30 = 8103
PM to 4PM = start : 15 * 60 - end : 16 * 60 = 900 - 960
this will allow minute precision.
calculate for each room, any available interval such that:
src.start <= target.start && src.end >= target.end
return available rooms found:
public class CountAvailableIntervals {
public static void main(String[] args) {
// Room 1 - 10:30AM - 11AM, 4PM - 5 PM
ConfRoom rc1 = new ConfRoom("room 1");
Interval rc1i2 = new Interval(convertHourStringToMinutes("10:30 AM"), convertHourStringToMinutes("11:00 AM"));
Interval rc1i3 = new Interval(convertHourStringToMinutes("4:00 PM"), convertHourStringToMinutes("5:00 PM"));
rc1.addInterval(rc1i2);
rc1.addInterval(rc1i3);
// Room 2 - 10AM - 11AM, 2:30PM - 4PM
ConfRoom rc2 = new ConfRoom("room 2");
Interval rc2i1 = new Interval(convertHourStringToMinutes("10:00 AM"), convertHourStringToMinutes("11:00 AM"));
Interval rc2i2 = new Interval(convertHourStringToMinutes("2:30 PM"), convertHourStringToMinutes("4:00 PM"));
rc2.addInterval(rc2i1);
rc2.addInterval(rc2i2);
// Room 3 - 9AM - 9:30AM, 5PM - 6PM
ConfRoom rc3 = new ConfRoom("room 3");
Interval rc3i1 = new Interval(convertHourStringToMinutes("9:00 AM"), convertHourStringToMinutes("9:30 AM"));
Interval rc3i2 = new Interval(convertHourStringToMinutes("5:00 PM"), convertHourStringToMinutes("6:00 PM"));
rc3.addInterval(rc3i1);
rc3.addInterval(rc3i2);
List<ConfRoom> cfs = new ArrayList<>();
cfs.add(rc1);
cfs.add(rc2);
cfs.add(rc3);
// check for any available room for 9 AM - 9:30AM
printAvailableRooms(getAvailableRooms(cfs, new Interval(convertHourStringToMinutes("9:00 AM"), convertHourStringToMinutes("9:30 AM"))));
// check for any available room for 3PM - 4PM
printAvailableRooms(getAvailableRooms(cfs, new Interval(convertHourStringToMinutes("3:00 PM"), convertHourStringToMinutes("4:00 PM"))));
// check for any available room for 3PM - 4PM
printAvailableRooms(getAvailableRooms(cfs, new Interval(convertHourStringToMinutes("4:00 PM"), convertHourStringToMinutes("5:00 PM"))));
}
private static int convertHourStringToMinutes(String hour) {
int idxOfMin = hour.indexOf(":");
int idxOfSpace = hour.indexOf(" ");
int hours = Integer.parseInt(hour.substring(0, idxOfMin != -1 ? idxOfMin : idxOfSpace));
int mins = idxOfMin != -1 ? Integer.parseInt(hour.substring(idxOfMin+1, idxOfSpace)) : 0;
String ampm = hour.substring(idxOfSpace + 1);
hours += ampm.equalsIgnoreCase("am") ? 0 : 12;
return hours * 60 + mins;
}
private static void printAvailableRooms(List<ConfRoom> cfs) {
for (ConfRoom confRoom : cfs) {
System.out.print(confRoom.name);
}
System.out.println();
}
/*
* Iterate over each available timeslot and check if interval fits
*/
public static boolean isRoomAvailable(ConfRoom cf, Interval interval) {
List<Interval> itvs = cf.intervals;
for (Interval interval2 : itvs) {
if (isIntervalAvailable(interval2, interval)) {
return true;
}
}
return false;
}
// does target fit in src
public static boolean isIntervalAvailable(Interval src, Interval target) {
return (src.start <= target.start && src.end >= target.end);
}
public static List<ConfRoom> getAvailableRooms(List<ConfRoom> cf, Interval interval) {
List<ConfRoom> result = new ArrayList<>();
for (ConfRoom confRoom : cf) {
if (isRoomAvailable(confRoom, interval)) {
result.add(confRoom);
}
}
return result;
}
}
class ConfRoom {
String name;
List<Interval> intervals;
public ConfRoom(String name) {
this.name = name;
intervals = new ArrayList<>();
}
public void addInterval(Interval it) {
if (intervals != null) {
intervals.add(it);
}
}
}
class Interval {
int start;
int end;
public Interval(int start, int end) {
this.start = start;
this.end = end;
}
}
1. Find pivot element (index where sequence changes from ascending to descending) using modified binary search - O (Log n)
2. max element will be either pivot-1 or 0. Min element will always be a corner element, either a[0] or a[a.length-1]. Check for these.
Total time: O(log N)
public class FindMinMax {
public static void main(String[] args) {
int[] a = {2,3,4,5,6,7,10,9,8,7};
int[] a2 = {10,9,8,7,6,5,4,3,2};
int[] a3 = {1,2,3,4,5,6,7,8};
int[] a4 = {6,7,8,10,11,12,13,14,15,16,9,8,7,6};
printMinMax(a);
printMinMax(a2);
printMinMax(a3);
printMinMax(a4);
}
private static void printMinMax(int[] a) {
int pivot = a.length == 1 || a[0] > a[1] ? 0 : findPivot(a, 0, a.length-1);
int max = pivot > 0 ? a[pivot-1] : a[0];
int min = Math.min(a[0], a[a.length-1]);
System.out.println("max = " + max + ", min = " + min);
}
private static int findPivot(int arr[], int low, int high) {
if (high < low)
return -1;
if (high == low)
return low;
int mid = (low + high) / 2;
if (mid < high && arr[mid] > arr[mid + 1])
return mid;
if (mid > low && arr[mid] < arr[mid - 1])
return (mid - 1);
if (arr[low] >= arr[mid])
return findPivot(arr, low, mid - 1);
return findPivot(arr, mid + 1, high);
}
}
Need to check every possible combination of A[i] and A[j]. Problem asks just to count distinct index pairs found that satisfies condition.
O(1) space and O(n^2) time:
public static int maxNumber(int[] a) {
int count = 0;
for (int i = 0; i < a.length - 1; i++) {
for (int j = i + 1; j < a.length; j++) {
if (Math.abs(a[i] - a[j]) <= Math.abs(i - j)) {
count += 2;
}
}
}
return count;
}
For each shard, try to merge list of Keys sequentially.
Boundary of each range (Start-End) will be:
Start - Max (shard.start, key.start)
End - Min (shard.end, key.end)
Start 2 iterators i for Shards and j for keys.
If current shard i contains key advance j
else merge last boundary for shard and key and advance i, advance j if key intersects with newly created range.
public static List<Range> getRanges(List<Shard> shards, List<Key> keys) {
List<Range> r = new ArrayList<>();
Range range = null;
int i = 0;
int j = 0;
Shard shard = null;
Key key = null;
while (i < shards.size() && j < keys.size()) {
shard = shards.get(i);
// set start of new Range
if (range == null) {
range = new Range();
range.i = Math.max(shard.i, keys.get(j).i);
}
// check for each key if it is part of range
while(j < keys.size()) {
key = keys.get(j);
// if key fits in shard
if (shard.i <= key.i && shard.j >= key.j) {
j++;
} else if (shard.j < key.i) {
range.j = j > 0 ? Math.min(keys.get(j - 1).j, shard.j) : shard.j;
r.add(range);
i++;
range = null;
break;
} else if (shard.j > key.i && shard.j < key.j) {
i++;
j++;
break;
} else {
j++;
}
}
}
// set last Range End
if (i < shards.size() && range.j == 0 && j > 0) {
range.j = Math.min(keys.get(j - 1).j, shard.j);
r.add(range);
}
return r;
}
public class CharCountString {
public static void main(String[] args) {
System.out.println(findFirstCharMaxKTimes("hello world"));
System.out.println(findFirstCharMaxKTimes("ho lloh"));
}
public static char findFirstCharMaxKTimes(String s) {
int[] charCount = new int[256];
char[] c = s.toCharArray();
int max = 1;
char firstMax = c[0];
int firstIdxOfMax = 0;
charCount[c[0]]++;
for (int i = 1; i < c.length; i++) {
charCount[c[i]]++;
if (charCount[c[i]] >= max) {
int firstIdxChar = s.indexOf(c[i]);
if (charCount[c[i]] > max || (charCount[c[i]] == max && firstIdxChar < firstIdxOfMax)) {
max = charCount[c[i]];
firstMax = c[i];
firstIdxOfMax = firstIdxChar;
}
}
}
return firstMax;
}
}
public class BiggestWordChain {
public static void main(String[] args) {
String[] w = {"a", "b", "ba", "bca", "bda", "bdca"};
System.out.println(biggestWordChain(w));
String[] w2 = {"a", "b", "ba", "bca", "bda", "bdca", "bdcaf", "f", "bdcafg", "g", "asdsddsdsa", "xyzxyzyxyz"};
System.out.println(biggestWordChain(w2));
}
public static int biggestWordChain(String[] w) {
int max = 1;
Map<String, Integer> wordCount = new HashMap<>();
for (int i = 0; i < w.length; i++) {
wordCount.put(w[i], wordCount.containsKey(w[i]) ? wordCount.get(w[i]) + 1 : 1);
}
// sort by size - start from bigger strings first - greedy aproach
Arrays.sort(w, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return o1.length() > o2.length() ? -1 : o1.length() < o2.length() ? 1 : 0;
}
});
for (int i = 0; i < w.length; i++) {
String s = w[i];
if (s.length() > max) {
int currMax = biggestWordChain(wordCount, new StringBuilder(s));
max = Math.max(max, currMax);
}
}
return max;
}
public static int biggestWordChain(Map<String,Integer> words, StringBuilder s) {
int max = 0;
char[] c = s.toString().toCharArray();
for (int i = 0; i < c.length; i++) {
// try removing char
String newStr = null;
if (i == 0) {
newStr = s.substring(i+1);
} else if (i == c.length-1) {
newStr = s.substring(0, c.length-1);
} else {
newStr = s.substring(0, i) + s.substring(i+1);
}
if (newStr.equals("")) {
return 1;
}
if (words.containsKey(newStr)) {
max = 1;
if (words.get(newStr) > 1) {
words.put(newStr, words.get(newStr) - 1);
} else {
words.remove(newStr);
}
int newMax = 1 + biggestWordChain(words, new StringBuilder(newStr));
max = Math.max(max, newMax);
// put back attempted string - backtrack
words.put(newStr, words.containsKey(newStr) ? words.get(newStr) + 1 : 1);
}
}
return max;
}
}
/*
output:
4
6
*/
public static void main(String[] args) {
String[] d1 = {"bad", "actor", "good", "act"};
String[] d2 = {"bad", "actor", "good", "acting"};
System.out.println(isPermutation("badactorgoodacting", d1));
System.out.println(isPermutation("badactorgoodacting", d2));
String[] d1b = {"bad", "good", "actor", "acting", "action"};
String[] d2b = {"best", "better", "actor", "acting", "movie"};
System.out.println(isPermutation("badgoodaction", d1b));
System.out.println(isPermutation("badgoodactionr", d1b));
System.out.println(isPermutation("betteractingactormovie", d2b));
}
public static boolean isPermutation(String s, String[] w) {
Map<Character, List<String>> mapStrings = new HashMap<>();
for (int i = 0; i < w.length; i++) {
Character key = Character.valueOf(w[i].charAt(0));
if (mapStrings.get(key) != null) {
mapStrings.get(key).add(w[i]);
} else {
List<String> list = new ArrayList<>();
list.add(w[i]);
mapStrings.put(key, list);
}
}
return isPermutation(s, 0, new StringBuilder(), mapStrings, new HashSet<>());
}
public static boolean isPermutation(String s, int start, StringBuilder t, Map<Character, List<String>> w, HashSet<String> usedStrings) {
for (int i = start; i < s.length(); i++) {
if(w.containsKey(s.charAt(i))) {
List<String> l = w.get(s.charAt(i));
Iterator<String> iter = l.iterator();
while (iter.hasNext()) {
String str = iter.next();
// if string fits in remaining length
if (!usedStrings.contains(str) && str.length() <= s.length() - i && s.substring(i, i + str.length()).equals(str)) {
t.append(str);
usedStrings.add(str);
if (t.length() == s.length()) {
return true;
} else if (t.length() < s.length()) {
if(isPermutation(s, i + str.length(), t, w, usedStrings)) {
return true;
}
}
// if no match found using this string prefix remove it
int lastIndex = s.lastIndexOf(str.charAt(0));
if (lastIndex != -1 && lastIndex + str.length() <= t.length() &&
t.substring(lastIndex, lastIndex + str.length()).equals(str)) {
t.delete(lastIndex, lastIndex + str.length());
}
usedStrings.remove(str);
}
}
}
}
return false;
}
}
/*
output:
false
true
true
false
true
*/
public static int[] getZigZag(int[] a) {
if (a == null || a.length <= 1) return a;
int temp;
for (int i = 1; i < a.length; i+=2) {
if (a[i] < a[i-1]) {
temp = a[i];
a[i] = a[i-1];
a[i-1] = temp;
}
if (i < a.length-1 && a[i] < a[i + 1]) {
temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
}
}
return a;
}
public class MultiArrayPermutation {
public static void main(String[] args) {
solveMultiPerms2();
}
public static void solveMultiPerms2() {
String[][] sets = new String[][] {
{ "quick", "slow" },
{ "brown", "red" },
{ "fox", "dog" }
};
List<List<String>> r = new ArrayList<List<String>>();
backtrack(r, sets, new LinkedList<String>(), 0);
printLists(r);
}
private static void printLists(List<List<String>> r) {
for (List<String> list : r) {
for (String string : list) {
System.out.print(string + " ");
}
System.out.println();
}
}
private static void backtrack(List<List<String>> strs, String[][] sets, LinkedList<String> list, int start) {
if (start == sets.length) {
strs.add(new ArrayList<>(list));
} else if (start < sets.length) {
for (int i = 0; i < sets[start].length; i++) {
list.addLast(sets[start][i]);
backtrack(strs, sets, list, start + 1);
list.removeLast();
}
}
}
}
/*
output:
quick brown fox
quick brown dog
quick red fox
quick red dog
slow brown fox
slow brown dog
slow red fox
slow red dog
*/
public class PrintAllPerms {
public static void main(String[] args) {
printAllStringCombinations("abc".toCharArray(), 3);
}
public static void printAllStringCombinations(char[] s, int size) {
List<String> l = getCombinations(s, size);
// filter out invalid strings
List<String> invalidList = new ArrayList<>();
for (String st : l) {
if (!isValid(st)) {
invalidList.add(st);
}
}
l.removeAll(invalidList);
for (String string : l) {
System.out.println(string );
}
}
private static boolean isValid(String st) {
char[] c = st.toCharArray();
int countBs = 0;
int countConsecutiveCs = 0;
for (int i = 0; i < c.length; i++) {
if (c[i] == 'b') {
countBs++;
} else if (c[i] == 'c' && i + 1 < c.length && c[i+1] == 'c') {
countConsecutiveCs++;
}
}
if (countBs > 1 || countConsecutiveCs > 1) {
return false;
}
return true;
}
public static List<String> getCombinations(char[] c, int size) {
List<String> r = new ArrayList<>();
generateCombinations(r, new StringBuilder(), c, size);
return r;
}
public static void generateCombinations(List<String> list, StringBuilder sb, char[] c, int size) {
if (sb.length() == size) {
list.add(sb.toString());
} else {
for (int i = 0; i < c.length; i++) {
sb.append(c[i]);
generateCombinations(list, new StringBuilder(sb.toString()), c, size);
sb.deleteCharAt(sb.length() - 1);
}
}
}
}
public class MaxCityTraffic {
public static void main(String[] args) {
int[][] adj = {
{1,5},
{2,5},
{3,5},
{4,5}
};
int[][] adj2 = {
{1,5},
{3,5},
{4,5},
{2,5},
{2,7},
{2,15}
};
MaxCityTraffic mc = new MaxCityTraffic();
mc.maxTraffic(adj);
System.out.println();
mc.maxTraffic(adj2);
}
public void maxTraffic(int[][] adj) {
// build Graph
int grandTotal = 0;
int idx = 0;
Map<Integer, Node> nodeMap = new HashMap<>();
for (int i = 0; i < adj.length; i++) {
int n1 = adj[i][0];
int n2 = adj[i][1];
Node node1 = null;
if (!nodeMap.containsKey(n1)) {
node1 = new Node(n1, idx);
grandTotal += n1;
idx++;
} else {
node1 = nodeMap.get(n1);
}
Node node2 = null;
if (!nodeMap.containsKey(n2)) {
node2 = new Node(n2, idx);
grandTotal += n2;
idx++;
} else {
node2 = nodeMap.get(n2);
}
node1.neighbors.add(node2);
node2.neighbors.add(node1);
if (!nodeMap.containsKey(n1)) {
nodeMap.put(n1, node1);
}
if (!nodeMap.containsKey(n2)) {
nodeMap.put(n2, node2);
}
}
// iterate over graph and print maxTraffic for each node
for(Map.Entry<Integer, Node> e : nodeMap.entrySet()) {
System.out.println(e.getKey() + " " + maxTraffic(e.getValue(), grandTotal));
}
}
private int maxTraffic(Node node, int grandTotal) {
if (node.neighbors.size() == 1) { // case of leaf
return grandTotal - node.val;
}
int maxLocal = -1;
for(Node n2: node.neighbors) {
maxLocal = Math.max(maxLocal, sumSubtree(n2, node));
}
return maxLocal;
}
private int sumSubtree(Node root, Node excluded) {
int sum = root.val;
for(Node n2 : root.neighbors) {
if (!n2.equals(excluded)) {
sum += sumSubtree(n2, root);
}
}
return sum;
}
}
class Node {
int i;
int val;
Set<Node> neighbors;
public Node(int val, int i) {
super();
this.i = i;
this.val = val;
this.neighbors = new HashSet<>();
}
}
public class SwapKthElements {
public static void main(String[] args) {
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(4);
head.next.next.next = new ListNode(5);
head.next.next.next.next = new ListNode(7);
head.next.next.next.next.next = new ListNode(8);
head = swapKthElements(head, 2);
printList(head);
}
public static ListNode swapKthElements(ListNode head, int k) {
int n = 0;
int i = 1; // start from head as index 1
ListNode node = head;
ListNode node1 = null;
while (node != null) {
if (i == k) {
node1 = node;
}
node = node.next;
i++;
}
int i2 = i - k; // kth from last
node = head;
i = 1;
ListNode node2 = null;
while(node != null) {
if (i == i2) {
node2 = node;
}
node = node.next;
i++;
}
int temp = node1.val;
node1.val = node2.val;
node2.val = temp;
return head;
}
}
// output: 1 - 7 - 4 - 5 - 2 - 8
example 2 is incorrect,{1,2,2} remove element 1 and you shall get array {2} and {2} of equal sum.
Algorithm based on partition set problem, checks for each distinct element if total sum - array[i] % 2, if so then check to see if there's a subset in array without element array[i] which sums to (sum - array[i])/2.
Code in Java:
public class PartitionSet {
public static void main(String[] args) {
int[] a = {1,1,1,1,1};
isDivisible(a);
int[] b = {1,2,2};
isDivisible(b);
}
public static boolean isDivisible(int[] a) {
int sum = 0;
for (int i = 0; i < a.length; i++) {
sum += a[i];
}
boolean foundAny = false;
Map<Integer, Boolean> removableElements = new HashMap<>();
for (int i = 0; i < a.length; i++) {
if (!removableElements.containsKey(a[i])) {
if ((sum - a[i]) % 2 == 0) {
foundAny = isSubsetSum(removeElement(a,i), (sum - a[i])/2);
removableElements.put(a[i], foundAny);
} else {
removableElements.put(a[i], Boolean.FALSE);
}
}
}
if (foundAny) {
StringBuilder sb = new StringBuilder();
for(Map.Entry<Integer, Boolean> e : removableElements.entrySet()) {
if (e.getValue().equals(Boolean.TRUE)) {
sb.append(e.getKey() + " ");
}
}
System.out.println("Yes. removing elements: " + sb.toString());
} else {
System.out.println("No");
}
return foundAny;
}
// returns a new array without element at index i of a
private static int[] removeElement(int[] a, int i) {
int[] b = new int[a.length-1];
int k = 0;
for (int j = 0; j < a.length; j++) {
if (j != i) {
b[k++] = a[j];
}
}
return b;
}
public static boolean isSubsetSum(int[] a, int sum) {
boolean dp[][] = new boolean[sum+1][a.length+1];
// array with sum 0 and any element true
for (int i = 0; i < dp.length; i++) {
dp[0][i] = true;
}
// array with sum non-zero and no element is false
for (int i = 0; i < dp.length; i++) {
dp[i][0] = false;
}
for (int i = 1; i <= sum; i++) {
for (int j = 1; j <= a.length; j++) {
dp[i][j] = dp[i-1][j-1];
if (i >= a[j-1]) {
dp[i][j] = dp[i][j] || dp[i-a[j-1]][j-1];
}
}
}
return dp[sum][a.length];
}
}
public class Toepliz {
public static void main(String[] args) {
int[][] m = {
{6,7,8,9,2},
{4,6,7,8,9},
{1,4,6,7,8},
{0,1,4,6,7}
};
System.out.println(isToepliz(m));
int[][] m2 = {
{6,7,8,9,2},
{4,6,7,8,9},
{1,4,6,2,8},
{0,1,4,6,7}
};
System.out.println(isToepliz(m2));
}
public static boolean isToepliz(int[][] m) {
int col = m[0].length-1;
int c1 = -1, r1 = -1;
int val = -1;
while (col >= 0) {
c1 = col;
r1 = 0;
val = m[r1][c1];
if (!checkDiagonal(val, m, r1,c1)) {
return false;
}
col--;
}
int row = 1;
while (row < m.length) {
c1 = 0;
r1 = row;
val = m[r1][c1];
if (!checkDiagonal(val, m, r1,c1)) {
return false;
}
row++;
}
return true;
}
private static boolean checkDiagonal(int val, int[][] m, int r1, int c1) {
while(c1 < m[0].length && r1 < m.length) {
if (m[r1][c1] != val) {
return false;
}
r1++;
c1++;
}
return true;
}
}
Greedy solution approach:
1. Filter all Triples not fit for selection (not within range) - O(n)
2. Sort triples according to weight formula (num. uncovered range length + cost). Best options will be picked first - O(n logn)
3. Keep removing triples from list while full range not covered and while list not empty.
Total Time: - O(n log n)
public class MinCostPaint {
public static void main(String[] args) {
Range r = new Range(0,5);
Triple t1 = new Triple(0,5, 10);
Triple t2 = new Triple(0,4, 1);
Triple t3 = new Triple(0,2, 5);
Triple t4 = new Triple(2,5, 1);
List<Triple> list = new ArrayList<>();
list.add(t1);
list.add(t2);
list.add(t3);
list.add(t4);
findMinCostPaint(r, list);
Triple t2a = new Triple(1,4, 10);
Triple t2b = new Triple(2,5, 6);
List<Triple> list2 = new ArrayList<>();
list2.add(t2a);
list2.add(t2b);
findMinCostPaint(r, list2);
}
public static int findMinCostPaint(Range r, List<Triple> ts) {
List<Triple> tss = new ArrayList<>();
for (Triple triple : ts) {
if (triple.s >= r.s && triple.s < triple.e) {
tss.add(triple);
}
}
tss.sort(new TripleComparator(r));
List<Triple> result = new ArrayList<>();
Map<Integer, Boolean> paintedMap = new HashMap<>();
for (int i = r.s; i <= r.e; i++) {
paintedMap.put(i, Boolean.FALSE);
}
int paintedCount = 0;
int cost = 0;
while(!tss.isEmpty() && paintedCount < paintedMap.size()) {
Triple t = tss.remove(0);
for (int i = t.s; i <= t.e; i++) {
if (paintedMap.containsKey(i) && paintedMap.get(i).equals(Boolean.FALSE)) {
paintedMap.put(i, Boolean.TRUE);
paintedCount++;
}
}
cost += t.cost;
result.add(t);
}
if (paintedCount < paintedMap.size()) {
System.out.println("No possible ranges");
return -1;
}
for (Triple triple : result) {
System.out.println("(" + triple.s + "," + triple.e + ")");
}
System.out.println("min cost = " + cost);
return cost;
}
}
class TripleComparator implements Comparator<Triple> {
private Range rangeToCover;
public TripleComparator(Range rangeToCover) {
super();
this.rangeToCover = rangeToCover;
}
@Override
public int compare(Triple o1, Triple o2) {
Integer o1RangeUnCovered = (rangeToCover.e - o1.e) + (o1.s - rangeToCover.s);
if (o1RangeUnCovered < 0) {
o1RangeUnCovered = rangeToCover.e - rangeToCover.s;
}
Integer o2RangeUnCovered = (rangeToCover.e - o2.e) + (o2.s - rangeToCover.s);
if (o2RangeUnCovered < 0) {
o2RangeUnCovered = rangeToCover.e - rangeToCover.s;
}
Integer o1Weight = o1RangeUnCovered + o1.cost;
Integer o2Weight = o2RangeUnCovered + o2.cost;
return o1Weight.compareTo(o2Weight);
}
}
class Range {
Integer s;
Integer e;
public Range(int s, int e) {
super();
this.s = s;
this.e = e;
}
}
class Triple extends Range {
Integer cost;
public Triple(int s, int e, int cost) {
super(s, e);
this.cost = cost;
}
}
/**
output:
(0,4)
(2,5)
min cost = 2
No possible ranges
/**
* Task is to detect if robot walks in a square. For that we need to find a cycle in path (360 turn)
* and if robot returns to origin after a while.
1. Start Robot looking North, Angle 0.
2. For each rotation move check if full cycle has been achieved >= 360 angle
3. Use a large treshold and test sample from i ... treshold times repeatedly.
4. If full turn not achieved return false
Time: O(T * N) where T is the testing treshold and N array of moves size.
*/
public class DetectRobotCycle {
public static void main(String[] args) {
int m[] = {10, 180, 10};
System.out.println(isWallPossible(m));
int m1[] = {10, 45, 10, -45, 10, 45};
System.out.println(isWallPossible(m1));
int m2[] = {10, 45, 10, -45, 10, 45, 10, -45};
System.out.println(isWallPossible(m2));
}
public static boolean isWallPossible(int[] moves) {
int treshold = 10000;
int i = 0;
Position p = new Position(0, MoveDirection.N); // start north
boolean rotate = false;
while (i < treshold) {
rotate = false;
for (int j = 0; j < moves.length; j++) {
if (rotate) {
p.addAngle(moves[j]);
} else {
p.addSteps(moves[j]);
}
rotate = !rotate;
}
if (p.cycled && p.x == 0 && p.y == 0) {
return true;
}
i++;
}
return false;
}
}
class Position {
int x;
int y;
int angle;
MoveDirection d;
boolean cycled;
public Position(int angle, MoveDirection d) {
super();
x = y = 0;
this.angle = angle;
this.d = d;
this.cycled = false;
}
public void addSteps(int s) {
if (d.equals(MoveDirection.N)) {
y += s;
} else if (d.equals(MoveDirection.E)) {
x += s;
} else if (d.equals(MoveDirection.S)) {
y -= s;
} else if (d.equals(MoveDirection.W)) {
x -= s;
}
}
public void addAngle(int a) {
angle += a;
if (angle >= 360) {
angle = angle % 360;
cycled = true;
}
if(angle >= 0 && angle < 90) {
d = MoveDirection.N;
}
else if(angle >= 90 && angle < 180) {
d = MoveDirection.E;
}
else if(angle >= 180 && angle < 270) {
d = MoveDirection.S;
}
else if(angle >= 270 && angle < 360) {
d = MoveDirection.W;
}
}
}
enum MoveDirection {
N,E,S,W;
}
/**
output:
true
false
false
*/
public static int[] getSum1Array(int[] a) {
if (a == null || a.length == 0) {
return null;
}
int[] r = new int[a.length];
boolean carry = true;
int i = a.length - 1;
while(i >= 0) {
if (carry && a[i] < 9) {
r[i] = a[i] + 1;
carry = false;
} else if (carry && a[i] == 9) {
r[i] = 0;
} else {
r[i] = a[i];
}
i--;
}
if (carry) {
int[] r2 = new int[r.length + 1];
Arrays.fill(r2, 0);
r2[0] = 1;
return r2;
}
return r;
}
public static String printReversedOnlyOnce(String s) {
if (s == null || s.equals("")) {
return null;
}
StringBuilder sb = new StringBuilder();
char[] c = s.toCharArray();
Map<Character, Boolean> mapChars = new HashMap<>();
for (int i = c.length - 1; i >= 0; i--) {
if (!mapChars.containsKey(c[i])) {
sb.append(c[i]);
mapChars.put(c[i], Boolean.TRUE);
}
}
return sb.toString();
}
public class RemoveCharOptimizer {
public static void main(String[] args) {
System.out.println(getMinLexReplacedString("cbacdcbc"));
System.out.println(getMinLexReplacedString("xyzadatyxzttttacacacbcbbb"));
}
public static String getMinLexReplacedString(String s) {
if (s == null || s.equals("")) {
return null;
}
Map<Character, Integer> mapChars = new HashMap<>();
int cnt = 0;
char c;
char[] chars = s.toCharArray();
int n = s.length();
boolean toRemove[] = new boolean[n];
boolean searchMore = false;
for (int i = 0; i < n; i++) {
if (!mapChars.containsKey(chars[i])) {
mapChars.put(chars[i], 1);
} else {
cnt = mapChars.get(chars[i]);
mapChars.put(chars[i], cnt + 1);
}
}
for (int i = 0; i < n; i++) {
c = chars[i];
cnt = mapChars.get(c);
if (cnt > 1) {
if (i + cnt >= (n - 1)) {
cnt--;
mapChars.put(c, cnt);
toRemove[i] = true;
} else {
searchMore = true;
if ((i + 1) < n && Character.compare(c, chars[i + 1]) < 0 && mapChars.get(chars[i + 1]) == 1) {
searchMore = false;
}
for (int j = i + 1; j < n && searchMore; j++) {
if (Character.compare(c, chars[j]) > 0) {
cnt--;
mapChars.put(c, cnt);
toRemove[i] = true;
searchMore = false;
}
}
}
}
}
StringBuilder sb = new StringBuilder();
mapChars = new HashMap<>();
for (int i = 0; i < toRemove.length; i++) {
if (!toRemove[i] && !mapChars.containsKey(chars[i])) {
sb.append(chars[i]);
mapChars.put(chars[i], 1);
}
}
return sb.toString();
}
}
public static List<List<Integer>> findSegments(int[] a) {
if (a == null || a.length == 0) {
return null;
}
List<List<Integer>> r = new ArrayList<>();
List<Integer> l = new ArrayList<>();
l.add(a[0]);
if (a.length == 1) {
r.add(l);
return r;
}
for (int i = 1; i < a.length; i++) {
if (a[i] - a[i - 1] == 1) {
l.add(a[i]);
} else {
r.add(l);
l = new ArrayList<>();
l.add(a[i]);
}
}
if (l.size() > 0) {
r.add(l);
}
return r;
}
Time: O(n), Space: O(n)
public static int[] getMissingArr(int[] a) {
if (a == null) {
return null;
}
int n = a.length * 2;
boolean present[] = new boolean[n];
int i = 0, j = 0;
int numMissing = n;
for (i = 0; i < a.length; i++) {
present[a[i]] = true;
numMissing--;
}
i = 0;
j = 0;
int[] r = new int[numMissing];
while(i < present.length && j < r.length) {
if (!present[i]) {
r[j] = i;
j++;
}
i++;
}
return r;
}
public class IntervalMerge {
public static void main(String[] args) {
List<Interval> list = new ArrayList<>();
Interval i1 = new Interval(2,6);
Interval i2 = new Interval(3,5);
Interval i3 = new Interval(7,21);
Interval i4 = new Interval(20,21);
list.add(i1);
list.add(i2);
list.add(i3);
list.add(i4);
IntervalMerge im = new IntervalMerge();
List<Interval> r = im.getOptimalIntervalList(list);
for (Interval interval : r) {
System.out.println(interval.s + " " + interval.e);
}
}
public List<Interval> getOptimalIntervalList(List<Interval> list) {
if (list == null || list.isEmpty()) {
return null;
}
Collections.sort(list);
List<Interval> r = new ArrayList<>();
int n = list.size();
boolean keep[] = new boolean[n];
Arrays.fill(keep, true);
Interval in1, in2;
int i = 1;
while (i < n) {
if (keep[i]) {
in1 = list.get(i);
in2 = list.get(i - 1);
if (in1.containsInterval(in2)) {
keep[i - 1] = false;
} else if (in2.containsInterval(in1)) {
keep[i] = false;
}
}
i++;
}
for (int j = 0; j < keep.length; j++) {
if (keep[j]) {
r.add(list.get(j));
}
}
return r;
}
}
class Interval implements Comparable<Interval> {
Integer s;
Integer e;
public Interval(int s, int e) {
super();
this.s = s;
this.e = e;
}
public boolean containsInterval(Interval i2) {
return (this.s <= i2.s && this.e >= i2.e);
}
@Override
public int compareTo(Interval o) {
return this.s.compareTo(o.s);
}
}
public class CombinationNumberKBits {
public static void main(String[] args) {
printCombinationsKBits(3);
}
public static void printCombinationsKBits(int k) {
if (k <= 0) return;
int pow = new Double(Math.pow(2, k)).intValue();
int i = 0, j = 0;
int num = 0;
List<int[]> r = new ArrayList<>();
int[] arr = null;
while (i < pow) {
num = i;
j = k-1;
arr = new int[k];
while(num > 0 && j >= 0) {
if ((num & 1) > 0) {
arr[j] = 1;
}
j--;
num = num >> 1;
}
i++;
r.add(arr);
}
for (int l = 0; l <= k && !r.isEmpty(); l++) {
List<int[]> subset = findArraysWithKBits(r, l);
printArrays(subset);
r.removeAll(subset);
}
}
private static List<int[]> findArraysWithKBits(List<int[]> arr, int k) {
List<int[]> r = new ArrayList<>();
for (int[] is : arr) {
if (countBits(is) == k) {
r.add(is);
}
}
return r;
}
public static int countBits(int[] arr) {
int count = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 1) {
count++;
}
}
return count;
}
public static void printArrays(List<int[]> arr) {
for (int[] is : arr) {
System.out.println();
for (int i = 0; i < is.length; i++) {
System.out.print(is[i] + " ");
}
}
}
}
// ouput:
/*
0 0 0
0 0 1
0 1 0
1 0 0
0 1 1
1 0 1
1 1 0
1 1 1
*/
public class ValidateJSONString {
public static void main(String[] args) {
System.out.println(isValidJSON("{a:b}"));
System.out.println(isValidJSON("{a:b, c:d}"));
System.out.println(isValidJSON("{a:b,c:{e:f}}"));
System.out.println(isValidJSON("{{a}}"));
System.out.println(isValidJSON("{{}}"));
System.out.println(isValidJSON("{}"));
System.out.println(isValidJSON("{a:b, c:dmomomo, f:efefefeokfoekfoekf, obj:{}}"));
System.out.println(isValidJSON("{a:b, , c:dm}"));
System.out.println(isValidJSON("{a:b, c:d:m}"));
}
public static boolean isValidJSON(String s) {
if (s == null || s.equals("") || s.length() <= 1) {
return false;
}
Stack<Character> stCBStart = new Stack<>();
StringBuilder temp = new StringBuilder();
char[] c = s.toCharArray();
int j = 0;
char cj;
for (int i = 0; i < c.length; i++) {
if (c[i] == '{') {
if (!stCBStart.isEmpty()) {
if (temp.length() != 0) {
j = temp.length()-1;
if (temp.charAt(j) != ':') {
return false;
}
cj = temp.charAt(j);
j--;
while(j >= 0 && cj != ',') {
cj = temp.charAt(j);
j--;
}
if (j == 0) {
temp = new StringBuilder();
} else if (j > 0 && cj == ',' && (j + 1) < temp.length()) {
temp.delete(j + 1, temp.length());
}
if (temp.length() > 0) {
if (!validateJSONStr(temp)) {
return false;
}
temp = new StringBuilder();
}
}
}
stCBStart.push('{');
} else if (c[i] == '}') {
if (stCBStart.isEmpty()) {
return false;
}
if (temp.length() > 0) {
if (!validateJSONStr(temp)) {
return false;
}
temp = new StringBuilder();
}
stCBStart.pop();
} else {
temp.append(c[i]);
}
}
if (stCBStart.size() > 0 || temp.length() > 0) {
return false;
}
return true;
}
private static boolean validateJSONStr(StringBuilder temp) {
String[] commas = temp.toString().split(",");
if (commas.length > 0) {
for (int i = 0; i < commas.length; i++) {
if (!isValidJSONExp(commas[i])) {
return false;
}
}
} else {
if (!isValidJSONExp(temp.toString())) {
return false;
}
}
return true;
}
private static boolean isValidJSONExp(String string) {
String[] groups = string.split(":");
return groups != null && groups.length == 2;
}
}
// output:
/*
true
true
true
false
true
true
true
false
false
*/
The solution below tries to form a palindrome centered on each index i of String. Considering even and odd scenarios.Time:O(n^2) where n is length of string, Space: O(1)
public class LongestPalindromic {
public static void main(String[] args) {
System.out.println(longestPalindromicSubstring("AABCDCBA"));
System.out.println(longestPalindromicSubstring("DEFABCBAYT"));
}
public static String longestPalindromicSubstring(String s) {
if (s == null || s.equals("")) {
return null;
}
if (s.length() == 1) {
return s;
}
char[] c = s.toCharArray();
int low = -1;
int hi = -1;
int len = s.length();
int maxL = 0;
int maxI = -1;
int maxJ = -1;
for (int i = 1; i < c.length; i++) {
// even
hi = i;
low = i - 1;
while(low >= 0 && hi < len && c[low] == c[hi]) {
if ((hi - low + 1) > maxL) {
maxL = hi - low + 1;
maxI = low;
maxJ = hi;
}
hi++;
low--;
}
// odd
hi = i + 1;
low = i - 1;
while(low >= 0 && hi < len && c[low] == c[hi]) {
if ((hi - low + 1) > maxL) {
maxL = hi - low + 1;
maxI = low;
maxJ = hi;
}
low--;
hi++;
}
}
if (maxL > 1) {
return s.substring(maxI, maxJ + 1);
}
return s.substring(0, 1);
}
}
Perform BFS traversal and keep track of the level with an int var incrementing it as each level + 1 for each next level until you reach leafs (no children), for each leaf in List of nodes of level check:
if (node-> left != null && node->left->right != null && node->left->right.equals(node)) {
return level;
}
not sure if I understood correctly the problem statement.
number of blocks = (last index of Damaged - first index of damaged) + 1
example above: (6 - 2) + 1 = 5,
other example, 1,2,3,4,5,6,7,8,9,10,11,12 N = 4(4,6,8,10). Ans would be 10 - 4 + 1 = 7 (4,5,6,7,8,9,10).
In-Order traversal, compare subtree from left and right, when Max subtree size found return max. Repeat for each subtree and compare with global max found.
public static void main(String[] args) {
/*
* 4
* / \
* 2 2
* / \ /\
* 1 3 1 3
*/
Node n2a = new Node(1, null, null);
Node n2b = new Node(3, null, null);
Node n2c = new Node(1, null, null);
Node n2d = new Node(3, null, null);
Node n1a = new Node(2, n2a, n2b);
Node n1b = new Node(2, n2c, n2d);
Node n0 = new Node(4, n1a, n1b);
System.out.println(maxDuplicateSubtree(n0, new StringBuilder(), 0));
// output - 3
}
public static int maxDuplicateSubtree(Node root, StringBuilder path, int maxSubtree) {
if (root == null) {
return 0;
}
StringBuilder leftPath = new StringBuilder();
StringBuilder rightPath = new StringBuilder();
int max = 0;
int maxLeft = maxDuplicateSubtree(root.left, leftPath, maxSubtree);
path.append(leftPath).append(root.v);
int maxRight = maxDuplicateSubtree(root.right, rightPath, maxSubtree);
max = Math.max(maxLeft, maxRight);
path.append(rightPath);
if (leftPath.toString().equals(rightPath.toString())) {
max = Math.max(leftPath.length(), max);
}
maxSubtree = Math.max(max, maxSubtree);
return maxSubtree;
}
public static String encodeStr(String str) {
char[] c = str.toCharArray();
char cur;
char prev;
int j = 0;
StringBuilder sb = new StringBuilder(new Character(str.charAt(0)).toString());
for (int i = 1; i < c.length; i++) {
cur = c[i];
prev = c[i-1];
j = 0;
if (cur == prev) {
while (cur == prev) {
j++;
i++;
cur = c[i];
prev = c[i-1];
}
}
if (j > 1) {
sb.deleteCharAt(sb.length()-1);
sb.append(j + 1).append("x").append(prev);
i--;
} else {
sb.append(cur);
}
}
return sb.toString();
}
public class Solution {
public static void main(String[] args) {
Integer[] a = {1,2,3,4,5,6,7,8,9};
printArray(getReversedNSectionArray(a, 3));
}
private static void printArray(Integer[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
public static Integer[] getReversedNSectionArray(Integer[] a, int n) {
if (a == null || n > a.length || n < 1) {
return null;
}
if (n == 1) {
return a;
}
int len = a.length;
// if n = len just return reversed array
if (n == len) {
return (Integer[]) Arrays.asList(a).stream().sorted((f1, f2) -> Integer.compare(f2, f1) * -1).toArray();
}
int s = -1; // sector size
int rem = len; // remaining elements
int i = 0;
int j = 0;
int k = 0;
while (i < len) {
s = (n > rem) ? rem : n; // possible sector size
j = i;
k = i + s - 1;
while (j < k) {
swap(a, j, k);
j++;
k--;
}
i += s;
rem -= s;
}
return a;
}
private static void swap(Integer[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
public class Solution {
public static void main(String[] args) {
String s = "abbaccdbac";
printOccurencesChars(s);
}
// assuming only ASCII chars in string.
private static void printOccurencesChars(String s) {
int[] count = new int[256];
for (int i = 0; i < count.length; i++) {
count[i] = 0;
}
char[] c = s.toCharArray();
int charVal = -1;
for (int i = 0; i < c.length; i++) {
charVal = (int) c[i];
count[charVal]++;
}
StringBuilder sb = new StringBuilder();
int charCount = -1;
for (int i = 0; i < count.length; i++) {
charCount = count[i];
if (charCount > 0) {
sb.append((char)i + "" + charCount);
}
}
System.out.println(sb.toString());
}
}
public class Solution {
public static void main(String[] args) {
Set<String> stringSet = new HashSet<String>();
getPermutationOfStringFiltered("heysam".toCharArray(), 0, "hey", "sam", stringSet);
List<String> strs = stringSet.stream().sorted().collect(Collectors.toList());
printSets(strs);
}
public static void getPermutationOfStringFiltered(char[] a, int i, String s1, String s2, Set<String> stringSet) {
if (i == a.length) {
String s = new String(a);
if (isValidString(s, s1.toCharArray()) && isValidString(s, s2.toCharArray())) {
stringSet.add(s);
}
} else if (i < a.length) {
for (int j = i; j < a.length; j++) {
swap(a, i, j);
getPermutationOfStringFiltered(a, i + 1, s1, s2, stringSet);
swap(a, i, j);
}
}
}
private static boolean isValidString(String string, char[] c) {
int index = -1;
int indexNext = -1;
for (int i = 0; i + 1 < c.length; i++) {
index = string.indexOf(c[i]);
indexNext = string.lastIndexOf(c[i + 1]);
if (index >= indexNext) {
return false;
}
}
return true;
}
private static void swapElements(char[] arr, int i, int j) {
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// generates:
/*
hesamy
hesaym
hesyam
heysam
hsaemy
hsaeym
hsamey
hseamy
hseaym
hseyam
sahemy
saheym
sahmey
samhey
shaemy
shaeym
shamey
sheamy
sheaym
sheyam
*/
Enables for minute precision interval booking, a user can book a meeting in any length given in minutes.
solution:
1.transform day length in int minutes. 1 day = 24 * 60 = 1440min-Intervals from 0 to 1440
calculate for each room, any available interval such that:
src.start <= target.start && src.end >= target.end
public class CountAvailableIntervals {
public static void main(String[] args) {
// Room 1 - 8AM - 9AM, 10:30AM - 11AM, 4PM - 5 PM
ConfRoom rc1 = new ConfRoom();
Interval rc1i1 = new Interval(480, 540);
Interval rc1i2 = new Interval(630, 660);
Interval rc1i3 = new Interval(960, 1020);
rc1.addInterval(rc1i1);
rc1.addInterval(rc1i2);
rc1.addInterval(rc1i3);
// Room 2 - 10AM - 12PM, 2:30PM - 4PM
ConfRoom rc2 = new ConfRoom();
Interval rc2i1 = new Interval(600, 720);
Interval rc2i2 = new Interval(870, 960);
rc2.addInterval(rc2i1);
rc2.addInterval(rc2i2);
// Room 3 - 7AM - 8:30AM, 5PM - 6PM
ConfRoom rc3 = new ConfRoom();
Interval rc3i1 = new Interval(420, 510);
Interval rc3i2 = new Interval(1020, 1080);
rc3.addInterval(rc3i1);
rc3.addInterval(rc3i2);
List<ConfRoom> cfs = new ArrayList<>();
cfs.add(rc1);
cfs.add(rc2);
cfs.add(rc3);
// check for any available room for 8 AM - 9AM
System.out.println(isAvailableRooms(cfs, new Interval(480, 540)));
// check for any available room for 3:30 PM - 5PM
System.out.println(isAvailableRooms(cfs, new Interval(930, 1020)));
// count available rooms from 10:30AM - 11AM
System.out.println(countAvailableRooms(cfs, new Interval(630, 660)));
}
public static boolean isRoomAvailable(ConfRoom cf, Interval interval) {
List<Interval> itvs = cf.intervals;
for (Interval interval2 : itvs) {
if (isIntervalAvailable(interval2, interval)) {
return true;
}
}
return false;
}
// does target fit in src
public static boolean isIntervalAvailable(Interval src, Interval target) {
return (src.start <= target.start && src.end >= target.end);
}
public static boolean isAvailableRooms(List<ConfRoom> cf, Interval interval) {
for (ConfRoom confRoom : cf) {
if (isRoomAvailable(confRoom, interval)) {
return true;
}
}
return false;
}
public static int countAvailableRooms(List<ConfRoom> cf, Interval interval) {
int roomsAvailable = 0;
for (ConfRoom confRoom : cf) {
if (isRoomAvailable(confRoom, interval)) {
roomsAvailable++;
}
}
return roomsAvailable;
}
}
class ConfRoom {
List<Interval> intervals;
public ConfRoom() {
intervals = new ArrayList<>();
}
public void addInterval(Interval it) {
if (intervals != null) {
intervals.add(it);
}
}
}
class Interval {
int start;
int end;
public Interval(int start, int end) {
this.start = start;
this.end = end;
}
}
// output:
// true
// false
// 2
public class DirectedGraphMaxPath {
public static void main(String[] args) {
NodeDAG n1 = new NodeDAG(3);
NodeDAG n2a = new NodeDAG(9);
NodeDAG n2b = new NodeDAG(4);
NodeDAG n3a = new NodeDAG(1);
NodeDAG n3b = new NodeDAG(8);
NodeDAG n3c = new NodeDAG(2);
NodeDAG n4a = new NodeDAG(4);
NodeDAG n4b = new NodeDAG(5);
NodeDAG n4c = new NodeDAG(8);
NodeDAG n4d = new NodeDAG(2);
List<NodeDAG> children = new ArrayList<>();
children.add(n2a);
children.add(n2b);
n1.children = children;
children = new ArrayList<>();
children.add(n3a);
children.add(n3b);
n2a.children = children;
children = new ArrayList<>();
children.add(n3b);
children.add(n3c);
n2b.children = children;
children = new ArrayList<>();
children.add(n4a);
children.add(n4b);
n3a.children = children;
children = new ArrayList<>();
children.add(n4b);
children.add(n4c);
n3b.children = children;
children = new ArrayList<>();
children.add(n4c);
children.add(n4d);
n3c.children = children;
solveMaxPath(n1);
}
public static void solveMaxPath(NodeDAG root) {
if (root == null) {
return;
}
int sum = 0;
int maxSum = 0;
List<NodeDAG> path = new ArrayList<>();
MaxPathSum mp = new MaxPathSum();
findMaxPath(root, sum, maxSum, path, mp);
printPath(mp.maxPath);
}
private static void printPath(List<NodeDAG> maxPath) {
for (NodeDAG nodeDAG : maxPath) {
System.out.print(nodeDAG.v + " ");
}
}
private static void findMaxPath(NodeDAG root, int sum, Integer maxSum, List<NodeDAG> path, MaxPathSum maxPathSum) {
if (root == null) {
return;
}
sum += root.v;
path.add(root);
if (sum > maxPathSum.max) {
maxPathSum.max = sum;
maxPathSum.maxPath = path;
}
if (root.children != null && !root.children.isEmpty()) {
for (NodeDAG nodeDAG : root.children) {
findMaxPath(nodeDAG, sum, maxSum, new ArrayList<NodeDAG>(path), maxPathSum);
}
}
}
}
class MaxPathSum {
int max;
List<NodeDAG> maxPath;
public MaxPathSum() {
this.max = 0;
this.maxPath = new ArrayList<>();
}
}
class NodeDAG {
int v;
List<NodeDAG> children;
public NodeDAG(int v) {
super();
this.v = v;
}
@Override
public String toString() {
return new Integer(v).toString();
}
}
My Solution solves graph Red-Black using a modified DFS, since if always a tree is guaranteed to exist, then you can pick any node as root and start from it's edge list, there will be a guaranteed path to the spanning tree. Time: O (V + E)
public void findRedBlackSpanningTree() {
List<Edge> r = new ArrayList<>();
boolean[] v = new boolean[nodes.size()];
// FIRST TRY BLACK from this node
dfsBlackRed(nodes.get(0), v, Color.BLACK, r);
if (r.size() == nodes.size() - 1) {
printEdges(r);
}
else // IF FROM BLACK NO SPANNING TREE RED-BLACK found TRY RED
{
r = new ArrayList<>();
v = new boolean[nodes.size()];
dfsBlackRed(nodes.get(0), v, Color.RED, r);
if (r.size() == nodes.size() - 1) {
printEdges(r);
}
}
}
public void dfsBlackRed(Node root, boolean[] visited, Color previousEdgeColor, List<Edge> r) {
visited[root.v - 1] = true;
Node n = null; // neighbor
for (Edge e : root.edges) {
// get neighbor
if (root.v == e.n1.v) {
n = e.n2;
} else {
n = e.n1;
}
if (!visited[n.v - 1] && !e.color.equals(previousEdgeColor)) {
r.add(e);
if (r.size() == this.nodes.size() - 1) {
// found list;
return;
}
dfsBlackRed(n, visited, previousEdgeColor.equals(Color.BLACK) ? Color.RED : Color.BLACK, r);
}
}
}
/*
Sample Test:
Edge e12 = new Edge(n1, n2, Color.BLACK);
Edge e13 = new Edge(n1, n3, Color.BLACK);
Edge e23 = new Edge(n2, n3, Color.RED);
Edge e34 = new Edge(n3, n4, Color.BLACK);
// output:
1 2 Color: BLACK
2 3 Color: RED
3 4 Color: BLACK
*/
public class InterleaveIterator<E> implements Iterator<E> {
private List<Iterator<E>> list;
private int i;
public InterleaveIterator() {
initFields();
}
public InterleaveIterator(List<Iterator<E>> list) {
initFields();
for (Iterator<E> iterator : list) {
addIterator(iterator);
}
}
private void initFields() {
list = new ArrayList<>();
i = 0;
}
public void addIterator(Iterator<E> it) {
list.add(it);
}
public void removeIterator(int index) {
list.remove(index);
if (i == index) {
i++;
}
if (i == list.size()) {
i = 0;
}
}
@Override
public boolean hasNext() {
if (list == null || list.isEmpty()) {
return false;
}
int j = i == list.size() ? 0 : i;
boolean hasNext = hasNextInLoop(j);
if (!hasNext) {
j = 0;
hasNext = hasNextInLoop(j);
}
return hasNext;
}
private boolean hasNextInLoop(int j) {
while (j < list.size()) {
Iterator<E> it = list.get(j);
if (it.hasNext()) {
return true;
}
j++;
}
return false;
}
@Override
public E next() {
if (list == null || list.isEmpty()) {
return null;
}
if (i == list.size()) {
i = 0;
}
E e = getNextInLoop();
if (e == null) {
i = 0;
e = getNextInLoop();
}
return e;
}
private E getNextInLoop() {
while (i < list.size()) {
Iterator<E> it = list.get(i);
i++;
if (it.hasNext()) {
return it.next();
}
}
return null;
}
}
/*
Sample Tests
*/
public static void main(String[] args) {
InterleaveIterator iter = new InterleaveIterator<>();
ArrayList<Integer> i1 = new ArrayList<>();
i1.add(1);
i1.add(2);
i1.add(3);
i1.add(4);
i1.add(5);
List<Node> i2 = new ArrayList<>();
i2.add(new Node(1));
i2.add(new Node(2));
Collection<Element> i3 = new ArrayList<>();
i3.add(new Element(1));
i3.add(new Element(2));
i3.add(new Element(3));
iter.addIterator(i1.iterator());
iter.addIterator(i2.iterator());
iter.addIterator(i3.iterator());
while (iter.hasNext()) {
System.out.print(iter.next() + " , ");
}
}
// output: 1 , n1 , e1 , 2 , n2 , e2 , 3 , e3 , 4 , 5
My solution is a greedy algorithm that expands on every Guard cell updating neighbor distances, after that it does a top down and bottom-up expansion for updating open space cells. Time : O(n^2) space: O(n). Quite extensive code but it works.
public class MuseumDistances {
private static final int UNDISCOVERED = Integer.MAX_VALUE;
public static void main(String[] args) {
char[][] m = {{'O', 'W', 'G', 'O'},
{'O', 'W', 'W', 'O'},
{'O', 'W', 'O', 'O'},
{'O', 'O', 'O', 'G'}};
printMatrix(findDistanceMatrix(m));
char[][] m2 =
{
{'O', 'O', 'G', 'G', 'G'},
{'O', 'W', 'O', 'O', 'O'},
{'O', 'W', 'G', 'W', 'O'},
{'O', 'W', 'W', 'W', 'O'},
{'O', 'O', 'O', 'O', 'O'}};
printMatrix(findDistanceMatrix(m2));
}
public static int[][] findDistanceMatrix(char[][] m) {
int r[][] = new int[m.length][m.length];
// prepare distance matrix
for (int i = 0; i < r.length; i++) {
for (int j = 0; j < r.length; j++) {
if (m[i][j] == 'G') {
r[i][j] = 0;
} else if (m[i][j] == 'W') {
r[i][j] = -1;
} else {
r[i][j] = UNDISCOVERED;
}
}
}
// expand based on Guard cells
for (int i = 0; i < m.length; i++) {
for (int j = 0; j < m.length; j++) {
if (r[i][j] == 0) {
expandDistances(r, i, j);
}
}
}
// top down and bottom up sweep to update open cell neighbors
for (int i = m.length - 1; i >= 0; i--) {
for (int j = m.length - 1; j >= 0; j--) {
if (r[i][j] != 0 && r[i][j] != -1) {
expandDistancesNeighbors(r, i, j, false);
expandDistancesNeighbors(r, i, j, true);
}
}
}
return r;
}
private static void expandDistancesNeighbors(int[][] r, int x, int y, boolean rightDown) {
int i = x, j = y;
int dist = r[x][y];
if (rightDown) {
// expand down
i = x + 1;
while (i < r.length && r[i][j] != 0 && r[i][j] != -1) {
r[i][j] = Math.min(r[i][j], dist + 1);
dist++;
i++;
}
// expand right
i = x;
j = y + 1;
dist = r[x][y];
while (j < r.length && r[i][j] != 0 && r[i][j] != -1) {
r[i][j] = Math.min(r[i][j], dist + 1);
dist++;
j++;
}
} else {
// expand up
i = x - 1;
while (i >= 0 && r[i][j] != 0 && r[i][j] != -1) {
r[i][j] = Math.min(r[i][j], dist + 1);
dist++;
i--;
}
// expand left
i = x;
j = y - 1;
dist = r[x][y];
while (j >= 0 && r[i][j] != 0 && r[i][j] != -1) {
r[i][j] = Math.min(r[i][j], dist + 1);
dist++;
j--;
}
}
}
public static void printMatrix(int[][] a) {
for (int i = 0; i < a.length; i++) {
System.out.println();
for (int j = 0; j < a.length; j++) {
System.out.print(a[i][j] + " ");
}
}
}
public static void expandDistances(int[][] r, int x, int y) {
if (x >= r.length || y >= r.length || x < 0 || y < 0 || r[x][y] == -1) {
return;
} else {
int i = x, j = y;
int dist = 1;
// expand up
i = x - 1;
while (i >= 0 && r[i][j] != 0 && r[i][j] != -1) {
r[i][j] = Math.min(r[i][j], dist);
dist++;
i--;
}
// expand down
i = x + 1;
dist = 1;
while (i < r.length && r[i][j] != 0 && r[i][j] != -1) {
r[i][j] = Math.min(r[i][j], dist);
dist++;
i++;
}
// expand right
i = x;
j = y + 1;
dist = 1;
while (j < r.length && r[i][j] != 0 && r[i][j] != -1) {
r[i][j] = Math.min(r[i][j], dist);
dist++;
j++;
}
// expand left
j = y - 1;
dist = 1;
while (j >= 0 && r[i][j] != 0 && r[i][j] != -1) {
r[i][j] = Math.min(r[i][j], dist);
dist++;
j--;
}
}
}
}
public static void testSolution() {
// test win row
Character[][] board = new Character[][] {
{'X', 'X', 'X'},
{'O', 'X', 'O'},
{'X', 'O', 'O'}
};
System.out.println(detectWin(board));
// test win col
board = new Character[][] {
{'X', 'O', 'X'},
{'X', 'X', 'O'},
{'X', 'O', 'O'}
};
System.out.println(detectWin(board));
// test win diag
board = new Character[][] {
{'X', 'O', 'O'},
{'O', 'X', 'O'},
{'X', 'O', 'X'}
};
// test no win
board = new Character[][] {
{'X', 'O', 'X'},
{'O', 'O', 'X'},
{'X', 'X', 'O'}
};
System.out.println(detectWin(board));
// test win col O
board = new Character[][] {
{'X', 'O', 'O'},
{'O', 'X', 'O'},
{'X', 'O', 'O'}
};
System.out.println(detectWin(board));
}
public static boolean detectWin(Character[][] board) {
return (testToken(board, 'X') || testToken(board, 'O'));
}
public static boolean testToken(Character[][] board, Character token) {
// check rows
int seq = 0;
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board.length; j++) {
if (board[i][j].equals(token)) {
seq++;
}
}
if (seq == 3) {
return true;
}
seq = 0;
}
seq = 0;
// check cols
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board.length; j++) {
if (board[j][i].equals(token)) {
seq++;
}
}
if (seq == 3) {
return true;
}
seq = 0;
}
// check diagonals
if ((board[0][0].equals(token) &&
board[1][1].equals(token) &&
board[2][2].equals(token)) ||
(board[2][0].equals(token) &&
board[1][1].equals(token) &&
board[0][2].equals(token))) {
return true;
}
return false;
}
Slices per person will be bound to either:
1. Total Number of pies / n
2. Min Pie Size.
Start with slices per person as pies/n (optimal scenario). Then try allocating on each pie
that qty. If not all people got served then decrement slices per person.
Code:
public class NumPies {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
list.add(6);
list.add(4);
list.add(6);
list.add(1);
System.out.println(getMaxSlices(list, 8));
}
public static int getMaxSlices(List<Integer> pieSlices, int n) {
if (pieSlices == null || pieSlices.isEmpty()) {
return -1;
}
int totalSlices = 0;
int minPieSize = Integer.MAX_VALUE;
for (Integer i : pieSlices) {
minPieSize = Math.min(minPieSize, i);
totalSlices += i;
}
if (n > totalSlices) {
return -1; // impossible to satisfy all
}
int slicesPerPerson = totalSlices / n;
if (slicesPerPerson >= minPieSize) {
return minPieSize;
}
int pies = 0;
while(pies < n && slicesPerPerson > 0) {
for (Integer i : pieSlices) {
pies += i / slicesPerPerson;
}
if (pies < n) {
pies = 0;
slicesPerPerson--;
}
}
return slicesPerPerson;
}
}
public class ReverseWords {
public static void main(String[] args) {
System.out.println(reverseWords("Man bites dog"));
}
public static String reverseWords(String value) {
if (value == null || value.equals("")) {
return null;
}
String[] words = value.split(" ");
StringBuilder sb = new StringBuilder();
for (int i = words.length - 1; i >= 0; i--) {
sb.append(words[i] + " ");
}
return sb.deleteCharAt(sb.length()-1).toString();
}
}
I came up with a Greedy algorithm for this problem, the idea is to consider all available elements of both arrays as a single pool of available elements. Once you pick a highest available, all the elements before and including that index should be flagged as not available for next iteration. Take care you measure the available K window remaining to not pick elements beyond that limit. Algorithm is returning the right response, please let me know if someone spot any edge cases or errors.
Java implementation:
public static void runSolution() {
int a1[] = {3, 4, 6, 5};
int a2[] = {9, 1, 2, 5, 8, 3};
System.out.println(getMaxKDigitNumber(a1, a2, 5));
}
public static int getMaxKDigitNumber(int[] a1, int[] a2, int k) {
if (a1 == null || a2 == null || a1.length == 0 || a2.length == 0) {
return -1; // error
}
int n = a1.length;
int m = a2.length;
int p = n + m; // pool size
if (k > p) {
return -1; // error
}
int i1 = 0, i2 = 0; // current indexes for each array
int c = 0; // count of how many picked elements so far
int h = 0; // highest element temp var.
int ih = -1; // index of highest found for this iteration
boolean foundInFirstArray = false; // flag to tell where the highest was found if first or last array
boolean[] usedA1 = new boolean[n]; // track used elements from first array.
boolean[] usedA2 = new boolean[m]; // track used elements from 2nd array.
int countSkipped = 0; // temp var used to count skipped elements of pool.
StringBuilder sb = new StringBuilder();
int ptemp = 0;
while (c < k) {
h = 0;
ih = -1;
ptemp = p;
for (int i = i1; ptemp >= (k - c) && i < a1.length; i++) {
if (!usedA1[i] && a1[i] > h) {
h = a1[i];
ih = i;
foundInFirstArray = true;
}
ptemp--;
}
ptemp = p;
for (int i = i2; ptemp >= (k - c) && i < a2.length; i++) {
if (!usedA2[i] && a2[i] > h) {
h = a2[i];
ih = i;
foundInFirstArray = false;
}
ptemp--;
}
countSkipped = 0;
if (foundInFirstArray) {
// mark all as used till ith element
for (int i = 0; i <= ih && i < a1.length; i++) {
if (!usedA1[i]) {
usedA1[i] = true;
countSkipped++;
}
}
sb.append(a1[ih]);
i1 = ih + 1;
} else {
// mark all as used till ith element
for (int i = 0; i <= ih && i < a2.length; i++) {
if (!usedA2[i]) {
usedA2[i] = true;
countSkipped++;
}
}
sb.append(a2[ih]);
i2 = ih + 1;
}
p = p - countSkipped;
c++;
}
return Integer.parseInt(sb.toString());
}
1. Create a HashMap and store Key = element value, Value = Count occurrences of element in array.
2. Traverse array storing element in Map and counting each elements occurrence - O(n)
3. Traverse HashMap and for each Key (element) get it's count. If count % 2 == 1 (Odd) print number.
- Try to find Max of 3 positive numbers in array or else max of 2 neg, 1 pos. Return max of these 2.
- If not found try to find 1 zero, if any then return 0;
- if not then try to find 3 highest negative (closest to zero) return their product.
Time: O(n) - space O(1).
Algorithm implementation in Java:
public static void runSolution() {
int[] a = {-1, 2, 3, -4, -5, -2, -8, -4};
System.out.println(findMaxProduct(a));
}
public static int findMaxProduct(int[] a) {
if (a == null || a.length < 3) {
return -1; // error
}
int nPos = 0; // count of positive nums.
int nNeg = 0; // count of negative nums.
int mPos1 = 0, mPos2 = 0, mPos3 = 0; // max. Found highest 3 positive
int mNeg1 = 0, mNeg2 = 0, mNeg3 = 0; // max. Found lowest 3 negative
int mN1 = Integer.MIN_VALUE, mN2 = Integer.MIN_VALUE, mN3 = Integer.MIN_VALUE; // max. Found highest 3 negative
int zCount = 0; // count of zeros;
for (int i = 0; i < a.length; i++) {
if (a[i] > 0) {
nPos++;
if (a[i] > mPos1) {
mPos3 = mPos2; mPos2 = mPos1; mPos1 = a[i];
} else if (a[i] > mPos2) {
mPos3 = mPos2; mPos2 = a[i];
} else if (a[i] > mPos3) {
mPos3 = a[i];
}
} else if (a[i] < 0) {
nNeg++;
if (a[i] < mNeg1) {
mNeg3 = mNeg2; mNeg2 = mNeg1; mNeg1 = a[i];
} else if (a[i] < mNeg2) {
mNeg3 = mNeg2; mNeg2 = a[i];
} else if (a[i] < mNeg3) {
mNeg3 = a[i];
}
// store min negative if any
if (a[i] > mN1) {
mN3 = mN2; mN2 = mN1; mN1 = a[i];
} else if (a[i] > mN2) {
mN3 = mN2; mN2 = a[i];
} else if (a[i] > mN3) {
mN3 = a[i];
}
} else {
zCount++;
}
}
// fetch highest 3 * positive numbers
int maxPos = 0;
if (nPos >= 3) {
maxPos = mPos1 * mPos2 * mPos3;
}
// fetch highest 1 positive * 2 negative
int maxPos2Neg = 0;
if (nPos >= 1 && nNeg >= 2) {
maxPos2Neg = mNeg1 * mNeg2 * mPos1;
}
// compare both if any and return highest
if (maxPos > 0 && maxPos2Neg > 0) {
return Math.max(maxPos, maxPos2Neg);
} else if (maxPos > 0 && maxPos2Neg == 0) {
return maxPos;
} else if (maxPos == 0 && maxPos2Neg > 0) {
return maxPos2Neg;
}
// return 0 if any found
if (zCount > 1) {
return 0;
}
// if all negative return 3 Min. negative
if (nNeg >= 3) {
return mN1*mN2*mN3;
}
return -1; // error should return any of the cases above.
}
RepI am randy, 29 year old and I am doing a job. I am doing a job as a plant ...
In Java:
- guilhebl May 04, 2017