These are the questions I have been asked during my in-process
Microsoft interviews thus far. I have a final in-person one as and when
I go to India and that could be make or break things. So, all fingers
crossed. Anyway, here are the Q'n'A -
1) My take on Inverted Indexes
(discussed over tech-screen)
To me, inverted indexes and databases store data in a highly
compressed manner and I am quite fascinated by this compression
characteristics because to me, they are like layers of an onion. Or
like folding of protiens. The shape of the structure and how it has
folded is a world onto itself.
2) Camel and bananas puzzle (asked
during tech-screen)
Q:
A camel has to take 3000 bananas across the desert over 1000kms. It is
a very hungry camel and eats 1 banana for every KM. How many could it
possibly take across if it can at any point carry a load of 1000
bananas?
Answer-1: The first non-tricky solution is depending on the
rate at which the camel consumes a banana. If we assume it to be not
instantaneous, then it would have to eat the banana for some time and
as per reverse-normalization, the number of bananas it can eat over the
journey would only be so many. The rest would be carried over on every
trip.
Answer-2: (given later by phone/email)
Basically, the answer to the problem is _400_ if we want to minimize
the number of trips and this is based on trying to get the final load
to be as close to 1000 as possible. The approach is that the camel
starts with 1000, goes to 400 kms of the distance, uses 400 bananas,
drops 200 bananas and consumes the rest of the 400 bananas on the
return. It does the same for the next 1000.
And the last 1000, it goes to the 400kms, has 600 left, picks up the
400 lying there and starts the journey of remaining 600 kms with 1000
bananas. At the end of the trip, it delivers 400.
This solution holds for a minima on the number of straight trips (not
the number of kms/paces) because I think that more than 400 bananas can
be shipped if the camel uses the same break-down approach in a discrete
manner.
3) Describe yourself as a Software
Design Engineer (HR-screen)
I
am not a dirty geeky coder. I like coding and it is a very pleasurable
experience but I believe that one should respect the principles of
software engineering wherever possible and try to minimize not only the
amount of coding but also the complexity of it. Because, coding takes
only 20% of the life-cycle but if not done properly, the up-keep of it
and the maintainence could get unwieldy.
Most of the time, I try to use joined-up approaches and use 3rd-party
libraries because they have been extensively tested before. Ultimately,
I think I am an engineer more than a programmer.
4) Describe one instance giving
evidence of your Program Management (HR-screen)
It was during the MultiXP project. We were to make pitches to NESTA and
we were building the prototype. The business manager stressed that what
we were to pitch should be eye-catching even if the technology behind
it was not mature or even identifying with the ethos of the project.
It was a hard decision to make but we did it for the sake of the
project that has to impress people who would be funding us. So, we went
on to implement translation and reading-out-loud in a roundabout manner
first. It was another matter that we did implement the core technology
because I pitched in with the coding but it made me realize that
sometimes, you have to be flexible and re-prioritize things.
This also involved communicating the change of plans to the team which
I found harder than the actual technical bit. I had to lead them into
the reasoning and had to time it and take their input and concerns
before re-scheduling and planning.
5) Talk about the future of search in
your own words (job-screen)
- First discussion went that the future would be on local search using
the sneakers example. But this is much more deeper than simple local
shop listings on the web as could be the first impression. Let me
rephrase the scenario. A guy is interested in buying sneakers. He has
somehow decided which one to buy. From a friend or by browsing a
web-site. Now how do we match his choice to the best offer out there?
A web-site(s) might have a good offer but what about the local
shoe-store which could have a better offer like a clearance sale? This
local store does not have a web-site. Even if it did, it should go
through the "process" of being in the right vicinity and ranks to be in
the results and compete with the big guys. How can we match this user
to this offer in the simplest possible manner? That is the future
problem and potential of search. The key here is not only about
improving the results but also, if not more so, for improving
advertisement handling because in this case, the local shoe-shop need
not maintain a web-site or anything. Rather, the owner register the
ephemeral offer with MSN (just like they would post a classified to a
newspaper). This offer is what should match and perhaps come on the
results page. No web-site required and the classified listing itself
should be as simple as sending an email or an SMS message. Like say,
"<Barcode-ID> <Price> <Shop>". Or a phone call. The
Barcode-ID (on back of shoe-box) would be resolved to a full-blown
description on MSN to come on the listings. Yes, MSN does need to do
some major work to make this happen.
The future of search to me is in plugging local businesses and their
offers with search in a smart manner. That should level the playing
field and also as per the long-tail fundae, cater to most users who
more often than not use the web (or want to) to buy more useful (on
daily basis), antiquated and rare material. As per the long-tail again,
the amount of business generated (if the listing is made simple and
fair) would far outdo the business that search currently generate as
per the 80:20 principle. Yes, search is primarily for information but
the example would be giving details of an expert on the topic of "local
search" in the neighbourhood (or someone who has a blog on the topic
but lives around) so that the user can drop by for a visit. I know for
example, that there is someone out there on the street that is offering
cheese for a huge discount because it is last day or something. I want
to know that for I love cheese. In fact, these classifieds could be
delivered as an RSS feed or whatever to users. PUSH and PULL. I would
filter for cheese and be first in line to the shop that has the special
offer in the corner shop.
- Let us move on the next top-level scenario I identified which is that
the future of search will be in how well MSN can cater to the next 80%
of users who would become online. The next 6 billion people so to
speak. They would become online mostly using mobile devices not
computers. These are going to be people who have never and will
probably never touch a PC in their life. Like the farmers and
milk-wallah's of India if Airtel adverts have to be believed.
What would they search for? More important than that, how would they?
Because, would it be the case that they will use keywords? Combine this
with the complexity of language. These are over and above the problems
with the core mobile UI (like entering words). Using MSN over mobile
phones is not what is under discussion but rather, what other ways can
search be done and how MSN can benefit from the huge numbers at stake?
With the farmer example, the farmer could take a picture of his brinjal
produce and get results for their market price. Or point to a poster
(like movies or polio) on the wall and get the information and listings
(this is good for a Western audience too). Or how about he calling
someone and explaining the query in a local language? Where is the
monetization? Well, it is in the communication itself.
- In the third instance, I was trying to combine the above of local
search and mobile search because mobile search has the added advantage
that it gives fine-grained location information to the resolution of
say, streets. This can be used to good effect in local search in many
cases not only for re-ranking, disambiguation, matching users with
their search needs and locale et al.
In fact, I submitted a document called BlueWeb to Nelia which addresses
such issues and more.
6) How would you go about designing a
digital camera for teenagers (job-screen)
- This is not such a hard thing to do if one understands what teenagers
are after which is not hard because everyone has been a teenager. So,
the solution is to have a stream of fad-oriented "look" for the digital
camera. Like the example of U2 (black and red) or a recent movie or
cult like Star Wars. Use the digital camera in promotion with such big
events like launches or concerts. In other words, "skin" the digital
camera. The outer covers can be changed. Nokia had such a thing so also
Titan Raaga watches. This gives flexibility for teenagers to be "hip"
with the latest trend which change at quite a fast rate. Raging
hormones. It is basically about expressing themselves and their
fanhood.
- Second aspect to it is the software. Make the cameras into utility
swiss-knives. Teenagers like to show things off and tell to their mates
how cool their product is and that it can do this and that. The camera
has a screen and speaker. So, why not use it as a music player or video
player (most cameras capture videos but how about playing downloaded
content such as viral videos?) The hardware is already there.
- Third aspect is sharing. Teenagers tend to socialize a lot and share
things while they are at it. It is one thing to show a picture and
another to actually transfer it. P2P was and is mostly a teenage
sensation. So, could we make the camera transfer without using PC or CD
etc. and do it on the spot? Well, there is something called Pictbridge
(perhaps specific to Canon) to communicate with printers. Can we use
that or similar? Perhaps yes. Some digicams come with Bluetooth as well
which is P2P technology anyway. Or perhaps maybe design the camera lens
such that it fits snugly to the screen and a picture can be transferred
(with some loss) directly using the screen and electro-staticity(?). Or
a cable which is built into the camera perhaps? Or a jigsaw
arrangement?
7) Prove that the middle number
between twin primes is divisible by 6 (job-screen)
Q: Twin primes are two prime numbers that are seperated by a distance
of 2. For example, 11 and 13. 5 and 7. 17 and 19 etc. The middle number
of twin primes has a property that it is a multiple of 6. Prove this.
Answer-1: In the call, I said I would use induction over the twin
primes. For 5 and 7 the middle number is 6. For 11 and 13, it is 12.
So, if we can prove it for 1 and K, then, the property holds. The hint
I was given is that to prove this, I can use the divisibility property
of 6 that if a number is divisible by 2 and 3, then it is divisible by
6. So, the middle number can be generalized to a form and proved for
the divisibility by 2 and 3. I used the property of primes being
odd-numbers etc.
Answer-2: (over email)
A better solution is let, A, B, C be the 3 numbers in question. With A
and C are the primes seperated by a distance of 2. The side-effect of
this situation is that A, B, C are consecutive numbers and B = (A+C)/2
(as with any 3 consecutive numbers).
Now, all primes are expressible in a sum of powers of 3 and 2. So, A
could be generalized as (2^m + 3^n) and C as (2^p + 3^q). Hence -
B = ((2^m + 3^n) + (2^p + 3^q))/2
= ((2^m + 2^p) + (3^n + 3^q))/2
Let us take the denominator out which is 2. The first sum-of-2's is
divisible by 2. The second sum-of-3's is always an even number and so
divisible by 2. So, the denominator could be silent. So, B could still
be expressed as a sum of 2's and sum of 3's.
To prove that B is divisible by 6, I will use the hint that we have to
prove that it is divisible by 2 and 3.
For 2, as above, it is trivial. For 3 again, the sum-of-3's is
divisible by 3. The trick bit is that the sum-of-2's be divisible by 3
because this property does not hold for all possible values of 'm' and
'p' (for example 2^2 + 2^4 = 20 which is not divisible by 3). However,
we can use the property of the twin primes (probably the key to this)
in that the possible values of 'm' and 'p' (in this situation) can only
be consecutive numbers. So, the sum-of-2's is always divisible by 3.
8) Circular jail puzzle (job-screen)
Q: There is a circular jail with 100 cells. A jailer one night gets
drunk and tipsy and runs around the jail opening the doors such that
for every Nth round, he opens doors which are multiples of N. He runs
around for 100 times and drops down tired. How many doors will be open
now?
Answer: The answer is 10.
The solution is based on the property of factoring which I alluding
during the call. Now, for any number in 1 to 100 and which can be
factored, factoring is complementary i.e. if a number N is divisible by
a number P, Q times, then it is also divisible by Q, P times. So, every
factorable number gets closed because the number of factors (would
become even and toggling puts them in the initial state of closed.
This applies even for primes because 1 is a factor and so also the
number itself.
The only anamolies are those numbers which are squares (1, 4, 9, 16,
25, 36, 49, 64, 81, 100 - total of 10). They are factorable in other
ways but they do not have a complementary in one case (they have but it
is the same number). So, they remain open.
Example, 50 = (1x50) * (2x25) * (5x10) = 12 toggles (including
complementary rounds of (10x5), (25x2) etc.) = Closed
36 = (1x36) * (2x18) * (3x12) * (4x9) * (6^6) = 17 toggles = Open
In fact, this is a general solution for any number of cells. For any N,
the number of gates opened for this situation is the number of squares
in the range.
8) Describe how mobiles can be made as
a replacement for credit cards (job-screen)
- I will not go into the area where mobile phones can be used to make
small payments as with certain iMode services in Japan and concentrate
on mobile phones as a straight replacement for credit-cards.
- The first solution of the user entering the number (of merchant ID
and cost as put on the bill) as an SMS message and getting the
validation back is a quick solution perhaps because in UK one can do
that to an extent on TV shows. I was thinking of the reciept coming
through to the merchant by SMS too as he could register himself to the
bank perhaps. But I do take the point of getting reciepts etc.
- The next solution was to use something like IR or Bluetooth or even
GSM signals (something like jammers exist) to give the credit card
details to the merchant (which is what they really seek). This was the
first solution that striked me but I thought it would be cumbersome to
give the mobile phone to a waiter in a restaurant (which is the
use-case I am aware of personally). Anyway, this could be done and it
does mean that the merchant has to install/upgrade the equipment at his
premises. The security would be a personal PIN on the phone. For the
merchant, the easiest way is of course to have both forms of payment as
you indentified but would it be possible for the merchant to NOT do
anything on his premises?
- Well, we never got to this point but how about using magnetism? The
Bluetooth/IR is only a replacement to send the information on the
credit-card which works via a magnetic strip. Can't we work on a
solution that uses magnetism? Maybe the credit card company would send
a magnetic strip (or a chip) that could be stuck on the back of the
mobile. This has the disadvantage of changing mobile phones though.
- More technical solutions could be to use the speaker hole. You know,
the headphone jack. This is universal for all mobiles. At the merchant,
the cable would be plugged and the user can give the details. Talking
of universality how about the credit-card details told using audio
pulses (like how DTMF works) or the number coming on screen as a
bar-code that can be scanned?
- It could still be the case that there is new equipment somewhere and
that has to be justified and your points on how one can convince the
merchant to put these new "scanners" (new market trend explanation) is
probably best. I was more or less thinking of the manual swipes (that
hand machine) who are merchants who do not know or want to use
technology even if the electronic swipe exists. I suppose this is not
the market we are aiming for. Or they can leap-frog.
