Re: [algogeeks] Re: Microsoft Interview Question

[atul anand]

@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
wrote:

> 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, 
>>> India
>>> Mobile No: +91-8798049298, +91-9424738542
>>> Alternate Email: rahulkumarpa...@hotmail.com
>>> [image: 
>>> Linkedin]
>>> [image: Twitter] 
>>> 
>>>
>>>
>>
>>
>> --
>> Thanks and Regards:
>> Rahul Kumar Patle
>> M.Tech, School of Information Technology
>> Indian Institute of Technology, Kharagpur-721302, 
>> India
>> Mobile No: +91-8798049298, +91-9424738542
>> Alternate Email: rahulkumarpa...@hotmail.com
>> [image: 
>> Linkedin]
>> [image: Twitter] 
>> 
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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

[Jaspreet Singh]

its not the best i think and also not a dp solution but can be done by this.

On Tue, Oct 16, 2012 at 4:28 AM, Jaspreet Singh
wrote:

> 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, 
>>> India
>>> Mobile No: +91-8798049298, +91-9424738542
>>> Alternate Email: rahulkumarpa...@hotmail.com
>>> [image: 
>>> Linkedin]
>>> [image: Twitter] 
>>> 
>>>
>>>
>>
>>
>> --
>> Thanks and Regards:
>> Rahul Kumar Patle
>> M.Tech, School of Information Technology
>> Indian Institute of Technology, Kharagpur-721302, 
>> India
>> Mobile No: +91-8798049298, +91-9424738542
>> Alternate Email: rahulkumarpa...@hotmail.com
>> [image: 
>> Linkedin]
>> [image: Twitter] 
>> 
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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 Singh]

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, 
>> India
>> Mobile No: +91-8798049298, +91-9424738542
>> Alternate Email: rahulkumarpa...@hotmail.com
>> [image: 
>> Linkedin]
>> [image: Twitter] 
>> 
>>
>>
>
>
> --
> Thanks and Regards:
> Rahul Kumar Patle
> M.Tech, School of Information Technology
> Indian Institute of Technology, Kharagpur-721302, 
> India
> Mobile No: +91-8798049298, +91-9424738542
> Alternate Email: rahulkumarpa...@hotmail.com
> [image: 
> Linkedin]
> [image: Twitter] 
> 
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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

[Don]

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+1
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,
> India
> Mobile No: +91-8798049298, +91-9424738542
> Alternate Email: rahulkumarpa...@hotmail.com
> [image: 
> Linkedin]
> [image: Twitter] 
> 

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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

[Rahul Kumar Patle]

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, 
> India
> Mobile No: +91-8798049298, +91-9424738542
> Alternate Email: rahulkumarpa...@hotmail.com
> [image: 
> Linkedin]
> [image: Twitter] 
> 
>
>


-- 
Thanks and Regards:
Rahul Kumar Patle
M.Tech, School of Information Technology
Indian Institute of Technology, Kharagpur-721302,
India
Mobile No: +91-8798049298, +91-9424738542
Alternate Email: rahulkumarpa...@hotmail.com
[image: Linkedin]
[image: Twitter] 


-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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

[coolfrog$]

@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  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 >   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://grou

[algogeeks] Re: Microsoft Interview Question

[Dave]

@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 ( curif( 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

[Navin Gupta]

@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 
> @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

[Dave]

@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

[mohit]

+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 Gupta]

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.

[algogeeks] Re: Microsoft Interview Question

[ANKIT BHARDWAJ]

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.

Re: [algogeeks] Re: Microsoft Interview Question

[sanjay pandey]

@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

[Nishant Pandey]

i mean o(n) in single traversal .

On Fri, Jun 22, 2012 at 12:53 AM, sanjay pandey
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 post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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.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

[rusty]

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

[sanjay pandey]

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

[Nishant Pandey]

can this be done in single pass in O(n) .

On Thu, Jun 21, 2012 at 8:10 PM, rusty  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 
> #include 
>
> 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.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.

[algogeeks] Re: Microsoft Interview Question

[rusty]

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 
#include 

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.

[algogeeks] Re: Microsoft Interview Question

[Anchal Gupta]

@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  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

[shiv narayan]

@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 Interview Question

[Navin.nitjsr]

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.

Re: [algogeeks] Re: Microsoft interview question

[Piyush Grover]

@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 
> wrote:
>
>> 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  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

[partha sarathi Mohanty]

 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 wrote:

> 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  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 sarathi Mohanty]

@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  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  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  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; i>> >> { diff= diff+a[i]-b[i];
>>> >> }
>>> >> if diff == 0
>>> >>  print: permutation
>>> >> else
>>> >>  print: not permutation
>>> >>
>>> >>
>>> >>
>>> >>
>>> >>
>>> >> On 20 May 2012 07:2 0, Dave  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+unsubscribe@**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+unsubscribe@**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+unsubscribe@**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,*
>>>
>>>

Re: [algogeeks] Re: Microsoft interview question

[Ashish Goel]

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  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  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  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; i>>> >> { diff= diff+a[i]-b[i];
 >> }
 >> if diff == 0
 >>  print: permutation
 >> else
 >>  print: not permutation
 >>
 >>
 >>
 >>
 >>
 >> On 20 May 2012 07:2 0, Dave  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/-/WEW0M5VUUVEJ.

 >>>
 >>> To post to this group, send email to algogeeks@googlegroups.com.
 >>> To unsubscribe from this group, send email to
 >>> algogeeks+unsubscribe@**googlegr**oups.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+unsubscribe@**googlegr**oups.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

Re: [algogeeks] Re: Microsoft interview question

[Dave]

@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  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  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; i>> >> { diff= diff+a[i]-b[i]; 
>>> >> } 
>>> >> if diff == 0 
>>> >>  print: permutation 
>>> >> else 
>>> >>  print: not permutation 
>>> >> 
>>> >> 
>>> >> 
>>> >> 
>>> >> 
>>> >> On 20 May 2012 07:2 0, Dave  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+unsubscribe@**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+unsubscribe@**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+unsubscribe@**googlegroups.com.
>>> >  
>>>
>>> > For more options, visit this group at 
>>> > http://groups.google.com/**group/algoge

[algogeeks] Re: Microsoft interview question

[karthikeya s]

in space

On May 21, 6:53 pm, Ashish Goel  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  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  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; i >> >> {         diff= diff+a[i]-b[i];
> >> >> }
> >> >> if diff == 0
> >> >>  print: permutation
> >> >> else
> >> >>  print: not permutation
>
> >> >> On 20 May 2012 07:2 0, Dave  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+unsubscribe@**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+unsubscribe@**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+unsubscribe@**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/-/

[algogeeks] Re: Microsoft interview question

[karthikeya s]

^not an O(n)

On May 21, 6:53 pm, Ashish Goel  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  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  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; i >> >> {         diff= diff+a[i]-b[i];
> >> >> }
> >> >> if diff == 0
> >> >>  print: permutation
> >> >> else
> >> >>  print: not permutation
>
> >> >> On 20 May 2012 07:2 0, Dave  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+unsubscribe@**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+unsubscribe@**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+unsubscribe@**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/algogeek

Re: [algogeeks] Re: Microsoft interview question

[Ashish Goel]

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  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  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; i> >> { diff= diff+a[i]-b[i];
>> >> }
>> >> if diff == 0
>> >>  print: permutation
>> >> else
>> >>  print: not permutation
>> >>
>> >>
>> >>
>> >>
>> >>
>> >> On 20 May 2012 07:2 0, Dave  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+unsubscribe@**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+unsubscribe@**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+unsubscribe@**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.

[algogeeks] Re: Microsoft interview question

[karthikeya s]

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  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]

@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  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; i >> { diff= diff+a[i]-b[i]; 
> >> } 
> >> if diff == 0 
> >>  print: permutation 
> >> else 
> >>  print: not permutation 
> >> 
> >> 
> >> 
> >> 
> >> 
> >> On 20 May 2012 07:2 0, Dave  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

[Abhishek]

@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 | (1<<59876) 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  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 wrote:
>
>
>
> > dat defeats the o(1) space constraint. :-)
> > On May 19, 2012 8:05 PM, "HARSHIT PAHUJA"  wrote:
>
> >> @malay ---  we can do it by precomputing the prime arrays
> >> 
>
> >> On Sun, May 20, 2012 at 1:10 AM, malay chakrabarti 
> >> wrote:
>
> >>> method is ryt but to find ith prime u cannot to it in constant time.
> >>>  On May 19, 2012 7:30 PM, "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 post to this group, send email to algogeeks@googlegroups.com.
>  To unsubscribe from 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

[Pralay Biswas]

@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; i { diff= diff+a[i]-b[i];
> }
> if diff == 0
>  print: permutation
> else
>  print: not permutation
>
>
>
>
> On 20 May 2012 07:2 0, Dave  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

[Kalyanasundaram]

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  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; i> { diff= diff+a[i]-b[i];
>> }
>> if diff == 0
>>  print: permutation
>> else
>>  print: not permutation
>>
>>
>>
>>
>>
>> On 20 May 2012 07:2 0, Dave  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

[atul anand]

@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; i { diff= diff+a[i]-b[i];
> }
> if diff == 0
>  print: permutation
> else
>  print: not permutation
>
>
>
>
>
> On 20 May 2012 07:2 0, Dave  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

[anuj agarwal]

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; i { diff= diff+a[i]-b[i];
> }
> if diff == 0
>  print: permutation
> else
>  print: not permutation
>
>
>
>
>
> On 20 May 2012 07:2 0, Dave  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 Khandelwal]

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; i 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.

[algogeeks] Re: Microsoft interview question

[Dave]

@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 Farooq]

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  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  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 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  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  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 
 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

[atul anand]

@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  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  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  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  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 
>>> 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.

[algogeeks] Re: Microsoft Interview Question

[Gene]

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  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  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

[algogeeks] Re: Microsoft Interview Question

[Gene]

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  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  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  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  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 
> >> 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
>
> >> > > --

[algogeeks] Re: Microsoft Interview Question

[Gene]

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  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  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  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  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 
> >> 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

Re: [algogeeks] Re: Microsoft Interview Question

[Dheeraj Sharma]

http://www.geeksforgeeks.org/archives/1155

On Tue, Mar 13, 2012 at 11:31 AM, Umer Farooq  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  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  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  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 
>>> 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

[Umer Farooq]

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  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  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  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 
>> 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

[Umer Farooq]

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  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  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 
> 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.

[algogeeks] Re: Microsoft Interview Question

[Gene]

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  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  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.

Re: [algogeeks] Re: Microsoft interview question

[Ashish Goel]

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  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.

[algogeeks] Re: Microsoft interview question

[Gene]

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.

Re: [algogeeks] Re: Microsoft interview question

[Amir hossein Shahriari]

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  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.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

[ADITYA KUMAR]

@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.

[algogeeks] Re: Microsoft interview question

[ligerdave]

@aditya
there is always trade-off. for what it's asking, TRIE is probably the
fastest. the problem already stated, using "data structure", which to
me, means, you index a document. indexing is expensive, but it's
overhead process and it has nothing to do w/ finding an existing word
in a doc.

On Dec 10, 5:33 am, ADITYA KUMAR  wrote:
> @ankit
> u can'nt use TRIE
> becoz , input will be given in form of text
> so generating the TRIE will be much expensive than linear search
>
> On Fri, Dec 10, 2010 at 3:13 PM, GOBIND KUMAR  wrote:
> > Help me in solving this problem...       Define a data struct for the 
> > search engine which will represent whether
>
> > given word is there in the document or not .It  should be fast.
>
> >  --
> > 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 > .com>
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> 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.

[algogeeks] Re: Microsoft interview question

[Dave]

It sets the rightmost bit to 0. Could also be done with
q = len & ~1;

Dave

On Dec 7, 12:50 am, ritesh  wrote:
>  q = (len >> 1) << 1;
>
> what this line is accomplishing?
>
> On Dec 4, 12:38 pm, Abioy Sun  wrote:
>
>
>
> > Hello,
>
> > 2010/12/4 siva viknesh :
>
> > >  Modified 2 color sort problem i.e. you are given an array of integers
> > > containing only 0s and 1s.You have to place all the 0s in even
> > > position and 1s in odd position. And if suppose, no. of 0s exceed no.
> > > of 1s or vice versa then keep them untouched. Do that in ONE PASS and
> > > without taking extra memory (modify the array in-place).
>
> > > For Example :
>
> > > Input Array: {0,1,1,0,1,0,1,0,1,1,1,0,0,1,0,1,1}
> > > Output Array: {0,1,0,1,0,1,0,1,0,1,0,1,0,1,1
> > > ,1,1}
>
> > the problem makes me to recall the quick-sort provided by Knuth in
> > Introduction to Algorithms, 2ed, here I use some skill like he shows.
>
> > eidx = 0 // even index
> > oidx = 1 // odd index
> > while (eidx < len && oidx < len):
> >     while (eidx < len && array[eidx] == 1) eidx += 2;
> >     while (oidx < len && array[oidx] == 0) oidx += 2;
>
> >     if (eidx < len && oidx < len) swap(eidx, oidx);}
>
> > if (eidx < len)
> > {
> >     p = eidx;
> >     q = (len >> 1) << 1;
> >     while (p < q)
> >     {
> >         while (p < q && array[p] == 1) p += 2;
> >         while (p < q && array[q] == 0) q -= 2;
> >         if (p < q) swap(p, q);
> >     }}
>
> > else if (oidx < len)
> >     // similar to above- 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 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

[Abioy Sun]

2010/12/7 ritesh :
>  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.

[algogeeks] Re: Microsoft interview question

[ritesh]

 q = (len >> 1) << 1;

what this line is accomplishing?

On Dec 4, 12:38 pm, Abioy Sun  wrote:
> Hello,
>
> 2010/12/4 siva viknesh :
>
> >  Modified 2 color sort problem i.e. you are given an array of integers
> > containing only 0s and 1s.You have to place all the 0s in even
> > position and 1s in odd position. And if suppose, no. of 0s exceed no.
> > of 1s or vice versa then keep them untouched. Do that in ONE PASS and
> > without taking extra memory (modify the array in-place).
>
> > For Example :
>
> > Input Array: {0,1,1,0,1,0,1,0,1,1,1,0,0,1,0,1,1}
> > Output Array: {0,1,0,1,0,1,0,1,0,1,0,1,0,1,1
> > ,1,1}
>
> the problem makes me to recall the quick-sort provided by Knuth in
> Introduction to Algorithms, 2ed, here I use some skill like he shows.
>
> eidx = 0 // even index
> oidx = 1 // odd index
> while (eidx < len && oidx < len):
>     while (eidx < len && array[eidx] == 1) eidx += 2;
>     while (oidx < len && array[oidx] == 0) oidx += 2;
>
>     if (eidx < len && oidx < len) swap(eidx, oidx);}
>
> if (eidx < len)
> {
>     p = eidx;
>     q = (len >> 1) << 1;
>     while (p < q)
>     {
>         while (p < q && array[p] == 1) p += 2;
>         while (p < q && array[q] == 0) q -= 2;
>         if (p < q) swap(p, q);
>     }}
>
> else if (oidx < len)
>     // similar to above

-- 
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.

[algogeeks] Re: Microsoft interview question

[dreamer .....................]

@ ashita and vrinda

can u please write ur ms written and interview questions..
i ll be really thankful to both of u as ms is going to visit my campus
soon.. so plz help...

On Sep 26, 1:58 pm, ashita dadlani  wrote:
> @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 wrote:
>
> > @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  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  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  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.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.
>
> >  --
> > 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.

-- 
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 dadlani]

@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 wrote:

> @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  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  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  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.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.
>>
>
>  --
> 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.
>

-- 
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 ranjan]

@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  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  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  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.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.
>

-- 
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 dadlani]

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  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  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.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.

[algogeeks] Re: Microsoft interview question

[Gene]

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  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.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Microsoft interview question

[Abhishek Shrivastav]

its an infinite loop. Beware.

On Mon, Aug 23, 2010 at 5:32 AM, Gene  wrote:

> This doesn't work on "abb" for example.
>
> On Aug 22, 9:28 am, Ashish Goel  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  >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.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.
>
>

-- 
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.

[algogeeks] Re: Microsoft interview question

[Gene]

This doesn't work on "abb" for example.

On Aug 22, 9:28 am, Ashish Goel  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 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.com > .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

[Ashish Goel]

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 wrote:

> 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  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  >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.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.
>
>

-- 
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

[nipun batra]

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 wrote:

> 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  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  >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.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.
>
>

-- 
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.

[algogeeks] Re: Microsoft interview question

[Saikat Debnath]

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  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 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.com > .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.