technology and zen of life

“A heisenbug (named after the Heisenberg Uncertainty Principle) is a computer bug that disappears or alters its characteristics when an attempt is made to study it.”

Reverse-engineering the cascode

(from – http://analogcircuits.posterous.com/reverse-engineering-the-cascode)

Cascode (shown in Fig. 1) is well known and widely used circuit for creating large-impedances in integrated circuits. Cascode circuits also provide another advantage i.e. isolation between input and output ports and thereby reducing the Miller-effect and as a result cascodes have a good frequency performance. And when impedances achieved from cascode circuits are not good enough, we go on to use active-cascodes or regulated-cascodes. Even though cascodes are affected by the limitations of headroom (voltage swing), there are work-arounds for this problem that have been figured out by circuit designers (the smart engineers again). The question that I want to discuss here is – how did someone (must be a genius) think of this circuit which provides an elegant area-efficient solution for achieving large impedances consequently large voltage gains?

Read the rest of this entry »

Why do we perform small signal analysis?

Why do we perform small signal analysis, when we are analyzing or designing analog circuits? This is a fundamental question that I think, is not discussed rigorously enough in the classes or text books on analog circuit design. I will attempt to qualitatively address this question here in this blogpost.

Untitled Why do we perform small signal analysis?

Fig. 1 a) Small-signal MOSFET model and b) small-signal bipolar model

Read the rest of this entry »

Puzzle 5: Burn the rope..

A classic puzzle involves being given 2 ropes and a lighter. The burning of one rope from end to end takes 1 hour, however the ropes do not burn in a uniform manner (ie: if you light it at one end, the first half of the rope could burn through in one minute while the second half may take 59 minutes to burn). Your goal is to measure out 15 minutes using the two ropes and the lighter.

You can assume that lighting a rope takes zero time.

Hint: You can break the rope with your bare hands..

Best Solution by Dark

using a single rope

it takes 1hr to burn the whole rope
rope is not burning evenly

break the rope in 2 parts (sizes don’t matter), part A and B

burn both the parts A and B from both sides.

as the ropes burn unevenly, let say A is burnt, and B has still unburnt part.

At the moment A is finished start a new fire somewhere in mid of B, thus making 2 new parts of ropes, lets say A’ and B’

if you continue this and the rope has 4 burnings ends always.. you can measure 15 mins using a single rope (assuming burning takes 0 time)

About the 2nd rope.. just burn it or timepass icon biggrin Puzzle 5: Burn the rope..

Puzzle 3: Color.. Color..

This is one of my favorite puzzle. Please don’t put spoilers if you already know the answer.

“If a bear walks one mile south, turns left and walks one mile to the east and then turns left again and walks one mile north and arrives at its original position, what is the color of the bear.”

Please give answer alongwith valid explaination instead of wild guesses.

Puzzle 1 : Take a chill pill!

This is one of the Microsoft interview questions, should be easier to answer as writing a code is not required. icon smile Puzzle 1 : Take a chill pill!

“You have 5 jars of pills. Each pill weighs 10 gram, except for contaminated pills contained in one jar, where each pill weighs 9 gm. Given a scale, how could you tell which jar had the contaminated pills in just one measurement?”

By scale I mean a digital weight measuring machine.

SOLUTION:

1. Mark the jars with numbers 1, 2, 3, 4, and 5.
2. Take 1 pill from jar 1, take 2 pills from jar 2, take 3 pills from jar 3, take 4 pills from jar 4 and take 5 pills from jar 5.
3. Put all of them on the scale at once and take the measurement.
4. Now, subtract the measurement from 150 ( 1*10 + 2*10 + 3*10 + 4*10 + 5*10)
5. The result will give you the jar number which has contaminated pill.

Algortihm Challenge 1: No division!

I have decided to come up with series of challenges n problems which are algorithmic in nature and are asked in interviews of reputed companies like Microsoft, Google.

This one was asked in a Google interview recently. Try to answer it in your comments. I will post the solutions if no one comes up with the right answer (let’s hope not).

“You have an unordered array X of N integers. Find the array M containing N elements where M_i is the product of all integers in X except for X_i. You may not use division. You can use extra memory.

What is the best way of doing this?”

Example:

N=4

X = {2, 5, 3, 7}

M_0 = 5*3*7 = 105

M_1 = 2*3*7 = 42

M_2 = 2*5*7 = 70

M_3 = 2*5*3 = 30

M = {105, 42, 70, 30}

(hint: There are solutions faster than O(N^2))

NOTE: while posting solution put your code (if any) inside <code></code> tags.


SOLUTION:
Thanks for your efforts. The solution presented here runs in O(N) time. Yes O(N), and thats what an interviewer would expect you to come up with, in less than an hour.

Form two arrays P and Q such that
P[1] = 1
P[i] = X[1] * X[2] * … * X[i-1] for 1 < i <= N
 
and
 
Q[i]  = X[i+1]*X[i+2]*… * X[N] for 1 <= i < N
Q[N] = 1
 
Set M[i] = P[i]*Q[i]
 
Both P and Q (i.e. M) can be found in O(N) time.

Once can access corresponding code snippet here.

Email Subscription

Disclaimer

The views expressed on this blog are personal. We do not claim to be a representative voice of the views of any organisation whatsoever. We are not responsible for the content present on the blogs to which we have linked.Views expressed are solely that of the author and does not reflect a collective opinion of contributors.