[algogeeks] Google Interview Question
Boolean tree problem: Each leaf node has a boolean value associated with it, 1 or 0. In addition, each interior node has either an AND or an OR gate associated with it. The value of an AND gate node is given by the logical AND of its two children's values. The value of an OR gate likewise is given by the logical OR of its two children's values. The value of all of the leaf nodes will be given as input so that the value of all nodes can be calculated up the tree. It's easy to find the actual value at the root using level order traversal and a stack(internal if used recursion). Given V as the desired result i.e we want the value calculated at the root to be V(0 or 1) what is the minimum number of gates flip i.e. AND to OR or OR to AND be required at internal nodes to achieve that? Also for each internal node you have boolean associated which tells whether the node can be flipped or not. You are not supposed to flip a non flippable internal node. Regards Shashank Mani Narayan BIT Mesra -- 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] SUN Microsystem Question
You Have File of Containing 1 Million Integers You need To Find 10 Maximum Integer Out of Them.How You Will Do That ...what is Time space Complexcity of Algorithm that you will usethen optrmize the solution.. Constraints- U can't Store Whole File in memory @ one time e.g. if u will do that gigabyt eof memory may be reuqired so that should be avoided. Regards Shashank Mani Narayan Birla Instute of Technology,Mesra -- 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 interview question
Given a boolean matrix with all the true elements on left side in the row so that each row can be broken into two parts left part containing only true elements and right part containing only false elements. Find the row with max number of true elements in it. 00011 0 1 true is 0 false is 1 .. so we will say 2nd row has maximum 1 -- thanks --mac -- 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 interview question
updated :) Given a boolean matrix with all the true elements on left side in the row so that each row can be broken into two parts left part containing only true elements and right part containing only false elements. Find the row with max number of true elements in it. 00011 0 1 true is 0 false is 1 .. so we will say 2nd row has maximum 1 and 3rd row has mximum 0 -- thanks --mac -- thanks --mac -- 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 Interview Question
Using the same level order traversal (bottom up), calculating the minimum flips to turn each internal node to given value (0/1). On 2010-12-24 17:19, bittu wrote: Boolean tree problem: Each leaf node has a boolean value associated with it, 1 or 0. In addition, each interior node has either an AND or an OR gate associated with it. The value of an AND gate node is given by the logical AND of its two children's values. The value of an OR gate likewise is given by the logical OR of its two children's values. The value of all of the leaf nodes will be given as input so that the value of all nodes can be calculated up the tree. It's easy to find the actual value at the root using level order traversal and a stack(internal if used recursion). Given V as the desired result i.e we want the value calculated at the root to be V(0 or 1) what is the minimum number of gates flip i.e. AND to OR or OR to AND be required at internal nodes to achieve that? Also for each internal node you have boolean associated which tells whether the node can be flipped or not. You are not supposed to flip a non flippable internal node. Regards Shashank Mani Narayan BIT Mesra -- 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: Array Ranking Problem
My method is using DP, as Snehal have pointed out.
Suppose S[0..n-1] and T[0..n-1] denotes the score and time for the n
questions respectively.
C[k][s] denotes the maximum total time when choosing from the first k
questions such that the total score do not exceed s.
Then C[0][s] = 0
C[k][s] = max(C[k-1][s], C[k-1][s-S[k-1]]+T[k-1]), s=S[k-1]
= C[k-1][s], sS[k-1]
Suppose the total score/time of all problem is SS/ST and the passing
score is PS
then the answer is (TS - C[n][SS-PS]).
The time complexity is O(n*(SS-PS)).
Actually the 0/1 knapsack problem is a NP-complete problem, and only
have pseudo-polynomial time algorithm, or polynomial time greedy
approximation algorithm.
Refer to http://en.wikipedia.org/wiki/Knapsack_problem#0-1_knapsack_problem
On 2010-12-24 14:00, Ankur Khurana wrote:
how will you choose that ?? without sorting . can you please mention
what method you intend to use to achieve that purpose ?
On Fri, Dec 24, 2010 at 8:16 AM, Terencetechnic@gmail.com wrote:
@Ankur:
It is just 0/1 knapsack problem:
Choose a subset of the questions with sum of scores not exceeding (Total
Score - Pass Score), while maximize the sum of time of the subset.
So I do not think O(nlogn) greedy algorithm will solve this problem.
On 2010-12-23 23:38, Ankur Khurana wrote:
it is just like 0/1 knapsack problem with maximum weight of knapsack
as 40. but in this case that is minimum that we have to calculate.
calculate marks/time for every element . then try finding the elements
with max value/time to fulfill the quota of marks. i dont know if this
can be done in O(n) but it can be certainly done in nlogn. any other
views ?
On Thu, Dec 23, 2010 at 9:03 PM, Davindkthar...@googlemail.comwrote:
Thanks for reply. I am looking for O(n) for solution.
Davin
On Dec 23, 8:29 pm, snehal jainlearner@gmail.comwrote:
hint : use dp
On Thu, Dec 23, 2010 at 8:30 PM, Davindkthar...@googlemail.comwrote:
Marks for Questions(1,6): {10,15,20,25,10,20}
Time for Each Questions(1,6) : { 2, 4,3,4, 2,4}
Passing Marks : 40 Out of 100
Find Questions with minimum time to pass the exam?
On Dec 23, 7:04 pm, juver++avpostni...@gmail.comwrote:
Please clarify the problem statement. Provide example.
From the first view problem seems to be unclear.
--
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.
--
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] SUN Microsystem Question
use B-trees On Fri, Dec 24, 2010 at 6:32 PM, bittu shashank7andr...@gmail.com wrote: You Have File of Containing 1 Million Integers You need To Find 10 Maximum Integer Out of Them.How You Will Do That ...what is Time space Complexcity of Algorithm that you will usethen optrmize the solution.. Constraints- U can't Store Whole File in memory @ one time e.g. if u will do that gigabyt eof memory may be reuqired so that should be avoided. Regards Shashank Mani Narayan Birla Instute of Technology,Mesra -- 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] SUN Microsystem Question
On Fri, Dec 24, 2010 at 3:02 PM, bittu shashank7andr...@gmail.com wrote: You Have File of Containing 1 Million Integers You need To Find 10 Maximum Integer Out of Them.How You Will Do That ...what is Time space Complexcity of Algorithm that you will usethen optrmize the solution.. Constraints- U can't Store Whole File in memory @ one time e.g. if u will do that gigabyt eof memory may be required so that should be avoided. Regards Shashank Mani Narayan Birla Instute of Technology,Mesra -- 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. Use External sorting. Divide the file data into smaller chunks. Sort the chunks of data one at a time and save them back to file. Then get top values from the chunks and sort them again till you get top 10 values. -- Dinesh Bansal 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 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: Simulation algo
I don't think Ant-Colony-Optimization is related to Discrete Event Simulation. If you are looking for a framework to model DES, you may have look at SimPy http://simpy.sourceforge.net/ Cheers, Pierre On 24 déc, 04:29, Chi i...@chihoang.de wrote: Ant-Colony-Optimization - Ursprüngliche Mitteilung - Hello, I'm looking for an algorithm of computer science simulation and specifically the discrete simulation of any model. Please All the best. -- 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.
[algogeeks] good question
Given a boolean matrix with all the true elements on left side in the row so that each row can be broken into two parts left part containing only true elements and right part containing only false elements. Find the row with max number of true elements in it. if the size of matrix is m*n then it can be solved in O(m+n) time. Any bettar 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 Question
You have been given a Two Dimensional Array and One Dimensional Array.. You have to return true if 2D array consists of given 1D Array… 2D array Consists of 1D array means all the elements of 1d are present contiguously in left side, right side ,in up or in down directions in 2d array.. 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 interview question
O(m+n). Search from rightmost top corner. Count the no of zero from right and go to left, i.e. traverse through columns from right of the first row. When you find a column having 0, go down to lower row. Check the correspondent column is 1 or not. If it is, follow the above step or else go down to next lower row. On 24 December 2010 16:02, MAC macatad...@gmail.com wrote: updated :) Given a boolean matrix with all the true elements on left side in the row so that each row can be broken into two parts left part containing only true elements and right part containing only false elements. Find the row with max number of true elements in it. 00011 0 1 true is 0 false is 1 .. so we will say 2nd row has maximum 1 and 3rd row has mximum 0 -- thanks --mac -- thanks --mac -- 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, soumya prasad ukil -- 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] matrix [MS]
this code has a problem for t[1][1] position when the value is 1(possible
values 0/1 i.e. B/W)
can fix tomorrow..
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Fri, Dec 24, 2010 at 5:58 PM, Ashish Goel ashg...@gmail.com wrote:
asnwer to original questioni have not checked it yet, apologies in case
of some mistake...
int t[n+1][n+1];
for (int i=0;i=n;i++)
t[i][0]=0;
for (int j=0;j=n;j++)
t[0][j]=0;
for (int i=1;i=n;i++)
for (int j=1;j=n;j++)
if (t[i-1][j] t[i-1][j-1] (t[i-1][j] == t[i][j-1]))
{
t[i][j]=t[i-1][j-1]+1;
if ( maxL t[i][j]) {maxL=t[i][j]; rightBottomX=i;
rightBottomY=j;}
}
else t[i][j]=0;
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Oct 27, 2010 at 11:30 AM, rahul patil
rahul.deshmukhpa...@gmail.com wrote:
hello all,
suppose given matrix contains the 0(white) and 1(black)
0
11100
00100
11100
01100
create the matrix R as follows
1 traverse each row where each cell represents no of continuos balck
cells till the current cell
0
12300
00100
12300
01200
similarly
creat the matrix C as follows
1 traverse each column where each cell represents no of continuos balck
cells till the current cell
0
11100
00200
11300
02400
Now it is easy job
1 traverse matrix row wise ( matrix is n,n )
2 go to position i,j i=row j=column
3 if R(i,j) 1 , then go till k,j (where i k = n )
for every (k=n;ki;k--)
if R(k,j) abs(i-k) {
if C(k,j) = abs(i-k) C(k- abs(i-k)= abs(i-k) {
if(abs(i-k) max_side){
maxi = i
maxj = k;
max_side = abs(i-k)
}
}
4 sol is square of length max_side with upper right corner maxi,maxj
On Fri, Oct 15, 2010 at 9:24 PM, snehal jain learner@gmail.comwrote:
Imagine you have a square matrix, where each cell is filled with
either black or white. Design an algorithm to find the maximum
subsquare such that all four borders are filled with black pixels.
--
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,
Rahul Patil
--
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: SUN Microsystem Question
@Bittu: Using the first 10 numbers, build a max heap. Then add each number into the 11th array position (always the 11th position) and perform the up-heap operation. At the end of the input, discard the 11th number in the heap. The remaining numbers will be the 10 maximum. O(n log k) where n = the number of items in the list and k = the number of maximum items you want. Dave On Dec 24, 3:32 am, bittu shashank7andr...@gmail.com wrote: You Have File of Containing 1 Million Integers You need To Find 10 Maximum Integer Out of Them.How You Will Do That ...what is Time space Complexcity of Algorithm that you will usethen optrmize the solution.. Constraints- U can't Store Whole File in memory @ one time e.g. if u will do that gigabyt eof memory may be reuqired so that should be avoided. Regards Shashank Mani Narayan Birla Instute of Technology,Mesra -- 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: good question
@Monty: Use an alternating across and down algorithm: Set the current row = the first row While current row is not the last row Look across the current row for the first false Look down the column containing that first false for a true If no such row is found, break. // current row is the result End While Since you only go to the right and down, you can't take more than m + n steps. Dave On Dec 24, 5:46 am, monty 1987 1986mo...@gmail.com wrote: Given a boolean matrix with all the true elements on left side in the row so that each row can be broken into two parts left part containing only true elements and right part containing only false elements. Find the row with max number of true elements in it. if the size of matrix is m*n then it can be solved in O(m+n) time. Any bettar 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: amazon interview question
@SoumyaNice 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] Codechef
I have solved this problem , but i need test cases for this as it it giving WA in online judge. i dont want algo , but if anyone have solved this, please provide with some random test cases or one or two corner test cases. i will be greatful. http://www.codechef.com/problems/ARRAYTRM Given n numbers, you can perform the following operation any number of times : Choose any subset of the numbers, none of which are 0. Decrement the numbers in the subset by 1, and increment the numbers not in the subset by K. Is it possible to perform operations such that all numbers except one of them become 0 ? Input : The first line contains the number of test cases T. 2*T lines follow, 2 for each case. The first line of a test case contains the numbers n and K. The next line contains n numbers, a_1...a_n. Output : Output T lines, one corresponding to each test case. For a test case, output YES if there is a sequence of operations as described, and NO otherwise. Sample Input : 3 2 1 10 10 3 2 1 2 2 3 2 1 2 3 Sample Output : YES YES NO Constraints : 1 = T = 1000 2 = n = 100 1 = K = 10 0 = a_i = 1000 -- 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: good question
@Dave nice algorithm On Fri, Dec 24, 2010 at 6:59 PM, Dave dave_and_da...@juno.com wrote: @Monty: Use an alternating across and down algorithm: Set the current row = the first row While current row is not the last row Look across the current row for the first false Look down the column containing that first false for a true If no such row is found, break. // current row is the result End While Since you only go to the right and down, you can't take more than m + n steps. Dave On Dec 24, 5:46 am, monty 1987 1986mo...@gmail.com wrote: Given a boolean matrix with all the true elements on left side in the row so that each row can be broken into two parts left part containing only true elements and right part containing only false elements. Find the row with max number of true elements in it. if the size of matrix is m*n then it can be solved in O(m+n) time. Any bettar 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- bhupendra dubey -- 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] SUN Microsystem Question
In addition - you should use 10 iterations of selection sort in each chunk. Then the same procedure for the group of chunks. -- 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] matrix [MS]
Incorrect, you tried to solve different problem. -- 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] Find a specific number in a special matrix.
Suppose you have a matrix n*m. each column and row of the matrix is already sorted. For example: 1,2,3 2,3,4 4,5,6 All 3 rows and 3 columns of above matrix are sorted. How to find a specific number in the matrix? The trivial O(nlogm) solution is to use binary search for all rows. I am looking for better solution. Thanks -- 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] Interview question
Given a Binary Matrix of 0's and 1's. Write an algorithm to: 1) Print the largest Rectangular Sub-matrix with all 1's. 2)Print the largest Sub-matrix with all boundary elements 0. Explain your whole algorithm with an example. -- thanks --mac -- 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 a specific number in a special matrix.
move from top rightmost column , go down if the number being searched is greater or left if the number being seracehd is small .. O(m+n) if u wanted to search 5 , u start from 3 (top right) , and since 53 , u go down to 4 , then 5 4 so go down , u reach 6 . now 5 6 so u will need to go left .. till u find 5 or less than 5 hope this helps regards --mac On Sat, Dec 25, 2010 at 8:25 AM, yq Zhang zhangyunq...@gmail.com wrote: Suppose you have a matrix n*m. each column and row of the matrix is already sorted. For example: 1,2,3 2,3,4 4,5,6 All 3 rows and 3 columns of above matrix are sorted. How to find a specific number in the matrix? The trivial O(nlogm) solution is to use binary search for all rows. I am looking for better solution. Thanks -- 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 --mac -- 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 a specific number in a special matrix.
@mac, Nice solution! On Fri, Dec 24, 2010 at 7:13 PM, MAC macatad...@gmail.com wrote: move from top rightmost column , go down if the number being searched is greater or left if the number being seracehd is small .. O(m+n) if u wanted to search 5 , u start from 3 (top right) , and since 53 , u go down to 4 , then 5 4 so go down , u reach 6 . now 5 6 so u will need to go left .. till u find 5 or less than 5 hope this helps regards --mac On Sat, Dec 25, 2010 at 8:25 AM, yq Zhang zhangyunq...@gmail.com wrote: Suppose you have a matrix n*m. each column and row of the matrix is already sorted. For example: 1,2,3 2,3,4 4,5,6 All 3 rows and 3 columns of above matrix are sorted. How to find a specific number in the matrix? The trivial O(nlogm) solution is to use binary search for all rows. I am looking for better solution. Thanks -- 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 --mac -- 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] random function
volume 2 , chapter 3 On Fri, Dec 24, 2010 at 11:13 AM, Puneet Ginoria punnu.gino...@gmail.comwrote: There is a book called The art of computer programming by donald knuth. He had discussed the random function in great detail. On Tue, Dec 21, 2010 at 8:06 PM, snehal jain learner@gmail.comwrote: How do you write your own random 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.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] UVA problems getting wrong answers
hii at all i was solving an adhoc problem on uva judge link -
http://uva.onlinejudge.org/index.php?option=com_onlinejudgeItemid=8page=show_problemcategory=121problem=208mosmsg=Submission+received+with+ID+8477913
and hers my code for the problem but i get wrong answer every tme
plzzz help me debug the code i dnt think i have missed any test case
the code is as follows
#includeiostream
#includecstdio
#includecstdlib
#includealgorithm
#includevector
using namespace std;
int main()
{
char str[1];// string of characters
int i,j,k;// counter variables
int len;// stores the length of the string
while(gets(str)!=NULL)
{
len=strlen(str);
vectorcharv;
j=0;
k=0;
for(i=0;ilen;i++)
{
if(str[i]==34)
{
++j;
if(j%2!=0)
{
v.push_back(96);
v.push_back(96);
}
else
{
v.push_back(39);v.push_back(39);
}
}
else
{
v.push_back(str[i]);
}
}
vectorchar::iterator p;
p=v.begin();
while(p!=v.end())
{
cout*p;
++p;
}
v.clear();
coutendl;
}
getchar();
getchar();
return 0;
}
thnx 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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
