# Questions d'entretiens - Software

Questions d'entretien de Software partagées par les candidats

## Le top des questions d'entretien

implement sqrt without using math libray 9 réponsese^((ln(x))/2) I think exp and ln still require a Math library. How about using Newton's method to find the root of f(x) = x^2 - a, where x is the solution (the sought square root) and where a is the number for which you want to find the square root? I would have implemented either Taylor or MacLaurin series, centered at an integer number that is closest to the number that you want to find the square root for, such that the square root of this integer is clean. So if you wanted to find the square root of 8.5, I would centre the series at 9 (sqrt(9) = 3), then compute the series at that point. I'd probably choose between 8 and 10 terms, as that is what is used in any scientific calculator. Afficher plus de réponses Actually, to add to that, I wouldn't be able to include 8 - 10 terms, as that would rely on the square root operation itself.... so I'd have to rely on a linear approximation. This is the way to go. Fast inverse square root as used in Quake III. float Q_rsqrt( float number ) { long i; float x2, y; const float threehalfs = 1.5F; x2 = number * 0.5F; y = number; i = * ( long * ) &y; // evil floating point bit level hacking i = 0x5f3759df - ( i >> 1 ); // what the fuck? y = * ( float * ) &i; y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration // y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed return y; } For detailed explanation of the algorithm, see http://en.wikipedia.org/wiki/Fast_inverse_square_root I wouldn't know about this algorithm, but I can think of a (definitely slower than this one) bisection algorithm to find the root of x^2 = number. Often what they are looking for is a programming data structures oriented solution. Such as using binary search to find sq root etc. poop |

Your on a farm, and your in a field with horses and you have a fence that you have to repair. But you left your hammer back at the house, what do you do? Remember the fence is broken and you cannot leave it alone otherwise the horses will escape. 7 réponsesRide one horse back to the house to get your hammer and use rope to temporarily secure the fence. or Tie one horse to the fence and go back to the house and get your hammer. Take a belt, if you have one, and tie the fence until you go home for the hammer. Why do you need a hammer to fix the fence? Maybe that assumption needs to be questioned. How is this for an assumption? Since its a farm, chances are the fence is made up of 5-6 ft. long wood pieces; which can be maneuvered into poles by hand. So, I would fix the fence and be on my way. Afficher plus de réponses Grab a rock and use it as a hammer. IMO a hammer is the easiest tool possible to replace. If there's absolutely no way to repair the fence without the hammer (can't use your shoe), and you have no assistant, bring the horse(s) with you to the house. Or send them into the barn -- pretty much all horses have a shelter for inclement weather, after all. Or scare all the horses to the far end of the pasture, then tie your shirt to the broken fence piece so it waves in the wind and spooks the horses away. Then go get the hammer. But frankly, if the fence is broken, how come the horses didn't escape before you got there to notice it was busted? Why assume the horses will want to leave? Horses are herd animals. Secure the stallion or lead mare, the rest will stay with them. How did it get broken while the horses were there, anyway? Are any of them injured? Do you have a bigger problem than some loose rails? Who left the horses in a pasture with a broken fence? If it was you, how will you CYA? If it was a coworker, how will you handle it? If it was the farmer's pretty daughter... nevermind. Or maybe just call someone to send over the hammer because the question does not say that I do not have a phone. |

A few questions on basic command-line syntax in Unix shells: 1. How would you log output and error messages from a command to a file? 2. How would you run the same command on every file in a directory? 3. How would you find the PID of a named process (say if you wanted to kill it)? 5 réponses1. command >file 2>&1 2. cd dir; for i in *; do command; done 3. ps | grep processname or ps -C processname #3 I disagree, more like ps aux |awk '$0 ~ /ProcessName/ && $0 !~ /awk/ {print $2}' If you want the PID #3 To find the PID: pgrep -x Afficher plus de réponses #3 - to find the PID Or simply use: pidof Opps!! there is typo; it should be: pidof |

Recently I attended the interview at Google and I was asked "You are given a sorted list of disjoint intervals and an interval, e.g. [(1, 5), (10, 15), (20, 25)] and (12, 27). Your task is to merge them into a sorted list of disjoint intervals: [(1, 5), (10, 27)]." 9 réponseshttp://www.mycareerstack.com/question/324/find-the-intervals-from-a-set-of-intervals-in-which-a-given-point-lies/ You can use line-sweep algorithm for that. First you need to sort the pairs according to their starts. Then we compare each two first pair together if they have intersection or not. if the end of the first pair is greater or equal to beginning of the second pair then they have intersection and it is obviously : start = min(start_first pair, start_second pair), end= max(end_first pair, end_second pair); this new pair will be compared with the next pair.. till the end. if there is not an intersection we leave it az an interval. We can use queue to hold the pairs Afficher plus de réponses google_interview = ( [(1, 5), (10, 15), (20, 25) ], (12,27) ) just_insert = ( [(1, 5), (10, 15), (20, 25), (80,89)], (17, 18) ) join_case = ( [(1, 5), (10, 15), (20, 25), (80,89)], (12, 22) ) empty_case = ( [], (1,10) ) def merge(orig,anew): """ If the input items are sorted, and interval is a 2-tuple, create a new list of intervals, such that we join together any overlapping intervals into a single tuple describing the combined range of the two or three tuples that could collide when we merge another interval into a list""" newlist = [] if len(orig)==0: return [anew] n = 0 # get items that are before the join while norig[n][0]: middleitem[0] = orig[n][0] if n=orig[n+1][0] and middleitem[1] middleitem[1]: # print "break",orig[n] break if orig[n][1] > middleitem[1]: # print "extend" middleitem[1] = orig[n][1] # print "skip",orig[n] n = n + 1 # now append remaining items newlist = newlist + [tuple(middleitem)] newlist += orig[n:] return newlist def test(tup): print 'merge( '+repr(tup[0])+', '+ repr(tup[1])+ ' )' print ' -> ', merge(tup[0], tup[1] ) print ' ' print "Test begin" test( google_interview ) test( just_insert ) test( join_case ) test( empty_case ) print "Test end" n*lgn sorted by lower bound and gogogo scan once. JAVA CODE: import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.List; /** * Created by admin on 3/2/16. */ class Interval { int start; int end; Interval() {start = 0;end =0;} Interval(int s, int e) { start = s; end = e; } } public class Solution { public List insert(List intervals, Interval newInterval) { ArrayList result = new ArrayList(); intervals.add(newInterval); return merge(intervals); } public List merge(List intervals) { ArrayList result = new ArrayList(); if (intervals == null || intervals.size() == 0) { return result; } Collections.sort(intervals, new Comparator() { public int compare(Interval a, Interval b) { return a.start - b.start; } }); for (int i=0;i= intervals.get(i+1).start) { current.end = Math.max(current.end, intervals.get(i+1).end); i++; } result.add(current); } return result; } } Time Complexity: nlgn + n = O(nlgn) Here is an implementation of the line sweep algorithm. https://gist.github.com/korayucar/e047749845d93bf5ad488ac9e42ce048 int[] mergeDisjointIntervals(int[] intervals, int[] range){ ArrayList result = new ArrayList(); for(int i=0;irange[0]&&high is inside return 0; } else if(lowrange[0]&&high overlaps tail return -1; } else if(low>range[0]&&lowrange[1]){ // 1 -> overlaps head return 1; } else{ // 2 -> does not overlap return 2; } } int[] mergeDisjointIntervals(int[] intervals, int[] range){ ArrayList result = new ArrayList(); for(int i=0;irange[0]&&high is inside return 0; } else if(lowrange[0]&&high overlaps tail return -1; } else if(low>range[0]&&lowrange[1]){ // 1 -> overlaps head return 1; } else{ // 2 -> does not overlap return 2; } } |

Given an array of 1001 elements, consists all numbers from 1-1000. Only one number is repeated. Write a function that returns the repeated number. 4 réponsesHonestly, there's two possible answers you could give, depending on whether you want space efficiency or time efficiency (assuming that the array is *not* sorted). For time efficiency, ironically, the brute-force method is fastest. You make a counter array of size 1000, all indices initialized to 0, which takes O(n) time. Then, you run the following: for (int i = 0; i 1) // pre-increment the counter, then check if we've counted 2. return array[i]; } Overall, the time-efficient algorithm takes O(2n) = O(n) time, but takes O(n) additional space. The space-efficient algorithm just quick- or heap-sorts the array in place, then runs a binary search, comparing the value to the index. If the value == array[mid], search higher; otherwise search lower. Leave the loop once (high - low == 1), and then return that value. This will take O(n log n) time due to the sorting process, but only take up O(1) extra space. Of course, if the array comes pre-sorted, you would trivially just run binary search as described above. hey, i have one quick solution, create a function that will take up an initial value and end value, that will add up all numbers between them. create another function to add all elements in the array. call the first function, with value (1, 1000) and call the second function. compare the value. whatever the difference is, that is the repeated number. I think Lucas has the right idea with his counter but there's one flaw to his posted solution. His check should be (if ++counter[array[i]-1] > 1). If you do indeed declare the count tracker as int counter[1000] (which is the values counter[0] to counter[999]), doing counter[array[i]] would cause an out of bounds problem for array[i] = 1000. A third alternative, along the lines of dsutandi's idea, is to recognize (if you took a number series class) that the sum of 1 to n = n *(n+1) / 2. So you can loop through the incoming array, sum up all the values, then subtract that sum against the afforementioned value (inserting 1000 for n) and that would be your duplicate. For example: int sum = 0; for (int i = 0; i < 1001; i++){ sum += array[i]; } return sum - (1000*1001)/2; Afficher plus de réponses here is my take : use following formula to get ideal sum : ideal_sum= n*(n+1)/2 real_sum=summation_of_all numbers in array repeated number = abs(real_sum-ideal_sum) |

Write a function that divides one number by another, without using the division operator, and make it better than O(n). 7 réponsesThis can be done in a recursive function, the following code is in Python. # get result of a/b without using a "divide" operator def div(a,b): if a < b: return 0 else: return div(a-b, b)+1 This is how human being do the division naturally, however, the running time of this is O(n/m), where n is the size of a, and m is the size of b, which means, O(n/m) is guaranteed to be less than O(n), when m is larger than 1. -Maxim The answer above is still O(n). We can use binary search and find the answer in the interval [1,a] and use multiplication operator. Totally agree with Vasil. Other option: Long Division Algorithm. O(log n) anyway. Afficher plus de réponses why not just a * b^(-1) :-) // Write a function that divides one number by another, without using the division operator, // Assume that x%y = 0 // O(log n) (function() { 'use strict'; var divide = function(x, y) { var xLength = (x + '').length; var i = 0; var result = 0; var xAry = ('' + x).split(); var xStart = ''; for (i = 1; i = y) { xStart -= y; result = parseInt(result, 10) + 1; } } } return result; }; console.log(divide(1000, 4)); })(); Use logarithms? O(1) log(x/y) = log(x) - log(y) = log(answer) answer = 10 ^ log(answer) Convert the number to divide into the base of the number that you are dividing with and then shift the 'bits' to the right by 1 then convert back to decimal |

Write a Java program that takes a 2D bitmap (represented as a 1D array of integers), and reverses it about its vertical axis. 4 réponsesI asked the interviewer whether I'm also provided with a width, so that I know how to interpret the data in the 1D bitmap, and he said yes. From a high level, you need a doubly nested for loop: the outer one iterates over the rows, and the inner one iterates over the elements, reversing them as you go along. function flip(array) { if(array.length === 0) { return []; } var done = false; var pos = 0; var result = []; while(!done) { done = true; result[pos] = 0; for(var i = 0; i >> 1; if(array[i] > 0) done = false; } pos += 1; } return result; } In Python: array1d = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15] #------------------------------------------------- def flipV(arr, width): rows = len(arr)//width for i in range(rows): # [0..rows) start = i * width # index of first element in row end = start + width - 1 # index of last element in row while start < end: arr[start],arr[end] = arr[end],arr[start] start += 1 end -= 1 #------------------------------------------------- def print2D(arr, width): rows = len(arr)//width for i in range(rows): # [0..rows) rowStart = i * width # start of row(i) for j in range(width): # [0..width) print(arr[rowStart + j], " ", end='') print() print(array1d) # original print2D(array1d, 4) flipV(array1d, 4) print(array1d) # flipped print2D(array1d, 4) Afficher plus de réponses Result: >>> Input [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Output [3, 2, 1, 0, 7, 6, 5, 4, 11, 10, 9, 8, 15, 14, 13, 12] 3 2 1 0 7 6 5 4 11 10 9 8 15 14 13 12 |

How to multiply a number by 7 without using + and * operators? 3 réponsesuse bit shifting. n=n<<3-n do the left.bit shift operation by 3 and then subtract the result by original number . eg: n=1 ,then n=n<<3 -n gives 7 , if n=2 ,then gives 14 |

Given 100 white marbles and 100 black marbles and two jaws. Put these marbles in the two jars in a way that would maximize the chance of retrieving a white marble from any given jaw. 4 réponsesdivide black marbles into the two jars first. then divide the white marbles on top of that in the two jars. Really that is what you would answer? What if they stirred the jars around after you distributed the marbles? Personally I think a better answer is to put 1 white marble in the first far and 99 white marbles and 100 black marbles in the second jar. If you choose the jar at random you now have a 74.87% chance of getting a white marble, regardless of the marbles position in the jar. qq is right, that is the optimum combination. Afficher plus de réponses 2 colours, 2 jars. White in one, black in the other |

Explain a situation where a deadlock would occur. 3 réponsesTwo processes each holding a resource tries to access the other's resource. Or you could forget to unlock. There are 4 conditions from Coffman's: A deadlock situation can arise if all of the following conditions hold simultaneously in a system:[1] 1. Mutual Exclusion: At least two resource must be non-shareable.[1] Only one process can use the resource at any given instant of time. 2. Hold and Wait or Resource Holding: A process is currently holding at least one resource and requesting additional resources which are being held by other processes. 3. No Preemption: The operating system must not de-allocate resources once they have been allocated; they must be released by the holding process voluntarily. 4. Circular Wait: A process must be waiting for a resource which is being held by another process, which in turn is waiting for the first process to release the resource. In general, there is a set of waiting processes, P = {P1, P2, ..., PN}, such that P1 is waiting for a resource held by P2, P2 is waiting for a resource held by P3 and so on until PN is waiting for a resource held by P1.[1][7] |