zyfo2
BAN USER- 0of 0 votes
Answersc = ‘a’
- zyfo2 in United States
w = “apple”
c covers w, iff w contains c.
c_set = {‘a’, ‘b’, ‘c’, ‘g’}
w_set = {‘apple’, ‘ibm’, ‘cisco’, ‘google’}
c_set covers w_set, iff every w in w_set is covered by some c in c_set.
Given c_set and w_set, Whether w_set is covered by c_set?
Follow up: if w_set is fixed say a book, how to determine whether a c_set covers this w_set?| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures
//simple code for comparing using left and right stack
//which is basically in order traversing using stack,
//when you are traversing in left subtree using left stack, every
//time pops, push the right child of the current node and all the
//left child of the right child.
Stack left;
while(root!=null){//initialize
left.push(root.l);
root=root.l;}
node root=left.pop();//when comparing using left stack
if(root.right!=null){
left.push(root.r);
root=root.r}
while(root!=null){
left.push(root.l);
root=root.l;}
bottom up recursion. time complexity O(n)
int max=0;
Stack path;
Stack longestPath(node root){
if(root=null){
Stack s=new Stack();
return s;}
Stack l=longestPath(root.left);
Stack r=longestPath(root.right);
if(l.size()+r.size()+1>max) {
max = l.size()+r.size()+1;
Stack tmp=new Stack();
tmp.addAll(l);
tmp.push(root);
tmp.addAll(r);
path=tmp;}
l.push(root);
r.push(root);
return l.size()>r.size()?l:r;}
node copy(node root){
HashMap old=new HashMap();
HashMap now=new HashMap();
int i=0,j=0;
oldfirst=root;
while(root!=null){
old.put(root,i);
root=root.next;
i++;}
node head=new node();
node first=head;
now.put(j,head);
while(j<i-1){
node tmp=new node();
head.next=tmp;
head=tmp;
j++;
now.put(j,head);}
head.next=null;
head=first;
root=oldfirst;
while(head!=null){
head.other=now.get(old.get(root));
head=head.next;
root=root.next;}
return first;}
does priority exist in these characters?
I assume the priority is { > ( > [ then we can use O(1) space to solve it
int a=0,b=0,c=0;
for (int i = 0; i < strlen(str): i++)
{
if(str[i]=='[') a++;
if(str[i]==']'){ a--; if(a<0) return false;}
if(str[i]=='(') {b++; if(a>0) return false;}
if(str[i]==')'){ b--; if(a>0||b<0) return false;}
if(str[i]=='{') {c++; if(a>0||b>0) return false;}
if(str[i]=='}') {c--; if(a>0||b>0||c<0) return false;}
}
if(a==0&&b==0&&c==0) return true;
return false;}
I get you. but you are only calculating the max for 1:5 and 2:6, it's also possible the max will be from a different starting point.
for example (-1) * 2 +3 *(-4) + (-5) +(-1) you can't get the max from 1:5 or 2:6, the max should be ((-5)+(-1)*2+(3))*(-4). I posted my solution already. you can check it.
I know it's preorder and supposed to be O(n). I'm just confused with why it specifies twice doesn't count as O(n). You know when you do recursive functions, you are storing the state in the stack so that you can get back to it later. you are not calculating the sum twice but technically you are visiting the same node more than once. I probably misunderstood the statement.
- zyfo2 January 21, 2013this makes sense. I wrote some code to elaborate the idea. let me know if I get it right. time complexcity O(n^3)
assume input as two arrays: list[N] has N integers, operator[N] has N corresponding operators
int dp[][]=new int[N][N]; /* row i represents computing with starting point of list[i] and column j represents the max result with j numbers after list[i];*/
int max=Integer.MIN_VALUE;
for(int i=0;i<N;i++){
dp[i][0]=list[i];}
for(int j=1;j<N;j++){
for(int i=0;i<N;i++){
for(int k=0;k<j;k++){
int val=compute(dp[i][k],operator[(i+k)%N],dp[(i+k+1)%N][j-k-1]);
if(val>dp[i][j]) dp[i][j]=val;
if(val>max&&j==N-1) max=val;
}}}
return max;
So are you saying that this problem is just about where to start first and then compute them vertex by vertex sequentially? I'm afraid you can't just do it just sequentially. say 1+2+3*4+5*1, you have to both compute 1+2+3 and 4+5 first, then multiply them. and there may also be negative numbers which can't be treated by adding first.
- zyfo2 January 17, 2013brute force recursive solution
boolean cycle(String[] words,int start){
if(start==words.length&&words[0].charAt[0]==words[words.length-1].charAt(words[words.length-1].length()-1)) return true;
for(int i=start;i<words.length;i++){
if(start==0){
swap(words[start],words[i]);
if(cycle(words,start+1)) return true;
}
else{
if(words[i].charAt(0)==words[start-1].charAt(words[start-1].length()-1)){
swap(words[start],words[i]);
if(cycle(words,start+1)) return true;}
}
return false;}
in main call cycle(words,0)
in hadoop the counter is used like global accessibility. it's asynchronized during a task and get eventually synchronized after the task finished.
- zyfo2 January 29, 2013