Re: [algogeeks] Min Edges to be added to DAG to make it Strongly connected?
@atul: No,it's not the correct answer. Let's take an example of star like DAG:- A-- B--C | V D This DAG contains only one cut vertex(B) but we need to add two edges to make it strongly connected. On Sat, Oct 6, 2012 at 7:37 PM, atul anand atul.87fri...@gmail.com wrote: find no. of cut vertex in the DAGthat will be the ans. On 6 Oct 2012 19:33, KK kunalkapadi...@gmail.com wrote: Given a DAG(Directed Acyclic Graph). How to find out the minimum number of edges that needs to be added so that the given graph becomes Strongly Connected? -- 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/-/PbR3j9S5OXUJ. 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. -- -- ‘Kailash Bagaria’ B-tech 4th year Computer Science Engineering Indian Institute of Technology, Roorkee Roorkee, India (247667) -- 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.
Re: [algogeeks] amazon Interview
Yeah Atul is right.
Here is my solution:--
1) first rearrange the dimensions of slabs i.e. put bigger dimension in y
and smaller dimenson in x (rotate the slab)
2) then arrange all slabs in increasing order of x dimension
3) and then find the longest increasing sub-sequence based on y
dimension..
Ex:- (2,5),(5,1),(1,3),(1,2),(6,1)
Step-1= (2,5),(1,5),(1,3),(1,2),(1,6)
Step-2= (1,2),(1,3),(1,5),(1,6),(2,5)
Step-3= LIS=4 { (1,2),(1,3),(1,5),(1,6) OR (1,2),(1,3),(1,5),(2,5) }
Correct me if i wrong...
On Sun, Aug 26, 2012 at 3:54 PM, atul anand atul.87fri...@gmail.com wrote:
its a LIS problem.
need to think for n-dimension...
On 8/26/12, Ravi Ranjan ravi.cool2...@gmail.com wrote:
You are given many slabs each with a length and a breadth. A slab i can
be
put on slab j if both dimensions of i are less than that of j. In this
similar manner, you can keep on putting slabs on each other. Find the
maximum stack possible which you can create out of the given slabs
and for general n-dimesions
--
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.
--
--
‘Kailash Bagaria’
B-tech 4th year
Computer Science Engineering
Indian Institute of Technology, Roorkee
Roorkee, India (247667)
--
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.
Re: [algogeeks] Re: Printing random word from file
@Dave: Can you throw some light on random() function?? How it is generating
numbers between 0.0 and 1.0, and how many digits are there after the
point...because if there is only one digit then we will not be able to
print words after 10th place because 10*0.1(lowest number generated by
random())=1...since lowest number generated by the random() function is not
able to convert 10th word into printable situation,so we can't print words
above 10th place (inclusive) so it's not solving the original
problem???
On Sun, Aug 26, 2012 at 3:55 AM, Dave dave_and_da...@juno.com wrote:
@Kunal: Yes. You are missing that you don't know the number of words in
the file in advance. So, to use your method, you would have to read the
file once to find n, and then read through it again to select the lucky_pos
th word. The method I proposed only requires reading the file once.
Furthermore, assuming that rand() produces a random non-negative integer,
rand()%n is not equiprobable for all values of n. Consider n = 3. Then
since rand() takes on 2^31 values, rand()%3 cannot take on the values 0, 1,
and 2 with equal probability since 2^31 is not divisible by 3.
Dave
On Saturday, August 25, 2012 1:44:03 PM UTC-5, Kunal Patil wrote:
How about using rand()%n ??
Like, calculate lucky_pos = rand()%n
Then print word at lucky_pos th position...
Am I missing anything? All words are still equiprobable to get printed
right?
On Aug 20, 2012 11:45 AM, Dave dave_an...@juno.com wrote:
@Navin: Okay. Here is a paraphrase. Assume double function random()
returns a uniformly distributed random number = 0.0 and 1.0.
read first word from file into string save;
int i = 1
while not EOF
{
read next word from file into string temp;
i++;
if( i * random() 1.0 )
copy temp to save;
}
print save;
Dave
On Monday, August 20, 2012 12:02:54 AM UTC-5, Navin Kumar wrote:
@Dave sir, I didn't get your logic. Can you please elaborate it?
On Sun, Aug 19, 2012 at 4:08 AM, Dave dave_an...@juno.com wrote:
@Navin: Here is the algorithm:
Save the first word.
For i = 2, 3, ..., n = number of words in the file
replace the saved word with the i-th word with probability 1/i.
When EOF is reached, every word in the file will have probability 1/n
of being the saved word. Print it.
Dave
On Saturday, August 18, 2012 1:28:56 AM UTC-5, Navin Kumar wrote:
Print a *Random word* from a file. Input is path to a file,
constraints- No extra memory like hashing etc. All the words in the
file should have equal probability.
--
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/*
*ms**g/algogeeks/-/HxO-wNzEP9gJhttps://groups.google.com/d/msg/algogeeks/-/HxO-wNzEP9gJ
.
To post to this group, send email to algo...@googlegroups.com.
To unsubscribe from this group, send email to algogeeks+...@**
googlegroups.com**.
For more options, visit this group at http://groups.google.com/**group
**/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en.
--
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/-/crET-x06vpkJhttps://groups.google.com/d/msg/algogeeks/-/crET-x06vpkJ
.
To post to this group, send email to algo...@googlegroups.com.
To unsubscribe from this group, send email to algogeeks+...@**
googlegroups.com.
For more options, visit this group at http://groups.google.com/**
group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en.
--
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/-/pvqb27sRhFAJ.
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.
--
--
‘Kailash Bagaria’
B-tech 4th year
Computer Science Engineering
Indian Institute of Technology, Roorkee
Roorkee, India (247667)
--
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.
Re: [algogeeks] Given an array of 32bit unsigned integers in which every number appears exactly twice except three of them, find those three numbers in O(n) time using O(1) extra space
http://www.mycareerstack.com/question/279/find-out-non-repeating-numbers/ go through above link.you can expand it's idea for your case ...enjoy :) On Mon, Aug 13, 2012 at 4:42 PM, vivek rungta vivekrungt...@gmail.comwrote: On Mon, Aug 13, 2012 at 4:39 PM, vivek rungta vivekrungt...@gmail.comwrote: @Navin- Its only for continuous number :- if size of array = max-min for Non continuous it takes O(R) space complexity as suggested by daksh. where R is range of number. On Mon, Aug 13, 2012 at 2:55 PM, Navin navin.nit...@gmail.com wrote: @vivek :- what if the array index goes out of bound. I mean if |max - min | size of the array, then how will u mark the element as negative/positive because that index doesn't exist even. It won't work in that case. -- 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/-/DXEES3kjKJoJ. 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. -- -- ‘Kailash Bagaria’ B-tech 4th year Computer Science Engineering Indian Institute of Technology, Roorkee Roorkee, India (247667) -- 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.
Re: [algogeeks] Constant time solution needed
@vicky your approach doesn't work for (x1,y1) = (1,2) (x2,y2) = (2,3) By your Approach:- Ans= sumArray[x2][y2] - sumArray[x1][y1] + ip[x1][y1]=66-18+6= *54* But Actual Ans is 6+7+10+11=*34* On Sun, Aug 12, 2012 at 8:19 PM, ~*~VICKY~*~ venkat.jun...@gmail.comwrote: Lets build the array for the example you gave. i/p: 0 1 2 3 4 5 6 7 8 9 10 11 (x1,y1) = (0,0) (x2,y2) = (1,2) sumArray 0 1 23 4 10 18 28 12 27 45 66 (will take O(n^2) to build above array) So now when you get coordinates as input, you can calc the sum by Ans = sumArray[x2][y2] - sumArray[x1][y1] + ip[x1][y1] For our case it will be Ans = 18-0+0 = 18 Please lemme know if any bugs with the logic. On Sun, Aug 12, 2012 at 6:27 PM, Srividhya Sampath srisam261...@gmail.com wrote: @ Vicky Can yo explain with an illustration ? On Sat, Aug 11, 2012 at 10:07 PM, ~*~VICKY~*~ venkat.jun...@gmail.comwrote: May be you can consider creating a 2d array to pre process and store all the rectangle sums as a dependent subproblem, the sum of larger rect will be currValuesAdded+OldRectSum. So when you get the coordinate as input u can calc the needed sum by subtracting sum of big rect and small rect which is not included in the given coordinates. This can be called constant time if u don't include the preprocessing time. On Sat, Aug 11, 2012 at 9:57 PM, adarsh kumar algog...@gmail.comwrote: Sum of the integers meaning? Do you mind giving an example test case? regards. On Sat, Aug 11, 2012 at 7:10 PM, Srividhya srisam261...@gmail.comwrote: hi all:) The coordinates of a rectangle will be specified. there is a matrix of integers. yo should find the sum of the integers that fall in the region specified by the coordinates . The solution to be in constant time . -- 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/-/qHSmXBshmS4J. 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. -- Cheers, Vicky -- 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. -- Cheers, Vicky -- 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. -- -- ‘Kailash Bagaria’ B-tech 4th year Computer Science Engineering Indian Institute of Technology, Roorkee Roorkee, India (247667) -- 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.
Re: [algogeeks] what is priority inversion ?
http://msdn.microsoft.com/en-us/library/aa915356.aspx nice explanation .. On Wed, Aug 8, 2012 at 9:26 PM, Prem Krishna Chettri hprem...@gmail.comwrote: Read Mar's PathFinder Case Failure It would illustrate it .. Infact the case was observed first on PathFinder Mission itself. On Wed, Aug 8, 2012 at 4:41 AM, Hraday Sharma hradaysha...@gmail.comwrote: i just read about priority inversion , how does it take place ? i read it in Galvin , it wasnt clear there. -- 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/-/5aVHrwEsiewJ. 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. -- -- ‘Kailash Bagaria’ B-tech 4th year Computer Science Engineering Indian Institute of Technology, Roorkee Roorkee, India (247667) -- 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] c++_Output
Please explain the output of the following program
#include iostream
using namespace std;
int main()
{
int i=5;
i=i++ + ++i;
coutiendl;
int j=5;
coutj++ + ++jendl;
int k=5;
k=k++ + k++ + ++k;
coutkendl;
system(pause);
return 0;
}
--
--
‘Kailash Bagaria’
B-tech 3rd year
Computer Science Engineering
Indian Institute of Technology, Roorkee
Roorkee, India (247667)
--
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.
