[algogeeks] Re: random number generator
clearly the prob. of getting true|false and false|true are equal to
0.6*0.4. Therefore the following code works,
bool uniform(){
bool f1;
bool f2;
do{
f1 = non_uniform();
f2 = non_uniform();
}while(!(f1 ^ f2));
return f1;
}
On Mar 17, 10:24 am, saurabh agrawal wrote:
> Given a function which returns true 60% time and false 40% time.
>
> Using this function you have to write a function which returns true 50% of
> the time.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Maze & labyrinth Solve Puzzle & WAP Efficiently
BFS search the maze
On Mar 2, 11:26 am, Don wrote:
> class coord
> {
> public:
> int x;
> int y;
>
> };
>
> class SolveMaze
> {
> public:
> SolveMaze() { location.x = location.y = 0; }
> bool Explore();
> private:
> list visited;
> coord location;
>
> };
>
> bool Explore()
> {
> // Determine if we've already been here
> if (visited.found(location))
> return false;
>
> // Base case, we are at an exit
> if (HasLadder()) return true;
>
> // Remember that we have been here
> visited.push(location);
>
> // Try all four directions
> for(direction = 0; direction < 4; ++direction)
> {
> if (TryMove(direction))
> {
> coord prev(location); // Copy current location
>
> // Track our current location
> switch(direction)
> {
> case 0: --location.y; break;
> case 1: ++location.x; break;
> case 2: --location.x; break;
> case 3: ++location.y; break;
> }
>
> // Explore from new location
> if (this->Explore()) return true;
>
> TryMove(3-direction); // Assume 3-direction is opposite move of
> direction
>
> // Back out location
> location = prev;
> }
> }
>
> // Remove current location from list
> visited.pop();
>
> // No exit found
> return false;
>
> }
>
> On Mar 2, 9:05 am, bittu wrote:
>
>
>
>
>
>
>
> > You are in a maze(like a labyrinth), and you open your eyes so you
> > don't know your position. The maze has walls and you can move only in
> > up, right, left and down directions. You can escape the maze when you
> > find a ladder.
>
> > The following API is given:
> > bool TryMove(direction) - returns true when you don't hit a wall;
> > bool HasLadder() - return true if you found the ladder.
>
> > Write a method bool Explore() that returns true if you can escape the
> > maze, false otherwise. Also, provide test cases.
>
> > A Good Explanation & Pseudo-code, Algorithmic discussion
> > needed..Object Oriented is Also Welcome
>
> > Thanks & Regards
> > Shahsank
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: sort partially sorted linked list
More comments on Ashish's approach. When implementing, you could reverse the list when you see it's in descending order. Then merge would be easier. On Mar 3, 1:03 am, Ashish Goel wrote: > find two consecutive sequences(can be two increasing2I, 1i1d,1d1i,2D), merge > them and then merge every next sequence with this merged sequence > > Best Regards > Ashish Goel > "Think positive and find fuel in failure" > +919985813081 > +919966006652 > > > > > > > > On Wed, Mar 2, 2011 at 8:33 PM, Shreyas VA wrote: > > I think in this case bubble sort with early exit will be efficient > > > On Wed, Mar 2, 2011 at 8:16 PM, snehal jain wrote: > > >> The LL is in alternating ascending and descendin orders. Sort the list > >> efficiently > >> egs: 1->2->3->12->11->2->10->6->NULL > > >> -- > >> You received this message because you are subscribed to the Google Groups > >> "Algorithm Geeks" group. > >> To post to this group, send email to algogeeks@googlegroups.com. > >> To unsubscribe from this group, send email to > >> algogeeks+unsubscr...@googlegroups.com. > >> For more options, visit this group at > >>http://groups.google.com/group/algogeeks?hl=en. > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algogeeks@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com. > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Missing Number in New Way Please Read Question Carefully..
for numbers from 0 to n, if you count the numbers whose LSB is 0 vs. those has 1, if count(0) > count(1), the missing number's LSB is 1, otherwise it's 0. Continue for the second LSB, your can find the missing number bitwise. On Mar 1, 3:14 pm, bittu wrote: > An array A[1...n] contains all the integers from 0 to n except for one > number which is missing. In this problem, we cannot access an entire > integer in A with a single operation. > The elements of A are represented in binary, and the only operation we > can use to access them is “fetch the jth bit of A[i]”, which takes > constant time. Write code to find the missing integer. Can you do it > in O(n) time? > > Thanks & Regards > Shashank Mani -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Amazon Interview question
@gaurav. They way I see it it's O(nlogn)?
you have n/4 for each level of the recursion tree and logn height. In
total its O(nlogn)
On Feb 28, 9:27 pm, Vinay Pandey wrote:
> Hi,
>
> Here is my solution, let me know:
>
> /* a helper function */
> void swap(int* arr, int index1, int index2) {
> /* this is only to swap to integers */
> arr[index1] = arr[index1]^arr[index2];
> arr[index2] = arr[index1]^arr[index2];
> arr[index1] = arr[index1]^arr[index2];
>
> }
>
> /* Actual switching */
> void switch(int* arr, int length) {
> if(length%2!=0 && length<2) {
> cout<<"Cannot switch in this case";
> return;}
>
> int index = length-1, first=0, second=0;
> bool flag = 0;
> while(index>=2) {
> if(flag == 0) {
> swap(arr, (index+1)/2, index);}
>
> if(flag == 1) {
> swap(arr, index/2 + 1, index);
> swap(arr, (index+1)/2, index);}
>
> index-=2;
> flag=(flag==0)?1:0;
>
>
>
>
>
>
>
> }
> }
> On Mon, Feb 28, 2011 at 4:32 PM, Dave wrote:
> > @Arpit: The problem is that for certain values of n, you get more than
> > one cycle, and the cycles are disjoint. You have to find all of the
> > disjoint cycles and move the elements in each one.
>
> > Dave
>
> > On Feb 28, 12:25 pm, Arpit Sood wrote:
> > > well space complexity should be mentioned in the question then, anyway,
> > > start with the second element put it at its correct location(say x), then
> > > take x put it at its correct location, this was when you do this n-1
> > time,
> > > you will get the correct answer because it forms a cycle.
>
> > > On Mon, Feb 28, 2011 at 11:33 PM, bittu
> > wrote:
> > > > @arpit otherwise it wont b amzon quest..
> > > > space dude..space is constants
>
> > > > Thanks
> > > > Shashank
>
> > > > --
> > > > 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.-Hide quoted text -
>
> > > - Show quoted text -
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Robot Moving on The Maze..Need All possible Path
DFS would work I think, if you try to find shortest path, use BFS On Mar 1, 3:30 pm, bittu wrote: > Imagine a robot sitting on the upper left hand corner of an NxN grid. > The robot can only move in two directions: right and down. How many > possible paths are there for the robot? > > FOLLOW UP > Imagine certain squares are “off limits”, such that the robot can not > step on them. Design an algorithm to get all possible paths for the > robot. > > Thanks & Regards > Shashank Mani -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: In Place Merging of Two Sorted .Array...Not Easy as seems to be,....
@ankit How do store the maximum? I know you mark the last element in
the heap invalid. But for the case above, first 80 was extracted and
then 60 should be extracted. But 60 would still lie in the first
array.
On Feb 25, 6:10 am, ankit sambyal wrote:
> Hey, it can be done in o(n*logn) time by calling maxheapify function on the
> two arrays. Then it decreases the size of the array whose last element is
> maximum of the two arrays. I hope you are aware of heap data structure and
> you have got the idea how to do it. If not let me know, it will explain it.
> Though its not O(n) but still better than o(n^2). I will think of O(n)
> solution.
>
> regards,
> Ankit
>
>
>
>
>
>
>
> On Fri, Feb 25, 2011 at 5:36 AM, bittu wrote:
> > we have two sorted array a[]={2,6,9,60}; b[]={1,3,5,34,80}; merge the
> > array in such way..
> > a[]={1,2,3,5}; b[]={6,9,34,60,80}; ..no extra space is allowed..i.e.
> > In-Place merging
>
> > Many of you thinks its easy..but here is q. of minimum complexity i
> > have done this but min e complexity high that not seems to be gud..i
> > know it can be done O(n) I have tried in O(n^2)...so i looking for
> > some gud solution for this
>
> > here is my approach lets take two array bigger & smaller
>
> > void merge(int[] smaller, int[] bigger)
> > {
> > int ls=smaller.length;
> > int bs=bigger.length;
>
> > while(true)
> > {
> > if(smaller[ls-1]<=bigger[0])
> > {
> > break;
> > }
>
> > //swap
> > int z=smaller[ls-1];
> > smaller[ls-1]=bigger[0];
> > bigger[0]=z;
>
> > //sort small
> > for(int j=ls-2; j>=0;j--)
> > {
> > if(smaller[j] > {
> > break;
> > }
>
> > int s=smaller[j+1];
> > smaller[j+1]=smaller[j];
> > smaller[j]=s;
> > }
>
> > //sort bigger
> > for(int j=0;j > {
> > if(bigger[j] > {
> > break;
> > }
>
> > int s=bigger[j+1];
> > bigger[j+1]=bigger[j];
> > bigger[j]=s;
> > }
> > }
> > }
>
> > Correct me if anything missing or wrong i can improve complexity ???
> > Hurray up!!!
>
> > Thanks & Regards
> > Shashank >>"The Best Way to Escape From The Problem is ton solve it"
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks]
Using Dynamic programming. Divide array into two parts a and b. Run the minimum edit distance solution for each pair of (a,b)(except this time for b we need to start from the end of the array). Find the minimum among those. On Feb 24, 10:41 am, sukhmeet singh wrote: > How do Levenshtein distance used.. For that u need to know the palindrome > that is closest to it.. and if that is know than there is no point in > calculating the distance .. we can easily see how many changes are to be > made..!(correct me if I am wrong) > > Further my approach is this : > taking the number in a string and then I can find the mid point of it. (for > an even number digit i have 2 mid points). Now i can move one pointer to > the left and other to the right to check whether there is a match in the > string , if not i increase the value of cntr by 1 > For eg > 98099 > mid is '0' so mantain to pointers and see that 8!=9 hence cntr+1 > next 9=9 . and we reach the end . > hence answer is 1. > > > > > > > > On Thu, Feb 24, 2011 at 7:36 PM, Balaji S wrote: > > how to solve it using DP?? > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algogeeks@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com. > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: amazon
Are you talking about IPC? On Feb 22, 10:05 am, jaladhi dave wrote: > What do you mean by data element here ? Also by file you mean the file where > you wrote the code ? And above all which programming language are we talking > ? > > You hit send button too early I guess :) > > On 22-Feb-2011 7:39 PM, "jalaj jaiswal" wrote: > > > > > > > > > Is there any way by which a data element in a file is accessible by > another > > file, where the program has multiple files. That data element should be > > accessible to a particular file only and inaccessible to the rest.? > > > declaring it as an extern will make it accessible to all i think .. what > cud > > be the answer ? > > > -- > > With Regards, > > *Jalaj Jaiswal* (+919019947895) > > Software developer, Cisco Systems > > B.Tech IIIT ALLAHABAD > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group.> To post to this group, send email to > algogeeks@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com.> For more options, visit this group at > > http://groups.google.com/group/algogeeks?hl=en. > > > > > > > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Directory Structure
use a tree. For the first N lines, build a tree accordingly. For the
next M lines search the tree. If miss, bump up the counter and add
the node.
On Feb 17, 7:53 am, Akshata Sharma wrote:
> On Unix computers, data is stored in directories. There is one root
> directory, and this might have several directories
> contained inside of it, each with di fferent names. These directories might
> have even more directories contained inside of them,
> and so on.
> A directory is uniquely identified by its name and its parent directory (the
> directory it is directly contained in). This is usually
> encoded in a path, which consists of several parts each preceded by a
> forward slash ('/'). The final part is the name of the
> directory, and everything else gives the path of its parent directory. For
> example, consider the path: /home/facebook/people
> This refers to the directory with name "people" in the directory described
> by "/home/facebook", which in turn refers to the
> directory with name "facebook" in the directory described by the path
> "/home". In this path, there is only one part, which means it
> refers to the directory with the name "home" in the root directory.
> To create a directory, you can use the mkdir command. You specify a path,
> and then mkdir wi ll create the directory described by
> that path, but only if the parent directory al ready exists. For example, i
> f you wanted to create the "/home/facebook/people" and
> "/home/facebook/tech" directories from scratch, you would need four
> commands:
> mkdir /home
> mkdir /home/facebook
> mkdir /home/facebook/people
> mkdir /home/facebook/tech
> Given the full set of directories already existing on your computer, and a
> set of new directories you want to create if they do not
> already exist, how many mkdir commands do you need to use?
>
> Input The first line of the input gives the number of test cases, T. T test
> cases follow. Each case begins with a line containing two
> integers N and M, separated by a space.
>
> The next N lines each give the path of one directory that already exists on
> your computer. This list will include every directory
> already on your computer other than the root directory. (The root directory
> is on every computer, so there is no need to l ist it
> explicitly.)
>
> The next M lines each give the path of one directory that you want to
> create.
> Each of the paths in the input is formatted as in the problem statement
> above. Speci fically, a path consists of one or more lower -
> case alpha-numeric strings (i .e., strings containing only the symbols
> 'a'-'z' and '0'-'9'), each preceded by a single forward slash.
> These alpha-numeric strings are never empty.
>
> Output For each test case, output one l ine containing "Case #x: y", where x
> is the case number (starting from 1) and y is the
> number of mkdir you need.
>
> Note: If a directory is listed as being on your computer, then its parent
> directory will also be listed, unless the parent is the root
> directory.
>
> INPUT
>
> 2
>
> 1 2
> /chicken
> /chicken/egg
> /chicken
>
> 1 3
> /a
> /a/b
> /a/c
> /b/b
>
> OUTPUT
>
> Case #1: 1
> Case #2: 4
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Large File & Millions of Records
Divide records into parts that could fit into main memory. Do rank find algorithm for certain range if necessary. On Feb 16, 7:26 pm, bittu wrote: > given a very large file (millions of record), find the 10 largest > numbers from it.in minimum time complexity > Don't think about hashing . Again Its Flat File Not the Database > > Thanks & Regards > Shashank Mani -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: String Operation
Greedy, always choose the remaining one that is the lexicographically
smallest since choose any other way will yield a lexicographically
greater one.
void concante(char **strings, int n){
qsort(strings,n,sizeof(char *),compareStr);
}
int compareStr(const void *a, const void *b){
return strcmp(*(char **)a,*(char **)b);
}
On Feb 16, 10:05 pm, simplyamey wrote:
> Try this code.
>
> #include
> #include
> using namespace std;
> int main()
> {
> string sArray[5] ={"aab","abc","bba","acc","bcc"};
>
> int n = 5;
>
> for(int i = 0;i < n; i++)
> {
> for( int j = 0; j < n - 1 ; j++)
> {
> if(sArray[j] > sArray[j+1])
> {
> string temp = sArray[j];
> sArray[j] = sArray[j + 1];
> sArray[j+1]= temp;
> }
> }
> }
>
> string sTemp;
> for(int k = 0; k < n ;k++)
> {
> sTemp = sTemp + sArray[k];}
>
> cout<<"printing result::"<< sTemp<
> }
>
> n = Number of strings.
>
> On Feb 17, 9:56 am, bittu wrote:
>
>
>
>
>
>
>
> > Given a group of strings, find a string by concatenating all the
> > strings in any order which produces the lexicographically smallest
> > string.
> > For e.g strings are acc bcc abb
> > So the string formed should be abbaccbcc
>
> > Thanks
> > Shashank
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: question at K10
Nice solution. Similarly you could #define:
void change()
{
#define change() i=10
}
On Feb 16, 12:55 pm, ankit sablok wrote:
> nice solution
>
> On Feb 15, 11:22 pm, jagannath prasad das wrote:
>
>
>
>
>
>
>
> > void change()
> > {
> > #define i i=10,n}
>
> > this will do..
>
> > On Tue, Feb 15, 2011 at 11:33 PM, Rel Guzman Apaza wrote:
>
> > > Nothing... 10 in base 5 = 5 in base 10.
>
> > > void change(){
> > > printf(""); //...?
> > > }
>
> > > 2011/2/15 Don
>
> > > A semicolon is valid in the middle of a line in C or C++.
>
> > >> For instance, no one says that
>
> > >> for(i = 0; i < 10; ++i)
>
> > >> is three lines of code.
>
> > >> Don
>
> > >> On Feb 15, 11:31 am, jalaj jaiswal wrote:
> > >> > after termination of semicolon , that will be considered a separate
> > >> > line
> > >> i
> > >> > guess
>
> > >> > On Tue, Feb 15, 2011 at 10:59 PM, Don wrote:
> > >> > > void change()
> > >> > > {
> > >> > > printf("10"); while(1) {}
> > >> > > }
>
> > >> > > On Feb 15, 10:17 am, Balaji S wrote:
> > >> > > > Insert only one line in the function change() so that the output of
> > >> the
> > >> > > > program is 10.
> > >> > > > You are not allowed to use exit(). You are not allowed to edit the
> > >> > > function
> > >> > > > main() or to
> > >> > > > pass the parameter to change()
>
> > >> > > > void change()
> > >> > > > {
> > >> > > > // Code here}
>
> > >> > > > int main()
> > >> > > > {
> > >> > > > int i=5;
> > >> > > > change();
> > >> > > > printf(“%d” ,i);
> > >> > > > return 0;
>
> > >> > > > }
>
> > >> > > --
> > >> > > 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.
>
> > >> > --
> > >> > With Regards,
> > >> > *Jalaj Jaiswal* (+919019947895)
> > >> > Software developer, Cisco Systems
> > >> > B.Tech IIIT ALLAHABAD
>
> > >> --
> > >> You received this message because you are subscribed to the Google Groups
> > >> "Algorithm Geeks" group.
> > >> To post to this group, send email to algogeeks@googlegroups.com.
> > >> To unsubscribe from this group, send email to
> > >> algogeeks+unsubscr...@googlegroups.com.
> > >> For more options, visit this group at
> > >>http://groups.google.com/group/algogeeks?hl=en.
>
> > > --
> > > You received this message because you are subscribed to the Google Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algogeeks@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com.
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Byte or Bite...Its byte Array
since it is guaranteed that l points to the start of the character. Thus I would refer to 'X‘ as the byte l points to. Each number in the following represents the MSB of the corresponding byte. E.g. 101X --> the byte preceding X has MSB 1 and the byte preceding that has MSB 0 the byte preceding that has MSB 1. The k-th character refers to the k- th character to the left of X. Now let's consider the following situation, where 1X Since X is the start of a character, thus the preceding byte couldn't the first byte of the 2-byte character albeit the MSB is 1. Thus we delete 1 byte preceding X. For the situation ***0X where the preceding byte MSB 0 we want to know if it is the start of a 1-byte character or the second byte of a 2-byte character. Thus we need to look back further. For 00X, we delete 1 byte since the 2nd byte has MSB 0, which means it either the second byte or the 1-byte character, either way, the 1st byte stands alone. For 010X, we delete 2. Similar logic. For 0110X, we delete one. Continue doing in the similar fashion, we conclude that if the 1st byte has MSB 0, count the number of 1s between that byte and the first byte to its left that has MSB 0 or we reach the very first byte of array. If the number of 1s is even, (including 0), delete 1 character preceding X and 2 otherwise. On Feb 15, 12:11 pm, jalaj jaiswal wrote: > give an example as what to do .. tha language of the question is not clear > to me > > > > > > > > > > On Tue, Feb 15, 2011 at 5:32 PM, bittu wrote: > > Given a byte array, in which characters can be 1 byte or 2 bytes long > > > For 1-byte characters, the Most significant bit must be 0. For a 2- > > byte character, the most significant bit of the most significant byte > > must be one and the most significant bit of the least significant byte > > is don’t care (X). You are given the index, I of a character in the > > byte array. Note that I-1 or I+1 can lead you to either a character or > > the middle of a character. Give a logic (no need of code) to delete > > the previous character of the one to which I points. > > > Please Read The Question Carefully..Mean While I am Also think for > > Solution > > > 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 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. > > -- > With Regards, > *Jalaj Jaiswal* (+919019947895) > Software developer, Cisco Systems > B.Tech IIIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Binary Tree Amazon
hash would be a perfect choice.
I make a MinMaxHash class which would keep track of the min and max
value of the key.(since in this case we would never remove a key, thus
this primitive approach works. Otherwise use treeMap)
class MinMaxHash extends HashMap{
private Integer min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
@Override
public Object put(Object key, Object value){
if((Integer)key < min){
min = (Integer)key;
}
if((Integer)key > max){
max = (Integer)key;
}
return super.put(key,value);
}
public Integer getMin(){return min;}
public Integer getMax(){return max;}
}
The propagate(TNode t, int k, MinMaxHash res) would form a MinMaxHash--
>res.
public static void propagate(TNode t, int k, MinMaxHash res){
if(t == null){
return;
}else{
if(res.containsKey(k)){
res.put(k,(Integer)res.get(k)+t.data);
}else{
res.put(k, new Integer(t.data));
}
propagate(t.left,k-1,res);
propagate(t.right,k+1,res);
}
}
The ArrayList findVertical(TNode root) would return a
ArrayList containing the result.
The idea is to form a MinMaxHash for left subtree and right subtree.
And test a few cases for the root and the line number for the right
subtree. The code should be pretty self-explanatory. (TNode has int
data, TNode left and TNode right)excuse me for the poor writings
of java code, I suck at writing beautiful java code like others in
this group do..
public static ArrayList findVertical(TNode root){
ArrayList res = new ArrayList();
MinMaxHash left = new MinMaxHash();
MinMaxHash right = new MinMaxHash();
propagate(root.left,0,left);
propagate(root.right,0,right);
if(left.size()>0){
for(int i = left.getMin(); i <= left.getMax(); i++){
res.add((Integer)left.get(i));
}
}
if(left.getMax()==0 || left.size() ==0){
res.add(root.data);
}else{
res.set(res.size()-1,
(Integer)res.get(res.size()-1)+root.data);
}
if(right.size()>0){
int start = right.getMin();
if(start < 0){
res.set(res.size()-1,(Integer)res.get(res.size()-1)+
(Integer)right.get(start));
start++;
}
for(int i = start; i <= right.getMax(); i++){
res.add((Integer)right.get(i));
}
}
return res;
}
On Feb 14, 9:11 am, sankalp srivastava
wrote:
> Just a slight addition , you would also like to keep a record for the
> maximum range of the levels (assuming the function is called as
> (root , 0))
>
> On Feb 14, 5:25 pm, jalaj jaiswal wrote:
>
>
>
>
>
>
>
> > use hash
>
> > take an array verticalsum[]={0};
>
> > the function will be like this
> > void vertcal_sum(node *root, int level){
> > if(root!=NULL){
> > verticalsum[level]+=root->data;
> > vertcal_sum(root->left,level-1);
> > vertcal_sum(root->left,level+1);
> > }
>
> > }
> > On Mon, Feb 14, 2011 at 5:04 PM, bittu wrote:
> > > Given a binary tree with no size limitation, write a program to find
> > > the sum of each vertical level and store the result in an appropriate
> > > data structure (Note: You cannot use an array as the tree can be of
> > > any size).
>
> > > 4
> > > / \
> > > 7 8
> > > / \ / \
> > > 10 11 / 13
> > > 12
>
> > > here 4(root) , 11(leftsubtree's right child ), 12 (rightsubtree's left
> > > child) are in same vertical Line
>
> > > so here vertical line 1 is fro 10
> > > vertical line 2 sum is 7
>
> > > vertical line 3 sum is 4+11+12=27 (May Have Some Doubt So i Have
> > > represented the figure in correct way)
>
> > > vertical line 4 is 8
> > > vertical line 5 is 13
>
> > > Hope its clear to every one
>
> > > Thanks & Regards
> > > Shashank Mani
>
> > > --
> > > 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.
>
> > --
> > With Regards,
> > *Jalaj Jaiswal* (+919019947895)
> > Software developer, Cisco Systems
> > B.Tech IIIT ALLAHABAD
--
You received this message because you are subscribe
[algogeeks] Re: interview quest..
@Abhijit. Does your code takes O(N^2)? I think the following code
would do it in O(N)
iterate the string once:
void remove(char *a){
if(!a){
int i = 0, j = 1;
while(a[j]!='\0'){
if(i<0 || a[i]!=a[j]){
if(j-1>i){
a[i+1] = a[j];
}
i++;j++;
}else{
for(;a[j]==a[i];j++);
i--;
}
}
a[i+1] = '\0';
}
}
On Feb 14, 11:17 pm, Tushar Bindal wrote:
> if we have "RBGGGBGGBR"
> what should be the answer???
> "RBGR" or ""(empty string)
>
> On Mon, Feb 7, 2011 at 3:51 PM, rajan goswami
> wrote:
>
>
>
>
>
>
>
>
>
> > yeh.
> > Agree with ramkumar.
> > Simplest solution is to use Stack...
>
> > On Sun, Feb 6, 2011 at 8:11 PM, Abhijit K Rao
> > wrote:
>
> >> I could not get it for recursively, but iteratively, I coded a solution.
> >> If anyone knows recursively,
> >> let us know please.
>
> >> #include
> >> void main()
> >> {
> >> char s[18]="DGGDBCBHH";
> >> int i=0,j=0;
> >> int count;
> >> while(s[i]!='\0')
> >> {
> >> if(s[i] == s[i+1])
> >> {
> >> count = strlen(s)-2;
> >> while(count--)
> >> {
> >> s[i]=s[i + 2];
> >> i++;
> >> }
> >> s[i]='\0';
> >> i=0;
> >> }
> >> else
> >> {
> >> i++;
> >> }
> >> }
> >> printf("%s",s);
> >> getch();
> >> }
>
> >> I/P: DGGDBCBHH O/P: BCB
>
> >> Best Regards
> >> Abhijit
>
> >> On Sun, Feb 6, 2011 at 1:47 PM, ramkumar santhanam <
> >> ramkumars@gmail.com> wrote:
>
> >>> use stack.
>
> >>> --
> >>> You received this message because you are subscribed to the Google Groups
> >>> "Algorithm Geeks" group.
> >>> To post to this group, send email to algogeeks@googlegroups.com.
> >>> To unsubscribe from this group, send email to
> >>> algogeeks+unsubscr...@googlegroups.com.
> >>> For more options, visit this group at
> >>>http://groups.google.com/group/algogeeks?hl=en.
>
> >> --
> >> You received this message because you are subscribed to the Google Groups
> >> "Algorithm Geeks" group.
> >> To post to this group, send email to algogeeks@googlegroups.com.
> >> To unsubscribe from this group, send email to
> >> algogeeks+unsubscr...@googlegroups.com.
> >> For more options, visit this group at
> >>http://groups.google.com/group/algogeeks?hl=en.
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> Tushar Bindal
> Computer Engineering
> Delhi College of Engineering
> Mob: +919818442705
> E-Mail : tusharbin...@jugadengg.com, tushicom...@gmail.com
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Finding elements near the median
I agree time should be O(kn) On Jan 26, 9:55 pm, Sharath Channahalli wrote: > a) Find the median - O(n) > b) remove the element and again find the median > c) conitnue b until you get k-1 elements > > time complexity - kO(n) > > On Wed, Jan 26, 2011 at 9:55 PM, ritu wrote: > > > solution is nice!!but How to keep track of k closet numbers? > > > On Jan 23, 9:22 pm, ritesh wrote: > > > 1.) find x= median in o(n) > > > 2.) subtract x from each number of the array > > > 3.) find the k smallest number using o(n) algrithm > > > > On Jan 21, 4:04 am, snehal jain wrote: > > > > > Given an unsorted array A of n distinct numbers and an integer k where > > > > 1 <= k <= n, design an algorithm that finds the k numbers in A that > > > > are closest in value to the median of A in O(n) time. > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algogeeks@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Doubt regarding Pointers in C......
call it by reference.
bst *rec = Null;
insert(rec,5);
void insert(bst *&rec,int data){rec->data = data;}
Or declare it as
void insert(bst **rec,int data){*rec->data = data;}
and invoke with insert(&rec,5);
First one is just syntactic sugar to me although you can argue about
the whole pass-by-value/ref/pointer thing for hours. :)
On Jan 27, 8:03 am, nishaanth wrote:
> How can we pass pointers by value. Lets say even if it creates a copy of the
> pointer.
> The address stored by the pointer is the same. So when we dereference it
> shouldnt it get updated(as its just a memory address)?
>
>
>
> On Thu, Jan 27, 2011 at 5:39 PM, ritu wrote:
> > Here you are passing record pointer by value.
>
> > as you call insert(record, 5),stack frame of insert contains a copy
> > of record.after this value is modified by calling program,it should
> > be either returned explicitly to caller program or needs to be passed
> > by reference,so that calling program refers to it always by address.
>
> > On Jan 27, 4:17 pm, nishaanth wrote:
> > > Hi guys,
>
> > > I have a small doubt regarding pointers and functions.
>
> > > Consider the following prototype
>
> > > void insert(bst * head, int data);
>
> > > This function creates a node and inserts the data in the node. Lets say i
> > > call this function iteratively from main.
>
> > > main(){
>
> > > bst* record=NULL;
> > > insert(record, 5);
> > > insert(record, 8);
>
> > > }
>
> > > I see that record is not getting modified. Now is this related to call by
> > > value. But since we are passing pointers shouldnt the change get
> > reflected
> > > in main.
> > > isnt is similar to passing an array?
> > > Enlighten me in this regard. I am tired of segfaults :(
>
> > > Regards,
> > > S.Nishaanth,
> > > Computer Science and engineering,
> > > IIT Madras.
>
> > --
> > 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.
>
> --
> S.Nishaanth,
> Computer Science and engineering,
> IIT Madras.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: google written
@Wei Please test you code on "cdbbcbbca". I believe it outputs 2
instead of 8.
On Jan 14, 4:09 am, "Wei.QI" wrote:
> FindStartIndex(char[] a)
> {
> int start = 0;
> int current = 1;
> while(current < a.Length)
> {
> if(a[current] < a[start])
> {
> start = current;
> ++current;
> }else if(a[current] > a[start])
> {
> ++current;
> }else //a[current] == a[start]
> {
> int lookforward = 0;
> int startnext = start;
> int currentnext = current;
> while(startnext != currnet && a[startnext] == a[currentnext])
> {
> ++lookforward;
> startnext = (start + lookforward) % a.Length;
> currentnext = (current + lookforward) % a.Length;
> }//finish when compare to current head or there is different
> if(startnext == current || a[startnext] < a[currentnext])
> {
> if(current > currentnext)
> {
> break;
> }else
> {
> current = currentnext+1;
> }
> }
> else //a[startnext] > a[currentnext]
> {
> start = current;
> if(current < currentnext)
> {
> current = currentnext + 1;
> }else
> {
> break;
> }
> }
> }
> }
> return start;
>
> }
>
> On Fri, Jan 14, 2011 at 12:45 AM, radha krishnan <
>
>
>
>
>
>
>
> radhakrishnance...@gmail.com> wrote:
> > There s O(n) solution for this :)
>
> > On Fri, Jan 14, 2011 at 2:13 PM, radha krishnan
> > wrote:
> > > append the string to original string and
> > > index=answer of that spoj problem
> > > now u can ouput the string from index to index+strlen(originalstring)-1
>
> > > On Fri, Jan 14, 2011 at 2:12 PM, radha krishnan
> > > wrote:
> > >> wow
> > >> This s a spoj problem
> > >>http://www.spoj.pl/problems/MINMOVE/
>
> > >> On Fri, Jan 14, 2011 at 1:40 PM, snehal jain
> > wrote:
> > >>> Write the code to find lexicographic minimum in a circular array, e.g.
> > >>> for the array
> > >>> BCABDADAB, the lexicographic mininum is ABBCABDAD.
>
> > >>> --
> > >>> 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 > .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 > .com>
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Amazon Interview - Algorithms
@svix, I think pacific means takes i+v, But it still won't give the
global optimal
@Avi, I am not an expert on greedy algorithm and some problems may be
solved by using greedy. But as far as I understand, the difference
between DP and Greedy is DP makes use of the solution of the
subproblems while greedy doesn't. DP solves current problem by solving
subproblems first and then making the choice. Greedy solves current
problem by making a choice and solving subproblems. (see CLRS).That's
why greedy gives me this idea that it usually takes less time then
DP.
In your latest post, it appears to me you are using DP instead greedy
because your solution to current problem is built upon the solution of
subproblems.
Please give me your input.
On Jan 15, 12:59 pm, SVIX wrote:
> actually, there is a way t do this in greedy... instead of taking the
> local maximum value v for an index i, take the local maximum f(v) = i
> + v... this will get you the right answer...more efficient than DP?
> that i'm not sure... but average case will be close to linear
>
> On Jan 14, 9:29 pm, SVIX wrote:
>
>
>
>
>
>
>
> > @pacific..
> > the approach needs a little bit of tuning...
>
> > for instance, for the set 9 8 7 6 5 4 3 2 1 1 2, per ur approach, u
> > will pick 9, 8, 7, 6 etc...
>
> > minimum jumps in reality is from 9 to 1 to 2.
>
> > On Jan 14, 8:19 pm, pacific pacific wrote:
>
> > > At each location if the value is k ,
> > > find the largest value in the next k elements and jump there.
>
> > > This greedy approach works in 0(n^2) and i believe it works. If not can
> > > someone give me a counter example ?
>
> > > On Sat, Jan 15, 2011 at 3:30 AM, Avi Dullu wrote:
> > > > @jammy Even I felt the same, but the greedy 'algo' u suggest is actually
> > > > IMHO not a greedy approach. You just take each arr[i] and jump *without
> > > > deciding a locally optimal policy* . SO, if u were to *see* arr[i] and
> > > > *decide* on the optimal policy I feel one would follow d same steps as
> > > > in a
> > > > DP solution. Its only just that the implementation would be O(n^2).
> > > > Just to
> > > > add, this is the greedy approach I feel:
>
> > > > greedy_min_steps[n]
> > > > for i = 0; i < n; i++:
> > > > for (j = 0; j < input[i]; j++)
> > > > greedy_min_steps[ i + j ] = min(greedy_min_step[ i + j ],
> > > > greedy_min_steps[ i ] + 1)
>
> > > > this is the greedy approach I build and I see this being exactly
> > > > similar to
> > > > my DP approach. There are instances of greedy approach based algorithms
> > > > which have *optimized* DP counter parts. I feel this problem is one of
> > > > them.
> > > > More ideas ?
>
> > > > 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 Sat, Jan 15, 2011 at 2:14 AM, Jammy wrote:
>
> > > >> @Avi Greedy approach doesn't work since you can't ensure the choice is
> > > >> locally optimum. Consider 3,9,2,1,8,3. Using greedy alg. would give
> > > >> you 3,1,8,3 while otherwise DP would give you 3,9,3.
>
> > > >> On Jan 14, 6:11 am, Avi Dullu wrote:
> > > >> > I guess u got confused with the comment I wrote, I have added 2 print
> > > >> > statements and now I guess it should be clear to you as to why the
> > > >> > code
> > > >> is
> > > >> > O(n). The comment means that each element of the min_steps_dp will be
> > > >> > ACCESSED only ONCE over the execution of the entire program. Hence
> > > >> > the
> > > >> outer
> > > >> > loop still remains O(n). The next_vacat variable if u notice is
> > > >> > always
> > > >> > incremental, never reset to a previous value.
>
> > > >> > #include
> > > >> > #include
>
> > > >> > #define MAX 0x7fff
>
> > > >> > inline int min(int a, int b) {
> > > >> > return a >= b ? b : a;
>
> > > >> > }
>
> > > >> > int find_min_steps(int co
[algogeeks] Re: Amazon Interview - Algorithms
@Avi Greedy approach doesn't work since you can't ensure the choice is
locally optimum. Consider 3,9,2,1,8,3. Using greedy alg. would give
you 3,1,8,3 while otherwise DP would give you 3,9,3.
On Jan 14, 6:11 am, Avi Dullu wrote:
> I guess u got confused with the comment I wrote, I have added 2 print
> statements and now I guess it should be clear to you as to why the code is
> O(n). The comment means that each element of the min_steps_dp will be
> ACCESSED only ONCE over the execution of the entire program. Hence the outer
> loop still remains O(n). The next_vacat variable if u notice is always
> incremental, never reset to a previous value.
>
> #include
> #include
>
> #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 {
> printf("Updating min[%d] to %d \n", i + input[i], min_steps_dp[i] +
> 1);
> min_steps_dp[temp] = min(min_steps_dp[temp], min_steps_dp[i] + 1);
> }
> if (temp > next_vacant) {
> printf("i: %d \n", i);
> for (; next_vacant < temp; next_vacant++) {
> printf("next_vacant: %d \n", next_vacant);
> min_steps_dp[next_vacant]
> = min(min_steps_dp[temp], min_steps_dp[next_vacant]);
> }
> }
> }
> for (i=0;i 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 Fri, Jan 14, 2011 at 1:49 PM, Decipher wrote:
> > I don't think the inner loop is executing only once . Kindly check it for
> > this test case {1,3,5,8,9,2,6,7,6,8,9} . And try to print i in inner loop
> > you will find that for same values of i(Outer index) inner loop is called.
> > Its an O(n2) solution .
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Building A Special Tree
It's irrelevant but Building Special Tree has the same acronyms as Binary Search Tree...lame joke I know On Jan 14, 8:44 am, vaibhav agrawal wrote: > If it is a BST...then having a pre-order traversal can give us the unique > binary tree. > > Also, as per the problem statement, > > > every node can have 0 or at most 2 nodes. > > that means every node can have 0 or two childs, which is not the case below. > > On Fri, Jan 14, 2011 at 6:49 PM, Balaji Ramani > wrote: > > > > > > > > > Two different binary trees can have same set of Leaves/Inner Nodes and same > > Preorder traversal > > > 5 > > / \ > > 3 10 > > / \ > > 1 9 > > \ > > 7 > > > 5 > > / \ > > 3 9 > > / / \ > > 1 7 10 > > > So, I guess it is not solvable unless we have some more information. > > > Thanks, > > Balaji. > > > On Fri, Jan 14, 2011 at 10:50 AM, Decipher wrote: > > >> A special type of tree is given, where all leaf are marked with L and > >> others are marked with N. every node can have 0 or at most 2 nodes. Trees > >> preorder traversal is given give a algorithm to build tree from this > >> traversal. > > >> -- > >> 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 >> .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 > .com> > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: probability
Bayes' theorem: http://en.wikipedia.org/wiki/Bayes'_theorem P(x=even|x>3) = P(x>3|x=even)*P(x=even)/P(x>3)===>B On Jan 14, 2:29 am, snehal jain wrote: > An unbalanced dice (with 6 faces, numbered from 1 to 6) is thrown. The > probability that the face value is odd is 90% of the probability that > the face value > is even. The probability of getting any even numbered face is the > same. > If the probability that the face is even given that it is greater than > 3 is 0.75, > which one of the following options is closest to the probability that > the face value > exceeds 3? > (A) 0.453 (B) 0.468 (C) 0.485 (D) 0.492 -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: palindrome
if you meant starting the leftmost 1, to check if its palindrome:
unsigned int o = v;
unsigned int r;
for (r = 0; v; v >>= 1)
{
r <<= 1;
r |= v & 1;
}
if (o == r)
printf("palindrome\n");
else
printf("not a palindrome\n");
On Jan 12, 5:50 am, awesomeandroid wrote:
> @azhar good solution
>
> Thanks and Regards
> Priyaranjan
> code-forum.blogspot.com
>
> On Dec 22 2010, 1:55 pm, Azhar Hussain 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
> > wrote:
>
> > > On Wed, Dec 22, 2010 at 12:11 PM, mohan@ismu wrote:
>
> > >> if x is a 32 bit number
> > >> if((x&0x)==((x>>16)&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 algogeeks@googlegroups.com.
> > >> To unsubscribe from this group, send email to
> > >> algogeeks+unsubscr...@googlegroups.com > >> .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 > > .com>
> > > .
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Sort string based upon the count of characters
sort on two keys, primary key is frequency, secondary key is
occurrence.
using namespace std;
struct Item{
int freq;
int occur;
char chr;
Item(){ freq = 0; occur = -1; chr = -1;};
};
bool sortItem(const Item a, const Item b){
if(a.freq != 0 && b.freq != 0){
if(a.freq != b.freq){
return a.freq > b.freq;
}else{
return a.occur < b.occur;
}
}else{
return b.freq < a.freq;
}
}
void sortBasedOnFreq(char *str){
Item *array = new Item[256];
for(int i = 0; str[i]!='\0'; i++){
int offset = str[i] + 128;
array[offset].freq++;
array[offset].chr = str[i];
if(array[offset].occur==-1){
array[offset].occur = i;
}
}
std::sort(array, array+256, sortItem);
for(int i = 0; i < 256; i++){
if(array[i].freq>0){
cout< 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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: amazon questions
@snehal 1. Both are valid. 2. see taocp's sol. The probability of selecting AB to shoot is 1/3, so is BC,AC If AB were selected, the probability of hitting the target is (1- probability of both of them missed) = (1-(1-P(A)(1-P(B)), similar with case BC and AC. On Jan 11, 11:58 am, snehal jain 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
implemented it based on juver++ & zhang. I think both stacks need to
provide get_min functionality...
class MyQueue{
private ItemStack pushstack;
private ItemStack popstack;
class Item{
int val;
int min;
public Item(int val,int min){
this.val = val;
this.min = min;
}
}
class ItemStack extends Stack{
public void push(int val){
if(this.isEmpty()){
super.push(new Item(val,val));
}else{
Item oneItem = this.peek();
if(val>oneItem.min){
super.push(new Item(val,oneItem.min));
}else{
super.push(new Item(val,val));
}
}
}
@Override
public Item peek(){
return (Item)super.peek();
}
@Override
public Item pop(){
return (Item)super.pop();
}
}
public MyQueue(){
pushstack = new ItemStack();
popstack = new ItemStack();
}
public void push_rear(int value){
pushstack.push(value);
}
public int pop_front(){
if(popstack.isEmpty()){
while(!pushstack.isEmpty()){
int value = pushstack.pop().val;
popstack.push(value);
}
}
return popstack.pop().val;
}
public int get_min(){
if(!pushstack.isEmpty() && !popstack.isEmpty()){
return Math.min(popstack.peek().min,
pushstack.peek().min);
}else if(pushstack.isEmpty() && popstack.isEmpty()){
throw new EmptyStackException();
}else if(!pushstack.isEmpty()){
return pushstack.peek().min;
}else{
return popstack.peek().min;
}
}
}
On Jan 2, 12:23 am, sourav wrote:
> Implement a queue in which push_rear(), pop_front() and get_min() are
> all constant time operations.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Adobe Interview Question
brute force approach
On Jan 12, 5:42 am, AKS wrote:
> 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 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 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 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 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
> > > > > 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
> > > > > > 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, vector &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
> > > > > >> :)
>
> > > > > >> vector minVector; //storing the cuts
>
> > > > > >> void cutMin(int *arr, int len){
> > > > > >> int cut=0, minV = INT_MAX;
> > > > > >> vector res;
> > > > > >> cutMinHelper(arr, 0, len, true, 0, cut, minV, res);
> > > > > >> if(minV > > > > >> cout<<"minimal cut is"< > > > > >> }
>
> > > > > >> }
>
> > > > > >> void cutMinHelper(int *arr, int start, int len, bool isFirst, int
> > > > > >> sum,
> > > > > >> int cut, int &minV,
[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 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 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.
[algogeeks] Re: Adobe Interview Question
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 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 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 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 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 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, vector &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 :)
>
> > > >> vector minVector; //storing the cuts
>
> > > >> void cutMin(int *arr, int len){
> > > >> int cut=0, minV = INT_MAX;
> > > >> vector res;
> > > >> cutMinHelper(arr, 0, len, true, 0, cut, minV, res);
> > > >> if(minV > > >> cout<<"minimal cut is"< > > >> }
>
> > > >> }
>
> > > >> void cutMinHelper(int *arr, int start, int len, bool isFirst, int sum,
> > > >> int cut, int &minV, vector &res){
> > > >> if(isFirst && start > > >> if(start==0) cut = 0;
> > > >> int sum = arr[start];
> > > >> cut++;
> > > >> for(int i = start+1; i < len; i++){
> > > >> vector addOne = res;
> > > >> addOne.push_back(i-1);
> > > >> cutMinHelper(arr, i , len, !isFirst, sum, cut,
> > > >> minV, addOne);
> > > >> sum += arr[i];
> > > >> }
> > > >> }
> > > >> if(!isFirst && start > > >> int i, sum2 = 0;
> > > >> for(i = start; i < len; i++){
> > > >> sum2 += arr[i];
> > > >> if(sum2 == sum){
> > > >> break;
> > > >> }
> > > >>
[algogeeks] Re: Adobe Interview Question
@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 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 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 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, vector &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 :)
>
> >> vector minVector; //storing the cuts
>
> >> void cutMin(int *arr, int len){
> >> int cut=0, minV = INT_MAX;
> >> vector res;
> >> cutMinHelper(arr, 0, len, true, 0, cut, minV, res);
> >> if(minV >> cout<<"minimal cut is"< >> }
>
> >> }
>
> >> void cutMinHelper(int *arr, int start, int len, bool isFirst, int sum,
> >> int cut, int &minV, vector &res){
> >> if(isFirst && start >> if(start==0) cut = 0;
> >> int sum = arr[start];
> >> cut++;
> >> for(int i = start+1; i < len; i++){
> >> vector addOne = res;
> >> addOne.push_back(i-1);
> >> cutMinHelper(arr, i , len, !isFirst, sum, cut,
> >> minV, addOne);
> >> sum += arr[i];
> >> }
> >> }
> >> if(!isFirst && start >> int i, sum2 = 0;
> >> for(i = start; i < len; i++){
> >> sum2 += arr[i];
> >> if(sum2 == sum){
> >> break;
> >> }
> >> }
> >> if( i==len-1 && sum2==sum) {
> >> if(cut >> minV = cut;
> >> minVector = res;
> >> }
> >> }
> >> if(i >> cut++;
> >> vector 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 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
> >> > for input
> >> > 1 4 5 6 2 2 2 2 4 5 6 1 1 7 8 8 1 7
> >> > segments :
> >> > (John)1 4 5 6 2 2 - (Mary)2 2 4 5 6 1 --- (john) 1 7 8 -- (Mary)
>
[algogeeks] Re: Adobe Interview Question
(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, vector &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 :)
vector minVector; //storing the cuts
void cutMin(int *arr, int len){
int cut=0, minV = INT_MAX;
vector res;
cutMinHelper(arr, 0, len, true, 0, cut, minV, res);
if(minV &res){
if(isFirst && start addOne = res;
addOne.push_back(i-1);
cutMinHelper(arr, i , len, !isFirst, sum, cut, minV,
addOne);
sum += arr[i];
}
}
if(!isFirst && start 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 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
> for input
> 1 4 5 6 2 2 2 2 4 5 6 1 1 7 8 8 1 7
> segments :
> (John)1 4 5 6 2 2 - (Mary)2 2 4 5 6 1 --- (john) 1 7 8 -- (Mary) 8 1
> 7
> minimum cuts made are 3
>
> (b) Divide the numbers in such a way that both recieve same sum of
> numbers.
> If input
> 3 4 5 7 2 5 2
> segments
> (john) 3 4 5 - (mary) 7 2 5 - (john) 2
> minimum cuts are 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.
[algogeeks] Re: floating point
I guess it has to do with how float/double is stored on your computer.
Always use an error tolerance when it comes to floating-point numbers
comparison. By the way, on my machine it outputs the same
thing("Hello")
e.g.
#define epsilon 10e-6
if(275.7-a>epsilon)
printf("HI");
else
printf("Hello");
On Jan 8, 9:24 pm, priya mehta wrote:
> #include
> int main()
> {
> float a=275.7;
> if(275.7>a)
> printf("Hi");
> else
> printf("Hello");
> return 0;
>
> }
>
> #include
> int main()
> {
> float a=75.7;
> if(75.7>a)
> printf("Hi");
> else
> printf("Hello");
> return 0;
>
> }
>
> why the above two programs give different output?
--
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: Problem from ACM ICPC 2010
I wondered that too...seems kid 3 gets too many wishes On Jan 8, 8:21 pm, bhawana goel wrote: > In the 3rd test case, how come the answer is Yes. 1,2 and 3 are > forming a cycle. > > On Jan 8, 1:19 pm, juver++ wrote: > > > > > > > > > Also, you may use hash_set and hash_map if such exists in your language. -- 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.
