# Software Interview Questions

Software interview questions shared by candidates

## Top Interview Questions

### Software Engineer at IBM was asked...

Puzzle: How do you weight an elephant without using a weigh machine? 34 AnswersUse a pool -> calculate the volume of water of the pool and the water level, put the elephant in the pool, take note of the level after the elephant after it is in the pool. By Archimedes principle, the volume of water dislocated is the same as the weight. So the weight of the elephant is the same as the difference in water volume. Not quite. The volume of the water is not the same as the weight of the elephant. You'd have to estimate the density of an elephant and multiply that by the volume of the water to get the mass, then multiply that by the acceleration due to gravity in water system (SI, English Customary, etc.) you're using. Luckily, mammals are mostly water (humans are around 70% water on average), so about 2/3 of the weight of the elephant would be equivalent to the weight of the water displaced. So you would have to estimate how dense the rest of the elephant is (since it'd be minerals and such, I'd say it's more dense than water) and follow the steps described above. Apply a known force to the elephant and measure the acceleration. Use physics to deduce the mass. Show more responses As it is not specified that the International System of Units must be used, define the Elephant unit (E) as the weight of your elephant. Your elephant then weights exactly 1E. Kyle I have to disagree with you. According to Buoyancy principle: Any object, wholly or partially immersed in a fluid, is buoyed up by a force equal to the weight of the fluid displaced by the object. So if you calculate the displaced fluid weight, which is quite easy in water as it is very close or equal to 1kg/L, you can get very close to the real weight of the elephant. Hmm, I think Kyle is right... and so are you when you say "Any object, wholly or partially immersed in a fluid, is buoyed up by a force equal to the weight of the fluid displaced by the object". IMHO elephants don't float... Actually Kyle is right. If we put something in the water, such as an sealed box with a ten pound weight inside (does not float), it will displace a proportionate amount of water. However, if we fill it up with a 50 pound weight, the same amount of water will be displaced, however. Fernando, you are using the Buoyancy principle. The Buoyancy principle is meant for objects that float (hence the word buoyancy-it means pressure to keep afloat). As Wouzz said, elephants don't float. You could just put a boat in water, measure displacement. Then put the elephant in the boat and take the difference. The displacement is going to equal mass as long as it's floating so you're good in a boat. Kyle was right that if you just threw an elephant in a pool, you would have you figure out density and all that. I would say bring a female elephant and let them enjoy life.. Isn't that just an improvised "weighing machine"? it sounds like you all are trying to determine whether an elephant is a witch (Monty Python reference). Instead of dealing with the whole mess of a wet elephant, why not use other pneumatic tools like an inflatable platform, an air pump, and a pressure sensor. See how much air pressure is required to lift the elephant. My experience is this, you don't have to have a perfectly correct answer. The goal of the question is to see if you can think around a problem. Besides elephants, I have heard 747's and aircraft carriers used as the object. A good answer shows that you thought of an alternate way of measurement, so the water displacement and pressure sensor ideas work. PS, if they ask you to weigh a 747, I would answer "Land it on an aircraft carrier and measure the additional water displacement!" I would use a see saw to weight my elephant. Using my weight (212 lbs in work wear), move the elephant until we balance, and then compare my distance to the pivot point to Clancy's distance to the pivot. (I named my elephant Clancy). The hardest part... finding a see saw strong enough to hold Clancy. Show more responses Archimedes Law of the Lever states: Magnitudes are in equilibrium at distances reciprocally proportional to their weights. "Give me a place to stand on, and I will move the Earth." Elephants DO float, even in fresh water. They're blubbery. Simple answer : Use a beam balance . Put elephant on one side and start throwing weights on the other side . When the beam is balanced you got the weight of the elephant equal to the sum of weights on the other ! Just ask him... Just find a person having a bad day and weigh him/her, help that person feel better, then weigh him/her again. The difference is the weight of the elephant you removed off his/her back. Works for monkeys too. one "weight"(s) by putting a weight on it note that the answer above is referenced to the question on THIS page which has been transcribed wrongly from the "home page" question (the "t" has been added) I would ask if it was an Indian elephant or an African elephant. I would solicit bids and then sub-contract the task to a reputable, cost-effective elephant weight service vendor, and let THEM decide the best approach.They can use a weigh machine or use any other method that does not require ME to use a weigh machine. The question (and answer) are no different than any other variation of, "How do you accomplish a task when you don't have the needed resources?" by using first clas lever. keep an elephant at known distance from the fulcrum; make the effort distance long enough that your weight balances the weight of an elephant; by using the formula load*load distance = effor*effortdistance( principle of lever) you already know load distance, effort distance and effort now you can calculate load, which is nothing but elephan'ts weight Show more responses By using the momentum conservation law, First I find a heavy enough object mith exact mass of m1 and then throw it with speed V1 to the elephant which is standing on a friction-less surface like ice or on plate with wheels under it to reduce the friction. after they meet, the elephant will move. and the object will change its direction and speed. Then I calculate the speed and direction of elephant and reflecting object, and finally I solve the vector equation below: m.v1=m.v2+M.V v1=vector of initial speed of object v2=vector of final speed of object M=elephant mass V=vector of elephant speed elevate the elephant to height "h". it will have potential energy of "U=mgh". hurl the elephant into a well which is vacumed well to avoid friction. at the end of the well, there is a pool of water with exact mass of " m' " and temprature of T1. after elephant reaches the pool he will give all of his energy to water causing water to become warmer Q=U. so mgh=m'c(T2-T1) with knowing g,h,m',c,T1 and T2 m can be calculated easily. place elephant on an iron plate and move it horizontally with steady speed v. and pass them through a constant magnetic field of B. change B untill the elephant start to move upward. read B and V. F=V x B is the force of magnetic field ( x denotes vector multiplication) which is now equal to weght force W=mg. knowing g the gravity constant, solve m. use SEE SAW put elephant on one side and on other side some men when it get balanced weighs the men Possible answers: 1. Zero. Take the elephant to space. The weight = 0. 2. I can guess it to around 150 kg ( there is fat person who lives next door and we call him an elephant his weight is 150 kg) I got asked this question. But the water displacement has gotten old. They prompted me for another answer. I said you measure the elephant and find out its volume in cubic meters. Then weigh its leg and measure it. Lets say the leg weighs 20 kgs and has a volume of 20 cubic metres. Then, each cubic metre weighs 1 kg. So if the total volume of elephant is 350 cubic meters, it will weigh 300 cubic metres. Take heavy weight gym dumbells keep start hanging with the one end of the rope an the other end to elephant and the rope goes over the pully,keep adding weight till elephant gets lifted esimate the answer to certain range and put it on a boat and if the boat shrinks it is more than the estimate weight else less else use F=MA forumula apply certain force and the calculate acceleration and then mass OK guys i take a boat which can carry more than a load of an elephant i keep the elephant in that boat [ there fore designed load = load of elephant+ X load] i will add some more load by boarding some swimmers one by one into boat if it starts sinking it means it reached designed load [designed load By allowing him to sit on us Show more responses Fernando,Your answer is really very wierd. First of all: rise in level of water will be equal to elephant's volume not weight. There is a vast difference in volume and weight. Second: if you think that you will estimate it's density to calculate it's weight then it will be a wierd thing because you will never be able to guess it right. Third: rise in level of water of pool will indicate the volume of submerged part of elephant and not whole elephant. If you think that you will submerge whole elephant then obviously you are killing it .So your answer is scientifically and economically wrong. I might suggest that you should take a help of a strong boat to determine elephant weight. take the boat in water and elephant on the boat.the boat will obviously sink a little.mark the level. now get elephant off the boat and put some weights on the boat till it reaches same level. now measure the weights and you will get the weight of elephant THANK YOU |

Given a number find it is one less than the power of two. 15 AnswersThe question could have been a little more detailed, most of the guys who took up the test could not understand this immediately. Given a number N, XOR it with N+1 = powers of 2 will give all 0s @Anonymous. That's not true. 3 in binary is 11 and 4 is 100, if you XOR 011 and 100 you will get 111, not 000. I think you meant to say that all numbers will be 1s. Show more responses N xor (N+1) = 2*N + 1 If the least bit is 1, then it is equal to N less than power of 2 if ( n << 7 ) cout << "It is one less than power of 2" For example 1 - 0000 0001 3 - 0000 0011 5 - 0000 0101 7- 0000 0111 // the power of two is always has the first bit set to1 and rest all would be set to 0. And one less than power of 2 has all the bits set to 1 except the fist bit. for example 16 = 10000 and 15 = 01111 Now if you do bit operation & on 16 and 15, you get zero. Hence, below is the code. public boolean oneLessPowTwo(int num){ boolean b = false; if(n & n+1 == 0){ b = true; } return b; } the power of two is always has the first bit set to1 and rest all would be set to 0. And one less than power of 2 has all the bits set to 1 except the fist bit. for example 16 = 10000 and 15 = 01111 Now if you do bit operation & on 16 and 15, you get zero. Hence, below is the code. public boolean oneLessPowTwo(int num){ boolean b = false; if((num & (num+1)) == 0){ b = true; } return b; } A one line answer to this question is: -1 + 2 to the power of -2 - language binary string prefix + length of binary string for N In Python: 2**(len(bin(511))-3)-1 Simple one line in any language with a function to convert int to binary string. 8 anwer Just another option of doing this Boolean checkNumber(int inputNum) { int temp = 2 ; while(temp < inputNum) { temp = temp * 2 ; } if(inputNum == temp-1) return True; else return False; } can any1 say it clarly..wt is dz 15+01111?? can any 1 say it clearly? package amazonExcerise; import java.util.Arrays; import org.apache.jasper.tagplugins.jstl.core.ForEach; public class concatenationArrays { public static void main(String[] args) { int a[] = { 1, 3, 77, 78, 90 }; int b[] = { 2, 5, 79, 81 }; int c[] = new int[9]; int j = 0; for (int i = 0; i 4) { c[i] = b[j]; j++; } System.out.print(" " + c[i]); } Arrays.sort(c); System.out.println(""); System.out.println("Sorted Array"); for (int i : c) { System.out.print(" "+i); } j = 0; System.out.println(); System.out.println("Array A:"); j = 0; for (int i = 0; i = 5) { b[j] = c[i]; System.out.print(" "+b[j]); j++; } } } } Show more responses For a number n, if n <= 1 the question doesn't really make sense. You can approach custom essay writing services for getting more details for your academic works.Visit http://essayguardian.com/. N is the number so (1< |

Assume a matrix of integers they are sorted in boh row and column vice .. how do u find a given number from the matrix in a optimal way? 10 AnswersLet the matrix is n*m matrix. Then O(n log m) solution is trivial (binary search in each row). There is a easy O(n+m) solution too. The idea is to start from upper right corner (mat[0][m-1]) and traverse toward lower left corner (mat[n-1][0]). On the way check each entry and depending on whether larger go left or down. If there is a solution you will find it on the way. Or you will arrive to a point where you can no longer move without going out of the matrix. Either way you will check at most O(n+m) entries thus the solution in O(n+m). I think it could be done even better than in O(n+m). Instead of starting at the upper right corner do a binary search on last column and find the biggest element that is still smaller than the given number. Say it's gonna be A[i, m-1]. Now we could throw away all rows up to an including i (since A[i, m-1] is larger than all of these elements) and the last column. Repeat everything for a smaller matrix of size (n - i, m - 1); To elaborate a little on dp's idea and add my take on it I would do a binary search on the last column to find the interval where the number is in. This interval will be one row within the matrix (assuming the value is not in the last column) and to find the interval should be O(log n). Then I would do a binary search on the row that remains which should cost O(log m). Combined that would be O(log n) + O(log m). Let me know what you guys think of this solution. Show more responses Anonymous, consider the matrix and you are searching for 9. Using this new algorithm we would look at rows 2 and 3 since 8 < 9 < 10 and completely miss 9 in the last row. (1 3 5 7) (2 3 6 8) (3 5 8 10) (6 9 11 12) dp, what do you do if the first element in the last column is already larger than the target? I.e. there may be no number that is smaller that the target. You could throw away that column, but that's it, I think. If so, the worst case becomes O(m). What if you did a binary search on the diagonal.... A better solution than O[log(mn)] is unlikely. An mxn array can be laid in memory as a m*n one dimensional array at its base form. So a matrix sorted by row and column simply means this mxn one dimensional array is sorted. A binary search will get you the result in O[log(mn)], that is the fastest solution available. How about this. for m columns - do binary range_search. As in, start with m/2 th column, if the number is in this range...col(0) O (log(m+n)) oops, there is a catch.... If the number is in a range, it can be in that column, or any of the columns towards left of it....and in some cases, if its in the range.. it can still be on any columns on right..... need to tweak a bit more. Ok writing this 3rd time , no one will see this but for the sake of it, Using radix sort Take 10 buckets and enter all numbers respectively. For example all numbers unit digit with 9 will in 9 number bucket. Just divide the given number (input) and into parts , using mod operator. And using the divided number"s unit digit find that index in the bucket. Tada . Radix sort way the. Linear search way to find the number Complexity O ( n ) Phew |

Why do you want to join Wipro ? and please don't give me crap answers ! 11 AnswersDon't say, this is the best company and all the regular stuff Its just for the fame,good salary,n happy life as i heard it s one of the best company too......:-) because, its good company and attractive salary,... Show more responses because its starting of my carrier and i have interest in this field and this is the better platform to boost up my carrier and its true that it gives better salary also ..................thanks and regards 2 fullfill my dreams its good , and I interest in this field To provide better service at the same time to increase the fame of wipro company....bcoz wipro is best company ever. because,they trust freshers and satisfy their needs.. its good company Wipro is one of the top most company and providing well equipments and standard products for society. Job security |

### Software Engineer at Google was asked...

Come out with an algorithm for getting the column number provided the column name in a excel sheet and vice versa. Excel has a naming convention of A,B..Z,AA,AB,AC..ZZ,AAA... This had to be converted to the column numbers. A will be 1 and AA will 27.. Also the algorithm to find the name provided column number. 13 AnswersIts conversion from decimal to base 26 with some exception like there is nothing maps to zero. There might be a better way to do it. void printColumn(uint32_t col) { col --; int div = 26; int add = 26; while( col / div ) { div *= 26; } div /= 26; while( div != 1) { printf("%c", (col / div) + 'a' - 1); col = col % div; div /= 26; } printf("%c\n", col + 'a'); } Opps above does not work after ZZ. The correct one is void printColumn(uint32_t col) { int a = 26; int denominator = 1; while(a 0; i /= 26) low += i; // if value is lower than lower bound, decrease quotient by one if( denominator != 1 && col < (quotient * denominator + low) ) { quotient --; } printf("%c", quotient - 1 + 'A'); col = col - denominator * quotient; denominator /= 26; } } Show more responses Let the size of the string asked is 3 e.g GHD . The formula to this : [ 26+26^2+...+ 26^(size-1) + (LetterIndex-1)*{26^(size-1)+....+(LetterIndex-1)*26}+Index ] In the code the above formula will use recursion to find the column number. The answer can be as simple as finding the first combination of number * i such that it is less then xcelcolvalue; ie repeat this till xcelColValue >= 26 ( 0 = 26){ int i = 1, num = 1; while((num * (i + 1)) 26){ i = 1; num++;} else i++; xcelNum -= num*i; sb.append((char) i); } if (xcelNum > 0) sb.append((char) xcelNum); return sb.toString(); } Also the above code is rough idea and not tested but gives enough idea on simplifying the solution. The code does not use lot of / and % calcuations but could elegantly find the solution. Note the Gaurd if(i > 26){ i = 1; num++;} else i++; which is important in finding the combination of num and i which multiples at least to xcelNum. I think the above is incorrect and it should be : public static String xcelString(int xcelNum) { StringBuffer sb = new StringBuffer(); while(xcelNum >= 26){ int i = 1; for(;(26 * (i + 1)) 0) sb.append((char) xcelNum); return sb.toString(); } Edge conditions aside, the program would be /* inputString - the column name. For e.g. "BZC" */ char [] columnName = inputString.toUpperCase().toCharArray(); int columnNumber = 0; for(int i = 0; i < columnName.length - 1; i++){ columnNumber = columnNumber + (int) Math.pow(26, (columnName.length - 1 - i)) * (columnName[i] - 64) ; } columnNumber = columnNumber + (columnName[columnName.length - 1] - 64); System.out.println("Column number is " + columnNumber); Edge conditions aside, the program would be /* inputString - the column name. For e.g. "BZC" */ char [] columnName = inputString.toUpperCase().toCharArray(); int columnNumber = 0; for(int i = 0; i < columnName.length - 1; i++){ columnNumber = columnNumber + (int) Math.pow(26, (columnName.length - 1 - i)) * (columnName[i] - 64) ; } columnNumber = columnNumber + (columnName[columnName.length - 1] - 64); System.out.println("Column number is " + columnNumber); int columnNumber(String col) { result = 0; for(i = 0;i< strlen(col) ; i++) { result *= 26; result + = col[i] - 'A' +1; } } int columnNumber(String col) { result = 0; for(i = 0;i< strlen(col) ; i++) { result *= 26; result + = col[i] - 'A' +1; } } public static String numToExcel(int n) { if(n 0) { int remainder = n%26; char newChar = (char) ('Z' - (26 -remainder)%26); result = newChar + result; n = (n-1)/26; } return result; } |

Given an array of numbers, nums, return an array of numbers products, where products[i] is the product of all nums[j], j != i. Input : [1, 2, 3, 4, 5] Output: [(2*3*4*5), (1*3*4*5), (1*2*4*5), (1*2*3*5), (1*2*3*4)] = [120, 60, 40, 30, 24] You must do this in O(N) without using division. 13 AnswersWell my answer was to divide the array in 2 different parts perform some logic and in end multiply both the arrays One solution would probably be to go through entire array once, keep a track of total product, and then in another loop populate result array by setting each index as totalProduct / (value at index in argument array) oh.. but without division. Didn't see that part with my tiny browser Show more responses If you were not supposed to divide the array into two, for processing.... import java.util.*; class aNum2{ public static void main(String[] args){ int[] a= new int[5]; int[] b= new int[5]; a[0]=1; a[1]=2; a[2]=3; a[3]=4; a[4]=5; int j; for(j=0;j<5;j++){ int i; int p=1; for(i=0; i<5; i++){ p=a[i]*p; } b[j]=p/j; } System.out.println(Arrays.toString(b)); } } if you werent supposed to use the division operator : import java.util.*; class aNum{ public static void main(String[] args){ int[] a= new int[5]; int[] b= new int[5]; a[0]=1; a[1]=2; a[2]=3; a[3]=4; a[4]=5; int j; for(j=0;j<5;j++){ int i; int p=1; for(i=0; i Please ignore the very first response .. there is a correction on line 20 If you were not supposed to divide the array into two, for processing.... import java.util.*; class aNum2{ public static void main(String[] args){ int[] a= new int[5]; int[] b= new int[5]; a[0]=1; a[1]=2; a[2]=3; a[3]=4; a[4]=5; int j; for(j=0;j<5;j++){ int i; int p=1; for(i=0; i<5; i++){ p=a[i]*p; } b[j]=p/a[j]; } System.out.println(Arrays.toString(b)); } } trick is to construct the arrays (in the case for 4 elements) for example { 1, a[0], a[0]*a[1], a[0]*a[1]*a[2], } // productsBelow { a[1]*a[2]*a[3], a[2]*a[3], a[3], 1, } // productsAbove then multiply productsBelow and productsAbove http://stackoverflow.com/questions/2680548/interview-q-given-an-array-of-numbers-return-array-of-products-of-all-other-nu #include using namespace std; int main(){ int a[4] = {1,2,3,4}; int b[4] = {1,1,1,1}; for(int i = 1 ; i =0; i--){ prod *= a[i+1]; b[i] *= prod; } for(int i = 0; i < 4; i++){ cout << b[i] << " " << endl; } } public class Example2 { static int[] Numarray={1,2,3,4,5}; public static void main(String[] args) { ArrayList arr1=new ArrayList(); int first=0; int count=1; for(int j=0;j<=Numarray.length-1;j++) { for(int i=0;i There should be no divsion of array not even numbers so the solution goes like this //SIMPLIFIED APPROACH class amazon2 { public static void main(String rags[]) { int []a={1,2,3,4,5};//any digits as per approach int []b=new int[10]; int []c=new int[10];//dummy integer array for(int i=0;i public void printProduct(int[] a) { int[] b= new int[a.length]; for(int j=0;j public void printProduct(int[] a) { int[] b= new int[a.length]; for(int j=0;j prodSum = function (arr, memo, index) { if(index >= arr.length){ return; } for(var i=0; i |

### Software Engineer at Google was asked...

How many rotations does earth make on its axis while going around the sun for one year. 10 AnswersDepends on the Leap Year or non Leap Year 365 for Non Leap Year 366 for Leap Year The question is flawed. It should either ask how many days earth takes in one revolution around sun, or how many days are in a year. The leap year is something imaginary humans have concocted to make the calendars look good. You can't say once is 4 years earth takes an extra day to go around the sun. It's to get you thinking about casting... the calender is a double casted to an int! Show more responses 365.25 / yr I wouldn't say 365/ 366 leap year. Jain has a point.^ It's either 364.25 or 366.25 depending on whether the earth spins in the same direction as it goes around the sun or not (I don't remember which it is and can't deduce it from the information that's available to me without looking it up). Imagine if the Earth did not spin at all on its axis so it would seem as if a year was equivalent to one day. It will take the Earth rotating either 264.24 or 366.25 times depending on the direction to seem like the 365.25 days that it does take. Every year it takes 365.25 rotations but while making calendar we ignore that 0.25 for 3 years and add an extra day in 4th year. <b>365.25 is WRONG!!!</b> Actually <b>Anonymous</b> is right! Just think about this (lay it out on your desk): <ul> <li>How many days would there be if the earth would not revolve around its axis?</li> <li>How many days would there be if it turned once around it's axis?</li> <li>Now do again one, change the direction the earth revolves it's axis, but keep going the same direction around the sun ...</li> </ul> The concrete right answer is 366.25 Here you find details on the exact number (with other proof): :) All answers here are false and crap. To say a leap day is added to look good is a lie. To say 365.25 rotations is also a lie because it is 365.25 days not rotations. It takes 366.25 rotations making the 365.25 days, so that in 4 years 1461 days are made by 1465 rotations. If the Earth rotated the opposite direction then the 366.25 rotations would make 367.25 days and the 1465 rotations would make 1469 days. Simple math, but the idiots rule the world, while retarded ones worse than the idiots try to play smarter and CAN'T. Same as with Venus it takes 1.62509035863 orbits to make 0.62509035863 synod. Mathematical geometry that all cycles differ by exactly ONE. (Like the 366.2422 to produce 365.2422, and the 366.2425 to produce the 365.2425, and the 366.25 to produce the 365.25 and this is why Venus takes 1.62509035863 of 224.606267349 days to make 0.62509035863 of 583.924347116 so that if the math is not an exact balance then you have the wrong figures. 1+fractional A times one orbit = fractional A times one synod. And so 13 orbits around the sun appear from Earth as 5 times around the sun. Or more precisely when the math is checked to be exactly equal by this LAW that I discover, 13 orbits will appear as 5.00044481781 synods as seen from Earth, and 5 synods (superior conjunctions) will be 12.9988435764 orbits. This question makes no sense. It's other way around, only when earth complete one round, we call it a year. To make human calculations easy, we introduced leap yrs. |

out of 25 horses select the fastest three in minimum number of races where in each race there would be exactly five horses. 10 Answers6 races i think it could be 6 races... first five races taking 5 horses each,and then the 6th ace taking the 1st horse of each of the previous race,den select the fastest three among them. would be 5 races if a stop watch is given..... however solutions given before are wrong since the horse coming 2nd in the first race might be faster than the horses that come first in the subsequent race :) hence we have to assume that a timer is provided Show more responses umesh no timer has been provided and it would be 7 races :) 11 races First 5 races taking 5 horses in each race. Next 5 races taking in each race horses which have come first, horses which have come second, third, fourth and fifth....... Final 11th race out of 5 which have won in second set of races to find fastest 3 6 Race would be wrong answer. What if in one group all the 5 horses are fastest of all others. Then from first round of 5 races we might lose those 2nd and 3rd ones. My answer is also 11 Races. Round one - 5 Races -------------------- Including all 25 horses. 5 each race. Left with -> 15 horses [Take 1st,2nd & 3rd from each race. Which would be total of 5*3=15 horses.] Round two - 3 Races [ Grouping any 5 of 15 horses left] ------------------- Left with -> 9 horses [Take 1st,2nd & 3rd from each race. which would be total of 3*3=9 horses.] Round three - 1 Race. ---------------- Take any 5 horses of 9 horses left Left with -> 7 horses 3 (1st 2nd and 3rd) + 4 (remaining ones) = 7 horses Round four - 1 Race. ---------------- Take any 5 out of 7 Left with -> 5 Round Five - 1 Race ---------- Race of 5 horses left 7 races: Split the 25 into 5 groups and make them race, this would be 5 races. Take the fastest horse of each group and make them race (6th race). Let's label the initial group of the top 3 horses of the 6th as a, b, c. The possible candidate for the 3 fastest are: a[1], a[2], a[3], b[1], b[2], c[1] We just need one last race to determine the top, the race would be between a[2], a[3], b[1], b[2], c[1]. The final result is a[1] then the top 2 of the 7th race. Easy: Correct answer is 11 but much easier method: 1. One race among 5 horses to find the fastest 3. 20 horses left not raced yet. 2. Now keep the 3 fastest horses you found and add two other horses out of 20 horses left to the race, again select the fastest 3. 3. Keep doing this for all 20 horses by selecting 2 of the horses left to race against the fastest 3 always. 1 race (to find the fastest 3) + 10 races (20/2 races to test all other 20 horses) = 11 races Constant Time - 7 Races 5 Races among 5 each. 6th Race for all third place holders 7th Race for Winner of sixth race +two people who defeated him in 1st race + two people who defeated the second place winner in 6th race. Best Case - 6 Races (3 place winner of 1st race against other 20 and he wins all the time) Worst Case - 11 Races( Make the fastest 3 of each race run against the other 2 each time) |

### Software Engineer at Google was asked...

Can't disclose the exact question because of NDA, but here's some food for thought: 3 can be written as 1+1+1, 1+2, 2+1 4 can be written as 1+1+1+1, 1+1+2, 2+2, 1+2+1, 2+1+1, 3+1, 1+3 Given an integer, how many possible expressions exist? (1+2 and 2+1 are different) 8 AnswersThere are total 2 ^(n-1)-1 expressions exist for any integer to be written on the basis of integers < the given Integer. Like for n=3, total 2^(3-1)-1= 3 expressions. For 4, 7 expressions exist and so on. No f(1) = 0 f(2) = 1 f(n) = Σf(i) + (n-1), where i = 1 to n-1, n>2 Show more responses Ader Lee: Shouldn't it be: f(n) = Σf(i) + (n-1), , where i = 1 to n-2, n>2 (i ranges from 1 to n-2, not n-1) f(1) = 0 and f(i) = i - 1 + sum_{i = 0}^{i - 1} f(i) Writing it down helps to find the sum: f(1) = 0(0) f(2) = 1 + 0(1) f(3) = 2 + 1 + 0(3) f(4) = 3 + 3 + 1 + 0(7) f(5) = 4 + 7 + 3 + 1 + 0(15) The first term(i - 1) equals the number of second terms and the second terms are the sum of 2 powers - 1 from 0 to (i - 2) so f(i) = 2^{i - 1} - 1 Also there is a neat normal form to generate all variations. For the sake of simplicity I show it for i = 4: Start from 1 + 1 + 1 + 1 and for j in 1 to i - 1 add together j and (j + 1) and write down the numbers and mark the added number in the next iteration. | | | 2 + 1 + 1 1 + 2 + 1 1 + 1 + 2 From the marked numbers to (last - 1) run j and do the same as before. The first generates 2 more, the second 1 more and the last one none. gen by first | | 3 + 1 2 + 2 gen by second: | 1 + 3 We could also generate the one element sum(4) from the first one but it's not needed in the problem. Also this representation looks nicer in a tree form but I can only type text here. The marks moved to the begining of the rows since the forum probably has some nice mangling algorithm. I hope you can figure out how the normalisation works. Might post some python code which does this later. a coin change problem with little modification will do . |

### Software Engineer at Google was asked...

Given n numbers (P1,P2,P3,.....Pn). Divide them in m contiguous partitions such that the sum of the maximum is minimum. For e.g. (5,1,4,2,3) and m =2 then (5,1)(4,2,3) 7 AnswersWas not able to solve this. But some guys used DP. Need to try all options according to m, Can be referred as spanning tree in depth of M. The leaf of the tree will hold the combination of the indexes that we've decided to divide by and than we can compute the min sum and choose the correct leaf Assume they are all integers? Get the sum and divide by m. Then try to get sum that can get the exact same value. If can't increase m by 1, try again, until find. Show more responses Binary search can be used to solve this. Let consider d[ i ][ j ] is solution of the problem when S = {s1, ..., si } and k = j. So it is easy to see that: d[ 0 ][ j ] = 0 for each j from 1 to k d[ i ][ 1 ] = sum(s1...si) for each i from 1 to n d[ i ][ j ] = minfor t = 1 to i (max ( d[i - t][j - 1], sum(si - t + 1...si)) for i = 1 to n and j = 2 to k Now let's see why this works: When there is no elements in the sequence it is clear that only one interval there can be (an empty one) and sum of its elements is 0. That's why d[ 0 ][ j ] = 0 for all j from 1 to k. When only one interval there can be, it is clear that solution is sum of all elements of the sequence. So d[ i ][ 1 ] = sum(s1...si). Now let's consider there are i elements in the sequence and number of intervals is j, we can assume that last interval is (si - t + 1...si) where t is positive integer not greater than i, so in that case solution is max ( d[i - t][j - 1], sum(si - t + 1...si), but as we want the solution be minimal we should chose t such to minimize it, so we will get minfor t = 1 to i (max ( d[i - t][j - 1], sum(si - t + 1...si)). Example: S = (5,4,1,12), k = 2 d[0][1] = 0, d[0][2] = 0 d[1][1] = 5, d[1][2] = 5 d[2][1] = 9, d[2][2] = 5 d[3][1] = 10, d[3][2] = 5 d[4][1] = 22, d[4][2] = 12 Code: #include #include #include using namespace std; int main () { int n; const int INF = 2 * 1000 * 1000 * 1000; cin >> n; vector s(n + 1); for(int i = 1; i > s[i]; vector first_sum(n + 1, 0); for(int i = 1; i > k; vector > d(n + 1); for(int i = 0; i <= n; ++i) d[i].resize(k + 1); //point 1 for(int j = 0; j <= k; ++j) d[0][j] = 0; //point 2 for(int i = 1; i <= n; ++i) d[i][1] = d[i - 1][1] + s[i]; //sum of integers from s[1] to s[i] //point 3 for(int i = 1; i <= n; ++i) for(int j = 2; j <= k; ++j) { d[i][j] = INF; for(int t = 1; t <= i; ++t) d[i][j] = min(d[i][j], max(d[i - t][j - 1], first_sum[i] - first_sum[i - t])); } cout << d[n][k] << endl; return 0; See Skiena's algorithm book. Dynamic programming chapter has this linear partition problem. Binary search the result and greedy check if it is obtainable. |

## See Interview Questions for Similar Jobs

- Senior Software Engineer
- Software Developer
- Associate Software Engineer
- Java Developer
- Software Development Engineer
- Intern
- Analyst
- Business Analyst
- Consultant
- Technical Lead
- Trainee Software Engineer
- Engineer
- Software Development Engineer II
- Systems Engineer
- Fresher
- Technical Support Engineer
- QA Engineer
- Software Engineer II
- Associate
- Project Manager