maintaining cumulative sums of left side of array from index i in in hash,
and maintaining variable for right cumulative sums at each j ( j=i+1 till
n-1) and check at each value on hash
will solve in O(n^2), let me know if im wrong..
surender
On Wed, Jan 11, 2012 at 9:12 PM, sravanreddy001
@gene
in that case ur erase() should even consider diagonal elements as well,
else there would be 2 islands in example
surender
On Wed, Jan 11, 2012 at 7:19 AM, Gene gene.ress...@gmail.com wrote:
Guys,
You are making this way too hard. It's really a graph problem. The
nodes are the 1's and
using extra space of O(n) we can do it in O(n^2)
take an array for storing cumulative sums from index i till 0,
then from i+1 till n-1 find summing each array value find whether it exists
in array.
if its so display indexes
eg
Array: 2,2,13,4,7,3,8,12,9,1,5
i = 3 ^
temp array: 4,
Nice Soln Lucifer,
i had problem of tracking kth value when coming across two siblings, each
sibling has many childs
so i think a bottom up approach would be better for finding number of
elements(say* y*) x
finally at root we have y,
if y=k then kth element is x
else kth elemnt is x
Surender
On
MinHeap with frequency of data is constructed, then sorting it.
But don't see with same frequency it maintains the order of the first
appeared element
Regards
Surender
On Sat, Dec 24, 2011 at 10:57 PM, Ankur Garg ankurga...@gmail.com wrote:
how can one do frequency sort .
Suppose we have an
Hi
how about finding this for an integer array and finding i and j such that
Min(j-i)
surender
On Fri, Dec 2, 2011 at 3:09 AM, sravanreddy001 sravanreddy...@gmail.comwrote:
An idea is to start with a heap of size k.
Its tricky how to keep track of the start and end indices of the smallest
All distinct combinations will result in string size of 2 + rest repeated
characters
eg
abcabcabc -aabbcc-abc-aa or bb or cc
surender
On Sat, Nov 12, 2011 at 4:24 PM, Snoopy Me thesnoop...@gmail.com wrote:
Given a string consisting of a,b and c's, we can perform the
following
operation:
@myself
if number of distinct characters are equal then its final string size is 2.
else there are more repeated characters other than distinct characters then
its 1
correct me !!!
surender
On Sat, Nov 12, 2011 at 4:46 PM, surender sanke surend...@gmail.com wrote:
All distinct combinations
@nitin
yes i meant the same, if each different character have equal number of
frequency like abcabcabc a's -3, b's - 3 c's- 3
then resultant string size is 2 else 1
surender
On Sun, Nov 13, 2011 at 12:21 AM, Ankur Garg ankurga...@gmail.com wrote:
@Srinivas
Wat if the string is abc
then it
this finds first and last index in pair structure in logn
void repindxs(int array[],int start, int end, int k, pairint, int *p, int
n/*last index*/)
{
if(startend) return ;
int m = (start+end)/2;
if( array[m] == k (m-10?-1:array[m-1] k) )
p-first = m;
else if(array[m] k || (array[m]==k
unlink each node in original tree in postorder, and insert these nodes in
new bst tree
surender
On Tue, Nov 8, 2011 at 4:48 AM, vikas vikas.rastogi2...@gmail.com wrote:
@ Above
no need to have another array or nything
binTreeToBST(node *root)
{
if(!root )return;
node *newRoot;
iterate it twice the length
max_sub_array()
{
int a[] = {200 -10 -10 -10 -10 -10 100} ;
int len = sizeof(a) / sizeof(a[0]);
int max_sum =0;
int max_till_now =0;
for(int i=0; ilen*2; i++)
{
if(max_till_now + a[i%len] 0)
max_till_now =0;
else
max_till_now += a[i%len];
if(max_sum
i think the solution requires to end at a leaf node with given sum 'k'.
if we gather the path from root till its leaf,
once we reach leaf we have root to leaf values in our path array
now create another array of same SIZE having sub_array_sum starting from
root.
we check the last value of
@vikas
ur algo will search for 1st element of 1d in whole 2d array,
on worst case u'll search it in n^2, then search for all 1d elements
in 2d in O(n)
so whole complexity goes to O(n^2 +n)
it can be reduced if we use hashing of 1d array, and count_found
and while searching for 1st element of 1d
@asit dhal,
in order of any BST is increasing order.
so required is only either preorder/postorder
surender
On Tue, Sep 27, 2011 at 12:42 AM, Gene gene.ress...@gmail.com wrote:
Here is a little program to show how it works. It's a nice little
problem. There is also a coding with recursion.
print all numbers in a given range *without* using any loop statements, jump
statements and recursion
surender
--
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
based on minmax in minimum number of comparisons..
struct pa
{
int max;
int secmax;
};
struct pa getmm(int arr[], int low, int high)
{
struct pa mm = {-1,-1}, mml, mmr; int mid;
/* If there is only on element */
if(low == high)
{
mm.max = arr[low];
mm.secmax = arr[low];
return
t = j-i+1; // total number bits (t) between i and j , i=2,j=6
t = 2^t-1; // value would be 2^5-1 .. 0001
t = ~t ;// ...1110
t = ti | 2^i-1 // 1000 0011
N = N t; // resets all bits between i and j to 0 in N
N = N | Mi; sets bits in N with bits in M
surender
take another matrix of same size, calculate sum at each element
if a[][] is the matrix,SM[][] stores sum till that point
SM[0,i] = a[0][i]
SM[i,0] = a[i][0]
SM[i][j] = SM[i][j-1]+SM[i-1][j]-SM[i-1][j-1]+a[i][j]; i,j=1 to n-1
track max value as u does this.
surender
On Sat, Sep 17, 2011 at 6:58
@ankur,
does this actually connects from start station to end station??
i think ur solution creates path which could be discontinuous,
but we want end to end connected path
surender
On Sat, Sep 17, 2011 at 5:39 AM, Ankur Garg ankurga...@gmail.com wrote:
Some typos in my solution :(
Use a Max
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
),linked_list);
Any better approach?
On Fri, Sep 9, 2011 at 11:09 AM, surender sanke surend...@gmail.comwrote:
maintain a hash of freq,linked_list
linked_list consists of values of that frequency.
values with same frequency comes under same list
if pop of a particular value is done, then frequency
explanation would be appreciated
surender
On Thu, Sep 8, 2011 at 12:12 AM, Piyush Grover piyush4u.iit...@gmail.comwrote:
4) a and b
On Thu, Sep 8, 2011 at 12:08 AM, Piyush Grover
piyush4u.iit...@gmail.comwrote:
1.)a
2.)b
3.)b
4)b
On Wed, Sep 7, 2011 at 11:08 PM, Mani Bharathi
maintain a hash of freq,linked_list
linked_list consists of values of that frequency.
values with same frequency comes under same list
if pop of a particular value is done, then frequency is changed of that
number, a new record would be created if required.
maintain two values tracking max and
@sukran, string shouldn't be replaced, only addition of characters allowed
On Tue, Sep 6, 2011 at 1:48 PM, sukran dhawan sukrandha...@gmail.comwrote:
my soln works without increasing the string length
just start with first and last character copy last character with first
increment i and
{ 1,1,2,2,2,2,3,3,3,4,4,5,5}, here 3 is missing its pair, does this also
comes under this problem?
surender
On Thu, Aug 25, 2011 at 8:12 AM, Dave dave_and_da...@juno.com wrote:
@Shailesh: Sir, your response is unresponsive, because the original
poster specifically asked for a solution that
concatenate both and find all permutations of that string
surender
On Thu, Aug 11, 2011 at 5:34 PM, Gayathri Anandan
gayathriananda...@gmail.com wrote:
Given two strings say AB and CD you should print all the possible
combinations. Use any language.
output: ABCD, ABDC, ACDB, ADBD, ADBC,
@dave, ur converting array values into baseN and doing radix?
then every time there will be N*N = 100(baseN).
i think ur code doesn't works as ur checking against msd first(/) , then
lsd(%)
we need to exchange these operations, then it works fine.
surender
On Wed, Aug 3, 2011 at 3:55 PM, Dave
Hi,
for 1 do +1
for 0 do -1
maintain count at every index of array
eg: 100110
array X 1 0 0 0 0 0 0 1 1 0
count 0 1 0 -1 -2 -3 -4 -5 -4 -3 -4
index -1 0 1 2 3 4 5 6 7 8 9
find count with same value having max index difference.
-3 is count at index 4 and 8
max difference
@Anand Shastri, if tasks enter randomly in runtime,
structure needs to add a member start_time, which will be different from
reference_time (till now u been considering it as same start time of every
task). finally GOOD work!!
surender
On Fri, Aug 5, 2011 at 9:42 AM, Gaurav Menghani
@sunny
consider *uncompressed* suffix tree, even with distinct elements maximum
number of nodes with string length n formed will be 2n.
once suffix tree is constructed, needs to traverse in dfs order appending
the node found on the way.
total complexity would be O(construction of suffix tree ) +
...@gmail.comwrote:
But still Printing O(N^2) substrings will take O(N^2) time isn't it ?
On Wed, Jul 27, 2011 at 12:39 PM, surender sanke surend...@gmail.comwrote:
@sunny
consider *uncompressed* suffix tree, even with distinct elements maximum
number of nodes with string length n formed
some extra time of construction of
tree and extra space too !
On Wed, Jul 27, 2011 at 1:45 PM, surender sanke surend...@gmail.comwrote:
*
/ \\
a bc
/\
b c
/
c
prints *a*
comes to b, appends a with bprints *ab*
comes to c
@anurag , it fails for {4,5,-2,0,-3,-4,4,2,3,5,-7};
urs calculates from index 4 to 9.
but maximum product is from index 5 to 10
surender
On Mon, Jul 25, 2011 at 11:38 AM, Anurag atri anu.anurag@gmail.comwrote:
Time O(n) , Space O(1)
int maximum_continuous_product ( int numbers[] , int
here's O(1)
x = n-pow(2,floor(log2(n)));
pos = x*k+1;
surender
On Fri, Jul 22, 2011 at 1:19 PM, Interstellar Overdrive
abhi123khat...@gmail.com wrote:
Yes, the solution with Circular linked list works fine but it certainly
involves great space considerations. I guess solving Josephus problem
small change here
x = n-pow(2,floor(log(n)));
pos = (x*k)%n+1;
surender
On Fri, Jul 22, 2011 at 4:54 PM, surender sanke surend...@gmail.com wrote:
here's O(1)
x = n-pow(2,floor(log2(n)));
pos = x*k+1;
surender
On Fri, Jul 22, 2011 at 1:19 PM, Interstellar Overdrive
abhi123khat
@kunal patil ur right, i forgot to mention k=2.
refer http://www.exploringbinary.com/powers-of-two-in-the-josephus-problem/
surender
On Fri, Jul 22, 2011 at 7:21 PM, Kunal Patil kp101...@gmail.com wrote:
@surender: I assume you want to give general solution to Josephus problem
in which we
josephus problem with mentioned k, k determines after how many persons to
execute, u guys are considering k=1 as josephus problem.
its with k=2 and still remains josephus problem.
On Fri, Jul 22, 2011 at 12:40 AM, chetan kapoor
chetankapoor...@gmail.comwrote:
yeah u r wrong...the question says
needs explicit function specialisation. be careful with constant strings.
T Add(T a, T b)
{return a+b ;}
template
char* Add char* a, char* b)
{return strcat((char*)a,b); }
surender
On Tue, Jul 19, 2011 at 10:17 PM, Anika Jain anika.jai...@gmail.com wrote:
here T becomes char *.. u r trying
try from back end
surender
On Wed, Jul 20, 2011 at 9:54 PM, Soumya Prasad Ukil
ukil.sou...@gmail.comwrote:
Two passes over the original array is required.
On 20 July 2011 08:10, SAMMM somnath.nit...@gmail.com wrote:
You can do it using stack concept:--
Pop the element from the end ,
how to deal with it??
surender
On Wed, Jul 20, 2011 at 9:02 PM, sunny agrawal sunny816.i...@gmail.comwrote:
http://groups.google.com/group/programming-puzzles/browse_thread/thread/4fecd0d904624a0d
this will clarify all doubts :)
On Wed, Jul 20, 2011 at 8:52 PM, SAMMM
sort each string according to their alphabetical order then hash it as key,
for hashing use preferably linked list as value for key
surender
On Thu, Jul 21, 2011 at 12:58 AM, SkRiPt KiDdIe anuragmsi...@gmail.comwrote:
Use trie for dictionary.Use permutaion to generate all anagrams and check
take two ptrs ptr1 and ptr2 pointing to head
move ptr1 until 1/4th of size of list.
move ptr1 and ptr2 until ptr1=null
ptr2 is pointing at 3/4th
surender
On Tue, Jul 19, 2011 at 3:42 PM, SAMMM somnath.nit...@gmail.com wrote:
Yaa this will work , you need to handle the case for odd number of
@Dave awesome..!
On Sat, Jul 16, 2011 at 7:15 PM, Dave dave_and_da...@juno.com wrote:
@Anand: Assuming that the file contains unsigned 32-bit integers. Set
an integer array a[65536] to zero, read through the file and tally the
numbers based on their low-order 16 bits: a[j0x]++. Since 4.3
@Dumanshu it also doesn't works, as min node doesn't satisfies bst
conditions, u swap it but it again creates inconsistencies with its left
subtree.
void binarytreetobst(btree *root)
{
if(root == NULL) return;
else if(root-left == NULL root-right == NULL) //base-case tree
of
@omega9
there's nothing like inorder hashing. maintain a map while traversing
through in order traversal of tree and make entry of sum-value,value.
i didn't thought of k/2 or k, if u have any idea pls suggest.
surender
On Mon, Jul 18, 2011 at 9:42 PM, omega9 tvssarma.ome...@gmail.com wrote:
@Damanshu for
1
/ \
2 3
/ \
4 5
/ \
67
im ending up at some non BST
surender
On Tue, Jul 19, 2011 at 4:06 AM, Dumanshu duman...@gmail.com wrote:
@Gaurav: The best solution would be to manipulate the given BTree in
place and get the BST. We don't
i have an idea of changing each row to decimal equilant
so we have an array of size n
each array element has logn bits, resetting each all bits except one
everytime and checking for AND of all n array
it should take maximum of O(logn)^n. improvements or ideas are welcome
surender
On Sat, Jul 16,
apart from stack and heap and text/code segment, there's another segment
called data segment for holding global and static vars.
Data segment itself has two variants for initialised and uninitialised
data(BSS).
surender
On Sun, Jul 17, 2011 at 5:09 PM, Ankur Khurana
p[i] maintains previous index from which b[i] has reached longest sequence
till i.
to get the actual list of non-decrease sequence, p has to be traversed
through back indices
for (u = b.size(), v = b.back(); u--; v = p[v]) b[u] = v;
surender
On Sat, Jul 16, 2011 at 9:06 AM, Neeraj Gupta
im a bit confused with child-sibling term, this expects output for
A
/\
B C
/ \ / \
DE F G
1
A
/
B C
/ /
DE FG
2 A
/
B-- C
/
DEFG
is output expected 1 or 2
@rishab, here it generates numbers which are powers of 2 until n gets to 0
int bit_generator(); // function which returns 1 and 0 with equal
probabilities
int generator(int n)
{
int generated_num[10],i;
int lg = (int)floor(log(n));
n -= pow(lg,2);
int m = 0;
i=0;
count number of elements from both lists and reverse list with minimum
number of elements, go ahead with checking and deleting linearly
surender
On Fri, Jul 15, 2011 at 10:38 PM, Nishant Mittal mittal.nishan...@gmail.com
wrote:
delete all the numbers found in list2 from list1 recursively or
.
i think if we apply merge sort on both the list then it would be easy to
delete after sorting.
correct me if i m wrong
On Sat, Jul 16, 2011 at 12:40 AM, surender sanke surend...@gmail.comwrote:
count number of elements from both lists and reverse list with minimum
number
its failing for 9*12 with n=7, if i take max square considered of hcf(9,12),
left space is 6*6 and 3*3.
i'll have more left space than what i consider three 4*4 squares, four 1*1
squares. leftspace is 1*5.
i think needs different trick
surender
On Mon, Jul 11, 2011 at 9:59 PM, Yogesh Yadav
i extend anurag's idea, instead of using an extra array,use map with keys
(k-ai , ai). while traversing through a, check if element found in map. if
found print pairs else add entry in map.
surender
2011/7/12 ●αηυяαg ∩ ℓιƒє ≈ Φ anuragmsi...@gmail.com
In order traversal results in a sorted list
space o(2n)
int LSM()
{
int a[] = {2,-8,-3,1,2};
int b[50],b1[50];
int n = sizeof(a)/sizeof(a[0]);
int i=0;
b[0]=a[0];
for(i=1;in;i++)
{
if(b[i-1]==0)
b[i]=a[i];
else
b[i]*=a[i];
}
b1[n-1] = a[n-1];
Hi, here i maintained two pair of indexes with respect to a and b, reply if
u found any test case which fails..
int npairs()
{
int a[] = {0,1,4,5,9,11,20};
int b[] = {0,2,3,6,8,11,15};
int c[20];
int len = sizeof(a)/sizeof(a[0]);
int i1,j1,i2,j2;
i1=len-1;
j1=len-2;
i2=len-2;
j2=len-1;
small mistake change a to b
if( (a[i1-1]+b[j2-1] a[i1]+b[j1]) (a[i1-1]+a[j2-1] a[i1]+b[j1]) )
surender
On Mon, Jul 11, 2011 at 3:54 PM, DK divyekap...@gmail.com wrote:
@surender: Your algo fails. See the counterexample posted by Sunny.
--
DK
http://twitter.com/divyekapoor
if b-a is exactly 2^k-1 , k0
then a + k bits (each bit is set using rand(0 1) ) with equal probability
surender
On Thu, Jul 7, 2011 at 1:20 PM, Nitish Garg nitishgarg1...@gmail.comwrote:
Yes, Random(0, 1) gives values 0 or 1 only with equal probabilities. But
your solution won't work.
--
You
@nitish i think all above meant
3+rand(0,1)+rand(0,1)+rand(0,1)
surender
On Thu, Jul 7, 2011 at 12:36 AM, Nitish Garg nitishgarg1...@gmail.comwrote:
If I understood you properly,
Random(a,b)=(b-a)*Random(0,1)+**a
-Random(3, 6) = (3)*Random(0, 1) + 3
= 3 + 3 = 6 or 0 +
val = 2*3*5*7*11
for(i = 0 to n-1)
if(val%a[i] == 0)
count++,sum+=a[i];
surender
On Tue, Jul 5, 2011 at 10:10 PM, Rajeev Bharshetty
rajeev.open.1...@gmail.com wrote:
Clarification : The number (count) is the number of elements between 1 and
n which are not evenly divisible by 5 prime
its two ints from X and Y classes :8
2 copies of int from Base class via Class X and Class Y :8
surender
On Tue, Jul 5, 2011 at 10:39 PM, oppilas . jatka.oppimi...@gmail.comwrote:
@T3rminal
Then how would you explain size of Z in case of normal inheritance(
sizeof(Z)=16
On Mon, Jul 4,
chk_bst doesnt works as its checking only for its immediate child's values.
i think inorder non decreasing sequence checking would require here which is
iteratively programmed
surender
On Thu, Jun 30, 2011 at 4:05 PM, Apoorve Mohan apoorvemo...@gmail.comwrote:
1.
int chk_bst(node *root)
{
seems its failing for
3
2 5
1 4 N N
Surender
On Mon, Jul 4, 2011 at 3:12 PM, Apoorve Mohan apoorvemo...@gmail.comwrote:
@surender: in the while loop all the nodes are being checked...please tell
me where u r stuck???
On Mon, Jul 4, 2011 at 2:13 PM, surender sanke
, Jul 4, 2011 at 3:28 PM, surender sanke surend...@gmail.comwrote:
seems its failing for
3
2 5
1 4 N N
Surender
On Mon, Jul 4, 2011 at 3:12 PM, Apoorve Mohan apoorvemo...@gmail.comwrote:
@surender: in the while loop all the nodes are being checked...please
tell
always maintain front and rear pointers, updating them accordingly during
insertion and deletion can achieve this in O(1)
surender
On Mon, Jul 4, 2011 at 9:59 PM, vaibhav shukla vaibhav200...@gmail.comwrote:
How to implement a QUEUE using a singly link list such that the operations
ENQUEUE
@t3erminal u r right!!!
thanks
surender
On Mon, Jul 4, 2011 at 4:16 PM, T3rminal piyush@gmail.com wrote:
@himanshu: http://en.wikipedia.org/wiki/Virtual_inheritance
Go through the last paragraph before reference.
On Jul 4, 12:02 pm, himanshu kansal himanshukansal...@gmail.com
wrote:
why two loops, find max and min and returns its difference
surender
On Fri, Jul 1, 2011 at 11:32 AM, sunny agrawal sunny816.i...@gmail.comwrote:
in function it is pointer pointing to an array of 6 elements , pointer have
size equal to word size in the system which is 4bytes for 32 bit
69 matches
Mail list logo