cubed
BAN USERO(2 * k) per character where k is the size of your stream's horizon (e.g. 10 here). I used k = 3 for demonstration purposes; change k's assignment to whatever you need otherwise.
To those demanding logic:
1) This build a prefix tree; each k-character instance encountered is added to the tree (if not already contained within it).
2) Adding to a prefix tree is linear in the length of the insertion (e.g. k).
3) Seeing if the string is contained in the tree is linear in the length of the String being checked (e.g. k).
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
public class Main{
static public void main(String[] args){
//I set k to 3, but you can easily up it to 10 if you want the full solution.
//It's easier to produce verifiable test cases for k = 3.
int k = 3;
Set<String> testStreams = new HashSet<String>();
testStreams.add("noasdninsfounlasdfnjnalfyuewebsLDKFkjjkwebweb");
testStreams.add("sadmaonunoonoqwqejklnbnmqw");
for(String testStream : testStreams){
analyzeStream(testStream, k);
}
}
private static void analyzeStream(String stream, int k){
System.out.println("Analyzing stream: " + stream);
Node root = new Node(true);
for(int i = 0; i < stream.length() - k + 1; i++){
String substr = stream.substring(i, i + k);
if(root.contains(substr)){
System.out.println(substr + " found in stream.");
}
root.addString(substr);
}
System.out.println();
}
private static class Node{
Map<Character, Node> children;
boolean root;
public Node(){
this(false);
}
public Node(boolean root){
this.root = root;
this.children = new HashMap<Character, Node>();
}
public boolean contains(String str){
//This tree is uniform height; 0 children => depth = 10
if(children.size() == 0 && !root){
return true;
}
Node child = children.get(str.charAt(0));
return child == null ? false : child.contains(str.substring(1));
}
public void addString(String in){
Node cur = children.get(in.charAt(0));
if(cur == null){
cur = new Node();
children.put(in.charAt(0), cur);
}
if(in.length() > 1){
cur.addString(in.substring(1));
}
}
}
}
- cubed November 09, 2014O(n*m*k) where k is the size of the dictionary, m is the maximum length of a word in the dictionary, and n is the length of the input String.
import java.util.HashSet;
import java.util.Set;
public class Main{
public static void main(String[] args){
Set<String> testPhrases = new HashSet<String>();
testPhrases.add("I am using a hashset.");
testPhrases.add("My bank account is overdrawn.");
testPhrases.add("I do not use any compound words.");
testPhrases.add("I have a doubleset of doublewords.");
Set<String> dictionary = new HashSet<String>();
dictionary.add("hash");
dictionary.add("set");
dictionary.add("over");
dictionary.add("drawn");
dictionary.add("double");
dictionary.add("set");
dictionary.add("word");
dictionary.add("words");
for(String phrase : testPhrases){
findCompounds(phrase, dictionary);
}
}
private static void findCompounds(String phrase, Set<String> dictionary){
for(String subphrase : phrase.split("\\s+")){
findCompound(subphrase.replace(".", "").toLowerCase(), dictionary);
}
}
private static void findCompound(String token, Set<String> dictionary){
Solution[] isFinishableFromHere = new Solution[token.length()];
for(int i = token.length() - 1; i >= 0; i--){
for(String word : dictionary){
if(token.length() - i < word.length()){
continue;
}
boolean match = true;
for(int j = 0; j < word.length(); j++){
if(!word.substring(j, j + 1).equals(token.substring(i + j, i + j + 1))){
match = false;
break;
}
}
if(match){
boolean solved = i + word.length() >= token.length() ? true : isFinishableFromHere[i + word.length()] != null;
if(solved){
isFinishableFromHere[i] = new Solution(word);
}
if(isFinishableFromHere[i] != null){
break;
}
}
}
}
if(isFinishableFromHere[0] != null && isFinishableFromHere[0].getPhrase().length() < token.length()){
System.out.print(token + " = ");
printSolution(isFinishableFromHere);
System.out.println();
}
}
private static void printSolution(Solution[] solns){
int index = 0;
Solution cur = solns[0];
while(cur != null){
System.out.print(cur.getPhrase() + " ");
if(index + cur.getPhrase().length() >= solns.length){
cur = null;
}
else{
cur = solns[index + cur.getPhrase().length()];
}
}
}
private static class Solution{
private String phrase;
public Solution(String phrase){
this.phrase = phrase;
}
public String getPhrase(){
return phrase;
}
}
}
So, getTop([1 .. k)] is order k; this is constant if you fix k = 1, 2, etc.
Push (O(k)).
Pop(O(k + n)) - you hit the n on replacement.
There are a hundred optimizations that you could make to this; among them, I think you could get the getTop() to a true constant (not dependent on k) by maintaining a hashmap from index to node in the topK data structure.
However, this problem escalated for me; I'm so finished with it. ; )
Works, but messy; real interview, I would try cleaning up some more. I wasn't going to publish here, but seeing that there are no other code answers, I feel obliged to provide my input.
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;
public class Main{
static final private Random rand = new Random();
public static void main(String[] args){
int k = 3;
Set<List<Integer>> testCases = new HashSet<List<Integer>>(){{
add(new ArrayList<Integer>(){{
add(1);
add(2);
add(3);
add(4);
}});
add(new ArrayList<Integer>(){{
add(1);
add(2);
add(2);
add(2);
add(0);
add(3);
add(4);
add(-3);
add(-2);
add(1);
add(4);
add(0);
add(0);
add(-1);
add(-1);
add(-1);
add(-1);
add(-1);
add(-1);
add(-1);
}});
add(new ArrayList<Integer>(){{
add(-1);
add(-5);
add(3);
add(4);
}});
}};
//TODO: pop
int index = 0;
for(List<Integer> testCase : testCases){
System.out.println("Running test case: " + ++index);
KStack<Integer> stack = new KStack<Integer>(k);
for(int i : testCase){
if(i >= 0){
System.out.println("Adding " + i);
stack.push(i);
}
else{
System.out.println("Popping");
stack.pop();
}
System.out.println(stack);
int kIndex = rand.nextInt(k) + 1;
System.out.println("top " + kIndex + ": " + stack.getTop(kIndex) + "\n");
}
}
}
public static class KStack<T extends Comparable<T>>{
int k;
int count;
int topKCount;
KStackNode<T> head;
List<TopKNode<T>> topK;
public KStack(int k){
count = 0;
topKCount = 0;
this.k = k;
this.head = null;
topK = new ArrayList<TopKNode<T>>();
}
public void push(T t){
count++;
KStackNode<T> newNode = new KStackNode<T>(t);
newNode.setChild(head);
this.head = newNode;
if(topK.size() == 0){
topKCount++;
topK.add(new TopKNode(t));
return;
}
for(int i = topK.size() - 1; i >= 0; i--){
if(t.compareTo(topK.get(i).getT()) == 0){
topK.get(i).add();
topKCount++;
break;
}
else if(t.compareTo(topK.get(i).getT()) < 0){
if(i != k - 1){
topK.add(i + 1, new TopKNode<T>(t));
topKCount += 1;
if(topK.size() > k){
topKCount -= topK.get(k).getCount();
topK.remove(k);
}
}
break;
}
if(i == 0){
topK.add(0, new TopKNode<T>(t));
topKCount++;
if(topK.size() > k){
topKCount -= topK.get(k).getCount();
topK.remove(k);
}
}
}
}
public T pop(){
if(head == null){
return null;
}
count--;
KStackNode top = head;
head = head.getChild();
T val = (T) top.getT();
for(int i = topK.size() - 1; i >= 0; i--){
int comp = val.compareTo(topK.get(i).getT());
if(comp < 0){
if(i == topK.size() - 1){
break;
}
else if(topK.get(i + 1).remove()){
topK.remove(i + 1);
addToTopK();
}
else{
topKCount--;
}
break;
}
else if(comp == 0){
topKCount--;
if(topK.get(i).remove()){
topK.remove(i);
addToTopK();
}
break;
}
}
return val;
}
public T getTop(int top){
if(top > k || top < 1 || top > count){
return null;
}
for(int i = 0; i < topK.size(); i++){
if(topK.get(i).getCount() >= top){
return topK.get(i).getT();
}
top -= topK.get(i).getCount();
}
return null;
}
private void addToTopK(){
if(topKCount < count){
T max = null;
KStackNode node = head;
T minInTop = topK.get(topK.size() - 1).getT();
while(node != null){
if(((T)node.getT()).compareTo(minInTop) < 0 &&(max == null || ((T) node.getT()).compareTo(max) > 0)){
max = (T) node.getT();
}
node = node.getChild();
}
topKCount++;
topK.add(new TopKNode<T>(max));
}
}
@Override
public String toString(){
return printTopK() + printData() + "\nInTopK: " + topKCount + " / " + count;
}
private String printTopK(){
String ret = "\n";
for(TopKNode<T> n : topK){
ret += "(" + n.getT() + " , " + n.getCount() + ") ";
}
return ret;
}
private String printData(){
String ret = "\n";
KStackNode cur = head;
while(cur != null){
ret += cur.getT() + " ";
cur = cur.getChild();
}
return ret;
}
}
public static class KStackNode<T>{
T t;
KStackNode child;
KStackNode(T t){
this.t = t;
child = null;
}
public T getT(){
return t;
}
public KStackNode getChild(){
return child;
}
public void setChild(KStackNode child){
this.child = child;
}
}
private static class TopKNode<T>{
int num;
T t;
public TopKNode(T t){
this.t = t;
this.num = 1;
}
public T getT(){
return t;
}
public void add(){
num += 1;
}
public int getCount(){
return num;
}
//Returns true if reduced to 0.
boolean remove(){
return --num == 0;
}
}
}
O(n^2)
import java.util.HashMap;
import java.util.Random;
public class Main {
private static Random rand = new Random();
//1
static public void main(String[] args){
int numTries = 10;
for(int i = 0; i < numTries; i++){
int n = Math.abs(rand.nextInt() % 20 + 5);
int[] input = new int[n];
for(int j = 0; j < n; j++){
input[j] = rand.nextInt() % 20;
}
solveEqn(input);
}
}
private static void solveEqn(int[] input){
HashMap<Integer, Indices> map = new HashMap<Integer, Indices>();
for(int i = 0; i < input.length - 1; i++){
for(int j = i + 1; j < input.length; j++){
int sum = input[i] + input[j];
Indices indices = map.get(sum);
if(indices != null){
if(indices.geti() != i && indices.getj() != j){
System.out.println(input[indices.geti()] + " + " + input[indices.getj()] + " = " + input[i] + " + " + input[j]);
return;
}
}
map.put(sum, new Indices(i, j));
}
}
System.out.println("No solution found.");
}
private static class Indices{
int i;
int j;
public Indices(int i, int j){
this.i = i;
this.j = j;
}
public int geti(){
return i;
}
public int getj(){
return j;
}
}
}
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
class Main{
public static void main(String[] args){
Set<String> dictionary = new HashSet<String>();
dictionary.add("back");
dictionary.add("new");
dictionary.add("golf");
dictionary.add("run");
dictionary.add("o");
dictionary.add("omaha");
dictionary.add("nebraska");
dictionary.add("page");
List<String> testStrings = new ArrayList<String>();
//True cases.
testStrings.add("newback");
testStrings.add("nebraska");
testStrings.add("o");
testStrings.add("backnewgolfrunoomahanebraskapage");
testStrings.add("oomahapageo");
//False cases
testStrings.add("car");
testStrings.add("zap");
testStrings.add("oomahe");
testStrings.add("pages");
testStrings.add("backnewgolfrunoomahanebraskapages");
for(String testString : testStrings){
System.out.println(testString + " - " + isComposed(testString, dictionary));
}
}
private static boolean isComposed(String key, Set<String> dictionary){
int length = key.length();
LinkedList<SearchNode> searchNodes = new LinkedList<SearchNode>();
searchNodes.add(new SearchNode(0));
Map<String, LinkedList<String>> shortcutMap = new HashMap<String, LinkedList<String>>();
for(String word : dictionary){
String newKey = word.substring(0, 1);
if(!shortcutMap.containsKey(newKey)){
shortcutMap.put(newKey, new LinkedList<String>());
}
shortcutMap.get(newKey).add(word);
}
//printShortcutmap(shortcutMap);
while(!searchNodes.isEmpty()){
int ptrOrig = searchNodes.getFirst().getPtr();
int ptr = ptrOrig;
searchNodes.removeFirst();
String ltr = key.substring(ptr, ptr + 1);
if(!shortcutMap.containsKey(ltr)){
continue;
}
LinkedList<String> subDic = shortcutMap.get(ltr);
for(String wrd : subDic){
ptr = ptrOrig;
int wrdLen = wrd.length();
if(wrdLen == 1){
if(ptr + 1 == length){
return true;
}
searchNodes.add(new SearchNode(ptr + 1));
continue;
}
ptr++;
boolean match = false;
if(length - ptr >= wrdLen - 2){
match = true;
for(int i = 1; i < wrdLen && ptr < length ; i++){
if(!key.substring(ptr, ptr + 1).equals(wrd.substring(i, i + 1))){
match = false;
break;
}
ptr++;
}
}
if(match){
if(ptr == length){
return true;
}
searchNodes.add(new SearchNode(ptr));
}
}
}
return false;
}
private static void printShortcutmap(Map<String, LinkedList<String>> map){
for(Map.Entry<String, LinkedList<String>> entry : map.entrySet()){
System.out.println(entry.getKey());
for(String word : entry.getValue()){
System.out.println(" " + word);
}
System.out.println();
}
}
private static class SearchNode{
int ptr;
public SearchNode(int ptr){
this.ptr = ptr;
}
public int getPtr(){
return ptr;
}
}
}
- cubed November 03, 2014O(n)
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class Main {
public static void main(String[] args){
List<String> strings = new ArrayList<String>();
strings.add("abc");
strings.add("abc");
strings.add("abc");
strings.add("abd");
strings.add("abc");
strings.add("ab");
strings.add("ab");
strings.add("abc");
strings.add("a");
strings.add("");
strings.add("");
strings.add("c");
strings.add("abde");
strings.add("abcde");
strings.add("bcdefg");
strings.add("abcdefg");
strings.add("");
strings.add("");
strings.add("abcdefg");
strings.add("abcdefg");
Iterator<String> iter = strings.iterator();
while(iter.hasNext()){
String a = (String) iter.next();
String b = (String) iter.next();
System.out.println(a + " - " + b + ": " + withinOneMutation(a, b));
}
}
public static boolean withinOneMutation(String str0, String str1){
int len0 = str0.length(), len1 = str1.length();
if(Math.abs(len0 - len1) > 1){
return false;
}
boolean mismatchFound = false;
int p0 = 0, p1 = 0;
while(p0 < len0 && p1 < len1){
if(str0.substring(p0, p0 + 1).equals(str1.substring(p1, p1 + 1))){
p0++;
p1++;
continue;
}
if(mismatchFound == true){
return false;
}
if(len0 > len1){
p0++;
}
else if(len1 > len0){
p1++;
}
else{
p0++;
p1++;
}
mismatchFound = true;
}
if(!mismatchFound){
return len0 == len1 ? false : true;
}
return true;
}
}
Linear, with test case.
}
- cubed November 13, 2014