as a hint, convert the BST to a sorted array and take two pointers one
pointing to the first number and the other pointing to the last. Then, move
pointers appropriately to find the two numbers summing up to k.
complexity: O(n)
2010/8/5 Seçkin Can Şahin
> what about the case:
> array : 1 3 10 1
what about the case:
array : 1 3 10 100 and k = 101. Your code doesn't find it I suppose.
On Thu, Aug 5, 2010 at 11:15 PM, Avik Mitra wrote:
>
> Inorder traversal of the BST will give elements in sorted way. Let us
> assume that the sorted elements are in an array A of length N.
> set i=1;
> whi
On 8/6/10, Avik Mitra wrote:
>
>
> Do you mean to convert a BST to a HEAP?
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email
Inorder traversal of the BST will give elements in sorted way. Let us
assume that the sorted elements are in an array A of length N.
set i=1;
while i k, then output: "No such node"
else if(a[i]==k)
{
if (a[i+1] ==0)
output: "Two nodes found" BREAK;
else
output: "No suc
Do you mean to convert a BST to a HEAP?
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
F
Merge two arrays using merging technique. Now use the following:
1. If the number elements is odd then median is (n+1)/2 th element.
2. If the number of elements is even then median is (n/2 th element +
(n/2 +1)-th element )/2.
--
You received this message because you are subscribed to the Goog
N = (3*4096+15*256+3*16+3)
= 3* (2^10) + 15*( 2^8) + 3*(2^4) + 3* (2^0)
= (1+2)*(2^10) + (1+2+2^2+ 2^3)*(2^8) + (1+2)*(2^4) + (1+2)
= (2^10 + 2^11) + (2^8+2^9+2^10+2^11) + (2^4 + 2^6)+ (1+2)
= 2^11+2^12+2^8+2^9+2^4+2^6+2+1
= 1 + 2 + 2^4 + 2^6 + 2^8 + 2^9 + 2^11 + 2^12
So there ar
Can some one explain me the significance of Load Factor in Hashing ?
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+un
There are well-developed algorithms for file diff. When comparing two
text files, you can identify the added/deleted/modified lines.
Now I am looking for an algorithm for comparing two tables. Say, I
have a table with m x n cells. Through a series of modifications --
adding/removing rows, adding/r
Use a two-step process. First, check for a repeated number in the
first 4 elements. If none is found, then there are at least n/2-1
occurrences of the repeated elements in the last n-3 elements, meaning
that there must be at least two repeated elements in adjacent
positions. So second, check for eq
http://codepad.org/8eDVyeBT
Using XOR logic we can find Duplicates in O(n)
On Thu, Aug 5, 2010 at 11:25 AM, ravindra patel wrote:
> Your test case is wrong. With this pattern you can have at max n/3
> occurrences of 1. The questions says that repeated element has n/2
> occurrences
>
>
> On Thu,
Nice solution. Reduces number of comparisons to half of Ashish's algo. The
complexity remains O[n] though. Can it be made more efficient, like O[log n]
On Thu, Aug 5, 2010 at 10:59 PM, Pramod Negi wrote:
> compare pair wise i.e a[0] and a[1]a[2] and a[3]..
>
> leave out last 4 elements...
>
Your test case is wrong. With this pattern you can have at max n/3
occurrences of 1. The questions says that repeated element has n/2
occurrences
On Thu, Aug 5, 2010 at 8:37 PM, Manjunath Manohar
wrote:
> consider the test case of...
>
> 1 2 3 1...
>
> 1 repeated n/2 times and 2,3 are distinct n/
compare pair wise i.e a[0] and a[1]a[2] and a[3]..
leave out last 4 elements...
repeated element can be found in 3 comparison for these 3 elements...
total no of comparison in worst case
(n/2+1)
Negi
On Thu, Aug 5, 2010 at 10:55 PM, Shiv ... wrote:
> In constant space??? How? will you p
In constant space??? How? will you please elaborate?
On Thu, Aug 5, 2010 at 9:29 PM, dinesh bansal wrote:
> If I understand the question correctly... there is an array of size n which
> has n/2 distinct elements and one element is repeated n/2 times.
>
> For e.g.:
>n = 4: 1 2 3 3
>n =
Order of Initialization will be from right to left.
Meaning if we have a derived class which got derived from two base class A
and B
Class D : class A , Class B.
Then members of class B are initialized first and then members of A are
initialized.
Thanks,
Anand
On Wed, Aug 4, 2010 at 11:08 AM,
can u explain how is this number reached at?
(2n)!/((n+1)!(n!))
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
On Thu, Aug 5, 2010 at 12:53 PM, umesh kewat wrote:
> Calculate the number of string can be formed by this formula in one
> statement..
If I understand the question correctly... there is an array of size n which
has n/2 distinct elements and one element is repeated n/2 times.
For e.g.:
n = 4: 1 2 3 3
n = 61 2 3 4 4 4
n = 81 2 3 4 5 5 5 5
So now this problem can be reduced to finding the first duplicate element
consider the test case of...
1 2 3 1...
1 repeated n/2 times and 2,3 are distinct n/2 elements
for this the algo will not work
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
travse array and check that if(a[i]==a[i+1]||a[i]==a[i+2]);
if more then n/2 no are there then that condition will satisfy ...adjust
with boundary condition
On Thu, Aug 5, 2010 at 6:36 AM, AlgoBoy wrote:
> an array in which n/2 elements are unique...and the remaning n/2 have
> the same elements
a[1n] b[1...m]
find median of two array say n1 and m1..if n1>m1 then median of both array
can't be in in region a[n1..n] and b[1...m1]so now search space is
reduced ..and we continue like this untill we find median.
On Thu, Aug 5, 2010 at 6:37 AM, AlgoBoy wrote:
> find the median of two
sort a BST represented like an array...(similar to representation of
HEAP)
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogee
in a BST..given k..find two nodes ...whose values sum to k..
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...
find the median of two sorted arrays..which have unequal lengths...
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsu
an array in which n/2 elements are unique...and the remaning n/2 have
the same elements but reapeated n/2 times. can anyone suggest a linear
solution with constant space/...
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this grou
I seem to have certain difficulties in understanding the prefix
function for the KMP algorithm...Can anyone pls help...
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubs
Hi,
Interviewer want to test the knowledge of design pattern of the
candidate . we can use any DS to store Employee info like
ArrayList ,Tree(Level by Level Trave.. is good option),or hash . This
problem is related to Composite and Iterator pattern.
Thanks
Yash
On Aug 5, 10:09 am, Chonku wrote:
We can store the employees as a list. Since each employee is managed by 1
boss, we can store the pointer to boss in the child.
To calculate getCostToCompany(char* bossName), we can scan the list and look
for those records where bossName matches those employees who have boss with
. This would bw O(n
Calculate the number of string can be formed by this formula in one
statement..
for cross check the result is
2N!/((N+1)! * N!) where is number of A or B in string
On Thu, Aug 5, 2010 at 8:54 AM, Ashish Goel wrote:
>
>>
>> void dyckWords(int index, int open, int close)
>> {
>> static i
Can some one suggest the approach for such problems?
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googl
30 matches
Mail list logo
