Engineer intern Interview Questions
engineer intern interview questions shared by candidates
Top Interview Questions
Suppose you had eight identical balls. One of them is slightly heavier and you are given a balance scale . What's the fewest number of times you have to use the scale to find the heavier ball? 59 Answers3 times. (2^3 = 8) Two. Split into three groups of three, three, and two. weigh the two groups of three against each other. If equal, weigh the group of two to find the heavier. If one group of three is heavier pick two of the three and compare them to find the heaviest. Brian - this would be correct if you in fact were using a weighing scale, and not a balance scale. The ability to weigh one group against another with a balance scale allows Marty's answer to be a correct answer. Although - the question as worded provides a loophole. If it had been worded as "What's the fewest number of times you have to use the scale to CONSISTENTLY find the heavier ball", then Marty's answer would be the only correct answer. However, it is possible that you could get lucky and find the heavier ball in the first comparison. Therefore, the answer to the question as stated, is ONE. Show More Responses This question is from the book "How to move Mt Fuji".... Marty has already got the right answer. Actually Bill, by your interpretation of the question the answer is zero, because you could just pick a ball at random. If you get lucky, then you've found the heaviest ball without using the scale at all, thus the least possible amount of times using the scale would be zero. The answer is 2, as @Marty mentioned. cuz its the worst case scenario which u have to consider, otherwise as @woctaog mentioned it can be zero, u just got lucky picking the first ball.... None- weigh them in your hands. Assuming that the balls cannot be discerned by physical touch, the answer is 3. You first divide the balls in two groups of 4, weigh, and discard the lighter pile. You do the same with the 4 remaining, dividing into two groups of 2, weighing, and discarding the lighter pile. Then you weigh the two remaining balls, and the heavier one is evident. 2 3a+3b+2 = 8 if wt(3a)==wt(3b) then compare the remaining 2 to find the heaviest if wt(3a) !== wt(3b) then ignore group of 2 discard lighter group of 3 divide the remaining group of 3 into 2+1 weigh those 2 If == the remaing 1 is the heaviest if !== the heaviest will be on the scale With the systematic approach, the answer is 3. But, if you randomly choose 2 balls and weigh them, and by coincidence one of these two is the heavier ball, then the fewest number of times you'd have to use the scale is 1. Although the real question is: are the balls truly identical if one is heavier than the rest? just once. Say you are lucky and pick the heavy ball. One use of the scale will reveal your lucky choice so once, or the creative answer zero if you allow for weighing by hand Without judging by hand: Put 4 balls on one side, and 4 on the other. Take the heavier group and divide again, put 2 balls on one side, and 2 on the other. Take the 2 that were heavier, and put one on each side. You've now found the heaviest ball. This is using the scale 3 times, and will always find the right ball. Show More Responses None. They are identical. None is heavier. 2 weighings to find the slightly heavier ball. Step 1. compare 2 groups of three balls. Case 1. if they are both equal in weight, compare the last 2 balls - one will be heavier. case 2. If either group of 3 balls is heavier, take 2 balls from the heavier side. compare 1 ball against the 2nd from the heavy group result 1. if one ball is heavier than the other, you have found the slightly heavier ball. result 2. if both balls are equal weight, the 3rd ball is the slightly heavier ball. Easy Shmeezi Fewest - get lucky and pick the heaviest one. But wait! How would you know it is the heaviest one by just weighing one ball? Your logic is flawed. Two groups of four. Split heavier one, weigh. Split heavier one, weigh. 3 times. i think its 3. i would take it like this OOOO OOOO then OO OO then OO problem solved. i do this everyday. bye. praise be to allah. thats it. It's 2. Period. If you can't figure it out look it up online or in "How Would You Move Mount Fuji" (like somebody else said). This is one of the most basic brainteasers you could be asked in an interview. The answer is 2. 1) Divide the balls into 3 groups. 2 piles with 3 balls each, 1 pile with 2 balls. 2) Weigh the 2 piles of 3 balls. If both piles are the same weight, discard all 6 and weigh the last 2 to find the heavier one. 3) If 1 pile of 3 is heavier than the other, discard the lighter pile and the pile of 2 balls. Weigh 2 of the remaining 3 balls from the heavier pile. If both of the weighed balls are equal, the last ball is the heavier one. 2=if all the balls are identical and you pick up the first...weigh it and the second one is lighter or heavier then you've found the heavier ball in the least amount of attempts. 1=if all the balls are identical and you pick up the first...balance it and the second one is lighter or heavier then you've found the heavier ball in the least amount of attempts. Amy is 100% correct for the following reason: everyone (except Amy) is solving the theoretical problem. The practical side of the problem - notwithstanding jimwilliams57's brilliant observation that if one weighs more than the others IT IS NOT IDENTICAL (would have loved to see the interviewer's face on that one) - in order to 'weigh' them on a scale, one has to pick them up, therefore, you will immediately detect the heavier one without weighing: pick-up three and three ... no difference, no need to weight. Pick-up the remaining two to determine the heavier one. Steve First off, take yourself through the process visually and forget square roots, that doesnt apply here and here is why: The question is the Minimum, not the MAXIMUM. BTW, the max would be 7 ( 8-1); you are comparing 2 objects, so 1 ball is eliminated automatically in the first step. Anyway, you have a fulcrom of which you are placing 2 of 8 objects on each end. If by chance you pick the slightly heavier object as one of the two balls, you have in fact, found the slightly heavier one in the first round... btw dont be a smartass with your interviewer, he is looking for smarts not smarmy;) Show More Responses Respectfully, the folks who are answering "3" are mathematically modeling the nature of the balance incorrectly. Performing a measurement on a balance scale is not binary. It is trinary. Each measurement gives you one of three responses: The left is heavier, the right is heavier, or they are equal. So while you do need three binary bits to specify a number from one to eight, you need only two TRINARY-DIGITS Formally, you want the smallest value of n such that 3^n >= 8. The answer is 2. Note that you could add a ninth ball, and still, you'd only need to make two measurements. Of course, the smarty pants answer would be one. Just pick two balls at random and be lucky to have chosen the heavy one. But you're not guaranteed to be able to do it in just one measurement. English isn't my mother tongue... What is a balance scale? If looking up on Google, I find some devices with two bowls on a bar bearing in the center. Hence, the answer is once (if I'm luck enough to select the heavier ball in teh first measurement) If a balance scale allows to measure only one ball at a time, then it would take two measurements, unless you'd have more information on the weight, which is not listed here, hence doesn't exist in the context of the question^. minimum is 1 (if lucky - 25% chance by picking 2 balls at random) & max is 2 (using most efficientl process to absolutely determine without luck - 3/3/2 scenario) While Symantec was busy weighing my balls I took a job with NetApp.... They need to focus on hiring good, capable security engineers, not weighing their balls. The point of these interview questions is to both check your logical brain function and to hear how you think. Most of you are just posting jerk off answers trying to be funny, or you are really dumb. These answer get you nowhere with me in an interview. Think out loud, go down the wrong path back track try another logic path, find the answer. None of this "0 if you use your hands". That is fine if you are interviewing for a job in advertising where creativity is desired, nobody wants you writing code like an 8 year old. You have 12 balls, equally big, equally heavy - except for one, which is a little heavier. How would you identify the heavier ball if you could use a pair of balance scales only twice? The problem is based on Binary Search. Split the balls into groups of 4 each. Choose the heavier group. Continue till you get the heavier ball. This can be done in log(8) (base 2) operations, that is, 3. Since there is only one scale available to weigh. You first divide the balls in half. Weigh each group, take the heaviest group. This is using the scale twice so far. Now, divide the previous heaviest group into half, weigh both groups. Take the heaviest. Divide this last group and take the heaviest. This is the heaviest ball. We have used the scale 5 times. Show More Responses Would it be wrong to say for a sample size as small as 8, we might as well not waste time thinking about an optimal solution and just use the scale 7 times, as this will be more efficient than coming up with an ideal solution prior to using the scale? I stumbled across this while looking for something else on Google but I had to answer. It is 2, split balls into 2,3 and 3. weigh the 2 groups of 3 against each other. If equal weigh the group of 2 and the heaviest is obvious. If they are not equal keep heavy group of 3 and weigh 2 of the balls. if equal heaviest ball is one you didn't weigh. If not equal the heavy ball is obvious. 2 times. 8 balls. 1st step: [3] [3] [2] 2nd step: [[1] [1] [1]] [[1] [1] [1]] [[1] [1]] No idea The fewest number of times to use the scale to find the heavier would be Eight to One times ? It will actually be 1 because the question asks what's the fewest amount of times which is one because you could just get lucky you can use any method you want it would still be one because that is the fewest amount of turns you can have It's one. The fewest number of tries on using a balance scale would be one. If you put one ball on each side and one is heavier, you have the found the heavier ball. Use an equilateral triangular lamina which is of uniform mass throughout. It is balanced on a pole or a similar structure. Steps: Place 2 balls at each corner (total 6 balls) i. if the odd ball is one of those, one side will either go up or go down. Now repeat the process with one ball at each corner including the 2 unbalanced ones. ii. if balance is perfect, repeat the process with the remaining two balls and one of the already weighed balls. test answer 2016-01-12 00:34:07 +0000 Show More Responses You would not be able to find a ball heavier than the others. All eight balls are identical; therefore, they must all be the same weight. Correct answer has already been posted. I just want to contribute some theoretical analysis. Given N balls, one of them is heavier. Finding out the ball requires log3(N) trit of information. (trit is the 3-base version of bit). Each weighing may give you one of the three outcomes: equal, left-heavier, right-heavier. So the amount of information given by each weighing is upper-bounded at 1 trit. Therefore, theoretical lower-bound for number of weighings in the worst case is log3(N), which is actually attainable. So 27 such balls need only 3 weighings and 243 balls need only 5 weighings, etc. 2 as many have indicated above. The 3 is the kneejerk reaction but 2 is the correct answer. Marty's answer is correct, but he does not explain why. The logic of the balance scale is three-valued: . Its most efficient use is the recursive application of the three-valued logic until there is only one item left. The integral ceiling of ln(x)/ln(3) thus gives the fewest number of times you have to use the balance scale to find the uniquely heaviest ball of x balls. Ceiling(ln(8)/ln(3)) = 2. TvRef Reviewing the answers from over the years has been fun! Some time I would like to be the interviewer to ask these kinds of questions. In first looking at the question, I thought, "probably eliminate as many as possible with the 4 and 4" but then why would it he a thought experiment, less one in an interview, if it was so 2 dimensional? Whether or not getting to the best answer is much of the point, being reductionist by ignoring details, like the context of who is asking, lead me to go my own way as of the question was just text on a screen. There's a lot of 3 dimensional information you could get from someone by this question -- how nervous they are, if they don't then you see how they handle that, or how much they think of their answers to anything. I wonder, were the semantic holes in the question also intentional? In the comments people have written about technicalities -- things about how it wasn't specified that they were only visually identical, and therefore the question is contradictory. Or, how it didn't explicitly specify how to consistently, by most likely repeated efficient scenario, find the heavier ball, so people started that the least possible would be 1 if lucky. Then, since it wasn't explicit that you have to know which one was heavier, people said you could go 0 and guess the right one without the scale, either by direct guessing or trusting your hands with an unspecified sized difference in weight. If the word choice is designed to allow for those, perhaps the question is even more fun than I thought. One could see where and if one goes or gets hung up, see if one would ask clarification if they got hung up, or claim steadfastly about their thoughts being the most important on it, or focus elsewhere -- then that would be another layer to the question that makes it more interesting than I originally thought. I like tea. Show More Responses One or more comments have been removed. |
What was one of your best achievements on a project in the past? 19 AnswersAnswered about a previous internship, mentioned scalability and had a small discussion on that. Were there any coding questions? And was this for an internship? There was a coding question. It was for the SDE summer internship. Show More Responses Sorry last question, how long did it take for them to give you a final phone interview. It's been 5 days now for me.should I follow up? From what i've heard and seen, just wait, following up will barely do you any good. Hey, I just have one question out of curiosity, was the second online assessment web-cam proctored? i heard amazon is changing their recruiting process. Many people complained that the online proctoring was an invasion of their privacy. I also had a second online assessment but it was not webcam proctored. I am assuming the recruiting process is now two online non webcam assessments then a final phone interview. My friend had that round of interviews with Amazon 2 weeks ago. if you dont mind, could you tell us the phone interview questions ? Can you describe your phone interview? Do you pick your lang? do they ask you concept questions? do you do a coding problem? etc... No that's cheating Who has their phone interviews soon? I still haven't gotten back with a scheduled phone interview after the second assessment. Anyone else know long the time gap was between the second assessment to final phone interview? I just finished the second online assessment today. Now waiting for their reply. How long did it take for them to get back to you after the second online assessment? It's been almost 2 months and I have not heard back. Show More Responses Took about 2 days. If you have a recruiter you should email them over that kind of a length. Anyone hear back? Its been 1 week now and I do not have a recruiter...How are we supposed to contact a recruiter when we do not have one. I just got my first logical question part, it says webcam should be enabled. Is there any place i can practice those from? Did you get the coding question correct for your phone interview? Has anyone gotten an offer or response yet after their phone interview I had mine last Thursday. If you had a phone interview in February and got an offer pls lmk One or more comments have been removed. |
Given two strings representing integer numbers ("123" , "30") return a string representing the sum of the two numbers ("153") 17 AnswersI don't understand...it's a very stupid question! return Integer.toString(Integer.parseInt("123") + Integer.parseInt("30)); It's not stupid a stupid question. What if the strings have 10000 characters? It's not stupid question, but it's not hard either. I believe the way to do it is to implement the manual addition process by looping through the digits starting from the right to left and adding them one by one. This is an O(N) operation. I'm not sure if there is a better way to do it. Show More Responses lol it is a stupid question i agree. All you have to do is parse the strings add em parse em again and return em It is basic but yet not stupid. I assume that the interviewer asked to implement atoi and itoa (in case the interview was in C/C++). The interviewer wanted a loop through the digits starting form right to left, adding them one by one, and keeping track of the carriage. public static String sumStrings(String a, String b){ char[] num1 = a.toCharArray(); char[] num2 = b.toCharArray(); int i = num1.length - 1; int j = num2.length - 1; StringBuilder sumString = new StringBuilder(); int carry = 0; while(i >= 0 || j >= 0){ int d1 = 0; int d2 = 0; if (i >= 0) d1 = num1[i--] - '0'; if (j >= 0) d2 = num2[j--] - '0'; int sum = d1 + d2 + carry; if (sum >= 10){ carry = sum / 10; sum = sum % 10; }else carry = 0; sumString.insert(0, sum); } return sumString.toString(); } public class StringToInt { public int stringToInt(String str) { int tens = 1; int num = 0; for(int i = 0; i < str.length(); ++i) { num += (str.charAt(str.length() - 1 - i) - '0') * tens; tens *= 10; } return num; } public int addStrings(String str1, String str2) { return stringToInt(str1) + stringToInt(str2); } public static void main(String [] args) { StringToInt s = new StringToInt(); System.out.println(s.addStrings("145", "23")); } } @Conner What if the strings are 1000 characters long? does your int tens and int num variables support that? int stringToNumber(char *a){ char *end = a; int it = 1; int acum = 0; while (*end != NULL){ end++; //move pointer to last char of string } while (&end != &a){ acum+=((*end - '0') * it); it *= 10; end--; } return acum; } int sum (char *a, char *b){ return stringToNumber(a) + stringToNumber(b); } import java.util.Arrays; import java.util.Scanner; public class AddNumericStrings { public static void main(String[] args) { final Scanner in = new Scanner(System.in); while (true) { System.out.println("Enter 2 numeric strings : "); String x = in.nextLine(); String y = in.nextLine(); System.out.println(add(x.toCharArray(), y.toCharArray())); } } private static char[] add(char[] big, char[] small) { char[] result = new char[big.length + 1]; Arrays.fill(result, '0'); for (int i = big.length - 1, j = small.length - 1; i >= 0 || j >= 0; i--, j--) { char x = big[i]; char y = '0'; if (j >= 0) { y = small[j]; } int val = x - '0'; val += (y - '0'); result[i+1] += val % 10; if (val > 10) { result[i] += (val/10); } } return result; } } You all know that negative integers exist, right? The question does not specify if the integers are non-negative. One just assume, therefore, that negative integers are possible. It would not be called subtraction. Subtraction does not exist. It would just be addition of the additive inverse. Show More Responses Index the tuple to find the 1st & 2nd element. Convert the elements into ints and then convert the answer back to a string. Code: str(int(inp[0]) + int(inp[1])) public static String addTwoStrings(String s1, String s2) { int len1 = s1.length(); int len2 = s2.length(); char[] s1Chars = s1.toCharArray(); char[] s2Chars = s2.toCharArray(); StringBuilder sb = new StringBuilder(); int pointerA = len1 -1; int pointerB = len2 -1; int carry = 0; while (pointerA >= 0 || pointerB >= 0){ int a = pointerA 10) { carry = sumTemp / 10; sumTemp = sumTemp % 10; } else { carry = 0; } sb.insert(0, sumTemp); } if(carry >0) sb.insert(0, carry); return sb.toString(); } One or more comments have been removed. |
To find and return the common node of two linked lists merged into a 'Y' shape. 13 Answershow did the two linked lists make their poses to merge into a 'Y' shape, one's head attached to the waist? please explain more to help understand the question The two linked lists were something like: 1->2->3->4->5 and 3->4->5->6->7->8. For a Y shaped like this: 1 -> 2 -> 3 -> 4 ->7 -> 8 -> 9 5 -> 6 -> 7 -> 8 -> 9 where the trunk portion is of constant length, it is easy. Get the length of the first list. In our case 7. Get the length of the second list: 5. Difference is 2. This has to come from the legs. So, walk the difference in the larger list. Now node1 points to 3. node 2 points to 5. Now, walk through the two lists until the next pointers are the same. Show More Responses @kvr what if the lists are 1-2-3-4-7-8-9 and 12-13-14-5-6-8-9 Can this be done using hash tables? Or is there anything more efficient? i think that kvr's answer is the best. @snv if the two lists are linked by the very last two nodes, then you would find out after you are checking the values of the second two last two nodes. you just got unlucky and basically have to check until the very end. so basically, as a diagram with your example, it would look like this 1 -2 -3 -4-7-8-9 x -x -x -x -x-o 12-13-14-5-6-8-9 (sorry about spacing) but because you know the difference in length is 0, you can start comparing the two lists of nodes one by one. from the very beginning. HASH TABLE seems the only efficient wt. 1. add each element's address (of the smallest list)and push it to the hash table. 2. start walking second list. 3. get element compar eits address with hash table if match is found in hash table, return 4. if list is not exhausted, go to step 2. 5. return NULL Hashtable is complete overkill. The point is to realize that the two linked lists have the same tail. That means if you traverse them with the same index but from the right you will eventually find the first similar node. It's almost as easy if the problem said the two linked lists had the same prefix, find the first node on which they split. Here you walk them with the same index from the left. First reverse both list and find point where both gets diverged For Y condition the list could be List 1: 1->2->3->4->5->6 List 2: 7->8->9->4->5->6 So reverse list would be 6->5->4->3->2->1 6->5->4->9->8->7 now compare two list and move forward the position where you find next node of both are different is the point of merging Some of the above will work for doubly linked list. If not, travel node by node simultaneously from each end. When one traversal ends and the postion of cursor at the traversal is the answer kvr's answer is good but I think it could be optimized better by using 2 stacks. Traverse both lists putting each value into 2 separate stacks. Then when both are fully traversed, the head of each stack will match. Pop one off each at a time till they don't match, return the last popped. But I suppose it comes down to where the first match is at. If its the beginning of the list, kvr's answer will be better, if its at the end or bottom half 2 stacks would be better. Let's say L1 is the list starting with the lower number, and L2 is the other Set X = Head of L1 Set Y = Head of L2 While X <= Y Set X = Next(L1) End While If (X==Y) Return X Else While Y<=X Set Y = Next(L2) End While If X==Y Return X End If End If Repeat until you reach the end of either list. |
Determine if an array from 1..n has a duplicate in constant time and space. 13 AnswersCorrect answer is to place each value in the array in its corresponding index (i.e. if array[x] = 3, put 3 into array[3]). If an index already contains its corresponding value, there's a duplicate. ^^ Sorry, that's linear time *and* at best linear space, you fail. What are the properties of an array that affect time complexity? Usually we're talking about the size of the array, N, such that linear time operations, O(N), are those that perform an operation on each of the elements in the array. However, an important thing to consider is that you can evaluate N (the size of the array) itself in constant time. The only way this can be done in constant time is if the input satisfies the precondition that "1..n" means there are no *missing* values in that range. In other words, such an array from "1..5" must contain at least one instance of the numbers 1, 2, 3, 4, and 5. With that precondition, you know that the length of the array will be 5 if no duplicates and greater than 5 if it does contain duplicates. Show More Responses SUM(array) - (N(N+1)/2) = missing number. @Facebook Intern: That wont help .. In case there are 2 duplicates this can be broken. {1, 1, 4, 4} I attach pseudo code here: FindDuplicate(A) i = A.length j = 1 count = 0 while j < i if A[--j] - j == 0 j++ else count++ return count count holds the number of duplicated items This cannot be done in linear time unless the data-structure used to hold the integers has a property that immediately flags duplicates upon insertion. For e.g. like in a Dictionary/HashMap. If an array has elements from 1 to n the size of the array will be n, thus if the size of the array is greater than n, there must exist a duplicate. I think they are just asking to determine if there is any duplicate number ir not. Its not mentioned to find out which number it is. So that we can find out by using sum of n numbers I think they are just asking to determine if there is any duplicate number ir not. Its not mentioned to find out which number it is. So that we can find out by using sum of n numbers They asked for constant time. So checking sum will not work. For zero indexed arrays, Check if arr[len(arr)-1] == len(arr) - 1. Obviously this can't be done with constant time or space. At best you could compute a solution in linear time. memoize/cache it once then you could return the solution in O(1) time for subsequent calls. One or more comments have been removed. |
Mechanical Engineer Intern at Nokia was asked...
If you have a refrigerator in an isolated room (no heat in or out) and left the door to the refrigerator open, what would happen to the temperature to the room? Would it go up, down or say the same? 13 AnswersIf the door to the refrigerator is left open, the frige has to work harder because now it has to try to cool the entire room rather than just the inside of the frige. The coils and condenser in the back of the frige would create more heat thus heating the room up. The temperature of the room would stay the same - the key is the fact that it is in an isolated room. There is no heat exchange between the room and it's external surroundings. The refrigerator will warm up the room. If you look on the back of the refrigerator, you will see metal grating. Touch it. Its warm! A refrigerator is transporting heat from the inside cavity to the outside. However, the power cord running from the wall is pumping energy into the refrigerator/room. Energy is powering the refrigerator. It is also running an irreversible process, the energy dissipates out as heat and work (mostly heat), making the net temperature of the room increase. Show More Responses I propose the room remains constant - but for the following reason. The room is reported to be isolated. I denote that to be a cube with no walls, windows, doors, plumbing, OR conduit or an electrical box that would allow cable or air to move within or without the isolated cube. Logically, in that the fridge is not powered, it is not generating heat through the use of the motor, condenser or heat - exchange coils. Really, it doesn't matter what the answer is... you've just got to defend it logically. If the fridge were powered - but was an excessively large model (as you might find in a grocery store walk in) the room might cool. If it were a smaller unit - the motor would have to work overtime to try and keep it cool - thus heating the room. Just be creative! That's what they're looking for. Can you think on your feet. Aa The room's temperature will be exactly as the refrigerator's temperature. Heat will be absorbed by the grating metal on the back of the refrigerator, so no need to worry about where the heat that refrigerator produces go. The room temperature will remain the same. The reason for this lies in its basic principle of vapor compression cycle. Its true that refrigerator transfers the heat from one place to another. But one has to remember that the door is open. So, As heat is extracted by refrigerant and thrown in room using condenser and since the room is isolated and refrigerator door is open.. the same heat will be added inside refrigerator and same refrigeration cycle continues after that. In a way refrigerator is not able to cool anything. it is just continuously maintaining energy equivalence. In this case, there is a net gain of energy from the refrigerator outlet into the room and no loss of energy out of the room. Thus, the room will warm up since there is a gain of energy. Part of the room's temperature would decrease slightly. The other part of the room's temperature will stay the same. Since the refrigerator's energy is not large enough to cool the whole room it will cool a small portion of the room. the temperature inside the room will increase The temperature and overall heat content of the room will increase. Yes, the fridge it providing cooling, but it is doing this by removing heat from part of the air and dumping it into other parts of the air, all while doing work which is harnessed from the power input (electricity) from the wall. In other words, the heat in the air is just displaced from one area of air to another, so no loss nor gain of net heat, HOWEVER the work used to do this creates additional heat. If you consider this from a total energy standpoint, all energy within the room is fixed, except there's energy being added through the power input, so there's an increase in energy with time. I'm shocked at some of the other answers here, I hope those saying the temperature remains the same do not have mechanical engineering degrees. One or more comments have been removed. |
There are 20 floors in a building. If you're on an elevator and you're trying to get to the 20th floor, what is the probability that 4 people ahead of you click the 20th floor before you do? Assuming you click last. 11 Answersassume there is one button for each floor, so 20 buttons. a person can press any 1 button out of the 20, prob is 1/20. Since there are 4 people, so1/16000 These are independent events so the chances of one person before you going to the 20th floor is 1/20. Since this happens 4 times before you the probability is 4*(1/20) or 1/5. The above two are close, but wrong.. There are 20 buttons, thus 20 choices, sure. But you are getting on at one of the floor. No body will press the button for the floor they get on.. Thus, there is really only 19 choices. P = (1/19)^3 (Independent events mean (1/19)(1/19)(1/19)). Show More Responses 1/19 + 1/18 + 1/17 + 1/16 assuming that there were no repeated destinations. based on question: P(all 4 ahead of you want to get off on 20th fl) = (1/19)^4 real life(all 4 want to get off on 20th fl, and one of them is the first person press the button to 20th fl, and that leave all others, including you, stay still): (1/19) * (1/4) about 20% is the right answer. I am surprised with some of the answers, they are all very small possibilities (some less than 1%). I'm quite sure you are all wrong: The real probability is 1 - P(nobody pushes 20) = 1 - (18/19)^3 = 15% If one of the 4 press the button for the 20th floor then the others won't have to do anything. The chances of one of them pressing 20th is: 1/19 + 1/19 + 1/19 + 1/19 = 4/19 The answer is 1-(19/20)^4 One or more comments have been removed. |
Software Engineer Intern at Facebook was asked...
Write a function in language of your choice that takes in two strings, and returns true if they match. Constraints are as follows: String 1, the text to match to, will be alphabets and digits. String 2, the pattern, will be alphabets, digits, '.' and '*'. '.' means either alphabet or digit will be considered as a "match". "*" means the previous character is repeat 0 or more # of times. For example: Text: Facebook Pattern: F.cebo*k returns true 8 AnswersNOTE : I didn't really get the part of : "*" means the previous character is repeat 0 or more # of times. If it can be repeated 0 or more times, that means it's always true... I might have misunderstood this part. This is the code considering '*' and '.' are exactly the same. bool myStringCompare(char* string1, char* string2){ bool match=false; for(int i=0; string1[i] != '\0' && string2[i]!='\0'; i++) { bool condition1 = string1[i]==string2[i]; bool condition2 = (string1[i]=='*' || string1[i]=='.') && (isalpha((int)string2[i]) || isdigit((int)string2[i])); bool condition3 = (string2[i]=='*' || string2[i]=='.') && (isalpha((int)string1[i]) || isdigit((int)string1[i])); if(condition1 || condition2 || condition3) match=true; else{ match=false; break; } } return match; } I have used '#' instead of '*' . this code goes according to the rule that '#' gives 0 or more number of prev character value. #include #include #include bool ifMatch(std::string text, std::string pattern) { int tlen = text.length(); int plen = pattern.length(); std::string output = ""; char prev = '\0'; int k = 0; for(int i=0; i< plen && k < tlen; i++) { char textc = text[k]; char patternc = pattern[i]; if(patternc == '#') { if(prev == '\0') prev = '#'; else if(prev == text[k]) { output = output + prev; k++; } } else if(patternc == '.') { prev = textc; output = output + text[k]; k++; } else if(textc == patternc) { output = output + textc; prev = textc; k++; } else prev = pattern[i]; } std::cout << output << std::endl; if(strcmp(text.c_str(),output.c_str())==0) return true; return false; } int main() { ifMatch("facebook","#m#f.cn#bo#k"); } #include using namespace std; bool regex_match(string s1, string s2); int main() { if(regex_match("facebook", ".*.")) { cout << "Pattern Matched!" << endl; } else { cout << "Pattern Not Matched!" << endl; } return 0; } bool regex_match(string s1, string s2) { char c1, c2; int s2i = 0; for(int i = 0; i < s1.length(); i++) { c1 = s1[i]; c2 = s2[s2i]; if(c2 == '.') { s2i++; continue; } if(c2 == '*') { c2 = s2[s2i - 1]; bool done = true; c1 = s1[i - 1]; for(int j = i; j < s1.length(); j++) { c1 = s1[j]; if(c2 != '.' && c1 != c2) { done = false; i = j - 1; break; } } if(done) { break; } } else if(c1 != c2) { return false; } s2i++; } if(s2i < s2.length()) { for(int j = s2i + 1; j < s2.length(); j++) { if(s2[j] != '*') { return false; } } } else { return true; } return true; } Show More Responses #include #include using namespace std; bool regex_match(string s1, string s2); int main() { string strs[10] = {"facebook", "f.cebo*k", "*", ".*", "facebo.*", "facebo.*k", ".*.", "", " ", ".....o*."}; for(int i = 0; i q; for(int i = 0; i < s1.length(); i++) { q.push(s1[i]); } char last_char; for(int i = 0; i < s2.length(); i++) { if(q.empty()) { return false; } char c1 = q.front(); q.pop(); if(last_char == '\0') { last_char = c1; } if(c1 == '.') { last_char = c1; continue; } if(c1 == '*') { if(last_char == '.' || last_char == '*') { last_char = c1; break; } bool done = true; for(int j = i; j < s2.length(); j++) { if(s2[j] != last_char) { done = false; i = j - 1; break; } } if(done) { last_char = c1; break; } } else if(c1 != s2[i]) { return false; } last_char = c1; } if(!q.empty()) { while(!q.empty()) { if(q.front() != '*') { return false; } q.pop(); } } return true; } boolean accepts(char* pattern, char* s) { if (!pattern || !s) return 0; if (0 == *pattern) return (0 == *s); if ((strlen(pattern) > 1) && (pattern[1] == '*')) { return (match(pattern, s) && accepts(pattern, s+1)) || accepts(pattern+2,s); } else { return (match(pattern, s) && accepts(pattern+1, s+1)); } } boolean match(char* pattern, char* s) { return ((*pattern == '*') || (*pattern == *s)); } @Rahul: a small bug there (matching the '*' rather than the '.'): boolean match(char* pattern, char* s) { return ((*pattern == '*') || (*pattern == *s)); } should be: boolean match(char* pattern, char* s) { return ((*pattern == '.') || (*pattern == *s)); } Other thoughts: -- "if ((strlen(pattern) > 1)" is redundant since "if (!pattern[1] =='*')" takes care of it. (and I'd generally avoid a strlen in either a loop or recursive call) -- This solution ends up with a stack depth that is equal to the length of the target string -- far from ideal. #include using namespace std; bool match(string s1, string s2) { bool matching = true; char c1 = s1.at(0), c2 = s2.at(0); unsigned int i = 0, j = 0; while(matching && (i 0 && c1 == s1.at(i - 1)) { i++; } else if(c2 != c1) { matching = false; } i++; j++; } return matching; } int main() { bool m = match("faceboooooook", "f.cebo*.k"); if(m) { cout<<"matching"< public class MatchTwoStrings { public static void main(String[] args) { String s = "F9ceboooooook"; String t = "F.cebo*k"; String td = ""; for(int i=0; i |
To return the 'm' smallest numbers from a file of 'n' numbers 8 AnswersI would first create an array holding the first m values of the file, and sort. Then, each value I read from the file, I can compare the the last (largest) value in the array. If its smaller, do a binary search to find the correct spot in the array. Insert the number and shift everything behind it back by 1. Worst case runtime will be O(n lg m) Why cant we simply start with min=INT_MIN. Then, read first number from file, if lower, set min=that number. Seek next number and so on... We dont need to load the whole file. We will go to the disk often though. I will create a min heap with the given numbers and extract 'm' minimums from the heap which will get stored into the resultant array Show More Responses Anuj, Wont it take time of O((M+N)log N) @spammer, I think it's O(n+m*log n), since you can construct the min heap bottom-up and that only takes O(n) Why don't we just sort the array and return the first m numbers? Takes O(nlogn) for sorting and O(m) to return the first m numbers. Modified quick sort. Pick a pivot and test if one half is smaller than m. If it is, drag the rest from the other half; if it is not, keep partitioning Maintain a heap of m numbers and also track a variable which stores the current highest value. So as u go through the n numbers, if the number is higher than the current highest number, ignore it else insert it into the heap and set the current highest value to the newly inserted value |
I was asked two questions. Q 1. You are given two version numbers of a software, like Version 10.3.4 and Version 10.3.41. Write a program to find out which of the version numbers are the latest. If version 1 is latest output -1, if version number 2 is latest output +1 else output 0 if same version. Both the version numbers are taken as string. He also asks to make the program of minimum time complexity as we can. At the end he also asked the difference between an iterative program and one with recurrence and their advantages and disadvantages. Q 2. Given two files with a list of application IDs (or some kind of data) stored in them , write a program to compare the data in the two files and output all the common data found in each. What data structure would you use and why ? Give a minimum time and space complexity algorithm. Why did you choose the particular data Structure or algorithm ? 7 Answers1. This was a little tricky. You have to check for the decimal place in both the versions and then Store that part of the string till the decimal place in a temporary variable and then convert them to integer and check which one is greater. You have to keep on doing that till you reach the end of the version numbers or till when you find the answer 2. In the second question you can use Linked lists and then Binary Search Algorithm. The interviewer will ask you the reason for this. Why not just delimit the string with "." Then you'll have an array of string numbers. Then loop with the array from 0 -> n (depending on how many decimals there was) and compare. Return when one is greater than the other. You will have to check if you get a index out of bounds if one has more decimals than the other. Over all, that should be in n time. As for #2. HashTable it. Also n time. Show More Responses If you are using c++, can't you just use the "compare" method that is built into the string class? Maybe not the best solution... the time complexity is O(n). public static void main(String[] args) { String ver1 = "10.22.7.3"; String ver2 = "10.22.8.4.1"; String split1[] = ver1.split("\\."); String split2[] = ver2.split("\\."); int max = split1.length > split2.length ? split1.length : split2.length; for (int i = 0; i i) { System.out.println(+1); break; } else if (split2.length i) { System.out.println(-1); break; } else { if (Integer.parseInt(split1[i]) > Integer.parseInt(split2[i])) { System.out.println(-1); break; } else if (Integer.parseInt(split1[i]) < Integer .parseInt(split2[i])) { System.out.println(+1); break; } } } } String v1="10.3.4"; String v2="10.3.41; double v12=v1.parseDouble(); double v22=v2.parseDouble(); If(v12>v22) { System.out.print(-1);} else if(v22>v12) {System.out.print(1);} else{ System. out. print(0);} Q:2 List a= new LinkedList(); List b= new LinkedList(); while(a.hasNext()) { ( int =1; i |
See Interview Questions for Similar Jobs
- Software Engineer
- Intern
- Software Engineering Intern
- Software Developer
- Senior Software Engineer
- Software Development Engineer
- Software Engineering
- Data Scientist
- Technology Analyst
- Product Manager
- Engineering
- Analyst