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

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

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

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

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

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

Re: [algogeeks] Re: Microsoft Question

The well known examples of priority queue is minheap and maxheap.. i guess the question is how do we implement one of these(at least) using queue? On Wed, Sep 14, 2011 at 9:08 AM, Ankuj Gupta wrote: > I guess the functionality of priority should be maintained > > On Sep 13, 11:59 pm, Ankur Garg

Re: [algogeeks] Re: Microsoft Question

But dude are u saying stack will be implemented as a map with and then choose element based on priority ? regards Ankur On Tue, Sep 13, 2011 at 10:16 PM, Ankuj Gupta wrote: > > For stack :- Keep incrementing the priority of each pushed element. So > the last pushed element will have the great

Re: [algogeeks] Re: Microsoft Question!

thank u:) -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this gro

Re: [algogeeks] Re: Microsoft Question!

thnx ... :D On Fri, Jul 22, 2011 at 9:19 PM, sagar pareek wrote: > gr8 shubham > > On Fri, Jul 22, 2011 at 1:42 PM, Shubham Maheshwari > wrote: > >> x = 0; >> while( n ){ >> x <<= 1; >> x = x | ( n & 1); >> n >>= 1; >> } >> >> return x; >> >> On Fri, Jul 22, 2011 at 1:31 PM, Puneet Gautam >> w

Re: [algogeeks] Re: Microsoft Question!

gr8 shubham On Fri, Jul 22, 2011 at 1:42 PM, Shubham Maheshwari wrote: > x = 0; > while( n ){ > x <<= 1; > x = x | ( n & 1); > n >>= 1; > } > > return x; > > On Fri, Jul 22, 2011 at 1:31 PM, Puneet Gautam wrote: > >> sorry guys.. dont check the above siolution.. its wrong...!!! >> misread it.. >>

Re: [algogeeks] Re: Microsoft Question!

x = 0; while( n ){ x <<= 1; x = x | ( n & 1); n >>= 1; } return x; On Fri, Jul 22, 2011 at 1:31 PM, Puneet Gautam wrote: > sorry guys.. dont check the above siolution.. its wrong...!!! > misread it.. > > > On 7/22/11, Puneet Gautam wrote: > > check this out: Considering all 4 bytes of int with

Re: [algogeeks] Re: Microsoft Question!

sorry guys.. dont check the above siolution.. its wrong...!!! misread it.. On 7/22/11, Puneet Gautam wrote: > check this out: Considering all 4 bytes of int with no left or right > shifts..!! > ;) > > main() > { unsigned int i,j,k,no=1; > j=4; > for(k=0;k<32;k++) >

Re: [algogeeks] Re: Microsoft Question!

check this out: Considering all 4 bytes of int with no left or right shifts..!! ;) main() { unsigned int i,j,k,no=1; j=4; for(k=0;k<32;k++) no*=2; no=no-j; cout<<"\n The reverse is"< wrote: > see this > > http://geeksforgeeks.org/?p=726 > > On Fri

Re: [algogeeks] Re: Microsoft Question!

see this http://geeksforgeeks.org/?p=726 On Fri, Jul 22, 2011 at 4:29 AM, adhyetha wrote: > reverse(int n) > { >int i, result = 0; > >for(i = 0; i < 32; i++) > result |= ((n >> i) & 1) << (31 - i); > } > > > assuming 32 bit integer to be reversed and assuming all 32 bits

Re: [algogeeks] Re: Microsoft Question!

I love the topcoder things. :) On Thu, Jul 21, 2011 at 8:09 PM, SkRiPt KiDdIe wrote: > To get complete 32 bit inverse : > > x=((x>>1)&0x) | ((x<<1)&0x); > x=((x>>2)&0x) | ((x<<2)&0x); > x=((x>>4)&0x0F0F0F0F) | ((x<<4)&0xF0F0F0F0); >

Re: [algogeeks] Re: Microsoft Question!

Solution assuming MSB the last digit x=((x>>1)&0x) | ((x<<1)&0x); x=((x>>2)&0x) | ((x<<2)&0x); x=((x>>4)&0x0F0F0F0F) | ((x<<4)&0xF0F0F0F0); x=((x>>8)&0x00FF00FF) | ((x<<8)&0xFF00FF00); x=((x>>16)&0x) | ((x<<16)&0

Re: [algogeeks] Re: Microsoft Question!

Yes, that's correct what is wrong with that? Basically when n&1 occurs, it kind of initiates the multiplication by m by setting m+=1. So, After that, m gets multiplied by 2 which is nothing but left shift by 1. n=100 m remains 0 as n&1==0 so m=0; n-> 10; 2. n=10 m*2-> m=0; n&1=0 so m=0; n->1; 3 n

Re: [algogeeks] Re: Microsoft Question!

No actually its fine if the number is 1100...bt for 0100 it gives only 0001 bec it only increments it once after shifting thrice and thn it becomes and it exits and so m nvr gets multiplied by 2... On Thu, Jul 21, 2011 at 10:01 PM, archita monga wrote: > @aditi-the algo is giving a problem

Re: [algogeeks] Re: Microsoft Question!

Ankit's Solution is actually based on the assumption that we will only reverse bits till MSB which is set. So, for 0100 It will reverse will 100, so the answer should be one. On 7/21/11, aditi garg wrote: > i have tried solving so many tyms bt i dnt think dis also is wrking fine fr > 0100 input.

Re: [algogeeks] Re: Microsoft Question!

@aditi-the algo is giving a problem when the last bit is 0..just like in ur case..when the number is being reversed instead of 0010 it is giving only 10 and neglecting the initial 0's since dey do not contribute in the number..i guess dis is d prob dat u r facing? On Thu, Jul 21, 2011 at 9:57 PM,

Re: [algogeeks] Re: Microsoft Question!

i have tried solving so many tyms bt i dnt think dis also is wrking fine fr 0100 input..plz chk On Thu, Jul 21, 2011 at 9:49 PM, aditi garg wrote: > @ankit : smhow im not able to follow the steps ur also is taking fr input > 0100 ,tho its fine fr 1011 and im not getting the required ans...can u

Re: [algogeeks] Re: Microsoft Question!

@ankit : smhow im not able to follow the steps ur also is taking fr input 0100 ,tho its fine fr 1011 and im not getting the required ans...can u plz explain... On Thu, Jul 21, 2011 at 8:31 PM, Aman Goyal wrote: > @ankit gupta: superb solutn > > > On Thu, Jul 21, 2011 at 8:09 PM, SkRiPt KiDdIe wr

Re: [algogeeks] Re: Microsoft Question!

@ankit gupta: superb solutn On Thu, Jul 21, 2011 at 8:09 PM, SkRiPt KiDdIe wrote: > To get complete 32 bit inverse : > > x=((x>>1)&0x) | ((x<<1)&0x); > x=((x>>2)&0x) | ((x<<2)&0x); > x=((x>>4)&0x0F0F0F0F) | ((x<<4)&0xF0F0F0F0); > x=(

Re: [algogeeks] Re: Microsoft Question!

To get complete 32 bit inverse : x=((x>>1)&0x) | ((x<<1)&0x); x=((x>>2)&0x) | ((x<<2)&0x); x=((x>>4)&0x0F0F0F0F) | ((x<<4)&0xF0F0F0F0); x=((x>>8)&0x00FF00FF) | ((x<<8)&0xFF00FF00); x=((x>>16)&0x) | ((x<<16)&0x)