Cisco, was one great experience with an amazing interview panel which was very directed. I was being interviewed for a team that works on firewall and what else can one expect to be tested at – string search! TeleCon was pretty normal and not much different than most interviews. Questions were a mix of C programming fundamentals, Bit twiddling, basic data structures, etc

Once I landed in Bangalore, I had to go through rigorous round of interviews. In all, I guess there were 10 rounds. It was a bit irritating that almost everyone in ever round (except managerial) was asking the same string search questions, but then that was the requirement.

In one of the rounds I was asked to write a string search in a given data structure, then we continued discussing the algorithm and refining and aligning it to the complexity being introduced by the interviewer. I started with a linear linked list and a simple search as asked in the scope of the question, then it was made complex by adding that I have to find all the common strings and part of strings in the given list of strings. This is where I really started to use my brain. Later on I merged all strings such that the common part formed the stem and rest created branches and leaves. Towards the end I was able to suggest that the data structure evolving on the white board could be used in for Dictionary and later it evolved into a spell search. Amazing, right?

   1: /*
   2:     C
   3:     H
   4:     A
   5: +---R----+
   6: A   T    I
   7: C   E    S
   8: T   R    M
   9: E        A
  10: R
  11: */

That was an amazing way of interviewing a candidate to make him use his mind and develop his own algorithms and solutions to a problem with evolving complexity. Interviewer kept making the problem complex and I kept continuing to refine my algorithm with minimum changes to address his changing requirements. After all minimum changes to cater current need is what good programming is all about.

In another round I was asked to implement a string search. To make it complex interviewer asked me to use multiple threads and then the obvious, ‘why’ questions. To further complicate the problem I was asked to tune my algorithm to work on a 5GB file on a system with two processors and 512MB RAM (Paging and multi threading). Then we discussed what-if conditions like what if I find a part of matching string at the end of buffer. I introduced the concept of sliding window protocol from networking to help me work around such boundary conditions.

With the manager was a very different talk. He sat there and asked me that they already checked and know why they should hire me, but I should tell him that why shouldn’t I be hired. And not just one reason but three. That was a mind game. If I would say a positive point as negative, he would say its ok, its positive and it don’t count… After talking some half an hour he was finally convinced on two to be no-hire reasons and that half an hour he came to know all about me 🙂

The next morning I had a couple of Video calls and I was thrown yet another interesting problem, to implement a library that can schedule and share a fix set of resources. Say for example a library that has 10 open connections to a database server and all my threads use this library to get access to one of the open channels, work and release. I thought for a while and then presented a solution with doubly linked list. I ensured that all operations are O(1). I don’t know why I was not able to explain my solution on one go. Interviewer on the other side was not convinced and he simply asked me the complexity of my solution to end the conversation there. When I said its O(1) and not just one operation but all and any, he asked me to check before I say. I challenged him on that and then he listened to my solution again and agreed that its the best he ever heard. Even the solution he had was not this good 🙂 Glad I was…

Finally the other video round had the following problem for which I will share my code piece.

Problem Statement: "Implement a library that records last 5 pings to any site you ping form your program and also maintain average and provide interface to query this average value. You can ping several sites simultaneously and your library should maintain stats of all. Should be dynamic."

Source File: