Technical Interview Questions

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.

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.

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).

More specifically, you would be given a list of words in the ciphertext which are in alphabetical order. Your job is to determine the alphabetic order of the ciphertext letters. In a graph, each node would represent a letter, the directed edge would indicate ordering of the two letters it connects. Once the graph is built you can do a simple traversal of the graph to generate your alphabetical ordering. Hope that helps!

I think I didn't get the question. Could someone elaborate on it a bit please?

@Alexander An example of what I believe the question is presenting to the applicant is as follows. Say I knew one of the words was 'CAT'. Now, if I look at the scrambled 3 letter word, and it was ZBS, then I know that C = Z, A = B, and T = S. Essentially, potentially every letter in the alphabet (up to 26 letters in total) are not of the same value. So, if I had another example word, say 'TACS', and the given scrambled word is 'SBCY', then I now know that S = Y as well. This is not an explanation of how to approach the problem, as we're not given any sample words; This is simply my interpretation of how the question is supposed to be interpreted as @Alexander is probably not the only person who does not understand the question. Of course, I could have it wrong too, so who knows.

http://www.careercup.com/question?id=19114716

mod and div operators are good, but you could set yourself apart by using a more efficient algorithm. In terms of big O, it will be the same, but it will have a higher throughput since the operations are slightly faster. > bool is_odd_set_bits(unsigned number) { bool result = false; int n = number; while(n != 0) { result |= ((n & 0x01) == 1); n >> 1; } return result; } masking is faster than a mod operator, and bit shifting is faster than divisions

i was trying this in java and found kinda small bug... so we should return false if the number is 3 which is 0000000011. I guess changing the line to: result ^= ((n & 0x01) == 1); will do the job...

PC, your solution is incorrect. It will always return true if the number has at least one set bit.

B, you're mistaken. Imagine the top three fastest horses are Santa's Little Helper, Yojimbo, and I'm Number One. By random luck, in your first race, the five random horses you choose includes all three of those. I'm Number One wins and goes on to the final race; the other two do not.

8 5 top horses from each race of 5 races (25 / 5) 5 top contenders race; 1 wins--that's one top horse (5-1) 4 remaining top horses race, one wins; that's 2 top horses (4-1) 3 remaining top horses contend; winner is #3 That's 3 top horses from 8 races

Race#1 Race#2 Race#3 Race#4 Race#5 A1 B1 C1 D1 E1 A2 B2 C2 D2 E2 A3 B3 C3 D3 E3 A4 B4 C4 D4 E4 A5 B5 C5 D5 E5 Race#6 A1 B1 C1 D1 E1 Let's Say ranking 1st 2nd 3rd 4th 5th Eliminate D1 E1 D2 E2 D3 E3 A4 B4 C4 D4 E4 A5 B5 C5 D5 E5 Left with B1 C1 A2 B2 C2 A3 B3 C3 Eliminate C3 as there are more than three faster horses C2, C1, B1, A1 Eliminate C2 as there are three faster horses C1, B1, A1 Eliminate B3 as there are three faster horses B2, B1, A1 Left with 5 horses for Race#7 B1 C1 A2 B2 A3 So 7 races

7 races. put 25 horses in 5 group. and we will have 5 sorted list of horses in each group. put 1st place horse in each group, and we will have a sorted list X. X_1 is the 1st place horse, and X_2 is 2nd place horse's candidate, X_3 is 3rd place's candidate. 2nd place horse in X_1's group is candidate for 2nd place, 3rd place one is candidate for 3rd place. and 2nd place horse in X_2's group is a candidate for 3rd place. that's 5 horses in total, 2 from X_1's group, 2 from X_2's group, X_3. race them, and 1st place is 2nd place, 2nd place is 3rd place horse.

8

the answer is one race as the question doesn't specify all the horses have to run in separate races.

uh... int heads = 13; for (int bullets = 0; bullets < heads; bullets++ ) { int n = bullets; puts(((char*)&n)[0]==n?"Y":"N"); } gives: Y Y Y Y Y Y Y Y Y Y

int heads = 130; for (int bullets = 0; bullets < heads; bullets++ ) { int n = bullets; puts(((char*)&n)[0]==n?"Y":"N"); } gives: Y Y .... .... N // 128 bullets N // 129 bullets (overflows the signed char)

Not even close guys. The code as written is not portable and invokes implementation-defined behavior. The problems involve whether or not a pointer to char corresponds to a pointer to unsigned char or pointer to signed char. char can be either and it is left up to the implementation. It is important because not all bits are value bits. An implementation can encode a signed char with value bits + pad bits + sign bit and conversion between pointer to int to pointer to char is not guaranteed to produce a meaningful value of the destination type. unsigned char has value bits while something like an unsigned int can have both value bits and padded bits. All that means, is that you can't go about mucking around with bit patterns and converting them between pointer types where the pointer type is not an allowable type to be converted to as outlined by the ANSI/ISO/INCITS standard that defines the abstract machine for the C programming language (9899:1990) and (9899:1999). A lot of this is also very similar to the C++ language so it also holds.

You can prove by induction, probably simpler. If the list only contains 1 member, probability is 1/1 = 1, which is correct. For the induction step, consider what happen when k-th member is encountered: case(a): for the k-th member, probability of being picked is 1/k, which is what we want. case(b): for each of the previous (k-1) members, probability of being picked become P(k-th not picked) * P(original, i.e. 1/(k-1)) = (k-1)/k * 1/(k-1) = 1/k, which is what we want. [] It is more fun if we were to picked m members at random, then the prove becomes less trivial (though almost equally as straightforward).

Thank you for the clear, concise explanation, Shards! I get everything except for one part: P(being picked) = P(k-th not picked) * P(original) Where does that come from? Is that a probability rule? If you could point me to a link on the web (or even what keywords to search on Google), that would be much appreciated. Thank you!

Just run rand() function to get a number for each member, always keep the member with the minimum number associated with it. Need a little extra effort to handle tie case.