raj
BAN USER- -1of 3 votes
AnswersThis Question was asked in written round on one of the online coding round, The Question was to code this. Question is as follows.
- raj in India
You want to create a staff to use in your martial arts training, and it has to meet some specific requirements.
You want it to be composed of two smaller staves of equal length so that you can either use it as a single staff or as two smaller ones.
You want the full sized staff's center of gravity to be exactly in the middle of the staff.
You have a very, very long branch from which you can cut the pieces for your staff. The mass of the branch varies significantly throughout it, so you use just any two pieces of the same length. Given a description of the mass throughout the branch, determine the longest staff you can make, then return three integers on a single line, the first two indicating the first index of each half-staff, and the third indicating the length of each half-staff.
The input will be given on a single line as a string of digits [1-9], each digit representing the mass of a section of the branch. All sections are the same size and the maximum length of the string is 500. Here is an example:
41111921111119
11119 11119
If the indicated sections are cut from the branch they will satisfy your requirements. They are both the same length, and they can be put together as either 9111111119 or 1111991111, both of which have a center of gravity exactly in the center of the staff.
Center of gravity can be determined by taking a weighted average of the mass of each section of the staff. Given the following distances and masses: Distance: 12345678 Mass: 22241211
Sum of the mass of each section: 2 + 2 + 2 + 4 + 1 + 2 + 1 + 1 = 15 Weighted sum of the masses: 2*1 + 2*2 + 2*3 + 4*4 + 1*5 + 2*6 + 1*7 + 1*8 = 60 Weighted sum / regular sum = 60 / 15 = 4
This means that the center of mass is in section 4 of the staff. If we wanted to use this staff the center of gravity would need to be (8+1)/2 = 4.5.
Here is an example problem:
131251141231 ---- ----
If we take the sections indicated we get 1312 and 1231. By reversing the first one and putting them together we get 21311231
Sum of the mass of each section: 2 + 1 + 3 + 1 + 1 + 2 + 3 + 1 = 14 Weight sum of the masses: 2*1 + 1*2 + 3*3 + 1*4 + 1*5 + 2*6 + 3*7 + 1*8 = 63 Weighted sum / regular sum = 63 / 14 = 4.5
This puts the center of mass exactly in the center of the staff, for a perfectly balanced staff. There isn't a longer staff that can be made from this, so the answer to this problem is
0 8 4
Because the half-staves begin at indices 0 and 8 (in that order) and each is of length 4| Report Duplicate | Flag | PURGE
Facebook Algorithm
Can You Please Explain what are you doing in the above code. BTW I run your code against some other test cases and I didn't get the expected output.
Here are those inputs
Input#00 : 123232111119232333277777999
Output#00: 7 15 6
Input#01:
751283918273129483751265369875938721253256
384982385781251985354664939832887525615625
665211639491598528185935839473825642193794
184375895489172359871654785647324524354639
289887198715265623845821451815818815252738
638451823475832516531656348728374628574593
847652354612753472165281273645987465847536
642387615238749187265876321827635482776859
871628376457165263745196283764872687654782
635987162983654786253476179834691827567647
382964865167234698172658761946256162516256
1527384273482748237482734827348274827
Output#01: 10 262 229
In both the above test cases your code is giving wrong answers.
Its not a Homework question, it is a question that was asked in a written round and the time limit for this question was 2 hour.
- raj February 26, 2013