@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 wrote:
> +1
> *
> Sanjay Kumar
>
+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 wrote:
> replace all 0s by -1
> keep additional array to get the sumHer
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
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
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, vi
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 subscri
IT will grt help for me... if u all tell me..
map 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, 2011 at 9:00
@shashank and @samm: Is the deletion and searching is o(1). I doubt
On Sat, Oct 1, 2011 at 6:30 PM, SAMM 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 hand..
>
> On 10/1/11,
nice idea..
On Oct 20, 11:04 am, SUMANTH M 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,2,-4,-3, 6 ,-3};
>
+1 for Sumanth's solution.
On Oct 20, 12:03 pm, anshu mishra 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 sum will be zero and
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 wrote:
> @All Why don't try with combination of* hash-table & Array* , It Will Work ,
> try it out :P
>
>
> Tha
@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
https://groups.google.
Dont know how to delete (how adress will be known of the node?
On Sat, Oct 1, 2011 at 12:27 PM, SAMMM 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 of open addresssing th
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 si
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 a
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 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 intervals."
> As
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,
This solution is not in O(n) time :(
Unfortunately interviewer wants O(n) .
On Sun, Sep 11, 2011 at 4:01 PM, Kunal Patil wrote:
> @Brijesh: +1
>
>
> On Sun, Sep 11, 2011 at 2:14 PM, Brijesh wrote:
>
>> This is the fastest way I can think of to do this, and it is linear to
>> the number of inter
@Brijesh: +1
On Sun, Sep 11, 2011 at 2:14 PM, Brijesh wrote:
> 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
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:
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 wrote:
> satisfy the point on lines, for point(x,y) to lie in between the two, the
> f(x,y) value w
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){
if(i
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 wrote:
> If I correctly understood the question, It says:
> 1. 0<= x[i] <=1 for all i and for all x of line i.
>
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] wrote:
> You are given n no. of lines in form of Ax + By = C, basically you are given
> A[i], b[i] and C[i] for line "i".
> Lines are given in a way such that 0 <= x[i] <= 1 and y[i] < y[i+1]
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 P
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
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 wrote:
> count is required since its not implemented as LL
>
>
> On Mon, Aug 22, 2011 at 7:47 PM, shady wrote:
>
>> i wish u had read the question... it is
count is required since its not implemented as LL
On Mon, Aug 22, 2011 at 7:47 PM, shady 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 wrote:
>
>> No n
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;
q
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 wrote:
> No need to count the number of nodes. Since its implemented as a linked
> list traverse the list with two two poin
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
@saurabh ...very nice solution negating the index :)
On Jul 20, 9:59 pm, siva viknesh wrote:
> @shubamhi i ve asked u to find 2 missing no.s
>
> eg : a[5] = {1,2, , , 5}
>
> 3 nd 4 r missing
>
> as per ur method:
>
> A - 15-8=7
> B - 55-30=25
>
> missing number = ((B/A) + A)/2; = ((2
@shubamhi i ve asked u to find 2 missing no.s
eg : a[5] = {1,2, , , 5}
3 nd 4 r missing
as per ur method:
A - 15-8=7
B - 55-30=25
missing number = ((B/A) + A)/2; = ((25/7)+7)/2= 5 !!!
.can u give a correct algo or correct me if i m wrong :)
On Jul 20, 1:26 pm, Shubham M
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
wrote:
> @saurabh.
> kindly use a lil bit of indentation ... ur algo is illegible.
>
>
>
>
>
>
>
>
>
> On Wed, Jul 20, 2011 at 1:
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
wrote:
> 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)
For quest 1 given as "Each number is present at least once except for 2
numbers." We can't apply the math formula unless its given as exactly once ?
On Wed, Jul 20, 2011 at 4:28 PM, saurabh singh wrote:
> space o(n) toomine takes o(1) space
>
>
> On Wed, Jul 20, 2011 at 3:50 PM, JIƬΣN BAJIYA
space o(n) toomine takes o(1) space
On Wed, Jul 20, 2011 at 3:50 PM, JIƬΣN BAJIYA wrote:
> simple one!! . all the missing nos which r not present b/w 1 to n will
> be printed!! TC O(n)
>
> #include
>
> #define size 1
>
> int main()
> {
> int i, j, n;
>
> scanf("%d",
simple one!! . all the missing nos which r not present b/w 1 to n will
be printed!! TC O(n)
#include
#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 <= n ;
dats much beter now ...
:D
On Wed, Jul 20, 2011 at 1:53 PM, saurabh singh wrote:
> Let my code speak for me..:)
> http://www.ideone.com/E2LhU
>
> Try to get what I am doing from the code.Its not hard and believe me it
> will be fun.:)
>
> --
> You received this message because you are subscr
Let my code speak for me..:)
http://www.ideone.com/E2LhU
Try to get what I am doing from the code.Its not hard and believe me it will
be fun.:)
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeek
@saurabh.
kindly use a lil bit of indentation ... ur algo is illegible.
On Wed, Jul 20, 2011 at 1:28 PM, saurabh singh wrote:
> 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 va
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::
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 wrote:
> Q1 can be solved using some simple maths:)
> Hint:What is the sum of fi
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 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 for 2 numbers. Find
Q1 can be solved using some simple maths:)
Hint:What is the sum of first n natural numbers?"And what is the sum of
squares of first n natural numbers?
On Wed, Jul 20, 2011 at 12:44 PM, siva viknesh wrote:
> gn array - say a
>
> hav extra array - say b - initialise all values to zero
>
> ques
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]]++;
}
then traverse b array and print i, for which b[i] = 2
o(n) time & space
same idea for ques 2
better approaches please
On Jul 20, 12:11 pm, siva viknesh wrote:
> gn arr
47 matches
Mail list logo
