Mike L
BAN USERIt looks like that solution from the above is not right...
let's assume that n is length of a word and q is number of consequent numbers.
for n = 6 and q = 3 we should consider following cases ('_' is a place where could be rather 'A' or 'B'):
1. BBB___ --> 8 different cases. --> 8 unique cases. --> 2^(n - q)
2. _BBB__ --> 8 different cases, but 4 is similar to case 1. --> 4 unique cases. --> 2^(n - q - 1)
3. __BBB_ --> 8 different cases, but 4 is similar to case 2. --> 4 unique cases. --> 2^(n - q - 1)
4. ___BBB --> 8 different cases, but 4 is similar to case 3. --> 4 unique cases. --> 2^(n - q - 1)
amount of shifts with amount of unique cases that equals to 2^(n - q - 1) is (n - q)
and 20 unique cases in total.
so, it means that total number of cases is 2^(n - q) + (n - q)*2^(n - q - 1) == (n - q + 2)*2^(n - q - 1)
so implementation is the following:
/**
* Count number of strings of length N with following properties:
*
* A. Consists of char 'A' and 'B' only.
* B. There is at least one occurrence of 3 consecutive Bs.
*/
public class StringWithProperties {
private final long modulo = 1000000007L;
long getNumberOfStringsByModuloWithLength(int n, int q) {
if (n < q) {
return 0L;
}
long expectedNumber = n - q + 2;
if (n - q - 1 >= 0) {
for (int i = 0; i < n - q - 1; i++) {
expectedNumber <<= 1;
expectedNumber %= modulo;
}
} else {
expectedNumber >>= 1;
expectedNumber %= modulo;
}
return expectedNumber;
}
}
my two cents:
import java.util.HashMap;
import java.util.Map;
public class SecondMostRepeatingWord {
String secondMostRepeating(String sentence) {
Map<String, Integer> stat = new HashMap<>();
for (String w : sentence.split("\\s+")) {
stat.put(w, stat.getOrDefault(w, 0) + 1);
}
String firstMostRepeating = null;
int firstCounter = -1;
String secondMostRepeating = null;
int secondCounter = -1;
for (Map.Entry<String, Integer> s: stat.entrySet()) {
if (s.getValue() >= firstCounter) {
if (s.getValue() == firstCounter) {
continue;
}
secondMostRepeating = firstMostRepeating;
secondCounter = firstCounter;
firstMostRepeating = s.getKey();
firstCounter = s.getValue();
} else if (s.getValue() > secondCounter) {
secondMostRepeating = s.getKey();
secondCounter = s.getValue();
}
}
return secondMostRepeating;
}
}
Some explanations in the comment to implementation.
I didn't find similar solutions in the example from above, so, I've decided to add my own.
/**
* Find all the numbers the sum of cube of each digits is the number itself.
*
* @implNote the first thing that should be done is how to identify upper boundary for list of
* numbers.
*
* If length == 1 (0 <= n < 9), then the max value of the sum of cubes will be 9*9*9 = 729
*
* If length == 2 (10 <= n < 100), then the max value of the sum of cubes will be 9*9*9*2 = 1458
*
* If length == 3 (100 <= n < 1000), then the max value of the sum of cubes will be 9*9*9*3 = 2187
*
* If length == 4 (1000 <= n < 10000), then the max value of the sum of cubes will be 9*9*9*4 =
* 2916
*
* If length == 5 (10000 <= n < 100000), then the max value of the sum of cubes will be 9*9*9*5 =
* 3645
*
* It means that for numbers with length equals to 4 there is a probability that it could be a
* number with sum of cubes equals to that number, but for numbers with length that equals to 5,
* it is not the case, expected sum will be less than a number all the time. So, we can use 10000 as
* a upper boundary for the calculation.
*/
public class SumOfCubes {
public static void main(String[] args) {
StringBuilder output = new StringBuilder();
for (int i = 0; i < 10000; i++) {
if (getSumOfCubes(i) == i) {
output.append(i).append(System.lineSeparator());
}
}
System.out.println(output);
}
private static int getSumOfCubes(final int number) {
if (number == 0) {
return 0;
}
int lastDigit = number % 10;
return getSumOfCubes(number / 10) + lastDigit * lastDigit * lastDigit;
}
}
My couple of cents in Java:
public class LevelWithMinimumSumOfBT {
static class Level {
private int levelId;
private long sumOfItems;
public Level(int levelId, long sumOfItems) {
this.levelId = levelId;
this.sumOfItems = sumOfItems;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder("Level: {");
sb.append("id = ").append(levelId);
sb.append(", sum = ").append(sumOfItems);
sb.append('}');
return sb.toString();
}
}
static class BNode {
private int id;
private BNode left = null;
private BNode right = null;
public BNode(int id) {
this.id = id;
}
public void setLeft(BNode left) {
this.left = left;
}
public BNode getLeft() {
return left;
}
public boolean hasLeft() {
return left != null;
}
public void setRight(BNode right) {
this.right = right;
}
public BNode getRight() {
return right;
}
public boolean hasRight() {
return right != null;
}
}
static Level getLevelWithMinimumSum(Map<Integer, BNode> tree, int root) {
long curSum = 0L;
long lowerSum = Long.MAX_VALUE;
int curLevel = 0;
int lowerLevel = -1;
LinkedList<BNode> queue = new LinkedList<>();
queue.add(tree.get(root));
int curLevelLength = queue.size();
while (!queue.isEmpty()) {
BNode curElement = queue.pollFirst();
curSum += curElement.id;
// To add child nodes is possible
if (curElement.hasLeft()) {
queue.addLast(curElement.getLeft());
}
if (curElement.hasRight()) {
queue.addLast(curElement.getRight());
}
// To check is it end of the level or not
curLevelLength--;
if (curLevelLength == 0) {
curLevel++;
if (curSum < lowerSum) {
lowerSum = curSum;
lowerLevel = curLevel;
}
curSum = 0;
curLevelLength = queue.size();
}
}
return new Level(lowerLevel, lowerSum);
}
}
I did not include the main method in the snippet, but example of the launch is:
6
50
50 6 l
50 2 r
6 30 l
6 80 r
2 7 l
Level: {id = 2, sum = 8}
My solution in Java:
static String reverseAnyWords(String initialString) {
StringBuilder reversedString = new StringBuilder();
StringBuilder word = new StringBuilder();
for(int ii = 0; ii < initialString.length(); ii++) { // O(N)
if (!Character.isSpaceChar(initialString.charAt(ii))) { // O(1)
word.append(initialString.charAt(ii));
}
else {
if (word.length() != 0) {
reversedString.append(word.reverse());
word.delete(0, word.length());
}
reversedString.append(initialString.charAt(ii));
}
}
// Last piece
if (word.length() != 0) {
reversedString.append(word.reverse());
word.delete(0, word.length());
}
return reversedString.toString();
}
The DFS approach, but using queue instead of recursion
private static final char GROUND = 'x';
private static final char WATER = 'o';
private static final char VISITED = 'v';
public static void main(String[] args) {
try (Scanner scanner = new Scanner(System.in)) {
int T = scanner.nextInt();
for (int t = 0; t < T; t++) {
int n = scanner.nextInt();
int m = scanner.nextInt();
scanner.nextLine();
char[][] board = new char[n][m];
for (int j = 0; j < m; j++) {
int i = 0;
for (String s : scanner.nextLine().split(" ")) {
board[i++][j] = s.toLowerCase().charAt(0);
}
}
int x = scanner.nextInt();
int y = scanner.nextInt();
System.out.println(getNumberOfIsles(board, n, m, x, y));
}
}
}
private static int getNumberOfIsles(char[][] board, int n, int m, int x, int y) {
// update board
char[][] updatedBoard = deepCopyOfBoard(board);
updatedBoard[x][y] = GROUND;
// check number of isles
int numberOfIsles = 0;
int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (updatedBoard[i][j] == GROUND) {
LinkedList<int[]> island = new LinkedList<>();
island.add(new int[]{i, j});
while (!island.isEmpty()) {
int[] currentPoint = island.pollFirst();
updatedBoard[currentPoint[0]][currentPoint[1]] = VISITED;
for (int[] direction : directions) {
int newI = currentPoint[0] + direction[0];
int newJ = currentPoint[1] + direction[1];
if (0 <= newI && newI < n && 0 <= newJ && newJ < m && updatedBoard[newI][newJ] == GROUND) {
island.add(new int[]{newI, newJ});
}
}
}
numberOfIsles++;
} else if (updatedBoard[i][j] == WATER) {
updatedBoard[i][j] = VISITED;
}
}
}
return numberOfIsles;
}
private static char[][] deepCopyOfBoard(char[][] originalBoard) {
if (originalBoard == null) {
return null;
}
char[][] copiedBoard = new char[originalBoard.length][];
int i = 0;
for (char[] originalBoardLine : originalBoard) {
copiedBoard[i++] = Arrays.copyOf(originalBoardLine, originalBoardLine.length);
}
return copiedBoard;
}
Input:
3
3 3
o o o
o o o
o o o
1 2
3 3
o o o
o x x
o x o
0 0
7 6
x o o o x o o
o o x o x x o
o x o x o x o
x o x o o x o
x o o o x o o
x x x o o x o
2 2
Output:
1
2
6
Implementation in Java. (I've assumed that 'aba' and 'aba' are meta words, but 'abc' and 'abc' are not)
static boolean isMetaWords(String firstWord, String secondWord) {
if (firstWord.length() != secondWord.length()) {
return false;
}
int firstDiff = -1, secondDiff = -1;
Map<Character, Integer> wordStatistic = new HashMap<>();
for (int i = 0; i < firstWord.length(); i++) {
char symbol = firstWord.charAt(i);
wordStatistic.put(symbol, wordStatistic.getOrDefault(symbol, 0) + 1);
if (symbol != secondWord.charAt(i)) {
if (firstDiff == -1) {
firstDiff = i;
} else if (secondDiff == -1) {
secondDiff = i;
} else {
return false;
}
}
}
if (firstDiff == -1 && secondDiff == -1) {
// both strings are the same, just check that the string has repeatable symbols
for (int v : wordStatistic.values()) {
if (v > 1) {
return true;
}
}
return false;
}
if (secondDiff == -1) {
return false;
}
return firstWord.charAt(firstDiff) == secondWord.charAt(secondDiff)
&& firstWord.charAt(secondDiff) == secondWord.charAt(firstDiff);
}
Subset of tests is:
{"Converse", "Conserve", true},
{"test", "test", true},
{"false", "true", false},
{"test", "text", false},
{"change", "cgahne", false},
{"change", "cganhe", true},
{"abcd", "abcd", false},
{"abcda", "abcda", true},
Here is my implementation in Java:
public static void main(String[] args) {
try (Scanner scanner = new Scanner(System.in)) {
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] matrix = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = scanner.nextInt();
}
}
StringBuilder output = new StringBuilder();
for (int[] rowDetails : getRowsWithMaxOnes(matrix)) {
output.append('[').append(rowDetails[0]).append(", ").append(rowDetails[1]).append(']')
.append(System.lineSeparator());
}
System.out.print(output);
}
}
private static List<int[]> getRowsWithMaxOnes(int[][] matrix) {
List<int[]> results = new ArrayList<>();
int maxAmount = 0;
for (int i = 0; i < matrix.length; i++) {
int maxOfCurrentLine = 0;
if (maxAmount == 0) {
for (int j = matrix[i].length - 1; j >= 0; j--) {
if (matrix[i][j] == 1) {
maxAmount = matrix[i].length - j;
} else {
results.add(new int[]{i + 1, maxAmount});
break;
}
}
} else {
for (int j = matrix[i].length - maxAmount; j >= 0; j--) {
if (matrix[i][j] == 0) {
maxOfCurrentLine = matrix[i].length - j - 1;
break;
}
}
if (maxOfCurrentLine == maxAmount) {
results.add(new int[]{i + 1, maxAmount});
} else if (maxOfCurrentLine > maxAmount) {
results.clear();
maxAmount = maxOfCurrentLine;
results.add(new int[]{i + 1, maxAmount});
}
}
}
return results;
}
Samples of both input and output:
The first:
12 6
0 0 0 0 0 0 0 1 1 1 1 1
0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 1 1 1 1 1
0 0 0 0 1 1 1 1 1 1 1 1
[2, 8]
[6, 8]
The second:
3 3
0 0 0
0 0 0
0 0 0
[1, 0]
[2, 0]
[3, 0]
The third:
3 3
0 0 0
0 0 1
0 1 1
[3, 2]
Implementation in Java:
public static void main(String[] args) {
try (Scanner scanner = new Scanner(System.in)) {
int n = scanner.nextInt();
scanner.nextLine();
AdvancedStack<Integer> stack = new AdvancedStack<>();
StringBuilder output = new StringBuilder();
for (int i = 0; i < n; i++) {
String[] command = scanner.nextLine().split(" ");
switch (command[0]) {
case "push": {
stack.push(Integer.valueOf(command[1]));
break;
}
case "pop": {
stack.pop();
break;
}
case "min": {
Integer min = stack.getMin();
output.append(min != null ? min : "null").append(System.lineSeparator());
break;
}
}
}
System.out.print(output);
}
}
}
class AdvancedStack<T extends Comparable<T>> {
LinkedList<T> originalElements = new LinkedList<T>();
LinkedList<T> onlyMinElements = new LinkedList<T>();
public void push(T element) {
originalElements.push(element);
if (!onlyMinElements.isEmpty()) {
if (onlyMinElements.getFirst().compareTo(element) >= 0) {
onlyMinElements.push(element);
}
} else {
onlyMinElements.push(element);
}
}
public T pop() {
if (originalElements.isEmpty()) {
return null;
}
if (onlyMinElements.getFirst().compareTo(originalElements.getFirst()) == 0) {
onlyMinElements.pop();
}
return originalElements.pop();
}
public T getMin() {
if (onlyMinElements.isEmpty()) {
return null;
}
return onlyMinElements.getFirst();
}
Sample Input:
31
push 1
push 2
push 3
min
pop
min
pop
push 1
push 1
min
pop
min
pop
min
pop
min
push 6
push 5
push 4
push 4
push 5
push 6
min
pop
min
pop
min
pop
min
pop
min
Sample Output:
1
1
1
1
1
null
4
4
4
4
5
Implementation in Java8
/**
*
* @param d - number of consecutive days
* @param log - list of lines from the log file
* @param separator - separator between the date and id
* @return - set of loyal customers who logs in {@code d} consecutive days
*/
static Set<String> getLoyalCustomers(int d, String[] log, String separator) {
Set<String> loyalCustomers = new HashSet<>();
Map<String, LinkedList<String>> cache = new HashMap<>();
for (String line : log) {
String[] details = line.split(separator);
String day = details[0];
String id = details[1];
// to check if the customer is already a loyal one
if (loyalCustomers.contains(id)) {
continue;
}
// to check if the customer is in cache already
if (!cache.containsKey(id)) {
cache.put(id, new LinkedList<>());
cache.get(id).add(day);
} else {
// to check if the day and last logged day is the consecutive days.
if (isItTwoConsecutiveDays(cache.get(id).getLast(), day)) {
if (cache.get(id).size() == d - 1) {
loyalCustomers.add(id);
cache.remove(id);
} else {
cache.get(id).add(day);
}
} else {
cache.get(id).clear();
cache.get(id).add(day);
}
}
}
return loyalCustomers;
}
/**
*
* @param day1 - day in format MM/dd/yyyy
* @param day2 - day in format MM/dd/yyyy
* @return - true if day2 is follow by day1, otherwise false
*/
private static boolean isItTwoConsecutiveDays(String day1, String day2) {
DateTimeFormatter formatter = DateTimeFormatter.ofPattern("MM/dd/yyyy");
LocalDate dayOne = LocalDate.parse(day1, formatter);
LocalDate dayTwo = LocalDate.parse(day2, formatter);
return dayOne.plusDays(1).isEqual(dayTwo);
}
required imports
import java.time.LocalDate;
import java.time.format.DateTimeFormatter;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
Consider
public class LinkedListNode {
int data;
LinkedListNode next;
}
Reverse function should be like that:
public LinkedListNode reverse(LinkedListNode head) {
if (head == null) {
return head;
}
LinkedListNode previous = null;
LinkedListNode current = head;
while (current != null) {
LinkedListNode t = current.next;
current.next = previous;
previous = current;
current = t;
}
return previous;
}
static long[] calculatesProductsOfAllItemsExceptOne(int[] items) {
long[] products = new long[items.length];
long productOfNonZero = 1L;
int indexOfZero = -1;
for (int i = 0; i < items.length; i++) {
if (items[i] != 0) {
productOfNonZero *= items[i];
} else {
if (indexOfZero == -1) {
indexOfZero = i;
} else {
return products;
}
}
}
if (indexOfZero == -1) {
for (int i = 0; i < products.length; i++) {
products[i] = productOfNonZero/items[i];
}
} else {
products[indexOfZero] = productOfNonZero;
}
return products;
}
Consider a linked list that could have two types of elements:
1. element
2. another linked list
class LinkedListOfLinkedListsIterator<T1> implements Iterator<T1> {
Iterator<Object> parentIterator = listOfLists.iterator();
Iterator<T1> childIterator;
@Override
public boolean hasNext() {
if (childIterator != null && childIterator.hasNext()) {
return true;
}
return parentIterator.hasNext();
}
@Override
public T1 next() {
if (childIterator != null) {
if (childIterator.hasNext()) {
return childIterator.next();
}
childIterator = null;
}
while (parentIterator.hasNext()) {
Object p = parentIterator.next();
if (p instanceof LinkedList) {
childIterator = ((LinkedList<T1>) p).iterator();
if (childIterator.hasNext()) {
return childIterator.next();
}
childIterator = null;
} else {
return (T1)p;
}
}
return null;
}
}
static String shortestSubstring(String input, char[] alphabet) {
Set<Character> usedChars = new HashSet<>();
boolean hasSubstringFound = false;
int start = 0, end = input.length();
for (int i = 0; i < input.length(); i++) {
for (; i < input.length() - 1 && input.charAt(i) == input.charAt(i + 1); i++) {
}
int j = i;
for (; usedChars.size() < alphabet.length && j < input.length(); j++) {
char current = input.charAt(j);
usedChars.add(current);
}
if (usedChars.size() == alphabet.length && end - start > j - i) {
hasSubstringFound = true;
start = i;
end = j;
}
usedChars.clear();
}
return hasSubstringFound ? input.substring(start, end) : null;
}
Original case:
static <T extends Comparable<T>> TreeNode<T> findParentForNodeInBT(TreeNode<T> root, T value) {
if (root == null) {
return null;
}
TreeNode<T> currentNode = root;
if (currentNode.val.compareTo(value) == 0) {
return null;
}
LinkedList<TreeNode<T>> queue = new LinkedList<>();
queue.add(currentNode);
while (!queue.isEmpty()) {
currentNode = queue.pollFirst();
// follow the right branch (if possible)
if (currentNode.right != null) {
if (currentNode.right.val.compareTo(value) == 0) {
return currentNode;
}
queue.add(currentNode.right);
}
// follow the left branch (if possible)
if (currentNode.left != null) {
if (currentNode.left.val.compareTo(value) == 0) {
return currentNode;
}
queue.add(currentNode.left);
}
}
return null;
}
If the binary tree is a binary search tree:
static <T extends Comparable<T>> TreeNode<T> findParentForNodeInBST(TreeNode<T> root, T value) {
if (root == null) {
return null;
}
TreeNode<T> currentNode = root;
if (currentNode.val.compareTo(value) == 0) {
return null;
}
while (true) {
// follow the right branch (if possible)
if (currentNode.val.compareTo(value) < 0 && currentNode.right != null) {
if (currentNode.right.val.compareTo(value) == 0) {
return currentNode;
}
currentNode = currentNode.right;
continue;
}
// follow the left branch (if possible)
if (currentNode.val.compareTo(value) > 0 && currentNode.left != null) {
if (currentNode.left.val.compareTo(value) == 0) {
return currentNode;
}
currentNode = currentNode.left;
continue;
}
break;
}
return null;
}
That's a bit tricky question.
There several way how we can implement the UnionFind approach.
First of all we should not consider equation like a character, approach should be more general.
Moreover, It is really depends on how much items in first sequence we will have and how mush items in the second one. Depends of that you can modify your algorithm.
In general, one of operations can cost you O(n) and another one O(1).
Approach where amount of distinct numbers is border by a fixed number works well for this challenge. If we have no such limit, this challenge should be solved via heaps.
So, my implementation in Java below:
The idea is similar to ChrisK, we store everything in array: index -> age; value -> amount of people of that age.
My function receive array with all ages as a parameter, build an array, based on description above and calculate the median.
static double getMedianAge(int[] peopleAges) {
int[] ages = new int[MAX_AGE];
if (peopleAges.length == 1) {
return peopleAges[0];
}
if (peopleAges.length == 2) {
return (peopleAges[0] + peopleAges[1]) / 2.0;
}
for (int p : peopleAges) {
ages[p]++;
}
boolean isAmountOfPeopleAnOddNumber = peopleAges.length % 2 == 1;
int half = peopleAges.length >> 1;
int left;
int right = -1;
double median = 0.0;
for (int i = 0; i < MAX_AGE; i++) {
if (ages[i] != 0) {
left = right + 1;
right = left + ages[i] - 1;
if (isAmountOfPeopleAnOddNumber && left <= half && half <= right) {
median = i;
break;
}
if (!isAmountOfPeopleAnOddNumber && left <= half - 1 && half - 1 <= right) {
median += i;
if (left <= half && half <= right) {
median += i;
} else {
// find next number
while (ages[++i] == 0) {
}
median += i;
}
median /= 2;
break;
}
}
}
return median;
}
My version of solution is:
static double fastExponent(double value, int power) {
// For all cases any number at power 0 is 1
if (power == 0) {
return 1;
}
// Any number at power 1 is the same number
if (power == 1) {
return value;
}
// If value equals to 0, than at any power (except 0, but this case has been checked above) is 0
if (value == 0) {
return 0;
}
// Negative power is equals to 1/(value^power)
if (power < 0) {
return 1 / fastExponent(value, -power);
}
// Check if power is even number
if ((power >> 1) << 1 == power) {
double preCalculatedValue = fastExponent(value, power >> 1);
return preCalculatedValue * preCalculatedValue;
}
return value * fastExponent(value, power - 1);
}
List of tests in format {<value>, <power>, <expected result>
{1000, 0, 1},
{3, 1, 3},
{0, 0, 1},
{0, 1000, 0},
{-2, 3, -8},
{-2, 4, 16},
{-2, -4, 0.0625},
{-2, -3, -0.125},
{1.01, 1000, 20959.155637813660064},
{2, 10, 1024.0},
{10, 13, 10000000000000.0}
Complexity is about ~O(2*log(n))
Since in worst case we will have following sequence of powers:
odd -> even -> odd -> even and so on.
Ex: if power = 15 the function will be called with following value as a power:
15 -> 14 -> 7 -> 6 -> 3 -> 2 -> 1
So, amount of sequences (odd -> even) is ~log(n) since every time we dividing by 2; Considering that number of operations in the pair is 2, result will be ~2*log(n) or just O(log(n)).
It is a very clever question.
From my point of view, it is not about the implementation itself, since it is pretty much easy to write such algorithm.
It is about design patterns, I faced similar challenge, and I thought: "Why those guys are asking me to solve such an easy challenge?" - after that I started thinking about how we can extend solution and so on - and it turned out that it is a question about how I can handle different design patterns.
So, regarding the challenge, from my point of view there are to cases here:
1. applying a tag -> Decorator pattern (How we can easily modify our solution to handle the '<i>' tag?)
2. list of substrings -> Strategy pattern (What will be in case if for different strings we would like to use different tags?)
And my solution is:
public class BoldTheSubstrings {
public static void main(String[] args) {
try (Scanner scanner = new Scanner(System.in)) {
String initialString = scanner.nextLine();
int amountOfSubstrings = scanner.nextInt();
HTMLTagStrategy strategy;
HTMLTag decorateWithBoldStyle = new SimpleHTMLTagImpl("b");
for (int i = 0; i < amountOfSubstrings; i++) {
strategy = new SimpleHTMLTagStrategyImpl(scanner.next());
initialString = strategy.applyTagToSubstring(decorateWithBoldStyle, initialString);
}
System.out.println(initialString);
}
}
}
/**
* Definition of the Decorator pattern
*/
// Interface
interface HTMLTag {
String applyTag(String string);
}
// Implementation
class SimpleHTMLTagImpl implements HTMLTag {
private String tagName;
public SimpleHTMLTagImpl(String tagName) {
this.tagName = tagName;
}
@Override
public String applyTag(String string) {
return "<" + tagName + ">" + string + "</" + tagName + ">";
}
}
/**
* Definition of the Strategy pattern
*/
// Interface
interface HTMLTagStrategy {
String applyTagToSubstring(HTMLTag decorator, String theString);
}
// Implementation
class SimpleHTMLTagStrategyImpl implements HTMLTagStrategy {
private String substring;
public SimpleHTMLTagStrategyImpl(String substring) {
this.substring = substring;
}
@Override
public String applyTagToSubstring(HTMLTag decorator, String theString) {
StringBuilder resultOutput = new StringBuilder();
String[] splitParts = theString.split(substring);
resultOutput.append(splitParts[0]);
for (int i = 1; i < splitParts.length; i++) {
resultOutput.append(decorator.applyTag(substring)).append(splitParts[i]);
}
return resultOutput.toString();
}
}
Input:
HelloWorld HelloWorld
2
el
rl
Output:
H<b>el</b>loWo<b>rl</b>d H<b>el</b>loWo<b>rl</b>d
Please correct me if I am wrong with such approach :)
- Mike L January 26, 2017I have the same approach with defining an additional structure, so, my solution in Java:
/**
* Overall complexity ~ O(n*log(n))
* @param a
* @return
*/
static int[] sortTheArray(int[] a) {
int[] b = new int[a.length];
// Pre-fill the map
Map<Integer, Node> statistic = new HashMap<>();
// complexity is ~ O(n)
for (int i = 0; i < a.length; i++) {
if (!statistic.containsKey(a[i])) {
statistic.put(a[i], new Node(a[i], i, 1));
} else {
statistic.get(a[i]).frequency += 1;
}
}
// Sort all values
// Complexity is ~ O(n)
List<Node> values = new ArrayList<>(statistic.values());
// Complexity is ~ O(n*log(n))
Collections.sort(values);
// Complexity is ~ O(n)
int position = 0;
for (Node v : values) {
for (int j = 0; j < v.frequency; j++, position++) {
b[position] = v.value;
}
}
return b;
}
private static class Node implements Comparable<Node> {
int value;
int firstOccurrence;
int frequency;
public Node(int v, int o, int f) {
value = v;
firstOccurrence = o;
frequency = f;
}
@Override
public int compareTo(Node o) {
if (frequency == o.frequency) {
return Integer.compare(firstOccurrence, o.firstOccurrence);
}
return -Integer.compare(frequency, o.frequency);
}
}
static int getMaxOfConsecutiveOnes(String s) {
int globalMax = 0;
int currentMax = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '1') {
currentMax++;
} else {
if (currentMax != 0) {
if (globalMax < currentMax) {
globalMax = currentMax;
}
currentMax = 0;
}
}
}
// check the end
if (globalMax < currentMax) {
globalMax = currentMax;
}
return globalMax;
}
Tests:
{"00110001001110", 3},
{"1000010001", 1},
{"00000", 0},
{"11111", 5}
My version of required function is:
/**
*
* @param a
* @return position of the first element with property that all elements in previous positions
* are less than this element - from the left side, and all elements in positions
* that greater or equal goes after the element - from the right side
*/
static int findMiddleElementPosition(int[] a) {
if (a == null) {
return -1;
}
int[] max = Arrays.copyOf(a, a.length);
for (int i = 1; i < a.length; i++) {
if (max[i] < max[i - 1]) {
max[i] = max[i - 1];
}
}
for (int j = a.length - 1; j >= 0; j--) {
if (a[j] < max[j]) {
// additional check if it is the latest element in the array
return j + (j != a.length - 1 ? 1 : 0);
}
}
return 0;
}
Samples in format array:position
{null, -1},
{new int[]{1}, 0},
{new int[]{1, 2}, 0},
{new int[]{1, 2, 3}, 0},
{new int[]{2, 1, 3}, 2},
{new int[]{-1, 2, -3, 4, 5, 6}, 3},
{new int[]{-1, 4, -3, 6, -2, 5, 8, 9}, 6},
{new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9}, 0},
{new int[]{-1, -2, -3, -4, -5, -6, -7, -8, -9}, 8},
{new int[]{-1, -1, -1, -1, 3, 3, 3, 3}, 0},
{new int[]{-1, 2, -1, 3, -1, 4, 4, 4, 4}, 5}
Agree with comments above, this task is about the 'merge' subroutine of Merge Sort.
My implementation in Java
static int[] mergeTwoSortedArrays(int[] a, int[] b) {
// Corner cases
if (a == null && b == null) {
return null;
}
if (a == null) {
return Arrays.copyOf(b, b.length);
}
if (b == null) {
return Arrays.copyOf(a, a.length);
}
// Common cycle
int[] c = new int[a.length + b.length];
int i = 0, j = 0, k = 0;
while (i < a.length && j < b.length) {
if (a[i] < b[j]) {
c[k] = a[i];
i++;
} else {
c[k] = b[j];
j++;
}
k++;
}
// ends
if (i == a.length) {
while (j < b.length) {
c[k++] = b[j++];
}
} else {
while (i < a.length) {
c[k++] = a[i++];
}
}
return c;
}
My solution is:
Complexity is about n*sqrt(n). Description in comments.
public class MinDiffBetweenPrimes {
public static void main(String[] args) {
try (Scanner in = new Scanner(System.in)) {
int T = in.nextInt();
for (int t = 0; t < T; t++) {
int n = in.nextInt();
int[] array = new int[n];
for (int i = 0; i < n; i++) {
array[i] = in.nextInt();
}
System.out.println(getMinDiffBetweenPrimes(array));
}
}
}
/**
* Complexity:
* 1. ~n*sqrt(n) to select all primes
* 2. ~n*log(n) to sort primes
* 3. ~n to find the difference
* So, maximum is n*sqrt(n)
* @return non-negative difference between primes, -1 in case if it is not possible to calculate
* the difference.
*/
private static int getMinDiffBetweenPrimes(int[] array) {
int minDiff = Integer.MAX_VALUE;
List<Integer> primesAtArray = new ArrayList<>();
for (int a : array) {
if (isPrime(a)) {
primesAtArray.add(a);
}
}
if (primesAtArray.size() < 1) {
return -1;
}
Collections.sort(primesAtArray);
int diff;
for (int i = 0; i < primesAtArray.size() - 1; i++) {
diff = primesAtArray.get(i + 1) - primesAtArray.get(i);
if (diff < minDiff) {
minDiff = diff;
}
}
return minDiff;
}
/**
* Complexity ~ sqrt(n)
* @param n
* @return is parameter a prime number or not
*/
static boolean isPrime(int n) {
if (n < 0) {
n = -n;
}
if (n == 1) {
return false;
}
if ((n >> 1) << 1 == n) {
return false;
}
double sqrtN = Math.sqrt(n);
for (int p = 3; p <= sqrtN; p += 2) {
if (n % p == 0) {
return false;
}
}
return true;
}
}
Sample Input:
6
10
1 2 3 4 5 6 7 8 9 10
16
10 8 3 4 16 32 44 15 127 45 14 19 16 12 100 101
10
-10 10 -8 8 -6 6 -7 7 -4 4
5
3 3 3 3 3
4
7 5 3 1
8
23 -3 0 15 38 47 46 45
Sample Output:
1
16
14
0
2
24
I considered a case when everything that inside quotes like "smth." or 'smth.' should be ignored.
So, my solution is:
private final static Map<Character, Character> symbolsPairs = new HashMap<>();
private final static Set<Character> brackets = new HashSet<>();
private final static Set<Character> quotes = new HashSet<>();
static {
// Brackets
brackets.add('<');
brackets.add('>');
brackets.add('{');
brackets.add('}');
brackets.add('[');
brackets.add(']');
brackets.add('(');
brackets.add(')');
// Quotes
quotes.add('\'');
quotes.add('\"');
// Pairs
symbolsPairs.put('(', ')');
symbolsPairs.put('<', '>');
symbolsPairs.put('{', '}');
symbolsPairs.put('[', ']');
}
public static void main(String[] args) {
try (Scanner in = new Scanner(System.in)) {
int T = in.nextInt();
StringBuilder output = new StringBuilder();
for (int t = 0; t < T; t++) {
boolean isBalanced = hasBalancedBracketsAndQuotes(in.next());
output.append(isBalanced ? "Yes" : "No").append(System.lineSeparator());
}
System.out.print(output);
}
}
static boolean hasBalancedBracketsAndQuotes(String s) {
LinkedList<Character> stack = new LinkedList<>();
boolean hasDoubleQuote = false;
boolean hasSingleQuote = false;
for (int i = 0; i < s.length(); i++) {
char b = s.charAt(i);
if (!brackets.contains(b) && !quotes.contains(b)) {
continue;
}
if (hasDoubleQuote && b == '\"') {
hasDoubleQuote = false;
continue;
}
if (hasSingleQuote && b == '\'') {
hasSingleQuote = false;
continue;
}
// to check brackets only we are not inside quotes
if (!hasDoubleQuote && !hasSingleQuote) {
if (symbolsPairs.containsKey(b)) {
stack.addLast(b);
} else if (quotes.contains(b)) {
if (b == '\"') {
hasDoubleQuote = true;
}
if (b == '\'') {
hasSingleQuote = true;
}
} else {
// to check that closed bracket is matched to open bracket
Character o = stack.pollLast();
if (o == null || !symbolsPairs.get(o).equals(b)) {
return false;
}
}
}
}
if (!stack.isEmpty() || hasDoubleQuote || hasSingleQuote) {
return false;
}
return true;
}
Tests are:
a{a{"a{{a"a}a}a - Yes
a{a{'a{{a'a}a}a - Yes
a{a{'a{{a"a}a}a - No
a{a{'a{{a"a}a}a - No
a{a{"a{{a}a"a}a - No
a{a{'a{{a}a'a}a - No
a{[a'a"a'a"a'a"a]a}a - Yes
a{[a'a'a'a"a'a"a]a}a - No
a{[a'a)a'a'a{a'a'a<a'a]a}a - Yes
a - Yes
a{a"a'a"a}a - Yes
a{a"a"a}a - Yes
a{{a'a}}'a}a} - Yes
<a{a(a[a"a}a]a>a)"a]a)a}a> - Yes
<a{a(a[a"a}a]a>a)"a>a}a)a] - No
a"a'a - No
a'a"a - No
Am I right that it should be something like that? I assumed that the pivot element is the first element of the array
public class QuicksortPartition {
public static void main(String[] args) {
try (Scanner scanner = new Scanner(System.in)) {
int N = scanner.nextInt();
int[] ar = new int[N];
for (int n = 0; n < N; n++) {
ar[n] = scanner.nextInt();
}
int p = ar[0];
int l = 0, r = 0;
for (int i = 0; i < ar.length; i++) {
if (ar[i] < p) {
int t = ar[i];
ar[i] = ar[r];
ar[r] = p;
ar[l] = t;
l++;
r++;
}
else if (ar[i] == p) {
int t = ar[i];
ar[i] = ar[r];
ar[r] = t;
r++;
}
}
StringBuilder stringBuilder = new StringBuilder();
for (int a: ar) {
stringBuilder.append(a).append(" ");
}
System.out.println(stringBuilder);
}
}
}
My version of solution:
public class FirstNonRepeatable {
public static void main(String[] args) {
try (Scanner scanner = new Scanner(System.in)) {
String s = scanner.nextLine();
System.out.println(firstNonRepeatable(s));
}
}
public static Character firstNonRepeatable(String s) {
if (s.length() == 0) {
return null;
}
Set<Character> nonRepeatable = new HashSet<>();
LinkedList<Character> distinct = new LinkedList<>();
Set<Character> repeatable = new HashSet<>();
nonRepeatable.add(s.charAt(0));
distinct.add(s.charAt(0));
char charToCheck;
for (int i = 1; i < s.length(); i++) {
charToCheck = s.charAt(i);
if (!repeatable.contains(charToCheck)) {
if (nonRepeatable.contains(charToCheck)) {
nonRepeatable.remove(charToCheck);
repeatable.add(charToCheck);
}
else {
nonRepeatable.add(charToCheck);
distinct.add(charToCheck);
}
}
}
if (nonRepeatable.isEmpty()) {
return null;
}
for (char c: distinct) {
if (nonRepeatable.contains(c)) {
return c;
}
}
return null;
}
}
Here is my version of solution on C#
private IEnumerable<Char> getSymbol(string word) {
foreach (char c in word) {
yield return c;
}
}
public IEnumerable<String> getPermutations(int index, string[] words) {
foreach (char c in getSymbol(words[index])) {
if (index < words.Length - 1) {
foreach(string s in getPermutations(index + 1, words)) {
yield return c + s;
}
}
else {
yield return c.ToString();
}
}
}
This is my version of solution:
public static string GenerateLowestNumber(string number, int n) {
StringBuilder lowest_number_str = new StringBuilder();
StringBuilder tmp_str = new StringBuilder ();
SortedSet<int> lowest_number_combination = new SortedSet<int> ();
int lowest_number = int.MaxValue;
foreach(SortedSet<int> combination in combination_to_test(0, number.Length, number.Length - n)) {
tmp_str.Clear ();
foreach (int element in combination) {
tmp_str.Append (number [element]);
}
if (lowest_number > int.Parse (tmp_str.ToString ())) {
lowest_number = int.Parse (tmp_str.ToString ());
lowest_number_str.Clear ();
lowest_number_str.Append (tmp_str.ToString ());
lowest_number_combination.Clear ();
lowest_number_combination.UnionWith (combination);
}
}
return lowest_number_str.ToString ();
}
private static IEnumerable<SortedSet<int>> combination_to_test(int start, int end, int requested_amount){
if (requested_amount == 1) {
for (int i = start; i < end; i++) {
yield return new SortedSet<int> (new int[]{ i });
}
} else {
for (int j = start; j + requested_amount <= end; j++) {
foreach (SortedSet<int> combination in combination_to_test(j + 1, end, requested_amount - 1)) {
SortedSet<int> combination_to_return = new SortedSet<int> (combination);
combination_to_return.UnionWith (new int[]{ j });
yield return combination_to_return;
}
}
}
}
What about regexp? (C#)
public class Question
{
private const string default_journal_file = "../../journal.txt";
private const string subject_for_acceptance_test = "Data Structures";
private List<StudentInfo> students;
public string journal_file { get; private set; }
public string subject { get; set; }
/**
* Struct with description of information about the student
*/
private struct StudentInfo {
public int StudentID;
public string Subject;
public int Mark;
public StudentInfo(int student_id, string subject, int mark) {
StudentID = student_id;
Subject = subject;
Mark = mark;
}
}
public Question (string subject_name)
{
subject = subject_name;
journal_file = default_journal_file;
students = new List<StudentInfo> ();
ReadJournal ();
}
public Question (string subject_name, string journal_file_path)
{
subject = subject_name;
journal_file = journal_file_path;
students = new List<StudentInfo> ();
ReadJournal ();
}
public int AverageMark() {
int sum_of_marks = 0;
int marks_count = 0;
foreach (StudentInfo student_info in students) {
if (student_info.Subject == subject) {
sum_of_marks += student_info.Mark;
marks_count++;
}
}
return sum_of_marks / marks_count;
}
private void ReadJournal() {
using (StreamReader sr = new StreamReader (journal_file)) {
Regex rgx = new Regex (@"^(\d+)\s(.+)\s(\d+)$");
while (!sr.EndOfStream) {
string current_line = sr.ReadLine ();
if (rgx.IsMatch(current_line.Trim())) {
Match m = rgx.Match (current_line.Trim());
students.Add (new StudentInfo (int.Parse (m.Groups [1].Value), m.Groups[2].Value.Trim(), int.Parse(m.Groups[3].Value)));
}
}
}
}
}
I didn't notice that someone is considering a negative sum as an input parameters, in that case an additional logic should be applied...
So, here is my solution:
and set of parameterised test cases:
- Mike L May 04, 2019