# Technical Interview Questions

interview questions shared by candidates

## Technical Interview Questions

### Sales Strat Intern at Goldman Sachs was asked...

Suppose we hire you, and you and the rest of the new interns decide to go buy a cup of coffee. Each intern purchases one cup of coffee. One of the interns suggests everyone play a game. Everyone will flip a fair coin, dividing the group of interns into two subgroups: those that got heads and those that got tails. The game is this: whichever group is smaller evenly splits the cost of everyone's cup of coffee (i.e. if there are 5 interns, 3 get H, 2 get T, then the two interns that got tails each buy 2.5 cups of coffee). However, nothing says you need to play this game. You can choose to buy your own cup of coffee and not play the game at all. The question: Should you play this game? (Note: You may assume that there is an odd number of interns, so there are no ties, and that if everyone gets H or everyone gets T, then everyone loses and just buys their own cup of coffee). 18 AnswersHint: Despite its look, this is not a math question. I dont get it, Would you please provide more hints? Assume each coffee costs $1, for simplicity. So this is effectively a choice between two outcomes: paying $1 with probability 100%, or paying $0 with some probability and paying more than $0 with some probability. So you ask yourself: what is your expected cost in the second case? Give that a try and see if you can figure it out. However, I want to remind you that the question is "should you play this game?" The answer to this question isn't just a math question. If you only work out expected values, you've missed the point. For example, a separate question (with the same kind of flavor as the direction I'm trying to lead you) is this: suppose I give you a choice of two outcomes. Either you get $1 with 100% probability or I give you $500,000,000 with probability 1/100,000,000 and 0 otherwise. Which would you pick? Now what if it was the same first choice, but the second choice was $50 with prob 1/10 and 0 otherwise? Now which would you pick? These are the kinds of things you want to think about while answering this kind of question. Let me know if you have anymore questions. And if you want me to post the answer, just let me know. Show More Responses I think I get it. It's about investor's risk appetite. Investors is likely to take guaranteed gains, here is $1. Well yes and no. This is indeed a risk aversion question. If you work it out, you'll find that the EV in each case is exactly the same (your EV is -1 cup of coffee in both scenarios) but that's not the end of it. It's also really a question for them to test your risk aversion. You can really support either answer, and *should* comment on the validity of either answer. My answer was to go with buying my own cup of coffee, and followed it up with a story where a friend of mine had tried to get us to play credit card roulette (which is similar in spirit to this game) and I told him that I did, in fact, say no in that instance and why I said no. However, traditionally people are risk-averse when faced with gains and risk-seeking when faced with losses, so many would probably choose to play the game. But this is as much a question about your psychology as it is about your math skills. And that's why this is such an awesome question, and is probably a question that kills most people they ask it to. Would you please explain to me how do you get -1 for the second scenario? There are 50% H and 50% T. Therefore players have 50% opportunity in the winning group. Given 5 interns, there are two combination of lossing group (4 vs. 1 and 3 vs. 2). EV=0.5*0 + 0.5*(0.5*-5 + 0.5*-2.5) = -1.875. The probability of winning isn't 50%. It's actually slightly above 50%, but that's not the way to look at it. The total number of coffees that need to be bought is n, where n is the number of interns. Going into this game, every intern is the same so they each have the same expected value, and the sum of the expected values must equal -n. So everyone has an EV of -1 as claimed. Thank you very much. I finally got it. I'm still not sure why you said no if the EV is the same? It's a matter of risk preference. See the example I gave in my Mar 19 posting: "Suppose I give you a choice of two outcomes. Either you get $1 with 100% probability or I give you $500,000,000 with probability 1/100,000,000 and 0 otherwise. Which would you pick? Now what if it was the same first choice, but the second choice was $50 with prob 1/10 and 0 otherwise? Now which would you pick? These are the kinds of things you want to think about while answering this kind of question." You would probably not play in the first instance and consider possibly playing in the second. (And those instances even have the risky game with a HIGHER EV). This coffee game is the same kind of game, and even if the EV is the same in each case, the volatility is not the same. It is usually a good rule of thumb to take the lower volatility outcome if the EV is the same (think Sharpe Ratio here! Or think efficient frontier here! Both get the point across I think.). Does that help? I say yes. To play the game. Only because I'm prepared if I lost. The fact that I can afford to loose, makes me want to try my chance at wining I would play the game. Consider the expected price with n total interns splitting a total cost of P. That is P/2*E[1/(N)|you're paying]. This is simply equal to P/2*E[1/(N+1)] where n is a binomial now corresponding to n-1 interns. Notice that 1/n+1 is a concave function. That means that P/2*E[1/(N+1)] <= P/2*(1/E[N]+1)=P/2 * 1/( (n-1)/2 + 1)) = P / (n +1). So it pays to play on average Apologies, but both of the above answers are incorrect. The EV of playing is the same as the EV of not playing. Show More Responses No way would I play! The most money I save is a dollar the most money I can lose ( in the case of five interns) is 4 dollars... That's a 400 percent downside verse a 100 percent upside ( kind of you cannot technically compute your return on zero dollars invested). Plus, I do not even drink coffee! Stupid...I don't have time to play games at work. The EV in both scenarios are not the same: it's clear when think about the case where there are n = 3 interns. I've already explains why they are the same. In either scenario there will be n cups of coffee bought (3 in your case) so total EV is -n (-3 in your case). In the game each person is the same as any other so their EV must all be the same. That is why in the game the EV is -1 (same as if they buy their own cup of coffee). To argue otherwise is to argue that either the total EV is not the number of coffees purchased or that someone has an unfair advantage in the game. Incidentally, if you are going to claim that someone who has given you the answer is wrong, you should provide more of a response than "go think about it." if v = pay by game -1 . Then all have five intern have same distributed V by symmetry 5EV=0 It's zero sum. |

### Software Engineer at Dropbox was asked...

Given an array of integers eg [1,2,-3,1] find whether there is a sub-sequence that sums to 0 and return it (eg 1,2,-3 or 2,-3,1) Checking every sub-sequence is O(n^2) which is too inefficient 14 AnswersShould do a running sum, storing previous sum values in a hash table along with array index if you ever get a sum value you’ve already seen, return the array indices (1+the index in the hash table, and the current index) This solution is O(n) Although the above algorithm runs in O(N) time, will it cover all cases? What about if the input array is [1,2,1,-3,-4]? In this case, the subsequence would be [2,1,-3]. I feel though that the algorithm described above will miss this subsequence since you are only keeping a running sum from the start of the array. Do you mean a subsequence (can be discontinue) or a sub array (continue)? Show More Responses Yes, the solution by Interview Candidate (do a running sum and return when you see a sum already seen) works for all cases. If the list is [1, 2, 1, -3, -4], S1 = 1; S2 = 3 (1 + 2); S3 = 4 (1 + 2 + 1) S4 = 1 (1 + 2 + 1 -3) ... since we have already seen this sum at index 1. the answer is list of numbers at [old_sums_index + 1, new_sums_index] = [2, 1, -3] [100 7 1 2 -3] the above method will not work for this array, It will work for [100 7 1 2 -3]. Index: 0, Sum = 100 (put in hashtable) Index: 1, Sum = 100 + 7 = 107 (put in hashtable) Index: 2, Sum = 107 + 1 = 108 (put in hashtable) Index: 3, Sum = 108 + 2 = 110 (put in hashtable) Index: 4, Sum = 110 + (-3) = 107 107 already exists in hashtable with index = 1. Hence we return (1+1, current index) meaning (2, 4) Doesn't work for [-1,-1,-3,4]. This looks like a classical NP-complete problem: http://en.wikipedia.org/wiki/Subset_sum_problem. And generating all sub sequences is not O(n^2) but O(n!) which is the cost to generate all permutations. It works for [-1 -1 -3 4] too. The subset sum problem allows discontinuous subsets, but this question asks for a subsequence implying no discontinuity. Here is a solution using Python 3: def findZeroSequence(list): hash = {} sum = 0 startIndex = -1 hash[sum] = startIndex # a sum of zero later in the list means the sequence starts at index 0 (== -1 + 1) for i, v in enumerate(list): sum = sum + v # print(i, ' has sum ', sum) try: startIndex = hash[sum] return list[startIndex+1:i+1] except KeyError: hash[sum] = i return [] # no subsequence print(findZeroSequence([1,2,-3,1])) print(findZeroSequence([1,2,1,-3,-4])) print(findZeroSequence([-1,-1,-3,4])) print(findZeroSequence([100, 7, 1, 2, -3])) print(findZeroSequence([-7, -3, -2, 5, 8])) Checking every sub-sequence is O(2^n) not O(n!), which is the cost for generating all subsets. Contrary to what the previous poster said, sub-sequence implies both continuity and discontinuity: http://en.wikipedia.org/wiki/Subsequence and the algorithm fails for this case: [2, 2, 1, -4]. How about these: [1,2,-3,4] or [-3,3,1] ? May be user should check for zero also? def hasSubSeqOfZero(a): if not a: return [] partialSums = {} partSum = 0 for i in range(len(a)): partSum += a[i] if (partSum in partialSums): return a[partialSums[partSum] + 1: i + 1] if (partSum == 0): return a[:i+1] partialSums[partSum] = i return [] Show More Responses public int[] ssz(int[] nums) { if (nums == null || nums.length == 0) return null; Map map = new HashMap(); int sum = 0; int index = 0; for (int n : nums) { if (n == 0) return new int[] { index, index }; sum += n; if (map.containsKey(sum)) { return new int[] { map.get(sum) + 1, index }; } map.put(sum, index); index++; } return null; } |

Implement a power function to raise a double to an int power, including negative powers. 11 AnswersCould be implemented many ways. I got the feeling that the interviewer wanted to see you approach the problem in multiple ways and demonstrate confidence in your math and recursive skills. #include #include #define MAX_ARRAY_LENGTH 256 double power(double, unsigned int); int main(int argc, char** argv) { double a = atof(argv[1]); int b = atoi(argv[2]); double result = power(a, b >> 31 == 0 ? b : -b); if ((unsigned int) b >> 31 == 1) { result = 1 / result; } printf("%f\n", result); return 0; } double power(double a, unsigned int b) { switch (b) { case 0: return 1.0; case 1: return a; default: return (b & 1) == 0 ? power(a * a, b >> 1) : power(a * a, b >> 1) * a; } } c implementation of the above (no recursion): int ipow(int base, int exp){ int result = 1; while(exp){ if(exp & 1) { result *= exp; } exp >>= 1; base *= base; } return result; } Show More Responses int power(double n, int exp) { bool npower = (exp < 0) ? true : false; double result = 1; exp = abs(exp); // get the absolute value for (int i = 0; i < exp; i++) { if (npower) { result = result/n; } else { result = result*n; } } return result; } C# code verified: static double Power(double d, int exp) { if (d == 0 || exp == 0) { if (exp >= 0) { return 1; } else { return double.PositiveInfinity; } } int expAbs = Math.Abs(exp); double res = d; for (int i = 1; i 0) ? (res) : (1 / res); } double power(double x, int y) { if(y == 0) return 1; int sign = 1; if(y < 0) sign = -1; y = abs(y); double d = power(x, y/2); if(y%2 == 0) d = d*d; else d = x*d*d; if(sign == -1) return 1.0/d; else return d; } I am surprised that not a single person here had noticed that the guy asked to raise a DOUBLE to a given power. Men, double are not integers. Their exponent is stored in a part of their binary representation. If you multiply n times a double you will make n times a rounding error and n useless calculations. Just changed the binary part of the double that is related to its exponent, and here it is, your double has been raised to a given power, a you absolutely lost no precision, and you've made 0 calculations. This is basic stuff, every university teaches that to its students... floating numbers representation... I believe interviewer is expecting for this public static double Power(double x, int y) { double result = 1; bool isNegative = y 0) { if ((y & 1) > 0) { result *= x; } y = (y >> 1); x *= x; } if (isNegative) result = 1 / result; return result; } Verified C# static double Pow(double b, double exp) { if (exp == 0) return 1; else if (exp > 0) return b * Pow(b, exp - 1); else return 1 / Pow(b, -exp); } Does it get more compact? TD's answer is interesting, but not very useful. If you actually try it you'll find that since the double's base is 2, any changes to the exponent portion approximately multiply (or divide) numbers by a power of two. I say approximately here, since TD forgot to mention that the number itself isn't stored in float point numbers, only the digits after the implied 1. So yes, it's important to know how floating point numbers work, but modifying the exponent portion of a floating point number is a fundamentally incorrect solution. public double power(double num, int exp) { if(exp == 0) return 1; double res = 1; for(int e=Math.abs(exp);e>0;num*=num,e>>=1) { if( (e&1) == 1) res *= num; } return (exp>0)?res:1.0/res; } |

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

Write a function that divides two numbers without using the divide '/' operator. 11 AnswersI had to use recursive subtraction or addition. But, I think I took too long a time to figure out the fastest code and I was typing it out in google docs while the interviewer was on the phone with me. I was nervous. It was my first ever interview. But, it was a heck of a experience. X * Y^(-1) One way is to iteratively count the number of times Xn = Xn-1 - Y >= Y. No recursion needed. Also, if Y is a power of 2, you can use a right-shift to get the answer...even faster. If the number space is sufficiently small, you can use a lookup table. Show More Responses int positionOfFirstAndOnlyBitSet(int m) { int pos = -1; int x = 0; for (; x > x) & 1) if (pos == -1) pos = x; else return -1; // found more than one bit } return pos; } int divide(int n, int m) { if (m == 1) return n; if (m == n) return 1; if (m > n) return 0; int pos = positionOfFirstAndOnlyBitSet(m); if (pos != -1) return n >> pos; // how manny times one can multiply m before going over n int x = 1; int mm = m; while (mm <= n) { mm += m; x++; } return x - 1; } assuming you want to be able to handle doubles, I like the idea of x * pow(y,-1.0); ... why make the answer more difficult for yourself than it needs to be? I got this question in facebook interview as well. You usually are not allowed to use floats, or pow(), or % And also you have to consider both +, - integers, so Steve M answer is not valid. public static int divide(int a, int b) { if(a < b) return 0; int div = b; int k = 1; while((div<<1) <= a) { div = div<<1; k = k<<1; } return k + (div == a ? 0 : divide(a-div,b)); } int num; int div; int rem; // assume only positive numbers for(i=0; num>=0 ; num-=div) { i++; rem=num; } printf("\ni: %s%d rem:%d", i, rem ); Victor, whats the complexity of your solution ? Binary search will work ? Let's say you need x/y. And only integral solution is needed i.e. 10/3 = 3 , not 3.33. This won't work if we need float as a result Pseudocode If x > 2) if mid*y == x : return mid if mid*y > x : hi = mid - 1 else: lo = mid + 1 return lo -------------------- Actually, it's quite simple. Recursively! function addTwo(x,y){ if (y === 0) { return x; } return addTwo( x ^ y, (x & y ) << 1); } addTwo(2,3) // 5 OR do it iteratively function addTwo(x, y) { // Iterate till there is no carry. while (y !== 0) { // Carry now contains common set bits of x and y. carry = x & y; // Sum of bits of x and y where at least one of the bits is not set. x = x ^ y; // Carry is shifted by one so that adding it to x gives the required sum. y = carry << 1; } return x; } |

### Software Development Engineer at Amazon was asked...

List all anagrams in a file. Assumptions: case-insensitive, a-z characters only, one word per line. For example, if the file contains dog, cat, ddd, goo, act, god -- output dog, god, act, cat 10 AnswersThankfully I was taking a theory course and one trick used in the course was "encoding" programs as a large natural number using product of primes. 1. Adapt the encoding as follows -- generate the first 26 primes and assign a prime to each letter 2a. For each word, take the product of each letter's prime. So #(act) = 2*5*prime(t) 2b. As you can see, #(cat) = 5*2*prime(t) = #(act) 3. Insert a handwavey argument about inserting the number/word pairing into a HashMap> Sort the words. Anagrams appear next to each other in the sorted list. Sorry, sort the letters in each word, then sort the words. Anagrams appear next to each other in the list. For example the sorted list for the input would be: act act ddd dgo dgo goo Show More Responses Thanks for sharing Bill For this set of input, the expected output should contain only [cat, act, god, dog]. I'm curious to see what "next steps" your algorithm will perform to provide this expected output You keep track of the mapping from the sorted word to the actual word in a pair, for example: [act, cat] [act, act] [ddd, ddd] [dgo, god] [dgo, dog] [goo, goo] Then you go through this list and count if you have a duplicate entry or not. If you do, like for act, you print out those duplicate entries: cat, act. Bill, your algorithm is O(n*log(n)) while the candidates would be O(n) - provided he uses a decent hash function donutello, bills algo is not n log n it is n*log(k) where as candidates algo is n * k again (multiplications for each word) where k = length of the longest word on top of that calculating primes is expensive anyway I would go with bills answer Bills algo is nlogk + nlgn. After sorting the k letters for n times you also have to sort the n words. #Get inputs a = [] f = open('input.txt','r') for line in f: line = line.strip() a.append(line) #Sort letters in a word def sort_letter(s): r = [] for i in s: r.append(i) t = sorted(r) v = ''.join(t) return v #Find anagrams d = {} for v in a: sv = sort_letter(v) if sv in d: d[sv].append(v) else: d[sv] = [v] #Print results for k,v in d.items(): if len(v) > 1: for s in v: print s think of each line as a set of characters, not a word, then create set of sets of characters which you fill from the input. then print the set (order does not matter as its not specified) |

### Assistant Trader at Five Rings Capital was asked...

You are standing beside a road watching cars pass by. The probability that you see a car pass by in 1 minute is 1/4. What is the probability that you see a car pass by in 30 seconds? 8 Answers1-sqrt(3)/2 why is this let p=probability that you see a car in 30 seconds p(see car in first 30 seconds)=p p(see car in second 30 seconds)=p p(see car in the first 60 seconds)=2p-p^2=1/4 solving you get p=1-sqrt(3)/2 (reject 1+sqrt(3)/2 since it's over 1) Show More Responses I have a question on this solution: 1-(1-p)^2 is the probability of seeing at least one car, not the probability of seeing a car. You can also solve this using exponential distribution. From the question, you can deduce that the distribution has to be memoryless and hence there has to be a constant rate per unit time for the event to occur. Let the probability per unit time of a car passing by be p. Then from the given information 1/4 = 1 - e^{-p*T} The required answer is e^{-p*T/2} which gives the answer as reported above. Minor correction in above. The required answer is 1 - e^{-p*T/2} ans 1/2 as the person sees car in 15 sec of each 1 minute if we divide 1 minute into 4 parts (60/4 = 15 secs) s the probablity of seeing car now we are asked in 30 sec . the rate of moving of car will not change it will still continue to come at a rate of 1 in each 15 sec so the ans for each 30 sec would be 1/2 if we divide 30 into 2 parts . so in 15 sec one car is left .but for next 30 sec no car is going to come then itls probability would be 0 . now the ans is tricky which 30 secs are asked , the 30 sec in which car is seen or in which it is not seen by the man 1 - sqrt(3)/2 is the wrong answer |

### Summer Analyst at Goldman Sachs was asked...

13 cubed 6 Answers2197 how long did it take you to answer this? I assume thats what they were testing I did it while doing some chit chat about his day. No longer then two minutes, and then he asked how I did it. So I explained the steps. Show More Responses really easy on paper, in your head, not so easy. In your head, here's how I'd do it: 13 squared is 169- that's easy. then, 10 times 19 is 1690, and 3 times 169 is approx 500, so 2190 is an easy approximation. Only 7 off from the actual answer! 13*13 = 169. Then do 13*170 = 10 * 170 + 3 * 170 = 1700 + 510 = 2210 Then, 2210 - 13 = 2197 Do it on your head. 13*13 = 169. For 169*13 first 3*169 = 507 second 10*169 = 1690 Finally 169*13 = 507 + 1690 = 2197. |

### Software Development Engineer at Amazon was asked...

What are the first 2 integers that, when added together, equal 10 in a "very large" array of unsigned integers? 6 AnswersMy in-interview answer was bad!!! I came up with a better one using a 2d array with 11 rows and 2 columns. First column to hold the first occurrence of each integer 0-10 (conveniently, the indices of each row match a relevent integer) and second column to hold the second occurrence of 5. When you first encounter an integer that can be used to equal 10, add the index to the first column. When encounter 5 for the second time, add it to the second column. Each time you update a value, check to see if both sides of the equation are populated...if so, you have your answer, if not continue on with the original array. Note: Adding the index enables you to keep track of WHERE the integers were in the original array, however if that doesn't matter, you could update it with any value that works for your evaluation logic. It's a specific case of the problem of finding two integers that add up to a given number in a list of integers. In general case, you do need to sort first and use two pointers from start and end and use an elimination to search in O(n). In this case, since sum is already given (a constant) we just need to maintain last unique indices of integrers <= 10. Any time we find two that adds up to 10 is the answer. if it is a "very large" collection, avoid sorting; i think we are creating a time consuming cycle there. i have given a little piece of code for a similar question in this forum itself, which can be used as a starting point for bettering your answers. i got this question few years ago, when i went for an interview, with a bay area network security company.. as a UI developer !! Show More Responses should not sort it. Create an array or length 11 (index of 0-10), call it H, fill it with null (you can use -1 as null) Call original array A. Code is very simple: i = 0 while(i++) complement = 10 - A[i] if(H[complement] == null) H[complement] = i else break at this point A[H[complement]] + A[i] == 10 I'm essentially using H as a hash table where hash(n) = n this solves the problem in O(n) I believe. I think hashing is preferred in this case. @maxzed2k I'm not entirely sure if your solution will cover all cases. What if the complement (i.e. 10-A[i]) is negative? H[ ] will give you a segmentation fault. |

Suppose you have two covariance matrices A and B. Is AB also a covariance matrix? Suppose that, by plain dumb luck, we also have that AB=BA. Is AB a covariance matrix under this additional condition? 12 AnswersI suppose it's clear from how I wrote the question that the answer to the first question is no (for you: why?). For the second question, this is a little bit harder if you aren't experienced in linear algebra. I actually have a PhD in algebra, and the interviewer also had a PhD in algebra, so on some level this question might have been specifically targeting my background. There is a standard result that applies here; see if you can figure it out. 1. no 2. no, give an example where diagonal positivity is not true. 1 is correct, 2 is wrong. Try again. :) Show More Responses 2. Just checked Wikipedia, AB is cov matrix because it is symmetric semi positive definite. Is it right? If AB=BA then yes it is symmetric. So the question boils down to: Is it in fact positive semi-definite? Why or why not? Work through that and you have your answer. My hint: Take a look at some results related to diagonalizing matrices that commute with each other. Hi for your telephone interview with doug, what was the focus for technical interview parts, everything from math, finance, programming? or mainly probability type of question? thanks I remember it being mostly probability and finance. Nothing too terrible. Hi Mr.interview candidate, what were the types of finance questions Doug asked? Thanks! Hi, Mr. interview. Do you remember what kind of data analysis example was for on-site interview? If so, can you share a little bit? What was the level of difficulty? Thanks! 1, no 2, yes How does the first one not contradict this: https://math.stackexchange.com/questions/982797/prove-that-the-product-of-two-positive-semidefinite-and-symmetric-matrices-has-n It doesn’t. It provides an alternative way of establishing that the eigenvalues must be nonnegative. In fact, if you read the proof, all that’s established is that AB is similar to a positive semidefinite matrix and therefore must be positive semidefinite. It says nothing about whether or not AB is symmetric (which is also required for AB to be a covariance matrix). |

### Software Engineer at Facebook was asked...

find 3 elements in an array that sum to 0. 6 AnswersI would construct a hash of all entries in the array and then iterate through a 2d product of all elements in the array and see if that sum was in the hash as first mentioned. Any comments ? @Richard no, that's not the way to do it actually. Your naive solution would take a N^3 / 2 complexity. A N^2 lgN complexity can be achieved if you first sort the array. A pair a[i] and a[j] is part of a triple that sums to 0 if and only if the value -(a[i]+ a[j]) is in the array(and not a[i] or a[j]). You need to sort the array, then do N (N - 1)/ 2 binary searches that each take time proportional to log N, for a total running time proportional to N^2 log N. Here's an example in java : http://algs4.cs.princeton.edu/14analysis/ThreeSumFast.java Thanks for the comment. However, I'm not sure how I am that far off.. If you just replace my hash with an ordered array, then essentially it's the same algorithm. How did I get to n^3 though .. I take it on board that a hash array take longer to construct than an ordered list in which to do a binary search - is that the additional order of magnitude? Show More Responses Richard, The solution using a Hashtable is better, because its time complexity would be O(N^2). public void sumIsZero(int[] a){ int n = a.length; for(int i=0; i More elegantly, RIchard is correct. Compute the 2sum (N^2/2 +N/2 operations) and store it in a has table (potentially O(1)) or sort the answer (potentiall O(n\lg n)). For each element in the list, look up the negation in this list (O(n) for has tables, O(nlg(n)) for sorted arrays). |