[algogeeks] Re: Microsoft Interview Question
void findPaths(int x, int y, int depth)
{
if (isEnd(x,y)) showSolution(); // One path will be marked by
letters A,B,C...
else
{
maze[x][y] = 'A' + depth;
if (x (maze[x-1][y]=='1')) findPaths(x-1,y,depth+1);
if (y (maze[x][y-1]=='1')) findPaths(x,y-1,depth+1);
if ((x+1size) (maze[x+1][y]=='1')) findPaths(x+1,y,depth
+1);
if ((y+1size) (maze[x][y+1]=='1')) findPaths(x,y+1,depth
+1);
maze[x][y] = '1';
}
}
On Oct 12, 3:01 pm, 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.
Re: [algogeeks] Re: Microsoft Interview Question
BFS On Sun, Oct 14, 2012 at 4:21 PM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: response awaited!!! anyone?? 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 -- 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] Re: Microsoft Interview Question
@jaspreet : i dont find much difference between using BFS or backtracking...which is doing similar to DFS. On Tue, Oct 16, 2012 at 4:28 AM, Jaspreet Singh jassajjassaj...@gmail.comwrote: BFS On Sun, Oct 14, 2012 at 4:21 PM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: response awaited!!! anyone?? 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 -- 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. -- You received this message because 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: Microsoft Interview Question
response awaited!!! anyone?? 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 -- 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.
[algogeeks] Re: MICROSOFT QUESTION
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.
Re: [algogeeks] Re: MICROSOFT QUESTION
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.
[algogeeks] Re: MICROSOFT QUESTION
yeah we can do it without using an extra array too. first calculating the product of elements on its left and putting in OUT[] and then multiplying with the product of elements on its right . no auxiliary space used. 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/-/qFD7wSqIm-QJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Re: MICROSOFT QUESTION
@Navin: Why? No division is used. Dave On Thursday, August 16, 2012 9:20:03 AM UTC-5, Navin Kumar wrote: We have to consider cases when an element is zero. On Thu, Aug 16, 2012 at 7:07 PM, shady sin...@gmail.com javascript: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 mohitsi...@gmail.comjavascript: 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 algo...@googlegroups.comjavascript: . To unsubscribe from this group, send email to algogeeks+...@googlegroups.com javascript:. 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 algo...@googlegroups.comjavascript: . To unsubscribe from this group, send email to algogeeks+...@googlegroups.com javascript:. 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/cOrXdXwNPUQJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 online questions : DLL to bst??
http://www.geeksforgeeks.org/archives/17629 On 2 August 2012 19:50, Daksh Talwar dakshtal...@gmail.com wrote: When asked , try to make the most balanced one . otherwise there are many possible BSTs for a given array/linked list. On Thu, Aug 2, 2012 at 5:05 PM, Umer Farooq the.um...@gmail.com wrote: A LinkedList is by itself is a BST such that one child node of each node is null. Do we need a simple BST or height balanced BST? On Tue, Jul 31, 2012 at 2:39 PM, Ashish Goel ashg...@gmail.com wrote: how would you do convert sorted doubly linked list to bst using same nodes as in DLL Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sun, Jul 29, 2012 at 10:30 PM, Purani Sekar nagapur...@gmail.comwrote: convert sorted doubly linked list to bst using same nodes as in DLL -- You received this message because 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. -- - - - - - - - - - - - - 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. -- aviNash -- You received this message because 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: Microsoft online questions : DLL to bst??
When asked , try to make the most balanced one . otherwise there are many possible BSTs for a given array/linked list. On Thu, Aug 2, 2012 at 5:05 PM, Umer Farooq the.um...@gmail.com wrote: A LinkedList is by itself is a BST such that one child node of each node is null. Do we need a simple BST or height balanced BST? On Tue, Jul 31, 2012 at 2:39 PM, Ashish Goel ashg...@gmail.com wrote: how would you do convert sorted doubly linked list to bst using same nodes as in DLL Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sun, Jul 29, 2012 at 10:30 PM, Purani Sekar nagapur...@gmail.comwrote: convert sorted doubly linked list to bst using same nodes as in DLL -- You received this message because 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. -- - - - - - - - - - - - - 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.
Re: [algogeeks] Re: Microsoft online questions : DLL to bst??
A LinkedList is by itself is a BST such that one child node of each node is null. Do we need a simple BST or height balanced BST? On Tue, Jul 31, 2012 at 2:39 PM, Ashish Goel ashg...@gmail.com wrote: how would you do convert sorted doubly linked list to bst using same nodes as in DLL Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sun, Jul 29, 2012 at 10:30 PM, Purani Sekar nagapur...@gmail.comwrote: convert sorted doubly linked list to bst using same nodes as in DLL -- You received this message because 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.
Re: [algogeeks] Re: Microsoft online questions : DLL to bst??
Ishan, i am assuming that the list to BST should give a inorder traversal, and the logic of yours does not seem to give a right solution. try two different trees with 7 nodes, convert into LL and then back to BST, the answer is not same as the trees that we start with. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Jul 31, 2012 at 5:19 PM, Ishan Sood sood.ishaan2...@gmail.comwrote: 1. get the middle of the linked list and make it root 2. same for left half and right half recursivly a. get the middle of left half and make it left child. b. get middle of rite half and make it rite child. this is must b he logic for the qstn. :) Thank You, Ishan Sood. 9805660301 On Tue, Jul 31, 2012 at 3:09 PM, Ashish Goel ashg...@gmail.com wrote: how would you do convert sorted doubly linked list to bst using same nodes as in DLL Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sun, Jul 29, 2012 at 10:30 PM, Purani Sekar nagapur...@gmail.comwrote: convert sorted doubly linked list to bst using same nodes as in DLL -- You received this message because 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: Microsoft online questions : DLL to bst??
can you give the link within geeksforgeeks please Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Jul 31, 2012 at 4:13 PM, a g ag20071...@gmail.com wrote: check on geeksforgeeks.org On Tue, Jul 31, 2012 at 3:09 PM, Ashish Goel ashg...@gmail.com wrote: how would you do convert sorted doubly linked list to bst using same nodes as in DLL Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sun, Jul 29, 2012 at 10:30 PM, Purani Sekar nagapur...@gmail.comwrote: convert sorted doubly linked list to bst using same nodes as in DLL -- You received this message because 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: Microsoft online questions : DLL to bst??
how would you do convert sorted doubly linked list to bst using same nodes as in DLL Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sun, Jul 29, 2012 at 10:30 PM, Purani Sekar nagapur...@gmail.com wrote: convert sorted doubly linked list to bst using same nodes as in DLL -- You received this message because 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: Microsoft online questions : DLL to bst??
check on geeksforgeeks.org On Tue, Jul 31, 2012 at 3:09 PM, Ashish Goel ashg...@gmail.com wrote: how would you do convert sorted doubly linked list to bst using same nodes as in DLL Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sun, Jul 29, 2012 at 10:30 PM, Purani Sekar nagapur...@gmail.comwrote: convert sorted doubly linked list to bst using same nodes as in DLL -- You received this message because 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: Microsoft online questions : DLL to bst??
1. get the middle of the linked list and make it root 2. same for left half and right half recursivly a. get the middle of left half and make it left child. b. get middle of rite half and make it rite child. this is must b he logic for the qstn. :) Thank You, Ishan Sood. 9805660301 On Tue, Jul 31, 2012 at 3:09 PM, Ashish Goel ashg...@gmail.com wrote: how would you do convert sorted doubly linked list to bst using same nodes as in DLL Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sun, Jul 29, 2012 at 10:30 PM, Purani Sekar nagapur...@gmail.comwrote: convert sorted doubly linked list to bst using same nodes as in DLL -- You received this message because 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: Microsoft online questions
I think they asked same questions for intern and full time. The second round questions were: 1. given a string , remove the duplicates and print it in ascending order eg : accommodate op: acdemot 2. given a sorted array with a few numbers in between reversed. fix the array eg : 1 2 3 4 9 8 7 11 12 14 op :1 2 3 4 7 8 9 11 12 14 3. convert sorted doubly linked list to bst using same nodes as in DLL. again 3 questions. written. 1hr. 1. given a number N and an array, find the tuples in the array that have a difference equal to N 2. insert a value into a sorted circular singly linked list 3. given a node N, find the left most node in the BST in the level that contains N. eg: 7 / \ 5 9 / \ /\ 1 4 8 12 given node N : 8 output : 1 On Sun, Jul 29, 2012 at 9:38 PM, Tanuj Makkar tanujmakkar.de...@gmail.com wrote: Also if smeone cn post some questions/experience for microsoft intern/placementit will be a grt help Thanks Tanuj Makkar Delhi College Of Engineering -- 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/-/hLscLeYPBXQJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Microsoft online questions
Also if smeone cn post some questions/experience for microsoft intern/placementit will be a grt help Thanks Tanuj Makkar Delhi College Of Engineering -- 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/-/hLscLeYPBXQJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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
No It will not.
For negative number, it will fail.
On Sun, Jul 15, 2012 at 11:45 PM, Tanuj Makkar
tanujmakkar.de...@gmail.comwrote:
double round(double num)
{ return (int)(num+0.5)
}
will it work all the time?
..
didnt get itcan anyone explain it.thnx in advance.
On Friday, 26 August 2011 21:58:05 UTC+5:30, rahul sharma wrote:
hi guys...microsoft is coming to our campus..plz nyone tell their
recruitment procedure..n give me their previous xams question if nyone
has...but please tell me their selection procedure n
roundscuming after 2 days.plz reply soon.n tell me the
subjects to crack microsoft.nyon having info reply fast
plz..
--
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/-/mWeduVanassJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: microsoft
thnx amit.jst asked a stupid quesiton:)
On Mon, Jul 16, 2012 at 11:55 AM, Amit Jain aj201...@gmail.com wrote:
No It will not.
For negative number, it will fail.
On Sun, Jul 15, 2012 at 11:45 PM, Tanuj Makkar
tanujmakkar.de...@gmail.com wrote:
double round(double num)
{ return (int)(num+0.5)
}
will it work all the time?
..
didnt get itcan anyone explain it.thnx in advance.
On Friday, 26 August 2011 21:58:05 UTC+5:30, rahul sharma wrote:
hi guys...microsoft is coming to our campus..plz nyone tell their
recruitment procedure..n give me their previous xams question if nyone
has...but please tell me their selection procedure n
roundscuming after 2 days.plz reply soon.n tell me the
subjects to crack microsoft.nyon having info reply fast
plz..
--
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/-/mWeduVanassJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Re: microsoft
double round(double num)
{ return (int)(num+0.5)
}
will it work all the time?
..
didnt get itcan anyone explain it.thnx in advance.
On Friday, 26 August 2011 21:58:05 UTC+5:30, rahul sharma wrote:
hi guys...microsoft is coming to our campus..plz nyone tell their
recruitment procedure..n give me their previous xams question if nyone
has...but please tell me their selection procedure n
roundscuming after 2 days.plz reply soon.n tell me the
subjects to crack microsoft.nyon having info reply fast
plz..
--
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/-/mWeduVanassJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Microsoft interview qs
@Atul thanx for the code its working for the example you took...Please check the same for i/p abcmno,abcmnop Algo displays:- mno It should display mno mnop... -- You received this message because 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: Microsoft Interview Question
@All *Here is the working code: test on input {-1,5,3,-8,4,-6,9} and
{1,-1,2}*
Algo:
increment current till first +ve number(p) and decerement end till last
-ve number(n)
now consider only array between [p..n]
If current is negetive, increment current
If current is positive, swap it with end and decrement end, and current
(if current 0)
current =0;
if current =end then breck;
now n1=first negetive no. n2= last negetive number
similarly p1=first positive number and p2 last positive number
swap array elements in between n1,n2 and p1,p2 , like first element is last
element and secound to secound last .
JavaCode:
public class OneSideNegOtherPostive {
private int start, end, current;
public void getOrderedArray(int b[]) {
start = 0;
end = b.length - 1;
while (b[start] 0)
start++;
while (b[end] = 0)
end--;
int n = start, p = end;
current = n;
while (current end) {
while (b[current] 0 (current end)) {
current++;
continue;
}
ArrayUtils.swap(b, current, end);
ArrayUtils.printArray(b, \n b at current + current + end
+ end + ==);
current--;
end--;
if (current 0)
current = 0;
}
ArrayUtils.swapWithIn(b, n, p);
}
* public static void main(String args[]) {
OneSideNegOtherPostive oNegOtherPostive = new
OneSideNegOtherPostive();
//int a[] = { -1, 5, 3, -8, 4, -6, 9 };
int a[] = {1,-1,2};
ArrayUtils.printArray(a, Input array );
oNegOtherPostive.getOrderedArray(a);
ArrayUtils.printArray(a, \nOutput array );
}*
}
public class ArrayUtils {
public static void swap(Object a, Object b, int end) {
Object tmp = a;
a = b;
b = tmp;
}
public static void swap(int array[], int a, int b) {
int tmp = array[a];
array[a] = array[b];
array[b] = tmp;
}
public static void swapWithIn(int b[], int n, int p) {
int nEnd, nStart = n, pEnd = p, pStart;
int i = 0;
while (b[i] 0) {
i++;
}
pStart = i;
nEnd = pStart - 1;
while (nStart nEnd) {
ArrayUtils.swap(b, nStart, nEnd);
nStart++;
nEnd--;
}
while (pStart pEnd) {
ArrayUtils.swap(b, pStart, pEnd);
pStart++;
pEnd--;
}
}
public static void printArray(int a[], String message) {
System.out.print(message);
for (int x : a) {
System.out.print( + x);
}
}
}
On Sun, Jul 1, 2012 at 9:38 AM, Dave dave_and_da...@juno.com wrote:
@Navin: If I am correctly executing your algorithm on the data in the
original posting, {-1,5,3,-8,4,-6,9}, I get {-1,-6,-8,4,3,5,9}, when the
correct answer is {-1,-8,-6,5,3,4,9}. The array contains the correct
numbers, but the order of the positive numbers and the order of the negtive
numbers is not maintained. You can't swap a number from the front part of
the array with a number from the back part and expect the order of
positives and negatives to remain intact.
Dave
On Saturday, June 30, 2012 12:42:09 AM UTC-5, Navin Gupta wrote:
@Dave :- a minor change
Initially, decrement the end pointer till it points to positive number,
Now end points to the last negative number.
Now,
If current is negative , increment current
If current is positive , swap it with the element at end and decrement
current and end both
If current = end , then break.
Algo :-
cur = 0;
end = size - 1;
while ( a[end] 0 end 0 ) end - - ;
while ( cur end ) {
if( a[cur] 0 ) cur++;
else{
swap( a[cur], a[end] );
end - - ;
} // end of if-else
} // end of while
In the above example :- ( 1, -1, 2 ), current points to 1 (cur=0) and end
points to -1 (end =1 )after end has been decremented.
Now swap the element at current and end pointers.
Now cur = 0, end =0, break condition is reached. the output is :- ( -1,
1, 2 )
Please check.
Navin Kumar Gupta
Final Year, B.Tech (Hons.)
Computer Science Engg.
National Institute of Technology,Jamshedpur
Mob - (+91) 8285303045
On Friday, 29 June 2012 22:28:15 UTC+5:30, Dave wrote:
@Navin: Try this with {1,-1,2}. current points to the 1 and end points
to the 2. Since 1 is positive, the algorithm swaps the 1 and the 2, giving
{2,-1,1}. Then it decrements current to point outside the array and end to
point to the -1. How can this be right?
Dave
--
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/-/97r3CtynC8oJ.
To post to this group, send email to
[algogeeks] Re: Microsoft Interview Question
@Dave :- a minor change
Initially, decrement the end pointer till it points to positive number,
Now end points to the last negative number.
Now,
If current is negative , increment current
If current is positive , swap it with the element at end and decrement
current and end both
If current = end , then break.
Algo :-
cur = 0;
end = size - 1;
while ( a[end] 0 end 0 ) end - - ;
while ( cur end ) {
if( a[cur] 0 ) cur++;
else{
swap( a[cur], a[end] );
end - - ;
} // end of if-else
} // end of while
In the above example :- ( 1, -1, 2 ), current points to 1 (cur=0) and end
points to -1 (end =1 )after end has been decremented.
Now swap the element at current and end pointers.
Now cur = 0, end =0, break condition is reached. the output is :- ( -1, 1,
2 )
Please check.
Navin Kumar Gupta
Final Year, B.Tech (Hons.)
Computer Science Engg.
National Institute of Technology,Jamshedpur
Mob - (+91) 8285303045
On Friday, 29 June 2012 22:28:15 UTC+5:30, Dave wrote:
@Navin: Try this with {1,-1,2}. current points to the 1 and end points to
the 2. Since 1 is positive, the algorithm swaps the 1 and the 2, giving
{2,-1,1}. Then it decrements current to point outside the array and end to
point to the -1. How can this be right?
Dave
--
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/-/bseavL7x8OQJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Microsoft Interview Question
@Navin: If I am correctly executing your algorithm on the data in the
original posting, {-1,5,3,-8,4,-6,9}, I get {-1,-6,-8,4,3,5,9}, when the
correct answer is {-1,-8,-6,5,3,4,9}. The array contains the correct
numbers, but the order of the positive numbers and the order of the negtive
numbers is not maintained. You can't swap a number from the front part of
the array with a number from the back part and expect the order of
positives and negatives to remain intact.
Dave
On Saturday, June 30, 2012 12:42:09 AM UTC-5, Navin Gupta wrote:
@Dave :- a minor change
Initially, decrement the end pointer till it points to positive number,
Now end points to the last negative number.
Now,
If current is negative , increment current
If current is positive , swap it with the element at end and decrement
current and end both
If current = end , then break.
Algo :-
cur = 0;
end = size - 1;
while ( a[end] 0 end 0 ) end - - ;
while ( cur end ) {
if( a[cur] 0 ) cur++;
else{
swap( a[cur], a[end] );
end - - ;
} // end of if-else
} // end of while
In the above example :- ( 1, -1, 2 ), current points to 1 (cur=0) and end
points to -1 (end =1 )after end has been decremented.
Now swap the element at current and end pointers.
Now cur = 0, end =0, break condition is reached. the output is :- ( -1, 1,
2 )
Please check.
Navin Kumar Gupta
Final Year, B.Tech (Hons.)
Computer Science Engg.
National Institute of Technology,Jamshedpur
Mob - (+91) 8285303045
On Friday, 29 June 2012 22:28:15 UTC+5:30, Dave wrote:
@Navin: Try this with {1,-1,2}. current points to the 1 and end points to
the 2. Since 1 is positive, the algorithm swaps the 1 and the 2, giving
{2,-1,1}. Then it decrements current to point outside the array and end to
point to the -1. How can this be right?
Dave
--
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/-/97r3CtynC8oJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Microsoft Interview Question
+1 naveen On Thursday, June 28, 2012 8:29:26 PM UTC+5:30, Navin Gupta wrote: Keep two pointers - one at start of the array and other at end of the array Now current points to start of the array If current is negative , increment current If current is positive , swap it with the element at end and decrement current and end both If current = end , then break. Navin Kumar Gupta Final Year, B.Tech (Hons.) Computer Science Engg. National Institute of Technology,Jamshedpur Mobile - 8285303045 -- 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/-/hTWp_UkuDc8J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Microsoft Interview Question
@Navin: Try this with {1,-1,2}. current points to the 1 and end points to
the 2. Since 1 is positive, the algorithm swaps the 1 and the 2, giving
{2,-1,1}. Then it decrements current to point outside the array and end to
point to the -1. How can this be right?
Dave
On Thursday, June 28, 2012 9:59:26 AM UTC-5, Navin Gupta wrote:
Keep two pointers - one at start of the array and other at end of the
array
Now current points to start of the array
If current is negative , increment current
If current is positive , swap it with the element at end and decrement
current and end both
If current = end , then break.
Navin Kumar Gupta
Final Year, B.Tech (Hons.)
Computer Science Engg.
National Institute of Technology,Jamshedpur
Mobile - 8285303045
--
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/-/JW4NPf7xBTkJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Microsoft Interview Question
keep swaping left most -ve and left most positive untill counter reaches at the end of array, can be done in o(n) no extra space required.. 3rd year manit bhopal -- 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/-/5PTaaqy6FhMJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Microsoft Interview Question
Keep two pointers - one at start of the array and other at end of the array Now current points to start of the array If current is negative , increment current If current is positive , swap it with the element at end and decrement current and end both If current = end , then break. Navin Kumar Gupta Final Year, B.Tech (Hons.) Computer Science Engg. National Institute of Technology,Jamshedpur Mobile - 8285303045 -- 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/-/j13jp_PBk44J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Interview Question
@wgp the ques is to maintain the order intact.. -- You received this message because 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: Microsoft question
refer to this link http://www.ics.uci.edu/~eppstein/161/960130.html. or Using quicksort , it can be done in O(n). One more way to do this is to make min heap of size-k. Then insert elements from the original array.If element is greater than root of the heap,swap them.In the Last, root of the heap would be the kth smallest element On Wed, Jun 20, 2012 at 8:47 PM, ajeet ajeet.sing...@gmail.com wrote: Hi, It looks like, The interviewer is expecting MinHeap from you, If modification to array is permitted just build the heap in place (from end bubbleUp n-1 time) and extract K elements in sorted order Otherwise you need minimum O(K) memory Again if you want to use the quick-sort, I would prefer only using partition part of quick sort.. 1. Select any pivot 'P' 2. Partition the array.. 3. position of the pivot p 4. if p k ( kth min lies on left part) repeat again for k 5 if p k ( kth min lies on right part) repeat again for k-p 6 if p = k ( You are lucky) exit Again in worst case it is o(N2) -Ajeet Thanks -A On Wednesday, 20 June 2012 00:56:36 UTC+5:30, adarsh kumar wrote: This can be done using the concept of median of medians, wherein we can achieve linear time complexity in the worst case. This is a concept used in parallel algorithms too, check it out. On Mon, Jun 18, 2012 at 5:38 PM, Prem Nagarajan prem.cmna...@gmail.comwrote: @enchantress : This problem can be solved using quicksort in O(nlogn). No need to go for selection sort. But O(n) solution is needed. On Mon, Jun 18, 2012 at 2:50 PM, enchantress elaenjoy...@gmail.comwrote: Hi all, A variation of selection sort can be used which takes O(nk) time. for i 1 to k min_index = i for j i+1 to n if a[j] a[min_index] min_index = j swap(a[i],a[min_index]) required element : a[k] On Sunday, 17 June 2012 08:13:18 UTC+5:30, Prem Nagarajan wrote: Give an array of unsorted elements, find the kth smallest element in the array. The expected time complexity is O(n) and no extra memory space should be used. Quickselect algorithm can be used to obtain the solution. Can anyone explain how quickselect works? -- 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/-/FABBRabzVqMJhttps://groups.google.com/d/msg/algogeeks/-/FABBRabzVqMJ . 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. -- 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/-/sBvT2ztJpoUJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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.
[algogeeks] Re: Microsoft Interview Question
@akshat ur code doesn't give intact output, so i modified ur code and
here is the code :
int j=0,k=0;
for (i = 0; i n; ++i)
{
if(a[i]0)
{
a[j] = a[i];
j++;
}
else
{
temp[k] = a[i];
k++;
}
}
k=0;
for (i = j; i n; ++i)
{
a[i] = temp[k];
k++;
}
On Jun 21, 1:47 pm, Rishabh Agarwal rishabh...@gmail.com wrote:
@Abhi: if you apply quick sort then again the order will will not be intact
--
You received this message because 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: Microsoft Interview Question
guys this is my solution to the problem, it's a bit sloppy but as far as I
checked it was working please have a go at it?
#include stdio.h
#include stdlib.h
int main() {
int arr1[] = {0,-5,3,0,4,-6,-9};
int arr2[7];
int j = 0;
for ( int i = 0 ; i 7 ; i++ ) {
//loop for -ve numbers
if ( arr1[i] 0 )
arr2[j++] = arr1[i];
}
//accomodate all the zeros if any
for ( int i = 0 ; i 7 ; i++ ) {
if ( arr1[i] == 0 )
arr2[j++] = arr1[i];
}
for ( int i = 0 ; i 7 ; i++ ) {
//loop for +ve numbers
if ( arr1[i] 0 )
arr2[j++] = arr1[i];
}
//print arr1 for reference
printf(\nInitially the array was);
for ( int i = 0 ; i 7 ; i++ )
printf(\narr1[%d]: %d,i,arr1[i]);
printf(\n\n);
//print arr2
for ( int i = 0 ; i 7 ; i++ )
printf(\narr2[%d]: %d,i,arr2[i]);
return 0;
}
On Wednesday, June 13, 2012 9:49:49 PM UTC+5:30, Krishna Kishore wrote:
Given a array of integers both positive and negative and you need to shift
positive numbers to one side
and negative numbers to other side with the order intact.
ex. {-1,5,3,-8,4,-6,9} to {-1,-8,-6,5,3,4,9}. This should be done 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/-/H8ANlbL0dmEJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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 Interview Question
can this be done in single pass in O(n) .
On Thu, Jun 21, 2012 at 8:10 PM, rusty dafc1...@gmail.com wrote:
guys this is my solution to the problem, it's a bit sloppy but as far as I
checked it was working please have a go at it?
#include stdio.h
#include stdlib.h
int main() {
int arr1[] = {0,-5,3,0,4,-6,-9};
int arr2[7];
int j = 0;
for ( int i = 0 ; i 7 ; i++ ) {
//loop for -ve numbers
if ( arr1[i] 0 )
arr2[j++] = arr1[i];
}
//accomodate all the zeros if any
for ( int i = 0 ; i 7 ; i++ ) {
if ( arr1[i] == 0 )
arr2[j++] = arr1[i];
}
for ( int i = 0 ; i 7 ; i++ ) {
//loop for +ve numbers
if ( arr1[i] 0 )
arr2[j++] = arr1[i];
}
//print arr1 for reference
printf(\nInitially the array was);
for ( int i = 0 ; i 7 ; i++ )
printf(\narr1[%d]: %d,i,arr1[i]);
printf(\n\n);
//print arr2
for ( int i = 0 ; i 7 ; i++ )
printf(\narr2[%d]: %d,i,arr2[i]);
return 0;
}
On Wednesday, June 13, 2012 9:49:49 PM UTC+5:30, Krishna Kishore wrote:
Given a array of integers both positive and negative and you need to
shift positive numbers to one side
and negative numbers to other side with the order intact.
ex. {-1,5,3,-8,4,-6,9} to {-1,-8,-6,5,3,4,9}. This should be done 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/-/H8ANlbL0dmEJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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.
Re: [algogeeks] Re: Microsoft question
Can't we use k iterations of bubble sort ? On Jun 18, 2012 2:11 PM, Ramindar Singh ramin...@gmail.com wrote: We can use Median of medians http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm On Sunday, 17 June 2012 08:13:18 UTC+5:30, Prem Nagarajan wrote: Give an array of unsorted elements, find the kth smallest element in the array. The expected time complexity is O(n) and no extra memory space should be used. Quickselect algorithm can be used to obtain the solution. Can anyone explain how quickselect works? -- 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/-/4lQsacmUPYUJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Microsoft Interview Question
single traversal n O(n) are 2 diff things...plz specify??? -- You received this message because 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: Microsoft Interview Question
Well they are the same you're going over an array once. As long as they are not nested they are still counted as O(n) because leading constants are dropped, at least that's what my acumen says. Need inputs on this guys! On Friday, June 22, 2012 12:53:02 AM UTC+5:30, suzi wrote: single traversal n O(n) are 2 diff things...plz specify??? -- 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/-/2cjTXWrkv7wJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Interview Question
i mean o(n) in single traversal . On Fri, Jun 22, 2012 at 12:53 AM, sanjay pandey sanjaypandey...@gmail.comwrote: single traversal n O(n) are 2 diff things...plz specify??? -- You received this message because 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.
Re: [algogeeks] Re: Microsoft question
Hi, It looks like, The interviewer is expecting MinHeap from you, If modification to array is permitted just build the heap in place (from end bubbleUp n-1 time) and extract K elements in sorted order Otherwise you need minimum O(K) memory Again if you want to use the quick-sort, I would prefer only using partition part of quick sort.. 1. Select any pivot 'P' 2. Partition the array.. 3. position of the pivot p 4. if p k ( kth min lies on left part) repeat again for k 5 if p k ( kth min lies on right part) repeat again for k-p 6 if p = k ( You are lucky) exit Again in worst case it is o(N2) -Ajeet Thanks -A On Wednesday, 20 June 2012 00:56:36 UTC+5:30, adarsh kumar wrote: This can be done using the concept of median of medians, wherein we can achieve linear time complexity in the worst case. This is a concept used in parallel algorithms too, check it out. On Mon, Jun 18, 2012 at 5:38 PM, Prem Nagarajan prem.cmna...@gmail.comwrote: @enchantress : This problem can be solved using quicksort in O(nlogn). No need to go for selection sort. But O(n) solution is needed. On Mon, Jun 18, 2012 at 2:50 PM, enchantress elaenjoy...@gmail.comwrote: Hi all, A variation of selection sort can be used which takes O(nk) time. for i 1 to k min_index = i for j i+1 to n if a[j] a[min_index] min_index = j swap(a[i],a[min_index]) required element : a[k] On Sunday, 17 June 2012 08:13:18 UTC+5:30, Prem Nagarajan wrote: Give an array of unsorted elements, find the kth smallest element in the array. The expected time complexity is O(n) and no extra memory space should be used. Quickselect algorithm can be used to obtain the solution. Can anyone explain how quickselect works? -- 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/-/FABBRabzVqMJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/sBvT2ztJpoUJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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
This can be done using the concept of median of medians, wherein we can achieve linear time complexity in the worst case. This is a concept used in parallel algorithms too, check it out. On Mon, Jun 18, 2012 at 5:38 PM, Prem Nagarajan prem.cmna...@gmail.comwrote: @enchantress : This problem can be solved using quicksort in O(nlogn). No need to go for selection sort. But O(n) solution is needed. On Mon, Jun 18, 2012 at 2:50 PM, enchantress elaenjoy...@gmail.comwrote: Hi all, A variation of selection sort can be used which takes O(nk) time. for i 1 to k min_index = i for j i+1 to n if a[j] a[min_index] min_index = j swap(a[i],a[min_index]) required element : a[k] On Sunday, 17 June 2012 08:13:18 UTC+5:30, Prem Nagarajan wrote: Give an array of unsorted elements, find the kth smallest element in the array. The expected time complexity is O(n) and no extra memory space should be used. Quickselect algorithm can be used to obtain the solution. Can anyone explain how quickselect works? -- 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/-/FABBRabzVqMJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Re: Microsoft question
We can use Median of medians http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm On Sunday, 17 June 2012 08:13:18 UTC+5:30, Prem Nagarajan wrote: Give an array of unsorted elements, find the kth smallest element in the array. The expected time complexity is O(n) and no extra memory space should be used. Quickselect algorithm can be used to obtain the solution. Can anyone explain how quickselect works? -- 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/-/4lQsacmUPYUJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Microsoft question
Hi all, A variation of selection sort can be used which takes O(nk) time. for i 1 to k min_index = i for j i+1 to n if a[j] a[min_index] min_index = j swap(a[i],a[min_index]) required element : a[k] On Sunday, 17 June 2012 08:13:18 UTC+5:30, Prem Nagarajan wrote: Give an array of unsorted elements, find the kth smallest element in the array. The expected time complexity is O(n) and no extra memory space should be used. Quickselect algorithm can be used to obtain the solution. Can anyone explain how quickselect works? -- 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/-/FABBRabzVqMJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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
@enchantress : This problem can be solved using quicksort in O(nlogn). No need to go for selection sort. But O(n) solution is needed. On Mon, Jun 18, 2012 at 2:50 PM, enchantress elaenjoy...@gmail.com wrote: Hi all, A variation of selection sort can be used which takes O(nk) time. for i 1 to k min_index = i for j i+1 to n if a[j] a[min_index] min_index = j swap(a[i],a[min_index]) required element : a[k] On Sunday, 17 June 2012 08:13:18 UTC+5:30, Prem Nagarajan wrote: Give an array of unsorted elements, find the kth smallest element in the array. The expected time complexity is O(n) and no extra memory space should be used. Quickselect algorithm can be used to obtain the solution. Can anyone explain how quickselect works? -- 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/-/FABBRabzVqMJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Microsoft Interview Question
@ayush goel couldnt really understand your algo , can you please explain
little bit more .
On Wednesday, 13 June 2012 21:49:49 UTC+5:30, Krishna Kishore wrote:
Given a array of integers both positive and negative and you need to shift
positive numbers to one side
and negative numbers to other side with the order intact.
ex. {-1,5,3,-8,4,-6,9} to {-1,-8,-6,5,3,4,9}. This should be done 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/-/5i2bW0t0pgQJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Microsoft Question
Queue can be defined as a priority queue where priority decreases with time. Hence an element inserted later has lower priority and goes to back of queue. (FIFO) Stack can be defined as a priority queue where priority increases with time.Hence an element inserted later has higher priority and goes to front of stack.(LIFO) On Tuesday, 13 September 2011 02:15:01 UTC+5:30, Ankur Garg wrote: How to Implement a Queue with a Priority Queue Similarly how woud you implement Stack with Priority Queue -- 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/-/SDq590tCZHkJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Microsoft Interview Question
Root of a graph can be any node whose in-degree is zero. i.e. there are no nodes pointing to that node. It can be found by using O( |V| ) space and O( |E| ) time . Now we can choose any node whose in-degree is zero if present. or choose any random node and itf DFS-tree is the desired tree. Time complexity of DFS is O(|E|). On Monday, 12 March 2012 15:05:49 UTC+5:30, Umer Farooq wrote: Hello friends, I recently had an onsite MS interview. One of the questions that they asked was: - Given a directed graph, write a program that takes root of the graph and returns root of a tree which comprises of all the nodes of the graph in the same way as they appeared in the graph (the graph contains no cycles). -- Umer -- 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/-/l-xn8uxltrwJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Microsoft interview question
@Gaurav: you are taking ia and ib as int so they will have 32 bits in
Java. So you can not set the bits for numbers in the array greater
than 32.
e.g if you have a[i]=59876 so you would want to set the 59876th bit in
ia : ia=ia | (159876) but that is not possible. How do you handle
this?
Also how do you handle the case for negative numbers??
What I think we can do is:
If we take ia and ib as BigInteger in Java then we don't have that
constraint of 32 bits. I tried it out it works for large no as 35000
instantly.
But that still doesn't solve the problem of -ve numbers.
regards
Abhishek Khanna
On May 20, 1:42 am, GAURAV CHAWLA togauravcha...@gmail.com wrote:
we can do it bitwise...
i can set the corresponding bit by 1 of any int ...
lets take
int ia,ib=0;
and set the a[i]th bit of ia as 1 ,
and similar for bth array and ib ...
and finally check.. if(ia==ib){permutation of each other}
hope this will work..
On Sun, May 20, 2012 at 1:39 AM, malay chakrabarti m1234...@gmail.comwrote:
dat defeats the o(1) space constraint. :-)
On May 19, 2012 8:05 PM, HARSHIT PAHUJA hpahuja.mn...@gmail.com wrote:
@malay --- we can do it by precomputing the prime arrays
On Sun, May 20, 2012 at 1:10 AM, malay chakrabarti
m1234...@gmail.comwrote:
method is ryt but to find ith prime u cannot to it in constant time.
On May 19, 2012 7:30 PM, HARSHIT PAHUJA hpahuja.mn...@gmail.com
wrote:
given 2 unsorted integer arrays a and b of equal size. Determine if b
is a permutation of a. Can this be done in O(n) time and O(1) space ?
please help me with my solution
suppose a -- 3 5 4
b -- 4 3 5
now we replace a[i] with a[i]..th prime number and b with b[i] .. th
prime number
now array a becomes 5 11 7
array b becomes 7 5 11
now we take product of elements of array a and do the same with array
b elements
if product is equal then b is a permutation of a
--
You received this message because 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.
--
HARSHIT PAHUJA
M.N.N.I.T.
ALLAHABAD
--
You received this message because 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.
--
Regards,
GAURAV CHAWLA
+919992635751
+919654127192
--
You received this message because 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: Microsoft interview question
@Piyush: Did you even try this on any examples? If not, try a = {0,1,2,3}
and b = {0,2,2,2}.
Dave
On Sunday, May 20, 2012 1:39:25 AM UTC-5, Kalyan wrote:
Piyush. I think we can use your logic. But You should check the product
also.
Have 4 variables, sum_a,sum_b , prod_a, prod_b
Calculate Sum and product of array 'a' and store it in sum_a,prod_a
Calculate Sum and product of array 'b' and store it in sum_b,prod_b
if sum_a=sum_b prod_a==prod_b then these 2 arrays are permutations
of each other.
Space = O(1)
Time=O(n)
I think this should work. Please correct me if you find mistakes.
On 5/20/12, anuj agarwal coolbuddy...@gmail.com wrote:
U are checking if the sum is same or not.. which can be same even if the
elements are different.
On Sun, May 20, 2012 at 11:54 AM, Piyush Khandelwal
piyushkhandelwal...@gmail.com wrote:
Hiii!! I have some idea about the solution. Please notify me if i am
wrong
a= [ 4,3,5 ] and b= [ 3,5,4 ]
diff=0;
for (i=0; in;i++)
{ diff= diff+a[i]-b[i];
}
if diff == 0
print: permutation
else
print: not permutation
On 20 May 2012 07:2 0, Dave dave_and_da...@juno.com wrote:
@Harshit: These are a few unanswered questions that came to mind when
I
read your solution attempt: What do you do with negative elements?
What
is
the -12th prime number? How do you deal with overflow in the cases
where
you have a lot of large prime numbers and the product exceeds your
native
data types?
Dave
On Saturday, May 19, 2012 2:29:52 PM UTC-5, harshit pahuja wrote:
given 2 unsorted integer arrays a and b of equal size. Determine if b
is
a permutation of a. Can this be done in O(n) time and O(1) space ?
please help me with my solution
suppose a -- 3 5 4
b -- 4 3 5
now we replace a[i] with a[i]..th prime number and b with b[i] .. th
prime number
now array a becomes 5 11 7
array b becomes 7 5 11
now we take product of elements of array a and do the same with array
b
elements
if product is equal then b is a permutation of a
--
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/-/WEW0M5VUUVEJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
*Piyush Khandelwal***
Mobile No: 91-8447229204
91-9808479765
--
You received this message because 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.
--
*
*
*Kalyanasundaram N*
*BE 2nd year, CSE*
*College of Engineering Guindy,*
*Chennai-600025*
*
*
--
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/-/i-WLn7rdzDYJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Microsoft interview question
No way u can do it in O(1) space and O(n) time.sols above are not gonna work..yeah, it is possible in O(n) space and O(n) time. On May 20, 12:29 am, HARSHIT PAHUJA hpahuja.mn...@gmail.com wrote: given 2 unsorted integer arrays a and b of equal size. Determine if b is a permutation of a. Can this be done in O(n) time and O(1) space ? please help me with my solution suppose a -- 3 5 4 b -- 4 3 5 now we replace a[i] with a[i]..th prime number and b with b[i] .. th prime number now array a becomes 5 11 7 array b becomes 7 5 11 now we take product of elements of array a and do the same with array b elements if product is equal then b is a permutation of a -- You received this message because 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: Microsoft interview question
Dave,
Cant we have a hash table with the item as key and its count as value (walk
over array A and build HT).
For permutation check, walk over second array and start reducing the count
and remove when count becomes zero for that particular key. If some char
not there in HT, return false, else return true.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, May 21, 2012 at 6:14 PM, Dave dave_and_da...@juno.com wrote:
@Piyush: Did you even try this on any examples? If not, try a = {0,1,2,3}
and b = {0,2,2,2}.
Dave
On Sunday, May 20, 2012 1:39:25 AM UTC-5, Kalyan wrote:
Piyush. I think we can use your logic. But You should check the product
also.
Have 4 variables, sum_a,sum_b , prod_a, prod_b
Calculate Sum and product of array 'a' and store it in sum_a,prod_a
Calculate Sum and product of array 'b' and store it in sum_b,prod_b
if sum_a=sum_b prod_a==prod_b then these 2 arrays are permutations
of each other.
Space = O(1)
Time=O(n)
I think this should work. Please correct me if you find mistakes.
On 5/20/12, anuj agarwal coolbuddy...@gmail.com wrote:
U are checking if the sum is same or not.. which can be same even if
the
elements are different.
On Sun, May 20, 2012 at 11:54 AM, Piyush Khandelwal
piyushkhandelwal...@gmail.com wrote:
Hiii!! I have some idea about the solution. Please notify me if i am
wrong
a= [ 4,3,5 ] and b= [ 3,5,4 ]
diff=0;
for (i=0; in;i++)
{ diff= diff+a[i]-b[i];
}
if diff == 0
print: permutation
else
print: not permutation
On 20 May 2012 07:2 0, Dave dave_and_da...@juno.com wrote:
@Harshit: These are a few unanswered questions that came to mind when
I
read your solution attempt: What do you do with negative elements?
What
is
the -12th prime number? How do you deal with overflow in the cases
where
you have a lot of large prime numbers and the product exceeds your
native
data types?
Dave
On Saturday, May 19, 2012 2:29:52 PM UTC-5, harshit pahuja wrote:
given 2 unsorted integer arrays a and b of equal size. Determine if
b is
a permutation of a. Can this be done in O(n) time and O(1) space ?
please help me with my solution
suppose a -- 3 5 4
b -- 4 3 5
now we replace a[i] with a[i]..th prime number and b with b[i] ..
th
prime number
now array a becomes 5 11 7
array b becomes 7 5 11
now we take product of elements of array a and do the same with
array b
elements
if product is equal then b is a permutation of a
--
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/-/WEW0M5VUUVEJhttps://groups.google.com/d/msg/algogeeks/-/WEW0M5VUUVEJ.
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.
--
*Piyush Khandelwal***
Mobile No: 91-8447229204
91-9808479765
--
You received this message because 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.
--
*
*
*Kalyanasundaram N*
*BE 2nd year, CSE*
*College of Engineering Guindy,*
*Chennai-600025*
*
*
--
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/-/i-WLn7rdzDYJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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
[algogeeks] Re: Microsoft interview question
^not an O(n)
On May 21, 6:53 pm, Ashish Goel ashg...@gmail.com wrote:
Dave,
Cant we have a hash table with the item as key and its count as value (walk
over array A and build HT).
For permutation check, walk over second array and start reducing the count
and remove when count becomes zero for that particular key. If some char
not there in HT, return false, else return true.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, May 21, 2012 at 6:14 PM, Dave dave_and_da...@juno.com wrote:
@Piyush: Did you even try this on any examples? If not, try a = {0,1,2,3}
and b = {0,2,2,2}.
Dave
On Sunday, May 20, 2012 1:39:25 AM UTC-5, Kalyan wrote:
Piyush. I think we can use your logic. But You should check the product
also.
Have 4 variables, sum_a,sum_b , prod_a, prod_b
Calculate Sum and product of array 'a' and store it in sum_a,prod_a
Calculate Sum and product of array 'b' and store it in sum_b,prod_b
if sum_a=sum_b prod_a==prod_b then these 2 arrays are permutations
of each other.
Space = O(1)
Time=O(n)
I think this should work. Please correct me if you find mistakes.
On 5/20/12, anuj agarwal coolbuddy...@gmail.com wrote:
U are checking if the sum is same or not.. which can be same even if
the
elements are different.
On Sun, May 20, 2012 at 11:54 AM, Piyush Khandelwal
piyushkhandelwal...@gmail.com wrote:
Hiii!! I have some idea about the solution. Please notify me if i am
wrong
a= [ 4,3,5 ] and b= [ 3,5,4 ]
diff=0;
for (i=0; in;i++)
{ diff= diff+a[i]-b[i];
}
if diff == 0
print: permutation
else
print: not permutation
On 20 May 2012 07:2 0, Dave dave_and_da...@juno.com wrote:
@Harshit: These are a few unanswered questions that came to mind when
I
read your solution attempt: What do you do with negative elements?
What
is
the -12th prime number? How do you deal with overflow in the cases
where
you have a lot of large prime numbers and the product exceeds your
native
data types?
Dave
On Saturday, May 19, 2012 2:29:52 PM UTC-5, harshit pahuja wrote:
given 2 unsorted integer arrays a and b of equal size. Determine if
b is
a permutation of a. Can this be done in O(n) time and O(1) space ?
please help me with my solution
suppose a -- 3 5 4
b -- 4 3 5
now we replace a[i] with a[i]..th prime number and b with b[i] ..
th
prime number
now array a becomes 5 11 7
array b becomes 7 5 11
now we take product of elements of array a and do the same with
array b
elements
if product is equal then b is a permutation of a
--
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/-/WEW0M5VUUVEJhttps://groups.google.com/d/msg/algogeeks/-/WEW0M5VUUVEJ.
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.
--
*Piyush Khandelwal***
Mobile No: 91-8447229204
91-9808479765
--
You received this message because 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.
--
*
*
*Kalyanasundaram N*
*BE 2nd year, CSE*
*College of Engineering Guindy,*
*Chennai-600025*
*
*
--
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/-/i-WLn7rdzDYJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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
[algogeeks] Re: Microsoft interview question
in space
On May 21, 6:53 pm, Ashish Goel ashg...@gmail.com wrote:
Dave,
Cant we have a hash table with the item as key and its count as value (walk
over array A and build HT).
For permutation check, walk over second array and start reducing the count
and remove when count becomes zero for that particular key. If some char
not there in HT, return false, else return true.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, May 21, 2012 at 6:14 PM, Dave dave_and_da...@juno.com wrote:
@Piyush: Did you even try this on any examples? If not, try a = {0,1,2,3}
and b = {0,2,2,2}.
Dave
On Sunday, May 20, 2012 1:39:25 AM UTC-5, Kalyan wrote:
Piyush. I think we can use your logic. But You should check the product
also.
Have 4 variables, sum_a,sum_b , prod_a, prod_b
Calculate Sum and product of array 'a' and store it in sum_a,prod_a
Calculate Sum and product of array 'b' and store it in sum_b,prod_b
if sum_a=sum_b prod_a==prod_b then these 2 arrays are permutations
of each other.
Space = O(1)
Time=O(n)
I think this should work. Please correct me if you find mistakes.
On 5/20/12, anuj agarwal coolbuddy...@gmail.com wrote:
U are checking if the sum is same or not.. which can be same even if
the
elements are different.
On Sun, May 20, 2012 at 11:54 AM, Piyush Khandelwal
piyushkhandelwal...@gmail.com wrote:
Hiii!! I have some idea about the solution. Please notify me if i am
wrong
a= [ 4,3,5 ] and b= [ 3,5,4 ]
diff=0;
for (i=0; in;i++)
{ diff= diff+a[i]-b[i];
}
if diff == 0
print: permutation
else
print: not permutation
On 20 May 2012 07:2 0, Dave dave_and_da...@juno.com wrote:
@Harshit: These are a few unanswered questions that came to mind when
I
read your solution attempt: What do you do with negative elements?
What
is
the -12th prime number? How do you deal with overflow in the cases
where
you have a lot of large prime numbers and the product exceeds your
native
data types?
Dave
On Saturday, May 19, 2012 2:29:52 PM UTC-5, harshit pahuja wrote:
given 2 unsorted integer arrays a and b of equal size. Determine if
b is
a permutation of a. Can this be done in O(n) time and O(1) space ?
please help me with my solution
suppose a -- 3 5 4
b -- 4 3 5
now we replace a[i] with a[i]..th prime number and b with b[i] ..
th
prime number
now array a becomes 5 11 7
array b becomes 7 5 11
now we take product of elements of array a and do the same with
array b
elements
if product is equal then b is a permutation of a
--
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/-/WEW0M5VUUVEJhttps://groups.google.com/d/msg/algogeeks/-/WEW0M5VUUVEJ.
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.
--
*Piyush Khandelwal***
Mobile No: 91-8447229204
91-9808479765
--
You received this message because 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.
--
*
*
*Kalyanasundaram N*
*BE 2nd year, CSE*
*College of Engineering Guindy,*
*Chennai-600025*
*
*
--
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/-/i-WLn7rdzDYJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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
Re: [algogeeks] Re: Microsoft interview question
@Ashish: Using a hash table violates the O(1) space requirement given in
the original problem.
Dave
On Monday, May 21, 2012 8:53:44 AM UTC-5, ashgoel wrote:
Dave,
Cant we have a hash table with the item as key and its count as value
(walk over array A and build HT).
For permutation check, walk over second array and start reducing the count
and remove when count becomes zero for that particular key. If some char
not there in HT, return false, else return true.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, May 21, 2012 at 6:14 PM, Dave dave_and_da...@juno.com wrote:
@Piyush: Did you even try this on any examples? If not, try a = {0,1,2,3}
and b = {0,2,2,2}.
Dave
On Sunday, May 20, 2012 1:39:25 AM UTC-5, Kalyan wrote:
Piyush. I think we can use your logic. But You should check the product
also.
Have 4 variables, sum_a,sum_b , prod_a, prod_b
Calculate Sum and product of array 'a' and store it in sum_a,prod_a
Calculate Sum and product of array 'b' and store it in sum_b,prod_b
if sum_a=sum_b prod_a==prod_b then these 2 arrays are permutations
of each other.
Space = O(1)
Time=O(n)
I think this should work. Please correct me if you find mistakes.
On 5/20/12, anuj agarwal coolbuddy...@gmail.com wrote:
U are checking if the sum is same or not.. which can be same even if
the
elements are different.
On Sun, May 20, 2012 at 11:54 AM, Piyush Khandelwal
piyushkhandelwal...@gmail.com wrote:
Hiii!! I have some idea about the solution. Please notify me if i am
wrong
a= [ 4,3,5 ] and b= [ 3,5,4 ]
diff=0;
for (i=0; in;i++)
{ diff= diff+a[i]-b[i];
}
if diff == 0
print: permutation
else
print: not permutation
On 20 May 2012 07:2 0, Dave dave_and_da...@juno.com wrote:
@Harshit: These are a few unanswered questions that came to mind
when I
read your solution attempt: What do you do with negative elements?
What
is
the -12th prime number? How do you deal with overflow in the cases
where
you have a lot of large prime numbers and the product exceeds your
native
data types?
Dave
On Saturday, May 19, 2012 2:29:52 PM UTC-5, harshit pahuja wrote:
given 2 unsorted integer arrays a and b of equal size. Determine if
b is
a permutation of a. Can this be done in O(n) time and O(1) space ?
please help me with my solution
suppose a -- 3 5 4
b -- 4 3 5
now we replace a[i] with a[i]..th prime number and b with b[i] ..
th
prime number
now array a becomes 5 11 7
array b becomes 7 5 11
now we take product of elements of array a and do the same with
array b
elements
if product is equal then b is a permutation of a
--
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/-/WEW0M5VUUVEJhttps://groups.google.com/d/msg/algogeeks/-/WEW0M5VUUVEJ.
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.
--
*Piyush Khandelwal***
Mobile No: 91-8447229204
91-9808479765
--
You received this message because 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.
--
*
*
*Kalyanasundaram N*
*BE 2nd year, CSE*
*College of Engineering Guindy,*
*Chennai-600025*
*
*
--
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/-/i-WLn7rdzDYJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
Re: [algogeeks] Re: Microsoft interview question
constant space vs no additional space and then O(n) time complexity not
possible..
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, May 21, 2012 at 8:01 PM, Dave dave_and_da...@juno.com wrote:
@Ashish: Using a hash table violates the O(1) space requirement given in
the original problem.
Dave
On Monday, May 21, 2012 8:53:44 AM UTC-5, ashgoel wrote:
Dave,
Cant we have a hash table with the item as key and its count as value
(walk over array A and build HT).
For permutation check, walk over second array and start reducing the
count and remove when count becomes zero for that particular key. If some
char not there in HT, return false, else return true.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, May 21, 2012 at 6:14 PM, Dave dave_and_da...@juno.com wrote:
@Piyush: Did you even try this on any examples? If not, try a =
{0,1,2,3} and b = {0,2,2,2}.
Dave
On Sunday, May 20, 2012 1:39:25 AM UTC-5, Kalyan wrote:
Piyush. I think we can use your logic. But You should check the product
also.
Have 4 variables, sum_a,sum_b , prod_a, prod_b
Calculate Sum and product of array 'a' and store it in sum_a,prod_a
Calculate Sum and product of array 'b' and store it in sum_b,prod_b
if sum_a=sum_b prod_a==prod_b then these 2 arrays are permutations
of each other.
Space = O(1)
Time=O(n)
I think this should work. Please correct me if you find mistakes.
On 5/20/12, anuj agarwal coolbuddy...@gmail.com wrote:
U are checking if the sum is same or not.. which can be same even if
the
elements are different.
On Sun, May 20, 2012 at 11:54 AM, Piyush Khandelwal
piyushkhandelwal...@gmail.com wrote:
Hiii!! I have some idea about the solution. Please notify me if i am
wrong
a= [ 4,3,5 ] and b= [ 3,5,4 ]
diff=0;
for (i=0; in;i++)
{ diff= diff+a[i]-b[i];
}
if diff == 0
print: permutation
else
print: not permutation
On 20 May 2012 07:2 0, Dave dave_and_da...@juno.com wrote:
@Harshit: These are a few unanswered questions that came to mind
when I
read your solution attempt: What do you do with negative elements?
What
is
the -12th prime number? How do you deal with overflow in the cases
where
you have a lot of large prime numbers and the product exceeds your
native
data types?
Dave
On Saturday, May 19, 2012 2:29:52 PM UTC-5, harshit pahuja wrote:
given 2 unsorted integer arrays a and b of equal size. Determine
if b is
a permutation of a. Can this be done in O(n) time and O(1) space ?
please help me with my solution
suppose a -- 3 5 4
b -- 4 3 5
now we replace a[i] with a[i]..th prime number and b with b[i] ..
th
prime number
now array a becomes 5 11 7
array b becomes 7 5 11
now we take product of elements of array a and do the same with
array b
elements
if product is equal then b is a permutation of a
--
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/-/WEW0M5VUUVEJhttps://groups.google.com/d/msg/algogeeks/-/WEW0M5VUUVEJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscribe@**googlegr**oups.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.
--
*Piyush Khandelwal***
Mobile No: 91-8447229204
91-9808479765
--
You received this message because 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@**googlegr**oups.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@**googlegr**oups.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.
--
*
*
*Kalyanasundaram N*
*BE 2nd year, CSE*
*College of Engineering Guindy,*
*Chennai-600025*
*
*
--
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/**
Re: [algogeeks] Re: Microsoft interview question
@ashish.. it wont be constant space then.. surely it will be o(n) though
On Mon, May 21, 2012 at 7:23 PM, Ashish Goel ashg...@gmail.com wrote:
Dave,
Cant we have a hash table with the item as key and its count as value
(walk over array A and build HT).
For permutation check, walk over second array and start reducing the count
and remove when count becomes zero for that particular key. If some char
not there in HT, return false, else return true.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, May 21, 2012 at 6:14 PM, Dave dave_and_da...@juno.com wrote:
@Piyush: Did you even try this on any examples? If not, try a = {0,1,2,3}
and b = {0,2,2,2}.
Dave
On Sunday, May 20, 2012 1:39:25 AM UTC-5, Kalyan wrote:
Piyush. I think we can use your logic. But You should check the product
also.
Have 4 variables, sum_a,sum_b , prod_a, prod_b
Calculate Sum and product of array 'a' and store it in sum_a,prod_a
Calculate Sum and product of array 'b' and store it in sum_b,prod_b
if sum_a=sum_b prod_a==prod_b then these 2 arrays are permutations
of each other.
Space = O(1)
Time=O(n)
I think this should work. Please correct me if you find mistakes.
On 5/20/12, anuj agarwal coolbuddy...@gmail.com wrote:
U are checking if the sum is same or not.. which can be same even if
the
elements are different.
On Sun, May 20, 2012 at 11:54 AM, Piyush Khandelwal
piyushkhandelwal...@gmail.com wrote:
Hiii!! I have some idea about the solution. Please notify me if i am
wrong
a= [ 4,3,5 ] and b= [ 3,5,4 ]
diff=0;
for (i=0; in;i++)
{ diff= diff+a[i]-b[i];
}
if diff == 0
print: permutation
else
print: not permutation
On 20 May 2012 07:2 0, Dave dave_and_da...@juno.com wrote:
@Harshit: These are a few unanswered questions that came to mind
when I
read your solution attempt: What do you do with negative elements?
What
is
the -12th prime number? How do you deal with overflow in the cases
where
you have a lot of large prime numbers and the product exceeds your
native
data types?
Dave
On Saturday, May 19, 2012 2:29:52 PM UTC-5, harshit pahuja wrote:
given 2 unsorted integer arrays a and b of equal size. Determine if
b is
a permutation of a. Can this be done in O(n) time and O(1) space ?
please help me with my solution
suppose a -- 3 5 4
b -- 4 3 5
now we replace a[i] with a[i]..th prime number and b with b[i] ..
th
prime number
now array a becomes 5 11 7
array b becomes 7 5 11
now we take product of elements of array a and do the same with
array b
elements
if product is equal then b is a permutation of a
--
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/-/WEW0M5VUUVEJhttps://groups.google.com/d/msg/algogeeks/-/WEW0M5VUUVEJ.
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.
--
*Piyush Khandelwal***
Mobile No: 91-8447229204
91-9808479765
--
You received this message because 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.
--
*
*
*Kalyanasundaram N*
*BE 2nd year, CSE*
*College of Engineering Guindy,*
*Chennai-600025*
*
*
--
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/-/i-WLn7rdzDYJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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
Re: [algogeeks] Re: Microsoft interview question
a[] = [-1,-3,4,0,7,0,36,2,-3] b[] = [0,0,6,2,-1,9,28,1,6] b1[] = [0,7,0,36,4,-6,3,0,0] b2[] =[-1,-3,11,0,0,0,35,0,0] suma = 42 proda = -84*72*3 sumb = 51 prodb = -84*72*3 sumb1 = 44 prodb1 = -84*72*3 sumb2 = 42 prodb2 = 33*35 do the sum and prod operation w/o 0s and compare the values.. if both are equal they are pormutations if i am missing any corner cases related to 0 or -e numbers u can keep a track of them while traversalO(N) and constant space On Mon, May 21, 2012 at 6:40 PM, karthikeya s karthikeya.a...@gmail.comwrote: No way u can do it in O(1) space and O(n) time.sols above are not gonna work..yeah, it is possible in O(n) space and O(n) time. On May 20, 12:29 am, HARSHIT PAHUJA hpahuja.mn...@gmail.com wrote: given 2 unsorted integer arrays a and b of equal size. Determine if b is a permutation of a. Can this be done in O(n) time and O(1) space ? please help me with my solution suppose a -- 3 5 4 b -- 4 3 5 now we replace a[i] with a[i]..th prime number and b with b[i] .. th prime number now array a becomes 5 11 7 array b becomes 7 5 11 now we take product of elements of array a and do the same with array b elements if product is equal then b is a permutation of a -- You received this message because 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: Microsoft interview question
@Partha
try with:
A = {2, 2, 9}
B= {1, 6, 6}
On Mon, May 21, 2012 at 7:08 PM, partha sarathi Mohanty
partha.mohanty2...@gmail.com wrote:
a[] = [-1,-3,4,0,7,0,36,2,-3]
b[] = [0,0,6,2,-1,9,28,1,6]
b1[] = [0,7,0,36,4,-6,3,0,0]
b2[] =[-1,-3,11,0,0,0,35,0,0]
suma = 42 proda = -84*72*3
sumb = 51 prodb = -84*72*3
sumb1 = 44 prodb1 = -84*72*3
sumb2 = 42 prodb2 = 33*35
do the sum and prod operation w/o 0s and compare the values.. if both are
equal they are pormutations
if i am missing any corner cases related to 0 or -e numbers u can keep a
track of them while traversalO(N) and constant space
On Mon, May 21, 2012 at 6:40 PM, karthikeya s
karthikeya.a...@gmail.comwrote:
No way u can do it in O(1) space and O(n) time.sols above are not
gonna work..yeah, it is possible in O(n) space and O(n) time.
On May 20, 12:29 am, HARSHIT PAHUJA hpahuja.mn...@gmail.com wrote:
given 2 unsorted integer arrays a and b of equal size. Determine if b
is a
permutation of a. Can this be done in O(n) time and O(1) space ?
please help me with my solution
suppose a -- 3 5 4
b -- 4 3 5
now we replace a[i] with a[i]..th prime number and b with b[i] .. th
prime
number
now array a becomes 5 11 7
array b becomes 7 5 11
now we take product of elements of array a and do the same with array b
elements
if product is equal then b is a permutation of a
--
You received this message because 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: Microsoft interview question
Hiii!! I have some idea about the solution. Please notify me if i am
wrong
a= [ 4,3,5 ] and b= [ 3,5,4 ]
diff=0;
for (i=0; in;i++)
{ diff= diff+a[i]-b[i];
}
if diff == 0
print: permutation
else
print: not permutation
On 20 May 2012 07:2 0, Dave dave_and_da...@juno.com wrote:
@Harshit: These are a few unanswered questions that came to mind when I
read your solution attempt: What do you do with negative elements? What is
the -12th prime number? How do you deal with overflow in the cases where
you have a lot of large prime numbers and the product exceeds your native
data types?
Dave
On Saturday, May 19, 2012 2:29:52 PM UTC-5, harshit pahuja wrote:
given 2 unsorted integer arrays a and b of equal size. Determine if b is
a permutation of a. Can this be done in O(n) time and O(1) space ?
please help me with my solution
suppose a -- 3 5 4
b -- 4 3 5
now we replace a[i] with a[i]..th prime number and b with b[i] .. th
prime number
now array a becomes 5 11 7
array b becomes 7 5 11
now we take product of elements of array a and do the same with array b
elements
if product is equal then b is a permutation of a
--
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/-/WEW0M5VUUVEJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
*Piyush Khandelwal***
Mobile No: 91-8447229204
91-9808479765
--
You received this message because 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: Microsoft interview question
U are checking if the sum is same or not.. which can be same even if the
elements are different.
On Sun, May 20, 2012 at 11:54 AM, Piyush Khandelwal
piyushkhandelwal...@gmail.com wrote:
Hiii!! I have some idea about the solution. Please notify me if i am
wrong
a= [ 4,3,5 ] and b= [ 3,5,4 ]
diff=0;
for (i=0; in;i++)
{ diff= diff+a[i]-b[i];
}
if diff == 0
print: permutation
else
print: not permutation
On 20 May 2012 07:2 0, Dave dave_and_da...@juno.com wrote:
@Harshit: These are a few unanswered questions that came to mind when I
read your solution attempt: What do you do with negative elements? What is
the -12th prime number? How do you deal with overflow in the cases where
you have a lot of large prime numbers and the product exceeds your native
data types?
Dave
On Saturday, May 19, 2012 2:29:52 PM UTC-5, harshit pahuja wrote:
given 2 unsorted integer arrays a and b of equal size. Determine if b is
a permutation of a. Can this be done in O(n) time and O(1) space ?
please help me with my solution
suppose a -- 3 5 4
b -- 4 3 5
now we replace a[i] with a[i]..th prime number and b with b[i] .. th
prime number
now array a becomes 5 11 7
array b becomes 7 5 11
now we take product of elements of array a and do the same with array b
elements
if product is equal then b is a permutation of a
--
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/-/WEW0M5VUUVEJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
*Piyush Khandelwal***
Mobile No: 91-8447229204
91-9808479765
--
You received this message because 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: Microsoft interview question
@piyush :
your solution will fail for the case
a={5,1,1}
b={3,3,1}
On Sun, May 20, 2012 at 11:54 AM, Piyush Khandelwal
piyushkhandelwal...@gmail.com wrote:
Hiii!! I have some idea about the solution. Please notify me if i am
wrong
a= [ 4,3,5 ] and b= [ 3,5,4 ]
diff=0;
for (i=0; in;i++)
{ diff= diff+a[i]-b[i];
}
if diff == 0
print: permutation
else
print: not permutation
On 20 May 2012 07:2 0, Dave dave_and_da...@juno.com wrote:
@Harshit: These are a few unanswered questions that came to mind when I
read your solution attempt: What do you do with negative elements? What is
the -12th prime number? How do you deal with overflow in the cases where
you have a lot of large prime numbers and the product exceeds your native
data types?
Dave
On Saturday, May 19, 2012 2:29:52 PM UTC-5, harshit pahuja wrote:
given 2 unsorted integer arrays a and b of equal size. Determine if b is
a permutation of a. Can this be done in O(n) time and O(1) space ?
please help me with my solution
suppose a -- 3 5 4
b -- 4 3 5
now we replace a[i] with a[i]..th prime number and b with b[i] .. th
prime number
now array a becomes 5 11 7
array b becomes 7 5 11
now we take product of elements of array a and do the same with array b
elements
if product is equal then b is a permutation of a
--
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/-/WEW0M5VUUVEJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
*Piyush Khandelwal***
Mobile No: 91-8447229204
91-9808479765
--
You received this message because 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: Microsoft interview question
Piyush. I think we can use your logic. But You should check the product also.
Have 4 variables, sum_a,sum_b , prod_a, prod_b
Calculate Sum and product of array 'a' and store it in sum_a,prod_a
Calculate Sum and product of array 'b' and store it in sum_b,prod_b
if sum_a=sum_b prod_a==prod_b then these 2 arrays are permutations
of each other.
Space = O(1)
Time=O(n)
I think this should work. Please correct me if you find mistakes.
On 5/20/12, anuj agarwal coolbuddy...@gmail.com wrote:
U are checking if the sum is same or not.. which can be same even if the
elements are different.
On Sun, May 20, 2012 at 11:54 AM, Piyush Khandelwal
piyushkhandelwal...@gmail.com wrote:
Hiii!! I have some idea about the solution. Please notify me if i am
wrong
a= [ 4,3,5 ] and b= [ 3,5,4 ]
diff=0;
for (i=0; in;i++)
{ diff= diff+a[i]-b[i];
}
if diff == 0
print: permutation
else
print: not permutation
On 20 May 2012 07:2 0, Dave dave_and_da...@juno.com wrote:
@Harshit: These are a few unanswered questions that came to mind when I
read your solution attempt: What do you do with negative elements? What
is
the -12th prime number? How do you deal with overflow in the cases where
you have a lot of large prime numbers and the product exceeds your native
data types?
Dave
On Saturday, May 19, 2012 2:29:52 PM UTC-5, harshit pahuja wrote:
given 2 unsorted integer arrays a and b of equal size. Determine if b is
a permutation of a. Can this be done in O(n) time and O(1) space ?
please help me with my solution
suppose a -- 3 5 4
b -- 4 3 5
now we replace a[i] with a[i]..th prime number and b with b[i] .. th
prime number
now array a becomes 5 11 7
array b becomes 7 5 11
now we take product of elements of array a and do the same with array b
elements
if product is equal then b is a permutation of a
--
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/-/WEW0M5VUUVEJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
*Piyush Khandelwal***
Mobile No: 91-8447229204
91-9808479765
--
You received this message because 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.
--
*
*
*Kalyanasundaram N*
*BE 2nd year, CSE*
*College of Engineering Guindy,*
*Chennai-600025*
*
*
--
You received this message because 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: Microsoft interview question
@Piyush: Try this i/p 8,0,0 ; 2,6,0-- Ur algo aint adequate..
On Sat, May 19, 2012 at 11:24 PM, Piyush Khandelwal
piyushkhandelwal...@gmail.com wrote:
Hiii!! I have some idea about the solution. Please notify me if i am
wrong
a= [ 4,3,5 ] and b= [ 3,5,4 ]
diff=0;
for (i=0; in;i++)
{ diff= diff+a[i]-b[i];
}
if diff == 0
print: permutation
else
print: not permutation
On 20 May 2012 07:2 0, Dave dave_and_da...@juno.com wrote:
@Harshit: These are a few unanswered questions that came to mind when I
read your solution attempt: What do you do with negative elements? What is
the -12th prime number? How do you deal with overflow in the cases where
you have a lot of large prime numbers and the product exceeds your native
data types?
Dave
On Saturday, May 19, 2012 2:29:52 PM UTC-5, harshit pahuja wrote:
given 2 unsorted integer arrays a and b of equal size. Determine if b is
a permutation of a. Can this be done in O(n) time and O(1) space ?
please help me with my solution
suppose a -- 3 5 4
b -- 4 3 5
now we replace a[i] with a[i]..th prime number and b with b[i] .. th
prime number
now array a becomes 5 11 7
array b becomes 7 5 11
now we take product of elements of array a and do the same with array b
elements
if product is equal then b is a permutation of a
--
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/-/WEW0M5VUUVEJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
*Piyush Khandelwal***
Mobile No: 91-8447229204
91-9808479765
--
You received this message because 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: Microsoft interview question
@Harshit: These are a few unanswered questions that came to mind when I read your solution attempt: What do you do with negative elements? What is the -12th prime number? How do you deal with overflow in the cases where you have a lot of large prime numbers and the product exceeds your native data types? Dave On Saturday, May 19, 2012 2:29:52 PM UTC-5, harshit pahuja wrote: given 2 unsorted integer arrays a and b of equal size. Determine if b is a permutation of a. Can this be done in O(n) time and O(1) space ? please help me with my solution suppose a -- 3 5 4 b -- 4 3 5 now we replace a[i] with a[i]..th prime number and b with b[i] .. th prime number now array a becomes 5 11 7 array b becomes 7 5 11 now we take product of elements of array a and do the same with array b elements if product is equal then b is a permutation of a -- 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/-/WEW0M5VUUVEJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Interview Question
@umer : did interviewer told any one of the solution provided in the given link below or different? http://www.geeksforgeeks.org/archives/1155 On Tue, Mar 13, 2012 at 11:31 AM, Umer Farooq the.um...@gmail.com wrote: Yes that is exactly what they wanted. I proposed BFS for this solution. Anyway, there was another problem that I was able to solve; but the interviewer brought up a much more efficient approach. The problem was: - Given a linked a linked list with one pointer pointing to next, another pointer pointing to any random pointer in the list. The random pointer can be before or after the current pointer or it can even be at the same node. Write a piece of code that can produce an exact copy of the linked list. On Tue, Mar 13, 2012 at 10:57 AM, Umer Farooq the.um...@gmail.com wrote: Yes that is exactly what they wanted. I proposed BFS for this solution. Anyway, there was another problem that I was able to solve; but the interviewer brought up a much more efficient approach. The problem was: Given a linked l On Mon, Mar 12, 2012 at 11:31 PM, Gene gene.ress...@gmail.com wrote: Since there is no mention of weights, you are looking for any spanning tree. Primm and Kruskal are for _minimum_ spanning tree. They are overkill for this problem. You can construct a spanning tree in any graph with DFS. Just record every edge you find that reaches a vertex that has never been visited before. This has to find every vertex, and since you are recording only the first edge used to arrive at each vertex, these edges must form a tree. This works even if there are cycles. The algorithm is O(| E|). Note that in general a graph doesn't have a single root. So you'd search from all roots. Another way to think about this: introduce your own dummy root and edges to each vertex where there are no incident in edges. Of course you don't report the dummy edges. On Mar 12, 1:09 pm, atul anand atul.87fri...@gmail.com wrote: i guess they were talking abt spanning tree , so you can use prism or kruskal algo to do the same. On Mon, Mar 12, 2012 at 3:05 PM, Umer Farooq the.um...@gmail.com wrote: Hello friends, I recently had an onsite MS interview. One of the questions that they asked was: - Given a directed graph, write a program that takes root of the graph and returns root of a tree which comprises of all the nodes of the graph in the same way as they appeared in the graph (the graph contains no cycles). -- 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. -- Umer -- 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] Re: Microsoft Interview Question
Well, the interviewer gave a hint to use hash-table. The key of hash-table will be memory address of original node and value will be the memory address of the new node. On Wed, Mar 14, 2012 at 9:43 PM, atul anand atul.87fri...@gmail.com wrote: @umer : did interviewer told any one of the solution provided in the given link below or different? http://www.geeksforgeeks.org/archives/1155 On Tue, Mar 13, 2012 at 11:31 AM, Umer Farooq the.um...@gmail.com wrote: Yes that is exactly what they wanted. I proposed BFS for this solution. Anyway, there was another problem that I was able to solve; but the interviewer brought up a much more efficient approach. The problem was: - Given a linked a linked list with one pointer pointing to next, another pointer pointing to any random pointer in the list. The random pointer can be before or after the current pointer or it can even be at the same node. Write a piece of code that can produce an exact copy of the linked list. On Tue, Mar 13, 2012 at 10:57 AM, Umer Farooq the.um...@gmail.comwrote: Yes that is exactly what they wanted. I proposed BFS for this solution. Anyway, there was another problem that I was able to solve; but the interviewer brought up a much more efficient approach. The problem was: Given a linked l On Mon, Mar 12, 2012 at 11:31 PM, Gene gene.ress...@gmail.com wrote: Since there is no mention of weights, you are looking for any spanning tree. Primm and Kruskal are for _minimum_ spanning tree. They are overkill for this problem. You can construct a spanning tree in any graph with DFS. Just record every edge you find that reaches a vertex that has never been visited before. This has to find every vertex, and since you are recording only the first edge used to arrive at each vertex, these edges must form a tree. This works even if there are cycles. The algorithm is O(| E|). Note that in general a graph doesn't have a single root. So you'd search from all roots. Another way to think about this: introduce your own dummy root and edges to each vertex where there are no incident in edges. Of course you don't report the dummy edges. On Mar 12, 1:09 pm, atul anand atul.87fri...@gmail.com wrote: i guess they were talking abt spanning tree , so you can use prism or kruskal algo to do the same. On Mon, Mar 12, 2012 at 3:05 PM, Umer Farooq the.um...@gmail.com wrote: Hello friends, I recently had an onsite MS interview. One of the questions that they asked was: - Given a directed graph, write a program that takes root of the graph and returns root of a tree which comprises of all the nodes of the graph in the same way as they appeared in the graph (the graph contains no cycles). -- 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. -- Umer -- 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. -- 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.
Re: [algogeeks] Re: Microsoft Interview Question
Yes that is exactly what they wanted. I proposed BFS for this solution. Anyway, there was another problem that I was able to solve; but the interviewer brought up a much more efficient approach. The problem was: Given a linked l On Mon, Mar 12, 2012 at 11:31 PM, Gene gene.ress...@gmail.com wrote: Since there is no mention of weights, you are looking for any spanning tree. Primm and Kruskal are for _minimum_ spanning tree. They are overkill for this problem. You can construct a spanning tree in any graph with DFS. Just record every edge you find that reaches a vertex that has never been visited before. This has to find every vertex, and since you are recording only the first edge used to arrive at each vertex, these edges must form a tree. This works even if there are cycles. The algorithm is O(| E|). Note that in general a graph doesn't have a single root. So you'd search from all roots. Another way to think about this: introduce your own dummy root and edges to each vertex where there are no incident in edges. Of course you don't report the dummy edges. On Mar 12, 1:09 pm, atul anand atul.87fri...@gmail.com wrote: i guess they were talking abt spanning tree , so you can use prism or kruskal algo to do the same. On Mon, Mar 12, 2012 at 3:05 PM, Umer Farooq the.um...@gmail.com wrote: Hello friends, I recently had an onsite MS interview. One of the questions that they asked was: - Given a directed graph, write a program that takes root of the graph and returns root of a tree which comprises of all the nodes of the graph in the same way as they appeared in the graph (the graph contains no cycles). -- 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. -- 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.
Re: [algogeeks] Re: Microsoft Interview Question
Yes that is exactly what they wanted. I proposed BFS for this solution. Anyway, there was another problem that I was able to solve; but the interviewer brought up a much more efficient approach. The problem was: - Given a linked a linked list with one pointer pointing to next, another pointer pointing to any random pointer in the list. The random pointer can be before or after the current pointer or it can even be at the same node. Write a piece of code that can produce an exact copy of the linked list. On Tue, Mar 13, 2012 at 10:57 AM, Umer Farooq the.um...@gmail.com wrote: Yes that is exactly what they wanted. I proposed BFS for this solution. Anyway, there was another problem that I was able to solve; but the interviewer brought up a much more efficient approach. The problem was: Given a linked l On Mon, Mar 12, 2012 at 11:31 PM, Gene gene.ress...@gmail.com wrote: Since there is no mention of weights, you are looking for any spanning tree. Primm and Kruskal are for _minimum_ spanning tree. They are overkill for this problem. You can construct a spanning tree in any graph with DFS. Just record every edge you find that reaches a vertex that has never been visited before. This has to find every vertex, and since you are recording only the first edge used to arrive at each vertex, these edges must form a tree. This works even if there are cycles. The algorithm is O(| E|). Note that in general a graph doesn't have a single root. So you'd search from all roots. Another way to think about this: introduce your own dummy root and edges to each vertex where there are no incident in edges. Of course you don't report the dummy edges. On Mar 12, 1:09 pm, atul anand atul.87fri...@gmail.com wrote: i guess they were talking abt spanning tree , so you can use prism or kruskal algo to do the same. On Mon, Mar 12, 2012 at 3:05 PM, Umer Farooq the.um...@gmail.com wrote: Hello friends, I recently had an onsite MS interview. One of the questions that they asked was: - Given a directed graph, write a program that takes root of the graph and returns root of a tree which comprises of all the nodes of the graph in the same way as they appeared in the graph (the graph contains no cycles). -- 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. -- Umer -- 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.
Re: [algogeeks] Re: Microsoft Interview Question
http://www.geeksforgeeks.org/archives/1155 On Tue, Mar 13, 2012 at 11:31 AM, Umer Farooq the.um...@gmail.com wrote: Yes that is exactly what they wanted. I proposed BFS for this solution. Anyway, there was another problem that I was able to solve; but the interviewer brought up a much more efficient approach. The problem was: - Given a linked a linked list with one pointer pointing to next, another pointer pointing to any random pointer in the list. The random pointer can be before or after the current pointer or it can even be at the same node. Write a piece of code that can produce an exact copy of the linked list. On Tue, Mar 13, 2012 at 10:57 AM, Umer Farooq the.um...@gmail.com wrote: Yes that is exactly what they wanted. I proposed BFS for this solution. Anyway, there was another problem that I was able to solve; but the interviewer brought up a much more efficient approach. The problem was: Given a linked l On Mon, Mar 12, 2012 at 11:31 PM, Gene gene.ress...@gmail.com wrote: Since there is no mention of weights, you are looking for any spanning tree. Primm and Kruskal are for _minimum_ spanning tree. They are overkill for this problem. You can construct a spanning tree in any graph with DFS. Just record every edge you find that reaches a vertex that has never been visited before. This has to find every vertex, and since you are recording only the first edge used to arrive at each vertex, these edges must form a tree. This works even if there are cycles. The algorithm is O(| E|). Note that in general a graph doesn't have a single root. So you'd search from all roots. Another way to think about this: introduce your own dummy root and edges to each vertex where there are no incident in edges. Of course you don't report the dummy edges. On Mar 12, 1:09 pm, atul anand atul.87fri...@gmail.com wrote: i guess they were talking abt spanning tree , so you can use prism or kruskal algo to do the same. On Mon, Mar 12, 2012 at 3:05 PM, Umer Farooq the.um...@gmail.com wrote: Hello friends, I recently had an onsite MS interview. One of the questions that they asked was: - Given a directed graph, write a program that takes root of the graph and returns root of a tree which comprises of all the nodes of the graph in the same way as they appeared in the graph (the graph contains no cycles). -- 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. -- Umer -- 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. -- *Dheeraj Sharma* -- You received this message because 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: Microsoft Interview Question
This problem is close to copying a graph. For that as you said, just
do DFS or BFS and maintain a map from original nodes to copies. Use
the copy to set pointers whenever it exists. When it doesn't exist,
make a new node and add it to the map.
You can implement the map in various ways. A hash table works fine.
If you can add a pointer to each original vertex node, you can store
the mapping right there. If nodes are numbered consecutively, you can
use these as indices into a table. Etc. Etc. Lots of schemes are
possible. No matter how you do it, the algorithm is the same:
Node copy(Node x)
{
if (x == null) return null;
if (Map(x) != null) return Map(x);
xCopy = new Node();
Set Map(x) = xCopy;
xCopy.next = copy(x.next);
xCopy.other = copy(x.other);
return xCopy;
}
But general graph copy is overkill here. The searching requires O(L)
space for a list of length L. So for this special problem, just
traverse the list once to find and copy all the nodes and then a
second time to set the other pointers:
Node Copy(Node x)
{
// Using a dummy head node makes copying simple.
Node dummyHead = new Node();
Node q = dummyHead;
// Make the copied list and fill in the Map.
for (Node p = x; p != null; p = p.next, q = q.next) {
Node pCopy = new Node();
q.next = pCopy;
Set Map(p) = pCopy;
}
// Set all the other pointers.
for (Node p = x; p != null; p = p.next)
Map(p).other = Map(p.other);
return dummyHead.next;
}
The final question is whether you can implement the Map in a tricky
way. After the list is constructed, you have the L other pointers
doing nothing, so how can they be exploited?
I'll let you think about that...
On Mar 13, 2:01 am, Umer Farooq the.um...@gmail.com wrote:
Yes that is exactly what they wanted. I proposed BFS for this solution.
Anyway, there was another problem that I was able to solve; but the
interviewer brought up a much more efficient approach.
The problem was:
- Given a linked a linked list with one pointer pointing to next,
another pointer pointing to any random pointer in the list. The random
pointer can be before or after the current pointer or it can even be at the
same node. Write a piece of code that can produce an exact copy of the
linked list.
On Tue, Mar 13, 2012 at 10:57 AM, Umer Farooq the.um...@gmail.com wrote:
Yes that is exactly what they wanted. I proposed BFS for this solution.
Anyway, there was another problem that I was able to solve; but the
interviewer brought up a much more efficient approach.
The problem was:
Given a linked l
On Mon, Mar 12, 2012 at 11:31 PM, Gene gene.ress...@gmail.com wrote:
Since there is no mention of weights, you are looking for any spanning
tree. Primm and Kruskal are for _minimum_ spanning tree. They are
overkill for this problem.
You can construct a spanning tree in any graph with DFS. Just record
every edge you find that reaches a vertex that has never been visited
before. This has to find every vertex, and since you are recording
only the first edge used to arrive at each vertex, these edges must
form a tree. This works even if there are cycles. The algorithm is O(|
E|).
Note that in general a graph doesn't have a single root. So you'd
search from all roots. Another way to think about this: introduce
your own dummy root and edges to each vertex where there are no
incident in edges. Of course you don't report the dummy edges.
On Mar 12, 1:09 pm, atul anand atul.87fri...@gmail.com wrote:
i guess they were talking abt spanning tree , so you can use prism or
kruskal algo to do the same.
On Mon, Mar 12, 2012 at 3:05 PM, Umer Farooq the.um...@gmail.com
wrote:
Hello friends,
I recently had an onsite MS interview. One of the questions that they
asked was:
- Given a directed graph, write a program that takes root of the
graph
and returns root of a tree which comprises of all the nodes of the
graph in
the same way as they appeared in the graph (the graph contains no
cycles).
--
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.
--
Umer
--
Umer
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send
[algogeeks] Re: Microsoft Interview Question
Copying a full graph requires a BFS or DFS. But here we have a big
advantage. We know the nodes are linked in a single chain. So we
don't need to search to find all nodes. We can just use .next
pointers.
No matter how we do things, we will need Map(A) that returns the copy
of node A if it already exists.
If you use a separate map like a hash table, then things are very
simple. Traverse the list one time to make copies of all the nodes,
chain them in a list, and create the Map. Then traverse the original
list a second time to set the other pointers: for each node A, set
Map(A).other = Map(A.other).
The Map requires O(L) space for a list of length L.
But it turns out we can store the map in a very tricky way that
requires zero additional space _if_ we are allowed to change the
original list while making the copy. If A' is the copy of A, and we
start with list [ A,B,C,... ], then we transform this in one pass to
[A, A', B, B', C, C', ... ]. In this list, A.next is A'. So we have
created the map without losing any information.
Here's untested code that ought to be at least very close:
class Node {
int val;
Node next, other;
Node() {}
Node(int val, Node next, Node other) {
this.val = val;
this.next = next;
this.other = other;
}
Node(Node org) {
this(org.val, org.next, org.other);
}
/**
* @return a copy of the list including other pointers
*/
Node copy() {
// Make the copies and the map.
for (Node p = this; p != null; p = p.next.next)
p.next = new Node(p);
// Use the map to fix up the other pointers in the
copies.
for (Node p = this.next; p.next != null; p =
p.next.next)
p.other = p.other.next;
// Split into original list and list of copies.
Node dummyHead = new Node();
for (Node p = this, q = dummyHead; p != null; p =
p.next, q =
q.next) {
q.next = p.next;
p.next = p.next.next;
}
return dummyHead.next;
}
}
On Mar 13, 2:01 am, Umer Farooq the.um...@gmail.com wrote:
Yes that is exactly what they wanted. I proposed BFS for this solution.
Anyway, there was another problem that I was able to solve; but the
interviewer brought up a much more efficient approach.
The problem was:
- Given a linked a linked list with one pointer pointing to next,
another pointer pointing to any random pointer in the list. The random
pointer can be before or after the current pointer or it can even be at the
same node. Write a piece of code that can produce an exact copy of the
linked list.
On Tue, Mar 13, 2012 at 10:57 AM, Umer Farooq the.um...@gmail.com wrote:
Yes that is exactly what they wanted. I proposed BFS for this solution.
Anyway, there was another problem that I was able to solve; but the
interviewer brought up a much more efficient approach.
The problem was:
Given a linked l
On Mon, Mar 12, 2012 at 11:31 PM, Gene gene.ress...@gmail.com wrote:
Since there is no mention of weights, you are looking for any spanning
tree. Primm and Kruskal are for _minimum_ spanning tree. They are
overkill for this problem.
You can construct a spanning tree in any graph with DFS. Just record
every edge you find that reaches a vertex that has never been visited
before. This has to find every vertex, and since you are recording
only the first edge used to arrive at each vertex, these edges must
form a tree. This works even if there are cycles. The algorithm is O(|
E|).
Note that in general a graph doesn't have a single root. So you'd
search from all roots. Another way to think about this: introduce
your own dummy root and edges to each vertex where there are no
incident in edges. Of course you don't report the dummy edges.
On Mar 12, 1:09 pm, atul anand atul.87fri...@gmail.com wrote:
i guess they were talking abt spanning tree , so you can use prism or
kruskal algo to do the same.
On Mon, Mar 12, 2012 at 3:05 PM, Umer Farooq the.um...@gmail.com
wrote:
Hello friends,
I recently had an onsite MS interview. One of the questions that they
asked was:
- Given a directed graph, write a program that takes root of the
graph
and returns root of a tree which comprises of all the nodes of the
graph in
the same way as they appeared in the graph (the graph contains no
cycles).
--
Umer
--
You received this message because you are subscribed to
[algogeeks] Re: Microsoft Interview Question
Sorry, a small test showed a loop quitting one iteration too soon.
Here is the fix.
import java.util.Random;
public class ListCopy {
class Node {
int val;
Node next, other;
Node() { }
Node(int val, Node next, Node other) {
this.val = val;
this.next = next;
this.other = other;
}
Node(Node org) {
this(org.val, org.next, org.other);
}
Node copy() {
// Make the copies and the map.
for (Node p = this; p != null; p = p.next.next) {
p.next = new Node(p);
}
// Use the map to fix up the other pointers in the copies.
for (Node p = this.next; ; p = p.next.next) {
p.other = p.other.next;
if (p.next == null)
break;
}
// Split into original list and list of copies.
Node d = new Node();
for (Node p = this, q = d; p != null; p = p.next, q =
q.next) {
q.next = p.next;
p.next = p.next.next;
}
return d.next;
}
}
void run() {
Node [] test = new Node [10];
int n = test.length;
int i = n - 1;
test[i] = new Node(n, null, null);
Random gen = new Random(42);
for (--i; i = 0; --i)
test[i] = new Node(i + 1, test[i + 1], null);
for (i = 0; i n; i++)
test[i].other = test[gen.nextInt(n)];
Node copy = test[0].copy();
int count = 0;
for (Node p = test[0], q = copy; p != null; p = p.next, q
=q.next) {
if (p.val != q.val || p.other.val != q.other.val || p == q
|| p.other == q.other)
System.err.println(error: p= + p.val + q= +
q.val);
count++;
}
System.err.println(# nodes: + count);
}
public static void main (String [] args) {
new ListCopy().run();
}
}
On Mar 13, 3:15 pm, Gene gene.ress...@gmail.com wrote:
Copying a full graph requires a BFS or DFS. But here we have a big
advantage. We know the nodes are linked in a single chain. So we
don't need to search to find all nodes. We can just use .next
pointers.
No matter how we do things, we will need Map(A) that returns the copy
of node A if it already exists.
If you use a separate map like a hash table, then things are very
simple. Traverse the list one time to make copies of all the nodes,
chain them in a list, and create the Map. Then traverse the original
list a second time to set the other pointers: for each node A, set
Map(A).other = Map(A.other).
The Map requires O(L) space for a list of length L.
But it turns out we can store the map in a very tricky way that
requires zero additional space _if_ we are allowed to change the
original list while making the copy. If A' is the copy of A, and we
start with list [ A,B,C,... ], then we transform this in one pass to
[A, A', B, B', C, C', ... ]. In this list, A.next is A'. So we have
created the map without losing any information.
Here's untested code that ought to be at least very close:
class Node {
int val;
Node next, other;
Node() {}
Node(int val, Node next, Node other) {
this.val = val;
this.next = next;
this.other = other;
}
Node(Node org) {
this(org.val, org.next, org.other);
}
/**
* @return a copy of the list including other pointers
*/
Node copy() {
// Make the copies and the map.
for (Node p = this; p != null; p = p.next.next)
p.next = new Node(p);
// Use the map to fix up the other pointers in the
copies.
for (Node p = this.next; p.next != null; p =
p.next.next)
p.other = p.other.next;
// Split into original list and list of copies.
Node dummyHead = new Node();
for (Node p = this, q = dummyHead; p != null; p =
p.next, q =
q.next) {
q.next = p.next;
p.next = p.next.next;
}
return dummyHead.next;
}
}
On Mar 13, 2:01 am, Umer Farooq the.um...@gmail.com wrote:
Yes that is exactly what they wanted. I proposed BFS for this solution.
Anyway, there was another problem that I was able to solve; but the
interviewer brought up a much more efficient approach.
The problem was:
- Given a linked a linked list with one pointer pointing to next,
another
[algogeeks] Re: MICROSOFT IDC: unsorted linked lists intersection
@Ashish
We can sort a list in another way as follows:
1) Recursively divide the list into two halves..
2) Call merge while joining the sorted lists..
MergeSort(node * p)
{
if ( p contains only one element)
return p;
p1 = MergeSort(first half of list pointed by p);
p2 = MergeSort(second half of list pointed by p);
return MergeSortedLLS(p1, p2);
}
Complexity of sorting:
To partition the list in 2 halves - O(N)
To merge 2 sorted list - O(N)
To sort:
T(N) = O(N) + T(N/2) + O(N)
= N log N
On Dec 31 2011, 4:46 pm, Lucifer sourabhd2...@gmail.com wrote:
@Ashish..
I have something in mind.. but would require verification by u..
Lets say, the structure of the data node is as follows:
struct node
{
int data;
struct node *next;
};
Now, given 2 sorted linked lists we can right a O(N) time and in-place
merge process, to build a sorted merged linked list...
I am not putting down the code for the merge process because that's
not the goal of the algo given below..
Lets call it:
node * MergeSortedLLS(node *p1, node*p2)
// here p1 and p2 are the head pointers of the 2 sorted lists..
// The return value is the head of the merged sorted list...
Now, say the lists are named as L1 and L2...
If we are not given the no. of elements in L1 and L2.. then we can
traverse both the lists and get the individual counts...
Say the no. of nodes in L1 and L2 are N1 and N2
The below cited algorithm is nothing but the application of mergesort
on a singly linked list rather than an array with slight
modification...
node* Merge2UnsortedLists(node *L1, node* L2, int N1, int N2)
{
node * p1 = MergeSortLL( L1, 0, N1 -1 );
node * p2 = MergeSortLL( L2, 0, N2 -1 );
return MergeSortedLLS(p1, p2);
}
node * MergeSort(node ** p, int start, int end)
{
node * head = *p;
if (start == end)
*p = (*p)-next;
else
{
int mid = (start + end)/2;
node * p1 = MergeSort(p, start, mid);
node * p2 = MergeSort(p, mid + 1, end);
head = MergeSortedLLS(p1, p2);
}
return head;
}
/*
Call : Merge2UnsortedLists(L1, L2, N1, N2);
*/
The above is in-place..
Time complexity:
MergeSortedLLS - N
MergeSort - NLogN
Merge2UnsortedLists - N1LogN1(2 sort the L1) + N2LogN2 (to sort L2) +
N1 + N2 ( to merge : sorted L1 and L2)
--
Let me know what do u think...
On 31 Dec, 14:27, Ashish Goel ashg...@gmail.com wrote:
merge two linked list without sorting them, the resultant list should be
sorted one...
any other better solution?
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jan 12, 2011 at 3:15 PM, Ashish Goel ashg...@gmail.com wrote:
without sorting, it will be mess...O(n^2)
with recursion, it will be lot of stack space however since this is asked
i would do it this way
The only problem i see with this code is what if the lists are 1,2,1,2 AND
2,1,1,1
This code will give 2 common message twice and 1 common message 4 times
struct node* sortAndMerge(struct node *a, struct node *b)
{
if !a return b;
if !b return a;
struct node *result = NULL;
if (a-data =b-data)
{ result =a; result-next = sortAndMerge(a-next, b);}
else { result =b; result-next = sortAndMerge(b-next, a);}
return result;
}
void merge(struct node **pL)
{
if (!(*pL) || !(*pL-next)) return NULL;
struct node *a=NULL;
struct node *b=NULL;
split(*pL, a, b);
merge(a); merge(b);
sortAndMerge(a,b);
}
void intersect(struct node *a, struct node *b)
{
if (!a) || (!b) return;
merge(a);
merge(b);
struct node * result = sortAndMerge(a,b);
struct node *current =result;
while (current)
{
if (current-data ==current-next-data) printf(%d ,
current-data);
current = current-next;
}
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jan 12, 2011 at 2:35 PM, Saurabh Koar
saurabhkoar...@gmail.comwrote:
I mean is it possible to solve the problem using recursion and without
sorting? (in O(1) space and O(n^2) complexity? ). As he didnt say
anything,I am just clearing my doubts.
--
You received this message because 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] Re: MICROSOFT IDC: unsorted linked lists intersection
@Ashish..
I have something in mind.. but would require verification by u..
Lets say, the structure of the data node is as follows:
struct node
{
int data;
struct node *next;
};
Now, given 2 sorted linked lists we can right a O(N) time and in-place
merge process, to build a sorted merged linked list...
I am not putting down the code for the merge process because that's
not the goal of the algo given below..
Lets call it:
node * MergeSortedLLS(node *p1, node*p2)
// here p1 and p2 are the head pointers of the 2 sorted lists..
// The return value is the head of the merged sorted list...
Now, say the lists are named as L1 and L2...
If we are not given the no. of elements in L1 and L2.. then we can
traverse both the lists and get the individual counts...
Say the no. of nodes in L1 and L2 are N1 and N2
The below cited algorithm is nothing but the application of mergesort
on a singly linked list rather than an array with slight
modification...
node* Merge2UnsortedLists(node *L1, node* L2, int N1, int N2)
{
node * p1 = MergeSortLL( L1, 0, N1 -1 );
node * p2 = MergeSortLL( L2, 0, N2 -1 );
return MergeSortedLLS(p1, p2);
}
node * MergeSort(node ** p, int start, int end)
{
node * head = *p;
if (start == end)
*p = (*p)-next;
else
{
int mid = (start + end)/2;
node * p1 = MergeSort(p, start, mid);
node * p2 = MergeSort(p, mid + 1, end);
head = MergeSortedLLS(p1, p2);
}
return head;
}
/*
Call : Merge2UnsortedLists(L1, L2, N1, N2);
*/
The above is in-place..
Time complexity:
MergeSortedLLS - N
MergeSort - NLogN
Merge2UnsortedLists - N1LogN1(2 sort the L1) + N2LogN2 (to sort L2) +
N1 + N2 ( to merge : sorted L1 and L2)
--
Let me know what do u think...
On 31 Dec, 14:27, Ashish Goel ashg...@gmail.com wrote:
merge two linked list without sorting them, the resultant list should be
sorted one...
any other better solution?
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jan 12, 2011 at 3:15 PM, Ashish Goel ashg...@gmail.com wrote:
without sorting, it will be mess...O(n^2)
with recursion, it will be lot of stack space however since this is asked
i would do it this way
The only problem i see with this code is what if the lists are 1,2,1,2 AND
2,1,1,1
This code will give 2 common message twice and 1 common message 4 times
struct node* sortAndMerge(struct node *a, struct node *b)
{
if !a return b;
if !b return a;
struct node *result = NULL;
if (a-data =b-data)
{ result =a; result-next = sortAndMerge(a-next, b);}
else { result =b; result-next = sortAndMerge(b-next, a);}
return result;
}
void merge(struct node **pL)
{
if (!(*pL) || !(*pL-next)) return NULL;
struct node *a=NULL;
struct node *b=NULL;
split(*pL, a, b);
merge(a); merge(b);
sortAndMerge(a,b);
}
void intersect(struct node *a, struct node *b)
{
if (!a) || (!b) return;
merge(a);
merge(b);
struct node * result = sortAndMerge(a,b);
struct node *current =result;
while (current)
{
if (current-data ==current-next-data) printf(%d ,
current-data);
current = current-next;
}
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jan 12, 2011 at 2:35 PM, Saurabh Koar
saurabhkoar...@gmail.comwrote:
I mean is it possible to solve the problem using recursion and without
sorting? (in O(1) space and O(n^2) complexity? ). As he didnt say
anything,I am just clearing my doubts.
--
You received this message because 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: Microsoft Question
Priority Queue:
when popped ... returns the max priority element and if the priorities
of two or more elements are same...then they will popped as they are
inserted ..
when pushed the element : puts the element in the list according to the
priority...
For making priority queue into Queue::
on popping : make priority of every element same... so on popping... the
element...(popped according to which they are inserted)
on pushing : insert the element as same priority as other inserted
elements
For making priority queue into stack..:
make priority of elements in increasing order... .. so on popping the
element... will pop the topmost element(with the highest priority
value)..
on pushing the element... push the element... with the priority value more
than topmost priority value...
With regards,
Praveen Raj
DCE-IT 3rd yr
735993
praveen0...@gmail.com
On Thu, Sep 15, 2011 at 6:37 PM, Yogesh Yadav medu...@gmail.com wrote:
For Stack:
just make a structure:
struct stack_with_priorityqueue
{
int num;
int priority;
struct stack_with_priorityqueue *ptr;
}
now when we add another number just increase the priority... priority++
For Queue:
do same...just decrease priority...priority--
...
On Wed, Sep 14, 2011 at 4:41 PM, bharatkumar bagana
bagana.bharatku...@gmail.com wrote:
The well known examples of priority queue is minheap and maxheap..
i guess the question is how do we implement one of these(at least) using
queue?
On Wed, Sep 14, 2011 at 9:08 AM, Ankuj Gupta ankuj2...@gmail.com wrote:
I guess the functionality of priority should be maintained
On Sep 13, 11:59 pm, Ankur Garg ankurga...@gmail.com wrote:
But dude are u saying stack will be implemented as a map with
value,priority
and then choose element based on priority ?
regards
Ankur
On Tue, Sep 13, 2011 at 10:16 PM, Ankuj Gupta ankuj2...@gmail.com
wrote:
For stack :- Keep incrementing the priority of each pushed element.
So
the last pushed element will have the greatest priority and the
element pushed first will have
lowest priority.
For queue:- keep decrementing the priority of each inserted element.
On Sep 13, 1:45 am, Ankur Garg ankurga...@gmail.com wrote:
How to Implement a Queue with a Priority Queue
Similarly how woud you implement Stack with Priority Queue
--
You received this message because 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.
--
**Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers = Save Trees
*BharatKumar Bagana*
**http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar
*
Mobile +91 8056127652*
bagana.bharatku...@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.
Re: [algogeeks] Re: Microsoft Question
On 10/29/11, praveen raj praveen0...@gmail.com wrote:
Priority Queue:
when popped ... returns the max priority element and if the priorities
of two or more elements are same...then they will popped as they are
inserted ..
when pushed the element : puts the element in the list according to the
priority...
For making priority queue into Queue::
on popping : make priority of every element same... so on popping... the
element...(popped according to which they are inserted)
on pushing : insert the element as same priority as other inserted
elements
For making priority queue into stack..:
make priority of elements in increasing order... .. so on popping the
element... will pop the topmost element(with the highest priority
value)..
on pushing the element... push the element... with the priority value more
than topmost priority value...
With regards,
Praveen Raj
DCE-IT 3rd yr
735993
praveen0...@gmail.com
On Thu, Sep 15, 2011 at 6:37 PM, Yogesh Yadav medu...@gmail.com wrote:
For Stack:
just make a structure:
struct stack_with_priorityqueue
{
int num;
int priority;
struct stack_with_priorityqueue *ptr;
}
now when we add another number just increase the priority...
priority++
For Queue:
do same...just decrease priority...priority--
...
On Wed, Sep 14, 2011 at 4:41 PM, bharatkumar bagana
bagana.bharatku...@gmail.com wrote:
The well known examples of priority queue is minheap and maxheap..
i guess the question is how do we implement one of these(at least) using
queue?
On Wed, Sep 14, 2011 at 9:08 AM, Ankuj Gupta ankuj2...@gmail.com wrote:
I guess the functionality of priority should be maintained
On Sep 13, 11:59 pm, Ankur Garg ankurga...@gmail.com wrote:
But dude are u saying stack will be implemented as a map with
value,priority
and then choose element based on priority ?
regards
Ankur
On Tue, Sep 13, 2011 at 10:16 PM, Ankuj Gupta ankuj2...@gmail.com
wrote:
For stack :- Keep incrementing the priority of each pushed element.
So
the last pushed element will have the greatest priority and the
element pushed first will have
lowest priority.
For queue:- keep decrementing the priority of each inserted element.
On Sep 13, 1:45 am, Ankur Garg ankurga...@gmail.com wrote:
How to Implement a Queue with a Priority Queue
Similarly how woud you implement Stack with Priority Queue
--
You received this message because 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.
--
**Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers = Save Trees
*BharatKumar Bagana*
**http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar
*
Mobile +91 8056127652*
bagana.bharatku...@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.
Re: [algogeeks] Re: MICROSOFT WRITTEN
How about this answer:
b?z:y
int main() {
int a=0,b,y=4,z=5,k;
cinb;
k=(((b+~a+1)7)1);//k will either be 0 or 1
cout (z-int((bool)k(z-y)));
return 0;
}
On Mon, Sep 12, 2011 at 5:32 PM, beginner shubh2...@gmail.com wrote:
although multiplication operator is not allowed..
but it's an attempt to write shorter...
c++ implementation-
int cond(int x, int y, int z){
return y*(int)((bool)x)+z*(1+(~(int)((bool)x)+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/-/5uGBGvacNEwJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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
Ravi Maggon
B.E. CSE, Final Year
Thapar University
www.algorithmguru.com
*Failure is the opportunity to begin again more intelligently*
--
You received this message because 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: MICROSOFT WRITTEN
return (((-1+!x)y) | ((-1+!!x)z)) ;
On Sun, Oct 2, 2011 at 3:18 PM, ravi maggon maggonr...@gmail.com wrote:
How about this answer:
b?z:y
int main() {
int a=0,b,y=4,z=5,k;
cinb;
k=(((b+~a+1)7)1);//k will either be 0 or 1
cout (z-int((bool)k(z-y)));
return 0;
}
On Mon, Sep 12, 2011 at 5:32 PM, beginner shubh2...@gmail.com wrote:
although multiplication operator is not allowed..
but it's an attempt to write shorter...
c++ implementation-
int cond(int x, int y, int z){
return y*(int)((bool)x)+z*(1+(~(int)((bool)x)+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/-/5uGBGvacNEwJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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
Ravi Maggon
B.E. CSE, Final Year
Thapar University
www.algorithmguru.com
Failure is the opportunity to begin again more intelligently
--
You received this message because 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.
--
Varun Jakhoria
...it's only about 0's 1's
--
You received this message because 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: microsoft interview
@Teja Bala
U dont need the last line for a[0][0]
else code will be wrong
conside
0 0 0 0 1
0 0 0 0 0
0 1 0 0 0
0 0 0 1 0
Regards
On Sun, Sep 11, 2011 at 11:56 PM, teja bala pawanjalsa.t...@gmail.comwrote:
//pseudo code dis will work for sure.
for(i=0;irow_count;i++)
for(j=0;jcolumn_count;j++)
{
if (a[i][j] == 1)
{
a[i][0] = 1;
a[0][j] = 1;
}
}
for(i=1;irow_count;i++)
for(j=1;jcolumn_count;j++)
{
if (a[0][j] == 1 || a[i][0] == 1)
{
a[i][j] = 1;
}
]
if (a[0][0] == 1)
{
for (i=0;irow_count;i++)
{
a[i][0] = 1;
}
for (i=0;icolumn_count;i++)
{
a[0][i] = 1;
}
--
You received this message because 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: MICROSOFT IDC
congrates dude On Thu, Sep 22, 2011 at 7:26 PM, Sanjay Rajpal srn...@gmail.com wrote: Saurabh : Thank u very much :) Sanju :) On Thu, Sep 22, 2011 at 6:15 AM, saurabh sah.saurab...@gmail.com wrote: thanx to all @sanjay I have shared my interview experience at http://msidcinterview.blogspot.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. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- You received this message because 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: MICROSOFT IDC
Congrats Saurabh. On Fri, Sep 23, 2011 at 7:18 PM, sagar pareek sagarpar...@gmail.com wrote: congrates dude On Thu, Sep 22, 2011 at 7:26 PM, Sanjay Rajpal srn...@gmail.com wrote: Saurabh : Thank u very much :) Sanju :) On Thu, Sep 22, 2011 at 6:15 AM, saurabh sah.saurab...@gmail.com wrote: thanx to all @sanjay I have shared my interview experience at http://msidcinterview.blogspot.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. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- You received this message because 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. -- Nitin Garg Personality can open doors, but only Character can keep them open -- You received this message because 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: Microsoft Question
@kartik:
i thnk u r searching for string...that may have characters..in the 2d matrix
..NO MATTER WHERE THEY ARE..
On Wed, Sep 21, 2011 at 7:10 PM, kartik sachan kartik.sac...@gmail.comwrote:
i think i can solve this in O(n^2)
here is code http://ideone.com/Gk69A
# includestdio.h# includestring.hchar a[100][100];int findword(int *b,int
n,int m){
int i,j,flag=0;
char s[1];
for(i=0;in;i++)
for(j=0;jm;j++)
s[a[i][j]]++;
for(i=0;istrlen(b);i++)
if(s[b[i]]!=0)
s[b[i]]--;
else
{flag=0; break;}
if(flag==0)
return 0;
else
return 1;}int main(){
int i,j,n,m;
char str[1];
scanf(%d %d,n,m);
for(i=0;in;i++)
for(j=0;jm;j++)
scanf(%c,a[i][j]);
scanf(%s,str);
if(findword(str,n,m))
printf
http://www.opengroup.org/onlinepubs/009695399/functions/printf.html(word
is there in matrix);
else
printf
http://www.opengroup.org/onlinepubs/009695399/functions/printf.html(word
is not there in matrix);return 0;}
plzz correct me if i am worng
--
You received this message because 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.
--
*Dheeraj Sharma*
Comp Engg.
NIT Kurukshetra
--
You received this message because 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: MICROSOFT IDC
thanx to all @sanjay I have shared my interview experience at http://msidcinterview.blogspot.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.
Re: [algogeeks] Re: Microsoft Question
@dheeraj i didn't get what u want to say explain me with the help of example -- You received this message because 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: MICROSOFT IDC
Saurabh : Thank u very much :) Sanju :) On Thu, Sep 22, 2011 at 6:15 AM, saurabh sah.saurab...@gmail.com wrote: thanx to all @sanjay I have shared my interview experience at http://msidcinterview.blogspot.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] Re: Microsoft Question
@kartik.,...where are u searching..that ..the next character should be present..only around the 8 possible locations around that character On Thu, Sep 22, 2011 at 6:34 AM, kartik sachan kartik.sac...@gmail.comwrote: @dheeraj i didn't get what u want to say explain me with the help of example -- You received this message because 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. -- *Dheeraj Sharma* Comp Engg. NIT Kurukshetra -- You received this message because 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: Microsoft Question
i think i can solve this in O(n^2)
here is code http://ideone.com/Gk69A
# includestdio.h# includestring.hchar a[100][100];int findword(int
*b,int n,int m){
int i,j,flag=0;
char s[1];
for(i=0;in;i++)
for(j=0;jm;j++)
s[a[i][j]]++;
for(i=0;istrlen(b);i++)
if(s[b[i]]!=0)
s[b[i]]--;
else
{flag=0; break;}
if(flag==0)
return 0;
else
return 1;}int main(){
int i,j,n,m;
char str[1];
scanf(%d %d,n,m);
for(i=0;in;i++)
for(j=0;jm;j++)
scanf(%c,a[i][j]);
scanf(%s,str);
if(findword(str,n,m))
printf
http://www.opengroup.org/onlinepubs/009695399/functions/printf.html(word
is there in matrix);
else
printf
http://www.opengroup.org/onlinepubs/009695399/functions/printf.html(word
is not there in matrix);return 0;}
plzz correct me if i am worng
--
You received this message because 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: Microsoft Question
@piyush: what is time and space complexity of u'r sol..
On Mon, Sep 19, 2011 at 11:03 AM, Piyush Grover
piyush4u.iit...@gmail.comwrote:
sry, in the findWord function all a's are different e.g
a0, a1a7
and if(!a) is actually if(a0||a1||...||a7)
thnx
piyush
On Mon, Sep 19, 2011 at 1:10 AM, Piyush Grover
piyush4u.iit...@gmail.comwrote:
for(i = 0; i n; i++)
for(j = 0; j n; j++){
setColor(i, j) = black;
if(A[i][j] == str[0]){
setColor(i, j) = blue;
a = findWord(A, i, j, str, 1)
if(!a) setColor(i, j) = black;
else break;
}
}
findWord(A, i, j, str, k){
if(k == strlen(str))
return true;
if(A[i-1][j-1] == str[k] getColor(i-1, j-1) != blue)
setColor(i-1, j-1) = blue;
a = findWord(A, i-1, j-1, str, k+1);
if(A[i-1][j] == str[k] getColor(i-1, j) != blue)
setColor(i-1, j) = blue;
a = findWord(A, i-1, j, str, k+1);
if(A[i-1][j+1] == str[k] getColor(i-1, j+1) != blue)
setColor(i-1, j+1) = blue;
a = findWord(A, i-1, j+1, str, k+1);
if(A[i][j-1] == str[k] getColor(i, j-1) != blue)
setColor(i, j-1) = blue;
a = findWord(A, i, j-1, str, k+1);
if(A[i][j+1] == str[k] getColor(i, j+1) != blue)
setColor(i, j+1) = blue;
a = findWord(A, i, j+1, str, k+1);
if(A[i+1][j-1] == str[k] getColor(i+1, j-1) != blue)
setColor(i+1, j-1) = blue;
a = findWord(A, i+1, j-1, str, k+1);
if(A[i+1][j] == str[k] getColor(i+1, j) != blue)
setColor(i+1, j) = blue;
a = findWord(A, i+1, j, str, k+1);
if(A[i+1][j+1] == str[k] getColor(i+1, j+1) != blue)
setColor(i+1, j+1) = blue;
a = findWord(A, i+1, j+1, str, k+1);
if(!a) setColor(i, j) = black;
return a;
}
This is a pseudo code. I haven't considered the boundary cases to make it
understandable.
On Mon, Sep 19, 2011 at 12:21 AM, vikas vikas.rastogi2...@gmail.comwrote:
hmm, nice questions, can we create an efficient DS to query the
strings ??
tried using trie but memory prints are very large ( O(n^2) )? :-((
On Sep 18, 12:59 pm, Anup Ghatage ghat...@gmail.com wrote:
For the mentioned scenario, it seems to be the only feasible solution.
On Sun, Sep 18, 2011 at 3:57 AM, bharatkumar bagana
bagana.bharatku...@gmail.com wrote:
@anup : the time complexity will be very high ...
O(n*M*M)...n=#characters
to be checked...M=size of the matrix ...
On Sat, Sep 17, 2011 at 8:30 AM, Anup Ghatage ghat...@gmail.com
wrote:
As WgpShashank once pointed out.
Search the whole matrix for the first character instances, for each
instance, send the array, string and that char's position to a
function that
will recursively check its direct neighbors for the next character.
Exhaustively check like that for each starting characters appearance
till
you find the string, if any.
On Fri, Sep 16, 2011 at 11:55 PM, Ankur Garg ankurga...@gmail.com
wrote:
In a matrix of. characters, find an string. String can be in any
way (all
8 neighbours to be considered)
like find Microsoft in below matrix.
A
C
P
*R
*C*
*X
*S
**O
*P
*C*
V
*O*
V
N
*I*
W
G
*F
**M
*N
Q
A
*T*
I
T
*Any Ideas How to Solve/Approach this problem ?*
--
You received this message because 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.
--
Anup Ghatage
--
You received this message because 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.
--
**Please do not print this e-mail until urgent requirement. Go
Green!!
Save Papers = Save Trees
*BharatKumar Bagana*
**http://www.google.com/profiles/bagana.bharatkumar
http://www.google.com/profiles/bagana.bharatkumar
*
Mobile +91 8056127652*
bagana.bharatku...@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.
--
Anup Ghatage
--
You received this message because you are subscribed to
[algogeeks] Re: Microsoft Question
hmm, nice questions, can we create an efficient DS to query the strings ?? tried using trie but memory prints are very large ( O(n^2) )? :-(( On Sep 18, 12:59 pm, Anup Ghatage ghat...@gmail.com wrote: For the mentioned scenario, it seems to be the only feasible solution. On Sun, Sep 18, 2011 at 3:57 AM, bharatkumar bagana bagana.bharatku...@gmail.com wrote: @anup : the time complexity will be very high ... O(n*M*M)...n=#characters to be checked...M=size of the matrix ... On Sat, Sep 17, 2011 at 8:30 AM, Anup Ghatage ghat...@gmail.com wrote: As WgpShashank once pointed out. Search the whole matrix for the first character instances, for each instance, send the array, string and that char's position to a function that will recursively check its direct neighbors for the next character. Exhaustively check like that for each starting characters appearance till you find the string, if any. On Fri, Sep 16, 2011 at 11:55 PM, Ankur Garg ankurga...@gmail.comwrote: In a matrix of. characters, find an string. String can be in any way (all 8 neighbours to be considered) like find Microsoft in below matrix. A C P *R *C* *X *S **O *P *C* V *O* V N *I* W G *F **M *N Q A *T* I T *Any Ideas How to Solve/Approach this problem ?* -- You received this message because 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. -- Anup Ghatage -- You received this message because 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. -- **Please do not print this e-mail until urgent requirement. Go Green!! Save Papers = Save Trees *BharatKumar Bagana* **http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar * Mobile +91 8056127652* bagana.bharatku...@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. -- Anup Ghatage -- You received this message because 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: Microsoft Question
for(i = 0; i n; i++)
for(j = 0; j n; j++){
setColor(i, j) = black;
if(A[i][j] == str[0]){
setColor(i, j) = blue;
a = findWord(A, i, j, str, 1)
if(!a) setColor(i, j) = black;
else break;
}
}
findWord(A, i, j, str, k){
if(k == strlen(str))
return true;
if(A[i-1][j-1] == str[k] getColor(i-1, j-1) != blue)
setColor(i-1, j-1) = blue;
a = findWord(A, i-1, j-1, str, k+1);
if(A[i-1][j] == str[k] getColor(i-1, j) != blue)
setColor(i-1, j) = blue;
a = findWord(A, i-1, j, str, k+1);
if(A[i-1][j+1] == str[k] getColor(i-1, j+1) != blue)
setColor(i-1, j+1) = blue;
a = findWord(A, i-1, j+1, str, k+1);
if(A[i][j-1] == str[k] getColor(i, j-1) != blue)
setColor(i, j-1) = blue;
a = findWord(A, i, j-1, str, k+1);
if(A[i][j+1] == str[k] getColor(i, j+1) != blue)
setColor(i, j+1) = blue;
a = findWord(A, i, j+1, str, k+1);
if(A[i+1][j-1] == str[k] getColor(i+1, j-1) != blue)
setColor(i+1, j-1) = blue;
a = findWord(A, i+1, j-1, str, k+1);
if(A[i+1][j] == str[k] getColor(i+1, j) != blue)
setColor(i+1, j) = blue;
a = findWord(A, i+1, j, str, k+1);
if(A[i+1][j+1] == str[k] getColor(i+1, j+1) != blue)
setColor(i+1, j+1) = blue;
a = findWord(A, i+1, j+1, str, k+1);
if(!a) setColor(i, j) = black;
return a;
}
This is a pseudo code. I haven't considered the boundary cases to make it
understandable.
On Mon, Sep 19, 2011 at 12:21 AM, vikas vikas.rastogi2...@gmail.com wrote:
hmm, nice questions, can we create an efficient DS to query the
strings ??
tried using trie but memory prints are very large ( O(n^2) )? :-((
On Sep 18, 12:59 pm, Anup Ghatage ghat...@gmail.com wrote:
For the mentioned scenario, it seems to be the only feasible solution.
On Sun, Sep 18, 2011 at 3:57 AM, bharatkumar bagana
bagana.bharatku...@gmail.com wrote:
@anup : the time complexity will be very high ...
O(n*M*M)...n=#characters
to be checked...M=size of the matrix ...
On Sat, Sep 17, 2011 at 8:30 AM, Anup Ghatage ghat...@gmail.com
wrote:
As WgpShashank once pointed out.
Search the whole matrix for the first character instances, for each
instance, send the array, string and that char's position to a
function that
will recursively check its direct neighbors for the next character.
Exhaustively check like that for each starting characters appearance
till
you find the string, if any.
On Fri, Sep 16, 2011 at 11:55 PM, Ankur Garg ankurga...@gmail.com
wrote:
In a matrix of. characters, find an string. String can be in any way
(all
8 neighbours to be considered)
like find Microsoft in below matrix.
A
C
P
*R
*C*
*X
*S
**O
*P
*C*
V
*O*
V
N
*I*
W
G
*F
**M
*N
Q
A
*T*
I
T
*Any Ideas How to Solve/Approach this problem ?*
--
You received this message because 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.
--
Anup Ghatage
--
You received this message because 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.
--
**Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers = Save Trees
*BharatKumar Bagana*
**http://www.google.com/profiles/bagana.bharatkumar
http://www.google.com/profiles/bagana.bharatkumar
*
Mobile +91 8056127652*
bagana.bharatku...@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.
--
Anup Ghatage
--
You received this message because 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
Re: [algogeeks] Re: Microsoft Question
sry, in the findWord function all a's are different e.g
a0, a1a7
and if(!a) is actually if(a0||a1||...||a7)
thnx
piyush
On Mon, Sep 19, 2011 at 1:10 AM, Piyush Grover piyush4u.iit...@gmail.comwrote:
for(i = 0; i n; i++)
for(j = 0; j n; j++){
setColor(i, j) = black;
if(A[i][j] == str[0]){
setColor(i, j) = blue;
a = findWord(A, i, j, str, 1)
if(!a) setColor(i, j) = black;
else break;
}
}
findWord(A, i, j, str, k){
if(k == strlen(str))
return true;
if(A[i-1][j-1] == str[k] getColor(i-1, j-1) != blue)
setColor(i-1, j-1) = blue;
a = findWord(A, i-1, j-1, str, k+1);
if(A[i-1][j] == str[k] getColor(i-1, j) != blue)
setColor(i-1, j) = blue;
a = findWord(A, i-1, j, str, k+1);
if(A[i-1][j+1] == str[k] getColor(i-1, j+1) != blue)
setColor(i-1, j+1) = blue;
a = findWord(A, i-1, j+1, str, k+1);
if(A[i][j-1] == str[k] getColor(i, j-1) != blue)
setColor(i, j-1) = blue;
a = findWord(A, i, j-1, str, k+1);
if(A[i][j+1] == str[k] getColor(i, j+1) != blue)
setColor(i, j+1) = blue;
a = findWord(A, i, j+1, str, k+1);
if(A[i+1][j-1] == str[k] getColor(i+1, j-1) != blue)
setColor(i+1, j-1) = blue;
a = findWord(A, i+1, j-1, str, k+1);
if(A[i+1][j] == str[k] getColor(i+1, j) != blue)
setColor(i+1, j) = blue;
a = findWord(A, i+1, j, str, k+1);
if(A[i+1][j+1] == str[k] getColor(i+1, j+1) != blue)
setColor(i+1, j+1) = blue;
a = findWord(A, i+1, j+1, str, k+1);
if(!a) setColor(i, j) = black;
return a;
}
This is a pseudo code. I haven't considered the boundary cases to make it
understandable.
On Mon, Sep 19, 2011 at 12:21 AM, vikas vikas.rastogi2...@gmail.comwrote:
hmm, nice questions, can we create an efficient DS to query the
strings ??
tried using trie but memory prints are very large ( O(n^2) )? :-((
On Sep 18, 12:59 pm, Anup Ghatage ghat...@gmail.com wrote:
For the mentioned scenario, it seems to be the only feasible solution.
On Sun, Sep 18, 2011 at 3:57 AM, bharatkumar bagana
bagana.bharatku...@gmail.com wrote:
@anup : the time complexity will be very high ...
O(n*M*M)...n=#characters
to be checked...M=size of the matrix ...
On Sat, Sep 17, 2011 at 8:30 AM, Anup Ghatage ghat...@gmail.com
wrote:
As WgpShashank once pointed out.
Search the whole matrix for the first character instances, for each
instance, send the array, string and that char's position to a
function that
will recursively check its direct neighbors for the next character.
Exhaustively check like that for each starting characters appearance
till
you find the string, if any.
On Fri, Sep 16, 2011 at 11:55 PM, Ankur Garg ankurga...@gmail.com
wrote:
In a matrix of. characters, find an string. String can be in any way
(all
8 neighbours to be considered)
like find Microsoft in below matrix.
A
C
P
*R
*C*
*X
*S
**O
*P
*C*
V
*O*
V
N
*I*
W
G
*F
**M
*N
Q
A
*T*
I
T
*Any Ideas How to Solve/Approach this problem ?*
--
You received this message because 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.
--
Anup Ghatage
--
You received this message because 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.
--
**Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers = Save Trees
*BharatKumar Bagana*
**http://www.google.com/profiles/bagana.bharatkumar
http://www.google.com/profiles/bagana.bharatkumar
*
Mobile +91 8056127652*
bagana.bharatku...@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.
--
Anup Ghatage
--
You received this message because 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] Re: Microsoft Question
For Stack:
just make a structure:
struct stack_with_priorityqueue
{
int num;
int priority;
struct stack_with_priorityqueue *ptr;
}
now when we add another number just increase the priority... priority++
For Queue:
do same...just decrease priority...priority--
...
On Wed, Sep 14, 2011 at 4:41 PM, bharatkumar bagana
bagana.bharatku...@gmail.com wrote:
The well known examples of priority queue is minheap and maxheap..
i guess the question is how do we implement one of these(at least) using
queue?
On Wed, Sep 14, 2011 at 9:08 AM, Ankuj Gupta ankuj2...@gmail.com wrote:
I guess the functionality of priority should be maintained
On Sep 13, 11:59 pm, Ankur Garg ankurga...@gmail.com wrote:
But dude are u saying stack will be implemented as a map with
value,priority
and then choose element based on priority ?
regards
Ankur
On Tue, Sep 13, 2011 at 10:16 PM, Ankuj Gupta ankuj2...@gmail.com
wrote:
For stack :- Keep incrementing the priority of each pushed element. So
the last pushed element will have the greatest priority and the
element pushed first will have
lowest priority.
For queue:- keep decrementing the priority of each inserted element.
On Sep 13, 1:45 am, Ankur Garg ankurga...@gmail.com wrote:
How to Implement a Queue with a Priority Queue
Similarly how woud you implement Stack with Priority Queue
--
You received this message because 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.
--
**Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers = Save Trees
*BharatKumar Bagana*
**http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar
*
Mobile +91 8056127652*
bagana.bharatku...@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] Re: MICROSOFT WRITTEN IN VASAVI
char str[10];
int length,count;
void fun(int x)
{
if(x==length)
printf(%d %s\n,++count,str);
else
{
fun(x+1);
str[x]-=32;
fun(x+1);
str[x]+=32;
}
}
int main()
{
scanf(%s,str);
length=strlen(str);
fun(0);
getch();
}
On Wed, Sep 14, 2011 at 10:05 AM, mohit verma mohit89m...@gmail.com wrote:
take an array containing all original upper-case letters and their smaller
case letters and now the problem is reduced to print all substrings
containing length of original string.
On Wed, Sep 14, 2011 at 8:55 PM, teja bala pawanjalsa.t...@gmail.comwrote:
//dis one works check it out..
#includectype.h
#includestdio.h
#includestring.h
#includeassert.h
void toggler(char* x, int pos)
{
if(pos==0){ printf(%s\n,x); return; }
// printf(String is now: %s\n,x);
x[pos-1] = toupper(x[pos-1]);
toggler(x, pos-1);
x[pos-1] = tolower(x[pos-1]);
toggler(x, pos-1);
return;
}
int main(void){
char str[500];
scanf(%s,str);
toggler(str, strlen(str));
return 0;
}
On Wed, Sep 14, 2011 at 7:22 PM, Dave dave_and_da...@juno.com wrote:
@Teja: Oops. I was wrong. By the time I fix my conceptual error, the
code is no shorter than Anshu's.
Dave
On Sep 14, 8:14 am, teja bala pawanjalsa.t...@gmail.com wrote:
@DAVE
dis was the o/p for ur prog.
aBC
abC
abC
abc
abc
abc
abc
abc
#includeiostream.h
main()
{
int i, n = 3;
char *s=ABC;
for( i = 0 ; i (1n) ; ++i )
{
s[i^(i1)] ^= 'a' ^ 'A';
cout s endl;
}
}- Hide quoted text -
- Show quoted text -
--
You received this message because 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.
--
*MOHIT VERMA*
--
You received this message because 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.
--
*Dheeraj Sharma*
Comp Engg.
NIT Kurukshetra
--
You received this message because 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: Microsoft coming to PEC on 19th, any specific pattern for written test
@Vivek Microsoft is open for CSE and IT department (B.Tech/M.Tech).. The eligibility is 7 CGPA @Rahul we don't have any information about the profile being offered, currently just the written test is taken on 19th which would be for 1 hr, no pre placement talks nothing.. @abhinav I already own a company, but want more exposure... :) and you know Microsoft is one of the best place to work... Ankur -- You received this message because 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: Microsoft coming to PEC on 19th, any specific pattern for written test
hey ankur.. thnaks for ur concern.. *mca *was not eligible kya.. On Fri, Sep 16, 2011 at 12:04 AM, techankur ankurmitta...@gmail.com wrote: @Vivek Microsoft is open for CSE and IT department (B.Tech/M.Tech).. The eligibility is 7 CGPA @Rahul we don't have any information about the profile being offered, currently just the written test is taken on 19th which would be for 1 hr, no pre placement talks nothing.. @abhinav I already own a company, but want more exposure... :) and you know Microsoft is one of the best place to work... Ankur -- You received this message because 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: Microsoft coming to PEC on 19th, any specific pattern for written test
PEC main mca hai hi nahin :P khaali B.E and M.E hai and from this year they have started M.Sc Ankur On Sep 15, 11:41 pm, vivek goel vivek.thapar2...@gmail.com wrote: hey ankur.. thnaks for ur concern.. *mca *was not eligible kya.. On Fri, Sep 16, 2011 at 12:04 AM, techankur ankurmitta...@gmail.com wrote: @Vivek Microsoft is open for CSE and IT department (B.Tech/M.Tech).. The eligibility is 7 CGPA @Rahul we don't have any information about the profile being offered, currently just the written test is taken on 19th which would be for 1 hr, no pre placement talks nothing.. @abhinav I already own a company, but want more exposure... :) and you know Microsoft is one of the best place to work... Ankur -- You received this message because 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: MICROSOFT WRITTEN IN VASAVI
Shorter. It is assumed that the input string consists of upper and
lower case letters only.
void allCase(string r)
{
int i, n = s.sise();
for( i = 0 ; i (1n) ; ++i )
{
string[i^(i1)] ^= 'a' ^ 'A';
cout s endl;
}
}
The expression i^(i1) is a Gray-code (see
http://en.wikipedia.org/wiki/Gray_code)
conversion. In Gray code, the numbers from 0 to 2^n - 1 are arranged
in an order so that only one bit changes from number to number. So
this code changes the case of one character at a time, and after 2^n
iterations, has printed all of the combinations of cases.
Dave
On Sep 14, 5:39 am, anshu mishra anshumishra6...@gmail.com wrote:
void allCase(string r)
{
int n = s.sise();
string s;
for (i = 0; i (1 n); i++)
{
s = r;
for ( j = 0; j n; j++)
{
if ( i ( 1 j) )
{
s[j] = s[j] + ('a' - 'A');
}
}
cout s endl;
}
}- Hide quoted text -
- Show quoted text -
--
You received this message because 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: Microsoft Question
The well known examples of priority queue is minheap and maxheap.. i guess the question is how do we implement one of these(at least) using queue? On Wed, Sep 14, 2011 at 9:08 AM, Ankuj Gupta ankuj2...@gmail.com wrote: I guess the functionality of priority should be maintained On Sep 13, 11:59 pm, Ankur Garg ankurga...@gmail.com wrote: But dude are u saying stack will be implemented as a map with value,priority and then choose element based on priority ? regards Ankur On Tue, Sep 13, 2011 at 10:16 PM, Ankuj Gupta ankuj2...@gmail.com wrote: For stack :- Keep incrementing the priority of each pushed element. So the last pushed element will have the greatest priority and the element pushed first will have lowest priority. For queue:- keep decrementing the priority of each inserted element. On Sep 13, 1:45 am, Ankur Garg ankurga...@gmail.com wrote: How to Implement a Queue with a Priority Queue Similarly how woud you implement Stack with Priority Queue -- You received this message because 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. -- **Please do not print this e-mail until urgent requirement. Go Green!! Save Papers = Save Trees *BharatKumar Bagana* **http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar * Mobile +91 8056127652* bagana.bharatku...@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.
Re: [algogeeks] Re: MICROSOFT WRITTEN IN VASAVI
@DAVE
dis was the o/p for ur prog.
aBC
abC
abC
abc
abc
abc
abc
abc
#includeiostream.h
main()
{
int i, n = 3;
char *s=ABC;
for( i = 0 ; i (1n) ; ++i )
{
s[i^(i1)] ^= 'a' ^ 'A';
cout s endl;
}
}
--
You received this message because 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: MICROSOFT WRITTEN IN VASAVI
wahat is the logic why 1n?
On Wed, Sep 14, 2011 at 6:44 PM, teja bala pawanjalsa.t...@gmail.comwrote:
@DAVE
dis was the o/p for ur prog.
aBC
abC
abC
abc
abc
abc
abc
abc
#includeiostream.h
main()
{
int i, n = 3;
char *s=ABC;
for( i = 0 ; i (1n) ; ++i )
{
s[i^(i1)] ^= 'a' ^ 'A';
cout s endl;
}
}
--
You received this message because 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.
--
*UTKARSH SRIVASTAV
CSE-3
B-Tech 3rd Year
@MNNIT ALLAHABAD*
--
You received this message because 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.
