# Questions d'entretiens - Software engineer

# 365 k

Questions d'entretien pour Software Engineer partagées par les candidats## Principales questions d'entretien

### Suppose that you earn 100% annual interest (APY) on $1 initial deposit. How long before you'll be as rich as Bill Gates ($63 billion)? Given a number, e.g., 314159, as an array [3,1,4,1,5,9], increment it: change it to [3,1,4,1,6,0].

17 réponses↳

Taking just the information we are given and ignoring taxes etc. 100% annual (compound) interest is the same as doubling your investment every year. So for the first four years it would go like this: $1, $2, $4, $8, $16, $32, ... Look familiar? Therefore: 63 Billion = 2^x or x = log2(63 billion) In an interview we wouldn't be able to throw this into a calculator so we would need to do it by hand. We can estimate powers of 2 as powers of 1000: 2^10 ~= 1000^1 2^20 ~= 1000^2 etc. Therefore 63 billion = 63 * 1000^3 or approximately = 63 * 2^30 We know that 64 is 2^6 so we can substitute that with the 63 to get: 2^6 * 2^30 which = 2^36 log2 of 2^36 is 36 Therefore you would have $63 billion after 36 years. Now if we validate with the calculator we see that after 36 years we would actually have about $68/$69 billion. While if we only waited until 35 years we would only have $34 billion. Moins

↳

It toke ^ 10 to for 2 to reach 1k. So it will take ^ 30 to reach 1b. Then u need another ^ 6 to just pass 63b. S the answer is 36 years. Moins

↳

Possible Java Array Incrememnt Function

### you have a sequence where each number is a multiple of 2 or 5 (so: 2^i * 5^j). he gave the beginning of the sequence as 1,2,3,4,5,8,10,16... and asked me to find an algorithm to calculate the next number in the sequence.

16 réponses↳

There are two sets: - Set-I is powers of 2 {2, 4, 8, 16, 32, 64....} Set-II is powers of 5 {5, 25, 125....} Set-III is composite function of both the above set {10, 20, 40,50, 80.......} Now start with Set-I and keep on displaying it until it is less than 1st element of Set-II ans Set-III or otherwise display an element of Set-II or Set-III which ever is less. Note:- Set-III is formed by multiplying Set I and Set II in sorted manner. (A code snippet is required to generate it) Moins

↳

How is 3 (the third number in the sequence) equal to 2^i * 5^j? Is 3 supposed to be there, or is it a typo? Moins

↳

At a second glance, the sequence is surprisingly simple. It is merely the set of all numbers 2^i * 5^j in ascending order (where i, j >= 0). The above answer can be implemented by a stack sorted in ascending order. Start off with 1, multiply it by 2 and 5, and put the products in the stack. Then go through each element in the stack, multiplying it by 2 and 5 and putting the products in the stack. (However, you don't want to insert duplicate entries, so you'd need to check for that while inserting the entries, but that wouldn't reduce the space/time efficiency.) Anyone with more efficient solutions? Moins

### Implement a function rotateArray(vector<int> arr, int r) which rotates the array by r places. Eg 1 2 3 4 5 on being rotated by 2 gives 4 5 1 2 3.

16 réponses↳

public static void rotateArray(int[] in, int r){ int i =0,j = in.length -1; reverseArr(in, i, j); reverseArr(in, 0, r -1); reverseArr(in, r, j); } public static void reverseArr(int[] in, int si, int ei){ int i =si,j = ei; while (i <= j){ int tmp = in[i]; in[i] = in[j]; in[j] = tmp; i++; j--; } } Moins

↳

def rotate(vec, r) : if r <= 0 : return vec L = len(vec) r %= L (cnt, beg) = (0, 0) while cnt < L : cur = beg tmp = vec[cur] while True : next = (cur + r) % L tmp1 = vec[next] vec[next] = tmp tmp = tmp1 cur = next cnt += 1 if cur == beg : break beg += 1 return vec Moins

↳

http://baibingz.wordpress.com/2012/10/26/rotate-array/ O(n) Time O(1) Space

### 1. Phone interview - Sort the characters in string by frequency and then by their alphabetical order. Example - bbaaccc -> cccaabb 2. The question that screwed me - given array is [0,1,1,0,1,1,1] ; output should be [0,1,1,0,1,2,3] ie., for every non-zero element in array, find its distance to the nearest zero in O(n) time. i would definitely encourage the candidates who read this post to share their solution for this question. 3. In order traversal of Binary search tree related (the solution is to start from right sub tree).

16 réponses↳

Missed the explanation. This is O(n) time complexity with O(1) space complexity. Basically this algorithm iterates through the input vector and records the incremental integers when 0 has been found. When you find 0, trace back to change the distance. If there's no 0 in the input vector, you will see -1 in the distance. This is sort of thing you need to discuss with the interviewer what to do when distance is unknown. std::vector dist(std::vector& value) { std::vector output(value.size()); int last_zero = -1; for (size_t i = 0; i < value.size(); ++i) { if (value[i] == 0) { int rewind = (last_zero == -1)?i:((i - last_zero) / 2); for (int j = 1; j <= rewind ; ++j) { output[i-j] = j; } last_zero = i; } else { output[i] = (last_zero == -1)?-1:(i-last_zero); } } return output; } Moins

↳

-> traverse left to right and make a temp1 array -> traverse right to left and make a temp2 array -> pick lower number at every index from temp1 and temp2 array to make result array Moins

↳

def findAndSetNearestDist(arr): n = len(arr) lastZeroIndex = -1 for index, a in enumerate(arr): if a == 0: if lastZeroIndex == -1: lastZeroIndex = index continue else: twoZeroDistance = index - lastZeroIndex for i in range(int((twoZeroDistance/2) + 1), index): arr[i] = abs(index -i) lastZeroIndex = index continue if a > 0 and lastZeroIndex != -1: dist = index - lastZeroIndex arr[index] = dist return arr Moins

### If I put you in a sealed room with a phone that had no dial tone, how would you fix it?

16 réponses↳

If you put me in a sealed room, I'd be more concerned about running out of air than I would be with getting a dial tone on a phone. I'd use the phone as a club to try to break out of the room before my air ran out. Then I'd use it on the interviewer who sealed me in the room. Moins

↳

It is a cell phone. It does not have a dial tone. (My assumption is as good as the question's.) Moins

↳

This is a great opportunity to use the "5 Whys" a Japanese approach to finding the root cause of (quality) problems: 1. Why ... does the phone need fixing (assuming no dial tone is an identified problem) Ans ... to talk to someone. 2. Why ... do you need to talk to someone? Ans ... to get help 3. Why ... do you need help? Ans ... to get something done 4. Why ... what needs to be done? Ans ... etc. 5. Why not ... see to THAT problem; the phone (if working) is only ONE tool to fix the ultimate problem. Now that you have a better idea of what the problem is, you can find another even better tool since you will have cut-out a less productive step fixing a phone that only marginally takes you forward. What interviewer wouldn't be impressed with so contemporary, thorough and cool approach? Afterall, the Japanese developed it. BTW if the room were sealed, you'd probably be dead and the interviewer elected to high government office. Moins

### You're given a string, and you want to split it into as few strings as possible such that each string is a palindrome.

15 réponses↳

Reversing the string and looking for common substrings will give false positives. Consider this string: ABCDEXYEDCBA It has no palindromes greater than length 1. Reversing it we have: ABCDEYXEDCBA The longest common substring is ABCDE. It's falsely identified as a palindrome. What we should be looking for is a common substring which emanates in both directions *from the same position in the string*. That's where a suffix tree comes in handy. Also, the greedy algorithm of finding the longest palindrome first can produce incorrect results. See my comment above (Nov 22) for an example. Moins

↳

Here is a simple way to build the set of all palindromes in O(n^2) time. What you do is you take every character (or two adjacent characters) and find all palindromes such that your character is in the middle. It's pretty easy to see that you can do this in O(n) time to find all palindromes with a given character in the middle, because if you have a palindrome then knocking a character off each end leaves you with another palindrome. Therefore it takes O(n^2) to find them all. Then, as others have mentioned, you can use dynamic programming to find the best covering. Moins

↳

You can find all maximal substring palindromes in O(n) using a generalized suffix tree. After that, you can use a dynamic programming algorithm to find an optimal way to split the string into the fewest palindromes: OPT(i) = min(1 + OPT(j-1) | substr(j,i) is a palindrome) This has a worst case O(n^2) running time, although with some optimizations (based on deciding which palindromes are worth trying) we can make it run in O(n) on average. Of course, the constant in that running time is probably rather bulky :P @vsp,jerom: I think you'd be onto something if we were allowed to rearrange characters in the string, but I don't think that's what the question is asking o_O Moins

### Aptitude questions were from the topics like Discounts, Profit or loss, Boats and streams, Work ,Pipes,Finding X and Y, Numbers, Ratio and Proportion. And all the programming questions were only from C language.

16 réponses↳

Programming questions from c...

↳

These were the questions we faced on round 1. You are supposed to predict the output for the given program... 1. preprocessor some thing like #define sqt(x) x*x main(){ i=64/sqt(4)} 2. various form of array notation like s[ i ], *(s+i), *(i+s), i[s] 3. based on increment operation on pointer. eg. char *s="asdf"; s++; print s++; print s; 4. string.h based ques. eg. char s1[]="asdfasdf",s2; strncpy(s2,s1,3); 5. print char array from n th position to 0. ie. consider previous ques s1[] now just print char from s1[8] to s1[0] using for loop. 6. switch statement with no break except in default statement, enclosed within a for loop, some thing like the below one main(){ int i=1; for (i=1;i<20;i++) { switch(i) { case 1: i+=2; case 2: i+=3; case 3; i+=4; default: i+=5; break; } } printf ("%d",i); } 7. nested function with a static int variable. it has 2 return statement in it one executed on a condition. 8. print sizeof(++i + ++i) considering i as a int of size 2bytes, as sizeof() will perform no arithmetic operation in it, it just print 2. 9. struct base question which as some thing like struct{ int a1:1; int a2:2} and it goes on something like that... 10. bitwice operation performed on int.. i dont remember the question but the result ended up as 1,1,0 Moins

↳

If results came please share...

### They just emailed me a word document with interview questions and after I sent it back, they said will contact me after an hour and sent me an email saying they will hire me and send the details soon.

16 réponses↳

What kind of questions was in the word document they send?

↳

I got a similar email on 19th June, regarding an interview on Monday.

↳

Yeah me too

### Find a sequence with max sum in an array of negative and positive real numbers.

15 réponses↳

Given an array a[n], find the subsequence with the greatest sum (without reordering the elements). Let p[i] = the max sum of elements up to and including a[i]. It may or may not include a[i-1], a[i-2], etc. but it must include a[i]. Then p[i+1] = max(a[i+1], p[i] + a[i+1]). The basis is p[0] = a[0]. This recurrence is simple enough to perform in O(n) time and O(1) space. At each step, we need only decide whether to extend the current run or start a new one. float bestsum = sum = a[0]; int i, besti = 0; int len, bestlen = 1; for (i = 1; i bestsum) { bestsum = sum; besti = i; bestlen = len; } } printf("Elements %d through %d sum to %g\n", besti, besti + bestlen - 1, bestsum); Moins

↳

The answer to this problem is the submaxarray algorithm. Find it here: http://en.wikipedia.org/wiki/Maximum_subarray_problem Moins

↳

If the minimum sequence length is 2, then it's still possible to solve in O(n). Briefly: float sum = a[0] + a[1]; float bestsum = sum; for (int i = 2; i bestsum) bestsum = sum; } return bestsum; Moins

### Given a list of n objects, write a function that outputs the minimum set of numbers that sum to at least K. FOLLOW UP: can you beat O(n ln n)?

15 réponses↳

I believe the closest answer to the correct one is birdy's. You're supposed to partition around a random element x, and get the sum S of all elements larger than x. if S is larger than K, you recurse on the subarray of the elements that are larger than x. if S is smaller than K, you recurse for S-K on the subarray of elements that are smaller than x. The worst case running time of this algorithm can be O(n^2), but it will be O(n) on the average. The probabilistic proof of that statement is not very easy, but the intuitive idea is that most of the time, the partition will be more balanced than a (1,10) ratio, and this enough to make the subarray sizes bounded by a geometric sequence of ratio less than one, which will guarantee you a linear time algorithm. It is also possible to get a worst case linear time algorithm by adapting the algorithm given here: http://en.wikipedia.org/wiki/Selection_algorithm to the weighted case, but this is really overkill and,in practice, the resulting algorithm will be slower than the randomized algorithm I described. Moins

↳

import random def minimum_numbers(lst, l, r, k): '''returns list of minimum amount of numbers which sum is greater than k''' if l + 1 == r: return [lst[l]] elif l == r: return [] x = random.randrange(l, r) val = lst[x] lsum = 0 rsum = 0 b = l e = r while b val: e -= 1 t = lst[e] lst[e] = lst[b] lst[b] = t rsum += lst[e] else: lsum += lst[b] b += 1 if lsum + rsum = k: return minimum_numbers(lst, e, r, k) else: return minimum_numbers(lst, l, e, k - rsum) + lst[e:r] Moins

↳

You could solve it in deterministic linear time using a combination of linear-time selection (median-of-medians solution) and binary search. At each iteration, find the median of the array being considered and partition around it. If the greater half sums to K, return it. If it sums to less than K, store all elements of the greater half and recurse on the lower half. Otherwise, recurse on the greater half. Once you get down to considering a small enough set, just sort and finish off the problem. We have to perform linear time selection and linear partition on n + 1/2n + 1/4n + 1/8n +... elements, which sums to 2n so O(n) running time. Moins