Find out the smallest segment in a document containing all the given
words.
Desired Complexity is O nlogK ..n is the total no of words in the
document and k is the number of input words
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post
We can do it by hashing. hash the 2-d array and then search for 1 d array
in the hash table.
--
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.com/d/msg/algogeeks/-/7PE1mqG4RRgJ.
Hint : try with prestoring the preorder traversal element position in
inorder traversal before constructing the tree
--
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 unsubscri
Given an unsorted array arr[0..n-1] of size n, find the minimum length
subarray arr[s..e] such that sorting this subarray makes the whole
array sorted.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algog
There is a binary tree (Not a BST) in which you are given three nodes
X,Y, and Z .Write a function which finds whether y lies in the path b/
w x and z.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algog
> = an + 2b + 2
>
> Now subtracting an+b from both sides we have b = -2.
>
> To find a, we need the base case. With T(2) = 1, we have
> T(2) = an + b = a(2) - 2 = 1
>
> This produces a = 3/2, so T(n) = 3/2 n - 2 as stated.
>
> On Nov 23, 3:59 am, Ankuj Gupta
When i try to solve this
T(n) = 2T(n/2) + 2
recurrence relation i get order N. But
http://www.geeksforgeeks.org/archives/4583
claims that it is 3/2n-2. The order is still N only but how do we get
the constants ?
--
You received this message because you are subscribed to the Google Groups
"A
; > remaining at the end will have the value 0.
>
> > I am not sure about the complexity of this algorithm...
>
> >> On Wed, Nov 23, 2011 at 12:02 AM, Anup Ghatage wrote:
>
> >>> I can't think of a better than O(n^2) solution for this..
> >>>
Input: A unsorted array of size n.
Output: An array of size n.
Relationship:
> elements of input array and output array have 1:1 correspondence.
> output[i] is equal to the input[j] (j>i) which is smaller than input[i] and
> jth is nearest to ith ( i.e. first element which is smaller).
> If no s
I guess its NlogN for balanced tree as it is traversing N nodes for H
times ie the height of tree which is logN for balanced and N for
skewed tree. So it should be Nlogn and N^2
On Nov 20, 9:27 am, tech coder wrote:
> @ sravanreddy001
> complexity is O(N^2) whether tree is balanced or not doesn't
O(N) method is trivial. Can we do better than this ? Using matrix f=
{ {1,1},{1,0}}.
--
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 t
Try it once. It is for level order only in dfs way
On Nov 19, 2:58 pm, shady wrote:
> this doesn't seem like level order printing, because you are simply
> printing the tree starting with the children as the root node.
>
>
>
>
>
>
>
> On Sat, Nov 19, 2
What is the time complexity of this code for Level Order Traversal.
void printLevel(BinaryTree *p, int level) {
if (!p) return;
if (level == 1) {
cout << p->data << " ";
} else {
printLevel(p->left, level-1);
printLevel(p->right, level-1);
}
}
void printLevelOrder(BinaryTree *
I tried to understand the logic of it but could not :(
On Nov 11, 11:17 am, shady wrote:
> no, for eg.
>
> array1 = { 1, 2, 5, 6, 7, 7, 7, 23};
> array2 = { 1, 2, 2, 4, 8, 9, 12 };
>
> then for
> k = 2, answer = 1
>
> k = 3, answer = 2
>
> k = 4, answer = 2,
>
> k = 6, answer = 4.
>
> anyway to d
I have a doubt in calculating LCA. While calculating LCA of two
nodes, should those two nodes can also be ancestor. As wikipedia
states that
"The lowest common ancestor is defined between two nodes v and w as
the lowest node in T that has both v and w as descendants (where we
allow a node to be a
I was thinking on the lines of heap
On Nov 2, 8:33 pm, Anup Ghatage wrote:
> Median of Medians?
>
> On Tue, Nov 1, 2011 at 10:44 PM, Ankuj Gupta wrote:
> > We have a N X N matrix whose rows and columns are in sorted order. How
> > efficiently can we find
> > t
We have a N X N matrix whose rows and columns are in sorted order. How
efficiently can we find
the median of those N^2 keys ?
--
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
No constraint on path. Though it is not necessary that it starts from
root only
On Oct 31, 10:02 pm, Prakash D wrote:
> any constraints for path?
>
>
>
>
>
>
>
> On Mon, Oct 31, 2011 at 11:19 AM, Ankuj Gupta wrote:
> > Print all path of the tree that sums up to
I had a doubt , if we simply go on constructing the tree from preorder
traversal one gets the same tree back am I missing something here
On Oct 19, 7:49 am, sravanreddy001 wrote:
> @Sunny, Rahul:
> Thanks a lot.. :)
>
> @Anshu: the code is perfect, This would be h = n* (height of BST) --> O
How to convert a Binary tree to BST ? Naive way is to create each node
of Binary tree one by one and keep on creating the BST.
--
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.
T
Given a node of a BST, modify it in such a way that the given node
becomes the root. The tree should still be BST. One way I could get is
store the Inoder traversal of the tree. Find that node in the
traversal and recursively make the BST.
--
You received this message because you are subscribed t
I am not getting what you said. For given tree
a(2)b(7)c(5)d(2)e(6)f(9)g(5)h(11)i(4) if i say given node is 6 and
distance is 1 then the output should be 7,5,11.
The nodes below the given nodes can be easily printed. I am not
getting the way to print nodes above the given node
On Oct 31, 1:30
Print all path of the tree that sums up to the given value. The path
may start from any node.
--
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, sen
You are given a function printK Distance Nodes which takes in a root
node of a binary tree, a start node and an integer K. Complete the
function to print the value of all the nodes (one-per-line) which are
a K distance from the given start node in sorted order. Distance can
be upwards or downwards.
t 1: try to find 2 indexes i, j such that a[i] <= K <= a[j]
>
> > On Sun, Oct 23, 2011 at 11:23 PM, Ankuj Gupta wrote:
>
> >> Given a sorted array of Infinite size, find an element ‘K’ in the
> >> array without using extra memory in O (lgn) time
>
&g
Given a sorted array of Infinite size, find an element ‘K’ in the
array without using extra memory in O (lgn) time
--
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
@rahul can you order your trees properly :(
For BST only preorder traversal is sufficient to reconstruct it back
On Oct 18, 5:58 pm, rahul patil wrote:
> @Anshu: for a tree
> 15
> 15
> 7 18 and
> 7 17
>
> 17
How to reconstruct a BST from just the prorder traversal of that tree ?
--
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+
Is the indexing correct ? For eg a1,a2,a3,b1,b2,b3,c1,c2,c3
for a2 the correct position is 3 but acc to the given formula it is 2.
On Oct 17, 9:35 pm, Navneet wrote:
> Great explanation Sunny. But with this approach, won't a single pass
> suffice?
>
> Select a card , find it's new position, inse
What is the time complexity of morris traversal ?
--
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...@googlegrou
How do you deduce number of multiplication that when we perform a^b
function using dividing the exponent by 2 at each stage to be log b?
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegro
There are two linked list of length m and n. There is some common data
at the end of both. Find the starting position in both the linked
list. I could suggest two methods
1) Reverse the list and check .
2) Use recursion to go to the last element and move back from there.
Is there any other way ?
Find lowest common ancestor of Binary Tree
--
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.
not scan next input until all
> numbers are over.
>
>
>
>
>
>
>
> On Tue, Sep 27, 2011 at 10:22 PM, Ankuj Gupta wrote:
> > Infinite numbers are coming in a stream . how will you find the
> > frequency of a given number ?
>
> > --
&g
We are given a tree so one should go for reconstruction of tree using
rotations ?
On Sep 27, 10:19 pm, Ankur Garg wrote:
> L , R ,LR , RL rotations
>
> On Tue, Sep 27, 2011 at 10:35 PM, sukran dhawan wrote:
>
>
>
>
>
>
>
> > avl tree
>
> > On Tue,
Infinite numbers are coming in a stream . how will you find the
frequency of a given number ?
--
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, se
Given a bst how to height balance it ?
--
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
Hi
I have written a simple template class.
#include
using namespace std;
template
class vector
{
T *arr;
int size;
public:
vector(int len)
{
arr = new T[size=len];
for(int i=0;iarr[i]*obj.arr[i];
return sum;
Hi
I have a doubt in functioning of realloc. Can we use realloc to shrink
the memory already allocated ? If yes, will it also free the left over
memory or programmer has to do it ? Also, while reallocating if it has
to move to some other location does the earlier location gets freed or
is it imple
yes it is n^5
On Sep 22, 8:53 am, siva viknesh wrote:
> @Dave ... thanks dude.So it should be O(n^5) .. am i right ??
>
> On Sep 22, 8:19 am, Dave wrote:
>
>
>
>
>
>
>
> > @Siva: Work from the inside out, using the identities
>
> > sum from i = 1 to n (i) = n*(n+1)/2
>
> > sum from i = 1 to
If it is the first largest ?
On Sep 21, 8:02 pm, Dave wrote:
> @Prasanth: Since there is no requirement to find the next larger
> number, you can go for the largest. Extract the digits into an array
> using modulus and division by 10. Then sort the digits into descending
> order. Finally, constru
Consider a class
class string
{
char *p;
int len;
public:
string(char *a);
};
string::string(char *a)
{
length = strlen(a);
p= new char[length +1];
strcpy(p,a);
}
string s1,s2;
char *name ="test";
s2=name; // statement
Why does constructor gets called in state
is talks of more tighter bound of O(nlogn)
On Sep 15, 11:24 pm, sunny agrawal wrote:
> Read CLRS
>
> On Thu, Sep 15, 2011 at 11:51 PM, saurabh agrawal wrote:
>
> > Building a max heap takes O(n) time irrespective of the array being sorted
> > / unsorted.
> > Can someone prove that. I already
It is still giving run time error
On Sep 16, 4:40 am, Deoki Nandan wrote:
> error due statement int*y; because it tries to allocate another pointer
> being uninitialized .It may happen that garbage address which was given to x
> is also try to give to y . This makes program crash ...
> You can ch
I guess the functionality of priority should be maintained
On Sep 13, 11:59 pm, Ankur Garg wrote:
> But dude are u saying stack will be implemented as a map with
>
>
> and then choose element based on priority ?
>
> regards
> Ankur
>
>
>
>
>
>
>
>
@Tanmay: fflush do work. Atleast it does not become a infinite loop.
But still the output is some garbage value in case of character input
On Sep 14, 1:04 am, Raghu Sarangapani
wrote:
> I modified your program as below.
> Every time, value of ret = 0.
> scanf is repeatedly failing cos there is so
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 wrote:
> How
What I am guessing is that the stdin used by scanf is not getting
flushed after entering a char as a result of which it is running into
infinite loop. If you use fflush(stdin) just after scanf it will not
be infinite loop. But I am not able to get the reason for it.
On Sep 13, 3:23 pm, Avinash Dha
Is there any restriction on the input like they are in given range ?
On Sep 11, 11:10 pm, Neha Singh wrote:
> You are given an array that contains integers. The integers content is such
> that every integer occurs 3 times in that array leaving one integer that
> appears only once.
> Fastest way t
Hi
Which is a good book for C++ ( Robert Lafore or Bjarne Stroustrup or
Herbert Schildt) ?
Ankuj
--
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
what is C and M
On Sep 10, 7:40 pm, Ishan Aggarwal
wrote:
> 1.)
>
> there is a pyramid with 1 cup at level , 2 at level 2 , 3 at level 3 and so
> on..
> It looks something like this
> 1
> 2 3
> 4 5 6
> every cup has capacity C. you pour L liters of water from top . when cup 1
> gets filled , it o
http://groups.google.com/group/algogeeks/browse_frm/thread/274f63b24388599d/da635c4f409d5e1b?lnk=gst&q=print%28max%28x%2B%2B%2Cy%29%2Cx%2Cy%29%3B+#da635c4f409d5e1b
On Sep 8, 2:04 am, htross wrote:
> can u please explain this code or give the link to the thread u
> mentioned before???
>
> On Sep 7
Data Structures and Algorithm Analysis by Mark Allen Weiss
On Sep 6, 3:39 pm, siddharam suresh wrote:
> @neha: there is site calledhttp://library.nu
> register there, u'll get majority of the books.
> Thank you,
> Sid.
>
> On Tue, Sep 6, 2011 at 3:54 PM, Prashant Kulkarni
>
>
>
>
>
>
> > wrote:
I guess we cant modify the original string. For yahoo should it be
yahoohay ? Please clarify
On Sep 6, 12:56 am, Pratz mary wrote:
> int main()
> {
>
> char *s="nitan";
> int n,i,j,c=0;
> char *d;
> n=strlen(s)/2;
> //printf("%d",n);
> for(i=1;i<=n;i++)
> {
>
> if(
@mohit: that will modify the original array
On Sep 4, 6:40 pm, sarath prasath wrote:
> here is my approach
> where i left the non repeating characters as it is and done some good code..
> char * runlengthencode(char* str,int size)
> {
> int i,j,flag=0;
> for(i=0,j=1;str[i]&&str[j]&&j
If someone has Algorithms for Interviews please share with me. I tried
the link which was earlier posted on the group but it says it is
locked.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@goo
p is a pointer to an array of 4 integers. So when you do (int(*)
[col])malloc(row*sizeof(*p)) total of 48 bytes is allocated as
sizeof(*p) is 12 bytes.
On Sep 3, 4:14 pm, rohit wrote:
> how many bytes are allocated by following code?
>
> #include
> #define col 4
> #define row 3
>
> int main()
> {
p 3, 2011 at 8:02 PM, siddharam suresh
> wrote:
>
>
>
>
>
>
>
> > sol already posted please search old thread
> > Thank you,
> > Sid.
>
> > On Sat, Sep 3, 2011 at 8:01 PM, Ankuj Gupta wrote:
>
> >> If we take our input to be characte
because your are trying to edit an unmodifiable object which C-
compiler will not allow
On Sep 3, 6:18 pm, priya ramesh
wrote:
> ok but y does the compiler say lvalue required if you perform a++??
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" gr
If we take our input to be characters a-z ans A-Z then we require
fixed space which can be treated as O(1).
On Sep 3, 7:10 pm, teja bala wrote:
> this 'll work if u i/p the string in dis manner
> aaabbcc(consecutive same)
> a3b2c2
>
> #include
> #include
> main()
> {
> int x=1,i=0;
> char a[100];
I could not get it. What does first train mean here?
On Sep 1, 1:08 am, Don wrote:
> Assuming that the man arrives at a random time during the 24-hour day,
> there are 228 minutes in the day when the next train will be the
> harbour line (2 minutes of every 10 for 19 hours). For the other 1212
>
Bitonic sort
On Aug 31, 11:26 am, bharatkumar bagana
wrote:
> while increasing ... we have to use insertion sort which is in place algo ..
> while decreasing... any way that is sorted one .. so no need to maintain ...
> But it takes O(n^2) time ..
>
> On Wed, Aug 31, 2011 at 1:58 AM, Navneet Gupt
If both number are negative shouldn't be b < min_int - a
On Aug 28, 11:49 pm, "Avinash LetsUncomplicate.." wrote:
> @Saurabh being ready to run your code for unsatisfactory input doesn't
> seem more logical than trying to find out if you can do something
> about it. i would have loved a kind repl
U can use binary search method
On Aug 30, 1:56 pm, Rajeev Kumar wrote:
> use Babylonian method(Efficient) algrithm..
> Refer
> :http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylo...
>
> public *void* getSquareRoot(double s) {
> double Xn = 2.0;
> double lastXn
how can be there 20 greens ?
On Aug 24, 12:12 am, DK wrote:
> The standard library is neither multithread safe nor multiprocess safe.
> If you want the correct answer, use shared memory and maintain a shared
> counter. Alternatively, as a quick hack, insert a fflush(stdout) after the
> printf sta
But the o/p at
http://ideone.com/zKZuS
seems to be different than what one is getting from parent child tree
On Aug 8, 10:41 am, Kamakshii Aggarwal wrote:
> what will be the o/p of the following program:
>
> main()
> {
> int ret;
> ret=fork();
> ret=fork();
> ret=fork();
> ret=fork();
>
> if(!r
I am getting 6 calls to red and 8 calls to green when i built parent
child tree but when i ran this code
http://ideone.com/UBaBB
I got 10 calls to red and 10 calls to green.
Can some explain this ?
On Aug 22, 9:31 pm, ghsjgl k wrote:
> i saw this question in one of DREAM companies
>
> i dont kn
We can modify it by keeping track of minimum element as well and find
diff of that with all elements(say max_diff) and at each iteration we
can find the minimum of max_diff and min_diff
On Aug 17, 9:34 am, Ankuj Gupta wrote:
> I assumed that we can find min diff when we subtract elements
I assumed that we can find min diff when we subtract elements of array
from the max element
On Aug 16, 11:18 pm, Anurag Narain wrote:
> @ankuj:
>
> i think the solution is not correct..
>
> could u please explain ur algo for
>
> 5,13,7,0,10,20,1,15,4,18
>
> acc to ur algo answer is 2 but it shoul
we take the difference with the maximum element found so far. So we
need to keep track of 2 things:
1) Minimum difference found so far (min_diff).
2) Maximum number visited so far (max_element).
min_diff=abs(a[0]-a[1]);
max_elem=a[0]
for(i=1;imax_elem)
max_elem=a[i];
Ankuj
On Aug 16, 7:26 pm
A good link
http://www.cse.yorku.ca/~oz/hash.html
On Aug 14, 11:50 pm, rohit wrote:
> Well I came across a great hashing algorithm, known as djb2 hash for hashing
> strings..would like to share it:
>
> int get_hash(char *s)
> {
> int hash = 0;
> while(c = *s++)
> {
> hash = ((hash << 5) + hash)
We can use min heap.
1) Build a Min Heap MH of the first m elements (arr[0] to arr[m-1]) of
the given array. O(m)
2) For each element, after the mth element (arr[m] to arr[n-1]),
compare it with root of MH.
a) If the element is greater than the root then make it root and call
heapify for MH
b) Else
C++ will not allow void pointer to increment. But in C we can perform
it where void will be treated as char*
http://stackoverflow.com/questions/3523145/pointer-arithmetic-for-void-pointer-in-c
On Aug 9, 6:39 pm, UMarius wrote:
> ++ on a void* will increase the address by 1 byte. ++ on a type* wi
How is the time O(n^2).It is O(nlgn)
On Aug 9, 7:53 pm, ankit sambyal wrote:
> 1. Square each element of the array and then sort it---O(nlogn)
> 2. for(i=0;i<(size-3);i++)
> {
> j=i+1; k=size-1;
> while(j {
> if(a[[i] + a[j] == a[k])
> printf("\n%d %d %
My bad but it can be made recursive :)
On Aug 9, 8:17 pm, Dave wrote:
> @Ankuj: Yeah, but he asked for it to be recursive. Yours is iterative.
>
> Dave
>
> On Aug 9, 9:56 am, Ankuj Gupta wrote:
>
>
>
>
>
>
>
> > we can do it in logn by using binary
we can do it in logn by using binary search approach found
n is the number whose square root has to be
if(n==1)
return 1;
if(n==0)
return 0;
int low=0,high=n/2,mid,temp;
while(1)
{
mid = (low+high)/2;
Has the results come ?
On Jul 26, 12:32 pm, "$hr! k@nth" wrote:
> Nybody got shortlisted in MS written test which happened on 23rd july???
>
> On Sun, Jul 24, 2011 at 7:32 PM, Bhanu Pratap Singh wrote:
>
>
>
>
>
>
>
>
>
> > We can also use, c++ map... for implementing this!
> > --
> > *with regar
77 matches
Mail list logo