Re: [algogeeks] Re: Microsoft Interview Question

@jaspreet : i dont find much difference between using BFS or backtracking...which is doing similar to DFS. On Tue, Oct 16, 2012 at 4:28 AM, Jaspreet Singh wrote: > BFS > > > On Sun, Oct 14, 2012 at 4:21 PM, Rahul Kumar Patle < > patlerahulku...@gmail.com> wrote: > >> response awaited!!! >> an

Re: [algogeeks] Re: Microsoft Interview Question

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

Re: [algogeeks] Re: Microsoft Interview Question

BFS On Sun, Oct 14, 2012 at 4:21 PM, Rahul Kumar Patle < patlerahulku...@gmail.com> wrote: > response awaited!!! > anyone?? > > On Sat, Oct 13, 2012 at 12:31 AM, Rahul Kumar Patle < > patlerahulku...@gmail.com> wrote: > >> Pls help to solve this que.. does any one have DP solution for following >

[algogeeks] Re: Microsoft Interview Question

void findPaths(int x, int y, int depth) { if (isEnd(x,y)) showSolution(); // One path will be marked by letters A,B,C... else { maze[x][y] = 'A' + depth; if (x && (maze[x-1][y]=='1')) findPaths(x-1,y,depth+1); if (y && (maze[x][y-1]=='1')) findPaths(x,y-1,depth+

[algogeeks] Re: Microsoft Interview Question

response awaited!!! anyone?? On Sat, Oct 13, 2012 at 12:31 AM, Rahul Kumar Patle < patlerahulku...@gmail.com> wrote: > Pls help to solve this que.. does any one have DP solution for following > que. > > http://www.geeksforgeeks.org/archives/24488 > section 5/question 2 > > Write a program to find

Re: [algogeeks] Re: MICROSOFT QUESTION

@Navin: Why? No division is used. Dave On Thursday, August 16, 2012 9:20:03 AM UTC-5, Navin Kumar wrote: > We have to consider cases when an element is zero. > > On Thu, Aug 16, 2012 at 7:07 PM, shady >wrote: > >> well we can do with just one array. Overwrite the answer directly on >> left[]

Re: [algogeeks] Re: MICROSOFT QUESTION

We have to consider cases when an element is zero. On Thu, Aug 16, 2012 at 7:07 PM, shady wrote: > well we can do with just one array. Overwrite the answer directly on > left[] array. > > > On Thu, Aug 16, 2012 at 6:47 PM, mohit wrote: > >> >> here are the steps : >> 1) Construct a temporary ar

[algogeeks] Re: MICROSOFT QUESTION

yeah we can do it without using an extra array too. first calculating the product of elements on its left and putting in OUT[] and then multiplying with the product of elements on its right . no auxiliary space used. On Thursday, August 16, 2012 2:26:58 PM UTC+5:30, ram wrote: > > > Hi, > >

Re: [algogeeks] Re: MICROSOFT QUESTION

well we can do with just one array. Overwrite the answer directly on left[] array. On Thu, Aug 16, 2012 at 6:47 PM, mohit wrote: > > here are the steps : > 1) Construct a temporary array left[] such that left[i] contains product > of all elements on left of A[i] excluding A[i]. > 2) Construct an

[algogeeks] Re: MICROSOFT QUESTION

here are the steps : 1) Construct a temporary array left[] such that left[i] contains product of all elements on left of A[i] excluding A[i]. 2) Construct another temporary array right[] such that right[i] contains product of all elements on on right of A[i] excluding A[i]. 3) To get OUT[], mult

Re: [algogeeks] Re: Microsoft online questions : DLL to bst??

http://www.geeksforgeeks.org/archives/17629 On 2 August 2012 19:50, Daksh Talwar wrote: > When asked , try to make the most balanced one . > otherwise there are many possible BSTs for a given array/linked list. > > > On Thu, Aug 2, 2012 at 5:05 PM, Umer Farooq wrote: > >> A LinkedList is by its

Re: [algogeeks] Re: Microsoft online questions : DLL to bst??

When asked , try to make the most balanced one . otherwise there are many possible BSTs for a given array/linked list. On Thu, Aug 2, 2012 at 5:05 PM, Umer Farooq wrote: > A LinkedList is by itself is a BST such that one child node of each node > is null. Do we need a simple BST or height balanc

Re: [algogeeks] Re: Microsoft online questions : DLL to bst??

can you give the link within geeksforgeeks please Best Regards Ashish Goel "Think positive and find fuel in failure" +919985813081 +919966006652 On Tue, Jul 31, 2012 at 4:13 PM, a g wrote: > check on geeksforgeeks.org > > On Tue, Jul 31, 2012 at 3:09 PM, Ashish Goel wrote: > >> how would you

Re: [algogeeks] Re: Microsoft online questions : DLL to bst??

Ishan, i am assuming that the list to BST should give a inorder traversal, and the logic of yours does not seem to give a right solution. try two different trees with 7 nodes, convert into LL and then back to BST, the answer is not same as the trees that we start with. Best Regards Ashish Goel "Th

Re: [algogeeks] Re: Microsoft online questions : DLL to bst??

A LinkedList is by itself is a BST such that one child node of each node is null. Do we need a simple BST or height balanced BST? On Tue, Jul 31, 2012 at 2:39 PM, Ashish Goel wrote: > how would you do "convert sorted doubly linked list to bst using same > nodes as in DLL" > Best Regards > Ashish

Re: [algogeeks] Re: Microsoft online questions : DLL to bst??

1. get the middle of the linked list and make it root 2. same for left half and right half recursivly a. get the middle of left half and make it left child. b. get middle of rite half and make it rite child. this is must b he logic for the qstn. :) Thank You, Ishan Sood. 9805660301

Re: [algogeeks] Re: Microsoft online questions : DLL to bst??

check on geeksforgeeks.org On Tue, Jul 31, 2012 at 3:09 PM, Ashish Goel wrote: > how would you do "convert sorted doubly linked list to bst using same > nodes as in DLL" > Best Regards > Ashish Goel > "Think positive and find fuel in failure" > +919985813081 > +919966006652 > > > On Sun, Jul 29,

Re: [algogeeks] Re: Microsoft online questions : DLL to bst??

how would you do "convert sorted doubly linked list to bst using same nodes as in DLL" Best Regards Ashish Goel "Think positive and find fuel in failure" +919985813081 +919966006652 On Sun, Jul 29, 2012 at 10:30 PM, Purani Sekar wrote: > convert sorted doubly linked list to bst using same nodes

Re: [algogeeks] Re: Microsoft online questions

I think they asked same questions for intern and full time. The second round questions were: 1. given a string , remove the duplicates and print it in ascending order eg : accommodate op: acdemot 2. given a sorted array with a few numbers in between reversed. fix the array eg : 1 2 3 4 9 8 7 1

[algogeeks] Re: Microsoft online questions

Also if smeone cn post some questions/experience for microsoft intern/placementit will be a grt help Thanks Tanuj Makkar Delhi College Of Engineering -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the

Re: [algogeeks] Re: microsoft

Use return (int)(num >= 0 ? num+0.5 : num - 0.5); Dave On Monday, July 16, 2012 1:25:04 AM UTC-5, amit wrote: > No It will not. > > For negative number, it will fail. > > On Sun, Jul 15, 2012 at 11:45 PM, Tanuj Makkar < > tanujmakkar.de...@gmail.com> wrote: > >> double round(double num) >> {

Re: [algogeeks] Re: microsoft

thnx amit.jst asked a stupid quesiton:) On Mon, Jul 16, 2012 at 11:55 AM, Amit Jain wrote: > No It will not. > > For negative number, it will fail. > > On Sun, Jul 15, 2012 at 11:45 PM, Tanuj Makkar < > tanujmakkar.de...@gmail.com> wrote: > >> double round(double num) >> { return (int)(n

Re: [algogeeks] Re: microsoft

No It will not. For negative number, it will fail. On Sun, Jul 15, 2012 at 11:45 PM, Tanuj Makkar wrote: > double round(double num) > { return (int)(num+0.5) > } > will it work all the time? > .. > didnt get itcan anyone explain it.thnx in advance. > > On Friday, 26 Augus

[algogeeks] Re: microsoft

double round(double num) { return (int)(num+0.5) } will it work all the time? .. didnt get itcan anyone explain it.thnx in advance. On Friday, 26 August 2011 21:58:05 UTC+5:30, rahul sharma wrote: > > hi guys...microsoft is coming to our campus..plz nyone tell their > recr

[algogeeks] Re: Microsoft interview qs

@Atul thanx for the code its working for the example you took...Please check the same for i/p "abcmno","abcmnop" Algo displays:- mno It should display mno mnop... -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send em

Re: [algogeeks] Re: Microsoft Interview Question

@All *Here is the working code: test on input {-1,5,3,-8,4,-6,9} and {1,-1,2}* Algo: increment current till first +ve number(p) and decerement end till last -ve number(n) now consider only array between [p..n] If current is negetive, increment current If current is positive, swap it with end and

[algogeeks] Re: Microsoft Interview Question

@Navin: If I am correctly executing your algorithm on the data in the original posting, {-1,5,3,-8,4,-6,9}, I get {-1,-6,-8,4,3,5,9}, when the correct answer is {-1,-8,-6,5,3,4,9}. The array contains the correct numbers, but the order of the positive numbers and the order of the negtive numbers

[algogeeks] Re: Microsoft Interview Question

@Dave :- a minor change Initially, decrement the end pointer till it points to positive number, Now end points to the last negative number. Now, If current is negative , increment current If current is positive , swap it with the element at end and decrement current and end both If current >=

[algogeeks] Re: Microsoft Interview Question

@Navin: Try this with {1,-1,2}. current points to the 1 and end points to the 2. Since 1 is positive, the algorithm swaps the 1 and the 2, giving {2,-1,1}. Then it decrements current to point outside the array and end to point to the -1. How can this be right? Dave On Thursday, June 28, 2012

[algogeeks] Re: Microsoft Interview Question

+1 naveen On Thursday, June 28, 2012 8:29:26 PM UTC+5:30, Navin Gupta wrote: > > Keep two pointers - one at start of the array and other at end of the > array > Now current points to start of the array > If current is negative , increment current > If current is positive , swap it with the elem

[algogeeks] Re: Microsoft Interview Question

Keep two pointers - one at start of the array and other at end of the array Now current points to start of the array If current is negative , increment current If current is positive , swap it with the element at end and decrement current and end both If current >= end , then break. Navin Kuma

[algogeeks] Re: Microsoft Interview Question

keep swaping left most -ve and left most positive untill counter reaches at the end of array, can be done in o(n) no extra space required.. 3rd year manit bhopal -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on

Re: [algogeeks] Re: Microsoft Interview Question

@wgp the ques is to maintain the order intact.. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegr

Re: [algogeeks] Re: Microsoft Interview Question

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 t

Re: [algogeeks] Re: Microsoft Interview Question

Well they are the same you're going over an array once. As long as they are not nested they are still counted as O(n) because leading constants are dropped, at least that's what my acumen says. Need inputs on this guys! On Friday, June 22, 2012 12:53:02 AM UTC+5:30, suzi wrote: > > single traver

Re: [algogeeks] Re: Microsoft Interview Question

single traversal n O(n) are 2 diff things...plz specify??? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@g

Re: [algogeeks] Re: Microsoft question

Can't we use k iterations of bubble sort ? On Jun 18, 2012 2:11 PM, "Ramindar Singh" wrote: > We can use Median of medians > > > http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm > > > On Sunday, 17 June 2012 08:13:18 UTC+5:30, Prem

Re: [algogeeks] Re: Microsoft Interview Question

can this be done in single pass in O(n) . On Thu, Jun 21, 2012 at 8:10 PM, rusty 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

[algogeeks] Re: Microsoft Interview Question

guys this is my solution to the problem, it's a bit sloppy but as far as I checked it was working please have a go at it? #include #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

[algogeeks] Re: Microsoft Interview Question

@akshat ur code doesn't give intact output, so i modified ur code and here is the code : int j=0,k=0; for (i = 0; i < n; ++i) { if(a[i]<0) { a[j] = a[i]; j++; } else { temp[k] = a[i]; k++; } } k=0; for (i = j; i < n; ++i) {

Re: [algogeeks] Re: Microsoft question

refer to this link . or Using quicksort , it can be done in O(n). One more way to do this is to make min heap of size-k. Then insert elements from the original array.If element is greater than root of the heap,swap them.In the Last, root of the heap

Re: [algogeeks] Re: Microsoft question

Hi, It looks like, The interviewer is expecting MinHeap from you, If modification to array is permitted just build the heap in place (from end bubbleUp n-1 time) and extract K elements in sorted order Otherwise you need minimum O(K) memory Again if you want to use the quick-sort, I wou

Re: [algogeeks] Re: Microsoft question

This can be done using the concept of median of medians, wherein we can achieve linear time complexity in the worst case. This is a concept used in parallel algorithms too, check it out. On Mon, Jun 18, 2012 at 5:38 PM, Prem Nagarajan wrote: > @enchantress : This problem can be solved using quick

Re: [algogeeks] Re: Microsoft question

@enchantress : This problem can be solved using quicksort in O(nlogn). No need to go for selection sort. But O(n) solution is needed. On Mon, Jun 18, 2012 at 2:50 PM, enchantress wrote: > > Hi all, > A variation of selection sort can be used which takes O(nk) time. > > for i 1 to k > min_index

[algogeeks] Re: Microsoft question

Hi all, A variation of selection sort can be used which takes O(nk) time. for i 1 to k min_index = i for j i+1 to n if a[j] < a[min_index] min_index = j swap(a[i],a[min_index]) required element : a[k] On Sunday, 17 June 2012 08:13:18 UTC+5:30, Prem Nagarajan wrote: > > Give

[algogeeks] Re: Microsoft question

We can use Median of medians http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm On Sunday, 17 June 2012 08:13:18 UTC+5:30, Prem Nagarajan wrote: > > Give an array of unsorted elements, find the kth smallest element in the > array.

[algogeeks] Re: Microsoft Interview Question

@ayush goel couldnt really understand your algo , can you please explain little bit more . On Wednesday, 13 June 2012 21:49:49 UTC+5:30, Krishna Kishore wrote: > > Given a array of integers both positive and negative and you need to shift > positive numbers to one side > and negative numbers to

[algogeeks] Re: Microsoft Interview Question

Root of a graph can be any node whose in-degree is zero. i.e. there are no nodes pointing to that node. It can be found by using O( |V| ) space and O( |E| ) time . Now we can choose any node whose in-degree is zero if present. or choose any random node and itf DFS-tree is the desired tree. Ti

[algogeeks] Re: Microsoft Question

Queue can be defined as a priority queue where priority decreases with time. Hence an element inserted later has lower priority and goes to back of queue. (FIFO) Stack can be defined as a priority queue where priority increases with time.Hence an element inserted later has higher priority and g

Re: [algogeeks] Re: Microsoft interview question

@Partha try with: A = {2, 2, 9} B= {1, 6, 6} On Mon, May 21, 2012 at 7:08 PM, partha sarathi Mohanty < partha.mohanty2...@gmail.com> wrote: > a[] = [-1,-3,4,0,7,0,36,2,-3] > b[] = [0,0,6,2,-1,9,28,1,6] > b1[] = [0,7,0,36,4,-6,3,0,0] > b2[] =[-1,-3,11,0,0,0,35,0,0] > > suma = 42 proda = -

Re: [algogeeks] Re: Microsoft interview question

a[] = [-1,-3,4,0,7,0,36,2,-3] b[] = [0,0,6,2,-1,9,28,1,6] b1[] = [0,7,0,36,4,-6,3,0,0] b2[] =[-1,-3,11,0,0,0,35,0,0] suma = 42 proda = -84*72*3 sumb = 51 prodb = -84*72*3 sumb1 = 44 prodb1 = -84*72*3 sumb2 = 42 prodb2 = 33*35 do the sum and prod operation w/o 0s and compare the values..

Re: [algogeeks] Re: Microsoft interview question

@ashish.. it wont be constant space then.. surely it will be o(n) though On Mon, May 21, 2012 at 7:23 PM, Ashish Goel 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 s

Re: [algogeeks] Re: Microsoft interview question

constant space vs no additional space and then O(n) time complexity not possible.. Best Regards Ashish Goel "Think positive and find fuel in failure" +919985813081 +919966006652 On Mon, May 21, 2012 at 8:01 PM, Dave wrote: > @Ashish: Using a hash table violates the O(1) space requirement given

Re: [algogeeks] Re: Microsoft interview question

@Ashish: Using a hash table violates the O(1) space requirement given in the original problem. Dave On Monday, May 21, 2012 8:53:44 AM UTC-5, ashgoel wrote: > Dave, > > Cant we have a hash table with the item as key and its count as value > (walk over array A and build HT). > For permutation

[algogeeks] Re: Microsoft interview question

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 particul

[algogeeks] Re: Microsoft interview question

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

Re: [algogeeks] Re: Microsoft interview question

Dave, Cant we have a hash table with the item as key and its count as value (walk over array A and build HT). For permutation check, walk over second array and start reducing the count and remove when count becomes zero for that particular key. If some char not there in HT, return false, else retu

[algogeeks] Re: Microsoft interview question

No way u can do it in O(1) space and O(n) time.sols above are not gonna work..yeah, it is possible in O(n) space and O(n) time. On May 20, 12:29 am, HARSHIT PAHUJA 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

Re: [algogeeks] Re: Microsoft interview question

@Piyush: Did you even try this on any examples? If not, try a = {0,1,2,3} and b = {0,2,2,2}. Dave On Sunday, May 20, 2012 1:39:25 AM UTC-5, Kalyan wrote: > Piyush. I think we can use your logic. But You should check the product > also. > Have 4 variables, sum_a,sum_b , prod_a, prod_b > > Ca

[algogeeks] Re: Microsoft interview question

@Gaurav: you are taking ia and ib as int so they will have 32 bits in Java. So you can not set the bits for numbers in the array greater than 32. e.g if you have a[i]=59876 so you would want to set the 59876th bit in ia : ia=ia | (1<<59876) but that is not possible. How do you handle this? Also how

Re: [algogeeks] Re: Microsoft interview question

@Piyush: Try this i/p 8,0,0 ; 2,6,0-- Ur algo aint adequate.. On Sat, May 19, 2012 at 11:24 PM, Piyush Khandelwal < piyushkhandelwal...@gmail.com> wrote: > Hiii!! I have some idea about the solution. Please notify me if i am > wrong > > a= [ 4,3,5 ] and b= [ 3,5,4 ] > diff=0; > for (i=0; i

Re: [algogeeks] Re: Microsoft interview question

Piyush. I think we can use your logic. But You should check the product also. Have 4 variables, sum_a,sum_b , prod_a, prod_b Calculate Sum and product of array 'a' and store it in sum_a,prod_a Calculate Sum and product of array 'b' and store it in sum_b,prod_b if sum_a=sum_b && prod_a==prod_b the

Re: [algogeeks] Re: Microsoft interview question

@piyush : your solution will fail for the case a={5,1,1} b={3,3,1} On Sun, May 20, 2012 at 11:54 AM, Piyush Khandelwal < piyushkhandelwal...@gmail.com> wrote: > Hiii!! I have some idea about the solution. Please notify me if i am > wrong > > a= [ 4,3,5 ] and b= [ 3,5,4 ] > diff=0; > for (i=0;

Re: [algogeeks] Re: Microsoft interview question

U are checking if the sum is same or not.. which can be same even if the elements are different. On Sun, May 20, 2012 at 11:54 AM, Piyush Khandelwal < piyushkhandelwal...@gmail.com> wrote: > Hiii!! I have some idea about the solution. Please notify me if i am > wrong > > a= [ 4,3,5 ] and b= [

Re: [algogeeks] Re: Microsoft interview question

Hiii!! I have some idea about the solution. Please notify me if i am wrong a= [ 4,3,5 ] and b= [ 3,5,4 ] diff=0; for (i=0; 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 -12t

[algogeeks] Re: Microsoft interview question

@Harshit: These are a few unanswered questions that came to mind when I read your solution attempt: What do you do with negative elements? What is the -12th prime number? How do you deal with overflow in the cases where you have a lot of large prime numbers and the product exceeds your native d

Re: [algogeeks] Re: Microsoft Interview Question

Well, the interviewer gave a hint to use hash-table. The key of hash-table will be memory address of original node and value will be the memory address of the new node. On Wed, Mar 14, 2012 at 9:43 PM, atul anand wrote: > @umer : did interviewer told any one of the solution provided in > the g

Re: [algogeeks] Re: Microsoft Interview Question

@umer : did interviewer told any one of the solution provided in the given link below or different? http://www.geeksforgeeks.org/archives/1155 On Tue, Mar 13, 2012 at 11:31 AM, Umer Farooq wrote: > Yes that is exactly what they wanted. I proposed BFS for this solution. > Anyway, there was ano

[algogeeks] Re: Microsoft Interview Question

Sorry, a small test showed a loop quitting one iteration too soon. Here is the fix. import java.util.Random; public class ListCopy { class Node { int val; Node next, other; Node() { } Node(int val, Node next, Node other) { this.val = val;

[algogeeks] Re: Microsoft Interview Question

Copying a full graph requires a BFS or DFS. But here we have a big advantage. We know the nodes are linked in a single chain. So we don't need to search to find all nodes. We can just use .next pointers. No matter how we do things, we will need Map(A) that returns the copy of node A if it alre

[algogeeks] Re: Microsoft Interview Question

This problem is close to copying a graph. For that as you said, just do DFS or BFS and maintain a map from original nodes to copies. Use the copy to set pointers whenever it exists. When it doesn't exist, make a new node and add it to the map. You can implement the map in various ways. A hash t

Re: [algogeeks] Re: Microsoft Interview Question

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.

Re: [algogeeks] Re: Microsoft Interview Question

Yes that is exactly what they wanted. I proposed BFS for this solution. Anyway, there was another problem that I was able to solve; but the interviewer brought up a much more efficient approach. The problem was: - Given a linked a linked list with one pointer pointing to next, another poin

Re: [algogeeks] Re: Microsoft Interview Question

Yes that is exactly what they wanted. I proposed BFS for this solution. Anyway, there was another problem that I was able to solve; but the interviewer brought up a much more efficient approach. The problem was: Given a linked l On Mon, Mar 12, 2012 at 11:31 PM, Gene wrote: > Since there is no

[algogeeks] Re: Microsoft Interview Question

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 vi

[algogeeks] Re: MICROSOFT IDC: unsorted linked lists intersection

@Ashish We can sort a list in another way as follows: 1) Recursively divide the list into two halves.. 2) Call merge while joining the sorted lists.. MergeSort(node * p) { if ( p contains only one element) return p; p1 = MergeSort(first half of list pointed by p);

[algogeeks] Re: MICROSOFT IDC: unsorted linked lists intersection

@Ashish.. I have something in mind.. but would require verification by u.. Lets say, the structure of the data node is as follows: struct node { int data; struct node *next; }; Now, given 2 sorted linked lists we can right a O(N) time and in-place merge process, to build a sorted merged l

Re: [algogeeks] Re: Microsoft Question

On 10/29/11, praveen raj wrote: > Priority Queue: > when popped ... returns the max priority element and if the priorities > of two or more elements are same...then they will popped as they are > inserted .. > when pushed the element : puts the element in the list according to the > pr

Re: [algogeeks] Re: Microsoft Question

Priority Queue: when popped ... returns the max priority element and if the priorities of two or more elements are same...then they will popped as they are inserted .. when pushed the element : puts the element in the list according to the priority... For making priority queue into Qu

Re: [algogeeks] Re: MICROSOFT WRITTEN

return (((-1+!x)&y) | ((-1+!!x)&z)) ; On Sun, Oct 2, 2011 at 3:18 PM, ravi maggon wrote: > How about this answer: > b?z:y > > int main() { >     int a=0,b,y=4,z=5,k; >     cin>>b; >     k=(((b+~a+1)>>7)&1);//k will either be 0 or 1 >     cout<< (z-int((bool)k&(z-y))); >     return 0; > } > > On

Re: [algogeeks] Re: MICROSOFT WRITTEN

How about this answer: b?z:y int main() { int a=0,b,y=4,z=5,k; cin>>b; k=(((b+~a+1)>>7)&1);//k will either be 0 or 1 cout<< (z-int((bool)k&(z-y))); return 0; } On Mon, Sep 12, 2011 at 5:32 PM, beginner wrote: > although multiplication operator is not allowed.. > but it's an

Re: [algogeeks] Re: microsoft interview

@Teja Bala U dont need the last line for a[0][0] else code will be wrong conside 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 Regards On Sun, Sep 11, 2011 at 11:56 PM, teja bala wrote: > //pseudo code dis will work for sure. > > for(i=0;i for(j=0;j { > if (a[i][j] == 1) >

Re: [algogeeks] Re: MICROSOFT IDC

Congrats Saurabh. On Fri, Sep 23, 2011 at 7:18 PM, sagar pareek wrote: > congrates dude > > > On Thu, Sep 22, 2011 at 7:26 PM, Sanjay Rajpal wrote: > >> Saurabh : Thank u very much :) >> >> Sanju >> :) >> >> >> >> On Thu, Sep 22, 2011 at 6:15 AM, saurabh wrote: >> >>> thanx to all >>> >>> @san

Re: [algogeeks] Re: MICROSOFT IDC

congrates dude On Thu, Sep 22, 2011 at 7:26 PM, Sanjay Rajpal wrote: > Saurabh : Thank u very much :) > > Sanju > :) > > > > On Thu, Sep 22, 2011 at 6:15 AM, saurabh wrote: > >> thanx to all >> >> @sanjay I have shared my interview experience at >> http://msidcinterview.blogspot.com/ >> >> -- >

Re: [algogeeks] Re: Microsoft Question

@kartik.,...where are u searching..that ..the next character should be present..only around the 8 possible locations around that character On Thu, Sep 22, 2011 at 6:34 AM, kartik sachan wrote: > @dheeraj i didn't get what u want to say explain me with the help of > example > > -- > You received

Re: [algogeeks] Re: MICROSOFT IDC

Saurabh : Thank u very much :) Sanju :) On Thu, Sep 22, 2011 at 6:15 AM, saurabh wrote: > thanx to all > > @sanjay I have shared my interview experience at > http://msidcinterview.blogspot.com/ > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Gee

Re: [algogeeks] Re: Microsoft Question

@dheeraj i didn't get what u want to say explain me with the help of example -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algog

[algogeeks] Re: MICROSOFT IDC

thanx to all @sanjay I have shared my interview experience at http://msidcinterview.blogspot.com/ -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group

Re: [algogeeks] Re: Microsoft Question

@kartik: i thnk u r searching for string...that may have characters..in the 2d matrix ..NO MATTER WHERE THEY ARE.. On Wed, Sep 21, 2011 at 7:10 PM, kartik sachan wrote: > i think i can solve this in O(n^2) > here is code http://ideone.com/Gk69A > > # include# includechar a[100][100];int findword

Re: [algogeeks] Re: Microsoft Question

i think i can solve this in O(n^2) here is code http://ideone.com/Gk69A # include# includechar a[100][100];int findword(int *b,int n,int m){ int i,j,flag=0; char s[1]; for(i=0;ihttp://www.opengroup.org/onlinepubs/009695399/functions/printf.html>("word is there in matrix

Re: [algogeeks] Re: Microsoft Question

@piyush: what is time and space complexity of u'r sol.. On Mon, Sep 19, 2011 at 11:03 AM, Piyush Grover wrote: > sry, in the findWord function all a's are different e.g > a0, a1a7 > > and if(!a) is actually if(a0||a1||...||a7) > > thnx > piyush > > > On Mon, Sep 19, 2011 at 1:10 AM, Piyush G

Re: [algogeeks] Re: Microsoft Question

sry, in the findWord function all a's are different e.g a0, a1a7 and if(!a) is actually if(a0||a1||...||a7) thnx piyush On Mon, Sep 19, 2011 at 1:10 AM, Piyush Grover wrote: > for(i = 0; i < n; i++) >for(j = 0; j < n; j++){ > setColor(i, j) = black; >if(A[i][j] == str[0]){

Re: [algogeeks] Re: Microsoft Question

for(i = 0; i < n; i++) for(j = 0; j < n; j++){ setColor(i, j) = black; if(A[i][j] == str[0]){ setColor(i, j) = blue; a = findWord(A, i, j, str, 1) if(!a) setColor(i, j) = black; else break; } } findWord(A, i, j, str, k){ if(k

[algogeeks] Re: Microsoft Question

hmm, nice questions, can we create an efficient DS to query the strings ?? tried using trie but memory prints are very large ( O(n^2) )? :-(( On Sep 18, 12:59 pm, Anup Ghatage wrote: > For the mentioned scenario, it seems to be the only feasible solution. > > On Sun, Sep 18, 2011 at 3:57 AM,

[algogeeks] Re: Microsoft coming to PEC on 19th, any specific pattern for written test

PEC main mca hai hi nahin :P khaali B.E and M.E hai and from this year they have started M.Sc Ankur On Sep 15, 11:41 pm, vivek goel wrote: > hey  ankur.. >  thnaks  for ur concern.. > *mca *was not eligible kya.. > > > > > > > > On Fri, Sep 16, 2011 at 12:04 AM, techankur wr

Re: [algogeeks] Re: Microsoft coming to PEC on 19th, any specific pattern for written test

hey ankur.. thnaks for ur concern.. *mca *was not eligible kya.. On Fri, Sep 16, 2011 at 12:04 AM, techankur wrote: > @Vivek Microsoft is open for CSE and IT department (B.Tech/M.Tech).. > The eligibility is 7 CGPA > @Rahul we don't have any information about the profile b

[algogeeks] Re: Microsoft coming to PEC on 19th, any specific pattern for written test

@Vivek Microsoft is open for CSE and IT department (B.Tech/M.Tech).. The eligibility is 7 CGPA @Rahul we don't have any information about the profile being offered, currently just the written test is taken on 19th which would be for 1 hr, no pre placement talks nothing.. @abhinav I already own a co

Re: [algogeeks] Re: MICROSOFT WRITTEN IN VASAVI

char str[10]; int length,count; void fun(int x) { if(x==length) printf("%d %s\n",++count,str); else { fun(x+1); str[x]-=32; fun(x+1); str[x]+=32; } } int main() { scanf("%s",str); length=strlen(str); fun(0); getch(); }

Re: [algogeeks] Re: Microsoft Question

For Stack: just make a structure: struct stack_with_priorityqueue { int num; int priority; struct stack_with_priorityqueue *ptr; } now when we add another number just increase the priority... priority++ For Queue: do same...just decrease priority...priority-- ...

[algogeeks] Re: MICROSOFT in VJTI mumbai

@Bharatkumar bagana : that is a standard Qs which uses line sweep algo and has O(n lgn) soln other than the trivial O(n^2) soln... google that Qs... @tej bala: out of 10.. 5-6 were output type obj Q... then 1 was what's full form of GCC... its gnu compiler collection.. i made mistake in this Q.. @d

  1   2   3   4   >