@all
plz.. tell if this thing would work..
assume 2 in place of every 0 in array. ie
1 1 0 0 0 1 0 1 be
1 1 2 2 2 1 2 1
then find max sub array wid sum length/2 * 3.
this can be done in O(n) but worst case would still be O(n lgn) .
On 1/26/12, Sanjay Rajpal sanjay.raj...@live.in wrote:
+1
Consider 2 temp arrays, B and C
Where B gets updated for every find of 0 and C for every find of 1
i.e if(a[i]==0)
b[i]+=b[i-1]+1;
c[i]=c[i-1];
i.e if(a[i]==1)
c[i]+=c[i-1]+1;
b[i]=b[i-1];
if(c[i]==b[i])
update max.
return max.
This is O(N) algo. Is it right or i
replace all 0s by -1
keep additional array to get the sumHere at every position of all -1s and
1s.
say you got
0 1 0 1 0 0 0 0 1 1 1 1 0
-1 1 -1 1 -1 -1 -1 -1 1 1 1 1 -1
sum -1 0 -1 0 -1 -2 -3 -4 -3 -2 -1 0 -1
all equal numbers in sum shows equal zeros and 1s between then
+1
*
Sanjay Kumar
B.Tech Final Year
Department of Computer Engineering
National Institute of Technology Kurukshetra
Kurukshetra - 136119
Haryana, India
Contact: +91-8053566286
*
On Thu, Jan 26, 2012 at 6:28 PM, Ashish Goel ashg...@gmail.com wrote:
replace all 0s by -1
keep additional array
Answer is already given in group search it...
PRAVEEN RAJ
DELHI COLLEGE OF ENGINEERING
--
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
yeah...u r right
--
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,
IT will grt help for me... if u all tell me..
mapstring,int m;
m[topcoder]=2
My question is this:
Is 2 is an key value??or index value of hash table...??...
kindly explain how actual mapping is done... in hash table...plz...
PRAVEEN RAJ
DELHI COLLEGE OF ENGINEERING
On Tue, Dec 27,
same question as above with one more task is given
4) FindAnyElement()
which will return any element present in that structure with O(1).
for given all 4 task
Please suggest which Data Structure is better now...?
Best Regards,
Pankaj Agarwal
--
You received this message because you are
@shashank and @samm: Is the deletion and searching is o(1). I doubt
On Sat, Oct 1, 2011 at 6:30 PM, SAMM somnath.nit...@gmail.com wrote:
Yaa it will work , but in case of deletion don't u think array will
not as efficient as linked list becoz array is Static we need to
define the memory b4
nice idea..
On Oct 20, 11:04 am, SUMANTH M sumanth.n...@gmail.com wrote:
- Take another sum array which contains sums of original array at each
index, here sum[0] = a[0]; sum[1] = a[0] + a[1]
;...sum[i]=a[0]+a[1]+...a[i];
- Traverse the sum array and search for duplicates.
ex: a[] =
+1 for Sumanth's solution.
On Oct 20, 12:03 pm, anshu mishra anshumishra6...@gmail.com wrote:
index = 0 1 2 3 4 5 6
ar = 0 1 2 -4 -3 6 -3
sumar = 0 1 3 -1 -4 2 -1
first index where we get the number which has already appeared in sumar will
be the last index of sub array whose
The hash table would be used by separate chaining method not open
addressing because it may not find the correct entry efficiently in
the hash table . In case of open addresssing the value gets entered in
the first available entry after collision.
In case of insertion :- (I have considered only
Dont know how to delete (how adress will be known of the node?
On Sat, Oct 1, 2011 at 12:27 PM, SAMMM somnath.nit...@gmail.com wrote:
The hash table would be used by separate chaining method not open
addressing because it may not find the correct entry efficiently in
the hash table . In case
@All Why don't try with combination of* hash-table Array* , It Will Work ,
try it out :P
Thanks
Shashank Mani
CSE, BIT Mesra
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
Yaa it will work , but in case of deletion don't u think array will
not as efficient as linked list becoz array is Static we need to
define the memory b4 hand..
On 10/1/11, WgpShashank shashank7andr...@gmail.com wrote:
@All Why don't try with combination of* hash-table Array* , It Will Work ,
however maximum subarray can be found in O(n)
just needs to get maximum difference in entries of each A[i]
[-2]-[5]
[-1]-[0, 2, 4, 6] maxdiff[-1] = 6-0
[0]-[-1, 1, 3, 7] maxdiff[0] = 7-(-1)
[1]-[8, 10] maxdiff[1] = 10-8
[2]-[9]
max(maxdiff[i]) = 8
surender
On Sun, Sep 11, 2011 at
This is the fastest way I can think of to do this, and it is linear to the
number of intervals there are.
Let L be your original list of numbers and A be a hash of empty arrays where
initially A[0] = [0]
sum = 0
for i in 0..n
if L[i] == 0:
sum--
A[sum].push(i)
elif L[i] == 1:
@Brijesh: +1
On Sun, Sep 11, 2011 at 2:14 PM, Brijesh brijeshupadhyay...@gmail.comwrote:
This is the fastest way I can think of to do this, and it is linear to the
number of intervals there are.
Let L be your original list of numbers and A be a hash of empty arrays
where initially A[0] =
This solution is not in O(n) time :(
Unfortunately interviewer wants O(n) .
On Sun, Sep 11, 2011 at 4:01 PM, Kunal Patil kp101...@gmail.com wrote:
@Brijesh: +1
On Sun, Sep 11, 2011 at 2:14 PM, Brijesh brijeshupadhyay...@gmail.comwrote:
This is the fastest way I can think of to do this,
As the author correctly mentions it:
Building the array is O(n) , but printing these intervals must be done in
linear time to the number of intervals.
Assuming n means number of elements in the original array
There are O(n^2) possible intervals, how can you print them in O(n) ???
On Sun, Sep 11,
Yeah :(
U r right dude ...I dont think O(n) solution can exist for this problem
On Sun, Sep 11, 2011 at 4:27 PM, Kunal Patil kp101...@gmail.com wrote:
As the author correctly mentions it:
Building the array is O(n) , but printing these intervals must be done in
linear time to the number of
If I correctly understood the question, It says:
1. 0= x[i] =1 for all i and for all x of line i.
2. y[i]y[i+1] means lines have positive slope
If line i is f(x,y): A[i]x + B[i]y -C[i], Use the following concept:
1. Find 1 line closest to the given point such that f(x,y) is of same
sign for both
I don't understand your point if y[i] y[i+1]
how come the slope is positive?
It's just that the i'th line will lie under line i+1th line.
On Sat, Aug 27, 2011 at 5:11 PM, monish001 monish.gup...@gmail.com wrote:
If I correctly understood the question, It says:
1. 0= x[i] =1 for all i and for
satisfy the point on lines, for point(x,y) to lie in between the two, the
f(x,y) value would have different sign.
This can be done using the binary search approach. Here is the pseudo code:
f(x,y) = Ax + By - C
(x0, y0)
initial Call: SearchLines(f, n/2, 0, n);
SearchLines(f, i, lower, upper){
pardon 1 small mistake
instead of
if(i == 0 || i == n)
return (lower, upper);
it should be
if(i == lower || i == upper)
return (lower, upper);
On Sat, Aug 27, 2011 at 8:31 PM, Piyush Grover piyush4u.iit...@gmail.comwrote:
satisfy the point on lines, for point(x,y) to lie in between the
why to bother this much...? just count the elements when popping and
output the middle one .
while(!s.empty()){
e= s.pop()
count++
q.enq(e);
}
count = 2;
while(count){
e = q.deq();
s.push(e);
count --;
}
output s.top()
while(!q.empty()){
e = q.deq();
s.push(e);
}
On Aug 22, 4:27 pm, Shravan
i wish u had read the question... it is simple.. push to new stack and then
pop back... number of elements count need to be there
On Mon, Aug 22, 2011 at 7:44 PM, muthu raj muthura...@gmail.com wrote:
No need to count the number of nodes. Since its implemented as a linked
list traverse the
No need to count the number of nodes. Since its implemented as a linked list
traverse the list with two two pointers one incremented one node next and
other incremented two nodes next simultaneously.
void delete_MiddleStack(node **h)
{
if(*h==NULL)
return;
node *p,*q;
p=*h;
count is required since its not implemented as LL
On Mon, Aug 22, 2011 at 7:47 PM, shady sinv...@gmail.com wrote:
i wish u had read the question... it is simple.. push to new stack and then
pop back... number of elements count need to be there
On Mon, Aug 22, 2011 at 7:44 PM, muthu raj
Sorry i dint read the question properly :)
*Muthuraj R
IV th Year , ISE
PESIT , Bangalore*
On Mon, Aug 22, 2011 at 7:24 AM, sukran dhawan sukrandha...@gmail.comwrote:
count is required since its not implemented as LL
On Mon, Aug 22, 2011 at 7:47 PM, shady sinv...@gmail.com wrote:
i wish
Hi,
How about the following approach.
lets take stack is stack1.
lets take 2 pointers , p1 and p2
for every pop , keep increment p1 , so that p1 will point to latest pop'ed
out element.
increment p2 for every odd count of pop's...
increment p2 , for 1 , 3 , 5 , pop'ings etc..
so at the end , p2
Since its not a Linked list,
so get middle value from top
pop till middle element and push elements in a new stack.
again push the elemetns back to original stack,except for the middle
element.
Ashima
M.Sc.(Tech)Information Systems
4th year
BITS Pilani
Rajasthan
On Mon, Aug 22, 2011 at 8:49
gn array - say a
hav extra array - say b - initialise all values to zero
ques 1:for(i=1;i=n;i++)
{
b[a[i]]++;
}
On Jul 20, 12:07 pm, siva viknesh sivavikne...@gmail.com wrote:
1.Given an array of size n. It contains numbers in the range 1 to n.
Each number is present at least once except
let A:: ((n(n+1)/2) - sum)
let B:: ((n(n+1)(2n+1)/6) - (sum of squares of elements))
then missing number = ((B/A) + A)/2;
complexity O(n).
space complexity O(1).
On Wed, Jul 20, 2011 at 12:47 PM, saurabh singh saurab...@gmail.com wrote:
Q1 can be solved using some simple maths:)
Q2 o(1) space o(n) sol.
traverse through the array.
do -1*a[abs(a[i])-1] if a[abs(a[i])-1) +ve else do nothing
traverse again to check for the indexes with +ve values.
On Wed, Jul 20, 2011 at 1:01 PM, Shubham Maheshwari
shubham.veloc...@gmail.com wrote:
let A:: ((n(n+1)/2) - sum)
let B::
simple one!! . all the missing nos which r not present b/w 1 to n will
be printed!! TC O(n)
#include stdio.h
#define size 1
int main()
{
int i, j, n;
scanf(%d, n);
int a[n + 1] ;
int b[n + 1] ;
a[0] = 0;
b[0] = 0;
for (i = 1; i =
space o(n) toomine takes o(1) space
On Wed, Jul 20, 2011 at 3:50 PM, JIƬΣN BAJIYA j.s.baj...@gmail.com wrote:
simple one!! . all the missing nos which r not present b/w 1 to n will
be printed!! TC O(n)
#include stdio.h
#define size 1
int main()
{
int i, j, n;
I doubt if it would work on the following example : size of array is
10, 5 and 7 are missing numbers
{1,2,3,4,6,6,6,8,9,10};
On Jul 20, 12:31 pm, Shubham Maheshwari shubham.veloc...@gmail.com
wrote:
let A:: ((n(n+1)/2) - sum)
let B:: ((n(n+1)(2n+1)/6) - (sum of squares of elements))
then
I doubt if it would work on the following example : size of array is
10, 5 and 7 are missing numbers
{1,2,3,4,6,6,6,8,9,10};
On Jul 20, 1:04 pm, Shubham Maheshwari shubham.veloc...@gmail.com
wrote:
@saurabh.
kindly use a lil bit of indentation ... ur algo is illegible.
On Wed, Jul
39 matches
Mail list logo
