artak.a.petrosyan
BAN USERJava code:
Function return type is String for avoiding overflow
import java.util.Arrays;
import java.util.Comparator;
import org.apache.commons.lang3.ArrayUtils;
public class MaxConcatenatedInteger {
public static String getMaxConcatenatedNumber(int[] numbers) {
final Integer[] sN = ArrayUtils.toObject(numbers);
Arrays.sort(sN, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
char[] digitsO1 = o1.toString().toCharArray();
char[] digitsO2 = o2.toString().toCharArray();
int n = Math.max(digitsO1.length, digitsO2.length);
char digit1 = 0;
char digit2 = 0;
for (int i = 0; i < n; i++) {
if (i < digitsO1.length)
digit1 = digitsO1[i];
if (i < digitsO2.length)
digit2 = digitsO2[i];
if (digit1 < digit2)
return 1;
if (digit1 > digit2)
return -1;
}
return 0;
}
});
StringBuffer sb = new StringBuffer();
for (int i = 0; i < sN.length; i++) {
sb.append(sN[i]);
}
return sb.toString();
}
public static void main(String[] args) {
int[] numbers = { 9, 918, 917 };
System.out.println("Result:" + getMaxConcatenatedNumber(numbers));
int[] numbers2 = { 1, 112, 113 };
System.out.println("Result:" + getMaxConcatenatedNumber(numbers2));
int[] numbers3 = { 8, 991, 89, 51, 5, 0 };
System.out.println("Result:" + getMaxConcatenatedNumber(numbers3));
}
}
O(k + n)
Java code:
import java.util.HashMap;
public class MaxSubstring {
public static String maxSubstring(String s1, String s2) {
HashMap<Character, Boolean> s2CharsMap = new HashMap<>();
// mapping all unique chars
char[] s2Chars = s2.toCharArray();
for (int i = 0; i < s2Chars.length; i++) {
s2CharsMap.put(s2Chars[i], true);
}
// now ready to iterate over s1 and get substrings
char[] s1Chars = s1.toCharArray();
String maxSubstring = "";
StringBuffer sb = new StringBuffer();
for (int i = 0; i < s1Chars.length; i++) {
if (s2CharsMap.get(s1Chars[i]) != null) {
sb.append(s1Chars[i]);
} else if (sb.length() > 0) {
if (sb.length() > maxSubstring.length()) {
maxSubstring = sb.toString();
}
sb.setLength(0);
} else
continue;
}
if (sb.length() > maxSubstring.length()) {
maxSubstring = sb.toString();
}
return maxSubstring;
}
public static void main(String[] args) {
String s1 = "abcdefgfoo1elt_fooMaxLength";
String s2 = "kpdrefbt!!!01 a werwerwc";
String maxSubstring = maxSubstring(s1, s2);
System.out.println("s1=\"" + s1 + "\"");
System.out.println("s2=\"" + s2 + "\"");
System.out.println("maxSubstring=\"" + maxSubstring + "\"");
System.out.println("-----------------------------------------------------");
s2 = "xaM Length of";
maxSubstring = maxSubstring(s1, s2);
System.out.println("s1=\"" + s1 + "\"");
System.out.println("s2=\"" + s2 + "\"");
System.out.println("maxSubstring=\"" + maxSubstring + "\"");
}
}
public class StackBy2Queues<E> {
private Queue<E> queue1 = new LinkedList<E>();
private Queue<E> queue2 = new LinkedList<E>();;
public boolean empty() {
return queue2.isEmpty() && queue1.isEmpty();
}
public E peek() {
if (queue2.isEmpty())
return queue1.peek();
return queue2.peek();
}
public synchronized int size() {
return queue2.size() + queue1.size();
}
public synchronized E pop() {
if (queue2.isEmpty())
return queue1.poll();
return queue2.poll();
}
public synchronized E push(E item) {
if (queue2.isEmpty()) {
queue2.add(item);
return item;
}
// Move all elements from queue1 to queue2 and swap
queue2.addAll(queue1);
Queue<E> q = queue1;
q.clear();
queue1 = queue2;
queue2 = q;
queue2.add(item);
return item;
}
public static void main(String[] args) {
StackBy2Queues<Integer> myStack = new StackBy2Queues<>();
for (int i = 0; i < 10; i++) {
myStack.push(i);
}
System.out.println("Stack items count:" + myStack.size());
int order = 1;
while (!myStack.empty()) {
System.out.println("Poped [" + order + "]: " + myStack.pop());
order++;
}
}
}
I believe there is a typo in the description.
Second row explanation for input
1 5
should be:
... stall 1 has 1 ticket, stall 2 has 5.
Also the number of stalls is redundant input unless we need to validate second row input.
import java.util.HashMap;
public class TicketsValue {
public static long calculateMaxAmount(int totalSold, int[] initialNumbers) {
long value = 0;
HashMap<Integer, Integer> initialNumbersCounter = new HashMap<>();
int maxPrice = 0;
for (int i = 0; i < initialNumbers.length; i++) {
if (initialNumbers[i] > maxPrice)
maxPrice = initialNumbers[i];
int counter = 0;
if (initialNumbersCounter.containsKey(initialNumbers[i])) {
counter = initialNumbersCounter.get(initialNumbers[i]);
}
counter++;
initialNumbersCounter.put(initialNumbers[i], counter);
}
int count = 0;
int rem = totalSold;
for (int price = maxPrice; price > 0; price--) {
if (initialNumbersCounter.containsKey(price)) {
count = initialNumbersCounter.get(price);
}
if (count < rem) {
rem -= count;
} else {
count = rem;
rem = 0;
}
value += count * price;
if (rem == 0)
return value;
}
if (rem > 0)
throw new IllegalArgumentException(
"Total number of sold tickets is greater then sum of the tickets which stalls had initially.");
return value;
}
public static void main(String[] args) {
//int numOfStalls = 2;
int totalSold = 4;
int[] remainings = { 1, 5 };
System.out.println("Maximum Amount: $" + calculateMaxAmount(totalSold, remainings));
}
public static <T> Iterator<T> repeat(T e, int num) {
final T t = e;
final int number = num;
return new Iterator<T>() {
private T object = t;
private int repeatNumber = number;
private int counter = 0;
@Override
public boolean hasNext() {
return counter < repeatNumber;
}
@Override
public T next() {
counter++;
return object;
}
@Override
public void remove() {
repeatNumber--;
}
};
}
public static void main(String[] args) {
Iterator<String> iter = repeat("Test repeater", 7);
while (iter.hasNext()) {
System.out.println(iter.next());
}
}
Brut force implementation:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
public class SwapCounter2 {
HashMap<Character, Pair> original_pairs = new HashMap<>();
HashMap<Character, Pair> pairs = new HashMap<>();
char[] original_placement;
char[] best_placement;
int minSwaps;
public int countSwaps(char[] input) {
original_placement = Arrays.copyOf(input, input.length);
minSwaps = -1;
original_pairs.clear();
// Finding pairs
for (int i = 0; i < input.length; i++) {
Character c = input[i];
Pair p;
if (original_pairs.containsKey(c)) {
p = original_pairs.get(c);
p.pos1 = i;
} else {
p = new Pair(input[i]);
p.pos0 = i;
original_pairs.put(c, p);
}
}
ArrayList<Character> keys = new ArrayList<Character>(original_pairs.keySet());
// Removing not paired characters and building inp str
StringBuilder sb = new StringBuilder();
for (Character c : keys) {
sb.append(c);
Pair p = original_pairs.get(c);
if (!p.isPair()) {
original_pairs.remove(c);
}
}
String allChars = sb.toString();
generateAndCheck("", allChars, allChars.length());
for (int i = 0; i < input.length; i++) {
input[i] = best_placement[i];
}
return minSwaps;
}
private void cloneOriginalPairs() {
pairs.clear();
for (Character c : original_pairs.keySet()) {
Pair p = original_pairs.get(c).clonePair();
pairs.put(p.c, p);
}
}
private void checkPlacement(String str) {
cloneOriginalPairs();
char[] candidatePalcement = new char[original_placement.length];
char[] strChars = str.toCharArray();
int j = 0;
for (int i = 0; i < strChars.length; i++) {
candidatePalcement[j] = strChars[i];
if (original_pairs.containsKey(strChars[i])) {
j++;
candidatePalcement[j] = strChars[i];
}
j++;
}
char[] input_clone = Arrays.copyOf(original_placement, original_placement.length);
Pair p = getNotNextPair();
int swaps = 0;
while (p != null) {
swap(p, input_clone, candidatePalcement);
swaps++;
if (minSwaps >= 0 && swaps > minSwaps)
return;
p = getNotNextPair();
}
minSwaps = swaps;
best_placement = candidatePalcement;
}
private void swap(Pair p, char[] current, char[] placement) {
for (int i = 0; i < placement.length; i++) {
if (placement[i] == p.c && (i != p.pos0 && i != p.pos1)) {
p.swap(i, current, pairs);
return;
}
}
}
private void generateAndCheck(String str, String input, int length) {
if (str.length() == length) {
checkPlacement(str);
} else
for (int i = 0; i < input.length(); i++)
generateAndCheck(str + input.charAt(i), input.substring(0, i) + input.substring(i + 1), length);
}
private Pair getNotNextPair() {
for (Character c : pairs.keySet()) {
Pair p = pairs.get(c);
if (p.isNexEachOther())
continue;
return p;
}
return null;
}
public class Pair {
char c;
public int pos0 = -1;
public int pos1 = -1;
public Pair(char chr) {
c = chr;
}
public boolean isPair() {
return (pos1 >= 0 && pos0 >= 0);
}
public boolean isNexEachOther() {
if (isPair()) {
return Math.abs(pos0 - pos1) == 1;
}
return false;
}
public Pair clonePair() {
Pair p = new Pair(this.c);
p.pos0 = this.pos0;
p.pos1 = this.pos1;
return p;
}
/*
* public boolean isSwapable(Pair other) { return (Math.abs(pos0 -
* other.pos0) == 1 && Math.abs(pos1 - other.pos1) == 1) ||
* (Math.abs(pos0 - other.pos1) == 1 && Math.abs(pos1 - other.pos0) ==
* 1); }
*/
public void swap(int swapPos, char[] arr, HashMap<Character, Pair> otherPairs) {
if (Math.abs(pos0 - swapPos) == 1) {
swapPos1(swapPos, arr, otherPairs);
} else {
swapPos0(swapPos, arr, otherPairs);
}
}
public void swapPos0(int swapPos, char[] arr, HashMap<Character, Pair> otherPairs) {
char swapChar = arr[swapPos];
Pair p = null;
if (otherPairs.containsKey(swapChar)) {
p = otherPairs.get(swapChar);
}
arr[pos0] = swapChar;
int swappedPos = pos0;
pos0 = swapPos;
arr[swapPos] = c;
if (p != null) {
if (p.pos0 == swapPos) {
p.pos0 = swappedPos;
} else {
p.pos1 = swappedPos;
}
}
}
public void swapPos1(int swapPos, char[] arr, HashMap<Character, Pair> otherPairs) {
char swapChar = arr[swapPos];
Pair p = null;
if (otherPairs.containsKey(swapChar)) {
p = otherPairs.get(swapChar);
}
arr[pos1] = swapChar;
int swappedPos = pos1;
pos1 = swapPos;
arr[swapPos] = c;
if (p != null) {
if (p.pos0 == swapPos) {
p.pos0 = swappedPos;
} else {
p.pos1 = swappedPos;
}
}
}
}
public static void main(String[] args) {
SwapCounter2 swapCnt = new SwapCounter2();
String inpStr = "CABEABEDDC";
// String inpStr = "CABABDDC";
// String inpStr = "CABBAC";
// String inpStr = "AABCCDBEFGGEHH";
// String inpStr = "caabbddc";
char[] input = inpStr.toCharArray();
int result = swapCnt.countSwaps(input);
System.out.println(" Input: " + inpStr);
System.out.println(" Result: " + new String(input) + " swaps:" + result);
System.out.println("\n====================================");
}
}
Recursive call with swapping elements before and after.
- artak.a.petrosyan November 24, 2015