Re: [algogeeks] Re: Amazon Question
Looks good. I concede that it works for a Binary Search Tree. On Sat, Jan 29, 2011 at 1:35 AM, Ritu Garg ritugarg.c...@gmail.com wrote: @nphard,see the following approach carefully to know *if right pointer is pointing to right child or in order successor* * *Q = node-right IF (Q is not NULL) { /*Determine if Q is node's right child or successor*/ /*Q is inorder successor of node*/ IF (Q-left == node OR Q-left-val node-val) { } /*Q is the right child of node*/ ELSE IF (Q-left == NULL or Q-left-val node-right) { } } 1. Q-left is smaller than or equal to node if Q is Inorder Successor of node 2. Q-left is either NULL or Q-left is greater than node if Q is right child of node * *Hence* in order traversal of right threaded BST without flag* is possible On Fri, Jan 28, 2011 at 9:40 AM, nphard nphard nphard.nph...@gmail.comwrote: Not correct. You cannot assume that the right node always points to the successor. If you do that, your traversal will be affected. Consider that when you reach a node B from the right pointer of its parent A, you traverse that subtree rooted at B in normal inorder. However, when you reach B from its inorder predecessor C, you should have the knowledge that you have visited that node's left subtree and should not visit again (which is only known if you have the information that you are reaching that node through a thread). On Thu, Jan 27, 2011 at 10:57 PM, Ritu Garg ritugarg.c...@gmail.comwrote: @nphard ideally,a flag is required in right threaded tree to distinguish whether right child is a pointer to inorder successor or to right child.Even we can do without flag assuming that there ll be no further insertions taking place in tree and no other traversal is required. here we suppose that right pointer always gives the successor.. The solution to get the linear inorder traversal is just tailored for a situation where there is no extra space,not even for stack!!! On Fri, Jan 28, 2011 at 5:42 AM, nphard nphard nphard.nph...@gmail.comwrote: @Ritu - Do you realize that you cannot just convert a given binary tree into right-threaded binary tree? You need at least 1 bit information at each node to specify whether the right pointer of that node is a regular pointer or pointer to the inorder successor. This is because traversal is done differently when you arrive at a node through its inorder predecessor. On Thu, Jan 27, 2011 at 7:22 AM, Ritu Garg ritugarg.c...@gmail.comwrote: solution is not too hard to understand!! 1. [quote] For every none leaf node , go to the last node in it's left subtree and mark the right child of that node as x [\quote]. How are we going to refer to the right child now ??We have removed it's reference now !! last node in left sub tree of any node always have right pointer as NULL because this is the last node 2. It is to be repeated for every node except the non leaf nodes . This will take O(n*n) time in worst case , say a leftist tree with only left pointers . root makes n-1 traversals , root's left subtree's root makes n-2 , and so on. i said that it ll take O(n) time for well balanced tree. for a node at height h ,it takes O(h) to fill this node as successor of some other node.if combined for all sum(O(h)) h=1 to lg n ..total time ll come as O(n) 3. Take the case below . 1 2 3 1 1.5 2.5 4 for node 2 , you will go to 1 , which is the successor of 2 , you make 2-right=1 but what about node 1.5 ??? same is the case with node 3 ... 3-right=2.5 . How will we refer to 4 now ?? when you ll process node 1,it ll be filled in as right child of 1.5 there is no successor for 4. In Brief 1. Convert the tree to right threaded binary tree.means all right children point to their successors. it ll take no additional space.ll take O(n) time if tree is well balanced 2. Do inorder traversal to find ith element without using extra space because succssor of each node is pointed by right child. i hope you got it now!! On Wed, Jan 26, 2011 at 5:31 PM, sankalp srivastava richi.sankalp1...@gmail.com wrote: I don't seem to understand ur solution . [quote] For every none leaf node , go to the last node in it's left subtree and mark the right child of that node as x [\quote]. How are we going to refer to the right child now ??We have removed it's reference now !! It is to be repeated for every node except the non leaf nodes . This will take O(n*n) time in worst case , say a leftist tree with only left pointers . root makes n-1 traversals , root's left subtree's root makes n-2 , and so on. Go to the largest node in the left subtree .This means go to the left subtree and keep on going to the right until it becomes null , in which case , you make y-right as x . This means effectively , that y is the predecessor of x , in the tree .
Re: [algogeeks] Re: Amazon Question
Yes,it works for binary search tree only On Sat, Jan 29, 2011 at 2:22 PM, nphard nphard nphard.nph...@gmail.comwrote: Looks good. I concede that it works for a Binary Search Tree. On Sat, Jan 29, 2011 at 1:35 AM, Ritu Garg ritugarg.c...@gmail.comwrote: @nphard,see the following approach carefully to know *if right pointer is pointing to right child or in order successor* * *Q = node-right IF (Q is not NULL) { /*Determine if Q is node's right child or successor*/ /*Q is inorder successor of node*/ IF (Q-left == node OR Q-left-val node-val) { } /*Q is the right child of node*/ ELSE IF (Q-left == NULL or Q-left-val node-right) { } } 1. Q-left is smaller than or equal to node if Q is Inorder Successor of node 2. Q-left is either NULL or Q-left is greater than node if Q is right child of node * *Hence* in order traversal of right threaded BST without flag* is possible On Fri, Jan 28, 2011 at 9:40 AM, nphard nphard nphard.nph...@gmail.comwrote: Not correct. You cannot assume that the right node always points to the successor. If you do that, your traversal will be affected. Consider that when you reach a node B from the right pointer of its parent A, you traverse that subtree rooted at B in normal inorder. However, when you reach B from its inorder predecessor C, you should have the knowledge that you have visited that node's left subtree and should not visit again (which is only known if you have the information that you are reaching that node through a thread). On Thu, Jan 27, 2011 at 10:57 PM, Ritu Garg ritugarg.c...@gmail.comwrote: @nphard ideally,a flag is required in right threaded tree to distinguish whether right child is a pointer to inorder successor or to right child.Even we can do without flag assuming that there ll be no further insertions taking place in tree and no other traversal is required. here we suppose that right pointer always gives the successor.. The solution to get the linear inorder traversal is just tailored for a situation where there is no extra space,not even for stack!!! On Fri, Jan 28, 2011 at 5:42 AM, nphard nphard nphard.nph...@gmail.com wrote: @Ritu - Do you realize that you cannot just convert a given binary tree into right-threaded binary tree? You need at least 1 bit information at each node to specify whether the right pointer of that node is a regular pointer or pointer to the inorder successor. This is because traversal is done differently when you arrive at a node through its inorder predecessor. On Thu, Jan 27, 2011 at 7:22 AM, Ritu Garg ritugarg.c...@gmail.comwrote: solution is not too hard to understand!! 1. [quote] For every none leaf node , go to the last node in it's left subtree and mark the right child of that node as x [\quote]. How are we going to refer to the right child now ??We have removed it's reference now !! last node in left sub tree of any node always have right pointer as NULL because this is the last node 2. It is to be repeated for every node except the non leaf nodes . This will take O(n*n) time in worst case , say a leftist tree with only left pointers . root makes n-1 traversals , root's left subtree's root makes n-2 , and so on. i said that it ll take O(n) time for well balanced tree. for a node at height h ,it takes O(h) to fill this node as successor of some other node.if combined for all sum(O(h)) h=1 to lg n ..total time ll come as O(n) 3. Take the case below . 1 2 3 1 1.5 2.5 4 for node 2 , you will go to 1 , which is the successor of 2 , you make 2-right=1 but what about node 1.5 ??? same is the case with node 3 ... 3-right=2.5 . How will we refer to 4 now ?? when you ll process node 1,it ll be filled in as right child of 1.5 there is no successor for 4. In Brief 1. Convert the tree to right threaded binary tree.means all right children point to their successors. it ll take no additional space.ll take O(n) time if tree is well balanced 2. Do inorder traversal to find ith element without using extra space because succssor of each node is pointed by right child. i hope you got it now!! On Wed, Jan 26, 2011 at 5:31 PM, sankalp srivastava richi.sankalp1...@gmail.com wrote: I don't seem to understand ur solution . [quote] For every none leaf node , go to the last node in it's left subtree and mark the right child of that node as x [\quote]. How are we going to refer to the right child now ??We have removed it's reference now !! It is to be repeated for every node except the non leaf nodes . This will take O(n*n) time in worst case , say a leftist tree with only left pointers . root makes n-1 traversals , root's left subtree's root makes n-2 , and so on. Go to the largest node in the left subtree .This means go to the left subtree and keep on going to the right until it becomes
[algogeeks] Re: zig zag
No , actually it's not ... it's O(n^2) , I misunderstood the subsequence thing , it could be discontinuous .. we , then need to find the maximum of dp[l] ... the second term makes sure that the sign of the two quantities is alternating i.e. positive or negative ! On Jan 29, 11:06 am, nishaanth nishaant...@gmail.com wrote: @above...can you please enlighten me about the second term in the dp expression And are you sure its O(n) ? On Fri, Jan 28, 2011 at 7:08 PM, sankalp srivastava richi.sankalp1...@gmail.com wrote: This can be done in O(n) very easily , similar to Longest increasing subsequence Solution :- dp[l]= maximum length of the zigzag sequence upto the length l //At any position , the particular number in the array can either extend the zigzag sequence containing the last element or it can start one of it's own . So the recurrance becomes dp[i]= max(dp[j]) ,and diff[A[p[j]]]^(A[i]-A[p[j]]31)!=0 , ji find out the maximum in this array , it will get you the answer . PS:- You can also check out the Topcoder tutorials . On Jan 27, 7:41 pm, bittu shashank7andr...@gmail.com wrote: well I found it as it Can be Done in O(n). but with additional space O(n) here program is written in Java public class ZigZag { public int longestZigZag(int[] sequence) { if (sequence.length==1) return 1; if (sequence.length==2) return 2; int[] diff = new int[sequence.length-1]; for (int i=1;isequence.length;i++) { diff[i-1]=sequence[i]-sequence[i-1]; } //90% Program is done here it self. by looking at the sign if alternative number in auxiliary array we can count longest zigzag array int sign=sign(diff[0]); int count=0; if (sign!=0) count=1; for (int i=1;idiff.length;i++) { int nextsign=sign(diff[i]); if (sign*nextsign==-1){ sign=nextsign; count++; } } return count+1; } public int sign(int a) { if (a==0) return 0; return a/Math.abs(a); } public static void main(String[] args) { ZigZag z = new ZigZag(); System.out.println(z.longestZigZag(new int[] { 1, 7, 4, 9, 2, 5 })); System.out.println(z.longestZigZag(new int[] { 1, 17, 5, 10, 13, 15, 10, 5, 16, 8 })); } } Try for Inplace Thanks Regards Shashank Mani The best way to escape from a problem is to solve it. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2Bunsubscribe@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Good Maths Question
Yuo might wanna check out The latest codeforces beta round problem C . On Jan 28, 8:34 pm, nishaanth nishaant...@gmail.com wrote: @All... According to the constraints(SPOJ problem) wont this dp solution time out ? On Tue, Jan 25, 2011 at 12:23 AM, sankalp srivastava richi.sankalp1...@gmail.com wrote: Correct me if I'm wrong dp[i][j]=how many numbers of length i with the last digit j(int base 10) dp[0][j]=0 dp[i][0]=dp[i-1][0] , last digit can't be zero otherwise the number has i-1 digits , not j; now the recursion to pass from one state to the next dp[i][j]=dp[i-1][k]+1(for each value of k such that k is less than j , from 0 to k) That is to say , the number of numbers with length i and last digit j , will be equal to the number of numbers with the last digit k , for each k less than j .One is added because , we must not have included the 0 in the last case , but we will include the zero case here . this one corresponds to zero case . Finally , the answer will be dp[n][j] , 1=j=9 , sum up all these and u have the answer For example for 2 digits dp[1][1-9]=1 , as nothing preceeds them and as said in the problem , one digit numbers are always increasing/decreasing . next dp[2][1]=dp[1][1](As only 1 is less than , equal to 1 , the last digit in this state) dp[2][2]=dp[1][1]+dp[1][2] =2( 1,2 and 2,2) Continuing this way , we will get the answer , may be 50 , though i din code it . similarly , for 3 digits Correct me if not! On Jan 25, 12:06 am, juver++ avpostni...@gmail.com wrote: dp[i][j] - how many numbers of length i and with the last digit j. Apply the scheme to increasing and decreasing number, then find ratio. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2Bunsubscribe@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Prime Numbers
Okay I got it myself @OP This can be done in O(n*k*logn) where k is of order 10^3 at the very max , when u need a prime like 1 trillion On Jan 28, 6:44 pm, sankalp srivastava richi.sankalp1...@gmail.com wrote: Correct me if I'm wrong , but according to you , will this be the approach ? boolean array[10]; int primes[100]; void seive() { int index=0; for(int i=2;i*i10;i++) { if(isprime[i]) { primes[index++]=i; for(int j=i*2;j100;j+=i) { isprimes[i]= false; } } } int kindex=index; } /* But now , how should I find out the 1 millionth prime number ? It requires another seive , i know , but it requires still bigger range */ Can you give me a pseudocode ? */ On Jan 26, 8:20 pm, juver++ avpostni...@gmail.com wrote: @above One million is 10^6. Problem wants 1 million of prime numbers. Not the prime numbers in range 1..1000. So, you should use two sieves. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Amazon Again
I'm sure you have misstated the problem statement just find out the total path length and return the first petrol pump which gives you the required milage go greedy On Jan 28, 5:09 pm, bittu shashank7andr...@gmail.com wrote: There are N petrol pumps along a circular path. Every petrol pump gives some amount of fixed petrol. Need not to be unique and in no particular order means it is random. We have a car and we need to find a petrol pump which can provide so much of petrol that we can take a full of the circle. Mileage of car is fixed. Distance between adjacent petrol pumps are given. Thanks Regards Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Google Question
We can do it Using a binary search approach (The cost function is monotonic over here , so we can use binary search) No. of As=A*(total number of keystrokes) , gives us a bound . We should have a lower bound as this , we can always get this much As Take the initial value as high and low as possible say left=1 and right=10^9 mid=left+right/2; if(can_get(this much As)) then , left=mid+1; else if(cannot get this much As) then , right=mid Continue this search until leftright .. This binary search gives the maximum value which you can get using the given combinations -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Using prefix sum to calculate maximum subarray in 2D
I am a rookie working with algorithms and especially implementing them. Im trying to implement the brute force method using the prefix sum of the NxN-array I got this piece of code, in which i want to return the sum of maximum subarray. prefix sum means that the array {{2, -1},{4, 19}} becomes {{2, 1},{6, 24}} // The prefix sum of the array is now stored in row tempmax=0; for(int i=0;in;i++) { for(int j=0;jn;j++) { for(int k=0;ki;k++) { for(int l=0;lj;l++) { /** Brute forcing all combinations of subarrays using the prefix sum array * and check if the sum is bigger than max */ tempmax=row[i][j]-row[i][l]-row[k][j]+row[k][l]; max = Math.max(tempmax, max); } } } } return max; } Please help me modify the code so max contains the correct value. I have used this paper as inpiration the above code should be the same as the one at page 11. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Using prefix sum to calculate maximum subarray in 2D
the paper: http://www.cosc.canterbury.ac.nz/research/reports/MastTheses/2007/mast_0705.pdf On Jan 29, 3:31 pm, AKO anders.konr...@gmail.com wrote: I am a rookie working with algorithms and especially implementing them. Im trying to implement the brute force method using the prefix sum of the NxN-array I got this piece of code, in which i want to return the sum of maximum subarray. prefix sum means that the array {{2, -1},{4, 19}} becomes {{2, 1},{6, 24}} // The prefix sum of the array is now stored in row tempmax=0; for(int i=0;in;i++) { for(int j=0;jn;j++) { for(int k=0;ki;k++) { for(int l=0;lj;l++) { /** Brute forcing all combinations of subarrays using the prefix sum array * and check if the sum is bigger than max */ tempmax=row[i][j]-row[i][l]-row[k][j]+row[k][l]; max = Math.max(tempmax, max); } } } } return max; } Please help me modify the code so max contains the correct value. I have used this paper as inpiration the above code should be the same as the one at page 11. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Frequently one of the Top Question Asked in Amazon
Convert BT in to DLL such that DLL represents the Sprial order traversal of BT. Inplace its Written Test Question They wants Exact Working Code...Not Approach..Be Clear..Try to provide best solutions Thanks Regards Shashank The best way to escape from a problem is to solve it. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Frequently one of the Top Question Asked in Amazon
@bittu offtopic: could you please tell us why do you use uppercase letters in 50% of the words?! -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Minimum positive-sum subarray
anyone here? On Fri, Jan 21, 2011 at 2:35 PM, snehal jain learner@gmail.com wrote: In this variation of the Maximum-Sum Subarray Problem, you are given a one-dimensional array A[1 : n] of positive or negative numbers, and you are asked to find a subarray A[i : j] such that the sum of its elements is (1) strictly greater than zero, and (2) minimum. In other words, you want to find a subarray of smallest positive sum. Give an O(nlog^2n) Divide and Conquer algorithm and a O(nlogn) Dynamic Programming Algorithm. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] CFP: The 2011 International Conference on Software Engineering Research and Practice (SERP'11), USA, July 18-21, 2011
CALL FOR PAPERS and Call For Workshop/Session Proposals SERP'11 The 2011 International Conference on Software Engineering Research and Practice Date and Location: July 18-21, 2011, USA http://www.world-academy-of-science.org/ Location: See the above web site for venue/city You are invited to submit a full paper for consideration. All accepted papers will be published in the SERP conference proceedings (in printed book form; later, the proceedings will also be accessible online). Those interested in proposing workshops/sessions, should refer to the relevant sections that appear below. SCOPE: Topics of interest include, but are not limited to, the following: O Software architectures O Software design and design patterns O Architectural analysis, verifications and validation methods O Quality oriented software architecture (design and Support) O Software reliability, safety critical systems and security methods O Software reuse and component engineering O UML/MDA and AADL O Object oriented technology (design and analysis) O Software metrics O Reverse and architectural recovery methods O Domain specific software engineering O Aerospace software and system engineering O Software engineering methodologies O Survivable systems O Engineering of safety/mission critical systems O Software testing, evaluation and analysis technologies O Workflow - Computer Supported Cooperative Work (CSCW) O Project management issues O Distributed and parallel systems O Legal issues and standards O Automated software design O Real-time embedded software engineering O Automated software design and synthesis O Software security engineering O Theoretic approaches (formal methods, graph, ...) O Software, domain modeling and meta-modeling O Model driven engineering O Software maintenance O Reflection and metadata methodologies O AI approaches to software engineering O Component based software engineering O Software engineering standards and guidelines O Reports on intelligent CASE tools and eclipse plugins issues O Multimedia in software engineering O Usability engineering O Novel software tools and environments O Pervasive software engineering O Requirement engineering and processes O Critical and embedded software design O Service oriented software architecture O Software cost estimation O Web engineering and web-based applications O Human computer interaction and usability engineering O Model based software engineering O Aspect oriented software engineering O Agent oriented software engineering O Programming languages and compilers O Education and law O Case studies and emerging technologies USEFUL WEB LINKS: To see the DBLP list of accepted papers of SERP 2009, go to: http://www.informatik.uni-trier.de/~ley/db/conf/serp/serp2009.html The DBLP list of accepted papers of SERP 2010 will soon appear at: http://www.informatik.uni-trier.de/~ley/db/conf/serp/serp2010.html SERP 2011 URL: http://www.world-academy-of-science.org/worldcomp11/ws/conferences/serp11 IMPORTANT DATES: March 10, 2011: Submission of papers (about 5 to 7 pages) April 03, 2011: Notification of acceptance (+/- two days) April 24, 2011: Final papers + Copyright/Consent + Registration July 18-21, 2011: The 2011 International Conference on Software Engineering Research and Practice (SERP'11) ACADEMIC CO-SPONSORS: Currently being prepared - The Academic sponsors of the last offering of SERP (2010) included research labs and centers affiliated with (a partial list): University of California, Berkeley; University of Southern California; University of Texas at Austin; Harvard University, Cambridge, Massachusetts; Georgia Institute of Technology, Georgia; Emory University, Georgia; University of Minnesota; University of Iowa; University of North Dakota; NDSU-CIIT Green Computing Comm. Lab.; University of Siegen, Germany; UMIT, Austria; SECLAB (University of Naples Federico II + University of Naples Parthenope + Second University of Naples, Italy); National Institute for Health Research; World Academy of Biomedical Sciences and Technologies; Russian Academy of Sciences, Russia; International Society of Intelligent Biological Medicine (ISIBM); The International Council on Medical and Care Compunetics; Eastern Virginia Medical School the American College of Surgeons, USA. SUBMISSION OF PAPERS: Prospective authors are invited to submit their papers by uploading them to the evaluation web site at: http://world-comp.org Submissions must be uploaded by March 10, 2011 and they must be in either MS doc (but not docx) or pdf formats (about 5 to 7 pages - single space, font size of 10 to 12). All reasonable typesetting formats are acceptable (later, the authors of accepted papers will be asked to follow a particular typesetting
[algogeeks] Re: Google Question
@ Sankalp : plz explain this line of yours : No. of As=A*(total number of keystrokes) , gives us a bound . We should have a lower bound as this , we can always get this much As On Jan 29, 5:32 pm, sankalp srivastava richi.sankalp1...@gmail.com wrote: We can do it Using a binary search approach (The cost function is monotonic over here , so we can use binary search) No. of As=A*(total number of keystrokes) , gives us a bound . We should have a lower bound as this , we can always get this much As Take the initial value as high and low as possible say left=1 and right=10^9 mid=left+right/2; if(can_get(this much As)) then , left=mid+1; else if(cannot get this much As) then , right=mid Continue this search until leftright .. This binary search gives the maximum value which you can get using the given combinations -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Minimum positive-sum subarray
On Jan 21, 1:05 am, snehal jain learner@gmail.com wrote: In this variation of the Maximum-Sum Subarray Problem, you are given a one-dimensional array A[1 : n] of positive or negative numbers, and you are asked to find a subarray A[i : j] such that the sum of its elements is (1) strictly greater than zero, and (2) minimum. In other words, you want to find a subarray of smallest positive sum. Give an O(nlog^2n) Divide and Conquer algorithm and a O(nlogn) Dynamic Programming Algorithm. There are three considerations here: 1) Insufficient clarity in the problem statement. 2) Most people don't want to do others homework/school problems for them. 3) At very least... you need to show that you are attempting to answer the problem yourself at least a little bit. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Frequently one of the Top Question Asked in Amazon
what do you mean by spiral order ? On Sat, Jan 29, 2011 at 8:25 PM, bittu shashank7andr...@gmail.com wrote: Convert BT in to DLL such that DLL represents the Sprial order traversal of BT. Inplace its Written Test Question They wants Exact Working Code...Not Approach..Be Clear..Try to provide best solutions Thanks Regards Shashank The best way to escape from a problem is to solve it. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Amazon Again
Starting with any pump A, try to finish the circle, if at pump B that can not reach pump B+1, it means all pumps from A to B can not finish the circle (it will go broke at pump B), then just start with B+1. After go through all the pumps start from some pump, we got an answer. if we go back to pump A and later, still can not find an answer, there is no answer. On Sat, Jan 29, 2011 at 4:38 AM, sankalp srivastava richi.sankalp1...@gmail.com wrote: I'm sure you have misstated the problem statement just find out the total path length and return the first petrol pump which gives you the required milage go greedy On Jan 28, 5:09 pm, bittu shashank7andr...@gmail.com wrote: There are N petrol pumps along a circular path. Every petrol pump gives some amount of fixed petrol. Need not to be unique and in no particular order means it is random. We have a car and we need to find a petrol pump which can provide so much of petrol that we can take a full of the circle. Mileage of car is fixed. Distance between adjacent petrol pumps are given. Thanks Regards Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Amazon Again
can you prove it? On Jan 29, 2011 6:38 PM, Wei.QI qiw...@gmail.com wrote: Starting with any pump A, try to finish the circle, if at pump B that can not reach pump B+1, it means all pumps from A to B can not finish the circle (it will go broke at pump B), then just start with B+1. After go through all the pumps start from some pump, we got an answer. if we go back to pump A and later, still can not find an answer, there is no answer. On Sat, Jan 29, 2011 at 4:38 AM, sankalp srivastava richi.sankalp1...@gmail.com wrote: I'm sure you have misstated the problem statement just find out the total path length and return the first petrol pump which gives you the required milage go greedy On Jan 28, 5:09 pm, bittu shashank7andr...@gmail.com wrote: There are N petrol pumps along a circular path. Every petrol pump gives some amount of fixed petrol. Need not to be unique and in no particular order means it is random. We have a car and we need to find a petrol pump which can provide so much of petrol that we can take a full of the circle. Mileage of car is fixed. Distance between adjacent petrol pumps are given. Thanks Regards Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Amazon Again
@Wei.Qi Can you clarify when your algorithm terminates and also what is the running time of the algorithm ? On Sun, Jan 30, 2011 at 9:46 AM, yq Zhang zhangyunq...@gmail.com wrote: can you prove it? On Jan 29, 2011 6:38 PM, Wei.QI qiw...@gmail.com wrote: Starting with any pump A, try to finish the circle, if at pump B that can not reach pump B+1, it means all pumps from A to B can not finish the circle (it will go broke at pump B), then just start with B+1. After go through all the pumps start from some pump, we got an answer. if we go back to pump A and later, still can not find an answer, there is no answer. On Sat, Jan 29, 2011 at 4:38 AM, sankalp srivastava richi.sankalp1...@gmail.com wrote: I'm sure you have misstated the problem statement just find out the total path length and return the first petrol pump which gives you the required milage go greedy On Jan 28, 5:09 pm, bittu shashank7andr...@gmail.com wrote: There are N petrol pumps along a circular path. Every petrol pump gives some amount of fixed petrol. Need not to be unique and in no particular order means it is random. We have a car and we need to find a petrol pump which can provide so much of petrol that we can take a full of the circle. Mileage of car is fixed. Distance between adjacent petrol pumps are given. Thanks Regards Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Minimum positive-sum subarray
@snehalno its incorrect..consider the following example -2 3 The answer to this problem is the entire array with sum 1.(not the min of positive number) On Sun, Jan 30, 2011 at 11:00 AM, snehal jain learner@gmail.com wrote: a friend of mine was asked this question in google interview.. according to me the min element in the array is the answer provided that its not zero.. as 1 element can also be a subarray. but that would solve the problem in O(n) only.. ( this is what i understood) am i missing anything..? please help.. On Sun, Jan 30, 2011 at 5:19 AM, Dan dant...@aol.com wrote: On Jan 21, 1:05 am, snehal jain learner@gmail.com wrote: In this variation of the Maximum-Sum Subarray Problem, you are given a one-dimensional array A[1 : n] of positive or negative numbers, and you are asked to find a subarray A[i : j] such that the sum of its elements is (1) strictly greater than zero, and (2) minimum. In other words, you want to find a subarray of smallest positive sum. Give an O(nlog^2n) Divide and Conquer algorithm and a O(nlogn) Dynamic Programming Algorithm. There are three considerations here: 1) Insufficient clarity in the problem statement. 2) Most people don't want to do others homework/school problems for them. 3) At very least... you need to show that you are attempting to answer the problem yourself at least a little bit. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Divide the array into groups
my approach sort in nlogn and then while traversing the array put the elements in a group till they are consecutive . when a[i+1]!=a[i]+1 then put a[i+1] in different group.. now we need to rearrange elements in the group so that they are according to the given array.. but that will make it O(n^2) .. anyone with better ideas? On Fri, Jan 21, 2011 at 1:20 PM, snehal jain learner@gmail.com wrote: Divide a list of numbers into groups of consecutive numbers but their original order should be preserved. Example: 8,2,4,7,1,0,3,6 Two groups: 2,4,1,0,3 8,7,6 Better than O(n^2) is expected. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Divide the array into groups
@snehal..i guess you are missing something in the question...divide it into 2 groups such that (there should be some other condition or criterion). On Sun, Jan 30, 2011 at 11:29 AM, snehal jain learner@gmail.com wrote: my approach sort in nlogn and then while traversing the array put the elements in a group till they are consecutive . when a[i+1]!=a[i]+1 then put a[i+1] in different group.. now we need to rearrange elements in the group so that they are according to the given array.. but that will make it O(n^2) .. anyone with better ideas? On Fri, Jan 21, 2011 at 1:20 PM, snehal jain learner@gmail.comwrote: Divide a list of numbers into groups of consecutive numbers but their original order should be preserved. Example: 8,2,4,7,1,0,3,6 Two groups: 2,4,1,0,3 8,7,6 Better than O(n^2) is expected. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Divide the array into groups
@nishanth divide into groups ( not necessarily 2) in as many group as possible.. such that elements in each group is consecutive another example to clearify A= { 9,7, 13, 11,6,12,8,10,3, 4, 2, 16,14,17,13,15) ans 9,7,13,11,6,12,8,10 3,4,2 16,14,17,13,15 On Sun, Jan 30, 2011 at 11:32 AM, nishaanth nishaant...@gmail.com wrote: @snehal..i guess you are missing something in the question...divide it into 2 groups such that (there should be some other condition or criterion). On Sun, Jan 30, 2011 at 11:29 AM, snehal jain learner@gmail.comwrote: my approach sort in nlogn and then while traversing the array put the elements in a group till they are consecutive . when a[i+1]!=a[i]+1 then put a[i+1] in different group.. now we need to rearrange elements in the group so that they are according to the given array.. but that will make it O(n^2) .. anyone with better ideas? On Fri, Jan 21, 2011 at 1:20 PM, snehal jain learner@gmail.comwrote: Divide a list of numbers into groups of consecutive numbers but their original order should be preserved. Example: 8,2,4,7,1,0,3,6 Two groups: 2,4,1,0,3 8,7,6 Better than O(n^2) is expected. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Minimum positive-sum subarray
@nishanth oh ya right.. On Sun, Jan 30, 2011 at 11:27 AM, nishaanth nishaant...@gmail.com wrote: @snehalno its incorrect..consider the following example -2 3 The answer to this problem is the entire array with sum 1.(not the min of positive number) On Sun, Jan 30, 2011 at 11:00 AM, snehal jain learner@gmail.comwrote: a friend of mine was asked this question in google interview.. according to me the min element in the array is the answer provided that its not zero.. as 1 element can also be a subarray. but that would solve the problem in O(n) only.. ( this is what i understood) am i missing anything..? please help.. On Sun, Jan 30, 2011 at 5:19 AM, Dan dant...@aol.com wrote: On Jan 21, 1:05 am, snehal jain learner@gmail.com wrote: In this variation of the Maximum-Sum Subarray Problem, you are given a one-dimensional array A[1 : n] of positive or negative numbers, and you are asked to find a subarray A[i : j] such that the sum of its elements is (1) strictly greater than zero, and (2) minimum. In other words, you want to find a subarray of smallest positive sum. Give an O(nlog^2n) Divide and Conquer algorithm and a O(nlogn) Dynamic Programming Algorithm. There are three considerations here: 1) Insufficient clarity in the problem statement. 2) Most people don't want to do others homework/school problems for them. 3) At very least... you need to show that you are attempting to answer the problem yourself at least a little bit. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Divide the array into groups
so whats the required outputlist all possiblities or anything else? if its just this one output...then it sounds trivial On Sun, Jan 30, 2011 at 11:43 AM, snehal jain learner@gmail.com wrote: @nishanth divide into groups ( not necessarily 2) in as many group as possible.. such that elements in each group is consecutive another example to clearify A= { 9,7, 13, 11,6,12,8,10,3, 4, 2, 16,14,17,13,15) ans 9,7,13,11,6,12,8,10 3,4,2 16,14,17,13,15 On Sun, Jan 30, 2011 at 11:32 AM, nishaanth nishaant...@gmail.com wrote: @snehal..i guess you are missing something in the question...divide it into 2 groups such that (there should be some other condition or criterion). On Sun, Jan 30, 2011 at 11:29 AM, snehal jain learner@gmail.comwrote: my approach sort in nlogn and then while traversing the array put the elements in a group till they are consecutive . when a[i+1]!=a[i]+1 then put a[i+1] in different group.. now we need to rearrange elements in the group so that they are according to the given array.. but that will make it O(n^2) .. anyone with better ideas? On Fri, Jan 21, 2011 at 1:20 PM, snehal jain learner@gmail.comwrote: Divide a list of numbers into groups of consecutive numbers but their original order should be preserved. Example: 8,2,4,7,1,0,3,6 Two groups: 2,4,1,0,3 8,7,6 Better than O(n^2) is expected. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Divide the array into groups
I don't see why you need O(n^2) time for rearranging. It can be done in O(n log n) if you maintain the index along with every element. Then reordering would mean sort as per the indices. -- Rohit Saraf Third Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.