Citi
came to hire summer interns on our campus. My name was in the list of the 20
people that were shortlisted after an online round which comprised of quant,
logical reasoning, English multiple choice questions and 2 coding questions.
TECH ROUND
Walked
in before the interviewer, smiled and greeted him, he greeted me back. Told him
my branch. Gave him my CV, sat down .I told him about course structure of Mathematics and Computing in my introduction.
He checked out my Olympiad ranks . Here he decided to start with puzzles.
- Started with marble weighing puzzle. You have 10 bags
full of marbles; in each bag are 1,000 coins.
But one bag is full of forgeries, and you can't remember which one.
But you do know that genuine coins weigh 1 gram, but forgeries weigh 1.1 grams.
I started with the divide into groups approach, gave
a log n solution. He asked if I could do better. With a tiny hint, I reached
here : If there is only 1 bag with forgeries, then take 1 coin from the first
bag, 2 coins from the second bag . . . 10 coins from the tenth bag and simply
weigh the picked coins together !
If there were no forgeries, you know that the total
weight should be (1+2+3+ . . . +10) = 55 grams .But if, for example, the weight
is 55.3 grams, then you know that 3 coins are forgeries, so that must be bag 3.
So, that solves it.Now, if there is more than 1 bag with forgeries, then you
will need to choose numbers that cannot be mistaken when added together. One
possibility is: 1, 2, 4, 10, 20, 50, 100, 200, 500 and 1000.
- Saw Monte Carlo estimates mentioned in my resume in a project and asked me to explain it. I used a sheet of paper and drew and showed how I reached the estimation of pi. Then I future explained my project
- My 1st coding question was a easy one: to check if a string is a palindrome. I suggested to take to flags , 1 at beginning and one at end, and compare term by term. Increment the 1st pointer, decrement the 2nd one till you reach the middle one.
Tricky follow up would have been : Check if a given
string is a rotation of a palindrome:
An Optimized
Solution can work in O(n) time. The idea is similar to this post.
Following are steps.
1) Let the
given string be ‘str’ and length of string be ‘n’. Create a temporary string
‘temp’ which is of size 2n and contains str followed by str again. For example,
let str be “aab”, temp would be “aabaab”.
2) Now the
problem reduces to find a palindromic substring of length n in str. If there is
palindromic substring of length n, then return true, else return false.
We can find whether there is a palindromic substring
of size n or not in O(n) time (See Longest
palindromic substring)
- Equilibrium-index-of-an-array : Now this was something I hadn’t heard before. It amazed me that I reached the correct solution on my own.
Method 1 (Simple but inefficient)
Use two loops. Outer loop iterates through all the element and
inner loop finds out whether the current index picked by the outer loop is
equilibrium index or not. Time complexity of this solution is O(n^2).
Method 2 (Tricky and Efficient)
The idea is to get total sum of array first. Then Iterate through
the array and keep updating the left sum which is initialized as zero. In the
loop, we can get right sum by subtracting the elements one by one.
- Young tableau : For our present discussion ,we confine this entity to a table which elements are sorted both column wise and row wise.The degree of orderliness among the elements is loosely bound that a row by row or column by column traversal of this matrix doesn't essentially list out the elements in a sorted manner.So the search on this matrix is not all that simple and straight forward as it looks like.
In the following sections we will
look at some interesting approaches to search for a key in this 2D array(after
all it is!!).
One interesting yet simple thing
worth observing is that
element A[i][j] is always >
A[p][q] for i > p and j> q .
The next 2 strategies are based
on this simple fact.
Strategy1 - A
grid search: About any element A[i][i]
divide the matrix in to 4 quadrants.
If the key K we are looking for
is
- A[i][j]<A[i][j] then we can eliminate the lower right quadrant because all its elements are >
- A[i][j]<<A[i][j] then we can eliminate the lower right quadrant because all its elements are >
- A[i][j]<=A[i][j]. then our search is over.The choice of this i can be done in a binary search manner.. reducing the search space by half.
Now we can search the 3 quadrants
individually and hence recursively.
T(N)=3*T(N/4)+O(1) which comes
out to be O(N^(log3/log4)) which is less than O(N).
Strategy2:Now we move a step further in reducing the search
space.Iterate along the diagonal and find i such that A[i][i] <k and
A[i+1][i+1] >k.Now we have only 2 search intervals to search for.
T(N)=2*T(N/4)+O(N) which comes
out to be O(N).
Strategy3:One more interesting
solution and smart solution that I found was(the credit goes to the geek named
Novice in the discussion http://inder-gnu.blogspot.com/2008/01/find-element-in-row-and-column-sorted.html ) this.
Start from the point in the last
row first column. Every point to its right is greater than this point and every
point on its top is smaller than this. So, if the point is greater than this
point then move right otherwise move top. So, you will traverse at most 2*n
points.
- The Two Guards (a 2000-year-old classic)
You stand at a fork in the road. Next to each of the two forks,
there stands a guard. You know the following things: 1. One path leads to
Paradise, the other to Death. From where you stand, you cannot distinguish
between the two paths. Worse, once you start down a path, you cannot turn back.
2. One of the two guards always tells the truth. The other guard always lies.
Unfortunately, it is impossible for you to distinguish between the two
guards.
You have permission to ask one guard one question to ascertain
which path leads to Paradise. Remember that you do not know which guard you're
asking -- the truth-teller or the liar -- and that this single question
determines whether you live or die. The question is: What one question asked of
one guard guarantees that you are led onto the path to Paradise, regardless of
which guard you happen to ask?
Ans) "If I asked the _other_ guard, which door would he
indicate leads to Paradise?" Take
the door _opposite_ to what's indicated! Regardless of whom you ask, they'll
point to the wrong door. Go ahead and talk about binary, make groups of (01,10)
and (11,00)
- He asked me what was the rarest and hardest puzzle I had encountered till date. I mentioned this :
HR ROUND
I
walked in, was surprised to see a panel of 2 instead of one.
The classic : tell me about yourself
I
smiled , maintained eye contact. “I am Shivali Vij, I am the branch opener of
mathematics and computing branch. I had a rank good enough for IT or software,
but I chose this branch. I have done 2 projects in College, one on Monte Carlo
simulation and key generation, other on DNA forensics. I have good analytic
skills and inquisitive nature which is evident by the fact as to how I have
participated in taekwondo demonstration in college, in animation, and I am the
technical head of ASES, and gave a presentation on stock market . ”
Questions
were asked on each of the sentences:
- Discussion on project 1: Monte Carlo simulation: I explained how I read about windows and open SSL ,Sony PlayStation key failures due to wrong seed but correct algorithm which led me to study random number generators, their simulation and cycles. They asked if any true random number generator existed, I joked about bringing a radioactive sample to the lab and counting emissions. Again on monte Carlo, same drawing, same explanation. Talked about application in finance theory.
<Notice
starting with real life application >
- Discussion on project 2: DNA forensics: sample size problem and study of how those probabilities were calculated.
- Taekwondo : he asked if I were a black belt. I told him I was honored with a green belt after the demo. Talked about increasing awareness and how no of girls joining the classes have increased, and more funds allocated to taekwondo group (I TALKED ABOUT RESULTS)
- A presentation on stock market: They asked me to imagine if they were my students and asked me to teach them. I started with the same “what do you do with a 1000 Rs” question. Talked about stock indexes. He asked me how they were calculated. I talked about choosing representative companies.
Tell
me about family : Told them my dad being a scientist, mom is mathematics teacher. I joked about how genetically it
affects me (scares off people)
Why Citibank ?
I
was prepared for this one. Talked about financial crises, how The CEO sold off bad assets and withdrew money. I
appreciated the move by saying that stepping back is equally important. I
clearly told them that I had been reading about CITI and I talked about the
share bike launch (faces lit up on this one.) and inside out entrepreneurship
event. They knew I had some my background research.
After
appreciating the company I talked about how I was suitable. My branch,
operation research, numerical methods we implement in Matlab, financial
engineering. I sold myself off to them.
For tips , check out How to answer : Why-do-you-want-to-work-for-us.
What are you hobbies?
I talked about
reading. Mentioned genre: personal finance, motivation, self-development.
Follow up question:
last book you have read? They asked me what I had learnt.
The
sir on the left asked if any other of Dale Carnegie books. I said honestly that
I liked this one and ordered one on public speaking. He told me this was his
favorite book. Went ahead and justified the book.
Draw your success curve and where you see yourself?
They
handed out a piece of paper and pen. Though I had heard this question in the
morning, I hadn’t been able to come up with a good answer all day. But as I
held the pen, a smile came to me. I said “Success depends on how you define it.
For me success is learning, so I’ll draw my learning curve”. Made a x=y ish curve, the cut it. I said ”A little bit of slope makes a lot of y
intercept.” Overwrote on my drawing. Increased the slope. Showed the intercept.
Announced “I want my learning curve to keep moving up. ” Smiled at them. They
blushed. I had won this one.
Any questions for us?
Asked
about their learning curve. It got them started. Both spoke for 5 minutes each.
They were speaking, I was listening and acting interest, internally saying
“yes, yes !” They both got tired.
Smiled. Asked me “Any more questions?’ I asked about the company and mentor
system. They answered in detail.
One of them
concluded by saying “ change is the only thing permanent in life, so embrace
change.”
Did i get it ? Oh yeah
Did i get it ? Oh yeah
