Re: [algogeeks] Re: Tejas Networks - Written Test
2. can this be done in the following manner ? print the preorder and inorder traversal of the tree and then you can build it back but for binary trees On Tue, Jan 11, 2011 at 1:12 PM, juver++ avpostni...@gmail.com wrote: 1. Any shortest path algorithms on graphs (Dijkstra, Bellman-Ford, Floyd). 2. Store it's edges while doing DFS. -- 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.comalgogeeks%2bunsubscr...@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 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.
Re: [algogeeks] Re: Tejas Networks - Written Test
You have a general tree. -- 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.
Re: [algogeeks] MICROSOFT IDC
Is there any way to do it using recursion? Interviewer asked to do it using recursion. -- 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.
Re: [algogeeks] MICROSOFT IDC
Of course, pass pointers to the head of the lists to the function and proceed until both of them reach end of the respective lists. -- 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] google paper/...plz help..its urgent
1. Quick-sort is run on two inputs shown below to sort in ascending
order
(i) 1,2,3, ….,n
(ii) n, n - 1, n - 2, …., 2, 1
Let C1 and C2 be the number of comparisons made for the inputs (i) and
(ii) respectively. Then,
a) C1 C2
b) C1 C2
c) C1 = C2
d) We cannot say anything for arbitrary n
2. Which of the following languages over {0, 1} is regular?
a) 0i1j such that i ≤ j
b) 0iw1j such that w ∈ {0, 1}∗ and i ≥ 0
c) All strings of 0s and 1s such that every pth character is 0 where p
is prime
d) None of the above
3. We are given a set X = {x1, x2, ..., xn} where xi = 2i. A sample S
(which is a subset of X) is
drawn by selecting each xi independently with probability pi = 1 / 2.
The expected value of the
smallest number in sample S is:
a) 1 / n
b) 2
c) sqrt(n)
d) n
4. Let S be an NP-complete problem and Q and R be two other problems
not known to be in
NP. Q is polynomial time reducible to S and S is polynomial-time
reducible to R. Which one of
the following statements is true?
a) R is NP-complete
b) R is NP-hard
c) Q is NP-complete
d) Q is NP-hard
5. For any string s ∈ (0 + 1)*, let d(s) denote the decimal value of s
(eg: d(101) = 5, d(011) = 3).
Let L = {s ∈ (0+1)* | d(s) mod 5 = 2 and d(s) mod 7 = 4}. Which of the
following statements is
true?
a) L is recursively enumerable, but not recursive
b) L is is recursive, but not context-free
c) L is context-free, but not regular
d) L is regular
Common data for questions 6 and 7
The 2n vertices of a graph G corresponds to all subsets of a set of
size n. Two vertices of G are
adjacent if and only if the corresponding sets intersect in exactly 2
elements
6. The number of vertices of degree zero in G is:
a) 1
b) n
c) 2n - 1
d) None
7. The number of connected components in G is:
a) 2n
b) n + 2
c) n C 2
d) None
8. There are 5 nested loops written as follows,
int counter = 0;
for (int loop_1=0; loop_1 10; loop_1++) {
for (int loop_2=loop_1 + 1; loop_2 10; loop_2++) {
for (int loop_3=loop_2 + 1; loop_3 10; loop_3++) {
for (int loop_4=loop_3 + 1; loop_4 10; loop_4++) {
for (int loop_5=loop_4 + 1; loop_5 10; loop_5++) {
counter++;
}
}
}
}
}
What will be the value of counter in the end (after all the loops
finished running)?
a) 15C5
b) 14C5
c) 10C5
d) 10 * 9 * 8 * 7 * 6 * 5
--
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] No. of ways to Merge 2 arrays
Can anyone help: *In how many ways can 2 sorted arrays of combined size N be merged?* -- Thanks and regards, ARINDAM CHATTERJEE, Mtech Second Year, Department of Computer Science and Engineering, IIT Bombay, Powai, Mumbai-400076 Contacts : +919022313724 Living is about making tomorrow better than today !! -- 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.
Re: [algogeeks] MICROSOFT IDC
May be combining merge sort and calculating final result is a possible 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] Amazon Analytical Puzzle
if you had 5,623 participants in a tournament, how many games would need to be played to determine the winner 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.
Re: [algogeeks] No. of ways to Merge 2 arrays
one approch is very simple. 1. keep two index on arrays, lets say array1 and array2, which ever index has small element put this element to output array and move index of smaller element to next position. repeate above process untill one of the array index get exausted then append remaining array to output. corner cases when one array is 1,2,3,4 and other is 5,6,7,8,...in this case you just need to append them...take care of this... On Wed, Jan 12, 2011 at 2:53 PM, Arindam Chatterjee arindam.chatterje...@gmail.com wrote: Can anyone help: *In how many ways can 2 sorted arrays of combined size N be merged?* -- Thanks and regards, ARINDAM CHATTERJEE, Mtech Second Year, Department of Computer Science and Engineering, IIT Bombay, Powai, Mumbai-400076 Contacts : +919022313724 Living is about making tomorrow better than today !! -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -- Manoj Lalavat -- 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.
Re: [algogeeks] Amazon Analytical Puzzle
check this... Tournament Algorithm Another method is tournament algorithm. The idea is to conduct a knockout minimal round tournament to decide the ranks. It first organises the games (comparisons) between adjacent pairs and moves the winners to next round until championship (the first best) is decided. It also constructs the tournament tree along the way. Now the second best element must be among the direct losers to winner and these losers can be found out by walking in the binary tree in O(log *n*) time. It organises another tournament to decide the second best among these potential elements. The third best must be one among the losers of the second best in either of the two tournament trees. The approach continues until we find k elements. This algorithm takes O(n + k log *n*) complexity, which for any fixed *k* independent of *n* is O(*n*). On Wed, Jan 12, 2011 at 3:05 PM, bittu shashank7andr...@gmail.com wrote: if you had 5,623 participants in a tournament, how many games would need to be played to determine the winner 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -- Manoj Lalavat -- 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: Amazon Analytical Puzzle
@manoj..can u elaborate by making what exactly u mean...??? According to me if Tournament strategy is is used then i think its ok... After each round, you would have half the number that started the previous round; except if it were an odd number it would he half + 1. So 13 rounds. 2812 1 1406 2 703 3 352 4 176 5 88 6 44 7 22 8 11 9 6 10 3 11 2 12 1 13 Regrads Shashank Don't b Evil U Can Earn while U Learn -- 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.
Re: [algogeeks] Amazon Analytical Puzzle
Each game eliminates one participant 5622 will have to be eliminated, so 5622 games. On Wed, Jan 12, 2011 at 3:09 PM, manoj lalavat manoj.lala...@gmail.comwrote: check this... Tournament Algorithm Another method is tournament algorithm. The idea is to conduct a knockout minimal round tournament to decide the ranks. It first organises the games (comparisons) between adjacent pairs and moves the winners to next round until championship (the first best) is decided. It also constructs the tournament tree along the way. Now the second best element must be among the direct losers to winner and these losers can be found out by walking in the binary tree in O(log *n*) time. It organises another tournament to decide the second best among these potential elements. The third best must be one among the losers of the second best in either of the two tournament trees. The approach continues until we find k elements. This algorithm takes O(n + k log *n*) complexity, which for any fixed *k* independent of *n* is O(*n* ). On Wed, Jan 12, 2011 at 3:05 PM, bittu shashank7andr...@gmail.com wrote: if you had 5,623 participants in a tournament, how many games would need to be played to determine the winner 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -- Manoj Lalavat -- 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.comalgogeeks%2bunsubscr...@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 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] google mcqs
A 4-stage pipeline has the stage delays as 150, 120, 160 and 140 ns
(nano seconds)
respectively. Registers that are used between the stages have a delay
of 5 ns each. Assuming
constant clocking rate, the total time taken to process 1000 data
items on this pipeline will
approximately be
a. 120 us (micro seconds)
b. 165 us
c. 180 us
d. 175 us
Which of the following statements are true?
I Shortest remaining time first scheduling may cause starvation
II Preemptive scheduling may cause starvation
III Round robin is better than first come first serve in terms of
response time
a) I only
b) I and III only
c) II and III only
d) I, II and III
Increasing the RAM of a computer typically improves performance
because:
a. Virtual memory increases
b. Larger RAMs are faster
c. Fewer segmentation faults occur
d. Fewer page faults occur
Suppose we want to synchronize two concurrent processes P and Q using
binary
semaphores S and T. The code for the processes P and Q is shown below.
Process P:
while (1) {
W:
print '0’;
print '0';
X:
}
Process Q:
while (1) {
Y:
print '1'
print '1'
Z:
}
Synchronization statements can be inserted only at points W, X, Y and
Z.
V() increments the semaphore, whereas P() decrements it
Which of the following will always lead to an output staring with
'001100110011' ?
a) P(S) at W, V(S) at X, P(T) at Y, V(T) at Z, S and T initially 1
b) P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S initially 1, and T
initially 0
c) P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S and T initially 1
d) P(S) at W, V(S) at X, p(T) at Y, V(T) at Z, S initially 1, and T
initially 0
can any1 suggest some source for such kind of questions
--
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.
Re: [algogeeks] MICROSOFT IDC: unsorted linked lists intersection
without sorting, it will be mess...O(n^2)
with recursion, it will be lot of stack space however since this is asked i
would do it this way
The only problem i see with this code is what if the lists are 1,2,1,2 AND
2,1,1,1
This code will give 2 common message twice and 1 common message 4 times
struct node* sortAndMerge(struct node *a, struct node *b)
{
if !a return b;
if !b return a;
struct node *result = NULL;
if (a-data =b-data)
{ result =a; result-next = sortAndMerge(a-next, b);}
else { result =b; result-next = sortAndMerge(b-next, a);}
return result;
}
void merge(struct node **pL)
{
if (!(*pL) || !(*pL-next)) return NULL;
struct node *a=NULL;
struct node *b=NULL;
split(*pL, a, b);
merge(a); merge(b);
sortAndMerge(a,b);
}
void intersect(struct node *a, struct node *b)
{
if (!a) || (!b) return;
merge(a);
merge(b);
struct node * result = sortAndMerge(a,b);
struct node *current =result;
while (current)
{
if (current-data ==current-next-data) printf(%d ,
current-data);
current = current-next;
}
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jan 12, 2011 at 2:35 PM, Saurabh Koar saurabhkoar...@gmail.comwrote:
I mean is it possible to solve the problem using recursion and without
sorting? (in O(1) space and O(n^2) complexity? ). As he didnt say
anything,I am just clearing my doubts.
--
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.comalgogeeks%2bunsubscr...@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 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.
Re: [algogeeks] google mcqs
An insurance company issues a policy on a small boat under the following
conditions:
The replacement cost of $5000 will be paid for a total loss. If it is not a
total loss,
but the damage is more than $2000, then $1500 will be paid. Nothing will be
paid for damage costing $2000 or less and of course nothing is paid out if
there
is no damage. The company estimates the probability of the first three
events
as .02, .10, and .30 respectively. The amount the company should charge for
the
policy if it wishes to make a profit of $50 per policy on average is:
a) $250
b) $201
c) $300
d) $1200
On Wed, Jan 12, 2011 at 3:15 PM, snehal jain learner@gmail.com wrote:
A 4-stage pipeline has the stage delays as 150, 120, 160 and 140 ns
(nano seconds)
respectively. Registers that are used between the stages have a delay
of 5 ns each. Assuming
constant clocking rate, the total time taken to process 1000 data
items on this pipeline will
approximately be
a. 120 us (micro seconds)
b. 165 us
c. 180 us
d. 175 us
Which of the following statements are true?
I Shortest remaining time first scheduling may cause starvation
II Preemptive scheduling may cause starvation
III Round robin is better than first come first serve in terms of
response time
a) I only
b) I and III only
c) II and III only
d) I, II and III
Increasing the RAM of a computer typically improves performance
because:
a. Virtual memory increases
b. Larger RAMs are faster
c. Fewer segmentation faults occur
d. Fewer page faults occur
Suppose we want to synchronize two concurrent processes P and Q using
binary
semaphores S and T. The code for the processes P and Q is shown below.
Process P:
while (1) {
W:
print '0’;
print '0';
X:
}
Process Q:
while (1) {
Y:
print '1'
print '1'
Z:
}
Synchronization statements can be inserted only at points W, X, Y and
Z.
V() increments the semaphore, whereas P() decrements it
Which of the following will always lead to an output staring with
'001100110011' ?
a) P(S) at W, V(S) at X, P(T) at Y, V(T) at Z, S and T initially 1
b) P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S initially 1, and T
initially 0
c) P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S and T initially 1
d) P(S) at W, V(S) at X, p(T) at Y, V(T) at Z, S initially 1, and T
initially 0
can any1 suggest some source for such kind of questions
--
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.comalgogeeks%2bunsubscr...@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 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.
Re: [algogeeks] No. of ways to Merge 2 arrays
@Manoj: Thanks, but can u tell me the no. of ways in which merging can be done on 2 arrays. On Wed, Jan 12, 2011 at 3:06 PM, manoj lalavat manoj.lala...@gmail.comwrote: one approch is very simple. 1. keep two index on arrays, lets say array1 and array2, which ever index has small element put this element to output array and move index of smaller element to next position. repeate above process untill one of the array index get exausted then append remaining array to output. corner cases when one array is 1,2,3,4 and other is 5,6,7,8,...in this case you just need to append them...take care of this... On Wed, Jan 12, 2011 at 2:53 PM, Arindam Chatterjee arindam.chatterje...@gmail.com wrote: Can anyone help: *In how many ways can 2 sorted arrays of combined size N be merged?* -- Thanks and regards, ARINDAM CHATTERJEE, Mtech Second Year, Department of Computer Science and Engineering, IIT Bombay, Powai, Mumbai-400076 Contacts : +919022313724 Living is about making tomorrow better than today !! -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -- Manoj Lalavat -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks and regards, ARINDAM CHATTERJEE, Mtech Second Year, Department of Computer Science and Engineering, IIT Bombay, Powai, Mumbai-400076 Contacts : +919022313724 Living is about making tomorrow better than today !! -- 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: MICROSOFT IDC
try this...its will be less then O(n^2) 1. find the biggest and smallest element in smaller list 2. start traversing other list and compare every element with the biggest smallest element of first list if element of second list is grater then the biggest element of first list then then move to next position in second list || element of second list is smaller then the smallest element of first list then move to next position in second list else traverse first list and print if element of second list exist in first list, if(exist) print and break this loop only no sorting...and better performance On Jan 12, 2:27 pm, juver++ avpostni...@gmail.com wrote: May be combining merge sort and calculating final result is a possible 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.
Re: [algogeeks] No. of ways to Merge 2 arrays
merging is merging...you can use different methods to do this... 1. I have told you... 2. build BST and print inorder 3. find biggest element, create hash of that size, init table element to zero (assume zero is not in input array) traverse each array and put that element into hash table finally print hashtable for non-zero elements. ..I hope you get some idea... On Wed, Jan 12, 2011 at 3:16 PM, Arindam Chatterjee arindam.chatterje...@gmail.com wrote: @Manoj: Thanks, but can u tell me the no. of ways in which merging can be done on 2 arrays. On Wed, Jan 12, 2011 at 3:06 PM, manoj lalavat manoj.lala...@gmail.comwrote: one approch is very simple. 1. keep two index on arrays, lets say array1 and array2, which ever index has small element put this element to output array and move index of smaller element to next position. repeate above process untill one of the array index get exausted then append remaining array to output. corner cases when one array is 1,2,3,4 and other is 5,6,7,8,...in this case you just need to append them...take care of this... On Wed, Jan 12, 2011 at 2:53 PM, Arindam Chatterjee arindam.chatterje...@gmail.com wrote: Can anyone help: *In how many ways can 2 sorted arrays of combined size N be merged?* -- Thanks and regards, ARINDAM CHATTERJEE, Mtech Second Year, Department of Computer Science and Engineering, IIT Bombay, Powai, Mumbai-400076 Contacts : +919022313724 Living is about making tomorrow better than today !! -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -- Manoj Lalavat -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks and regards, ARINDAM CHATTERJEE, Mtech Second Year, Department of Computer Science and Engineering, IIT Bombay, Powai, Mumbai-400076 Contacts : +919022313724 Living is about making tomorrow better than today !! -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -- Manoj Lalavat -- 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: No. of ways to Merge 2 arrays
Explain problem using examples. When two merging are different? -- 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.
Re: [algogeeks] Re: No. of ways to Merge 2 arrays
what? On Wed, Jan 12, 2011 at 3:38 PM, juver++ avpostni...@gmail.com wrote: Explain problem using examples. When two merging are different? -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -- Manoj Lalavat -- 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: MICROSOFT IDC
it is better then pute brute force, but it is O(N^2) -- 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.
Re: [algogeeks] Re: MICROSOFT IDC
worst case...but in avrg cases its better and dont use sorting... On Wed, Jan 12, 2011 at 3:41 PM, juver++ avpostni...@gmail.com wrote: it is better then pute brute force, but it is O(N^2) -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -- Manoj Lalavat -- 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.
Re: [algogeeks] Re: Amazon Analytical Puzzle
yes...but if you want to find second best and third best and so on...then you need to consider all loser to first winner and so onthink on this line.. On Wed, Jan 12, 2011 at 3:14 PM, bittu shashank7andr...@gmail.com wrote: @manoj..can u elaborate by making what exactly u mean...??? According to me if Tournament strategy is is used then i think its ok... After each round, you would have half the number that started the previous round; except if it were an odd number it would he half + 1. So 13 rounds. 2812 1 1406 2 703 3 352 4 176 5 88 6 44 7 22 8 11 9 6 10 3 11 2 12 1 13 Regrads Shashank Don't b Evil U Can Earn while U Learn -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -- Manoj Lalavat -- 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.
Re: [algogeeks] Re: No. of ways to Merge 2 arrays
What do you mean by number of ways? A = 1(1), 1(2), 2 B = 1(3), 3. a(b) - means - that there is an element with value a but with unique id b if there is only one element with such value, skip brackets. Here are the possible results of merging (using operator for the values) 1(1); 1(2); 1(3); 2; 3 1(1); 1(3); 1(2); 2; 3 1(2); 1(1); 1(3); 2; 3 1(2); 1(3); 1(1); 2; 3 1(3); 1(1); 1(2); 2; 3 1(3); 1(2); 1(1); 2; 3 So, the answer will be something like P(1)! * P(2)! * P(3)! ... * P(n)! where P(k) means - amount of elements with value = Array[k]. -- 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.
Re: [algogeeks] Re: MICROSOFT IDC
In average it is O(N^2) anyway but with a bit smaller constant. -- 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.
Re: [algogeeks] Re: MICROSOFT IDC
hahahahgood...givesome thing better without sorting... On Wed, Jan 12, 2011 at 3:48 PM, juver++ avpostni...@gmail.com wrote: In average it is O(N^2) anyway but with a bit smaller constant. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -- Manoj Lalavat -- 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.
Re: [algogeeks] Re: MICROSOFT IDC
However, sorting works faster than your straighforward 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 Interview Question
can someone just expain the plain simple logic used to solve this
problem ??
Cdn't get it seeing the code
On Jan 11, 10:08 pm, Jammy xujiayiy...@gmail.com wrote:
There are apparently more than one way to make the cuts(totally it'll
still be three). The code only outputs first possible.
On Jan 11, 10:42 am, Arpit Sood soodfi...@gmail.com wrote:
oh, i considered that the sum of the total numbers for both john and mary to
be equal after the whole division process. I am not considering pair wise
sum.
That's why for input
1 4 5 6 2 2 2 2 4 5 6 1 1 7 8 8 1 7
segments should be:
(John)1 4 5 6 2 2 - (Mary)2 2 4 5 6 1 1 7 8 -- (John) 8 1 7
minimum cuts made are 2
but if we consider pair wise cuts as done by you, output will be :
(John)1 4 5 6 2 2 - (Mary)2 2 4 5 6 1 --- (john) 1 7 8 -- (Mary) 8 1
7
minimum cuts = 3
On Tue, Jan 11, 2011 at 8:38 PM, Jammy xujiayiy...@gmail.com wrote:
@Arpit Please explain your solution to me. As far as I understand,
every alternate of two person should sum up equally. Which means
every pair of (john, mary) has the same sum for john and mary.
On Jan 11, 2:55 am, Arpit Sood soodfi...@gmail.com wrote:
@jammy your code isnt working for the mentioned test case.
One simple approach is to go greedy on the test data, but that wont
always
give the optimum answer.
On Tue, Jan 11, 2011 at 1:11 PM, Arpit Sood soodfi...@gmail.com wrote:
the output for first test case is wrong it should be
(John)1 4 5 6 2 2 - (Mary)2 2 4 5 6 1 1 7 8 -- (Mary) 8 1 7
minimum cuts made are 2
On Tue, Jan 11, 2011 at 10:04 AM, Jammy xujiayiy...@gmail.com wrote:
(a) it is intuitive to see we need to make a recursive function which
takes the following arguments:
1) array,
2) start index,
3) length of the array,
4) a sentinel indicating if it is the first half or second half
5) a sum if it is the second half
6) number of cuts so far
7) a global minimal cuts
So my recursive function looks something like this,
void cutMinHelper(int *arr, int start, int len, bool isFirst, int
sum,
int cut, int minV, vectorint res);
and its wrapper just takes two arguments
void cutMin(int *arr, int len);
The idea is to differentiate the first half and second half. If it's
the first half, you need make all possible cuts, and recursive call
itself to get the second done. If it's the second half, you need
calculate sums all the way to the end. Break out of the loop if it
equals to the sum of the first part. And then recursively call itself
to get the first half done.
I hope my code explains the idea...Please report any bugs you find :)
vectorint minVector; //storing the cuts
void cutMin(int *arr, int len){
int cut=0, minV = INT_MAX;
vectorint res;
cutMinHelper(arr, 0, len, true, 0, cut, minV, res);
if(minVINT_MAX){
coutminimal cut isminVendl;
}
}
void cutMinHelper(int *arr, int start, int len, bool isFirst, int
sum,
int cut, int minV, vectorint res){
if(isFirst startlen){
if(start==0) cut = 0;
int sum = arr[start];
cut++;
for(int i = start+1; i len; i++){
vectorint addOne = res;
addOne.push_back(i-1);
cutMinHelper(arr, i , len, !isFirst, sum, cut,
minV, addOne);
sum += arr[i];
}
}
if(!isFirst startlen){
int i, sum2 = 0;
for(i = start; i len; i++){
sum2 += arr[i];
if(sum2 == sum){
break;
}
}
if( i==len-1 sum2==sum) {
if(cutminV){
minV = cut;
minVector = res;
}
}
if(ilen-1){
cut++;
vectorint addOne = res;
addOne.push_back(i);
cutMinHelper(arr, i+1, len, !isFirst, 0, cut,
minV,
addOne);
}
}
}
(b) I didn't write the code, but I think the code would look like the
first one with few modifications.
On Jan 10, 1:08 pm, shady sinv...@gmail.com wrote:
Given an array of numbers : a1, a2, a3. an
(a) divide them in such a way that every alternate segment is
given
to
two persons john and mary, equally the number of segments made
should be
minimum...
eg
[algogeeks] Re: MICROSOFT IDC
1) Get count of the nodes in first list, let count be c1. 2) Get count of the nodes in second list, let count be c2. 3) Get the difference of counts d = abs(c1 – c2) 4) Now traverse the bigger list from the first node till d nodes so that from here onwards both the lists have equal no of nodes. 5) Then we can traverse both the lists in parallel till we come across a common node. (Note that getting a common node is done by comparing the address of the nodes) On Jan 12, 3:28 pm, juver++ avpostni...@gmail.com wrote: However, sorting works faster than your straighforward 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.
Re: [algogeeks] google mcqs
I think c) $300
On Wed, Jan 12, 2011 at 3:17 PM, snehal jain learner@gmail.com wrote:
An insurance company issues a policy on a small boat under the following
conditions:
The replacement cost of $5000 will be paid for a total loss. If it is not a
total loss,
but the damage is more than $2000, then $1500 will be paid. Nothing will be
paid for damage costing $2000 or less and of course nothing is paid out if
there
is no damage. The company estimates the probability of the first three
events
as .02, .10, and .30 respectively. The amount the company should charge for
the
policy if it wishes to make a profit of $50 per policy on average is:
a) $250
b) $201
c) $300
d) $1200
On Wed, Jan 12, 2011 at 3:15 PM, snehal jain learner@gmail.comwrote:
A 4-stage pipeline has the stage delays as 150, 120, 160 and 140 ns
(nano seconds)
respectively. Registers that are used between the stages have a delay
of 5 ns each. Assuming
constant clocking rate, the total time taken to process 1000 data
items on this pipeline will
approximately be
a. 120 us (micro seconds)
b. 165 us
c. 180 us
d. 175 us
Which of the following statements are true?
I Shortest remaining time first scheduling may cause starvation
II Preemptive scheduling may cause starvation
III Round robin is better than first come first serve in terms of
response time
a) I only
b) I and III only
c) II and III only
d) I, II and III
Increasing the RAM of a computer typically improves performance
because:
a. Virtual memory increases
b. Larger RAMs are faster
c. Fewer segmentation faults occur
d. Fewer page faults occur
Suppose we want to synchronize two concurrent processes P and Q using
binary
semaphores S and T. The code for the processes P and Q is shown below.
Process P:
while (1) {
W:
print '0’;
print '0';
X:
}
Process Q:
while (1) {
Y:
print '1'
print '1'
Z:
}
Synchronization statements can be inserted only at points W, X, Y and
Z.
V() increments the semaphore, whereas P() decrements it
Which of the following will always lead to an output staring with
'001100110011' ?
a) P(S) at W, V(S) at X, P(T) at Y, V(T) at Z, S and T initially 1
b) P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S initially 1, and T
initially 0
c) P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S and T initially 1
d) P(S) at W, V(S) at X, p(T) at Y, V(T) at Z, S initially 1, and T
initially 0
can any1 suggest some source for such kind of questions
--
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.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Cheers
Naveen Kumar
--
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: Find The Looping Node
you can find explanation of same problem at http://code-forum.blogspot.com/2010/12/loop-in-linked-list.html On Dec 22 2010, 8:41 pm, Saurabh Koar saurabhkoar...@gmail.com wrote: Finding whether a loop exists or not in a linked list, is a very familiar problem.But I want an algorithm that will find the node that is causing the loop. Well,I have an approach.Start from the head.Copy its data into an array.Mark node's data as infinity.Move to the next node.When u find node-next-data=infinity u will say that the current node is causing the loop.Then restore the data of the linked list from the array.But I think more optimized algorithm is possible.Reply if you know more optimized way. -- 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: palindrome
@azhar good solution
Thanks and Regards
Priyaranjan
code-forum.blogspot.com
On Dec 22 2010, 1:55 pm, Azhar Hussain azhar...@gmail.com wrote:
Hi,
Here is the simple solution
unsigned int r = v; // r will be reversed bits of v; first get LSB of v
int s = sizeof(v) * CHAR_BIT - 1; // extra shift needed at end
for (v = 1; v; v = 1)
{
r = 1;
r |= v 1;
s--;
}
r = s; // shift when v's highest bits are zero
if (v == r)
printf(palindrome\n);
else
printf(not a palindrome\n);
source and more optimized
versionshttp://www-graphics.stanford.edu/~seander/bithacks.html#BitReverseObv...
-
Azhar.
On Wed, Dec 22, 2010 at 2:09 PM, pacific pacific pacific4...@gmail.comwrote:
On Wed, Dec 22, 2010 at 12:11 PM, mo...@ismu mohan...@gmail.com wrote:
if x is a 32 bit number
if((x0x)==((x16)0x)))
x's bit pattern is a polyndrome
@snehal :Do you want to consider binary representation of 5 as 101 or
..0101 ?
--
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.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 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: MICROSOFT IDC
@davin this solution will work properly. Thanks and Regards Priyaranjan code-forum.blogspot.com On Jan 12, 3:42 pm, Davin dkthar...@googlemail.com wrote: 1) Get count of the nodes in first list, let count be c1. 2) Get count of the nodes in second list, let count be c2. 3) Get the difference of counts d = abs(c1 – c2) 4) Now traverse the bigger list from the first node till d nodes so that from here onwards both the lists have equal no of nodes. 5) Then we can traverse both the lists in parallel till we come across a common node. (Note that getting a common node is done by comparing the address of the nodes) On Jan 12, 3:28 pm, juver++ avpostni...@gmail.com wrote: However, sorting works faster than your straighforward 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.
Re: [algogeeks] Re: Tejas Networks - Written Test
1.question is not clear if m[i][j] inidicates minimum distance from i to j then m[0][n] is final answer 2. 1st of all if question is asking abt tree u shud think of tree of any degree then for any degree tree make its right child left sibling notation then save inorder and any of one among preorder and post order On Wed, Jan 12, 2011 at 1:47 PM, juver++ avpostni...@gmail.com wrote: You have a general tree. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Aditya Kumar B-tech 3rd year Computer Science Engg. MNNIT, Allahabad. -- 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: MICROSOFT IDC
Justify your algo on examples. -- 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.
Re: [algogeeks] Find The Looping Node
@snehal But it doesn't seem to find the node where loop begins...
On Wed, Dec 22, 2010 at 9:56 PM, snehal jain learner@gmail.com wrote:
@ above
well this a ver old and easy problem.. but unlike u, criticizing others wen
u knw the solution i wud rather post my solution..
int removeCycle(list head)
{
struct listnode * slow, *fast,*slow;
slow=fast=head;
do
{
if(!fast || ! fast-next) rteurn -1;
slow=slow-next;
fast=fast-next-next;
} while(slow!=fast);
slow1=head;
while( slow1!=slow)
{
prev=slow;
slow=slow-next;
slow1=slow1-next;
}
prev-next=null;
return 1;
}
well this is the code for solving ur prob.. but i hv nt attached y this
works.. i hope u ll work out on this.. rather than having spoon feeding..
still if u cant work out, u can ask it.. i would love to answer and explain
to a genius (/ or the person who considers himself genius and the one who
considers others doubts as homework problem and his own doubts as a big
tricky problem although it is too old and common problem :P).
On Wed, Dec 22, 2010 at 9:11 PM, Saurabh Koar saurabhkoar...@gmail.comwrote:
Finding whether a loop exists or not in a linked list, is a very
familiar problem.But I want an algorithm that will find the node that
is causing the loop.
Well,I have an approach.Start from the head.Copy its data into an
array.Mark node's data as infinity.Move to the next node.When u find
node-next-data=infinity u will say that the current node is causing
the loop.Then restore the data of the linked list from the array.But I
think more optimized algorithm is possible.Reply if you know more
optimized way.
--
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.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 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: MICROSOFT IDC
wake up ..L I think original question has asked about intersection (set intersection)...not the node intersection of two linked list. On Jan 12, 4:04 pm, juver++ avpostni...@gmail.com wrote: Justify your algo on examples. -- 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
use rank node http://code-forum.blogspot.com/2010/12/rank-of-node.html#comments Thanks and Regards Priyaranjan code-forum.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: amazon questions
@snehal i think for first question both statement are correct.when you declare const char * cpp then you can not change the value pointed by this pointer(using this variable),however you can change where it was pointing. On Jan 11, 9:58 pm, snehal jain learner@gmail.com wrote: 1. what is valid in cpp char *cp; const char* cpp; 1. cpp=cp 2. cp=cpp 2 there r 3 ppl A B C A can shoot the target 4 out of 5 times B can shoot 6 out of 7 times and C can shoot 8 out of times. 2 people r selected at random. then wat is the probability of hitting the target? -- 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: amazon questions
@snehal i think for first question both statement are correct.when you declare const char * cpp then you can not change the value pointed by this pointer(using this variable),however you can change where it was pointing. Thanks and Regards Priyaranjan code-forum.blogspot.com On Jan 11, 9:58 pm, snehal jain learner@gmail.com wrote: 1. what is valid in cpp char *cp; const char* cpp; 1. cpp=cp 2. cp=cpp 2 there r 3 ppl A B C A can shoot the target 4 out of 5 times B can shoot 6 out of 7 times and C can shoot 8 out of times. 2 people r selected at random. then wat is the probability of hitting the target? -- 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: MICROSOFT IDC
@manoj, Can you please explain question about your understanding? On Jan 12, 4:19 pm, manoj manoj.lala...@gmail.com wrote: wake up ..L I think original question has asked about intersection (set intersection)...not the node intersection of two linked list. On Jan 12, 4:04 pm, juver++ avpostni...@gmail.com wrote: Justify your algo on examples. -- 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: MICROSOFT IDC
my understanding of question when I have given solution... list1 = 4--2--3--6 list2 = 5--7--2--3 output should be: 2,3 other understand of this question on which davin has given solution is.. two linked list froming Y and find intersecting node or find if they are intersecting or not. On Jan 12, 5:05 pm, Davin dkthar...@googlemail.com wrote: @manoj, Can you please explain question about your understanding? On Jan 12, 4:19 pm, manoj manoj.lala...@gmail.com wrote: wake up ..L I think original question has asked about intersection (set intersection)...not the node intersection of two linked list. On Jan 12, 4:04 pm, juver++ avpostni...@gmail.com wrote: Justify your algo on examples. -- 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.
Re: [algogeeks] Re: MICROSOFT IDC
@manoj we need to find a common node, not nodes in list having same values how a node can be pointing to 2 next values at the same time as in your case 3 is pointing to both null and 6, I think On Wed, Jan 12, 2011 at 5:44 PM, manoj manoj.lala...@gmail.com wrote: my understanding of question when I have given solution... list1 = 4--2--3--6 list2 = 5--7--2--3 output should be: 2,3 other understand of this question on which davin has given solution is.. two linked list froming Y and find intersecting node or find if they are intersecting or not. On Jan 12, 5:05 pm, Davin dkthar...@googlemail.com wrote: @manoj, Can you please explain question about your understanding? On Jan 12, 4:19 pm, manoj manoj.lala...@gmail.com wrote: wake up ..L I think original question has asked about intersection (set intersection)...not the node intersection of two linked list. On Jan 12, 4:04 pm, juver++ avpostni...@gmail.com wrote: Justify your algo on examples. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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: MICROSOFT IDC
coool hai... On Jan 12, 5:18 pm, sunny agrawal sunny816.i...@gmail.com wrote: @manoj we need to find a common node, not nodes in list having same values how a node can be pointing to 2 next values at the same time as in your case 3 is pointing to both null and 6, I think On Wed, Jan 12, 2011 at 5:44 PM, manoj manoj.lala...@gmail.com wrote: my understanding of question when I have given solution... list1 = 4--2--3--6 list2 = 5--7--2--3 output should be: 2,3 other understand of this question on which davin has given solution is.. two linked list froming Y and find intersecting node or find if they are intersecting or not. On Jan 12, 5:05 pm, Davin dkthar...@googlemail.com wrote: @manoj, Can you please explain question about your understanding? On Jan 12, 4:19 pm, manoj manoj.lala...@gmail.com wrote: wake up ..L I think original question has asked about intersection (set intersection)...not the node intersection of two linked list. On Jan 12, 4:04 pm, juver++ avpostni...@gmail.com wrote: Justify your algo on examples. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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.
Re: [algogeeks] Re: MICROSOFT IDC
I think problem is about to find the intersection of lists as for sets. So work with values. It is a nonsense if the lists are intersected with their nodes. -- 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.
Re: [algogeeks] Re: MICROSOFT IDC
@Sunny your are wrong definetely. If some lists has intersections in a nodes, than it is not a list as a data structure. -- 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: Amazon Analytical Puzzle
2nd puzzle You have a birthday cake and have exactly 3 slices to cut it into 8 equal pieces. How do you do 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: Amazon Analytical Puzzle
3rd Puzzle There are three boxes, one contains only apples, one contains only oranges, and one contains both apples and oranges. The boxes have been incorrectly labeled such that no label identifies the actual contents of the box it labels. Opening just one box, and without looking in the box, you take out one piece of fruit. By looking at the fruit, how can you immediately label all of the boxes correctly? 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] Amazon Again
How will you raise a n x n matrix to the power k efficiently. What's the time complexity and space complexity of you algorithm? How will you optimize this? Thanks Regards Shashank Don't b Evil U Can Earn While U Learn -- 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.
Re: [algogeeks] Amazon Again
Using Matrix Exponentiation technique Complexity is n^3*(lg n) for matrix n x n we need two n x n matrix to raise the matrix to power K .. Correct me if am wronf On Wed, Jan 12, 2011 at 6:28 PM, bittu shashank7andr...@gmail.com wrote: How will you raise a n x n matrix to the power k efficiently. What's the time complexity and space complexity of you algorithm? How will you optimize this? Thanks Regards Shashank Don't b Evil U Can Earn While U Learn -- 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. -- 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: Amazon Analytical Puzzle
One solution - make two orthogonal cuts, then you have 4 pieces. Then make one parallel cut to the bottom of the cake, and at the height = H / 2, where H - height of the cake. ))). -- 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: No. of ways to Merge 2 arrays
Let A(m,n) = the number of ways two sorted arrays of size m and n can be merged. Then A satisfies the recurrence A(m,n) = A(m-1,n) + A(m,n-1) A(m,0) = 1 A(0,n) = 1 The solution is A(m,n) = (m+n) choose m, the binomial coefficient. If m = n = N, then A(N,N) = 2N choose N. Dave On Jan 12, 3:23 am, Arindam Chatterjee arindam.chatterje...@gmail.com wrote: Can anyone help: *In how many ways can 2 sorted arrays of combined size N be merged?* -- Thanks and regards, ARINDAM CHATTERJEE, Mtech Second Year, Department of Computer Science and Engineering, IIT Bombay, Powai, Mumbai-400076 Contacts : +919022313724 Living is about making tomorrow better than today !! -- 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: Amazon Analytical Puzzle
i think 1st Make 1 Horizontal Cut then 1Vertical Cut these 2 Cut can be done in reverse order finally now we have 4 piece of cake arrange these 4 piece in to an one Queue then make a horizontal cut that goes from center of all the above 4 piece of cake we have done Thanks Regards Shashank Mani Don't B evil U Can Earn While U Can Learn -- 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: Amazon Analytical Puzzle
Cut the cake into quarters with two cuts as usual. Stack the quarters up and cut through them all with the third cut. Dave On Jan 12, 6:44 am, bittu shashank7andr...@gmail.com wrote: 2nd puzzle You have a birthday cake and have exactly 3 slices to cut it into 8 equal pieces. How do you do 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: Amazon Analytical Puzzle
Open the box labeled apples and oranges and inspect one piece of fruit. Say that it is an apple. Then label this box apples since it cannot be apples and oranges or oranges. To identify the boxes that should be labeled oranges and apples and oranges, realize that since the remaining boxes are mislabeled, the one labeled oranges cannot contain only oranges, so it must be apples and oranges. And the last box is oranges. Deal with discovering an orange in the first box in a similar way. Dave On Jan 12, 6:52 am, bittu shashank7andr...@gmail.com wrote: 3rd Puzzle There are three boxes, one contains only apples, one contains only oranges, and one contains both apples and oranges. The boxes have been incorrectly labeled such that no label identifies the actual contents of the box it labels. Opening just one box, and without looking in the box, you take out one piece of fruit. By looking at the fruit, how can you immediately label all of the boxes correctly? 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.
Re: [algogeeks] Re: Amazon Analytical Puzzle
@Dave: gud one :) On Wed, Jan 12, 2011 at 7:48 PM, Dave dave_and_da...@juno.com wrote: Open the box labeled apples and oranges and inspect one piece of fruit. Say that it is an apple. Then label this box apples since it cannot be apples and oranges or oranges. To identify the boxes that should be labeled oranges and apples and oranges, realize that since the remaining boxes are mislabeled, the one labeled oranges cannot contain only oranges, so it must be apples and oranges. And the last box is oranges. Deal with discovering an orange in the first box in a similar way. Dave On Jan 12, 6:52 am, bittu shashank7andr...@gmail.com wrote: 3rd Puzzle There are three boxes, one contains only apples, one contains only oranges, and one contains both apples and oranges. The boxes have been incorrectly labeled such that no label identifies the actual contents of the box it labels. Opening just one box, and without looking in the box, you take out one piece of fruit. By looking at the fruit, how can you immediately label all of the boxes correctly? 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- best wishes!! Vaibhav Shukla DU-MCA -- 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.
Re: [algogeeks] Re: Google Question: Find kth largest of sum of elements in 2 array
this will not work out
a[0]b[0] doesn't mean that a[0]+b[i] is ith largest sum
try
int a[]={10,8,6,4,1};
int b[]={9,6,3,2,1};
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Oct 6, 2010 at 11:36 PM, ligerdave david.c...@gmail.com wrote:
use pointers and lengths of two arrays. depends on what K is, if K
m*n/2, you reverse the pointers. therefore, the worst case is either
O(m) when length of m is shorter or O(n) when length of n is
shorter,
make the pointers pointing to the first elements in both arrays.
A)
4,3,2,2,1
^
B)
5,3,2,1
^
compare them to find out which one is larger, here 5 is larger than 4.
by definition, you know 5 would be bigger than any elements in array
A, and sum of 5 with kth element of array A (here, kth = A.length)
will be the one(kth largest sum(a+b) overall) you are looking for.
if kA.length, shift the pointer of B one number to the right and
repeat the same process.
like i said, if the k m*n/2, start from small
On Oct 6, 6:34 am, sourav souravs...@gmail.com wrote:
you are given 2 arrays sorted in decreasing order of size m and n
respectively.
Input: a number k = m*n and = 1
Output: the kth largest sum(a+b) possible. where
a (any element from array 1)
b (any element from array 2)
The Brute force approach will take O(n*n). can anyone find a better
logic. thnkx in advance.
--
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.comalgogeeks%2bunsubscr...@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 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.
Re: [algogeeks] Re: Amazon Interview - Algorithms
doesn't greedy approach work here ? On Sun, Jan 9, 2011 at 8:00 PM, juver++ avpostni...@gmail.com wrote: It doesn't matter how to make transitions: from current position make all necessary moves, or determine all positions from which we can achieve i-th position. So your method is only the one of possible. -- 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.comalgogeeks%2bunsubscr...@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 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.
Re: [algogeeks] BT
Here is my pseudo code :
check( node t1 , node t2 )
{
if ( t1-data == t2-data)
{
return check( t1-left , t2-left ) check(t1-right, t2-right) ;
}
else
{
return check(t1-left , t2) || check(t1-right , t2);
}
}
time complexity : o(n) because each node in t1 needs to be visited once.let
me know if this works.
On Sun, Jan 9, 2011 at 1:30 PM, Harshal hc4...@gmail.com wrote:
@Nishaanth
T1 has millions of nodes. Suppose all the nodes of T1 are equal to root of
T2. Then u will have to check every where in T1. Putting height as
constraint, u will have to check only those nodes whose height is equal to
T2. It will reduce time complexity.
Well m not able to think of better time complexity, another way would be:
Find Height of T2 ... O(k) //k is no. of nodes in T2
Find Height of each node in T1... O(N) //N is no. of nodes in T1
now if p nodes in T1 have height same as T2, then we can find if a subtree
rooted at any of those p nodes are identical to T2 in O(pk) time.
Thus total time complexity: O(N) + O(k) + O(pk).
correct me if I am wrong..
--
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.comalgogeeks%2bunsubscr...@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 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.
Re: [algogeeks] [Athena 2011]
didn't get your question dude On Wed, Jan 12, 2011 at 10:39 PM, Pratik Bhadkoliya pkbhadkol...@gmail.comwrote: (a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z) is an ordered list of positive integers Let magic(value) denote the number of such ordered lists that exist such that gcd(a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z)=1 AND max(a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z)=value Find the divisors of 11(18 -digits) . For each of the divisors D , compute magic(D) . Find the last 8 digits of the sum of all the magic(D) computed . -- 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.comalgogeeks%2bunsubscr...@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 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.
Re: [algogeeks] Re: MICROSOFT IDC
Hi all Its about set intersection. @Davin predicted the problem wrongly. So,sorting gives the best performance. -- 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.
Re: [algogeeks] Re: Amazon Interview - Algorithms
No, there is a counterexample fot the greedy. -- 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.
Re: [algogeeks] Re: MICROSOFT IDC
Hi all Its about set intersection. @Davin predicted the problem wrongly. So,sorting gives the best performance. -- 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.
Re: [algogeeks] BT
It seems to be incorrect. try to implement it and run on a sample input data. -- 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] scales - binary search spoj
https://www.spoj.pl/problems/SCALE/ hi guys.. need tips on solving this problem i thought as follows: search the immediately largest weight to the given number in the series of powers of three(log n) then do bit wise checking to find the set bit (after introducing the given weight in a proper place in the series till the no found in the above step) logic similar to find the subset sum using set bits... http://www.codechef.com/wiki/tutorial-paying now if u analyse the sum generated sums.. not more than 2 cases will have the same sum one denotes the left pan and the other denotes the right pan this worked with test cases i checked... help me out.. thanks guys.. :-) -- 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: 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.
Re: [algogeeks] scales - binary search spoj
searching the immediately largest can fail i think but depends how u handeled as in case of 11 , immediately larger is 27 but it can be handled using 1,3,9 only as 9+3-1 so what is needed is find min i such that for 0-i sum of 3^i's is greater than X On Wed, Jan 12, 2011 at 11:42 PM, muthu valliappan muthuvvalliap...@gmail.com wrote: https://www.spoj.pl/problems/SCALE/ hi guys.. need tips on solving this problem i thought as follows: search the immediately largest weight to the given number in the series of powers of three(log n) then do bit wise checking to find the set bit (after introducing the given weight in a proper place in the series till the no found in the above step) logic similar to find the subset sum using set bits... http://www.codechef.com/wiki/tutorial-paying now if u analyse the sum generated sums.. not more than 2 cases will have the same sum one denotes the left pan and the other denotes the right pan this worked with test cases i checked... help me out.. thanks guys.. :-) -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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: Amazon Again
I think you meant n^3*log(K). Multiplication on two matrices would take O(n) per entry. And total #entries is n*n, thus multiplying 2 matrices takes O(n^3) To get a^(K), use simple divide-and-conquer technique. Since once one gets a^(K/2), to get a^(K) only needs to square it. Now we get T(K) = T(K/2)+O(multiply)---T(K) = logK*O(multiply) = n^3*logK. On Jan 12, 8:04 am, radha krishnan radhakrishnance...@gmail.com wrote: Using Matrix Exponentiation technique Complexity is n^3*(lg n) for matrix n x n we need two n x n matrix to raise the matrix to power K .. Correct me if am wronf On Wed, Jan 12, 2011 at 6:28 PM, bittu shashank7andr...@gmail.com wrote: How will you raise a n x n matrix to the power k efficiently. What's the time complexity and space complexity of you algorithm? How will you optimize this? Thanks Regards Shashank Don't b Evil U Can Earn While U Learn -- 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 athttp://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 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.
Re: [algogeeks] Re: MICROSOFT IDC
SO .. u guys propose that 'sorting' is an O(1) space ? Won't the sorting algo swap elements of the list so making it a O(n) space algo ? (Just proposing :) ) Programmers should realize their critical importance and responsibility in a world gone digital. They are in many ways similar to the priests and monks of Europe's Dark Ages; they are the only ones with the training and insight to read and interpret the scripture of this age. On Wed, Jan 12, 2011 at 11:16 PM, aniket chatterjee aniket...@gmail.comwrote: Hi all Its about set intersection. @Davin predicted the problem wrongly. So,sorting gives the best performance. -- 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.comalgogeeks%2bunsubscr...@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 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.
Re: [algogeeks] Re: Amazon Again
@jammy: Sorry for wrong answer thats O(n^3 *lg(K)) On Thu, Jan 13, 2011 at 12:28 AM, Jammy xujiayiy...@gmail.com wrote: I think you meant n^3*log(K). Multiplication on two matrices would take O(n) per entry. And total #entries is n*n, thus multiplying 2 matrices takes O(n^3) To get a^(K), use simple divide-and-conquer technique. Since once one gets a^(K/2), to get a^(K) only needs to square it. Now we get T(K) = T(K/2)+O(multiply)---T(K) = logK*O(multiply) = n^3*logK. On Jan 12, 8:04 am, radha krishnan radhakrishnance...@gmail.com wrote: Using Matrix Exponentiation technique Complexity is n^3*(lg n) for matrix n x n we need two n x n matrix to raise the matrix to power K .. Correct me if am wronf On Wed, Jan 12, 2011 at 6:28 PM, bittu shashank7andr...@gmail.com wrote: How will you raise a n x n matrix to the power k efficiently. What's the time complexity and space complexity of you algorithm? How will you optimize this? Thanks Regards Shashank Don't b Evil U Can Earn While U Learn -- 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 athttp://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 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. -- 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.
Re: [algogeeks] Re: MICROSOFT IDC
Merging lists can be done using O(1) extra space, inplace. -- 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.
Re: [algogeeks] Re: MICROSOFT IDC
Sure, I raised concern about 'sorting'. Programmers should realize their critical importance and responsibility in a world gone digital. They are in many ways similar to the priests and monks of Europe's Dark Ages; they are the only ones with the training and insight to read and interpret the scripture of this age. On Thu, Jan 13, 2011 at 1:05 AM, juver++ avpostni...@gmail.com wrote: Merging lists can be done using O(1) extra space, inplace. -- 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.comalgogeeks%2bunsubscr...@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 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.
Re: [algogeeks] Re: SUMMER INTERNSHIP
can anyone tell me how to apply for iit nlp project On Mon, Jan 10, 2011 at 10:28 PM, cr.a...@gmail.com cr.a...@gmail.comwrote: Dept of EE at IISc: http://www.ee.iisc.ernet.in/internship.html http://www.ee.iisc.ernet.in/internship.htmlDept. of CSA should have their's soon Anil On Mon, Jan 10, 2011 at 7:26 PM, Aviral Gupta aviral@gmail.comwrote: 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.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 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.
Re: [algogeeks] Re: SUMMER INTERNSHIP
and about any other such projects of iit On Thu, Jan 13, 2011 at 2:29 AM, abhishesh srivastava abhishesh.srivast...@gmail.com wrote: can anyone tell me how to apply for iit nlp project On Mon, Jan 10, 2011 at 10:28 PM, cr.a...@gmail.com cr.a...@gmail.comwrote: Dept of EE at IISc: http://www.ee.iisc.ernet.in/internship.html http://www.ee.iisc.ernet.in/internship.htmlDept. of CSA should have their's soon Anil On Mon, Jan 10, 2011 at 7:26 PM, Aviral Gupta aviral@gmail.comwrote: 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.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 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.
Re: [algogeeks] Re: Amazon Interview - Algorithms
@juver++ : what is the greedy approach one could take here? I know it would
be wrong, but I tried to come up with a test case for greedy failure, but
realized the greedy policy here will be equivalent to the dp.
@Decipher: your's seems to be a O(n^2) solution. Here in the O(n) version of
it.
#includestdio.h
#includestdlib.h
#define MAX 0x7fff
inline int min(int a, int b) {
return a = b ? b : a;
}
int find_min_steps(int const * const input, const int n) {
int min_steps_dp[n], i, temp, next_vacant;
for (i = 0; i n; min_steps_dp[i++] = MAX);
min_steps_dp[0] = 0;
next_vacant = 1; // Is the index in the array whose min_steps needs to be
updated
// in the next iteration.
for (i = 0; i n min_steps_dp[n - 1] == MAX; i++) {
temp = i + input[i];
if (temp = n) {
min_steps_dp[n - 1] = min(min_steps_dp[n - 1], min_steps_dp[i] + 1);
temp = n - 1;
} else {
min_steps_dp[temp] = min(min_steps_dp[temp], min_steps_dp[i] + 1);
}
if (temp next_vacant) {
// this loop executes only ONCE for each element in the array, so over
the
// course of execution, is an O(n) loop only. The order of the outer
loop still
// remains O(n).
for (; next_vacant temp; next_vacant++) {
min_steps_dp[next_vacant]
= min(min_steps_dp[temp], min_steps_dp[next_vacant]);
}
}
}
for (i=0;in;printf(%d ,min_steps_dp[i++]));printf(\n);
return min_steps_dp[n-1];
}
int main() {
int n, *input, i;
scanf(%d,n);
if ((input = (int *)malloc(n * sizeof(int))) == NULL) {
return -1;
}
for (i = 0;i n; scanf(%d,input[i++]));
printf(Minimum steps: %d\n,find_min_steps(input, n));
return 0;
}
Programmers should realize their critical importance and responsibility in a
world gone digital. They are in many ways similar to the priests and monks
of Europe's Dark Ages; they are the only ones with the training and insight
to read and interpret the scripture of this age.
On Wed, Jan 12, 2011 at 11:27 PM, juver++ avpostni...@gmail.com wrote:
No, there is a counterexample fot the greedy.
--
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.comalgogeeks%2bunsubscr...@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 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.
Re: [algogeeks] google paper/...plz help..its urgent
On Wed, Jan 12, 2011 at 1:14 AM, snehal jain learner@gmail.com wrote:
1. Quick-sort is run on two inputs shown below to sort in ascending
order
(i) 1,2,3, ….,n
(ii) n, n - 1, n - 2, …., 2, 1
Let C1 and C2 be the number of comparisons made for the inputs (i) and
(ii) respectively. Then,
a) C1 C2
b) C1 C2
c) C1 = C2
Answer is c
http://codepad.org/8xpqfGwJ
d) We cannot say anything for arbitrary n
2. Which of the following languages over {0, 1} is regular?
a) 0i1j such that i ≤ j
b) 0iw1j such that w ∈ {0, 1}∗ and i ≥ 0
c) All strings of 0s and 1s such that every pth character is 0 where p
is prime
d) None of the above
3. We are given a set X = {x1, x2, ..., xn} where xi = 2i. A sample S
(which is a subset of X) is
drawn by selecting each xi independently with probability pi = 1 / 2.
The expected value of the
smallest number in sample S is:
a) 1 / n
b) 2
c) sqrt(n)
d) n
4. Let S be an NP-complete problem and Q and R be two other problems
not known to be in
NP. Q is polynomial time reducible to S and S is polynomial-time
reducible to R. Which one of
the following statements is true?
a) R is NP-complete
b) R is NP-hard
c) Q is NP-complete
d) Q is NP-hard
5. For any string s ∈ (0 + 1)*, let d(s) denote the decimal value of s
(eg: d(101) = 5, d(011) = 3).
Let L = {s ∈ (0+1)* | d(s) mod 5 = 2 and d(s) mod 7 = 4}. Which of the
following statements is
true?
a) L is recursively enumerable, but not recursive
b) L is is recursive, but not context-free
c) L is context-free, but not regular
d) L is regular
Common data for questions 6 and 7
The 2n vertices of a graph G corresponds to all subsets of a set of
size n. Two vertices of G are
adjacent if and only if the corresponding sets intersect in exactly 2
elements
6. The number of vertices of degree zero in G is:
a) 1
b) n
c) 2n - 1
d) None
7. The number of connected components in G is:
a) 2n
b) n + 2
c) n C 2
d) None
8. There are 5 nested loops written as follows,
int counter = 0;
for (int loop_1=0; loop_1 10; loop_1++) {
for (int loop_2=loop_1 + 1; loop_2 10; loop_2++) {
for (int loop_3=loop_2 + 1; loop_3 10; loop_3++) {
for (int loop_4=loop_3 + 1; loop_4 10; loop_4++) {
for (int loop_5=loop_4 + 1; loop_5 10; loop_5++) {
counter++;
}
}
}
}
}
What will be the value of counter in the end (after all the loops
finished running)?
a) 15C5
b) 14C5
c) 10C5
d) 10 * 9 * 8 * 7 * 6 * 5
Answer is D
--
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.comalgogeeks%2bunsubscr...@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 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: [Athena 2011]
For example, for 1: divisor is only 1 so, answer is magic(1) = 1 [since (1,1,1,1,1,...,1,1) is the only list possible.] for 2: divisors are 1 and 2 answer is [magic(1) + magic(2)] % 10^8 for 3: answer is [magic(1) + magic(3)] % 10^8 for 4: answer is [magic(1) + magic(2) + magic(4)] % 10^8 by ordered list means : (1,1,1,1,1,1,2) is different from (1,1,1,1,1,,2,1).. that is order of all integers in the list is important. some starting values of magic function magic(1) = 1 magic(2) = 67108862 magic(3) = 2541798719464 magic(4) = 4501057694433304 magic(5) = 1485612519757395128 magic(6) = 169091609518327614304 On Jan 12, 10:23 pm, ashish agarwal ashish.cooldude...@gmail.com wrote: didn't get your question dude On Wed, Jan 12, 2011 at 10:39 PM, Pratik Bhadkoliya pkbhadkol...@gmail.comwrote: (a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z) is an ordered list of positive integers Let magic(value) denote the number of such ordered lists that exist such that gcd(a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z)=1 AND max(a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z)=value Find the divisors of 11(18 -digits) . For each of the divisors D , compute magic(D) . Find the last 8 digits of the sum of all the magic(D) computed . -- 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.comalgogeeks%2bunsubscr...@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 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] tic-tac-toe in a distributed environment
1) write a program to play tic-tac-toe in a distributed environment.The two players will be playing from different machines.. 2)write a program for real time video broadcasting by using RTP protocol? could u help me by sending the codes of any of those problem? -- 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 email%3adipan...@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.
[algogeeks] Sort string based upon the count of characters
Smaple Data : input : abcdacdc Output : cadb If the count is same for characters. maintain the original order of the characters from input string. Please do let me know for any clarification. -- 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] Sort string based upon the count of characters
we can use the count sort array in this to count the frequencies of character (array size would be fixed 26) and sort that counting array by again count sort or quick sort in decrsaing order and than print the valur in ascci format '97+i'. On Thu, Jan 13, 2011 at 11:53 AM, Davin dkthar...@googlemail.com wrote: Smaple Data : input : abcdacdc Output : cadb If the count is same for characters. maintain the original order of the characters from input string. Please do let me know for any clarification. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- SOURABH JAKHAR,(CSE)(3 year) ROOM NO 167 , TILAK,HOSTEL 'MNNIT ALLAHABAD The Law of Win says, Let's not do it your way or my way; let's do it the best way. -- 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] google paper/...plz help..its urgent
for second question answer is b
On Thu, Jan 13, 2011 at 4:41 AM, Anand anandut2...@gmail.com wrote:
On Wed, Jan 12, 2011 at 1:14 AM, snehal jain learner@gmail.comwrote:
1. Quick-sort is run on two inputs shown below to sort in ascending
order
(i) 1,2,3, ….,n
(ii) n, n - 1, n - 2, …., 2, 1
Let C1 and C2 be the number of comparisons made for the inputs (i) and
(ii) respectively. Then,
a) C1 C2
b) C1 C2
c) C1 = C2
Answer is c
http://codepad.org/8xpqfGwJ
d) We cannot say anything for arbitrary n
2. Which of the following languages over {0, 1} is regular?
a) 0i1j such that i ≤ j
b) 0iw1j such that w ∈ {0, 1}∗ and i ≥ 0
c) All strings of 0s and 1s such that every pth character is 0 where p
is prime
d) None of the above
3. We are given a set X = {x1, x2, ..., xn} where xi = 2i. A sample S
(which is a subset of X) is
drawn by selecting each xi independently with probability pi = 1 / 2.
The expected value of the
smallest number in sample S is:
a) 1 / n
b) 2
c) sqrt(n)
d) n
4. Let S be an NP-complete problem and Q and R be two other problems
not known to be in
NP. Q is polynomial time reducible to S and S is polynomial-time
reducible to R. Which one of
the following statements is true?
a) R is NP-complete
b) R is NP-hard
c) Q is NP-complete
d) Q is NP-hard
5. For any string s ∈ (0 + 1)*, let d(s) denote the decimal value of s
(eg: d(101) = 5, d(011) = 3).
Let L = {s ∈ (0+1)* | d(s) mod 5 = 2 and d(s) mod 7 = 4}. Which of the
following statements is
true?
a) L is recursively enumerable, but not recursive
b) L is is recursive, but not context-free
c) L is context-free, but not regular
d) L is regular
Common data for questions 6 and 7
The 2n vertices of a graph G corresponds to all subsets of a set of
size n. Two vertices of G are
adjacent if and only if the corresponding sets intersect in exactly 2
elements
6. The number of vertices of degree zero in G is:
a) 1
b) n
c) 2n - 1
d) None
7. The number of connected components in G is:
a) 2n
b) n + 2
c) n C 2
d) None
8. There are 5 nested loops written as follows,
int counter = 0;
for (int loop_1=0; loop_1 10; loop_1++) {
for (int loop_2=loop_1 + 1; loop_2 10; loop_2++) {
for (int loop_3=loop_2 + 1; loop_3 10; loop_3++) {
for (int loop_4=loop_3 + 1; loop_4 10; loop_4++) {
for (int loop_5=loop_4 + 1; loop_5 10; loop_5++) {
counter++;
}
}
}
}
}
What will be the value of counter in the end (after all the loops
finished running)?
a) 15C5
b) 14C5
c) 10C5
d) 10 * 9 * 8 * 7 * 6 * 5
Answer is D
--
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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
SOURABH JAKHAR,(CSE)(3 year)
ROOM NO 167 ,
TILAK,HOSTEL
'MNNIT ALLAHABAD
The Law of Win says, Let's not do it your way or my way; let's do it the
best way.
--
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] Sort string based upon the count of characters
we can also the concept of HASHING to count the frequency of each character . On Thu, Jan 13, 2011 at 11:53 AM, Davin dkthar...@googlemail.com wrote: Smaple Data : input : abcdacdc Output : cadb If the count is same for characters. maintain the original order of the characters from input string. Please do let me know for any clarification. -- 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.comalgogeeks%2bunsubscr...@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.
