Re: [algogeeks] os question
If virtualization is concerned, then answer would be choice d. Since its not necessary to load complete process in memory. On Sat, Dec 8, 2012 at 12:45 AM, sahil gupta sahilgupta...@gmail.comwrote: It's b. Windows follow this Operation. On Fri, Dec 7, 2012 at 4:21 AM, manish narayan.shiv...@gmail.com wrote: Four processes of 1gb,1.2gb,2gb,2gb are there and RAM available is 2gb. We have a time shared system. Which of the following is the most appropriate scheduling algorithm? a. all processes are loaded sequentially 1 by 1 b. load one process at a time and execute processes in RR fashion c. load 1gb, 1,2gb first then processes 3 and 4 follow d. All processes can be loaded together and CPU time shared among them -- -- --
Re: [algogeeks] Microsoft Interview Question
@rahul: I got my fault. I didn't thought about that test case. I am thinking about applying DFS traversal algorithm for graph here. It may work here. On Wed, Oct 17, 2012 at 9:01 AM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: @navin: still i am not getting your solution.. can you make more clear it pls.. here is my doubt.. take input matrix and one temp visited matrix which stores the visited path. eg: 1 1 0 0 0 1 1 0 0 0 0 1 1 1 0 0 1 1 1 0 0 0 1 1 1 Suppose i want to find the number of paths between M[4][2] - M[0][0] First i explore path M[4][2]-M[4][3]-M[3][3] and so on... your program set 1 on visited matrix... on corresponding V[i][j] entries next time i explore the path M[4][2]-M[3][2]-M[3][3]... but here we found that V[3][3]=1 so we can't take this in put path... but actually both are different paths.. how you will ensure this. because we are maintaining only one visited matrix. On Wed, Oct 17, 2012 at 7:54 AM, Navin Kumar algorithm.i...@gmail.comwrote: @Rahul: Loop won't occur because when you are visiting any matrix element then you are marking 1 in visited matrix. So second time it will be seen as a already visited element and it will choose another element (or path if exist) or will blocked. On Tue, Oct 16, 2012 at 9:31 AM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: @atul: in your solution object only can move down or right direction. but in my problem object is free to move in any direction and hence there are chances of cycle.. how to memoize cycle. if there is cycle then your approach will give infinite solution. consider this maze 1 1 0 0 0 1 1 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 1 1 1 you can see that object can take path M[0][0] - M[0][1] - M[1][1]- M[1][2]- M[][]- M[][] OR M[0][0] - M[1][0] - M[1][1]- M[1][2]- M[][]- M[][] But simple approach will also take path M[0][0] - M[0][1] - M[1][1]- M[1][0]- M[0][0]- M[0][1] -- CYCLE how you will avoid these cycles... On Tue, Oct 16, 2012 at 8:58 AM, atul anand atul.87fri...@gmail.comwrote: http://www.geeksforgeeks.org/archives/13376 On Tue, Oct 16, 2012 at 8:56 AM, atul anand atul.87fri...@gmail.comwrote: can be done simply by backtracking . On Sat, Oct 13, 2012 at 12:31 AM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: Pls help to solve this que.. does any one have DP solution for following que. http://www.geeksforgeeks.org/archives/24488 section 5/question 2 Write a program to find all the possible paths from a starting point to dest point in a maze(2-D array). ex: 1 0 1 0 1 1 1 1 0 1 0 1 0 0 1 1 If there is a block it’s represented by 0. If there is a path it’s represented by 1. -- Thanks and Regards: Rahul Kumar Patle M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com [image: Linkedin]http://www.linkedin.com/profile/view?id=106245716trk=tab_pro [image: Twitter] https://twitter.com/rahulkumarpatle https://www.facebook.com/rkpatle -- 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. -- 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. -- Thanks and Regards: Rahul Kumar Patle M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com [image: Linkedin]http://www.linkedin.com/profile/view?id=106245716trk=tab_pro [image: Twitter] https://twitter.com/rahulkumarpatle https://www.facebook.com/rkpatle -- 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. -- 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
Re: [algogeeks] Microsoft Interview Question
@Rahul: Loop won't occur because when you are visiting any matrix element then you are marking 1 in visited matrix. So second time it will be seen as a already visited element and it will choose another element (or path if exist) or will blocked. On Tue, Oct 16, 2012 at 9:31 AM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: @atul: in your solution object only can move down or right direction. but in my problem object is free to move in any direction and hence there are chances of cycle.. how to memoize cycle. if there is cycle then your approach will give infinite solution. consider this maze 1 1 0 0 0 1 1 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 1 1 1 you can see that object can take path M[0][0] - M[0][1] - M[1][1]- M[1][2]- M[][]- M[][] OR M[0][0] - M[1][0] - M[1][1]- M[1][2]- M[][]- M[][] But simple approach will also take path M[0][0] - M[0][1] - M[1][1]- M[1][0]- M[0][0]- M[0][1] -- CYCLE how you will avoid these cycles... On Tue, Oct 16, 2012 at 8:58 AM, atul anand atul.87fri...@gmail.comwrote: http://www.geeksforgeeks.org/archives/13376 On Tue, Oct 16, 2012 at 8:56 AM, atul anand atul.87fri...@gmail.comwrote: can be done simply by backtracking . On Sat, Oct 13, 2012 at 12:31 AM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: Pls help to solve this que.. does any one have DP solution for following que. http://www.geeksforgeeks.org/archives/24488 section 5/question 2 Write a program to find all the possible paths from a starting point to dest point in a maze(2-D array). ex:1 0 1 0 1 1 1 1 0 1 0 1 0 0 1 1 If there is a block it’s represented by 0. If there is a path it’s represented by 1. -- Thanks and Regards: Rahul Kumar Patle M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com [image: Linkedin]http://www.linkedin.com/profile/view?id=106245716trk=tab_pro [image: Twitter] https://twitter.com/rahulkumarpatle https://www.facebook.com/rkpatle -- 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. -- 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. -- Thanks and Regards: Rahul Kumar Patle M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com [image: Linkedin]http://www.linkedin.com/profile/view?id=106245716trk=tab_pro [image: Twitter] https://twitter.com/rahulkumarpatle https://www.facebook.com/rkpatle -- 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. -- 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] finding element in array with minimum of comparing
@atul: still it won't compare 0 th element. Slight modification in your code: n=*sizeof(arr)*; do { if(elem==arr[*--n*]) print found; }while(n); On Mon, Oct 1, 2012 at 9:50 AM, atul anand atul.87fri...@gmail.com wrote: yes, but there no need of checking outside the loop n=sizeof(arr)-1; do { if(elem==arr[n]) print found; n--; }while(n); On Mon, Oct 1, 2012 at 9:33 AM, Navin Kumar algorithm.i...@gmail.comwrote: @atul: keep one more checking outside loop for element at 0 th index. Because when n = 0 the your loop come out from the loop without comparing it. On Mon, Oct 1, 2012 at 8:55 AM, atul anand atul.87fri...@gmail.comwrote: n=sizeof(arr); n--; while(n) { if(elem=arr[n]) print found; n--; } On Sun, Sep 30, 2012 at 2:56 PM, רפי וינר rafiwie...@gmail.com wrote: Hi i was in an interview and was given a simple function int arrExsits(int* arr,int size,int elem){ for (int i=0;isize;++i) if(elem==arr[i]) return i; return -1; } this function does 2n compares n- the if statment n-check that i is smaller then size i was suppose to give an optimal (less compares) solution so i gave int arrExsits(int* arr,int size,int elem){ if (arr[size-1]==elem) return size-1; arr[size-1]=elem] for (int i=0;;++i) if(elem==arr[i]){ if (i!=size-1) return i; return -1; } this solution works and it has n+2 compares the first one another n and the second inner if. they told me it's good (and I've passed) but they told just for my knowledge that there is a better N compare solution. I've searched the web but couldn't find it. anybody knows? Thanks -- 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. -- 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. -- 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. -- 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. -- 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] finding element in array with minimum of comparing
@atul: keep one more checking outside loop for element at 0 th index. Because when n = 0 the your loop come out from the loop without comparing it. On Mon, Oct 1, 2012 at 8:55 AM, atul anand atul.87fri...@gmail.com wrote: n=sizeof(arr); n--; while(n) { if(elem=arr[n]) print found; n--; } On Sun, Sep 30, 2012 at 2:56 PM, רפי וינר rafiwie...@gmail.com wrote: Hi i was in an interview and was given a simple function int arrExsits(int* arr,int size,int elem){ for (int i=0;isize;++i) if(elem==arr[i]) return i; return -1; } this function does 2n compares n- the if statment n-check that i is smaller then size i was suppose to give an optimal (less compares) solution so i gave int arrExsits(int* arr,int size,int elem){ if (arr[size-1]==elem) return size-1; arr[size-1]=elem] for (int i=0;;++i) if(elem==arr[i]){ if (i!=size-1) return i; return -1; } this solution works and it has n+2 compares the first one another n and the second inner if. they told me it's good (and I've passed) but they told just for my knowledge that there is a better N compare solution. I've searched the web but couldn't find it. anybody knows? Thanks -- 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. -- 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. -- 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] longest palindrome in a string size 2*10^4
*Ukkonen's algorithm* is a linear-time, online algorithmhttp://en.wikipedia.org/wiki/Online_algorithmfor constructing suffix trees http://en.wikipedia.org/wiki/Suffix_tree, proposed by Esko Ukkonenhttp://en.wikipedia.org/w/index.php?title=Esko_Ukkonenaction=editredlink=1in 1995 source: wikipedia On Sun, Sep 23, 2012 at 5:08 PM, Navin Kumar algorithm.i...@gmail.comwrote: Build a common suffix tree for the given string and for its reverse. Then take out the string ending at maximum depth at a common node. Time complexity would be linear. On Sat, Sep 22, 2012 at 5:33 PM, Aditya Raman adityarareloa...@gmail.comwrote: Hello everybody, I need to find a way of finding the longest palindrome in a very very long string (n=2) . a linear time algo is expected. help me out -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/JdXOBU9fu34J. 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. -- 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] Adobe Written Test - 25 SEPT 2010
@Dave sir: Thanx for reply. your solution gives the exact multiple like 37 for 3, 8547 for 13. In the question i think we have to print the number which is 13x8547 which will be very large (out of integer range).In that case we have to store result in string. On Fri, Sep 21, 2012 at 12:09 PM, Dave dave_and_da...@juno.com wrote: @Navin: It means that given a positive integer n whose decimal representation ends in 3, find a multiple, m*n, which is written solely with the digit 1. E.g., 3: 37 * 3 = 111; 13: 8547 * 13 = 111,111. Dave On Thursday, September 20, 2012 11:56:08 PM UTC-5, Navin Kumar wrote: @all: Please explain question number 8. I am not getting the question exactly what it says ? On Fri, Sep 21, 2012 at 9:30 AM, Dave dave_an...@juno.com wrote: @Bharat: Simulate long division, dividing a number ...1 by the number. You can do this one digit at a time, printing the quotient digit by digit until you bring down a zero. It could look something like this: int n=the number that ends with 3; int divisor=1; while( divisor n ) divisor = 10 * divisor + 1; while( divisor != 0 ) { printf(%d,divisor / n); divisor = 10 * (divisor % n) + 1; } printf(\n); Dave On Thursday, September 20, 2012 9:45:55 PM UTC-5, bharat wrote: what is the solution(not brute force) for 8th question ? On Fri, Sep 14, 2012 at 5:19 PM, Bhupendra Dubey bhupen...@gmail.comwrote: Which edition of barron? On Wed, Sep 28, 2011 at 6:05 PM, VIHARRI vihar...@gmail.com wrote: 1. Java uses stack for byte code in JVM - each instruction is of one byte, so how many such instructions are possible in an operating system. 2. Three processes p1, p2, p3, p4 - each have sizes 1GB, 1.2GB, 2GB, 1GB. And each processes is executed as a time sharing fashion. Will they be executed on an operating system. 3. write a recursive program for reversing the linked list. 4. write a program for checking the given number is a palindrome. ( dont use string / array for converting number ). 5. write a recursive program for multiplying two numbers a and b, with additions. The program should take care of doing min # additions as that of which ever number is lower between a and b. 6. There are two sets A and B with n integers, write a program to check the whether there exists two numbers a in A and b in B such that a+b = val ( val is given ); 7. write a program to return the row number which has max no of one's in an array of NxN matrix where all 1's occur before any 0's starts. 8. For every number that has 3 in its units place has one multiple which has all one's i.e. 111 is such multiple and 13 has a multiple 11. Write a program to find such multiple for any number that has 3 at its units place. 9. what are the maximum no of edges that can be connected in a graph of n vertices and 0 edges such that after adding edges given graph is still disconnected. 10. One Question on critical section. For Analytical Test - Prepare the Questions in the barrons book of sample paper - 2 ( they have give two passages ) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algo...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+...@** googlegroups.com**. For more options, visit this group at http://groups.google.com/** group**/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en . -- Thanks regards Bhupendra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algo...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+...@** googlegroups.com**. For more options, visit this group at http://groups.google.com/**group **/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/** msg/algogeeks/-/pDBPxDR3R1oJhttps://groups.google.com/d/msg/algogeeks/-/pDBPxDR3R1oJ . To post to this group, send email to algo...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+...@** googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/LpHDrQKDb90J. 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. -- You received this message because you are subscribed
Re: [algogeeks] Adobe Written Test - 25 SEPT 2010
@all: Please explain question number 8. I am not getting the question exactly what it says ? On Fri, Sep 21, 2012 at 9:30 AM, Dave dave_and_da...@juno.com wrote: @Bharat: Simulate long division, dividing a number ...1 by the number. You can do this one digit at a time, printing the quotient digit by digit until you bring down a zero. It could look something like this: int n=the number that ends with 3; int divisor=1; while( divisor n ) divisor = 10 * divisor + 1; while( divisor != 0 ) { printf(%d,divisor / n); divisor = 10 * (divisor % n) + 1; } printf(\n); Dave On Thursday, September 20, 2012 9:45:55 PM UTC-5, bharat wrote: what is the solution(not brute force) for 8th question ? On Fri, Sep 14, 2012 at 5:19 PM, Bhupendra Dubey bhupen...@gmail.comwrote: Which edition of barron? On Wed, Sep 28, 2011 at 6:05 PM, VIHARRI vihar...@gmail.com wrote: 1. Java uses stack for byte code in JVM - each instruction is of one byte, so how many such instructions are possible in an operating system. 2. Three processes p1, p2, p3, p4 - each have sizes 1GB, 1.2GB, 2GB, 1GB. And each processes is executed as a time sharing fashion. Will they be executed on an operating system. 3. write a recursive program for reversing the linked list. 4. write a program for checking the given number is a palindrome. ( dont use string / array for converting number ). 5. write a recursive program for multiplying two numbers a and b, with additions. The program should take care of doing min # additions as that of which ever number is lower between a and b. 6. There are two sets A and B with n integers, write a program to check the whether there exists two numbers a in A and b in B such that a+b = val ( val is given ); 7. write a program to return the row number which has max no of one's in an array of NxN matrix where all 1's occur before any 0's starts. 8. For every number that has 3 in its units place has one multiple which has all one's i.e. 111 is such multiple and 13 has a multiple 11. Write a program to find such multiple for any number that has 3 at its units place. 9. what are the maximum no of edges that can be connected in a graph of n vertices and 0 edges such that after adding edges given graph is still disconnected. 10. One Question on critical section. For Analytical Test - Prepare the Questions in the barrons book of sample paper - 2 ( they have give two passages ) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algo...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+...@** googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en. -- Thanks regards Bhupendra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algo...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+...@** googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/pDBPxDR3R1oJ. 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. -- 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] Data Structure
Which data structure is used to maintain browser history? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/MCj-0bFwvV0J. 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] Data Structure
@atul: I think, its better to use date as a key instead of day. we may require history of last 6 month . As firefox do. On Tue, Sep 18, 2012 at 5:38 PM, atul anand atul.87fri...@gmail.com wrote: i guess even circular queue , make new queue for each date now add all urls to this queue say for monday for Tuesday create another queue ..and soo on now at the end of day you just add queue to the hastable with key = day (say monday ) and value=queue reference. you can do these till sunday , after sunday created new queue say last_week and append all queues created to the this new queue and add it to hastable. clear all previous monday to sunday queues. and start creating queue for new week. On Tue, Sep 18, 2012 at 1:20 PM, Navin Kumar algorithm.i...@gmail.comwrote: Which data structure is used to maintain browser history? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/MCj-0bFwvV0J. 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. -- 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. -- 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] Finding top 10 most frequent repeated word
@ashish: will you use HashMap or any other mapping technique? please throw some light on map? On Tue, Sep 11, 2012 at 11:09 AM, Ashish Goel ashg...@gmail.com wrote: map + heap for 10 most occurred words.. external sort for not sufficient memory if the words are dynamically added/deleted, the first map+heap should succeed. Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sat, Sep 8, 2012 at 8:06 PM, Kumar Vishal kumar...@gmail.com wrote: if it can be loaded we can use map , else look for external sorting coming to second point it dynamically changing leads lot of other questions before going give algo . On Sat, Sep 8, 2012 at 7:43 PM, Navin Kumar algorithm.i...@gmail.comwrote: Given a file which has billions of words and file can be loaded in memory. Now find 10 most frequent words in file. What if file is dynamically changing means words are continuously added to it. What if file cant be loaded in memory. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/UcdJKQHPGzoJ. 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. -- Regards Kumar Vishal _ *http://wethecommonpeople.wordpress.com/ * *h**ttp://kumartechnicalarticles.wordpress.com/http://kumartechnicalarticles.wordpress.com/ * _ -- 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. -- 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. -- 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] Finding top 10 most frequent repeated word
@ashish: what if there is not sufficient memory to build hashmap? On Tue, Sep 11, 2012 at 4:19 PM, bharat b bagana.bharatku...@gmail.comwrote: but in the question it says that billions of words .. I don't think using hashmap is good idea .. On Tue, Sep 11, 2012 at 2:34 PM, Ashish Goel ashg...@gmail.com wrote: hashmap for word to count mapping and a heap will have count and corresponding words (will get updated at run time) Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Sep 11, 2012 at 2:07 PM, Navin Kumar algorithm.i...@gmail.comwrote: @ashish: will you use HashMap or any other mapping technique? please throw some light on map? On Tue, Sep 11, 2012 at 11:09 AM, Ashish Goel ashg...@gmail.com wrote: map + heap for 10 most occurred words.. external sort for not sufficient memory if the words are dynamically added/deleted, the first map+heap should succeed. Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sat, Sep 8, 2012 at 8:06 PM, Kumar Vishal kumar...@gmail.comwrote: if it can be loaded we can use map , else look for external sorting coming to second point it dynamically changing leads lot of other questions before going give algo . On Sat, Sep 8, 2012 at 7:43 PM, Navin Kumar algorithm.i...@gmail.com wrote: Given a file which has billions of words and file can be loaded in memory. Now find 10 most frequent words in file. What if file is dynamically changing means words are continuously added to it. What if file cant be loaded in memory. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/UcdJKQHPGzoJ. 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. -- Regards Kumar Vishal _ *http://wethecommonpeople.wordpress.com/ * *h**ttp://kumartechnicalarticles.wordpress.com/http://kumartechnicalarticles.wordpress.com/ * _ -- 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. -- 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. -- 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. -- 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. -- 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. -- 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] Number of arrangements
@tendua: answer would be 6C3. Read about combination definition. On Thu, Sep 6, 2012 at 5:05 PM, atul anand atul.87fri...@gmail.com wrote: question says *3 alphabets with no data repeated* ...you no need of doing 3! permutation. eg 123 and 321 are same On Thu, Sep 6, 2012 at 4:35 PM, tendua bharat.kra...@gmail.com wrote: from the six elements, we could choose any three in C(6,3) ways which is 20 and then permute all the three elements so it will be multiplied by 3! which is 6. Hence, 20*6 = 120. We still have to multiply it by 3 to get 360 but I'm not getting why? On Thursday, September 6, 2012 3:54:11 PM UTC+5:30, atul007 wrote: seems output should be 20. On Thu, Sep 6, 2012 at 3:26 PM, tendua bharat...@gmail.com wrote: from the set {a,b,c,d,e,f} find number of arrangements for 3 alphabets with no data repeated? Answer given is 360. but how? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/** msg/algogeeks/-/E4U2XlfkvgMJhttps://groups.google.com/d/msg/algogeeks/-/E4U2XlfkvgMJ . To post to this group, send email to algo...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+...@** googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/VMO1othQRcQJ. 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. -- 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. -- 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] Number of arrangements
@tendua: Answer will be 6C3 x 3! . For example: If 5 letters are given then you can get only 10 combination of different letter = 5C3 ABC ABD ABE BCD BCE CDE ACD ACE ADE BDE now each of these can be arranged in 3! ways. So final answer will be : 120 On Fri, Sep 7, 2012 at 1:11 AM, tendua bharat.kra...@gmail.com wrote: http://placement.freshersworld.com/placement-papers/Persistent-/Placement-Paper-Whole-Testpaper-1884 question no. 4 in 5th section On Thursday, September 6, 2012 4:40:08 PM UTC+5:30, isandeep wrote: Can you send the link to the question. On Thu, Sep 6, 2012 at 4:35 PM, tendua bharat...@gmail.com wrote: from the six elements, we could choose any three in C(6,3) ways which is 20 and then permute all the three elements so it will be multiplied by 3! which is 6. Hence, 20*6 = 120. We still have to multiply it by 3 to get 360 but I'm not getting why? On Thursday, September 6, 2012 3:54:11 PM UTC+5:30, atul007 wrote: seems output should be 20. On Thu, Sep 6, 2012 at 3:26 PM, tendua bharat...@gmail.com wrote: from the set {a,b,c,d,e,f} find number of arrangements for 3 alphabets with no data repeated? Answer given is 360. but how? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/* *ms**g/algogeeks/-/E4U2XlfkvgMJhttps://groups.google.com/d/msg/algogeeks/-/E4U2XlfkvgMJ . To post to this group, send email to algo...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+...@** googlegroups.com**. For more options, visit this group at http://groups.google.com/**group **/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/** msg/algogeeks/-/VMO1othQRcQJhttps://groups.google.com/d/msg/algogeeks/-/VMO1othQRcQJ . To post to this group, send email to algo...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+...@** googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/z6KbH2i6BP0J. 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. -- 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] MICROSOFT:Given a BST and a number. Find two node in a BST whose sum is equal to given number in O(n) time and O(1) space.
@all: Now the problem is for getting O(n) time and O(1) space we have to run two inorder traversal simultaneously. How can we do it?? On Mon, Sep 3, 2012 at 9:31 PM, Karthikeyan V.B kartmu...@gmail.com wrote: @navin and @atul: inorder traversal without recursion and stack can be done using Morris traversal in O(1) space. Refer the following link for Morris traversal http://www.geeksforgeeks.org/archives/6358 now the problem takes O(n) time and O(1) space. -- 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. -- 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] MICROSOFT:Given a BST and a number. Find two node in a BST whose sum is equal to given number in O(n) time and O(1) space.
@all: If we are doing inorder traversal , it will automatically take O(n) space for internal stack. On Mon, Sep 3, 2012 at 5:17 PM, atul anand atul.87fri...@gmail.com wrote: @ashish : i.e in decreasing order inorder(root) if not null inorder(root-right); inorder(root-left); On Mon, Sep 3, 2012 at 4:35 PM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: @dave same doubt as @atul, how we can manage both function parallel and to all can we traverse a tree using some looping instead of traditional recursive methods..?? On Mon, Sep 3, 2012 at 1:13 PM, atul anand atul.87fri...@gmail.comwrote: @Dave : algo seems fine...but it seems to me that it would difficult to maintain both left to right and right to left parallel way :( :( . it would be gr8 if you can provided little bit of coded algorithm for it. On Mon, Sep 3, 2012 at 10:36 AM, Dave dave_and_da...@juno.com wrote: @Atul007: No need to destroy the BST. Perform two simultaneous inorder traversals of the BST, one from left to right (the usual direction) and one from right to left. At any stage you have selected two nodes. If the sum is less than the given number, advance the left-to-right traversal; If the sum is greater, advance the right-to-left traversal. Quit with success when the sum equals the given number or with failure when the two traversals have reached the same node. Dave On Sunday, September 2, 2012 11:00:42 PM UTC-5, atul007 wrote: convert BST to sorted DLL.. now it is a double linked list , so we can find 2 number in O(n) time by keeping 2 pointers(one at start and one at end) from sorted DLL. now convert DLL to BST. On Mon, Sep 3, 2012 at 1:32 AM, Navin Kumar algorit...@gmail.comwrote: MICROSOFT:Given a BST and a number. Find two node in a BST whose sum is equal to given number in O(n) time and O(1) space. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/oizd-5CSfuoJ. 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. -- 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. -- Thanks and Regards: Rahul Kumar Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com -- 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. -- 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. -- 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] Contiguous Sub sequence
Given an unsorted integer array. Find the contiguous sub sequences whose sum is 0. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/pFvfWQjVrnkJ. 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] Contiguous Sub sequence
Can you provide O(n) algo? On Sun, Sep 2, 2012 at 1:36 PM, Carl Barton odysseus.ulys...@gmail.comwrote: 1. Calculate the sum of every prefix of the array O(n) 2. Store as pairs (sum, index) and sort by sum using a stable sort. Observation: Sum of every factor can be expressed as the difference between the sum of 2 prefixes. 3. for each entry search for the corresponding difference such the index found is greater than original index. Works for any sum, not just 0. Takes O(n log n) On 2 September 2012 14:22, Navin Kumar algorithm.i...@gmail.com wrote: Given an unsorted integer array. Find the contiguous sub sequences whose sum is 0. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/pFvfWQjVrnkJ. 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. -- 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. -- 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] Contiguous Sub sequence
@pradip: Finding same element in temp array is little bit tricky. For displaying item from i+1 to j , you have to make sure that there is equal element at i and j index in temp array. How will you ensure it in O(n) time? On Sun, Sep 2, 2012 at 3:16 PM, Pradeep Mishra pradam.prad...@gmail.comwrote: This algorithm is *O(n)*. Given an int[] input array, you can create an int[] tmp array where tmp[i] = tmp[i - 1] + input[i]; Each element of tmp will store the sum of the input up to that element. Now if you check tmp, you'll notice that there might be values that are equal to each other. Let's say that this values are at indexes j an k with j k, then the sum of the input till j is equal to the sum tillk and this means that the sum of the portion of the array between j and k is 0! Specifically the 0 sum subarray will be from index j + 1 to k. - NOTE: if j + 1 == k, then k is 0 and that's it! ;) - NOTE: The algorithm should consider a virtual tmp[-1] = 0; Correct me if i am wrong Thanx -- Pradeep Kumar Mishra IIIT Allahabad B. Tech 3rd Year ( IT ) Another Mail - prad...@gmail.com -- 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. -- 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] Microsoft written test question
void correctBST(struct node *root) { int flag =0; static struct node *temp1, *temp2, *temp3, *prev; static int found; if(found) return; if(root) { correctBST(root-left); if(!temp1 prev root-data prev-data) { temp1 = prev; temp2 = root; swap((temp1-data), (temp2-data)); flag = 1; prev = temp1; } else if(!temp3 prev root-data prev-data) { temp3 = root; swap((temp1-data), (temp2-data)); swap((temp1-data), (temp3-data)); found = 1; return; } if(!flag) prev = root; correctBST(root-right); } } On Sun, Sep 2, 2012 at 4:02 PM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: help to solve the following.. Question: Two of the nodes of a BST are swapped. Correct the BST (taken from GeekforGeeks http://www.geeksforgeeks.org/archives/23272 2nd online test 3rd question) -- Thanks and Regards: Rahul Kumar Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com -- 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. -- 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] Contiguous Sub sequence
@atul : suppose if all element of input array is zero then i think hashing will also produce n^2 output. so worst case time complexity would be O(n^2). On Sun, Sep 2, 2012 at 9:18 PM, Carl Barton odysseus.ulys...@gmail.comwrote: No you're correct. I was doubting it would work :P For hashing you would need perfect hashing to ensure O(n) wouldn't you? On 2 September 2012 23:21, atul anand atul.87fri...@gmail.com wrote: @carl : if it would work only for entirely positive integers , then i aux[] array created will never contain 0 or repeated elements... correct me if i am wrong... On 9/2/12, atul anand atul.87fri...@gmail.com wrote: @navin : hashMap can be used to do it in O(n) time. On 9/2/12, Carl Barton odysseus.ulys...@gmail.com wrote: Your approach sounds like the optimal (and linear) algorithm for the submass finding problem. But if I recall correctly that only works in linear time if the input is entirely positive integers? Maybe I'm being stupid but wont checking that array be quadratic? On 2 September 2012 20:02, Navin Kumar algorithm.i...@gmail.com wrote: @pradip: Finding same element in temp array is little bit tricky. For displaying item from i+1 to j , you have to make sure that there is equal element at i and j index in temp array. How will you ensure it in O(n) time? On Sun, Sep 2, 2012 at 3:16 PM, Pradeep Mishra pradam.prad...@gmail.comwrote: This algorithm is *O(n)*. Given an int[] input array, you can create an int[] tmp array where tmp[i] = tmp[i - 1] + input[i]; Each element of tmp will store the sum of the input up to that element. Now if you check tmp, you'll notice that there might be values that are equal to each other. Let's say that this values are at indexes j an k with j k, then the sum of the input till j is equal to the sum tillk and this means that the sum of the portion of the array between j and k is 0! Specifically the 0 sum subarray will be from index j + 1 to k. - NOTE: if j + 1 == k, then k is 0 and that's it! ;) - NOTE: The algorithm should consider a virtual tmp[-1] = 0; Correct me if i am wrong Thanx -- Pradeep Kumar Mishra IIIT Allahabad B. Tech 3rd Year ( IT ) Another Mail - prad...@gmail.com -- 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. -- 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. -- 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. -- 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. -- 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. -- 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] Contiguous Sub sequence
@atul: what if n-1 contiguous 0's are there?? Can't we have some mechanism in hash such that it will avoid O(n^2) ?? On Mon, Sep 3, 2012 at 12:29 AM, atul anand atul.87fri...@gmail.com wrote: @navin : this case can be avoided by checking input array first , if it contain all zero or notwhich will be O(n). On 9/2/12, Navin Kumar algorithm.i...@gmail.com wrote: @atul : suppose if all element of input array is zero then i think hashing will also produce n^2 output. so worst case time complexity would be O(n^2). On Sun, Sep 2, 2012 at 9:18 PM, Carl Barton odysseus.ulys...@gmail.comwrote: No you're correct. I was doubting it would work :P For hashing you would need perfect hashing to ensure O(n) wouldn't you? On 2 September 2012 23:21, atul anand atul.87fri...@gmail.com wrote: @carl : if it would work only for entirely positive integers , then i aux[] array created will never contain 0 or repeated elements... correct me if i am wrong... On 9/2/12, atul anand atul.87fri...@gmail.com wrote: @navin : hashMap can be used to do it in O(n) time. On 9/2/12, Carl Barton odysseus.ulys...@gmail.com wrote: Your approach sounds like the optimal (and linear) algorithm for the submass finding problem. But if I recall correctly that only works in linear time if the input is entirely positive integers? Maybe I'm being stupid but wont checking that array be quadratic? On 2 September 2012 20:02, Navin Kumar algorithm.i...@gmail.com wrote: @pradip: Finding same element in temp array is little bit tricky. For displaying item from i+1 to j , you have to make sure that there is equal element at i and j index in temp array. How will you ensure it in O(n) time? On Sun, Sep 2, 2012 at 3:16 PM, Pradeep Mishra pradam.prad...@gmail.comwrote: This algorithm is *O(n)*. Given an int[] input array, you can create an int[] tmp array where tmp[i] = tmp[i - 1] + input[i]; Each element of tmp will store the sum of the input up to that element. Now if you check tmp, you'll notice that there might be values that are equal to each other. Let's say that this values are at indexes j an k with j k, then the sum of the input till j is equal to the sum tillk and this means that the sum of the portion of the array between j and k is 0! Specifically the 0 sum subarray will be from index j + 1 to k. - NOTE: if j + 1 == k, then k is 0 and that's it! ;) - NOTE: The algorithm should consider a virtual tmp[-1] = 0; Correct me if i am wrong Thanx -- Pradeep Kumar Mishra IIIT Allahabad B. Tech 3rd Year ( IT ) Another Mail - prad...@gmail.com -- 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. -- 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. -- 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. -- 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. -- 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. -- 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. -- You received this message because you
[algogeeks] MICROSOFT:Given a BST and a number. Find two node in a BST whose sum is equal to given number in O(n) time and O(1) space.
-- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/aLuPUOKxmaoJ. 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] TRIE problem
@atul: Given a word and a dictionary find all the anagrams of that word in that dictionary. For efficient access i am storing each word in TRIE with their sorted key. Ex: BAT will be inserted with key ABT. By this we will form TRIE of all words.For all the words whose sorted version are same , they will reside at same node.For storing more than one word i am using linked list. Now for finding anagram of a given word i will just traverse with their corresponding sorted word and will display all the word at that node. Complexity: Each word insertion will take O(m),( sorting can be done in O(m)). If n words are in dictionary then total complexity will be:O(mn). This is the time complexity of building TRIE. Cost of displaying anagram of a word: O(m + d) where d = total output word . Comparison with HASH: With this above approach we are saving time w.r.t. calculating hash key and resolving collision time. Also writing a good hash function is also a challenge. On Sat, Sep 1, 2012 at 6:12 PM, atul anand atul.87fri...@gmail.com wrote: yes but i would like to knw for which application you need this ? On 8/31/12, Carl Barton odysseus.ulys...@gmail.com wrote: There's no reason why a trie or a tree node couldn't be used to 'represent' more than one word. Although you'd take a penalty in the complexity for searching etc. On 31 August 2012 15:33, Navin Kumar algorithm.i...@gmail.com wrote: Can we store multiple words in single TRIE node by using linked list or some other data structure. Based on the some property a node in TRIE will hold all the word with same property. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/tvqq-_HUZ8sJ. 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. -- 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. -- 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. -- 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] TRIE problem
Can we store multiple words in single TRIE node by using linked list or some other data structure. Based on the some property a node in TRIE will hold all the word with same property. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/tvqq-_HUZ8sJ. 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: give the algo or program to find second largest element in a list using tournament method
@sangeeta: n-1 comparison required to choose winner. By tournament approach winner has played match with logn team and winner must have beaten second largest element. So among logn number we can select maximum in logn - 1 comparison. So total comparison required is: n + logn -2 On Thu, Aug 30, 2012 at 10:23 PM, sangeeta goyal sangeeta15...@gmail.comwrote: @Don can you give the algorithm for the same?? how would you implement it?? On Thu, Aug 30, 2012 at 10:03 PM, Don dondod...@gmail.com wrote: The second largest element is the largest element beaten by the winner. So if you implement a tournament in which each element keeps track of the largest element it has beaten, you'll get the second largest naturally. Don On Aug 29, 9:15 am, Sangeeta sangeeta15...@gmail.com wrote: give the algo or program to find second largest element in a list using tournament method -- 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. -- 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. -- 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] Amazon Q
Q1 Solution: . we can use doubly linked list with hash to implement all the operation in O(1). By keeping track of head and tail pointer we can do enqueue and dequeue in O(1) time. In hash we will keep track of each element present in linked list(queue). With node value as a hash key and address of node as a value. So for searching we can do it in O(1). For deleting an element we will directly take address of that value from hash and delete it. O(1) time. Q2. /*my code will return NULL if not palindrome and head if it is palindrome */ count = totalnode/2; //odd = 0 if totalnode is even else 1 struct node *checkPalindrome(struct node *head, int count) { struct node *temp; if(count == 0) { if(odd head-next) return head-next; else return head; } if(count 0) temp = checkPalindrome(head-next, count - 1); if(temp (temp-data == head-data ) !temp-next) return head; else if (temp (temp-data == head-data )) return temp-next; else return NULL; } On Sun, Aug 26, 2012 at 12:41 AM, Ashish Goel ashg...@gmail.com wrote: Q1. Design a data structure for the following operations: I.Enqueue II. Dequeue III. Delete a given number(if it is present in the queue, else do nothing) IV. isNumberPresent All these operations should take O(1) time. Q2. Check if a linked list (each char is a node) is palindrome, recursively. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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. -- 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] MS QUESTION
Reversing a linked list if loop exists: 1. Find the node from which loop start by any loop finding algorithm in linked list and keep the position of that node. 2. Unroll the loop i.e. set the last node's(last unrepeating node) next pointer to NULL. 3. Reverse this singly linked list. 4. Change the last node's next pointer to the node corresponding to the position we found in step1. On Thu, Aug 23, 2012 at 8:02 PM, sulekha metta metta.sule...@gmail.comwrote: Hi all, This was asked in microsoft, question is write a program to reverse a linked list.and write it's test cases. i got very few test cases 1) check if the node is null 2) check if there is only one node 3) check if there is any loop in the linked list. can any one tell how to reverse a linked list if loop exits? is it possible? and can any one add few more test cases?? -- Regards sulekha metta B.E computer science osmania university -- 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. -- 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] MS QUESTION
Few more Test cases : Check for 10 node. Check for 1 million node Check for even number of nodes Check for odd number of nodes... etc etc... On Fri, Aug 24, 2012 at 6:25 PM, Navin Kumar algorithm.i...@gmail.comwrote: Reversing a linked list if loop exists: 1. Find the node from which loop start by any loop finding algorithm in linked list and keep the position of that node. 2. Unroll the loop i.e. set the last node's(last unrepeating node) next pointer to NULL. 3. Reverse this singly linked list. 4. Change the last node's next pointer to the node corresponding to the position we found in step1. On Thu, Aug 23, 2012 at 8:02 PM, sulekha metta metta.sule...@gmail.comwrote: Hi all, This was asked in microsoft, question is write a program to reverse a linked list.and write it's test cases. i got very few test cases 1) check if the node is null 2) check if there is only one node 3) check if there is any loop in the linked list. can any one tell how to reverse a linked list if loop exits? is it possible? and can any one add few more test cases?? -- Regards sulekha metta B.E computer science osmania university -- 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. -- 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] MS interview
Anagram problem solution using TRIE.. For each word in dictionary we will put it in TRIE as.. 1. First sort the word 2. Search in trie using sorted word. If search found then we will add the original word in that TRIE node. 3. If node node not found then using simple TRIE insertion insert sorted word with original value stored at last node. For example: CAT sort it = ACT Search in trie with ACT : if node found then add CAT in that node. If not found then create node with search key ACT store value CAT. Time complexity for listing all anagram : For a given word sort it in O(L) and go to the node by traversing with sorted word as a search key and will display all the value present at that node. Total time complexity : O(L) ,L = length of string On Fri, Aug 24, 2012 at 11:18 AM, GAURAV CHAWLA togauravcha...@gmail.comwrote: Ques Given a large text... in the text.. there are gt; , lt; etc representing and .(there can be others like eq; etc) the task is to replace such (gt;) with the '' symbol... and (lt;) with '' given the table which have corresponding matches... and table is finite . suggest an efficient algo... -- Regards, G C -- 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. -- 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] Invert bits
x ^= 15; (^ = bit wise xor) On Wed, Aug 22, 2012 at 4:16 PM, Abhi abhi120@gmail.com wrote: Write a one line code to invert the last four bits of an integer ? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/sy3Ff971pRMJ. 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. -- 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] MS interview
@Ashish: According to your algo making multimap itself takes O(mn) time complexity (preprocessing). After then getting anagram of a string takes O(n) time. Am i right? On Thu, Aug 23, 2012 at 6:51 AM, Ashish Goel ashg...@gmail.com wrote: O(n) convert each string into format a1b2and then insert into multimap wityh this a1b2...as key and original word as value. All words with same key are anagrams Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Aug 22, 2012 at 11:39 PM, GAURAV CHAWLA togauravcha...@gmail.comwrote: Ques.. Given a m-word dictionary ... and a n-sized word... .. now suggest DS for dictionary such that you can find out all the anagrams of the given word present in dictionary... -- Regards, G C -- 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. -- 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. -- 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: Printing random word from file
@Dave sir, I didn't get your logic. Can you please elaborate it? On Sun, Aug 19, 2012 at 4:08 AM, Dave dave_and_da...@juno.com wrote: @Navin: Here is the algorithm: Save the first word. For i = 2, 3, ..., n = number of words in the file replace the saved word with the i-th word with probability 1/i. When EOF is reached, every word in the file will have probability 1/n of being the saved word. Print it. Dave On Saturday, August 18, 2012 1:28:56 AM UTC-5, Navin Kumar wrote: Print a *Random word* from a file. Input is path to a file, constraints- No extra memory like hashing etc. All the words in the file should have equal probability. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/HxO-wNzEP9gJ. 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. -- 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] Printing random word from file
Print a *Random word* from a file. Input is path to a file, constraints- No extra memory like hashing etc. All the words in the file should have equal probability. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/haNqu33z-TUJ. 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: MICROSOFT QUESTION
We have to consider cases when an element is zero. On Thu, Aug 16, 2012 at 7:07 PM, shady sinv...@gmail.com wrote: well we can do with just one array. Overwrite the answer directly on left[] array. On Thu, Aug 16, 2012 at 6:47 PM, mohit mohitsingh1...@gmail.com wrote: here are the steps : 1) Construct a temporary array left[] such that left[i] contains product of all elements on left of A[i] excluding A[i]. 2) Construct another temporary array right[] such that right[i] contains product of all elements on on right of A[i] excluding A[i]. 3) To get OUT[], multiply left[] and right[]. time complexity : O(n) On Thursday, August 16, 2012 2:26:58 PM UTC+5:30, ram wrote: Hi, This is a microsoft question asked in our campus previous year. Anyone having idea please share it here... Given an array of n elements A[n]. Write a program to create a new array OUT[n], which has its elements as multiplication of all the elements in the input array A[n] except that element (i.e.) OUT[2] = A[0] * A[1] * A[3] * ? * A[n-1]. Constraint is one should not use division operator. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/iqyLUMLQRS0J. 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. -- 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. -- 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] Finding Minimum of the maximum values
We can solve using Dynamic programming.. Take n*2 matrix for storing sum. Let A be original matrix and matrix M hold sum. Let M[i, j] contains max sum upto i th row and j th column. recursion will be as follows: M[i, j] = max(M[i - 1, j], M[i, j-1]) + A[i, j] By above formula fill whole M matrix and return the M[n-1, 1] value. P.S. I have not written boundary condition. For this if M[i - 1, j] goes beyond matrix boundary then take M[i, j-1] value and vice versa. Initialize M[0, 0] = A[0, 0] On Sun, Aug 12, 2012 at 3:16 PM, Hassan Monfared hmonfa...@gmail.comwrote: DP can help us to find max path, I couldn't find out any specific solution for complexity less than O(n!) but as an initial Idea, I think some kind of sorting rows or modified Floyd-Warshal algorithm may help us.please discuss If you have any Idea for challenge the problem. On Sun, Aug 12, 2012 at 1:22 PM, MeHdi KaZemI mehdi.kaze...@gmail.comwrote: Yes, and all the values are positive integers. For example 1 2 3 4 5 6 Maximum path in this matrix is 15, Another permutation of the same matrix 5 6 1 2 3 4 Maximum path in this matrix is 17, We want the minimum value among these maximum paths. On 8/12/12, MeHdi KaZemI mehdi.kaze...@gmail.com wrote: On 8/12/12, Hassan Monfared hmonfa...@gmail.com wrote: do we sum all cell values when we step over them ? On Sun, Aug 12, 2012 at 12:42 PM, MeHdi KaZemI mehdi.kaze...@gmail.comwrote: Hi there, There is a integer Matrix with dimensions n*2, If you want to go from (1,1) to (n,2) and you are allowed just to go down or right, what's the maximum value you can get? Alright this is easy, but we want to consider all the permutations of rows of the matrix which is n!, find this maximum for each permutation, and finally we want the minimum amount among these maximum values. Do you have an Idea to solve this problem better than O(n!)? -- MeHdi KaZemI -- 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. -- 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. -- MeHdi KaZemI -- MeHdi KaZemI -- 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. -- 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. -- 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] Finding Minimum of the maximum values
Thanx hassan for correcting me. I think there must be some DP solution for this problem. On Sun, Aug 12, 2012 at 5:26 PM, Hassan Monfared hmonfa...@gmail.comwrote: Mr. Navin ! the main question is not about finding max path for one permutation among the n! permutations! please read the question again and join us for solving the main problem On Sun, Aug 12, 2012 at 4:19 PM, Navin Kumar algorithm.i...@gmail.comwrote: We can solve using Dynamic programming.. Take n*2 matrix for storing sum. Let A be original matrix and matrix M hold sum. Let M[i, j] contains max sum upto i th row and j th column. recursion will be as follows: M[i, j] = max(M[i - 1, j], M[i, j-1]) + A[i, j] By above formula fill whole M matrix and return the M[n-1, 1] value. P.S. I have not written boundary condition. For this if M[i - 1, j] goes beyond matrix boundary then take M[i, j-1] value and vice versa. Initialize M[0, 0] = A[0, 0] On Sun, Aug 12, 2012 at 3:16 PM, Hassan Monfared hmonfa...@gmail.comwrote: DP can help us to find max path, I couldn't find out any specific solution for complexity less than O(n!) but as an initial Idea, I think some kind of sorting rows or modified Floyd-Warshal algorithm may help us.please discuss If you have any Idea for challenge the problem. On Sun, Aug 12, 2012 at 1:22 PM, MeHdi KaZemI mehdi.kaze...@gmail.comwrote: Yes, and all the values are positive integers. For example 1 2 3 4 5 6 Maximum path in this matrix is 15, Another permutation of the same matrix 5 6 1 2 3 4 Maximum path in this matrix is 17, We want the minimum value among these maximum paths. On 8/12/12, MeHdi KaZemI mehdi.kaze...@gmail.com wrote: On 8/12/12, Hassan Monfared hmonfa...@gmail.com wrote: do we sum all cell values when we step over them ? On Sun, Aug 12, 2012 at 12:42 PM, MeHdi KaZemI mehdi.kaze...@gmail.comwrote: Hi there, There is a integer Matrix with dimensions n*2, If you want to go from (1,1) to (n,2) and you are allowed just to go down or right, what's the maximum value you can get? Alright this is easy, but we want to consider all the permutations of rows of the matrix which is n!, find this maximum for each permutation, and finally we want the minimum amount among these maximum values. Do you have an Idea to solve this problem better than O(n!)? -- MeHdi KaZemI -- 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. -- 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. -- MeHdi KaZemI -- MeHdi KaZemI -- 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. -- 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. -- 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. -- 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. -- 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] Data Cache implementation problem
I think best data structure would be Optimal BST On Fri, Aug 10, 2012 at 11:47 PM, Kumar Vishal kumar...@gmail.com wrote: Huffman tree ??? On Fri, Aug 10, 2012 at 11:38 PM, Varma Selvaraj varm...@gmail.comwrote: A data cache needs to be implemented for the top 100 data items selected based on their frequency of access. The most frequent data member must be accessed fastest. And the access time/iterations of each data member from the cache should correspond to the frequncy of its access. Please choose the right data structure and find the right algorithm for the scenario? Can anyone help on this question? Thanks and Regards, Varma -- 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. -- Regards Kumar Vishal _ *http://wethecommonpeople.wordpress.com/ * *h**ttp://kumartechnicalarticles.wordpress.com/http://kumartechnicalarticles.wordpress.com/ * _ -- 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. -- 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] converting binary tree to BST
@vaibhav : yes it will be a balanced BST. On Wed, Aug 8, 2012 at 11:29 AM, vaibhav shukla vaibhav200...@gmail.comwrote: @Navin By your algo of starting with the middle node,I guess a balanced BST would be created. Is it ? On Wed, Aug 8, 2012 at 1:24 AM, Navin Kumar algorithm.i...@gmail.comwrote: 1. Convert your Binary tree into doubly linked list. 2. Sort the linked list using merge sort 3. Build BST using doubly linked list by each time selecting middle node and recursively calling left part of linked list and right part of linked list. On Tue, Aug 7, 2012 at 10:23 PM, vaibhav shukla vaibhav200...@gmail.comwrote: Hi all The problem is to convert a binary tree into Binary Search Tree My approach was : 1. Store the Inorder traversal of BT in an array. 2. Sort the array in ascending order. 3. Again do inorder traversal and write the Node's data from array one by one. This approach takes O(n) extra space. Can someone tell a better approach that doesn't require any extra space. Thanx. -- best wishes!! Vaibhav -- 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. -- 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. -- best wishes!! Vaibhav -- 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. -- 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] converting binary tree to BST
1. Convert your Binary tree into doubly linked list. 2. Sort the linked list using merge sort 3. Build BST using doubly linked list by each time selecting middle node and recursively calling left part of linked list and right part of linked list. On Tue, Aug 7, 2012 at 10:23 PM, vaibhav shukla vaibhav200...@gmail.comwrote: Hi all The problem is to convert a binary tree into Binary Search Tree My approach was : 1. Store the Inorder traversal of BT in an array. 2. Sort the array in ascending order. 3. Again do inorder traversal and write the Node's data from array one by one. This approach takes O(n) extra space. Can someone tell a better approach that doesn't require any extra space. Thanx. -- best wishes!! Vaibhav -- 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. -- 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: DE Shaw written test
This is a linear time constant space algorithm. Assume the stocks prices are given in an array where index represents the day no . For ex a[365] represents stock price on 365th day of year. Find the min and max element in the array. If the min comes before max, then return the dates- min to buy and max to sell. But if the min comes after max, find the max element that comes after min i.e. maxRight find the min element that comes before max i.e. minLeft Now find the difference (max - minLeft)( maxRight - min) return the dates for which the difference is higher. Code:-- void FindDaytoBuySellStock(int stocks[], int N) // here N = 365 { int minPos = findMinPos(stocks); int maxPos = findMaxPos(stocks); if(minPos maxPos ) { BuyDate = minPos,SellDate = maxPos; } else{ minLeft = find min in array from 0 to maxPos-1 maxRight = find max in array from minPos+1 to N int d1 = max - minLeft; int d2 = maxRight - min; if(d1 = d2 ) {BuyDate = minLeft,SellDate = max; } else{ BuyDate = min ,SellDate = maxRight; } } } -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/dSJCOIuUuKUJ. 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] merging
Actually i wanted to do it inplace. Using extra space it is much easier problem. On Mon, Aug 6, 2012 at 12:27 AM, payal gupta gpt.pa...@gmail.com wrote: int merge(int arr[],int n) { int l=0; int j=(n/3); int k=2*(n/3); int *a=(int*)malloc(sizeof(int)*n); for(int i=0;in/3;i++) { a[l++]=arr[i]; a[l++]=arr[j++]; a[l++]=arr[k++]; } for(int i=0;in;i++) arr[i]=a[i]; free(a); } cud be dun be dun recursively also to minimize d space complexity... On Sat, Aug 4, 2012 at 8:20 AM, Navin Kumar algorithm.i...@gmail.comwrote: In given array of elements like [a1,a2,a3,..an,b1,b2,b3,..bn,c**1,c2,c3,...cn] .Write an efficient program to merge them like [a1,b1,c1,a2,b2,c2,...an,bn,cn**]. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/gVCyxQV1IhAJ. 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. -- 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. -- 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] Amazon CodeSprint
Given the array of digits, you have to calculate the least positive integer value of the expression that could *NOT *have been received by you. The binary operators possible are *, +, -, / and brackets possible are ( and ). Note that / is an integer division i.e. 9/5 = 1. For ex- 6 6 4 4 the answer is 18 1 = 6 /6 + 4-4 2 = 6/6 + 4/4 3 = 6 +( 6/4) -4 4 = (6+6+4) / 4 …….. 18 cannot be formed -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/cxnY9WEACTIJ. 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] merging
In given array of elements like [a1,a2,a3,..an,b1,b2,b3,..bn,c1,c2,c3,...cn] .Write an efficient program to merge them like [a1,b1,c1,a2,b2,c2,...an,bn,cn]. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/gVCyxQV1IhAJ. 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] Microsoft first round interview question.
@sahil: Please elaborate your question. I didn't understand your question. what is straight doubly linked list?? How many pointers each node have?? On Thu, Aug 2, 2012 at 4:26 PM, Amit Basak abas...@gmail.com wrote: Does each node in the list have three pointers? What do you mean by straight doubly link list? Thanks, Amit On Wed, Aug 1, 2012 at 7:25 PM, sahil gupta sahilgupta...@gmail.comwrote: There is doubly link list and each node is having another pointer which is points to another doubly link list or points to null. You need make it straight doubly link list. Provide the efficient code. Sahil Gupta -- 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. -- 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. -- 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] Microsoft online questions
@Daksh: you are right :) On Tue, Jul 31, 2012 at 11:30 PM, Daksh Talwar dakshtal...@gmail.comwrote: @Navin : Thanks a lot . Also , I had this doubt , that taking the middle of the array as the root is just a convention right ? The tree we get is just one of the n(catalan number) trees we can get using the DLL/array given ..? On Tue, Jul 31, 2012 at 10:57 PM, manish untwal manishuntw...@gmail.comwrote: hey friends, just wanted to ask like what they ask in quants and DI On Tue, Jul 31, 2012 at 10:45 PM, Navin Kumar algorithm.i...@gmail.comwrote: @Daksh: total number of BST possible with n nodes will be : catalan number we can build balanced BST by each time selecting middle element as a root node and its left pointer will point to left linked list and right pointer will point to right linked list. Do it recursively for left list and right list. struct node *buildBST(struct node *list) { if(!list) return NULL; struct node *middle = getMiddle(list); middle-previous-next = NULL; middle-previous = buildBST(list); middle-next = buildBST(middle-next); return middle; } On Tue, Jul 31, 2012 at 8:35 PM, Daksh Talwar dakshtal...@gmail.comwrote: Anyone with a logic/algo/code for the 3. convert sorted doubly linked list to bst using same nodes as in DLL. . Would it be recursive ? On Tue, Jul 31, 2012 at 12:30 AM, Purani Sekar nagapur...@gmail.comwrote: Analytical questions were from logical reasoning, syllogism, piechart, etc. Technical questions were like - they'll give a flow chart (eg:http://en.wikipedia.org/wiki/File:FlowchartExample.png) or C program and ask to trace the output. no data structures and all. On Sun, Jul 29, 2012 at 10:16 PM, Tanuj Makkar tanujmakkar.de...@gmail.com wrote: hi can u please elaborate on analytical questions.like if they were from logical reasoning,verbal(syllogism) and in technical...were questions based on output of c programs...or there were data structures nd other topics plz help...it will be a great help ... . Thanx On Sun, Jul 29, 2012 at 9:58 PM, Purani Sekar nagapur...@gmail.com wrote: Hi, They conducted 2 online rounds. First round was of 1 hour duration. It tests your speed and analytical skills. The mark split was as given below: 30 analytical questions - data interpretation type 20 technical questiions - flow chart and basic c Second round was online coding round. But compiler will not be provided. It will be like typing a code in notepad. On Sun, Jul 29, 2012 at 4:56 PM, Sanchit Mittal since1991sanc...@gmail.com wrote: Hi, Can anybody help by sharing MS online test pattern and questions ? I have heard they have also included aptitude questions this time, is that right? Thanks -- Sanchit Mittal Fourth Year Undergraduate Computer Engineering Delhi College of Engineering ph- +919582414494 -- 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. -- 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. -- 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. -- 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. -- - - - - - - - - - - - - With Regards Daksh Talwar -- 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. -- 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
[algogeeks] coin problem
You are blindfolded and 20 coins are placed on the table in front of you. Out of them 10 coins have heads facing up and other tails. You are allowed to flip and move the coins. You should divide those coins into two sets such that one set contains 10 heads and other tails. You are allowed to only move or flip the coins -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/5On_Zr16xMIJ. 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] Microsoft online questions
@Daksh: total number of BST possible with n nodes will be : catalan number we can build balanced BST by each time selecting middle element as a root node and its left pointer will point to left linked list and right pointer will point to right linked list. Do it recursively for left list and right list. struct node *buildBST(struct node *list) { if(!list) return NULL; struct node *middle = getMiddle(list); middle-previous-next = NULL; middle-previous = buildBST(list); middle-next = buildBST(middle-next); return middle; } On Tue, Jul 31, 2012 at 8:35 PM, Daksh Talwar dakshtal...@gmail.com wrote: Anyone with a logic/algo/code for the 3. convert sorted doubly linked list to bst using same nodes as in DLL. . Would it be recursive ? On Tue, Jul 31, 2012 at 12:30 AM, Purani Sekar nagapur...@gmail.comwrote: Analytical questions were from logical reasoning, syllogism, piechart, etc. Technical questions were like - they'll give a flow chart (eg:http://en.wikipedia.org/wiki/File:FlowchartExample.png) or C program and ask to trace the output. no data structures and all. On Sun, Jul 29, 2012 at 10:16 PM, Tanuj Makkar tanujmakkar.de...@gmail.com wrote: hi can u please elaborate on analytical questions.like if they were from logical reasoning,verbal(syllogism) and in technical...were questions based on output of c programs...or there were data structures nd other topics plz help...it will be a great help ... . Thanx On Sun, Jul 29, 2012 at 9:58 PM, Purani Sekar nagapur...@gmail.com wrote: Hi, They conducted 2 online rounds. First round was of 1 hour duration. It tests your speed and analytical skills. The mark split was as given below: 30 analytical questions - data interpretation type 20 technical questiions - flow chart and basic c Second round was online coding round. But compiler will not be provided. It will be like typing a code in notepad. On Sun, Jul 29, 2012 at 4:56 PM, Sanchit Mittal since1991sanc...@gmail.com wrote: Hi, Can anybody help by sharing MS online test pattern and questions ? I have heard they have also included aptitude questions this time, is that right? Thanks -- Sanchit Mittal Fourth Year Undergraduate Computer Engineering Delhi College of Engineering ph- +919582414494 -- 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. -- 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. -- 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. -- 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. -- - - - - - - - - - - - - With Regards Daksh Talwar -- 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. -- 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: coin problem
@all: i have seen this question on careercup.com. I think question should be like this: Divide 20 coins in group of two such that both group must have equal number of heads and tails. solution given by dave sir solve this question. If this is not the case, i.e. if we will try to divide into two groups such that one group contain 10 heads and other group contains 10 tail ..i think it is not possible blindfolded. Because in that case we must have to identify (blindfolded) which coin is head and which is tail. On Tue, Jul 31, 2012 at 9:51 PM, Vipin Kumar vipink1ber...@gmail.comwrote: I think we are blindfolded.. how can we know afetr dividing 10 coins that 7 r heads.. or 'x' are heads and we need to flip it over.. ? On Tuesday, 31 July 2012 12:33:09 UTC+5:30, Navin Kumar wrote: You are blindfolded and 20 coins are placed on the table in front of you. Out of them 10 coins have heads facing up and other tails. You are allowed to flip and move the coins. You should divide those coins into two sets such that one set contains 10 heads and other tails. You are allowed to only move or flip the coins -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/bVriGdkAmMUJ. 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. -- 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] absolute minimum difference
Given array of integers (0 or +ve or -ve value) find two elements having minimum difference in their absolute values. e.g. Input {10 , -2, 4, 9,-20,17,-8,14,12) output {9,-8} I have solved it in O(nlogn). can it be solved in O(n). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/f6YMTX7R2tAJ. 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]
#include stdio.h #include stdlib.h #include ctype.h char *decrypt(char *s) { int n; char *digit = (char *)malloc(sizeof(char) * 5); char *p1 = (char *)malloc(sizeof(char) * 1024); char *p = p1; char *digit2; char prev; prev = *s; *p++ = *s++; while(s != '\0') { if(isdigit(*s)) { digit2 = digit; while(isdigit(*s)) *digit2++ = *s++; *digit2 = '\0'; n = atoi(digit); while(n 1) { *p++ = prev; n--; } } prev = *s; if(*s != '\0') *p++ = *s++; else{ *p = *s; break; } } *p = '\0'; return p1; } int main() { char *s = a10b10c1d3e4; char *s2 = decrypt(s); printf(%s, s2); return 0; } On Wed, Jul 25, 2012 at 6:46 AM, Sathish babu satbrucei...@gmail.comwrote: can anyone provide the code to convert ab1cd3 to abcddd **~Sathish Babu~** On Tue, Jul 24, 2012 at 11:39 PM, Mind Boggler min.b...@gmail.com wrote: Traditional decryption problem Convert a3b2c5 into aaabbc Can anyone Put forward an algo for the test case: a3b1c3d1 Thanx -- 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. -- 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. -- 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]
logic is very simple ...just trace the program you will understand. On Wed, Jul 25, 2012 at 7:28 PM, Navin Kumar algorithm.i...@gmail.comwrote: #include stdio.h #include stdlib.h #include ctype.h char *decrypt(char *s) { int n; char *digit = (char *)malloc(sizeof(char) * 5); char *p1 = (char *)malloc(sizeof(char) * 1024); char *p = p1; char *digit2; char prev; prev = *s; *p++ = *s++; while(s != '\0') { if(isdigit(*s)) { digit2 = digit; while(isdigit(*s)) *digit2++ = *s++; *digit2 = '\0'; n = atoi(digit); while(n 1) { *p++ = prev; n--; } } prev = *s; if(*s != '\0') *p++ = *s++; else{ *p = *s; break; } } *p = '\0'; return p1; } int main() { char *s = a10b10c1d3e4; char *s2 = decrypt(s); printf(%s, s2); return 0; } On Wed, Jul 25, 2012 at 6:46 AM, Sathish babu satbrucei...@gmail.comwrote: can anyone provide the code to convert ab1cd3 to abcddd **~Sathish Babu~** On Tue, Jul 24, 2012 at 11:39 PM, Mind Boggler min.b...@gmail.comwrote: Traditional decryption problem Convert a3b2c5 into aaabbc Can anyone Put forward an algo for the test case: a3b1c3d1 Thanx -- 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. -- 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. -- 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] [amazon]: calculating resistance
Given a Circuit (with resistors), we need to calculate the total resistance. Input will be like AB-5ohm, BC-6ohm, BC-10ohm, BC-20 ohm, CD-5 ohm. BC has been repeated twice implying they are in parallel. Write a program by implementing efficient data structure for storing and calculating the total resistance.http://www.careercup.com/question?id=14408748 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/q1AxlJQBmGEJ. 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] Anagram problem
@Abhishek +1 On Wed, Jul 18, 2012 at 11:19 PM, Abhishek Sharma abhi120...@gmail.comwrote: sort each word in the list,then sort the whole list. Now,sort the input word(string). and then use binary search to find the word. On Wed, Jul 18, 2012 at 8:59 PM, Bhupendra Dubey bhupendra@gmail.comwrote: Sort each of the word and form a trie , if any words comes again you get one sch case. On Wed, Jul 18, 2012 at 2:12 PM, vindhya chhabra vindhyachha...@gmail.com wrote: yes,sorry count sort will be O(n) so better.thanks On Wed, Jul 18, 2012 at 1:43 PM, saurabh singh saurab...@gmail.comwrote: ^sorting a string would be o(n^2logn) if u use q.sort.count sort would be better. Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Wed, Jul 18, 2012 at 1:08 PM, vindhya chhabra vindhyachha...@gmail.com wrote: sort the list,sort the word(use quick sort(nlogn time))- and den search using binary search(logn time) or we can evn do by hashing-hash the word,den for every word keep decreasing the counter,if the hash array is zero ,anagram,else reset the hash array for given input for the checking the next word. On Wed, Jul 18, 2012 at 2:07 AM, Navin Kumar algorithm.i...@gmail.com wrote: Assuming a preexisting list of 100 words, how would you efficiently see if a word received from input is an anagram of any of the 100 words? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/5kuxjymYEc4J. 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. -- Vindhya Chhabra -- 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. -- 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. -- Vindhya Chhabra -- 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. -- Thanks regards Bhupendra -- 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. -- Abhishek Sharma Under-Graduate Student, PEC University of Technology -- 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. -- 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: Appropriate data structure
@Dave sir, K is known in advance. Many people including me think stack as an appropriate data structure but still i am not satisfied with this answer. In case K is not known in advance : according to your solution when a new item is inserted next larger and next smallest item is searched.Isn't it cause much overhead?? can we think a better data structure to optimize this ? On Tue, Jul 17, 2012 at 10:52 PM, Dave dave_and_da...@juno.com wrote: @All: We seem to have different understandings of the problem. So Navin, as original poster, answer this question: Is k known in advance, or is it given in the request for the min and max elements. I assumed the latter, so that one request could ask for the max and min of the last 5 days and another could ask for the max and min for the last 100 days. Others seem to assume that k is known as the data are collected. Dave On Saturday, July 14, 2012 2:55:48 PM UTC-5, Navin Kumar wrote: A set of integer values are being received (1 per day). Store these values and at any given time, retrieve the min and max value over the last k days. What data structures would you use for storing and retrieving ? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/c58RGUBQobUJ. 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. -- 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] Anagram problem
Assuming a preexisting list of 100 words, how would you efficiently see if a word received from input is an anagram of any of the 100 words? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/5kuxjymYEc4J. 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] Appropriate data structure
I think stack would solve the purpose. please comment. On Sun, Jul 15, 2012 at 5:42 PM, enchantress elaenjoy...@gmail.com wrote: It says K days if you keep heap the order of values gets disturbed. How are last k values accessed then? On Sunday, 15 July 2012 12:46:02 UTC+5:30, adarsh kumar wrote: Min or max heap accordingly. This will do the job in O(log n) time. On Sun, Jul 15, 2012 at 1:25 AM, Navin Kumar algorithm.i...@gmail.comwrote: A set of integer values are being received (1 per day). Store these values and at any given time, retrieve the min and max value over the last k days. What data structures would you use for storing and retrieving ? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/** msg/algogeeks/-/2AhV1Xn3jD8Jhttps://groups.google.com/d/msg/algogeeks/-/2AhV1Xn3jD8J . To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/peWhqjKLIH8J. 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. -- 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] Appropriate data structure
A set of integer values are being received (1 per day). Store these values and at any given time, retrieve the min and max value over the last k days. What data structures would you use for storing and retrieving ? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/2AhV1Xn3jD8J. 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] [Amazon] : constructing fully binary tree
Given Preorder and postorder traversals of a tree. Device an algorithm to constuct a fully binary tree from these traversals. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/fx4LY5IUFT8J. 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] Remove duplicates from min-heap.
-- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/lZRdyZn85fcJ. 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: [Google] Finds all the elements that appear more than n/3 times
@sachin: you can find median in linear sort. http://valis.cs.uiuc.edu/~sariel/research/CG/applets/linear_prog/median.html On Wed, Jul 11, 2012 at 12:28 PM, sachin goyal sachingoyal@gmail.comwrote: To Mr. B how will you find median in O(n) time? please elaborate. On Wednesday, July 11, 2012 4:01:43 AM UTC+5:30, Mr.B wrote: I found a similar solution looking somewhere else. The solution for this problem is: a. There can be atmost 3 elements (only 3 distinct elements with each repeating n/3 times) -- check for this and done. -- O(n) time. b. There can be atmost 2 elements if not above case. 1. Find the median of the input. O(N) 2. Check if median element is repeated N/3 times or more -- O(n) - *{mark for output if yes}* 3. partition the array based on median found above. - O(n) -- {partition is single step in quicksort} 4. find median in left partition from (3). - O(n) 5. check if median element is repeared n/3 times or more - O(n) *{mark for output if yes}* 6. find median in right partition from (3). - O(n) 7. check if median element is repeared n/3 times or more - O(n) *{mark for output if yes}* its 7*O(N) = O(N) solution. Constant space. we need not check further down or recursively. {why? reason it.. its simple} On Wednesday, 27 June 2012 18:35:12 UTC-4, Navin Kumar wrote: Design an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list. The algorithm should run in linear time ( n =0 ). You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don't use standard linear time deterministic selection algo. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/PxIJd3So3tkJ. 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. -- 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: [Google] Finds all the elements that appear more than n/3 times
@sachin: http://valis.cs.uiuc.edu/~sariel/research/CG/applets/linear_prog/median.html On Wed, Jul 11, 2012 at 12:28 PM, sachin goyal sachingoyal@gmail.comwrote: To Mr. B how will you find median in O(n) time? please elaborate. On Wednesday, July 11, 2012 4:01:43 AM UTC+5:30, Mr.B wrote: I found a similar solution looking somewhere else. The solution for this problem is: a. There can be atmost 3 elements (only 3 distinct elements with each repeating n/3 times) -- check for this and done. -- O(n) time. b. There can be atmost 2 elements if not above case. 1. Find the median of the input. O(N) 2. Check if median element is repeated N/3 times or more -- O(n) - *{mark for output if yes}* 3. partition the array based on median found above. - O(n) -- {partition is single step in quicksort} 4. find median in left partition from (3). - O(n) 5. check if median element is repeared n/3 times or more - O(n) *{mark for output if yes}* 6. find median in right partition from (3). - O(n) 7. check if median element is repeared n/3 times or more - O(n) *{mark for output if yes}* its 7*O(N) = O(N) solution. Constant space. we need not check further down or recursively. {why? reason it.. its simple} On Wednesday, 27 June 2012 18:35:12 UTC-4, Navin Kumar wrote: Design an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list. The algorithm should run in linear time ( n =0 ). You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don't use standard linear time deterministic selection algo. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/PxIJd3So3tkJ. 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. -- 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] seperate diff types of coins
Minimum no. weighings: Divide 8 coins in group of 3, 3 and 2. For minimum weighsing group1 's total weight is x units(say) --FIrst weighing Groups 2nd total weights is y units Second weighing. Lastly one more weighing among a unit and b unit coins.---3 rd weighing So minimum 3 weighing is required. On Tue, Jul 10, 2012 at 11:03 AM, payal gupta gpt.pa...@gmail.com wrote: You have 8 coins. 3 of them weigh x units, 3 y units, 1 a units and 1 b units. They are all mixed and look identical. What are the minimum no of weighings reqd to seperate the for types of coins??? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/HhIaN4zgpxMJ. 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. -- 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] seperate diff types of coins
Let we have 8 coins named (for simplicity) x1, x2, x3, y1, y2, y3, a, b According to your question 3 of them weigh x units : x1+x2+x3 =x 3 of them weigh y units: y1+y2+y3 =y now consider the case when i grouped (x1, x2 x3) in single group (y1,y2 ,y3) in one group and (a,b) in one group. Now we will measure weight of 1st group (x1, x2, x3) :It will give x then we conclude that all elements in this group are those element whose total weight is x :Type 1 element. similarly for y. and for the last group we will pick up any element and measure its weight ..its weight will be either a or b. Depending upon outcome we will categorize them a and b. So 3 weighing is required. On Tue, Jul 10, 2012 at 7:05 PM, payal gupta gpt.pa...@gmail.com wrote: @navin...Sorry didnt get you how come u were able to segregate all the coins by the proposed method?? On 7/10/12, Navin Kumar algorithm.i...@gmail.com wrote: Minimum no. weighings: Divide 8 coins in group of 3, 3 and 2. For minimum weighsing group1 's total weight is x units(say) --FIrst weighing Groups 2nd total weights is y units Second weighing. Lastly one more weighing among a unit and b unit coins.---3 rd weighing So minimum 3 weighing is required. On Tue, Jul 10, 2012 at 11:03 AM, payal gupta gpt.pa...@gmail.com wrote: You have 8 coins. 3 of them weigh x units, 3 y units, 1 a units and 1 b units. They are all mixed and look identical. What are the minimum no of weighings reqd to seperate the for types of coins??? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/HhIaN4zgpxMJ. 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. -- 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. -- 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. -- 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] Google : Print in interleaved fashion
Given two strings .Print all the interleavings of the two strings. Interleaving means that the if B comes after A .It should also come after A in the interleaved string. ex- AB and CD ABCD ACBD ACDB CABD CADB CDAB -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/oAU32CrEVYYJ. 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: seperate diff types of coins
@payal: In this case too i think minimum number of weighing required is 3. Slightly change in my previous solution. x1+x2+x3 = 3x and y1+y2+y3 = 3y. On Wed, Jul 11, 2012 at 8:00 AM, payal gupta gpt.pa...@gmail.com wrote: @ Dave sir the balance considered here is simple balance scale incapable of giving any numeric reading and the we are unaware of any relationship between x,y,a,b or any kind denominations prioirity in terms of weights... @navin.. 3 of them weigh x means 3 of the coins individually weigh x gms,it isnt the cumulative sum of the coins as u considered ,thats what i got from the question.. Correct me if i'm wrong. Could it be done it done in lesser than 8 weighings?? Regards, PAYAL GUPTA. On 7/10/12, Dave dave_and_da...@juno.com wrote: @Gupta: You haven't defined the problem sufficiently. What type of scale do we have, a balance scale or one that gives a numeric reading? Do we know x, y, a, and b, or are you just saying that one set of three coins weigh the same, another set of three also weigh the same but have different weight that the first set, and the remaining two weigh different amounts than each other and the two sets? Is there any known relationship between x, y, a, and b? We can assume without loss of generality that x y and a b, but what about the relationships between x and a, x and b, y and a, and y and b? Knowing more will allow a solution with fewer weighings than knowing less. Dave On Tuesday, July 10, 2012 12:33:47 AM UTC-5, payal gupta wrote: You have 8 coins. 3 of them weigh x units, 3 y units, 1 a units and 1 b units. They are all mixed and look identical. What are the minimum no of weighings reqd to seperate the for types of coins??? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/c41Sw3CqNz4J. 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. -- 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. -- 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] Inversion problem
Let A[n] be an array of n distinct number. If ij and A[i] A[j] then the pair (i , j) is called inversion of A. Give an algorithm that determines the total number of inversions in O(nlogn) time. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/o7L4RLyUMuQJ. 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: Inversion problem
Thanx Deepika :) On Sun, Jul 8, 2012 at 11:48 AM, deepikaanand swinyanand...@gmail.comwrote: http://www.geeksforgeeks.org/archives/3968 On Jul 8, 11:01 am, Navin Kumar algorithm.i...@gmail.com wrote: Let A[n] be an array of n distinct number. If ij and A[i] A[j] then the pair (i , j) is called inversion of A. Give an algorithm that determines the total number of inversions in O(nlogn) time. -- 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. -- 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] Write a C program to reconstruct a BST from a given array of preorder traversal.
@Vindhya: BST can be reconstructed only by preorder traversal. In case of binary tree we need two traversal inorder and pre/post order On Wed, Jul 4, 2012 at 1:07 PM, vindhya chhabra vindhyachha...@gmail.comwrote: u need inoder traversal as well On Wed, Jul 4, 2012 at 11:22 AM, Navin Kumar algorithm.i...@gmail.comwrote: -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/xmZH9KY72_IJ. 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. -- Vindhya Chhabra -- 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. -- 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] serialize a binary tree
we can serialize the binary tree using preorder traversal and marking NULL pointer as '#'. source: http://www.leetcode.com/2010/09/serializationdeserialization-of-binary.html On Wed, Jul 4, 2012 at 4:21 PM, Ashish Goel ashg...@gmail.com wrote: my understanding is to either write the level order traversal noting parent, child relation or write the adjacency list into a file where we store the edges Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 4, 2012 at 3:58 PM, adarsh kumar algog...@gmail.com wrote: Serialisation meaning? Numbering the nodes. Any specific order, or as in level order?? On 7/4/12, Ashish Goel ashg...@gmail.com wrote: a] How would you serialize a binary tree in a file(improve it) b] serialization that you have chosen, write a code to reconstruct the tree Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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. -- 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. -- 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. -- 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] simple FILE reading problem.
Suppose a file.txt contains : 50 40 30 # # 5 # 10 # # i want to fetch only integers. How should i fetch it. I tried with fgetc and fscanf but it was too complicated. My approach: fetched one word at a time and put it into separate string and then i converted that string to integer(if each character of that string was between '0' to '9'). Is there any simple way to do this. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/btvudXnBrAIJ. 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] Write a C program to reconstruct a BST from a given array of preorder traversal.
-- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/xmZH9KY72_IJ. 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] [Google] Finds all the elements that appear more than n/3 times
Design an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list. The algorithm should run in linear time ( n =0 ). You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don't use standard linear time deterministic selection algo. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/dtpraFWNFSEJ. 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] MS Question: Add two large numbers where the numbers are stored in an array format
whether it is in character array or integer array?? On Tue, Jun 26, 2012 at 3:40 PM, Ashish Goel ashg...@gmail.com wrote: Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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. -- 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] [amazon ] Finding Sub segment
please provide some good data structure to solve this problem: http://www.careercup.com/question?id=14062676 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/WZiRDVnMKQYJ. 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] Is max distance between two leaves(diameter) in a tree is equal to max distance between any two node in that tree??
-- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/xM3mGdcfvi4J. 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: Largest Path in Tree [SPOJ BENFECT]
Is this similar to finding the diameter of a tree(longest disteance between two leaves) ?? If yes than visit this link http://www.cs.duke.edu/courses/spring00/cps100/assign/trees/diameter.html On Sat, Jun 23, 2012 at 2:44 PM, Avinash jain.av...@gmail.com wrote: Some how I found that we need to run bfs twice to get the largest distance between any two nodes of a tree. Please explain me how it works. regards, avinash -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/jodahB_dChYJ. 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. -- 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: Largest Path in Tree [SPOJ BENFECT]
Is longest path between two node in a tree is equal two logest path between two leaves?? On Sat, Jun 23, 2012 at 5:35 PM, Navin Kumar algorithm.i...@gmail.comwrote: Is this similar to finding the diameter of a tree(longest disteance between two leaves) ?? If yes than visit this link http://www.cs.duke.edu/courses/spring00/cps100/assign/trees/diameter.html On Sat, Jun 23, 2012 at 2:44 PM, Avinash jain.av...@gmail.com wrote: Some how I found that we need to run bfs twice to get the largest distance between any two nodes of a tree. Please explain me how it works. regards, avinash -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/jodahB_dChYJ. 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. -- 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] Programming Question
Extract words from file and make a BST. Then do inorder traversal and print them. On Fri, Jun 22, 2012 at 3:52 PM, Sourabh Singh singhsourab...@gmail.comwrote: u can use stl::map(string,vectorstring) idea is same bucket sort :-) On Fri, Jun 22, 2012 at 3:02 AM, Eshwar eshwaronl...@gmail.com wrote: Bucket sort algortihm Linkedlist based On Fri, Jun 22, 2012 at 3:31 PM, Gobind Kumar Hembram gobind@gmail.com wrote: I was asked this question in one company Programming Round.Please help me in solving this,I tried with array of pointers ,2-D array and by buffering. You have a file with names of brands separated by comma. Write a program (in language of your choice) to group them by their starting letter. For example, if the input file is this: Reebok, Puma, Adidas, Clarks, Catwalk, Converse, FILA, Lotto, Newfeel, Nike, Numero Uno, New Balance, ASICS, Carlton London, Crocs The program should print the following: A ASICS, Adidas C Carlton London, Catwalk, Clarks, Converse, Crocs F FILA L Lotto N New Balance, Newfeel, Nike, Numero Uno P Puma R Reebok -- 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. -- Regards, Eshwar +91-95350-86592 This message (including any attachments) is intended only for the use of the individual or entity to which it is addressed and may contain information that is non-public, proprietary, privileged, confidential, and exempt from disclosure under applicable law or may constitute as attorney work product. If you are not the intended recipient, you are hereby notified that any use, dissemination, distribution, or copying of this communication is strictly prohibited. If you have received this communication in error, notify us immediately by telephone and (i) destroy this message if a facsimile or (ii) delete this message immediately if this is an electronic communication. Thank you. -- 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. -- 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. -- 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] Reverse Queue
How to reverse a Queue . Constraints: Time complexity O(n). space complexity: O(1) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/kepls-8qRwgJ. 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] Reverse Queue
@Saurabh: queue will be remain unchanged according to your algorithm. Because if you will delete an element from front and add at rear no change will be there. After n iteration front will be pointing to same element and rear will also point to same element. Correct me if i am wrong. :) On Wed, Jun 20, 2012 at 6:39 PM, saurabh singh saurabh.n...@gmail.comwrote: count the size of queue : O(n) loop for n and do remove and add in queue : O(n) Total : O(n) On Wed, Jun 20, 2012 at 6:34 PM, Navin Kumar algorithm.i...@gmail.comwrote: How to reverse a Queue . Constraints: Time complexity O(n). space complexity: O(1) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/kepls-8qRwgJ. 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. -- Thanks Regards, Saurabh -- 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. -- 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] Reverse Queue
For ex: let only two element are in queue: 1 2 (1 at front and rear is at 2). looping two times: first time: delete from front and adding to rear: queue will be: 2 1(front at 2 , rear at 1) second iteration: deleting 2 and adding to queue :result will be: 1 2 (front 1, rear 2) On Wed, Jun 20, 2012 at 6:46 PM, Navin Kumar algorithm.i...@gmail.comwrote: @Saurabh: queue will be remain unchanged according to your algorithm. Because if you will delete an element from front and add at rear no change will be there. After n iteration front will be pointing to same element and rear will also point to same element. Correct me if i am wrong. :) On Wed, Jun 20, 2012 at 6:39 PM, saurabh singh saurabh.n...@gmail.comwrote: count the size of queue : O(n) loop for n and do remove and add in queue : O(n) Total : O(n) On Wed, Jun 20, 2012 at 6:34 PM, Navin Kumar algorithm.i...@gmail.comwrote: How to reverse a Queue . Constraints: Time complexity O(n). space complexity: O(1) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/kepls-8qRwgJ. 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. -- Thanks Regards, Saurabh -- 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. -- 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] Reverse Queue
Use only standard operation of Queue like: EnQueue, DeQueue, IsEmptyQueue etc On Wed, Jun 20, 2012 at 6:50 PM, amrit harry dabbcomput...@gmail.comwrote: can we create other methods or we have to use only enqueue and dequeue...? if yes then simply for(i=0;i=n/2;i++) swap(i,n-i); On Wed, Jun 20, 2012 at 6:46 PM, Navin Kumar algorithm.i...@gmail.comwrote: @Saurabh: queue will be remain unchanged according to your algorithm. Because if you will delete an element from front and add at rear no change will be there. After n iteration front will be pointing to same element and rear will also point to same element. Correct me if i am wrong. :) On Wed, Jun 20, 2012 at 6:39 PM, saurabh singh saurabh.n...@gmail.comwrote: count the size of queue : O(n) loop for n and do remove and add in queue : O(n) Total : O(n) On Wed, Jun 20, 2012 at 6:34 PM, Navin Kumar algorithm.i...@gmail.comwrote: How to reverse a Queue . Constraints: Time complexity O(n). space complexity: O(1) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/kepls-8qRwgJ. 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. -- Thanks Regards, Saurabh -- 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. -- 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. -- Thanks Regards Amritpal singh -- 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. -- 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] Reverse Queue
@Kirubakaran : still space complexity is O(n) due to stack.Can it be solved in space complexity O(1). On Wed, Jun 20, 2012 at 8:00 PM, Kirubakaran D kirubakara...@gmail.comwrote: You could use recursion. def reverse_Q q if !q.isEmpty? el = q.dequeue nQ = reverse_Q(q) nQ.enqueue el return nQ end return q end On Wednesday, June 20, 2012 6:57:23 PM UTC+5:30, Navin Kumar wrote: Use only standard operation of Queue like: EnQueue, DeQueue, IsEmptyQueue etc On Wed, Jun 20, 2012 at 6:50 PM, amrit harry dabbcomput...@gmail.comwrote: can we create other methods or we have to use only enqueue and dequeue...? if yes then simply for(i=0;i=n/2;i++) swap(i,n-i); On Wed, Jun 20, 2012 at 6:46 PM, Navin Kumar algorithm.i...@gmail.comwrote: @Saurabh: queue will be remain unchanged according to your algorithm. Because if you will delete an element from front and add at rear no change will be there. After n iteration front will be pointing to same element and rear will also point to same element. Correct me if i am wrong. :) On Wed, Jun 20, 2012 at 6:39 PM, saurabh singh saurabh.n...@gmail.comwrote: count the size of queue : O(n) loop for n and do remove and add in queue : O(n) Total : O(n) On Wed, Jun 20, 2012 at 6:34 PM, Navin Kumar algorithm.i...@gmail.com wrote: How to reverse a Queue . Constraints: Time complexity O(n). space complexity: O(1) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/ **msg/algogeeks/-/kepls-8qRwgJhttps://groups.google.com/d/msg/algogeeks/-/kepls-8qRwgJ . To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@* *googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en . -- Thanks Regards, Saurabh -- 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+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en 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+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Amritpal singh -- 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+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/qmLUaTNJns8J. 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. -- 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] Reverse Queue
@saurabh : i want solution with space complexity of O(1) . your solution is right but it takes O(n) space. On Wed, Jun 20, 2012 at 8:28 PM, saurabh singh saurabh.n...@gmail.comwrote: Why will my proposed solution not work for you ??? On Wed, Jun 20, 2012 at 8:19 PM, Navin Kumar algorithm.i...@gmail.comwrote: @Kirubakaran : still space complexity is O(n) due to stack.Can it be solved in space complexity O(1). On Wed, Jun 20, 2012 at 8:00 PM, Kirubakaran D kirubakara...@gmail.comwrote: You could use recursion. def reverse_Q q if !q.isEmpty? el = q.dequeue nQ = reverse_Q(q) nQ.enqueue el return nQ end return q end On Wednesday, June 20, 2012 6:57:23 PM UTC+5:30, Navin Kumar wrote: Use only standard operation of Queue like: EnQueue, DeQueue, IsEmptyQueue etc On Wed, Jun 20, 2012 at 6:50 PM, amrit harry dabbcomput...@gmail.comwrote: can we create other methods or we have to use only enqueue and dequeue...? if yes then simply for(i=0;i=n/2;i++) swap(i,n-i); On Wed, Jun 20, 2012 at 6:46 PM, Navin Kumar algorithm.i...@gmail.com wrote: @Saurabh: queue will be remain unchanged according to your algorithm. Because if you will delete an element from front and add at rear no change will be there. After n iteration front will be pointing to same element and rear will also point to same element. Correct me if i am wrong. :) On Wed, Jun 20, 2012 at 6:39 PM, saurabh singh saurabh.n...@gmail.com wrote: count the size of queue : O(n) loop for n and do remove and add in queue : O(n) Total : O(n) On Wed, Jun 20, 2012 at 6:34 PM, Navin Kumar algorithm.i...@gmail.com wrote: How to reverse a Queue . Constraints: Time complexity O(n). space complexity: O(1) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/**msg/algogeeks/-/kepls-8qRwgJhttps://groups.google.com/d/msg/algogeeks/-/kepls-8qRwgJ . To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@**googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en . -- Thanks Regards, Saurabh -- 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+unsubscribe@ **googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=enhttp://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+unsubscribe@* *googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en . -- Thanks Regards Amritpal singh -- 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+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/qmLUaTNJns8J. 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. -- 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. -- Thanks Regards, Saurabh -- 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. -- You received this message because you are subscribed
Re: [algogeeks] Reverse Queue
@Saurabh:i was wrong in deciding space complexity. Yes, your algo will take O(1) time but you have to enqueue elements in reverse order.Not in the order you fetched. Think about it :). Then you have to take stack or some other data structure. On Wed, Jun 20, 2012 at 8:40 PM, saurabh singh saurabh.n...@gmail.comwrote: How ?? I am asking to manipulate the same queue. Dequeue n-1 elements and enqueue them in order to you take out to the same queue..Where is extra space involved ? On Wed, Jun 20, 2012 at 8:36 PM, Navin Kumar algorithm.i...@gmail.comwrote: @saurabh : i want solution with space complexity of O(1) . your solution is right but it takes O(n) space. On Wed, Jun 20, 2012 at 8:28 PM, saurabh singh saurabh.n...@gmail.comwrote: Why will my proposed solution not work for you ??? On Wed, Jun 20, 2012 at 8:19 PM, Navin Kumar algorithm.i...@gmail.comwrote: @Kirubakaran : still space complexity is O(n) due to stack.Can it be solved in space complexity O(1). On Wed, Jun 20, 2012 at 8:00 PM, Kirubakaran D kirubakara...@gmail.com wrote: You could use recursion. def reverse_Q q if !q.isEmpty? el = q.dequeue nQ = reverse_Q(q) nQ.enqueue el return nQ end return q end On Wednesday, June 20, 2012 6:57:23 PM UTC+5:30, Navin Kumar wrote: Use only standard operation of Queue like: EnQueue, DeQueue, IsEmptyQueue etc On Wed, Jun 20, 2012 at 6:50 PM, amrit harry dabbcomput...@gmail.com wrote: can we create other methods or we have to use only enqueue and dequeue...? if yes then simply for(i=0;i=n/2;i++) swap(i,n-i); On Wed, Jun 20, 2012 at 6:46 PM, Navin Kumar algorithm.i...@gmail.com wrote: @Saurabh: queue will be remain unchanged according to your algorithm. Because if you will delete an element from front and add at rear no change will be there. After n iteration front will be pointing to same element and rear will also point to same element. Correct me if i am wrong. :) On Wed, Jun 20, 2012 at 6:39 PM, saurabh singh saurabh.n...@gmail.com wrote: count the size of queue : O(n) loop for n and do remove and add in queue : O(n) Total : O(n) On Wed, Jun 20, 2012 at 6:34 PM, Navin Kumar algorithm.i...@gmail.com wrote: How to reverse a Queue . Constraints: Time complexity O(n). space complexity: O(1) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/**msg/algogeeks/-/kepls-8qRwgJhttps://groups.google.com/d/msg/algogeeks/-/kepls-8qRwgJ . To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@**googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en . -- Thanks Regards, Saurabh -- 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+unsubscribe@**googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=enhttp://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+unsubscribe@**googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en . -- Thanks Regards Amritpal singh -- 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+unsubscribe@ **googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/qmLUaTNJns8J. 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. -- 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
Re: [algogeeks] Reverse Queue
@Rishabh: i know using stack or recursion it can be done easily with O(n) space. I want to know whether there exist more space efficient algo for this problem or not? On Wed, Jun 20, 2012 at 9:20 PM, Rishabh Agarwal rishabh...@gmail.comwrote: @Navin: as you say you have to take stack or some other data structure then it will definately not be donw in O(1) space complexity i think the recursive solution is best because we are not explicitly using any extra space its internal stack is using this space. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/oKM6PICuD6oJ. 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. -- 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]
@Umer: rand(5) + (rand(5)%2): = it will never give 6 because for rand(7) range will be 0-6. So better try this: rand(5) + (rand(5)%3). On Tue, Jun 19, 2012 at 2:45 PM, Umer Farooq the.um...@gmail.com wrote: rand(5) + (rand(5)%2); On Tue, Jun 19, 2012 at 12:30 PM, Sourabh Singh singhsourab...@gmail.comwrote: @ sry condition should be: if(20*prob = 500/7) :-) On Tue, Jun 19, 2012 at 12:26 AM, Sourabh Singh singhsourab...@gmail.com wrote: @ALL Given a random number generator say r(5) generates number between 1-5 uniformly at random , use it to in r(7) which should generate a random number between 1-7 uniformly at random i have seen this on many site's but not a single correct solution. all solution's posted got rejected by someone else.: plz.. suggest some algo : my aprroach: let's assume a rectangle : 100 |___ |___|__ 500/7 | || | || |___|__| 0 1 2 3 4 5 67 now : let : num = rand(5); prob = rand(5); if(prob = rand(5)) print num else print 5 + num*(2/5) -- 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. -- 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. -- Umer -- 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. -- 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] MS Question: Reverse stack using push, pop without any auxiliary data structure
void Reverse(struct Stack *S) { int data; if(IsEmptyStack(S)) return; data=pop(s); ReverseStack(S); InsertAtBottom(S, data); } void InsertAtBottom(struct stack *S, int data) { int temp; if(!IsEmptyStack(S)){ push(S,data); return; } temp=pop(S); InsertAtBottom(S,data); push(S, temp); } On Thu, Jun 14, 2012 at 2:44 PM, rahul patil rahul.deshmukhpa...@gmail.comwrote: to store items in stack you will need some DS. Do they mean you cant use any auxillary DS than stack ? On Thu, Jun 14, 2012 at 2:24 PM, Ashish Goel ashg...@gmail.com wrote: Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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. -- Regards, Rahul Patil -- 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. -- 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] MS Question: Reverse stack using push, pop without any auxiliary data structure
@all: In my code isntead of (!IsEmptyStack) use IsEmptyStack Logic : First pop the all element and then start putting element at bottom in reverse order i.e. the element which is fetched last is put at the bottom and so on. ex: let our stack is: 1 2 3 4 (1 is at bottom). function Call is will be: Reverse(S) --Reverse(S) --Reverse(S) --Reverse(S) --stack empty so return InsertAtBottom(4) InsertAtBottom(3)InsertAtBottom(2) InsertAtBottom(1) going back First 1 will be placed at bottom: stack content :1 now 2 will be placed at bottom: stack content will be: 2 1 now 3 will be placed at bottom: stack content will be: 3 2 1 now 4 will be placed at bottom: stack content will be:4 3 2 1 On Thu, Jun 14, 2012 at 2:46 PM, Nishant Pandey nishant.bits.me...@gmail.com wrote: stack means inbuild stack we cant use any DS from our program explicitly. On Thu, Jun 14, 2012 at 2:44 PM, rahul patil rahul.deshmukhpa...@gmail.com wrote: to store items in stack you will need some DS. Do they mean you cant use any auxillary DS than stack ? On Thu, Jun 14, 2012 at 2:24 PM, Ashish Goel ashg...@gmail.com wrote: Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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. -- Regards, Rahul Patil -- 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. -- Cheers, Nishant Pandey |Specialist Tools Development | npan...@google.comgvib...@google.com | +91-9911258345 -- 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. -- 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] MS Question: Reverse stack using push, pop without any auxiliary data structure
I corrected in function InsertAtBottom :In my code isntead of (!IsEmptyStack) use IsEmptyStack On Fri, Jun 15, 2012 at 10:49 AM, Navin Kumar algorithm.i...@gmail.comwrote: @all: In my code isntead of (!IsEmptyStack) use IsEmptyStack Logic : First pop the all element and then start putting element at bottom in reverse order i.e. the element which is fetched last is put at the bottom and so on. ex: let our stack is: 1 2 3 4 (1 is at bottom). function Call is will be: Reverse(S) --Reverse(S) --Reverse(S) --Reverse(S) --stack empty so return InsertAtBottom(4) InsertAtBottom(3)InsertAtBottom(2) InsertAtBottom(1) going back First 1 will be placed at bottom: stack content :1 now 2 will be placed at bottom: stack content will be: 2 1 now 3 will be placed at bottom: stack content will be: 3 2 1 now 4 will be placed at bottom: stack content will be:4 3 2 1 On Thu, Jun 14, 2012 at 2:46 PM, Nishant Pandey nishant.bits.me...@gmail.com wrote: stack means inbuild stack we cant use any DS from our program explicitly. On Thu, Jun 14, 2012 at 2:44 PM, rahul patil rahul.deshmukhpa...@gmail.com wrote: to store items in stack you will need some DS. Do they mean you cant use any auxillary DS than stack ? On Thu, Jun 14, 2012 at 2:24 PM, Ashish Goel ashg...@gmail.com wrote: Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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. -- Regards, Rahul Patil -- 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. -- Cheers, Nishant Pandey |Specialist Tools Development | npan...@google.comgvib...@google.com | +91-9911258345 -- 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. -- 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] [amazon]: dutch national flag algorithm
@Ashot: You can traverse array one time. In your case you are traversing twice. First for counting occurrence of R , G and B then again traversing for assigning values. But constraints is that you have to traverse only once. On Sun, Jun 10, 2012 at 5:13 PM, Akshat Sapra sapraaks...@gmail.com wrote: int low,mid,high; low = mid = 0; high = (int)(sizeof(arr)/sizeof(arr[0]))-1; /* According to Dutch national flag problem there are three types of quantities in an array and we have to combine these elements together but in a certain order Let the elements in the array are in the form 0,1,2 then these elements in an array should appear in order 0 then 1 then 2 ( low to middle-1 ) - elements having 0 as a number (middle to high-1 ) - 1 as a number ( high to arr - size) - 2 as a number / n = high; for ( int i = 0; i = n; i++ ) { if ( arr[mid] == 0 ) { swap(arr[low],arr[mid]); low++; mid++; } else if ( arr[mid] == 2 ) { swap(arr[mid],arr[high]); high--; } else { mid++; } } -- 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. -- 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] Word printing Program
Write an efficient program that prints the distinct words in its input sorted into decreasing order of frequency of occurrence. Precede each word by its count. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/8iCd9zYdPXwJ. 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] [amazon]: dutch national flag algorithm
Given a character array as input. Array contains only three types of characters 'R', 'G' and 'B'. Sort the array such that all 'R's comes before 'G's and all 'G's comes before 'B's. Constraint :- No extra space allowed(except O(1) space like variables) and minimize the time complexity. You can only traverse the array once. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/54GHWSwHHw8J. 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: wrong output of C program
@sengar: sorry dude...i got his doubt.Though my explanation was correct. I think now everybody's doubt is clear.By the way thanx for correcting me. On Fri, Jun 8, 2012 at 11:48 AM, sengar.mahi sengar.m...@gmail.com wrote: @naveen :read the his doubt properly...he was expecting 5 10 15 but was getting 8 32 96...and dats the correction required which i made On Fri, Jun 8, 2012 at 8:08 AM, Navin Kumar algorithm.i...@gmail.comwrote: @Mahendra: for ur above code with t=(a2)+a o/p will be 5,10, 15 as i explained above. without bracket answer will be 8 , 32 and 96 because + precedence is higher than . On Fri, Jun 8, 2012 at 7:31 AM, Mahendra Sengar sengar.m...@gmail.comwrote: Cracked it...i guess precedence of + is more than so use t=(a2)+a; I checked, its giving proper output now !!! On Friday, June 8, 2012 5:46:09 AM UTC+5:30, algo lover wrote: The following is a simple C program which tries to multiply an integer by 5 using the bitwise operations. But it doesn't do so. Explain the reason for the wrong behavior of the program. #include stdio.h #define PrintInt(expr) printf(%s : %d\n,#expr,(expr)) *int* FiveTimes(*int* a) { *int* t; t *=* a**2 *+* a; *return* t; } *int* main() { *int* a *=* 1, b *=* 2,c *=* 3; PrintInt(FiveTimes(a)); PrintInt(FiveTimes(b)); PrintInt(FiveTimes(c)); *return* 0; } -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/7CNEyeGuUzEJ. 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. -- 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. -- 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. -- 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] wrong output of C program
one left shift is equivalent to multiplying with 2.Two left is equivalent to multiplying with 2^2. and so on. so i left shift means multiplying with 2^i. In your program you did left shift with 2.so it is equivalent to multiplying with 4. so when input is 1 function will return 4*1+1=5. when input is 2..output is 2*4+2=10.For 3 o/p is 3*4+3=15 On Fri, Jun 8, 2012 at 5:46 AM, Mad Coder imamadco...@gmail.com wrote: The following is a simple C program which tries to multiply an integer by 5 using the bitwise operations. But it doesn't do so. Explain the reason for the wrong behavior of the program. #include stdio.h #define PrintInt(expr) printf(%s : %d\n,#expr,(expr)) *int* FiveTimes(*int* a) { *int* t; t *=* a**2 *+* a; *return* t; } *int* main() { *int* a *=* 1, b *=* 2,c *=* 3; PrintInt(FiveTimes(a)); PrintInt(FiveTimes(b)); PrintInt(FiveTimes(c)); *return* 0; } -- 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. -- 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: wrong output of C program
@Mahendra: for ur above code with t=(a2)+a o/p will be 5,10, 15 as i explained above. without bracket answer will be 8 , 32 and 96 because + precedence is higher than . On Fri, Jun 8, 2012 at 7:31 AM, Mahendra Sengar sengar.m...@gmail.comwrote: Cracked it...i guess precedence of + is more than so use t=(a2)+a; I checked, its giving proper output now !!! On Friday, June 8, 2012 5:46:09 AM UTC+5:30, algo lover wrote: The following is a simple C program which tries to multiply an integer by 5 using the bitwise operations. But it doesn't do so. Explain the reason for the wrong behavior of the program. #include stdio.h #define PrintInt(expr) printf(%s : %d\n,#expr,(expr)) *int* FiveTimes(*int* a) { *int* t; t *=* a**2 *+* a; *return* t; } *int* main() { *int* a *=* 1, b *=* 2,c *=* 3; PrintInt(FiveTimes(a)); PrintInt(FiveTimes(b)); PrintInt(FiveTimes(c)); *return* 0; } -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/7CNEyeGuUzEJ. 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. -- 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] MS Question: WAP to find files in a directory/subdirectories
#include stdio.h #include stdlib.h #include sys/types.h #include dirent.h #include unistd.h #include ctype.h #include string.h void dirfun(char *); int main() { char *home=/home/navin/temp/; dirfun(home); return 0; } void dirfun(char *path) { struct dirent *dir; DIR *dp= opendir(path); if(dp!=NULL) { while((dir = readdir(dp))) { if(dir-d_type == DT_DIR) { if(strcmp(dir-d_name,.) strcmp(dir-d_name,..)) printf(%s\n,dir-d_name); } else printf(%s\n,dir-d_name); } } } On Sun, Jun 3, 2012 at 8:14 AM, Ashish Goel ashg...@gmail.com wrote: ls-r implementation needed... Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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. -- 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] MS Question: WAP to find files in a directory/subdirectories
you can set your directory path in this line char *home=/home/navin/temp/; On Sun, Jun 3, 2012 at 11:26 AM, Navin Kumar algorithm.i...@gmail.comwrote: #include stdio.h #include stdlib.h #include sys/types.h #include dirent.h #include unistd.h #include ctype.h #include string.h void dirfun(char *); int main() { char *home=/home/navin/temp/; dirfun(home); return 0; } void dirfun(char *path) { struct dirent *dir; DIR *dp= opendir(path); if(dp!=NULL) { while((dir = readdir(dp))) { if(dir-d_type == DT_DIR) { if(strcmp(dir-d_name,.) strcmp(dir-d_name,..)) printf(%s\n,dir-d_name); } else printf(%s\n,dir-d_name); } } } On Sun, Jun 3, 2012 at 8:14 AM, Ashish Goel ashg...@gmail.com wrote: ls-r implementation needed... Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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. -- 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] MS Question: Delete a node in single linked list if it is less than any of the successor nodes
I think the easiest method to do this problem is this: http://k2code.blogspot.in/2011/09/deleting-node-in-singly-linked-list-if.html On Thu, May 31, 2012 at 5:58 PM, Ashish Goel ashg...@gmail.com wrote: that is what i have done by using recursion=stack. my code has problem, after free(pCurr);, i should have return pRest; Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Thu, May 31, 2012 at 4:37 PM, atul anand atul.87fri...@gmail.comwrote: then i guess ...it can be done using stack..with O(n) complexity.. it is similar to finding next greater element http://www.geeksforgeeks.org/archives/8405 element in the stack at the end of the algo...are the element which will remain in the linked list . if stack is not empty then keep poping elements and create a SLL. On Thu, May 31, 2012 at 4:29 PM, Ashish Goel ashg...@gmail.com wrote: yes Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Thu, May 31, 2012 at 2:34 PM, atul anand atul.87fri...@gmail.comwrote: @Ashish : please clarify this ques... delete a node in SLL if it is less than *any* of the succesor node .. 1 2 8 10 3 4 7 12 delete 1,2,8,10,3,4,7 ouput will be single node i.e 12 dats what question asks? On Thu, May 31, 2012 at 2:16 PM, Ashish Goel ashg...@gmail.com wrote: the LL is unsorted, is there any better solution that this? struct node* deleteNodes(struct node *pHead, struct node *pPrev) { struct node *pLL = *pHead; if (!pLL) return NULL; struct node *pCurr = pLL; struct node *pRest = deleteNodes(pCurr-next, pCurr); if (!pRest) return pCurr; if (pCurr-data pRest-data) { if (pPrev) { pPrev-next = pRest; }; free(pCurr); } else { pCurr-next = pRest; } return pCurr; } Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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. -- 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. -- 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. -- 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. -- 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. -- 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.