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.
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
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 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 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 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.
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
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.
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.
Re: [algogeeks] Re: Microsoft interview question
I would assume that in addition to functional testing through automation(combination of various fonts,sizes etc) the tenets like reliability, accessibility, interoperability, security(fuzz testing), different architectures(amd, intel 32 bit, 64 bit etc), stress(extremely long file reaching space constraints), internationalization etc should be looked at. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Feb 2, 2011 at 7:25 AM, Gene gene.ress...@gmail.com wrote: Well, this is a white box test. In a wbt, you look for edge and corner cases. Edge cases in this scenario are the largest and smallest point sizes. The fonts with largest kerning values. Largest ascenders and descenders. Largest number of printable characters. You'd probably concentrate on bold italic style because this will have the most extreme values of some of the dimensions already mentioned. So edge cases have 2 of the 3 attributes with average values and the third with the extreme value: TImes New Roman, normal, 120pt. Corner cases have 3 for 3 extreme values. Complex script font, Bold/Italic, 4pt. You could/should pick 30 to 100 of these. You will want to come up with a document that has all possible justification, wrapping around boxes, narrow columns, tables with all kinds of column formatting using all possible character codes. Incorporate all the cases described above into different copies of these formatting constraint hurdles. You'd need a trained typographer to examine the formatting for correct results. You'd want to measure formatting times on an older machine to ensure the algorithms are responsive enough. You'd want to ensure save and open produce the same document you started with. Print and verify correct printed results. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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
use suffix tree it's much faster than simple trie with ukkonen's method you can build it in O(size of document) and then searching in it is practically O(1) http://en.wikipedia.org/wiki/Suffix_tree http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf On Fri, Dec 10, 2010 at 7:54 PM, ADITYA KUMAR aditya...@gmail.com wrote: @ligerdave agree with u :) -- Regards Aditya Kumar B-tech 3rd year Computer Science Engg. 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from 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
@ligerdave agree with u :) -- Regards Aditya Kumar B-tech 3rd year Computer Science Engg. 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 algoge...@googlegroups.com. To unsubscribe from 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
2010/12/7 ritesh riteshcseit...@gmail.com: q = (len 1) 1; what this line is accomplishing? q = len 0xFFFE; -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from 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
@Mohit: I dont think it really matters here.We just have to validate the snapshot of the game board.Number of players should not have any relevance here. On Sat, Sep 25, 2010 at 2:46 PM, mohit ranjan shoonya.mo...@gmail.comwrote: @Ashita, Your logic is fine for one vs one game, but as per question it's one vs many game Any idea what is that ? Mohit On Sat, Sep 25, 2010 at 1:18 PM, ashita dadlani ash@gmail.com wrote: 1.The soldiers are initially placed at row 2 or row 7th(each-one of white and either of black).Also let white ones be at row 2.So they can never be at row 1st.Incase it is so in the game,its not a valid game. 2.There are Bishops.Each color has one of its Bishop which moves diagonally on all white squares,and the other on all black squares.Incase it is not so,the game cannot be valid. 3.Now suppose,no black soldier ever moved.That is,all the black soldiers are at row 7th.This means that the elephant(i am sorry,I generally mess up with their names..:P) of any other player(except horse) cannot be in any row but 8th one. I know only 3 test cases.Incase any one has more,please elaborate. PS:Vrinda,I also got the same question..:P On Sat, Sep 25, 2010 at 2:49 AM, Gene gene.ress...@gmail.com wrote: Valid must mean that you can get from an initial board to the the current game state by a series of legal moves. This is a classic branch and bound game tree search problem. You could search either from a starting configuration and try to find the current game state. Or start from the current state, use 'backward' moves, and try to find the initial configuration. In this case, you'd have to include backward moves that 'untake' pieces that are missing from the current state. Or you could do a simultaneous search from both ends, looking for common states in the middle. You'd generally use a heuristic search. Problems like this often work well with A-Star. The heuristic evaluator would favor states closer to the desired end (either start or current). Gene On Sep 24, 6:26 am, vrinda vasishth vrindavasis...@gmail.com wrote: Asked in microsoft interview Given a snapshot of an ongoing chess game, which probably is a one vs many game, identify whether it is a valid game or not. It would be great if someone would clarify on what conditions does validity of the game depend.. --Vrinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from 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
@Ashita, Your logic is fine for one vs one game, but as per question it's one vs many game Any idea what is that ? Mohit On Sat, Sep 25, 2010 at 1:18 PM, ashita dadlani ash@gmail.com wrote: 1.The soldiers are initially placed at row 2 or row 7th(each-one of white and either of black).Also let white ones be at row 2.So they can never be at row 1st.Incase it is so in the game,its not a valid game. 2.There are Bishops.Each color has one of its Bishop which moves diagonally on all white squares,and the other on all black squares.Incase it is not so,the game cannot be valid. 3.Now suppose,no black soldier ever moved.That is,all the black soldiers are at row 7th.This means that the elephant(i am sorry,I generally mess up with their names..:P) of any other player(except horse) cannot be in any row but 8th one. I know only 3 test cases.Incase any one has more,please elaborate. PS:Vrinda,I also got the same question..:P On Sat, Sep 25, 2010 at 2:49 AM, Gene gene.ress...@gmail.com wrote: Valid must mean that you can get from an initial board to the the current game state by a series of legal moves. This is a classic branch and bound game tree search problem. You could search either from a starting configuration and try to find the current game state. Or start from the current state, use 'backward' moves, and try to find the initial configuration. In this case, you'd have to include backward moves that 'untake' pieces that are missing from the current state. Or you could do a simultaneous search from both ends, looking for common states in the middle. You'd generally use a heuristic search. Problems like this often work well with A-Star. The heuristic evaluator would favor states closer to the desired end (either start or current). Gene On Sep 24, 6:26 am, vrinda vasishth vrindavasis...@gmail.com wrote: Asked in microsoft interview Given a snapshot of an ongoing chess game, which probably is a one vs many game, identify whether it is a valid game or not. It would be great if someone would clarify on what conditions does validity of the game depend.. --Vrinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from 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
1.The soldiers are initially placed at row 2 or row 7th(each-one of white and either of black).Also let white ones be at row 2.So they can never be at row 1st.Incase it is so in the game,its not a valid game. 2.There are Bishops.Each color has one of its Bishop which moves diagonally on all white squares,and the other on all black squares.Incase it is not so,the game cannot be valid. 3.Now suppose,no black soldier ever moved.That is,all the black soldiers are at row 7th.This means that the elephant(i am sorry,I generally mess up with their names..:P) of any other player(except horse) cannot be in any row but 8th one. I know only 3 test cases.Incase any one has more,please elaborate. PS:Vrinda,I also got the same question..:P On Sat, Sep 25, 2010 at 2:49 AM, Gene gene.ress...@gmail.com wrote: Valid must mean that you can get from an initial board to the the current game state by a series of legal moves. This is a classic branch and bound game tree search problem. You could search either from a starting configuration and try to find the current game state. Or start from the current state, use 'backward' moves, and try to find the initial configuration. In this case, you'd have to include backward moves that 'untake' pieces that are missing from the current state. Or you could do a simultaneous search from both ends, looking for common states in the middle. You'd generally use a heuristic search. Problems like this often work well with A-Star. The heuristic evaluator would favor states closer to the desired end (either start or current). Gene On Sep 24, 6:26 am, vrinda vasishth vrindavasis...@gmail.com wrote: Asked in microsoft interview Given a snapshot of an ongoing chess game, which probably is a one vs many game, identify whether it is a valid game or not. It would be great if someone would clarify on what conditions does validity of the game depend.. --Vrinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from 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
its an infinite loop. Beware. On Mon, Aug 23, 2010 at 5:32 AM, Gene gene.ress...@gmail.com wrote: This doesn't work on abb for example. On Aug 22, 9:28 am, Ashish Goel ashg...@gmail.com wrote: use a array arr[char]=count char represent say a-z count is # of occurances while (*s!='\0') { arr[*s-'a']++; if (arr[*s-'a']==1) lastchar=*s; } lastchar is the last non repeating char Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sun, Aug 22, 2010 at 3:30 PM, Saikat Debnath saikat@gmail.com wrote: How to find last unique character in a given string. Unique character means non-repeated number. Give an optimized way. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from 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
Maybe to reduce the memory usage and to include all types of characters we could create a one to one mapping between the character and the number of occurrences.And while retrieving start from reverse checking the mapping value,print if it's one. On Sun, Aug 22, 2010 at 7:59 PM, Saikat Debnath saikat@gmail.comwrote: This is the answer i have given and interviewer said, Optimise it further in terms of memory and character need not be ASCII On Aug 22, 6:28 pm, Ashish Goel ashg...@gmail.com wrote: use a array arr[char]=count char represent say a-z count is # of occurances while (*s!='\0') { arr[*s-'a']++; if (arr[*s-'a']==1) lastchar=*s; } lastchar is the last non repeating char Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sun, Aug 22, 2010 at 3:30 PM, Saikat Debnath saikat@gmail.com wrote: How to find last unique character in a given string. Unique character means non-repeated number. Give an optimized way. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from 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
optimization, use bitmap instead of array... char can be unicode, char may take 1 or 2 bytes, that can be written, big deal.. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sun, Aug 22, 2010 at 7:59 PM, Saikat Debnath saikat@gmail.comwrote: This is the answer i have given and interviewer said, Optimise it further in terms of memory and character need not be ASCII On Aug 22, 6:28 pm, Ashish Goel ashg...@gmail.com wrote: use a array arr[char]=count char represent say a-z count is # of occurances while (*s!='\0') { arr[*s-'a']++; if (arr[*s-'a']==1) lastchar=*s; } lastchar is the last non repeating char Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sun, Aug 22, 2010 at 3:30 PM, Saikat Debnath saikat@gmail.com wrote: How to find last unique character in a given string. Unique character means non-repeated number. Give an optimized way. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.