[algogeeks] Re: subarray wid sum=k
Make an associative sum array ... then find two indexes in the new
array such that b[j] - b[i] =k, which can be done by a hash table. The
found indexes form ur answer , i+1 j.
For e.g
A = {1,2,3,4,5,6,7,8,9}
B = {1,3,6,10,15,21,28,36,45}
and k = 15
now B[5] - B[2] = 15
so ans is 3 5 i.e 4+5+6
Running time O(n).
Regards
Aviral
http://coders-stop.blogspot.com/
On Sep 2, 8:35 pm, Neha Singh neha.ndelhi.1...@gmail.com wrote:
@Shashank : I think the sub array need not start from the the index 0. For
eg: If the array is of size 10, then the sub array can be from index 3 to 7.
Here is my solution :
Given : int arr[size] , int sum
1. Take an array prefix_sum[size]
2. int temp=0;prefix_sum[0]=0;
for(int i=0;isize;i++)
{
temp+=arr[i];
prefix_sum[i]=temp;
}
3. for (int i=0;isize;i++)
for(int j=0;j=i;j++)
{
if(prefix_sum[i]-prefix_sum[j]+arr[j] == sum)
printf(%d %d,i,j); // sub array from index i to j is the
required sub array
}
Time : O(n^2)
Space : O(n)
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Find the first K smallest element from 1 million sized array ...Amazon Question..
http://coders-stop.blogspot.com/2010/12/kth-largest-element.html On Mar 16, 12:18 pm, Srirang Ranjalkar srira...@gmail.com wrote: there are two ways to do it: 1. if k n, then simply have an array of size k. put the firsk k elements in the array and sort it. For each number you see which is less than arr[k], insert that number in the array and remove one element and sort it again. So by the end of the input you are left with k smallest elements and arr[k] gives you the kth smallest element. O(n.k.lgk) (assuming that sort is of order O(k.lgk)) 2. Maintain a max heap of size K, populate it and when you see an element less than the max of the heap, insert it and call heapify(). That way by the end of your input sequence you'll be left with k smallest elements in the heap. Thank you, Srirang Ranjalkar -- Luck is when hard work meets opportunity On Wed, Mar 16, 2011 at 12:38 PM, Sriram gupta gupta.sri...@gmail.comwrote: Use Max - heap of size K. On Wed, Mar 16, 2011 at 10:36 AM, DIPANKAR DUTTA dutta.dipanka...@gmail.com wrote: use heap tree to slove this.. plz see careercup post.. On Wed, Mar 16, 2011 at 10:31 AM, Ankit Sinha akki12...@gmail.comwrote: Asked in Amazon interview.. Find the first K smallest element from 1 million sized array . Assume your ram memory is so small that it cannot accommodate all 1 Million element at once. Guys provide your inputs on the same... Thanks, Ankit -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- DIPANKAR DUTTA M-TECH,Computer Science Engg. EC Dept,IIT ROORKEE Uttarakhand , India – 247667 --- website:http://people.iitr.ernet.in/shp/09535009/Website/index.html ph no-09045809987 Lab: 286454 email:dipan...@iitr.ernet.in -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Amazon Online Test
with the given constraints there is only one possible tree Regards Aviral http://coders-stop.blogspot.com On Feb 23, 5:47 pm, murthy.krishn...@gmail.com murthy.krishn...@gmail.com wrote: hii vinay, the prob is we can get many such trees given a preorder traversal with the condition that each node has zero or two children. Please correct me if I am wrong. Thanks, Krishna. On Wed, Feb 23, 2011 at 6:00 PM, murthy.krishn...@gmail.com murthy.krishn...@gmail.com wrote: thanks vinay :-) On Wed, Feb 23, 2011 at 5:39 PM, vinay reddy gvina...@gmail.com wrote: U need to construct a binary tree given only PreOrder traversal with the condition that each node has zero or two children. On Wed, Feb 23, 2011 at 10:52 AM, murthy.krishn...@gmail.com murthy.krishn...@gmail.com wrote: hii vinay, can u elaborate the third question thanks, Krishna On Wed, Feb 23, 2011 at 9:34 AM, vinay reddy gvina...@gmail.comwrote: Hi Anurag, I have taken that online test there were 3 questions ... 1. given a linked list check if it is a palindrome. 2.given two sorted arrays a[m] b[2*m], each contains m elements only. You need to merge those two arrays into second array b[2*m] 3. construct a Binary tree from a given String, where every node has zero or two children. e.g String = NNNLLL , N represents internal Node , L represents leaf Node. The alloted time was 1hr. and asked to write the function only ... no main function and all. hope this helps Thanks vinay On Wed, Feb 16, 2011 at 3:45 PM, Anurag Bhatia abhati...@gmail.comwrote: Has anyone give any first round online test for Amazon? If yes, can you please share details? --Anurag -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Sites for Interview Questions
http://coders-stop.blogspot.com/ On Jan 19, 12:47 pm, Decipher ankurseth...@gmail.com wrote: Careercup.com is best but for beginners you can also see geeksforgeeks.org . -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Amazon Interview - Algorithms
http://coders-stop.blogspot.com/2010/12/minimum-number-of-jumps.html -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Modular Arithmetic
we can do it when hcf(b,m)=1 , in that case find inverse of b by extended euclidean mod m and then multiply it by a Regards Aviral http://coders-stop.blogspot.com/ On Jan 12, 6:36 am, mittal mohitm.1...@gmail.com wrote: Somehelp with (a/b)modm expression. http://en.wikipedia.org/wiki/Modular_arithmetic i visited this link but found only for addition,subtraction and multiplication. -- 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: kth largest in tree
traverse inorder for k steps.. Regards Aviral http://coders-stop.blogspot.com/ On Jan 11, 10:03 pm, snehal jain learner@gmail.com wrote: how to find kth largest in bst. u cnt use static/global variable and u cnt pass value of k to any function. -- 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: twin pair
Use sieve algorithm for generating the primes and then check for the condition of twin numbers... Regards Aviral http://coders-stop.blogspot.com/ On Jan 11, 10:20 pm, ankit agarwal ankit.agarwal.n...@gmail.com wrote: as all prime no. greater than 3 are of the form 6n+1 or 6n-1 so start checking for all these numbers and if they both are prime then they will make pair count the pair no. as well as u move on Ankit On Jan 11, 9:23 pm, snehal jain learner@gmail.com wrote: you will be given an input no. n u have to output nth twin pair.. for eg input 1 output(3,5) input 5 output (29,31) twin pair is a pair in which prime no. differ by 2.. (3,5) , (5,7) (11,13), (17,19) (29,31) -- 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: SUMMER INTERNSHIP
You can consider submitting ur resumes for the internships in various IITs(forms for most of them are released in jan-mar) Regards http://coders-stop.blogspot.com/ On Jan 9, 6:47 pm, Decipher ankurseth...@gmail.com wrote: Post your resume on some Job search website or try LinkedIn(Job search option) . In the search engine (of that website) put trainee or software trainee . You might find some useful result there . Or google search internship . -- 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Adobe Question
Replace 0 by -1 and make a[i] as sum of all a[j] j=i Now u need to find the subarray with sum 0 For this u can use array of size 2n denoting -n to n Now at sum u can update array of 2n size with the index just found corresponding to that sum Overall complexity O(n) Regards http://coders-stop.blogspot.com/ On Jan 9, 6:19 pm, bittu shashank7andr...@gmail.com wrote: i think its DP Problemstill thinking on the soultion.. @ankur..ur approach nearly matches to mine..what i thought..but we need actual solution.. -- 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Adobe Question
Replace 0 by -1 and make a[i] as sum of all a[j] j=i Now u need to find the subarray with sum 0 For this u can use array of size 2n denoting -n to n Now at sum u can update array of 2n size with the index just found corresponding to that sum Overall complexity O(n) Regards http://coders-stop.blogspot.com/ On Jan 9, 6:19 pm, bittu shashank7andr...@gmail.com wrote: i think its DP Problemstill thinking on the soultion.. @ankur..ur approach nearly matches to mine..what i thought..but we need actual solution.. -- 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Google Question
http://coders-stop.blogspot.com/2010/12/most-used-data.html On Jan 7, 5:24 pm, bittu shashank7andr...@gmail.com wrote: You have a stream of infinite queries (ie: real time Google search queries that people are entering). Describe how you would go about finding a good estimate of 1000 samples from this never ending set of data and then write code for it. Thanks Regards Shashank -- 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: difference x
use hash map.O(n) or you can use use the binary search for each element O(nlogn) Regards Aviral http://coders-stop.blogspot.com On Dec 22, 3:05 pm, snehal jain learner@gmail.com wrote: How will you find the pair from an sorted array whose difference is x -- 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: largest substring
Suffix trees efficiently solves the problem. Regards Aviral http://coders-stop.blogspot.com On Dec 14, 8:43 pm, divya sweetdivya@gmail.com wrote: Given a string, find the largest substring that occur multiple times within the same string. Extend your code to find the substring occuring atleast n times. Perform in linear time and space. -- 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Puzzles
For programming Puzzles visit the blog http://coders-stop.blogspot.com/ -- 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
