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[],
well we can do with just one array. Overwrite the answer directly on left[]
array.
On Thu, Aug 16, 2012 at 6:47 PM, mohit mohitsingh1...@gmail.com wrote:
here are the steps :
1) Construct a temporary array left[] such that left[i] contains product
of all elements on left of A[i] excluding
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,
We have to consider cases when an element is zero.
On Thu, Aug 16, 2012 at 7:07 PM, shady sinv...@gmail.com wrote:
well we can do with just one array. Overwrite the answer directly on
left[] array.
On Thu, Aug 16, 2012 at 6:47 PM, mohit mohitsingh1...@gmail.com wrote:
here are the steps
@Navin: Why? No division is used.
Dave
On Thursday, August 16, 2012 9:20:03 AM UTC-5, Navin Kumar wrote:
We have to consider cases when an element is zero.
On Thu, Aug 16, 2012 at 7:07 PM, shady sin...@gmail.com javascript:wrote:
well we can do with just one array. Overwrite the answer
refer to this link http://www.ics.uci.edu/~eppstein/161/960130.html.
or Using quicksort , it can be done in O(n).
One more way to do this is to make min heap of size-k. Then insert elements
from the original array.If element is greater than root of the heap,swap
them.In the Last, root of the heap
Can't we use k iterations of bubble sort ?
On Jun 18, 2012 2:11 PM, Ramindar Singh ramin...@gmail.com wrote:
We can use Median of medians
http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm
On Sunday, 17 June 2012 08:13:18
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
This can be done using the concept of median of medians, wherein we can
achieve linear time complexity in the worst case.
This is a concept used in parallel algorithms too, check it out.
On Mon, Jun 18, 2012 at 5:38 PM, Prem Nagarajan prem.cmna...@gmail.comwrote:
@enchantress : This problem can
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.
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
@enchantress : This problem can be solved using quicksort in O(nlogn). No
need to go for selection sort.
But O(n) solution is needed.
On Mon, Jun 18, 2012 at 2:50 PM, enchantress elaenjoy...@gmail.com wrote:
Hi all,
A variation of selection sort can be used which takes O(nk) time.
for i 1
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
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
On 10/29/11, praveen raj praveen0...@gmail.com wrote:
Priority Queue:
when popped ... returns the max priority element and if the priorities
of two or more elements are same...then they will popped as they are
inserted ..
when pushed the element : puts the element in the list
@kartik:
i thnk u r searching for string...that may have characters..in the 2d matrix
..NO MATTER WHERE THEY ARE..
On Wed, Sep 21, 2011 at 7:10 PM, kartik sachan kartik.sac...@gmail.comwrote:
i think i can solve this in O(n^2)
here is code http://ideone.com/Gk69A
# includestdio.h#
@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
@kartik.,...where are u searching..that ..the next character should be
present..only around the 8 possible locations around that character
On Thu, Sep 22, 2011 at 6:34 AM, kartik sachan kartik.sac...@gmail.comwrote:
@dheeraj i didn't get what u want to say explain me with the help of
example
i think i can solve this in O(n^2)
here is code http://ideone.com/Gk69A
# includestdio.h# includestring.hchar a[100][100];int findword(int
*b,int n,int m){
int i,j,flag=0;
char s[1];
for(i=0;in;i++)
for(j=0;jm;j++)
s[a[i][j]]++;
@piyush: what is time and space complexity of u'r sol..
On Mon, Sep 19, 2011 at 11:03 AM, Piyush Grover
piyush4u.iit...@gmail.comwrote:
sry, in the findWord function all a's are different e.g
a0, a1a7
and if(!a) is actually if(a0||a1||...||a7)
thnx
piyush
On Mon, Sep 19, 2011 at
hmm, nice questions, can we create an efficient DS to query the
strings ??
tried using trie but memory prints are very large ( O(n^2) )? :-((
On Sep 18, 12:59 pm, Anup Ghatage ghat...@gmail.com wrote:
For the mentioned scenario, it seems to be the only feasible solution.
On Sun, Sep 18,
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
sry, in the findWord function all a's are different e.g
a0, a1a7
and if(!a) is actually if(a0||a1||...||a7)
thnx
piyush
On Mon, Sep 19, 2011 at 1:10 AM, Piyush Grover piyush4u.iit...@gmail.comwrote:
for(i = 0; i n; i++)
for(j = 0; j n; j++){
setColor(i, j) = black;
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--
...
The well known examples of priority queue is minheap and maxheap..
i guess the question is how do we implement one of these(at least) using
queue?
On Wed, Sep 14, 2011 at 9:08 AM, Ankuj Gupta ankuj2...@gmail.com wrote:
I guess the functionality of priority should be maintained
On Sep 13,
For stack :- Keep incrementing the priority of each pushed element. So
the last pushed element will have the greatest priority and the
element pushed first will have
lowest priority.
For queue:- keep decrementing the priority of each inserted element.
On Sep 13, 1:45 am, Ankur Garg
But dude are u saying stack will be implemented as a map with
value,priority
and then choose element based on priority ?
regards
Ankur
On Tue, Sep 13, 2011 at 10:16 PM, Ankuj Gupta ankuj2...@gmail.com wrote:
For stack :- Keep incrementing the priority of each pushed element. So
the last
I guess the functionality of priority should be maintained
On Sep 13, 11:59 pm, Ankur Garg ankurga...@gmail.com wrote:
But dude are u saying stack will be implemented as a map with
value,priority
and then choose element based on priority ?
regards
Ankur
On Tue, Sep 13, 2011 at
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;k32;k++)
no*=2;
no=no-j;
cout\n The reverse isno;
getch();
return 0;
}
On 7/22/11, nicks
sorry guys.. dont check the above siolution.. its wrong...!!!
misread it..
On 7/22/11, Puneet Gautam puneet.nsi...@gmail.com 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;k32;k++)
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 puneet.nsi...@gmail.comwrote:
sorry guys.. dont check the above siolution.. its wrong...!!!
misread it..
On 7/22/11, Puneet Gautam puneet.nsi...@gmail.com wrote:
check this out:
gr8 shubham
On Fri, Jul 22, 2011 at 1:42 PM, Shubham Maheshwari
shubham@gmail.comwrote:
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 puneet.nsi...@gmail.comwrote:
sorry guys.. dont check the above siolution.. its
thnx ...
:D
On Fri, Jul 22, 2011 at 9:19 PM, sagar pareek sagarpar...@gmail.com wrote:
gr8 shubham
On Fri, Jul 22, 2011 at 1:42 PM, Shubham Maheshwari shubham@gmail.com
wrote:
x = 0;
while( n ){
x = 1;
x = x | ( n 1);
n = 1;
}
return x;
On Fri, Jul 22, 2011 at 1:31 PM,
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
To get complete 32 bit inverse :
x=((x1)0x) | ((x1)0x);
x=((x2)0x) | ((x2)0x);
x=((x4)0x0F0F0F0F) | ((x4)0xF0F0F0F0);
x=((x8)0x00FF00FF) | ((x8)0xFF00FF00);
x=((x16)0x) | ((x16)0x);
--
You received this
@ankit gupta: superb solutn
On Thu, Jul 21, 2011 at 8:09 PM, SkRiPt KiDdIe anuragmsi...@gmail.comwrote:
To get complete 32 bit inverse :
x=((x1)0x) | ((x1)0x);
x=((x2)0x) | ((x2)0x);
x=((x4)0x0F0F0F0F) | ((x4)0xF0F0F0F0);
@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 aman.goya...@gmail.com wrote:
@ankit gupta: superb solutn
On Thu, Jul 21, 2011 at 8:09
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 aditi.garg.6...@gmail.comwrote:
@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
@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
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 aditi.garg.6...@gmail.com wrote:
i have tried solving so many tyms bt i dnt think dis also is
Yes, that's correct what is wrong with that?
Basically when n1 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 n1==0 so m=0;
n- 10;
2. n=10
m*2- m=0;
n1=0 so m=0;
n-1;
3 n=1;
Solution assuming MSB the last digit
x=((x1)0x) | ((x1)0x);
x=((x2)0x) | ((x2)0x);
x=((x4)0x0F0F0F0F) | ((x4)0xF0F0F0F0);
x=((x8)0x00FF00FF) | ((x8)0xFF00FF00);
x=((x16)0x) | ((x16)0x);
I love the topcoder things. :)
On Thu, Jul 21, 2011 at 8:09 PM, SkRiPt KiDdIe anuragmsi...@gmail.comwrote:
To get complete 32 bit inverse :
x=((x1)0x) | ((x1)0x);
x=((x2)0x) | ((x2)0x);
x=((x4)0x0F0F0F0F) | ((x4)0xF0F0F0F0);
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
to be reversed.. i.e 100101 reverses to
10100100
--
You received this message because
see this
http://geeksforgeeks.org/?p=726
On Fri, Jul 22, 2011 at 4:29 AM, adhyetha ranjith.kaga...@gmail.com 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
unsigned int reverse_bits (unsigned int n)
{
unsigned int m;
m=0;
while(n) {
m*=2;
if( n1 ) {
m+=1;
}
n=1;
}
return m;
}
--
You received this message because you are subscribed to the Google Groups
This is pretty standard stuff. Look up finite automaton.
On Aug 9, 9:30 am, amit amitjaspal...@gmail.com wrote:
Given a text file, implement a solution to find out if a pattern
similar to wild cards can be detected.
fort example find if a*b*cd*, or *win or *def* exists in the text.
--
You
47 matches
Mail list logo
