Vincent
BAN USER- 1of 1 vote
AnswersString getSentence(String text, Set<String> dictionary);
- Vincent in United States
// text is a string without spaces, you need to insert spaces into text, so each word seperated by the space in the resulting string exists in the dictionary, return the resulting string
// running time has to be at least as good as O(n)
// getSentence("iamastudentfromwaterloo", {"from, "waterloo", "hi", "am", "yes", "i", "a", "student"}) -> "i am a student from waterloo"| Report Duplicate | Flag | PURGE
Twitter Google Software Engineer / Developer Software Engineer in Test Algorithm
You have two votes, but I think there is a bug. Correct me if I am wrong.
In the following case:
0 1 1 0
0 1 0 0
In the first step you ll change the matrix to be
0 0 1 0
0 1 0 0.
and the answer would be 2 for your algorithm, which is not correct.
Is that rite?
public class IntComparator implements Comparator<Integer>{
@Override
public int compare(Integer arg0, Integer arg1) {
if(Integer.parseInt(arg0+""+arg1)>Integer.parseInt(arg1+""+arg0))
return 1;
else if(Integer.parseInt(arg0+""+arg1)<Integer.parseInt(arg1+""+arg0))
return -1;
return 0;
}
}
Briget design pattern should be used
public abstract class Furniture
{
private Material material;
public void setMaterial(Material m)
{
material=m;
}
public int getIgnitionPoint()
{
return this.material.getIgnitionPoint();
}
}
public interface Material
{
...
}
public class Oak implements Material
public class Steel implements Material
public class Desk extends Furniture
public class Chair extends Furniture
using selection algorithm
1. quickselect (amorized cost is O(n))
or 2. median of median algorithmO(n))
pesudo code:
input: Array
Element elements=new Element[3];
elements[0]=selectKthElement(Array,0);
elements[1]=selectKthElement(Array,Array.size/3);
elements[2]=selectKthElement(Array,Array.size/3*2);
// each Element in elements is a candidate for appearing more than n/3 times.
for(int i=0;i<elements.size;i++)
{
if(appearMoreThanNOver3Times(elements[i]))
print(elements[i]);
}
set unknown = createSet(All the people)
set notCelebrity;
while(size(unknown)>1)
{
randomly choose two people from unknown (first,second);
if(knows(first,second))
{
remove first from unknown and put into notCelebrity;
}
else
{
if(knows(second,first))
{
remove second from unknown and put into not Celebrity;
}
else
{
// first doesn't know second and second doesn't know first
remove first and second from unknown and put them into notCelebrity
}
}
}
Dude, thx for your solution, do you mind to explain why it is the minimum cost solution?
- Vincent March 17, 2014