Tuesday, July 2, 2013

Explaining Emotional Detachment

Not long ago, I took a simple Online Test that concluded that my personality type is INTJ. Subsequent introspection, besides confirming that I almost perfectly fit that stereotype (which was disappointing in itself since my emotional side would have preferred to believe that I was somehow special or unique), also led me to explore the consequences of the realization that I will eventually but inevitably no longer be who I am right now.

And that means that every thing I value right now, it may all be just a phase that I am going through. It may all be just a matter of time before I find flaws in the reasoning behind everything that I believe in. And if I don't, that doesn't necessarily mean that there are none. Now, it would have been a reasonable assumption that smarter men and women than I have struggled with the same problems and (factoring in the substantially more time and life experience they have had to think about this than I) would have proceeded beyond this point. But having explored the available answers to the philosophical questions that I obsess over, I already knew that none of the existing ones satisfy me.

Wednesday, March 6, 2013

Nothing is Sacred

One of the biggest goals in each one of our lives is to figure out our purpose. Why do we exist? Not how ... because the answer to that is known, but why? Explanations involving God just result in the question being modified to: Why does God exist? Now, I recognize that I am making an assumption here (which, if proven false, would render this entire chain of thought invalid), justified by the lack of convincing evidence to the contrary, but this is what I fundamentally believe as of now: there is no greater purpose.

The universe, as a result of the fact that it is logically consistent, can exist. But so can any number of other logically consistent universes with different histories or different laws of physics altogether. And why should anything exist at all anyway? Well, the principles of justice that I have been conditioned to think according to (yes, I know that it sounds evil, but if you think about it objectively, the definition does apply) make me want to believe that all possibilities are (withholding the word: equally) feasible, and exist as a superimposition which happens to be most closely described by the term: Multiverse. But essentially, we exist, because we can.

Friday, November 9, 2012

Computation using Time Travel

Time Travel is one of the most fascinating subject I have ever encountered. Having spent an unreasonably large amount of time thinking about it, the following describes one of the ideas I had regarding how we can use it.

Consider for a moment that humanity has somehow managed to develop the technology for Time Travel, and confirmed that the universe abides by the Novikov Self-Consistency Principle. For the purposes of this discussion, you may assume (although the specific details of how it is done don't matter here) that this is done via a Wormhole (stabilized using exotic matter with Negative Mass/Energy), one end of which (through Time Dilation effects) lies in our future. Now, we can establish a communication link across this wormhole, which allows us to send data into the past or receive data from the future. Additionally, let's assume that we can transfer information over this link via two specific functions in a computer program:

void send(data) # Sends data back into the past.
data receive() # Receives data from the future.

Thursday, September 27, 2012

Directi Selection

The following is an account of the selection process that I went through when Directi had come to our college for placements for the Software Developer profile on 25th July.

Aptitude Round
  • 30 question, 45 minutes from Number Theory, Logic, Networking, Operating System, Programming, Servers, etc.
  • A lot of these question were repeated from the aptitude round conducted when Directi had come for Internships, so I'd seen a lot of them before. However, I hadn't really bothered finding out the solutions after last time, so I was able to answer exactly only those that I had answered the last time. Somehow, I still had the highest score as compared to all the other people in this round. Helped a lot later.

Coding Round

Platform: CodeChef
  • A board of width W is placed on the X-axis. Initially, the board is placed such that its left end is at (0,0) and the right end at (W, 0). N coins will fall from the same height but different integral X co-ordinates. Coins fall one by one, i.e the second coin starts falling only after the first coin has reached the X-axis. Given the X co-ordinates of the N coins in the order that they fall, you have to calculate the minimum distance that the board needs to move to collect all the coins.
  • A N x N grid is filled with lower case characters from 'a' to 'z'. A square matrix is called a palindrome if the string formed by concatenating characters from the main diagonal is a palindrome. Count the number of sub-squares in the N x N grid, including itself, that are palindrome.
  • I was able to solve the first one very quickly, but got stuck in the second one. Using the usual statistics of 10^9 calculations per seconds, I estimated that an O(N^4) solution with N<=100 would run in less than 2 seconds but it didnt. So I had to optimize it using a basic form of hashing which I was unable to perfect at the time. However, I did get a WA instead of a TLE, which was better as it meant that I only needed to fix some logical errors.

Algorithm Round : Personal Interview

Interviewer: Nikhil
  • Given N squares, you are standing on the first one and you need to move to the last one. You can, from any square, take one, two or three steps forward. How many possible distinct paths are there from one end to the other? I gave a linear solution, which he was happy with, although I later discovered that a logrithmic solution existed based on the Fibonacci Series.
  • Given the coordinates of N pairs of cities, each pair containing cities on two opposite sides of a river, we need to make bridges between the pairs. What is the maximum number of non-overlapping bridges that can be built? I had seen this question somewhere not to long ago, so I was able to give an O(nlgn) solution in which we sort according to one coordinate (X) and then perform an LIS on the other (Y). I gave the answer instantly, so he asked if I'd heard the solution before. I said yes, so he said this one wouldnt count.
  • Given a matrix, divide it using a vertical and a horizontal line into four parts such that the minimum sum of all values in any one part is mazimized. I created an auxiliary matrix with each element being the sum of all elements to the left and top in the original matrix. Using this, we can find the required values. O(n*n)
  • What type of data structure would you use to perform range maximum queries and why? Segment trees, because of logrithmic query time, with the possibility of lazy propagation for range updates.

Technical Round : Telephonic Interview

Interviewer: Vineet Gupta, General Manager of Software Engineering.
  • Given two string A and B, find the longest prefix of A that is a suffix of B. This one involved actual coding using collabedit/piratepad, so I first implemented a O(n*n) solution that I amortized to O(nlgn) using a basic form of hashing and binary search. However, he wanted a linear time solution which I finally gave as KMP applied on the strings in reverse.
  • If there is sufficient RAM for all the programs that need to be executed, why should we use Virtual Memory? Isolation between address spaces for programs. I assumed this, and didnt say it explicitly and kept looking for alternative solutions. Later when he gave the solution, I told him about it.
  • What determines that a system is 32-bit or 64-bit or whatever? Internal processor bus architecture and register size. WHat are the implications of increasing this. Higher power consumption, more complex circuitry, larger address space, faster execution. Benefits dont make up for the disadvantages however, so 128-bit systems aren't that common.
  • What possible reason could we have for using multithreading on a single processor system? IO Blocking, but he wanted more that I couldnt give.
  • Which programming language is my favorite and why? I said Python because of the lack of datatype bindings to variables. Also mentioned that I dont like Java much.
  • Which was my favorite project? I wasn't able to decide so he randomly decided to discuss the distributed chat client I had built during the summer at IIT.
  • Why were you using a UDP broadcast instead of TCP to local peers in the local subnet? Because although UDP doesnt provide a guarantee of delivery, it's much faster.
  • He asked me to explain the security mechanisms we had used. I explained Deffie Hellman Key Agreement, but after that he moved on.
  • How does the DataLink Layer in the TCP/IP stack implement broadcasts? How do routers do it? I wasn't sure, so I told him that there should be a MAC broadcast address like IP has. Also mentioned some random things about ARP Tables and stuff, which wasn't really answering the question, but just to show him that I wasent completely clueless.
  • If your access to the various programs that you use daily was to be revoked, which is the last program/software you'd want with you? I first said some game for the entertainment, but then he gave me a second chance, and I said a compiler, which he was happy with, cause then we can build whatever we want out of it.
  • Which is your favorite editor? Right now, I use Notepad++, but I'm learning to using VIM.
  • How would you design a text editor? This was a long one in which we discussed the various functionality that needs to be implemented, followed by the data structures that we will use and the architecture of the code. I wasn't to happy with my answers cause none of them seemed to satisfy him. We discussed cases of large input and matters of efficiency.
  • Finally, he said that he was done, and asked if I had a couple of questions. I asked a few personal ones, after which we ended the conversation.

A few minutes later, Kinnari Gandhi (the Directi HR) came and told me that I had successfully cleared it and had gotten the offer.