Re: [algogeeks] MS ques

2011-07-20 Thread Deepthi Srinivasan
@Vicky Piyush's algo is based on a little trick to determine divisibility by 3. Number of bits set in odd position - Number of bits set in even position 'll be divisible by 3 For example, take 9. 1001. No. of bits set in odd position - number of bits set in even position is 0. Hence divisible by

Re: [algogeeks] Microsoft Interview Qn - Looping

2011-07-20 Thread naveen ms
yup...thank u:) -- 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

Re: [algogeeks] Re: Amazon

2011-07-20 Thread oppilas .
Thanks :) On Wed, Jul 20, 2011 at 10:55 AM, SAMM somnath.nit...@gmail.com wrote: This comes from the below n-n/2-n/2^2-..-n/2^k until n/2^k=1 Think from bits prospective -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To

[algogeeks] Re: Circle Circle more Circles .........

2011-07-20 Thread SAMMM
I doubth . For (d r0 + r1) ignore the point with smaller radius as it will overshadowed the bigger circle completely There may be a case where the circle is partially overlapped by the other circles. Then this algo will fail . The area will be of like these :- Suppose 3 circles are there X,YZ

[algogeeks] Re: Amazon ques

2011-07-20 Thread siva viknesh
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 sivavikne...@gmail.com 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

Re: [algogeeks] Non-redundant permutations of the string

2011-07-20 Thread ~*~VICKY~*~
@SkRiPt KiDdIe kindly explain the working of ur algo with the given example On Wed, Jul 20, 2011 at 1:09 AM, SkRiPt KiDdIe anuragmsi...@gmail.comwrote: #includeiostream #includestring using namespace std; void permute(string str,int x,string print) { int mask=0;

[algogeeks] Re: MS

2011-07-20 Thread Dumanshu
check the above solution.. urs is O(logn) mine is O(log k). On Jul 19, 11:35 pm, sagar pareek sagarpar...@gmail.com wrote: well i dont think so...any better solution will be there compare mine one On Wed, Jul 20, 2011 at 12:00 AM, Dumanshu duman...@gmail.com wrote: heres the code

Re: [algogeeks] Re: Amazon ques

2011-07-20 Thread Shubham Maheshwari
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 saurab...@gmail.com wrote: Q1 can be solved using some simple maths:)

Re: [algogeeks] Re: Solve it

2011-07-20 Thread Piyush Sinha
ya nitish above condition will do On 7/20/11, Nitish Garg nitishgarg1...@gmail.com wrote: I think: s[i] = max(s[i-2], s[i-2]+a[i], s[i-1], a[i]) should satisfy all the cases, even when all the numbers are negative. Pleas check. On Wed, Jul 20, 2011 at 12:44 AM, pnandy

Re: [algogeeks] Re: Adding w/o +

2011-07-20 Thread Anurag atri
int a = 20 ; //whatever value you like int b = 30 ; // again int sum = a - (-b) ; cout sum ; //eh ? On Wed, Jul 13, 2011 at 6:17 PM, vaibhav shukla vaibhav200...@gmail.comwrote: :D :D ;) On Wed, Jul 13, 2011 at 6:11 PM, Anika Jain anika.jai...@gmail.comwrote: @ vaibhav: ohh sorry,

Re: [algogeeks] Re: Amazon ques

2011-07-20 Thread saurabh singh
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::

[algogeeks] Whats the complexity?

2011-07-20 Thread Dumanshu
Given an infinite length list. u got to find index of an element k. use this approach- initially, take length as 2^x where x increases from 1 to ... while (still not found) { now if arr[2^x-1] k, increment x else binarysearch on length 2^(x-1) to 2^(x) } Please help me to find the

Re: [algogeeks] Non-redundant permutations of the string

2011-07-20 Thread Anantha Krishnan
@SkRiPt KiDdIe I got your logic. Nice. Thanks. Regards Anantha Krishnan On Wed, Jul 20, 2011 at 2:04 PM, SkRiPt KiDdIe anuragmsi...@gmail.comwrote: While you are on a state do not change ur state on encountering a specific character if u have already done so earlier.This check in addition to

Re: [algogeeks] Non-redundant permutations of the string

2011-07-20 Thread kavitha nk
pls explain...i cant get the idea...:( -- //BE COOL// kavi -- 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] Coding Ques..............

2011-07-20 Thread UMESH KUMAR
Hi Given an array how to find a sequence whose sum is maximum *but condition is that no two adjacent elements* of the given Array. ex:- Array:-[3,6,7,10,4] output:- {6,10}=16 Array::[12,3,5,30] output:-{12,30}= 42 -- You received this message because you are subscribed to the Google Groups

Re: [algogeeks] Re: Amazon ques

2011-07-20 Thread JIƬΣN BAJIYA
simple one!! . all the missing nos which r not present b/w 1 to n will be printed!! TC O(n) #include stdio.h #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 =

Re: [algogeeks] Re: Circle Circle more Circles .........

2011-07-20 Thread Piyush Sinha
I would like to redefine my algo with cases clarified... Create a queue that is made to contain the points... say points queue [1000]; for i:1 to n for j:i+1 to n Calculate d (distance between the two centers) if (d = r0 + r1) keep them in two separate queues //the circles don't

Re: [algogeeks] Re: Amazon ques

2011-07-20 Thread saurabh singh
space o(n) toomine takes o(1) space On Wed, Jul 20, 2011 at 3:50 PM, JIƬΣN BAJIYA j.s.baj...@gmail.com wrote: simple one!! . all the missing nos which r not present b/w 1 to n will be printed!! TC O(n) #include stdio.h #define size 1 int main() { int i, j, n;

[algogeeks] Re: Coding Ques..............

2011-07-20 Thread SAMMM
http://groups.google.com/group/algogeeks/browse_thread/thread/2ada4a0cd27036c2 This has already been discussed follow the above link . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to

Re: [algogeeks] interview question

2011-07-20 Thread surender sanke
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

Re: [algogeeks] Re: Circle Circle more Circles .........

2011-07-20 Thread Piyush Sinha
@Dumanshu..i am not partitioning them into just two queues... Moreover I just gave a raw idea...and yeah the complexity is in the order of n^2 only. There are many chances of improvement in it.. On Wed, Jul 20, 2011 at 5:30 PM, Dumanshu duman...@gmail.com wrote: @Piyush: Initially for

Re: [algogeeks] Re: Circle Circle more Circles .........

2011-07-20 Thread Pankaj
http://www.codechef.com/FEB10/problems/M5/ On Wed, Jul 20, 2011 at 5:35 PM, Piyush Sinha ecstasy.piy...@gmail.comwrote: @Dumanshu..i am not partitioning them into just two queues... Moreover I just gave a raw idea...and yeah the complexity is in the order of n^2 only. There are many

[algogeeks] Axis­ Aligned Rectangles

2011-07-20 Thread Dumanshu
Describe
 an
 algorithm 
that
 takes an 
unsorted 
array 
of 
axis‐ aligned 
rectangles 
and returns 
any 
pair 
of 
rectangles 
that overlaps, 
if 
there 
is such 
a 
pair. 

Axis‐aligned means 
that all 
the
 rectangle 
sides 
are 
either 
parallel
 or 
perpendicular to 
the 
x 
and y‐axis.

You

Re: [algogeeks] Negative index of array

2011-07-20 Thread sunny agrawal
if a[i] is negative then what u can do is first find the min of the array(say Min) and then do map[a[i]-Min]++ On Wed, Jul 20, 2011 at 6:17 PM, anonymous procrastination opamp1...@gmail.com wrote: Hello, Usually whenever we use index as key to count frequency or other similar algos. The

[algogeeks] Contiguous subarray with sum zero

2011-07-20 Thread Pankaj
Given an array with + and - numbers, including zero, Write an algorithm to find all the possible sub arrays which sum up to zero. For example, if given array is 20 , -9 , 3 , 1, 5 , 0, -6 , 9 Then possible sub arrays are: -9, 3, 1, 5 0 1, 5, 0, -6 -- You received this message because you are

Re: [algogeeks] C output

2011-07-20 Thread chetan kapoor
but its showing output On Wed, Jul 20, 2011 at 6:53 PM, mohit verma mohit89m...@gmail.com wrote: hey guys... 1. char c='a'; while(c=='a') { printf(%c,c); c=getchar(); } .. 2. char c='a'; while(c!='b') { printf(%c,c); c=getchar(); }

Re: [algogeeks] Re: Ever growing sorted linked list

2011-07-20 Thread Gaurav Popli
i want to ask one thing...the way some are saying first check with 2 then 4 and then 16to reach at that place we are suppose to traverse it and also hav eto put a condition say like countn or something...in this case also we are comparing so whats the usecorrect me if im wrong. On

[algogeeks] Re: C output

2011-07-20 Thread chetan
its showing same output... On Jul 20, 6:40 pm, chetan kapoor chetankapoor...@gmail.com wrote: but its showing output On Wed, Jul 20, 2011 at 6:53 PM, mohit verma mohit89m...@gmail.com wrote: hey guys... 1. char c='a';   while(c=='a') {  printf(%c,c); c=getchar(); }

[algogeeks] Re: C output

2011-07-20 Thread mohit
guys just give input a stream of characters as: a a a a a a a a a a a a ---(press enter) for second case input as: c d e f g h i j b -(press enter) and see the difference. (I know that printf() is line buffered. So why?) 1.printf() shows 'a' one time only. 2.here it shows

Re: [algogeeks] Output

2011-07-20 Thread Pankaj
I think sunny meant that in IA-64 the pointer is of size 8 but here we are assigning it to int *p. So, the segfault can occur. On Wed, Jul 20, 2011 at 6:52 PM, Sandeep Jain sandeep6...@gmail.com wrote: @Sunny: I couldn't understand how size of int int* matter here?? Regards, Sandeep Jain

Re: [algogeeks] Re: Ever growing sorted linked list

2011-07-20 Thread Pankaj
One a not so standard way of doing that is while creating the link list, keep an extra pointer in the node to point to the jump location. Just hold the previous node in a temp say address of 2 node and when i/p reaches 4, point the jumper pointer to 4 and make 4 the next jumper pointer. On

Re: [algogeeks] Contiguous subarray with sum zero

2011-07-20 Thread Ankur Khurana
create another array with sum of the elements from 0 to i. 20 , -9 , 3 , 1, 5 , 0, -6 , 9 20 , 11,14,15,20,0,14,23 above thing can be done in O(n) . now start hashing them (sum as keys and index as value), and if the sum exist previously , then that means from that point , from where you are

Re: [algogeeks] Re: C output

2011-07-20 Thread sunny agrawal
In first case first character input is 'a' and second is space so loop breaks in second loop runs till b is not read hence all characters including spaces are found in output On Wed, Jul 20, 2011 at 7:29 PM, mohit mohit89m...@gmail.com wrote: guys just give input a stream of characters

Re: [algogeeks] Re: Ever growing sorted linked list

2011-07-20 Thread saurabh singh
I think the novelty of this is that we are avoiding the comparison of new element with all the members of data in LL On Wed, Jul 20, 2011 at 7:27 PM, Ankur Khurana ankur.kkhur...@gmail.comwrote: @Popli : Bingo , that is what i was thinking and mentioned in my previous post.. On Wed, Jul

[algogeeks] Microsoft

2011-07-20 Thread Balaji S
Question - you are given a1b3c7d8.. an array like this. This is a compressed array. (Similar to Run Length) You are supposed to expand the given input IN-PLACE. That is, your array is large enough to hold the output. Example - Input - a1b4 - Array Length - 5 Output - a -- With Regards,

[algogeeks] Re: Negative index of array

2011-07-20 Thread SAMMM
You can try this out :--- If the range of the number are in between -N to +N eg: -10^6 to +10^6 , then take the the Absolute( Lower bound.) i:e N (10^6) . For each number add it in the Index [i+N] .. While printing the value of Number at Index X, Print the value in the Index [X-N]..

Re: [algogeeks] Re: Negative index of array

2011-07-20 Thread ankit sambyal
You can make the following structure : #define MAX 100 typedef struct { int count_positive; int count_negative; }Element; typedef Element Map[MAX]; Now you can just create a map as : Map map; Now for every element read, first check whether it is +ve or -ve. Use the absolute value of the

Re: [algogeeks] Re: Negative index of array

2011-07-20 Thread pacific :-)
This works. code #include iostream #include map using namespace std; int main() { mapint,int a; a[-1] = 0; couta[-1]endl; } /code On Wed, Jul 20, 2011 at 7:50 PM, ankit sambyal ankitsamb...@gmail.comwrote: You can make the following structure : #define MAX 100 typedef struct { int

[algogeeks] Re: Amazon ques

2011-07-20 Thread rkumar
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 shubham.veloc...@gmail.com wrote: let A:: ((n(n+1)/2) - sum) let B:: ((n(n+1)(2n+1)/6) - (sum of squares of elements)) then

[algogeeks] Re: Amazon ques

2011-07-20 Thread rkumar
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 shubham.veloc...@gmail.com wrote: @saurabh. kindly use a lil bit of indentation ... ur algo is illegible. On Wed, Jul

Re: [algogeeks] Contiguous subarray with sum zero

2011-07-20 Thread TIRU REDDY
Hey there are three answers for the given example. But you solution will give only 2 -- 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

[algogeeks] Re: C output

2011-07-20 Thread mohit
ohh ...got it. On Jul 20, 7:06 pm, sunny agrawal sunny816.i...@gmail.com wrote: In first case first character input is 'a' and second is space so loop breaks in second loop runs till b is not read hence all characters including spaces are found in output On Wed, Jul 20, 2011 at

Re: [algogeeks] Contiguous subarray with sum zero

2011-07-20 Thread TIRU REDDY
Sorry. This will work Best Regards, -- 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.

[algogeeks] Re: Microsoft

2011-07-20 Thread SAMMM
You can do it using stack concept:-- Pop the element from the end , taking two variable index1, index2 and Ch(character to Iterate) Eg:- a1b4 here index1=4 , Ch='b', index2=1; Start filling the element of Ch from the extreme end of the array .. From right hand side . The array will look

[algogeeks] Re: Output

2011-07-20 Thread SAMMM
Yaa even if it is 8 bytes long . Compiler will treat the value 10 as 8 bytes only . It should be able to assign it to the pointer of the same size (type) .. Try to free the dynamically allocated memory just before return 0 and tell me the result after compilation . Try this :- int main() {

Re: [algogeeks] Re: Output

2011-07-20 Thread sunny agrawal
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 somnath.nit...@gmail.com wrote: Yaa even if it is 8 bytes long . Compiler will treat the value 10 as 8 bytes only . It should be able

[algogeeks] [offTopic] Any one attended Informatica Interview

2011-07-20 Thread Rahul Menon
I would like if any here have attended informatica interview and also about the interview procedure. -- 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

[algogeeks] Re: Find valid anagrams

2011-07-20 Thread SAMMM
One question wht is the data structure used for the Dictionary ... The algo is dependent on the Implementation of the dictionary . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to

Re: [algogeeks] Re: MS

2011-07-20 Thread sagar pareek
oh common mine is log(k) too... i m taking only k elements On Wed, Jul 20, 2011 at 1:01 PM, Dumanshu duman...@gmail.com wrote: check the above solution.. urs is O(logn) mine is O(log k). On Jul 19, 11:35 pm, sagar pareek sagarpar...@gmail.com wrote: well i dont think so...any better

[algogeeks] Re: Contiguous subarray with sum zero

2011-07-20 Thread SAMMM
Nice solution dude . Like that one -- 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

Re: [algogeeks] Re: Microsoft

2011-07-20 Thread surender sanke
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 ,

Re: [algogeeks] Whats the complexity?

2011-07-20 Thread Ankur Khurana
when n is not defined , you want complexity in terms of ? On Wed, Jul 20, 2011 at 3:16 PM, Dumanshu duman...@gmail.com wrote: Given an infinite length list. u got to find index of an element k. use this approach- initially, take length as 2^x where x increases from 1 to ... while (still

[algogeeks] clock synchronisation puzzle..

2011-07-20 Thread shiv narayan
There is a clock at the bottom of the hill and a clock at the top of the hill. The clock at the bottom of the hill works fine but the clock at the top doesn't. How will you synchronize the two clocks. Obviously, you can,t carry either of the clocks up or down the hill! And you have a horse to help

[algogeeks] Re: Whats the complexity?

2011-07-20 Thread Dumanshu
that is why m confused. how would u rate this algo? in what order? On Jul 20, 10:44 pm, Ankur Khurana ankur.kkhur...@gmail.com wrote: when n is not defined , you want complexity in terms of ? On Wed, Jul 20, 2011 at 3:16 PM, Dumanshu duman...@gmail.com wrote: Given an infinite length

Re: [algogeeks] Re: Microsoft

2011-07-20 Thread Kamakshii Aggarwal
first count the no of elements to be printed say it is 'n'. now start from n-1 and start expanding the array from right to left.. On Wed, Jul 20, 2011 at 10:56 PM, surender sanke surend...@gmail.comwrote: try from back end surender On Wed, Jul 20, 2011 at 9:54 PM, Soumya Prasad Ukil

Re: [algogeeks] Re: Contiguous subarray with sum zero

2011-07-20 Thread sagar pareek
@Kamakshi... answer must be sub sequence of the array anyone pls explain ANKUR's approach On Thu, Jul 21, 2011 at 12:12 AM, Kamakshii Aggarwal kamakshi...@gmail.comwrote: for the above example,there are more possible sub arrays like -9,9 -9,0,9 On Thu, Jul 21, 2011 at 12:06 AM, sagar

Re: [algogeeks] Re: Contiguous subarray with sum zero

2011-07-20 Thread Pankaj
*Contiguous elements* On Thu, Jul 21, 2011 at 12:12 AM, Kamakshii Aggarwal kamakshi...@gmail.comwrote: for the above example,there are more possible sub arrays like -9,9 -9,0,9 On Thu, Jul 21, 2011 at 12:06 AM, sagar pareek sagarpar...@gmail.comwrote: @ankur pls explain through an

Re: [algogeeks] Re: Output

2011-07-20 Thread surender sanke
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

Re: [algogeeks] Re: Contiguous subarray with sum zero

2011-07-20 Thread sagar pareek
@Pankaj did u get ankur's approach? On Thu, Jul 21, 2011 at 12:16 AM, Pankaj jatka.oppimi...@gmail.com wrote: *Contiguous elements* On Thu, Jul 21, 2011 at 12:12 AM, Kamakshii Aggarwal kamakshi...@gmail.com wrote: for the above example,there are more possible sub arrays like -9,9 -9,0,9

Re: [algogeeks] Re: Contiguous subarray with sum zero

2011-07-20 Thread varun pahwa
nice solution by ankit. but can anyone tell if we were to find sequence that may or may not be contiguous. On Thu, Jul 21, 2011 at 12:22 AM, Kamakshii Aggarwal kamakshi...@gmail.comwrote: a little mistake in ankur's solution 20 , -9 , 3 , 1, 5 , 0, -6 , 9 20 , 11,14,15,20,20(instead of

Re: [algogeeks] Re: Contiguous subarray with sum zero

2011-07-20 Thread Kamakshii Aggarwal
@sagar: i read contiguous afterords therefore i deleted my post... and for ankur's approach : original array:20 , -9 , 3 , 1, 5 , 0, -6 , 9 array after addition:20 , 11,14,15,20,20,14,23 now when u hash second array elements then u fill find collision at value 14 and 20 this means terms b/w 1st

Re: [algogeeks] Re: Contiguous subarray with sum zero

2011-07-20 Thread sagar pareek
pls anyone explain it Please please please On Thu, Jul 21, 2011 at 12:37 AM, varun pahwa varunpahwa2...@gmail.comwrote: nice solution by ankit. but can anyone tell if we were to find sequence that may or may not be contiguous. On Thu, Jul 21, 2011 at 12:22 AM, Kamakshii Aggarwal

Re: [algogeeks] Re: Contiguous subarray with sum zero

2011-07-20 Thread Kamakshii Aggarwal
@sagar: i read contiguous afterwards therefore i deleted my post... and for ankur's approach : original array:20 , -9 , 3 , 1, 5 , 0, -6 , 9 array after addition:20 , 11,14,15,20,20,14,23 now when u hash second array elements then u fill find collision at value 14 and 20 this means terms b/w 1st

Re: [algogeeks] Re: Contiguous subarray with sum zero

2011-07-20 Thread sagar pareek
how collision occur at 14 and 20 actually i m not getting hash function Thanks in advance On Thu, Jul 21, 2011 at 12:39 AM, Kamakshii Aggarwal kamakshi...@gmail.comwrote: @sagar: i read contiguous afterwards therefore i deleted my post... and for ankur's approach : original array:20 , -9 , 3

Re: [algogeeks] Re: Find valid anagrams

2011-07-20 Thread SkRiPt KiDdIe
Use trie for dictionary.Use permutaion to generate all anagrams and check finally. -- 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

Re: [algogeeks] Axis­ Aligned Rectangles

2011-07-20 Thread SAMM
use line sweep method On 7/20/11, Dumanshu duman...@gmail.com wrote: Describe
 an
 algorithm 
that
 takes an 
unsorted 
array 
of 
axis‐ aligned 
rectangles 
and returns 
any 
pair 
of 
rectangles 
that overlaps, 
if 
there 
is such 
a 
pair. 

Axis‐aligned means 
that all 
the
 rectangle 


Re: [algogeeks] Re: Find valid anagrams

2011-07-20 Thread surender sanke
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

Re: [algogeeks] Re: Adding w/o +

2011-07-20 Thread Kamakshii Aggarwal
anika can u pls explain ur solution.I am not getting it. On Wed, Jul 20, 2011 at 1:27 PM, Anurag atri anu.anurag@gmail.comwrote: int a = 20 ; //whatever value you like int b = 30 ; // again int sum = a - (-b) ; cout sum ; //eh ? On Wed, Jul 13, 2011 at 6:17 PM, vaibhav shukla

Re: [algogeeks] Shooters in a circle

2011-07-20 Thread SAMM
I think it is related to Joshepus problm... ckeck wikipedia for more info. On 7/20/11, Vivek Srivastava srivastava.vivek1...@gmail.com wrote: If n people are standing in a circle ,they start shooting the person standing next to their neighbour.If they start firing in this way , determine

Re: [algogeeks] Re: Adding w/o +

2011-07-20 Thread Kamakshii Aggarwal
@anika: Now I am able to understand.thanks anyways.:) On Thu, Jul 21, 2011 at 1:18 AM, Kamakshii Aggarwal kamakshi...@gmail.comwrote: anika can u pls explain ur solution.I am not getting it. On Wed, Jul 20, 2011 at 1:27 PM, Anurag atri anu.anurag@gmail.comwrote: int a = 20 ; //whatever

[algogeeks] Re: Axis­ Aligned Rectangles

2011-07-20 Thread DK
O(N^2) naiive algorithm is obvious - check every pair of rectangles. This problem can be done in O(N log N) using a data structure called an R tree or a QuadTree. If you want to use and R Tree - read: http://en.wikipedia.org/wiki/R-tree The QuadTree approach is very simple. Maintain something

Re: [algogeeks] Re: Contiguous subarray with sum zero

2011-07-20 Thread Kamakshii Aggarwal
use sum calculated in 2nd array as index for hashing..and index for second array as value of hashing; for example original array:20 , -9 , 3 , 1, 5 , 0, -6 , 9 array after addition:20 , 11,14,15,20,20,14,23 according to above example hashing will be like this k[20]=0; k{11]=1; k[14]=2; k[15]=3;

[algogeeks] Re: Whats the complexity?

2011-07-20 Thread Dumanshu
it should involve the exponential increment! somebody plz help On Jul 20, 10:56 pm, Ankur Khurana ankur.kkhur...@gmail.com wrote: in my opinion , it is log(indexof(k)) On Wed, Jul 20, 2011 at 11:23 PM, Dumanshu duman...@gmail.com wrote: that is why m confused. how would u rate this algo?

Re: [algogeeks] Re: Microsoft

2011-07-20 Thread Gaurav Popli
is it given that string alphabets wud be in alphabetical order...?? On Thu, Jul 21, 2011 at 12:04 AM, Kamakshii Aggarwal kamakshi...@gmail.com wrote: first count the no of elements to be printed say it is 'n'. now start from n-1 and start expanding the array from right to left.. On Wed, Jul

Re: [algogeeks] Microsoft Interview Qn - Looping

2011-07-20 Thread Kamakshii Aggarwal
please some1 tell how to do part 2. On Wed, Jul 20, 2011 at 6:20 PM, kavitha nk kavithan...@gmail.com wrote: for 3rd v can replace decrement by an increment operator! //BE COOL// kavi -- You received this message because you are subscribed to the Google Groups Algorithm Geeks

[algogeeks] Re: clock synchronisation puzzle..

2011-07-20 Thread DK
Use a modification of the Cristian Algorithm. Start from the faulty clock. Go to the accurate clock, get a time sample T, come back. Set the new time as T + RTT* K/(1 + K), just choose a ratio K which represents the ratio of the time taken between going downhill and uphill It's a famous

[algogeeks] Microsoft Question!

2011-07-20 Thread archita
How to reverse the order of bits of a number in minimum space complexity? if the no is 11-1011 the output should b 1101. -- 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

[algogeeks] MS interview

2011-07-20 Thread ((** VICKY **))
Given a linked list with a n*n matrix elements write an algo to compute product of two such linked list. say n = 3then 1 2 3 4 5 6 7 8 9 will be given as 1-2-3-4-5-6-7-8-9 now given two matrices , given a algo to perform matrix multiplication giving result in thrid linked list. -- You

Re: [algogeeks] Re: Find valid anagrams

2011-07-20 Thread hary rathor
calculate hash value of word then compare with hash value of source string -- 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] Adobe ques

2011-07-20 Thread Anika Jain
write a c code that takes a 32 bit ip address n prints it in dotted notation as a.b.c.d. The code shall work for big endian as well as for little endian.. In this how can i make it common for big endian and little endian?? if in little endian my lower order 8 bits shall be d but for big endian

Re: [algogeeks] Adobe ques

2011-07-20 Thread Piyush Sinha
@Anika..can u give one example?? On 7/21/11, Anika Jain anika.jai...@gmail.com wrote: write a c code that takes a 32 bit ip address n prints it in dotted notation as a.b.c.d. The code shall work for big endian as well as for little endian.. In this how can i make it common for big endian

Re: [algogeeks] Microsoft Question!

2011-07-20 Thread Piyush Sinha
unsigned int reverse_bits (unsigned int n) { if(n==1) return n; int j,p; for(j = 31;j0;j--) if(n(1j)) break; //to find the first set bit from left p =0; while(jp) { int x1 = (n (1j))j; int x2 = (n(1p))p; if(x1!=x2) {

Re: [algogeeks] Shooters in a circle

2011-07-20 Thread karthiga m
take an assumption,if an one ppl s there he never die eg : no.of ppl person who will not die 11 2 1 3 2 4 4 5 1 6 On 7/21/11, SAMM somnath.nit...@gmail.com wrote: I think it is related to

Re: [algogeeks] Re: Coding Ques..............

2011-07-20 Thread UMESH KUMAR
Hi @Somnath my question is some different if given array :3,2,7,10 So according to last discussion Only Out put is *13 *not the show elements Output :: {3,10} So basically my question is that how to pick all elements that return max sum Thanks.. -- You received this message

[algogeeks] Re: Microsoft Question!

2011-07-20 Thread Ankit Gupta
unsigned int reverse_bits (unsigned int n) { unsigned int m; m=0; while(n) { m*=2; if( n1 ) { m+=1; } n=1; } return m; } -- You received this message because you are subscribed to the Google Groups

Re: [algogeeks] Re: C OUTPUT HELP

2011-07-20 Thread Anurag atri
@Nicks : Kindly share the source from where you are practicing these c output questions .. Thank You :) -- 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

Re: [algogeeks] Re: Solve it

2011-07-20 Thread Anisha Mazumder
do both s[i-2] and s[i-1] need to be checked? isn't by construction s[i-1]=s[i-2] ? what about s[i] = max( s[i-2]+a[i], s[i-1], a[i]) ? On Wed, Jul 20, 2011 at 3:48 AM, Piyush Sinha ecstasy.piy...@gmail.comwrote: ya nitish above condition will do On 7/20/11, Nitish Garg