guilhebl
BAN USERSlightly different approach from aonecoding.
public class Sample {
public static void main(String[] args) {
System.out.println(lonelyPixelCount(new int[][]{ //1: black, 0: white
{0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
{0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
{0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
}));
}
private static int lonelyPixelCount(int[][] picture) {
int m = picture.length, n = picture[0].length;
int total = 0;
//First traversal sum up the count of black pixels by column if sum > 1 tag column as invalid: -1
for(int j = 0; j < n; j++){
int sum = 0;
for(int i = 0; i < m; i++){
sum += picture[i][j];
}
if (sum > 1) {
for(int i = 0; i < m; i++){
if (picture[i][j] > 0) {
picture[i][j] = -1;
}
}
}
}
//check row discarding invalid columns
for(int i = 0; i < m; i++){
int count = 0;
for(int j = 0; j < n; j++) {
if (picture[i][j] == -1 || count > 1) {
break;
}
if (picture[i][j] > 0) {
count++;
}
}
if (count == 1) {
total++;
}
}
return total;
}
}
public String findRepPattern(String str) {
int len = str.length();
for(int i = 1; i <= len/2; ++i) {
if (len % i == 0) {
String prefix = str.substring(0, i);
int start = i;
boolean found = true;
while (start < len && found) {
String lastPrefix = str.substring(start, start + i);
if (lastPrefix.equals(prefix)) {
start += i;
} else {
found = false;
}
}
if (start == len) {
System.out.println("pattern: " + prefix + " N = " + (len / prefix.length()));
return prefix;
}
}
}
return null;
}
public class Example {
public static void main(String[] args) {
Example e = new Example();
List<String> list = new ArrayList<>();
list.add("vil");
list.add("sit");
list.add("flick");
list.add("pat");
list.add("pluck");
list.add("sat");
list.add("vat");
List<String> r = e.getClosestStrings("vit", list, 1);
r.forEach(System.out::println);
}
public List<String> getClosestStrings(String str, List<String> list, int maxDist) {
if (str == null || list == null || list.isEmpty()) return null;
List<String> res = new ArrayList<>();
PriorityQueue<StringDist> pq = new PriorityQueue<>(Comparator.comparingInt(s1 -> s1.dist));
Map<Character, Integer> charCountMap = getCharCountMap(str);
for(String s: list) {
int dist = getDist(getCharCountMap(s), charCountMap);
pq.offer(new StringDist(s, str, dist));
}
while (!pq.isEmpty()) {
StringDist sd = pq.poll();
if (sd.dist > maxDist) break;
res.add(sd.source);
}
return res;
}
private Map<Character, Integer> getCharCountMap(String str) {
Map<Character, Integer> map = new HashMap<>();
for(char c: str.toCharArray()) {
map.put(c, map.getOrDefault(c, 0) + 1);
}
return map;
}
private Integer getDist(Map<Character, Integer> map1, Map<Character, Integer> map2) {
int diff = 0;
for(Map.Entry<Character, Integer> e: map1.entrySet()) {
diff += map2.containsKey(e.getKey()) ? Math.abs(e.getValue() - map2.get(e.getKey())) : e.getValue();
}
return diff;
}
private class StringDist {
String source;
String target;
Integer dist;
public StringDist(String source, String target, Integer dist) {
this.source = source;
this.target = target;
this.dist = dist;
}
}
}
Scala Functional Programming approach:
def findAnagrams(s: String, p: String): List[Int] = {
val map = p.groupBy(identity).mapValues(_.length)
s.zipWithIndex.view.foldLeft(List.empty[Int])((acc, x) => {
if (map.contains(x._1) && x._2 + p.length <= s.length) {
val mapIdx = s.substring(x._2, x._2 + p.length).groupBy(identity).mapValues(_.length)
if (map == mapIdx) acc :+ x._2 else acc
} else {
acc
}
})
}
Using a greedy algorithm approach:
1. Build a Max Heap of Country sorting by number of players, countries with most players will be picked first
2. fill priority queue with input list
3. while queue not empty: iterate collecting players from each country in each cycle until a bucket of size K is filled
4. return num of cycles executed
Implementation of the above idea in Scala:
case class Country(players: Int, name: String)
object SplitKBuckets {
def main(args: Array[String]): Unit = {
println(maxGroupsK(
List(
Country(4, "USA"),
Country(6, "CHI"),
Country(6, "IND"),
Country(3, "BRA"),
Country(2, "AUS"),
Country(1, "CAN")),
3
))
}
def sortByPlayers(c: Country) = c.players
def maxGroupsK(countries: List[Country], k: Int): Int = {
val priorityQueue: PriorityQueue[Country] = PriorityQueue()(Ordering.by(sortByPlayers))
priorityQueue ++= countries
def cycle(): Boolean = {
if (priorityQueue.isEmpty) {
false
} else {
val list = ListBuffer.empty[Country]
var count = 0
while (priorityQueue.nonEmpty && count < k) {
val c = priorityQueue.dequeue()
if (c.players > 1) {
list += Country(c.players - 1, c.name)
}
count += 1
}
priorityQueue ++= list
count == k
}
}
@tailrec def numCycles(count: Int): Int = {
if (!cycle()) count
else numCycles(count + 1)
}
numCycles(0)
}
}
/*
output: 7
*/
const cars = [
{make: "toyota", color: "red", cat: "suv"},
{make: "honda", color: "black", cat: "sedan"},
{make: "toyota", color: "red", cat: "sedan"},
{make: "nissan", color: "blue", cat: "suv"},
];
const rejects = [
{key: "color", value: "black"},
{key: "color", value: "blue"},
{key: "make", value: "honda"},
];
function rejectByKeyValues(items, rejectKeyValues) {
return items.filter(item => {
let isValid = true;
rejectKeyValues.forEach(keyValue => {
if (item[keyValue.key] === keyValue.value) isValid = false;
});
return isValid;
});
}
let r = rejectByKeyValues(cars, rejects);
console.log(r);
Functional approach using Scala:
object MergeCountIntervals {
def main(args: Array[String]): Unit = {
println(mergeSegments(Array(Array(1,4), Array(2,3))))
println(mergeSegments(Array(Array(4,6), Array(1,2))))
println(mergeSegments(Array(Array(1,4), Array(6,8), Array(2,4), Array(7,9), Array(10,15))))
}
def mergeSegments(segments: Array[Array[Int]]): Int = {
if (segments == null || segments.length == 0) return 0
val list = List.empty[Array[Int]]
val merged = segments.sortWith(_(0) < _(0)).foldLeft(list)((seq, s) =>
if (seq.isEmpty || seq.last(1) < s(0)) {
seq :+ s
} else {
val last = seq.last
seq.dropRight(1) :+ Array(last(0), Math.max(last(1), s(1)))
}
)
merged.foldLeft(0)((acc, x) => acc + x(1) - x(0))
}
}
// output:
/*
3
3
11
*/
Use a HashMap and a Doubly Linked List, where Hashmap would have a pointer to the list Node such as Map<Key, ListNode> and List would have ListNode(Value, Left, Right)
and the head of the list would be the most recent element added or read.
HEAD -> * Most recently added or read
TAIL -> * Least recently read or added, "oldest" element
For set(Key, value) check if key exists in HashMap, if so get ListNode and set new value make it HEAD, set left and right pointers accordingly. If not create new ListNode, set it as new HEAD and make HEAD -> right point to old HEAD.
For get(Key) check if key exists in HashMap, if so get ListNode and make it HEAD, set left and right pointers accordingly. Return value. If it does not exits return null or throw exception.
For delete(Key) check if key exists in HashMap, if so get ListNode and set left and right pointers accordingly eliminate this node and remove it from hashmap . Return value. If it does not exits return null or throw exception.
For last() check if list is empty, if not return HEAD, If empty return null.
There will be 3 scenarios to consider:
- node is 0 and is leaf: simply remove node from parent children, return empty
- node is 0 and is a parent with non-empty valid children: make first child as the new "promoted" parent and return new collection of filtered-out children
- node is non-zero, return node and return filtered-out children
implementation of the above idea in Scala:
package code.tree
case class TreeNode(nodes: Seq[TreeNode] = Seq.empty, data: Int = 0)
object RemoveNodes {
def main(args: Array[String]): Unit = {
// Let us create the tree
val root = TreeNode(
nodes = Seq(
TreeNode(nodes = Seq(
TreeNode(data = 25), TreeNode(), TreeNode(data = 30), TreeNode()),
data = 14),
TreeNode(nodes = Seq(
TreeNode(data = 18), TreeNode(), TreeNode(data = 11), TreeNode()),
data = 6),
TreeNode(nodes = Seq(
TreeNode(data = 4), TreeNode(), TreeNode(data = 3), TreeNode())),
TreeNode(nodes = Seq(
TreeNode(), TreeNode(), TreeNode(data = 5), TreeNode(nodes = Seq(
TreeNode(data = 7), TreeNode(), TreeNode(data = 9), TreeNode()))))
),
data = 12
)
// Remove 0s
val head = removeZeros(root)
printTree(head)
}
def printTree(node: Option[TreeNode]): Unit = {
node match {
case Some(x) => printTree(x)
case _ => println("Empty tree")
}
}
def printTree(node: TreeNode): Unit = {
println(node.data)
node.nodes.foreach(printTree)
}
def getValidChildren(node: TreeNode) = {
node.nodes.map(removeZeros).filter(_.isDefined).map(_.get)
}
def removeZeros(node: TreeNode): Option[TreeNode] = {
if (node.data == 0 && node.nodes.isEmpty) {
None
}
else if (node.data == 0 && node.nodes.nonEmpty) {
val validChildren = getValidChildren(node)
Some(
TreeNode(
data = validChildren.head.data,
nodes = validChildren.drop(1)
)
)
}
else {
Some(
TreeNode(
data = node.data,
nodes = getValidChildren(node)
)
)
}
}
}
// output:
/*
12
14
25
30
6
18
11
4
3
5
7
9
*/
In Scala:
def binTreeToList(node: TreeNode): TreeNode = {
if (node == null) {
node
} else {
var newNode = binTreeToListUtil(node)
while (newNode.left != null) newNode = newNode.left
newNode
}
}
def binTreeToListUtil(node: TreeNode): TreeNode = {
if (node != null) {
if (node.left != null) {
var left = binTreeToListUtil(node.left)
while (left.right != null) left = left.right
left.right = node
node.left = left
}
if (node.right != null) {
var right = binTreeToListUtil(node.right)
while (right.left != null) right = right.left
right.left = node
node.right = right
}
}
node
}
use a MaxHeap based on Rate, and run:
1. pass through collection adding all elements to heap - O ( n )
2. Extract 10 max elements from heap.
Total time: O ( n )
In Java 8 Heap can be implemented as a PriorityQueue.
Example using Scala:
case class Video (name: String, rate: Int)
val sample = Seq(Video("Ghost", 56), Video("Titanic", 74), Video("Alien", 88), Video("Krappe", 18),
Video("Krappe", 18), Video("VideoA1", 43), Video("VideoA2", 63), Video("VideoA3", 58),
Video("Krappe2", 12), Video("VideoA4", 62), Video("VideoA5", 31), Video("VideoA6", 39))
def videoRatingOrderer(t: Video) = t.rate
def topTen() = {
val pq = collection.mutable.PriorityQueue()(Ordering.by(videoRatingOrderer))
pq.enqueue(sample: _*)
println(pq.take(10))
}
println(topTen())
public class CheckBitPermutationInString {
public static void main(String[] args) {
System.out.println(isValid("11001", 2));
}
public static boolean isValid(String s, int k) {
List<String> l = getAllBinarySubsets(k);
for (String binary : l) {
if (s.indexOf(binary) == -1) {
return false;
}
}
return true;
}
public static List<String> getAllBinarySubsets(int k) {
List<String> list = new ArrayList<>();
String format = "%0" + k + "d";
for(int i = 0; i < Math.pow(2, k); i++) {
list.add(String.format(format, Integer.valueOf(Integer.toBinaryString(i))));
}
return list;
}
}
Under the hoods it's actually the parens match problem:
public class IsValidExpression {
public static void main(String[] args) {
System.out.println(isValid("aabbab"));
System.out.println(isValid("abbaab"));
}
public static boolean isValid(String expression) {
if (expression == null || expression.equals("")) {
return false;
}
Stack<Character> opStack = new Stack<>();
char[] c = expression.toCharArray();
for (int i = 0; i < c.length; i++) {
if (c[i] == 'a') {
opStack.push(c[i]);
} else if (c[i] == 'b') {
if (opStack.isEmpty() || opStack.peek() != 'a') {
return false;
}
opStack.pop();
}
}
if (!opStack.isEmpty()) {
return false;
}
return true;
}
}
public static boolean isMatch(String str, String pattern) {
int n = str.length();
int m = pattern.length();
if (m == 0 && n == 0) return true;
boolean[][] t = new boolean[n + 1][m + 1];
for(int i = 0; i < n + 1; i++)
Arrays.fill(t[i], false);
t[0][0] = true;
for (int j = 1; j <= m; j++) {
if (pattern.charAt(j - 1) == '*' || (pattern.charAt(j - 1) == '+')) {
t[0][j] = t[0][j - 1];
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (pattern.charAt(j - 1) == '*') {
t[i][j] = t[i][j - 1] || t[i - 1][j];
}
else if (pattern.charAt(j - 1) == '+') {
t[i][j] = t[i][j - 1] || t[i - 1][j - 1];
}
else if (str.charAt(i - 1) == pattern.charAt(j - 1)) {
t[i][j] = t[i - 1][j - 1];
}
else {
t[i][j] = false;
}
}
}
return t[n][m];
}
Scala solution:
object FindAirportRoutes {
def main(args: Array[String]): Unit = {
val a = Seq(("ITO", "KOA"), ("ANC", "SEA"), ("LGA", "CDG"), ("KOA", "LGA"), ("PDX", "ITO"), ("SEA", "PDX"))
printOrderedRoute(a)
}
def printOrderedRoute(a : Seq[(String,String)]) : Unit = {
val sources = a.groupBy(_._1).map { case (k,v) => (k,v.length)}
val destinations = a.groupBy(_._2).map { case (k,v) => (k,v.length)}
val origin = sources.filter(p => destinations.getOrElse(p._1, 0) < p._2)
def dfs(source :String, tickets: Seq[(String,String)], path: Seq[(String,String)]): Unit = {
if (tickets.isEmpty) {
println(path)
} else {
tickets.filter(_._1.equals(source)).foreach { t =>
dfs(t._2, tickets.filterNot(x => t._1 == x._1 && t._2 == x._2), path :+ t)
}
}
}
// try all possible origin tickets
origin.foreach(or => dfs(or._1, a, Seq.empty[(String, String)]))
}
}
// prints: ((ANC,SEA), (SEA,PDX), (PDX,ITO), (ITO,KOA), (KOA,LGA), (LGA,CDG))
Calculate the Longest path of each node to all other nodes and pick the max among all.
1. Calculate longest path for a single node to all other nodes: O(n) for DAGs using Topological Sort.
2. Calculate for each node its longest path to all others in graph: O(N)^2
3. start a variable max = 0; loop through all the results and pick the max found.
Time: O(n^2)
If it's a connected and directed graph a possible solution could be:
1. Find all distances between each node of the graph, Djikstra applied for each node or else Floyd-Warshall algorithm could be used.
2. iterate over each node of graph and calculate average distance by summing all distances of node from all others and dividing it by N (size of graph).
3. Keep track of the min in the 2nd step and return min.
A sample implementation in Java using Floyd-warshall (Djikstra would be eventually better for performance for the sake of simplicity I'm using floyd-warshall in this example since the code is simpler):
class AllPairShortestPath
{
final static int INF = 99999, V = 4;
void minAverageDist(int graph[][])
{
int dist[][] = new int[V][V];
float averageDist[] = new float[V];
int i, j, k;
// step 1 - Floyd warshall - find all shortest distances between nodes
for (i = 0; i < V; i++)
for (j = 0; j < V; j++)
dist[i][j] = graph[i][j];
for (k = 0; k < V; k++)
{
// Pick all vertices as source one by one
for (i = 0; i < V; i++)
{
// Pick all vertices as destination for the
// above picked source
for (j = 0; j < V; j++)
{
// If vertex k is on the shortest path from
// i to j, then update the value of dist[i][j]
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
// 2. once all distances are calculated for each node calculate average distance
float min = INF;
int minNode = 0;
for (i = 0; i < V; i++) {
int sum = 0;
for (j = 0; j < V; j++) {
sum += dist[i][j];
}
averageDist[i] = (float)sum / V;
if (min > averageDist[i]) {
min = averageDist[i];
minNode = i;
}
}
System.out.print("MIN dist average = " + min + " NODE = " + minNode);
}
public static void main (String[] args)
{
/* Let us create the following weighted graph
10
(0)------->(3)
| /|\
5 | |
| | 1
\|/ |
(1)------->(2)
3 */
int graph[][] = { {0, 5, INF, 10},
{INF, 0, 3, INF},
{INF, INF, 0, 1},
{INF, INF, INF, 0}
};
AllPairShortestPath a = new AllPairShortestPath();
a.minAverageDist(graph);
}
}
1. Use a Map<Int, Int> for keeping scores of each player by ID, Points.
2. after every game build a rank by transforming the list to a sequence and sorting it according to points.In Scala this could be done in a functional way like this:
// players is a Map[Int, Int]
val rankings = players.toSeq.sortBy(_._2):_*
Solution in Scala using transpose:
object InterleaveArrays {
def main(args: Array[String]): Unit = {
val list1 = List(1,2,3)
val list2 = List(9,0)
val list3 = List(5)
val list4 = List(-4, -5, -2, -3, -1)
println(getInterleaved(list1, list2, list3, list4))
}
def transpose[A](xs: List[List[A]]): List[List[A]] = xs.filter(_.nonEmpty) match {
case Nil => Nil
case ys: List[List[A]] => ys.map{ _.head }::transpose(ys.map{ _.tail })
}
def getInterleaved(lists : List[Int]*) : List[Int] = {
transpose(lists.toList).flatten
}
}
// prints List(1, 9, 5, -4, 2, 0, -5, 3, -2, -3, -1)
- guilhebl April 18, 2018solution in Scala:
object SumSubsequence {
def main(args: Array[String]): Unit = {
val subArray = Array(1,2,3)
val interval = (3,6)
println(getCountSumSubarray(subArray, interval))
}
def getCountSumSubarray(subArray : Array[Int], interval : (Int,Int)) : Int = {
var count = 0 // to count num of subsequenecs within range
var sum = 0
val n = subArray.length
for (i <- 0 until n) {
for (j <- i until n) {
for (k <- i to j) {
sum += subArray(k)
print(subArray(k))
}
println(" - sum = " + sum)
if (sum >= interval._1 && sum <= interval._2) {
count += 1
}
sum = 0
}
}
count
}
}
Let's suppose at noon we run the algorithm, we first calculate the distance from each googler to one another:
int maxDist = range; // max limit for lunch together
distance[n][n] // store all distances - init with Int.MAX_VAL
persons // array of Persons object Person {id , coords}
for (Person p : persons ) {
for (Person j : persons ) {
if (p.id != j.id && distance[p.id][j.id] != int.MAX_VALUE) {
distance[p.id][j.id] = calculateDistance(p.coords, j.coords) // apply formula based on coordinates
if (distance[p.id][j.id] >= maxDist) return false // no lunch possible
}
}
}
return true;
}
Let's call the period P and the threshold T
1. Let's suppose we have an event listener that listens for incoming events and we have a function to handle the call, we can use a queue or either just a plain int for counting the number of events within a timewindow P:
int numEvents = 0;
function eventHandler {
numEvents ++;
if (numEvents >= T) {
return true
}
return false
}
2. After that we build a scheduler that will run every P units of time (milliseconds, seconds etc...) the scheduler will run a task that resets the counter to 0
class ResetTask extends TimerTask {
public void run() {
numEvents = 0;
}
}
Timer timer = new Timer();
timer.schedule(new ResetTask(), 0, T); // make sure to conver to proper unit : milis, seconds, etc...
This way you can know for any given timestamp X if the threshold has been surpassed
- guilhebl April 18, 2018Use mergesort with Java ForkJoin. This way each thread will receive a slice of each array and sort it, after the subsequent sorts and merges the final array will be sorted.
Here's a sample code I found on the internet:
Mergesort
import java.lang.reflect.Array;
public class MergeSort {
public static <T extends Comparable<? super T>> void sort(T[] a) {
@SuppressWarnings("unchecked")
T[] helper = (T[])Array.newInstance(a[0].getClass() , a.length);
mergesort(a, helper, 0, a.length-1);
}
private static <T extends Comparable<? super T>> void mergesort(T[] a, T[] helper, int lo, int hi){
if (lo>=hi) return;
int mid = lo + (hi-lo)/2;
mergesort(a, helper, lo, mid);
mergesort(a, helper, mid+1, hi);
merge(a, helper, lo, mid, hi);
}
private static <T extends Comparable<? super T>> void merge(T[] a, T[] helper, int lo, int mid, int hi){
for (int i=lo;i<=hi;i++){
helper[i]=a[i];
}
int i=lo,j=mid+1;
for(int k=lo;k<=hi;k++){
if (i>mid){
a[k]=helper[j++];
}else if (j>hi){
a[k]=helper[i++];
}else if(isLess(helper[i], helper[j])){
a[k]=helper[i++];
}else{
a[k]=helper[j++];
}
}
}
private static <T extends Comparable<? super T>> boolean isLess(T a, T b) {
return a.compareTo(b) < 0;
}
}
The Task:
private static class MergeSortTask<T extends Comparable<? super T>> extends RecursiveAction{
private static final long serialVersionUID = -749935388568367268L;
private final T[] a;
private final T[] helper;
private final int lo;
private final int hi;
public MergeSortTask(T[] a, T[] helper, int lo, int hi){
this.a = a;
this.helper = helper;
this.lo = lo;
this.hi = hi;
}
@Override
protected void compute() {
if (lo>=hi) return;
int mid = lo + (hi-lo)/2;
MergeSortTask<T> left = new MergeSortTask<>(a, helper, lo, mid);
MergeSortTask<T> right = new MergeSortTask<>(a, helper, mid+1, hi);
invokeAll(left, right);
merge(this.a, this.helper, this.lo, mid, this.hi);
}
private void merge(T[] a, T[] helper, int lo, int mid, int hi){
for (int i=lo;i<=hi;i++){
helper[i]=a[i];
}
int i=lo,j=mid+1;
for(int k=lo;k<=hi;k++){
if (i>mid){
a[k]=helper[j++];
}else if (j>hi){
a[k]=helper[i++];
}else if(isLess(helper[i], helper[j])){
a[k]=helper[i++];
}else{
a[k]=helper[j++];
}
}
}
private boolean isLess(T a, T b) {
return a.compareTo(b) < 0;
}
}
And finally a wrapper method that will do all the job behind the scenes:
public static <T extends Comparable<? super T>> void sort(T[] a) {
@SuppressWarnings("unchecked")
T[] helper = (T[])Array.newInstance(a[0].getClass() , a.length);
ForkJoinPool forkJoinPool = new ForkJoinPool(10);
forkJoinPool.invoke(new MergeSortTask<T>(a, helper, 0, a.length-1));
}
The solution for the problem is to find the min Window from indexes i to j in text such that all target keywords are present and distance from i to j is minimal.
One approach is to start a sliding window mechanism with the help of a Queue and for every keyword found check if head of queue (first inserted keyword in window) is equal to new found keyword, if so remove the keyword from head and place it in the tail of queue. This way will allow the algorithm to test for all windows of matches found for every keyword, and in the end returning the min. Window size.
Implementation of the above algorithm in Scala:
object MinKWindowSum {
def main(args: Array[String]): Unit = {
val document = "This Hello is a huge text with thousands of Hello words and other lines and World and many other Hello docs Words of World in many langs and features"
println(getMinWindowSize(document, "Hello World"))
}
def getMinWindowSize(doc:String, s:String): Int = {
val keywords = s.split(" ").toSet
val idxs = keywords.map(k => (k -> ("(?i)\\Q" + k + "\\E").r.findAllMatchIn(doc).map(_.start)))
.map{ case (keyword,itr) => itr.foldLeft(List[(String,Int)]())((result, num) => result :+ (keyword, num))}
.foldLeft(List[(String,Int)]())((res, list) => res ++ list)
.sortBy(_._2)
var min = Int.MaxValue
var minI = 0
var minJ = 0
var currWindow = ListBuffer[(String,Int)]()
for( tuple <- idxs ) {
if (!currWindow.isEmpty && currWindow.head._1.equals(tuple._1)) currWindow.remove(0)
currWindow += tuple
if (keywords.subsetOf(currWindow.map(_._1).toSet)) {
val currMin = currWindow.last._2 - currWindow.head._2 + currWindow.last._1.length
if (min > currMin) {
min = currMin
minI = currWindow.head._2
minJ = currWindow.last._2
}
}
}
println("min = " + min + " ,i = " + minI + " j = " + minJ )
min
}
}
/*
input:
This Hello is a huge text with thousands of Hello words and other lines and World and many other Hello docs Words of World in many langs and features
output:
min = 25 ,i = 97 j = 117
*/
Does it need to be a contiguous subarray say (1,2,3,4,5,6,1,2,3) k = 3 = (4,5,6) or
can it be a non-contiguous subarray? say (8,2,3,4,8,6,1,2,8) k = 3 = (8,8,8)
One possible implementation:
if K = N (size of array) return sum of array
else:
if contiguous: (easy case)
Build a subarray of size K starting from (0 ... k)
use 2 vars i and j i = 0, j = k
iterate from i ... n - k
check each element and current sum (removing previous element and adding new one)
return maxSUM
else (if non-contiguous):
use a Min Heap (PriorityQueue) of size K (insert first K elements into it)
iterate from 0 ... N-1
for each a[i] element compare if a[i] > queue.peek() // min element of queue
if greater then: queue.poll // remove min element and queue.add(a[i])
at the end return poll all remaining elements of queue ( Max K elements found )
algorithm idea: keep a sliding window from left to right,
use a Queue to insert words found in document as they appear in order from index 0 to (doc.length - 1) for each new keyword found apply the rule: first element in Queue must appear only once. If new element is equal to first element remove first element and append it to the end of Queue. Once all elements are present in Queue keep track of min window size found so far. This way the algorithm will test all sequences of keywords found in document.
1. split keywords by " " empty space
2. find all matches of keywords in document map them with their indexes in the form (keyword, index). combine All elements into a single list
3. sort resulting list by index position
4. from the resulting list iterate from left to right using the algorithm approach above
Implementation of the idea using Scala:
object MinKWindowSum {
def main(args: Array[String]): Unit = {
val document = "MS(1) Awesome x y Is MS(5) x y MS(8) x Is Awesome x y z Awesome"
println(getMinWindowSize(document, "MS is awesome"))
}
def getMinWindowSize(doc:String, s:String): Int = {
val keywords = s.split(" ").toSet
val idxs = keywords.map(k => (k -> ("(?i)\\Q" + k + "\\E").r.findAllMatchIn(doc).map(_.start)))
.map{ case (keyword,itr) => itr.foldLeft(List[(String,Int)]())((result, num) => result :+ (keyword, num))}
.foldLeft(List[(String,Int)]())((res, list) => res ++ list)
.sortBy(_._2)
var min = Int.MaxValue
var minI = 0
var minJ = 0
var currWindow = ListBuffer[(String,Int)]()
for( tuple <- idxs ) {
if (!currWindow.isEmpty && currWindow.head._1.equals(tuple._1)) currWindow.remove(0)
currWindow += tuple
if (keywords.subsetOf(currWindow.map(_._1).toSet)) {
val currMin = currWindow.last._2 - currWindow.head._2
if (min > currMin) {
min = currMin
minI = currWindow.head._2
minJ = currWindow.last._2
}
}
}
println("min = " + min + " ,i = " + minI + " j = " + minJ )
min
}
}
/*
input: "MS(1) Awesome x y Is MS(5) x y MS(8) x Is Awesome x y z Awesome"
output: min = 15 ,i = 6 j = 21
*/
public class LotteryTickets {
public static void main(String[] args) {
for (int i = 0; i < args.length; i++) {
isValidLotteryTicket(args[i].toCharArray());
}
}
private static boolean isValidLotteryTicket(char[] s) {
// string must be between 7 (only single elements) and 14 (all double digit elements)
if (s.length == 0 || s.length < 7 || s.length > 14 || s[0] == '0') {
return false;
}
// transform input string into an array of integers - check for any invalid inputs such as negatives or non-numbers
int[] nums = new int[s.length];
try {
for (int i = 0; i < s.length; i++) {
nums[i] = Integer.parseInt(Character.valueOf(s[i]).toString());
if (nums[i] < 0) return false;
}
} catch (NumberFormatException nfe) {
return false;
}
int doubleDigitNums = nums.length - 7;
int singleDigitNums = 7 - doubleDigitNums;
return isValidLotteryTicket(nums, new ArrayList<>(), 0, singleDigitNums, doubleDigitNums);
}
private static boolean isValidLotteryTicket(int[] nums, List<Integer> numsUsed, int i, int singleDigitNums, int doubleDigitNums) {
if (i > nums.length || numsUsed.size() > 7) {
return false;
}
else if (i == nums.length) {
if (numsUsed.size() == 7) {
// stop condition check if all elements were used and lottery ticket has 7 elements.)
for (Integer n : numsUsed) {
System.out.print(n + " ");
}
System.out.println();
}
return true;
}
int num = nums[i];
if (num > 5) { // number can only be used as a single digit in ticket, such elements are 6,7,8,9
if (singleDigitNums <= 0 || numsUsed.contains(num)) {
return false;
}
numsUsed.add(num);
return isValidLotteryTicket(nums, new ArrayList<>(numsUsed), i + 1, singleDigitNums-1, doubleDigitNums);
} else {
// number can be used as a single digit or as a pair for a double digit number 10-59 try both possibilities
boolean valid = false;
boolean added = false;
// try it as single digit
if (singleDigitNums > 0 && !numsUsed.contains(num)) {
numsUsed.add(num);
added = true;
valid = isValidLotteryTicket(nums, new ArrayList<>(numsUsed), i + 1, singleDigitNums-1, doubleDigitNums);
}
// try it as double digit
if (!valid && i + 1 < nums.length && doubleDigitNums > 0) {
if (added) numsUsed.remove(numsUsed.size() - 1);
int doubleDigitNum = new Integer(num + "" + nums[i + 1]);
if (!numsUsed.contains(doubleDigitNum)) {
numsUsed.add(doubleDigitNum);
valid = isValidLotteryTicket(nums, new ArrayList<>(numsUsed), i + 2, singleDigitNums, doubleDigitNums-1);
}
}
return valid;
}
}
}
for every number from 1 to N count number of digits = K
implementation in Scala:
object NumKCount {
def main(args: Array[String]): Unit = {
println(countK(30,3))
}
def countKDigit(n:Int, k:Int):Int = {
var num = n
var count = 0
while (num > 10) {
val digit = num % 10
if (digit == k) {count += 1}
num = num / 10
}
if (num == k) {count += 1}
count
}
def countK(n:Int, k:Int):Int = {
1.to(n).foldLeft(0)((acc, x) => acc + countKDigit(x, k))
}
}
In Scala:
object CheckNumber {
def main(args: Array[String]): Unit = {
println(checkNum(25,2))
}
def checkNum(x:Int, y:Int):Int = {
var count = 0
def countFreq(n:Int) = {
var num = n
while (num > 0) {
if (num % 10 == y) count += 1
num = num / 10
}
}
1.to(x).foreach(n => countFreq(n))
count
}
}
In Scala using a functional approach:
object FindFamous {
def main(args: Array[String]): Unit = {
val a = Array(
("Joe", "John", true),
("Suzy", "John", true),
("Jay", "John", true),
("Jack", "John", true),
("Jay", "Jack", false),
("Joe", "Suzy", true),
("Jay", "Suzy", false),
("Jack", "Suzy", true),
("John", "Suzy", false)
)
println(getFamous(a))
}
def getFamous(arr:Array[(String,String,Boolean)]) : String = {
val a = arr.filter(_._3 == true)
val copy = a.clone()
val result = a.filter {
case (p1,p2,r) => !copy.exists(_._1.equals(p2))
}
if (result.size > 0) {
return result(0)._2
}
return ""
}
}
Use a LinkedList and a HashMap<Id, ListNode<T>>
LinkedList - preserve the order of first seen objects
HashMap - keep track of those already seen and keep a reference for the ListNode of all first time seen elements
for every element of stream:
1. if first time seen (element ID is not in Map): insert it on end of LinkedList also insert ListNode reference in Map
2. else if already seen (element exists in Map): get ListNode reference from Map and use it to find Prev and Next nodes of the Object's ListNode, make LIstNode.Prev->Next = Next (eliminate this node from linked list). Set Map Value to Null, so in Map it would be <Key = Obj.ID, Value = NULL> this way we can keep track of those already seen.
At the end of the stream, select HEAD element from LinkedList, if empty return Null.
In Scala
object DiamondOddNumber {
def main(args: Array[String]): Unit = {
printDiamondPattern(7)
}
def printDiamondPattern(num:Int) = {
def f(n:Int) = {
val whitespace = (num - n) / 2
1.to(whitespace).foreach(elem => print(' '))
1.to(n).foreach(elem =>
if (elem % 2 == 1) print('o')
else print('*')
)
1.to(whitespace).foreach(elem => print(' '))
println
}
1.to(num).filter(n => n % 2 != 0).foreach(n => f(n))
(num-1).to(1).by(-1).filter(n => n % 2 != 0).foreach(n => f(n))
}
}
Concise version in Scala:
object MaxWindowKSum {
def main(args: Array[String]): Unit = {
val a = Array(10, 12, 15, 18, 20, 4, 5, 9, 28)
println(getMaxWindowKSum(a, 3))
}
def getMaxWindowKSum(a:Array[Int], k:Int) : Int = {
var max = 0
var i = 0
while (i + k < a.length) {
val sum = a.slice(i , i + k).sum
if (max < sum) max = sum
i += 1
}
return max
}
}
in scala:
object WordsBinarySearch {
def main(args: Array[String]): Unit = {
val a = Array("pto", "ret", "supp", "und", "xen", "asyn", "bah", "bano", "ccc", "ddd")
println(getIndexRotationPoint(a))
}
def getIndexRotationPoint(a:Array[String]) : Int = {
var i = 0
var j = a.length-1
while (i < j) {
val m = a.length / 2
if (m >= 1 && a(m).compareTo(a(m-1)) < 0) {
return m
} else if (m < a.length+1 && a(m).compareTo(a(m+1)) > 0) {
return m+1
}
if (a(i).compareTo(a(m)) < 0) {
i = m + 1
} else {
j = m - 1
}
}
return i
}
}
in Scala:
object MaxProfitSingleBuy {
def main(args: Array[String]): Unit = {
val a = Array(100, 120, 150, 180, 200, 40, 56, 90, 280)
println(getMaxProfitSingleBuy(a))
}
def getMaxProfitSingleBuy(a:Array[Int]) : Int = {
var i = 0
var j = 0
var max = -1
var maxI = -1
var maxJ = -1
while (i < a.length - 1) {
while (i < a.length-1 && a(i) > a(i + 1)) i += 1
j = i + 1
while (j < a.length-1 && a(j) < a(j + 1)) j += 1
// found local maxima
if (a(j) - a(i) > max) {
max = a(j) - a(i)
maxI = i
maxJ = j
}
i += 1
}
return max
}
}
Scala version using backtracking:
object StringToCharMapping {
val mappings = Map("AB" -> 'C', "BA" -> 'C', "AC" -> 'B', "CA" -> 'B', "BC" -> 'A', "CB" -> 'A')
def main(args: Array[String]): Unit = {
println(toSingleCharNumChanges("ABACB"))
println(toSingleCharNumChanges("ABACABB"))
}
def toSingleCharNumChanges(s:String) : Int = {
var str = new StringBuilder(s)
def f() : Int = {
if (str.size == 0) return -1
if (str.size == 1) return 0
if (str.sliding(2).map(a => a(0) == a(1)).count(identity) > 0) return -1
for (i <- 0 to str.size - 2) {
val c = str(i)
val n = str(i+1)
if (c != n) {
// backtracking
str(i) = mappings(c+""+n)
str.deleteCharAt(i+1)
val steps = f()
if (steps >= 0) return steps + 1
// place chars back to original spots
str(i) = c
str(i + 1) = n
}
}
return -1
}
f()
}
}
In Scala:
object Main {
val mapping = Map(1 -> "ABC", 2 -> "DEF")
def main(args: Array[String]): Unit = {
val a = mapping.keySet.toArray
var c = Array.ofDim[Char](a.length)
printCombos(a, 0, c)
}
def printCombos(a:Array[Int], i:Int, c:Array[Char]) : Unit = {
if (i == a.length) {
c foreach print
println
} else if (i < a.length) {
var j = 0
for (j <- 0 to mapping(a(i)).length() - 1) {
c(i) = mapping(a(i)).charAt(j)
printCombos(a, i + 1, c)
}
}
}
}
// output:
/*
AD
AE
AF
BD
BE
BF
CD
CE
CF
*/
My algorithm uses the following idea:
1. keep a HashMap of <Char, Int> as each char and its occurence in string.
2. Use a Deque to keep the current used window of K last inserted chars.
3. Build result picking the best available candidate as:
. has the max. number of count and was not recently inserted in the deque of K last chars.
. if none available pick an already existing element from deque starting from head and keep track of its cost of insertion to result.
Using a custom Tuple<Char, Int> class since Java 8 doesn't support Tuples out-of-the-box as to keep track of selected candidate <Char> and its cost to add to result <Int>.
Implementation in Java:
public class TaskCountString {
public static void main(String[] args) {
System.out.println(rearrangeTasks("AAABBBCCC", 3));
System.out.println(rearrangeTasks("AAABC", 2));
System.out.println(rearrangeTasks("AAADBBCC", 2));
}
public static int rearrangeTasks(String s, int k) {
List<Character> listC = new ArrayList<Character>();
for (char c : s.toCharArray()) {
listC.add(c);
}
// create a map of each char as key and its count num. of occurences in string
Map<Character, Long> mapCount = listC.stream()
.collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
int i = 0;
int numChars = s.length();
StringBuilder sb = new StringBuilder();
Deque<Character> deque = new LinkedList<>(); // use a deque to keep track of last used chars
int totalCost = 0;
while(i < numChars) {
Tuple<Character,Integer> t = getMaxCount(mapCount, deque, k);
sb.append(t.x);
totalCost += t.y;
deque.addLast(t.x);
long countOfChar = mapCount.get(t.x);
if (countOfChar == 1) {
mapCount.remove(t.x);
} else {
mapCount.put(t.x, countOfChar - 1);
}
if (deque.size() > k) {
deque.removeFirst();
}
i++;
}
System.out.println(sb);
return totalCost;
}
private static Tuple<Character,Integer> getMaxCount(Map<Character, Long> mapCount, Deque<Character> deque, int k) {
long max = 0;
Character maxChar = null;
Map<Character, Long> mapCopy = new HashMap<>(mapCount);
for(Character c : deque) {
mapCopy.remove(c);
}
if (!mapCopy.isEmpty()) {
for(Map.Entry<Character, Long> e : mapCopy.entrySet()) {
if (e.getValue() > max) {
max = e.getValue();
maxChar = e.getKey();
}
}
return new Tuple<>(maxChar, 1);
}
int cost = 2;
for(Character c : deque) {
if (mapCount.get(c) != null)
return new Tuple<>(c, cost);
cost++;
}
return null;
}
}
class Tuple<X, Y> {
public final X x;
public final Y y;
public Tuple(X x, Y y) {
this.x = x;
this.y = y;
}
}
1. f (string, strong) // happy path
2. f (null, null) // both null
3. f ("", "") // both empty strings
4. f (" ", " ") // both empty strings with spaces - blank strings
5. f ("abc", "zxy") // no matches
6. f ("!@#$", "1@#!@") // special chars
7. f (null, "somestring") // 1st param null other not
8. f ("somestring", null) // 2nd param null other not
9. Test with very large inputs
10. f ("azzzzzzzz", "zzzzzzza") // mathcing in different positions
In general terms these are some sample test cases to begin with, but
other tests that could be included as necessary.
RepI am randy, 29 year old and I am doing a job. I am doing a job as a plant ...
In Scala:
- guilhebl April 28, 2019