If you are majoring in Computer Science, chances are you’ll be working with jobs that require some degree of programming. When you’re looking for a job in the market, you’ll be having a lot of interviews. Interviewer loves to challenge you by asking some technical interview questions. There are 3 types of technical questions in general:

1) Algorithms/Data structure

2) Programming language-specific / General CS knowledge

3) Brain teaser

I’ll go over with more details on each of them:

1) Algorithms/Data structure

You should understand these topics deeply from a typical data structure course: Array, Linked-list, Binary tree, Hash table… You should be able to tell when to use an array vs. linked-list, implementation details of linked list such as reversing a list…

Interviewer typically test your problem-solving ability by asking algorithmic questions. Some examples are:

– Reversing the words in a sentence.

– Reversing the letters in a word. (Try both iteration and recursion solutions)

– How to find duplicate data in a list.

– Generating permutations of n digits. (hint: recursion)

– Find the median of combination of two sorted arrays of numbers. (hint: divide and conquer)

– How to spell-check and correct a word (hint: edit distance)

2) Programming language-specific / General CS knowledge

If you’re applying a C++ programmer position, be prepared for lots of C++ questions. Same with other languages. If the position you applying does not have a language-specific role, you may be asked general CS knowledge, such as difference between allocating on a stack and heap, …

Some C++ related questions I encounter often:

– What are virtual functions? How is it implemented? What are the trade-offs using virtual functions?

– What is a virtual destructor? When do you need them? What if you don’t implement a destructor as virtual?

– What is copy constructor and when is it being called?

– What’s the difference between malloc and new?

3) Brain teaser

Some interviewers like to ask a brain teaser question to end the interview ðŸ™‚ You’ll know it when they ask: Do you like puzzles? Prepare for some creative thinking ðŸ™‚

Some sample questions:

– Two eggs problem:

You have two identical eggs and you are given access to a 100 story building. You would like to know the highest floor for the egg not to break when dropped. The problem is the egg might break on the 1st floor, or even the 100th floor, you just don’t know. Find the maximum number of trials you need to conduct in order to find the answer.

– Reverse the bits in one byte data as fast as possible.

– You have 5 identical jars. 4 of the jars contain balls with identical size weighing 10g each, while 1 of the jar contains balls weighing 9g each. You are given a digital scale, find out the 1 jar that has the 9g balls with only 1 weighing.

Interview tips for programmers,
what is the solution of the very last question(5 jars)? thanks –mitbbs

0Pick one ball from jar1, 2 balls from jar2 and so on till 5balls from jar5,weighing them.

Total no of balls=15. If there is no defective balls total weight should be 150gm but since 1 jar is faulty, so total weight is less than 150. Let us assume the weight is 146gm(u can choose any one from 145 to 149). Since total weight is 4gm less than actual weight then the jar4 is the faulty jar bcoz we pick 4 balls from jar4 having 1 gm less than the original.

+14I'll give you hints instead of spoiling the fun:

Try to get different number of balls from each jar and put it on the digital scale. Let me know if you are still stuck.

+1The first and the last brain-teaser questions appeared in The Algorithm Design Manual

0I am still stuck with the last brain-teaser

0Last puzzle:

Assuming there are more than one balls in each jar. Since digital scale will give exact weight, so if we put one ball from each jar, the digital scale would show 49. Similarly, if we put two balls from each jar on the scale and then weigh, it would show 98. This means we can use combinations of balls and since we know the expected weight, we can find out which jar has lighter balls. How?

Pick 1 ball from 1st jar, 2 balls from 2nd and so on. Put all of these on scale, let the reading be X. Now suppose each ball in each jar weighed 10g. In that case, the scale would have read (1+2+3+4+5) * 10 = 150. According to the problem, one jar has balls weighing 9g, i.e. 1g lesser than those in rest of the jars. That means the reading X would differ from 150 exactly by the number of balls weighing 9g, but since we picked different balls from each jar, we know exactly which jar has these balls. Answer: 150 – X

+4Thanks v33n

0Thanks

0good tips

0“Reverse the bits in one byte data as fast as possible”.

1. One solution is using a temp variable (slow but still), taking i=0 and j=n-1 and swapping the values of the bits.

2. Other can be “merge sort like” where bits are divided into small groups until only two are left and then swapped. And in the last step left half is swapped with the right half.

Any other solution faster than this.

Thanks.

+3For each pair of bits to be swapped (e.g. 0 and (i-1), 1 and (i-2), etc), perform the swap using xor. That will be faster than using a tmp variable.

To swap two integers (or bits) x and y:

x^=y

y^=x

x^=y

+1What will be the time complexity for second mergesort-like approach ??

0O(lgN) assuming O(1) work per iteration.

0Lookup array. You just have to precompute 256 entries.

0