CareerCup

Step 1 : Create prefix sum array
Step 2: apply binary search to find reqired box

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    
    public static int bbSearch(int[] a, int l, int r, int k) {
        
        if (l <= r) {
            
            int mid = (l + r +1)/2;
            
            if(l==r && k <= a[mid]) {
                
                return mid;
            }
        
            if( mid >= 1 && k > a[mid-1] && k <= a[mid])
                return mid;
        
            if(a[mid] > k)
                return bbSearch(a, l, mid-1, k);
            if(a[mid] < k) 
                return bbSearch(a, mid+1, r, k);
        }
        return -1;    
    }

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int[] a = new int[n];
		int[] pa = new int[n];
		for(int i = 0; i<n; i++) {
			a[i] = in.nextInt();
			if(i == 0)
				pa[i] = a[i];
                        else	
				pa[i] = pa[i-1] + a[i];
		}
        
        int q = in.nextInt();
        for(int i =0; i < q; i++) {
            int idx = in.nextInt();
            int ans = bbSearch(pa, 0, n-1, idx);
            System.out.println(ans + 1);
        }
		

	}
}

@Erasmus.....if adjacency list is given then u r right ......but in question he mention List of (parent, child ) ...and after that he write adjacency list.....i think adjacency list is not same as List of (parent, child) pairs
consider following small example

A
        /    \
      B     C

adjacency list is

A->{B C}


and (parent,child) is (A,B),(A,C) {(Parent,Child) pairs}

so for constructing adjacency list from (parent,child )pairs we need hashtablet....

@Vin.....no need for root node.....do dfs from any node...u will able to find whether there is loop or not...for finding loop u have to keep track of visited nodes....once u find node again then loop exist otherwise not....

@Erasmus..how can u do dfs in O(1) space complexity in this case....for dfs u have to construct adjacency list or adjacency matrix from given pairs and also u have to keep track of visited nodes while dfs is running O(V) space

in my method u have to traverse list one time... maintaining hash table for counting unique node... simultaneously count number of edges and we are done

we can do it more efficiently ..........in case of binary tree....
number of edges in n nodes binary tree is equals to (n - 1)
count number of nodes in binary tree lets say n
and also count number of edges(numbers of parents child pairs given) lets say e

if(e>n-1)
    return false
else
    return true

yes this is best solution for this problem......

i think above code is correct and telling that weather we can make valid dictionary word by breaking giving word....but in your for loop...u are processing some substrings again and again..which is inefficient i think.... following is java code which printing all valid world from dictionary(or we can modified following code if u want only bool value)...my point is making for loop efficient(only processing one substring one time)...correct me if i wrong..or my code is wrong

public void removeword(String s,int j){
        int i;
        if(s==NULL)
            return;
        if(s.length()==1){
            System.out.println(s);
            return;}
        if(dic.contain(s))
           System.out.println(s);
        for(i=j;i<s.length();i++){
             removeword(s.substring(0,i)+s.substring(i+1,s.length()),i);
        }   
    
    }

we can do this with XOR....suppose 2 elements are present one time....lets take an example
given array is {1,3,1,2,2,5,4,5} our output will be 3 and 4

step 1: XOR all elements...we get 3(XOR)4=111(in binary)
step 2: check first one in binary of XOR from right side....in our example first LSB is one....which means...LSB of required numbers is are not same.....
step 3: divide array in two parts..first part numbers has 1 at LSB and second part number has 0 at LSB

step 4: take XOR of first part we get first number and XOR of second part give second

our example
first part: 1(001),1(001),3(011) ,5(101), 5(101) .....XOR of these give 3
secont part: 2(010),2(010),4(100) XOR of these give 4

output: 3,4....which is required

i think for number more then 2 unique numbers..suppose for 10 unique numbers we have to divide array further to get all 10 element(for further division we can use other bits of xor)

@somebody, is your comment to reffer my code..
then,if counting start from 0 then 52 is BA
or if counting start from 1 then its AZ
my code will give BA for 52(because I start counting from 0)
if u want to start counting from 1....just add num=num-1 to my code after raw_input() line
please comment if my code give wrong answer

python code

num=int(raw_input())
result=""
while(num>=0):
    t=num%26
    result=chr(ord("A")+t)+result
    num=num/26 -1
    
print result

Another possible solution(Python code)

num=int(raw_input())
result=""
while(num>=0):
    t=num%26
    result=chr(ord("A")+t)+result
    num=num/26 -1
    
print result

you can do like this....extra space is required.....but if extra space is not allowed then apply mergsort on array.....at the time of merging put only one instance of integer by discarding all duplicates....complexity is O(nlogn)

@Anon....is this comment reffers to my programm

void strper(char *str,int a,int n,int l){

int i;

if(l==n){
if(a!=2)return;
str[l]='\0';
printf("%s\n",str);
return;
}
if(a!=2){
str[l]='a';
strper(str,a+1,n,l+1);
}

for(i=1;i<26;i++){

str[l]='a'+i;
strper(str,a,n,l+1);

}
}



int main ( ) {
char *str;
int n;
printf("Enter the value of n:");
scanf("%d",&n)
str=(char *)malloc(n+1);
strper(str,0,n,0);

return 0;
}

we have to convert BST into doubly linked list(instead of single) then merge
and then convert back into balabced BST( DLL to balanced BST can be done inplace)

void p2(int open1,int open2,int open3,int close1,int close2,int close3,int n,char *s){

if(open1==0 && close1==0 && open2==0 && close2==0 && open3==0 && close3==0){
printf("%s\n",s);
return;
}
if(open1==close1 && open2==close2 && open3==close3){
if(open1>0){
s[n]='{';
p2(open1-1,open2,open3,close1,close2,close3,n+1,s);}
}

if((open1<close1 ||(open1==0 && close1==0))&& open2==close2 && open3==close3){
if(open1>0){
s[n]='{';
p2(open1-1,open2,open3,close1,close2,close3,n+1,s);}
if(open2>0){
s[n]='[';
p2(open1,open2-1,open3,close1,close2,close3,n+1,s);}
if(close1>1){
s[n]='}';
p2(open1,open2,open3,close1-1,close2,close3,n+1,s);}
}


if((open2<close2 || (open2==0 && close2==0)) && open3==close3){
if(open2>0){
s[n]='[';
p2(open1,open2-1,open3,close1,close2,close3,n+1,s);}
if(open3>0){
s[n]='(';
p2(open1,open2,open3-1,close1,close2,close3,n+1,s);}
if(close2>1){
s[n]=']';
p2(open1,open2,open3,close1,close2-1,close3,n+1,s);}
}

if(open3<close3){
if(open3>0){
s[n]='(';
p2(open1,open2,open3-1,close1,close2,close3,n+1,s);}
if(close3>0){
s[n]=')';
p2(open1,open2,open3,close1,close2,close3-1,n+1,s);}
}

if(close2==1 && open3==0 && close3==0){
s[n]=']';
p2(open1,open2,open3,close1,close2-1,close3,n+1,s);
}

if(close1==1 && open2==0 && close2==0 && open3==0 && close3==0){
s[n]='}';
p2(open1,open2,open3,close1-1,close2,close3,n+1,s);
}

}



int main(){
char *st=malloc(20);

p2(1,4,1,1,4,1,0,st);

}

but interviewer is looking for better then o(n+m)......better then this approach..there is one more approach which is 'improved binary partition'....this approach is fastest approach for searching element in sorted 2d array....
first  we do binary search along either the middle row or middle column and find two element a1   and  a2 such that   a1< search element > a2  or we find required element if element is present in middle row or column
after this our problem divided into two subproblem
solve these subproblem recursively 

for example we have to find 22  in following matrix
[1   14    25   35]           
[2    16    28   38]           
[5     20    28   40]          
[16   22     38   41]

first we do binary search  in  middle row which is row 2
in binary search if we find required element then return,otherwise we find  two element like    16< 22 >28  after this our problem divided in two sub problem
 first
 [5    20] 
 [16  22]   

second is  [25 35]  
 then we solve this two  problem recursively

this approach is much faster

XOR all elements form given set, let say...X
and XOR elements form 1...n,let say..Y
then repeated element is = X(xor)Y
for example set is 1,2,3,4,4
X=1xor2xor3xor4xor4
Y=1xor2xor3xor4
and repeated element is=X(xor)Y=4

XOR all elements form given set, let say...X
and XOR elements form 1...n,let say..Y
then repeated element is = X(xor)Y
for example set is 1,2,3,4,4
X=1xor2xor3xor4xor4
Y=1xor2xor3xor4
and repeated element is=X(xor)Y=4

@ sK thanks i was also thinking about this case
my iretrative solution wrongly asume that mid point of combined string lies in mid point of LL ,which can,t give correct answer to your case(abcdef -> ghihgfed -> c -> b -> a)
in your example mid point of combined string lies in second node
which is not mid point of list so its does not give correct answer
but my recursive solution will work for this but it takes O(n) space due to recursion
i m try to modifie my iretrative soln to work for all case
thanks sK once again for this example because of this i find error on my code
i will back with update soln

we can reach mid point of linklist without knowing its size
just take two pointer fast and slow
initialy

struct node *mid(struct node *head){
struct node *fast=head
struct node *slow=head

while(fast->next!=NULL && fast->next->next!=NULL){
slow=slow->next;
fast=fast->next->next
}
return slow;
}
fast->next!=NULL condition for LL of odd number of node
fast->nex->nextt!=NULL condition for LL of even number of node
after this slow point to mid point of LL

Jay try to run above code post by me u will find it is working properly

yes u r right
a=y2-y1
b=x2-x1
no. of path is c(a+b,a)=c(a+b,b)

first reached at mid point
then reverse last half
then start comparing from head to last half reversed list
then again reverse last half to retain orignal list
try to run this code u will understand
now space complexity is O(1)
please comment if something seems wrong

with out recursion we have to reverse half list
following isolution is with out recursion

struct nodes *reverse(struct nodes *head){

struct nodes *p=NULL;
struct nodes *c=head;
struct nodes *n=head->next;


while(c!=NULL){
c->next=p;
p=c;
c=n;
if(n!=NULL)
n=n->next;
}
return p;
}


int  checkpalindrom2(struct nodes *head){
   
   char *r;
   struct nodes *t=head;
   struct nodes *s=head;
   struct nodes *f=head;
   int ri,li,a,b;
   while(f->next!=NULL && f->next->next!=NULL){
     s=s->next;
     f=f->next->next;
   }
   s->next=reverse(s->next);
   f=s->next;
   li=0;
   while(f!=NULL){
      ri=strlen(f->c);
      while(ri>0){
         if((t->c)[li]!=(f->c)[ri-1]){
            s->next=reverse(s->next);
            return 0;
         }   
         ri--;
         li++;
         if((t->c)[li]=='\0'){
            t=t->next;  
            li=0;
         }

       }
       f=f->next;
    }
    if((t->c)[li]!='\0'){
     r=malloc(strlen(&(t->c)[li]));
     strcpy(r,&(t->c)[li]);
      li=0;
      ri=strlen(r);
      while(ri>li){
        if(r[li]!=r[ri-1]){
            s->next=reverse(s->next);
            return 0;
         }
         li++;
         ri--;
      }
         

    }
       
    s->next=reverse(s->next);
    return 1;
}

try to run following code u will get your answer

struct nodes {
  char *c;
  struct nodes *next;
};


struct nodes *newnodes(char *c){
      struct nodes *temp=malloc(sizeof(struct nodes));
      temp->c=malloc(sizeof(*c));
      strcpy(temp->c,c);
      temp->next=NULL;
      return temp;
}

void pushs(struct nodes **head,char *c){
      struct nodes *temp=*head;
       if(*head==NULL){
          *head=newnodes(c);
           return;
       }
      *head=newnodes(c);
      (*head)->next=temp;
      return;
}

void prints(struct nodes *head){
     struct nodes *t=head;
     while(t!=NULL){
     printf("%s-->",t->c);
     t=t->next;
     }
     printf("NULL \n");
}


int checkpalindrom(struct nodes **left,struct nodes *right){
    static int a=1,b=0,ri=0;
    int li,r;
    if(right==NULL)
        return 1;
    b=b+1;
    r=checkpalindrom(left,right->next);
    if(r==0)
        return 0;
    li=strlen(right->c);
    if(b-a<0)
       return 1;
    while(li>0){
       if(((*left)->c)[ri]!=(right->c)[li-1])
           return 0;
       li--;
       ri++;
       if(((*left)->c)[ri]=='\0'){
           (*left)=(*left)->next;
           a=a+1;
           b=b-1;
           ri=0;
       }
    }
    return 1;
}



void main(){


struct nodes *head=NULL;
struct nodes *left;
struct nodes *right;

//a-->bcd-->ef-->g-->f-->ed-->c-->ba. 
//a-->bcd-->efgf-->edc-->ba 
pushs(&head,"ba");
pushs(&head,"edc");
pushs(&head,"efgf");
pushs(&head,"bcd");
pushs(&head,"a");
//pushs(&head,"zgy");
//pushs(&head,"ef");
//pushs(&head,"bcd");
//pushs(&head,"a");

left=head;
right=head;

prints(head);
printf("\n%d\n",checkpalindrom(&left,right));
prints(head);
}

its not going backward
first right pointer reached at end
till now left still pointing to head
after this compare
right->data to left->data
if not same return not a link list not palindrom return 0
if same increment (*left)=(*left)->next
return 1
after return 1 left pointing to 2nd node and right pointing to 2nd from last
and so on till b-a>=0
'b' increment from 1
and ' a' decrement from n(number of nodes in list)
when b-a=0 both left and right pointing to middle node
after this we do not need to do nothing simply return 1
this is the idea

this is my code to check palindrome
this is just modified version of checking link list palindrom which contain only one character per node

left=head ot LL
right=head of LL
int checkpalindrom(struct nodes **left,struct nodes *right){
    static int a=1,b=0,ri=0;
    int li,r;
    if(right==NULL)
        return 1;
    b=b+1;
    r=checkpalindrom(left,right->next);
    if(r==0)
        return 0;
    li=strlen(right->c);
    
    if(b-a<0)
       return 1;
    while(li>0){
       if(((*left)->c)[ri]!=(right->c)[li-1])
           return 0;
       li--;
       ri++;

       if(((*left)->c)[ri]=='\0'){
           (*left)=(*left)->next;
           a=a+1;
           b=b-1;
           ri=0;
       }
    }
    
    return 1;

}