diloreto.p
BAN USERdef findFirstNonRepeat(hasNext:()=>Boolean, next:()=>Char): Option[String] = {
@tailrec
def helper(lm:ListMap[String, Boolean]):Option[String] = {
val nextWord = parseWord(hasNext, next)
nextWord match {
case None => lm.filter{ case (_, duplicated) => !duplicated}.map(_._1).headOption
case Some(word) => helper(lm + (word -> lm.contains(word)))
}
}
helper(ListMap.empty)
}
The solution instead to iterate on every single element of the list, is doubling the index to check each time, once the value at the index is greater than the value we are looking for, will move to the middle index between the current position and the previous and keep it doing recursively until it converges.
- diloreto.p February 22, 2015/**
* Suppose you have an array with infinite numbers,
* which is sorted and there may be duplicates.
* Find the occurrence of a number.
*/
def findDuplicate(xs:Stream[Int], n:Int):Boolean = {
def helper(previous:Int, index:Int, upperBound:Option[Int]): Boolean = {
val value = xs(index)
if(value == n) {
value == xs(index-1) || value == xs(index+1)
}
else if(value < n) {
val upperValue = upperBound.getOrElse(3*index)
val nextIndex = index + (upperValue - index)/2
helper(index, nextIndex, upperBound)
}
else {
val nextIndex = previous + (index - previous)/2
helper(previous, nextIndex, Some(index))
}
}
helper(0, 1, None)
}
/**
* You are given an array,
* you have to replace each element of the array with product of the rest element.
* Example: {1,2,3}==> {6,3,2}
*/
def rest(xs:List[Int]):List[Int] = {
val product = xs.reduce(_*_)
xs.map(x => if(x==0) product else product/x)
}
Solution with immutable list.
This solution can be improved removing the usage of foldLeft (because each foldLeft costs O(n) so a valueAccumulator will simply solve the problem.
def subsets(elements: List[Int]): List[List[Int]] = {
def subsetsBranch(c: List[Int], acc: List[Int]): List[List[Int]] = (c, acc) match {
case (Nil, a) => if (a.foldLeft(0)(_ + _) == 5) a :: Nil else Nil
case (_, Nil) => Nil
case (h :: t, _) if (acc.foldLeft(h)(_ + _) == 5) => (h :: acc) :: subsetsBranch(c.tail, acc)
case (h :: t, _) if (acc.foldLeft(h)(_ + _) < 5) => subsetsBranch(t, h :: acc)
case (h :: t, _) if (acc.foldLeft(h)(_ + _) > 5) => subsetsBranch(c.tail, acc.tail) // > 5
}
elements match {
case Nil => Nil
case h :: t => subsetsBranch(t, List(h)) ++ subsets(t)
}
}
/**
* If a=1, b=2, c=3,....z=26. Given a string,
* find all possible codes that string can generate.
* Give a count as well as print the strings.
*
* For example:
* Input: "1123". You need to general all valid alphabet codes from this string.
*
* Output List
* aabc //a = 1, a = 1, b = 2, c = 3
* kbc // since k is 11, b = 2, c= 3
* alc // a = 1, l = 12, c = 3
* aaw // a= 1, a =1, w= 23
* kw // k = 11, w = 23
*
* @author patrick
*
*/
public class Digit2String {
public static void main(String[] args) {
d2s("",new int[]{1, 1, 2, 3}, 0);
}
public static void d2s(String accumulator, int[] A, int start) {
if(start>=A.length) {
System.out.println(accumulator);
return;
}
d2s(accumulator + new String(d2c(A[start])), A, start+1);
if(start<A.length-1) {
int c2value= A[start]*10 + A[start+1];
if(c2value<=26)
d2s(accumulator + d2c(c2value), A, start+2);
}
}
private static String d2c(int v) {
return new String(Character.toChars(96+v));
}
}
it fails because the list is very small and the distribution to get the next index is expo, so because the list has only 7 elements on the 3rd iteration I'm looking already at the index 8. The pre-condition of the problem says that is a huge list where I don't know the size as that is very large.
- diloreto.p July 07, 2013/**
* You are given a list of integers.
* You can call only one method on the list:getItemAt(x),
* which will return the integer at the index x from the list.
*
* The list starts with value 0 and it goes on to have value 0 continuously until some index.
* After the index the list continues to have value 1 till the end.
*
* You do not know the size of the list.
* Its huge.
* You need to find the index from where the value 1 begins in the list.
* @author patrick_diloreto
*
*/
public class FindPivot {
public static void main(String[] args) {
//pivot-index = 16
int[] elements = new int[] {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 , 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
int index = findPivotIndex(elements, 0, 0);
System.out.println("16 == " + index);
assert(16 == index);
}
public static int findPivotIndex(int[] elements, int index, int previous) {
int value = elements[valueFor(index)];
if(value == 0)
return findPivotIndex(elements, index+1, index);
else {
//value = 1
return binarySearch(elements, valueFor(previous), valueFor(index));
}
}
private static int binarySearch(int[] elements, int start, int end) {
if(end == start)
return start;
else {
int middle = (start + end)/2;
if(start == middle)
return end;
return (elements[middle]==0) ?
binarySearch(elements, middle, end) :
binarySearch(elements, start, middle);
}
}
private static int valueFor(int index) {
if(index == 0) {
return 0;
}
else {
return (int)Math.pow(2, index);
}
}
}
This is a recursive solution to the problem:
/**
* Write a function that takes a string and returns true if the entire string is a palindrome,
* otherwise return false. The function should be case-insensitive and ignore any whitespace or punctuation.
*
* For example, return true for:
* "A man, a plan, a canal: Panama."
* @author patrick
*
*/
public class PalindromeAdv {
private static final char START = 'A';
private static final char END = 'Z';
public static void main(String[] args) {
String text = "A man, a plan, a canal: Panama.";
System.out.println(text + " -> " + isPalindromeRecursive(text.toUpperCase().toCharArray(), 0, text.length()-1));
}
public static boolean isPalindromeRecursive(char[] text, int start, int end) {
if(start>=end)
return true;
char b = text[start];
if(!isValidChar(b)) {
return isPalindromeRecursive(text, start+1, end);
}
char e = text[end];
if(!isValidChar(e)) {
return isPalindromeRecursive(text, start, end-1);
}
return b!=e ? false : isPalindromeRecursive(text, start+1, end-1);
}
private static boolean isValidChar(char c) {
return (c>=START && c<=END);
}
}
This is an iterative solution for the problem
/**
* Write a function that takes a string and returns true if the entire string is a palindrome,
* otherwise return false. The function should be case-insensitive and ignore any whitespace or punctuation.
*
* For example, return true for:
* "A man, a plan, a canal: Panama."
* @author patrick
*
*/
public class PalindromeAdv {
private static final char START = 'A';
private static final char END = 'Z';
public static void main(String[] args) {
String text = "A man, a plan, a canal: Panama.";
System.out.println(text + " -> " + isPalindrome(text));
}
public static boolean isPalindrome(String text) {
if(text == null)
return false;
if(text.length()<=1)
return true;
char[] letters = text.toUpperCase().toCharArray();
int k = text.length()-1;
for(int i=0; i<text.length(); i++) {
char beginning = letters[i];
if(isValidChar(beginning)) {
char ending = letters[k];
while(!isValidChar(ending)) {
k--;
ending = letters[k];
}
if(k<=i)
return true;
if(beginning != ending)
return false;
k--;
}
}
return false;
}
private static boolean isValidChar(char c) {
return (c>=START && c<=END);
}
}
/**
* Given an virtual 4x4 boggle board, and some 4 letter words, determine if the words are in the board
* ex.
*
* S M E F
* R A T D
* L O N I
* K A F B
*
* STAR- no
* TONE- no
* NOTE- yes
* SAND- yes
* etc.
* @author patrick
*
*/
public class Board {
public static void main(String[] args) {
char[][] board = new char[][]{
{'S','M','E','F'},
{'R','A','T','D'},
{'L','O','N','I'},
{'K','A','F','B'}
};
String[] words = new String[] {"STAR", "TONE", "NOTE", "SAND"};
for(String word : words) {
char[] letters = word.toCharArray();
Coordinate[] starters = find(board, letters[0]);
boolean found = false;
for(Coordinate starter : starters) {
if(boggleHelper(board, letters, 1, starter, null)) {
System.out.println(word + " - YES");
found = true;
break;
}
}
if(!found) {
System.out.println(word + " - NO");
}
}
}
private static boolean boggleHelper(char[][] board, char[] word, int index, Coordinate current, Coordinate origin) {
if(index >= word.length) {
return true;
}
Coordinate[] neighbors = findNeighbors(board, current, origin);
for(Coordinate neighbor : neighbors) {
if(board[neighbor.y][neighbor.x] == word[index]) {
if(boggleHelper(board, word, index+1, neighbor, current)) {
return true;
}
}
}
return false;
}
public static Coordinate[] findNeighbors(char[][] board, Coordinate current, Coordinate origin) {
Coordinate[] all = new Coordinate[] {
new Coordinate(current.y+1, current.x-1),
new Coordinate(current.y+1, current.x),
new Coordinate(current.y+1, current.x+1),
new Coordinate(current.y, current.x-1),
new Coordinate(current.y, current.x+1),
new Coordinate(current.y-1, current.x-1),
new Coordinate(current.y-1, current.x),
new Coordinate(current.y-1, current.x+1)
};
List<Coordinate> result = new ArrayList<Coordinate>(all.length);
for(Coordinate c : all) {
if(c.y >=0 && c.y<4 && c.x>=0 && c.x<4 && !c.equals(origin)) {
result.add(c);
}
}
return result.toArray(new Coordinate[result.size()]);
}
private static Coordinate[] find(char[][] board, char c) {
List<Coordinate> results = new LinkedList<Coordinate>();
for(int y=0; y<4; y++) {
for(int x=0; x<4;x++) {
if(board[y][x] == c) {
results.add(new Coordinate(y, x));
}
}
}
return results.toArray(new Coordinate[results.size()]);
}
}
public class Coordinate {
public int x;
public int y;
public Coordinate() {}
public Coordinate(int y, int x) {
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object obj) {
if(obj instanceof Coordinate) {
Coordinate c = (Coordinate)obj;
return this.x == c.x && this.y == c.y;
}
return false;
}
@Override
public int hashCode() {
return y*10 + x;
}
}
The solution is based on the creation of a binary tree, left branch values smaller than the node, right branch values greater than the node and smaller than 26. A visitor then will visit the tree and create all the strings based on the path.
/**
* If a=1, b=2, c=3,....z=26. Given a string,
* find all possible codes that string can generate.
* Give a count as well as print the strings.
*
* For example:
* Input: "1123". You need to general all valid alphabet codes from this string.
*
* Output List
* aabc //a = 1, a = 1, b = 2, c = 3
* kbc // since k is 11, b = 2, c= 3
* alc // a = 1, l = 12, c = 3
* aaw // a= 1, a =1, w= 23
* kw // k = 11, w = 23
*
* @author patrick
*
*/
public class App {
private static final String DEFAULT = "1123";
public static void main(String[] args) {
char[] word = DEFAULT.toCharArray();
WordNode root = new WordNode(-1);
parse(word, 0, root);
PrintWordVisitor v = new PrintWordVisitor();
v.visit(root);
WordVisitor wv = new WordVisitor();
wv.visit(root);
for(String s : wv.getValues()) {
System.out.println(s);
}
}
private static void parse(char[] word, int index, WordNode parent) {
if(index<word.length) {
//build left node
int lvalue = Integer.parseInt(new String(new char[] {word[index]}));
WordNode left = new WordNode(lvalue);
parent.setLeft(left);
parse(word, index+1, left);
int rightIndex = index+1;
if(rightIndex<word.length) {
int rvalue = Integer.parseInt(new String(new char[] {word[index], word[rightIndex]}));
if(rvalue<=26) {
WordNode right = new WordNode(rvalue);
parent.setRight(right);
parse(word, rightIndex+1, right);
}
}
}
}
}
public class WordNode {
private WordNode left;
private WordNode right;
private int value;
public WordNode(int value) {
this.value = value;
}
public WordNode getLeft() {
return left;
}
public void setLeft(WordNode left) {
this.left = left;
}
public WordNode getRight() {
return right;
}
public void setRight(WordNode right) {
this.right = right;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
}
Visitor that print all the possible strings:
public class WordVisitor {
private static int BASE_VALUE = 96;
private Set<String> values = new HashSet<String>();
public void visit(WordNode node) {
values.clear();
visitHelper("", node);
}
private void visitHelper(String base, WordNode node) {
if(node.getValue()>0) {
base += new String(Character.toChars(BASE_VALUE+node.getValue()));
}
//is leaf?
if(node.getLeft() == null) {
values.add(base);
}
else {
visitHelper(base, node.getLeft());
if(node.getRight() != null) {
visitHelper(base, node.getRight());
}
}
}
public Set<String> getValues() {
return values;
}
}
Here is another visitor that print the tree structure:
public class PrintWordVisitor implements IVisitor {
public void visit(WordNode node) {
visitHelper("", node);
}
private void visitHelper(String indent, WordNode node) {
System.out.println(indent + "[node: " + node.getValue() + "]");
if(node.getLeft() != null) {
visitHelper(indent+" ", node.getLeft());
if(node.getRight() != null) {
visitHelper(indent+" ", node.getRight());
}
}
}
}
Output:
Tree structure:
[node: -1] // Root
[node: 1]
[node: 1]
[node: 2]
[node: 3]
[node: 23]
[node: 12]
[node: 3]
[node: 11]
[node: 2]
[node: 3]
[node: 23]
String combinations:
kw
kbc
alc
aaw
aabc
/**
* You are given an array of 1's 2's and 3's. Sort this list so the 1's are first, the 2's come second, and the 3's come third.
*
* Ex: Input [1, 3, 3, 2, 1]
* Output [1, 1, 2, 3, 3]
*
* But there is a catch!! The algorithm must be one pass, which means no merge/quick sort. Also no extra list allocations are allowed, which means no bucket/radix/counting sorts.
*
* You are only permitted to swap elements.
*
* @author patrick
*
*/
public class App {
private static void swap(int[] values, int i, int j) {
int x = values[j];
values[j] = values[i];
values[i] = x;
}
public static void sort(int[] values) {
for(int i=1; i<values.length; i++) {
int j = i;
while(j>0) {
int v = values[j];
//adjacent value
int pv = values[j-1];
//if current value is smaller than adjacent
if(v < pv) {
swap(values, j-1, j);
j--;
}
else {
break;
}
}
}
}
public static void main(String[] args) {
int[] values = new int[] {1, 3, 3, 2, 1};
sort(values);
for(int v : values) {
System.out.print(v + " ");
}
}
}
**
*
* Given an array, find all unique three-member subsets,
* with unique being that [0,2,3] and [3,2,0] are the same set.
* Should run in faster than 2^n time
* @author patrick
*
*/
public class UniqueGroup {
public static void main(String[] args) {
int[] values = new int[] {1, 2, 3, 4, 5};
List<int[]> r = unique(values);
for(int[] t : r) {
System.out.println("[" + t[0] + " " + t[1] + " " + t[2] + "]");
}
}
public static List<int[]> unique(int[] values) {
List<int[]> results = new ArrayList<int[]>();
for(int j=0; j<values.length; j++) {
int a = values[j];
int i=j;
int k=j+1;
while(i< values.length-2) {
results.add(new int[] {a, values[i+1], values[k+1]});
k++;
if(k==values.length-1) {
i++;
k=i+1;
}
}
}
return results;
}
}
Utility methods:
- diloreto.p February 24, 2015