Krishna Bharadwaj's blog

Ideological Subversion

We come across so many incidents in our country that make us wonder what is wrong with us. Some of these incidents are very stupid while some tend to be very serious. Media blows anything and everything out of proportion and in many cases, selective reporting gives viewers an entirely different picture. We often hear the phrase "Paid media" and general VK Singh has expressed his frustration regarding the same on several occasions. And this is not something happening in our country alone. Several international media companies are being accused of the selective reporting in case of refugee crisis in Europe [1] Why would they do something like this?

I was curious about the refugees crisis in Europe which led me to read a little bit more about the same and stumbled upon an interview of Yuri Bezmenov, an ex-KGB agent who was undercover in India and Canada. He talks about a process known as subversion. It is a systematic way of tearing a nation apart. Many countries employ this on their enemies. In fact, he says that waging a war against a country is very foolish. In his exact words - "The highest form of warfare is not to fight at all". This talk [2] happened sometime in 1985 and it is amazing to see how we can see the result of this with our own eyes today.

Subversion has 4 steps

Demoralization

- This process usually takes about 15 - 20 years. As the name suggests, this makes citizens of the country demoralized. The reason why it takes 15 to 20 years is because it is the time needed to educate a generation. This step infects fundamental building blocks of a nation or society. At 10:14 in the video, there is a table which talks about all the methods employed and corresponding results of each method.

Religion - Destroy and ridicule religion which results in Fights / Deaths
Education - Ignorance
Media - Uninformed Myopia
Culture - Addictive fads
Law and Order - Mistrust in Justice
Security - Defenselessness
Family, Society - No loyalty
Labor - Victimization

With each of these fundamental building blocks of a nation attacked, it is very hard to be not demoralized. In any democracy there are several movements that are against the government or the ruling party. Subverters capitalize on these movements. They will appoint members who can systematically bring a divide in the country. From the following video [3] in which Yuri talks about the process -

A large amount of time is spent in amassing information about people who are instrumental in creating public opinion - publishers, intellectuals, editors, journalists, actors, professors, members of parliament, members of business circles. These members were divided into groups, those who were working in accordance of the soviet policy, they were promoted to the positions of power through media and public opinion manipulation. Those who refuse this would be character assassinated or executed physically.

"We reach movie makers, intellectuals, so called academic circles, cynical ego centric people who can look into your eye and tell you a lie. These are the most recruitable people, people who lack moral principles, people who are either too greedy, or suffer from self importance. These are the people who we wanted to recruit. When their job is done, they are not needed. They know too much."

In one instance (26:00), Yuri says the following about equality - People are not born equal and no religion which talks about equality. in fact, what religion says is the quite opposite, You are judged by your deeds and what you do is important. Yet we build our society on the basis of equality, which is a lie and at some point of time, it will collapse.

Another very powerful way to get things done is via sympathy. It induces some sort of guilt among decision makers and at some point of time they succumb to the pressure mounted by media and unwashed masses who have little to no information about the complete picture. Remember the Syrian boy who drowned? Or take a look at this video [4] - media selectively picks images and portrays as though the refugees are being ill treated by military and the government, there by showing the government in bad light. We often see Palestine civilians as being victimized by media. I would like to share this one conversation that I had with fellow interns at Google, we were talking about Israel and Palestine conflict and how a civilians were suffering. Soon, one of the intern who was from Israel(and had worked with Israel military in the intelligence wing for 3 years) said the following - "It is simple math, Hamas fires rockets on Israel. Each of their rockets cost $500 to $1000 and each one of our Iron Dome interceptor costs $50k. If we don't go offensive, we will not be able to protect our people for long, it is just that Hamas takes cover behind civilians and there is very little that we can do about it". A country cannot fight in defensive mode forever, that's when it shifts to defensive offense. I highly recommend watching this talk of Ajit Doval, National security advisor to Prime Minister Narendra Modi [5] to understand more about the same.

He makes one statement - Subverters are not spies who come to your country and blow up bridges like in hollywood movies, they are people who might have come on an exchange program, or someone who is an artist or an actor etc.. They(sleepers) go to a sleep mode and are re-activated during destabilization.

Destabilization

This takes about 2 to 5 years. This is a stage where members of the society cannot reach a compromise situation and they want to get it resolved by either moving to a court or fight with each other. Even for the smallest of quarrels. Relationships are radicalized - it could be between universities and students, employees and workers etc.. There are groups of people that come together to protest again certain issues. Most of the sleepers who were trained by the subverters, they become leaders and public figures of these groups. They start talking about political issues and start demanding rights, respect and equality and what not. There are violent clashes between his group and police. Sometimes with fire arms. These so called public figures get funds from various organizations which want to destabilize a nation.

Crisis

This stage takes only about 2 to 6 months - A stage where legitimate / elected bodies of power cannot function any more. At this time there are several fake organizations injected by the subverters. There are a lot of strikes and protests. People are tired of protesting and they need some strong man who can lead them and have a strong government. There comes a savior - Either a foreign nation comes in (Invasion) or there is a local group of leftists / marxists (Civil war).

Normalization

At this stage, the nation is completely torn apart and now the subverter tries to bring the situation to a stabilized state. All the actors, intellectuals, professors who helped in the previous two stages are no longer needed and they are eliminated. The new rulers need stability to exploit the country and they don't need revolutionaries.

If we go through the entire process, we can start correlating it with a lot of events we have seen in our country in the last few years. What stage of subversion are we in? :-) What countries could be targeting us? Can we trust all nations that seem to be friendly with us? From Ajit Doval's talk, it seems like India has not ventured into this subversion business yet but I feel it is this very nature of our country which makes india like-able by a lot of other countries.

Couple of days back, Narendra Modi in his UK talk, asked citizens to not pay much attention to selective reporting of media and the country is too huge to be generalized. I sometimes feel that our government is operating at a different level altogether. If it has recognized that a demoralized country is not a healthy state to be in and is working relentlessly to come out of it. I would consider that as a huge step in the direction of progress. The way world sees India today is very different from the way it used to be 2 years back. It is interesting to see that the method suggested by Yuri to bring back the nation to its normal state is through religion. Apparently, that is something which holds people together according to him. And probably the main reason why it is attacked so frequently.

As citizens, we all have some responsibility towards our nation, for a long time, I used to wonder why we have so many issues here. But now, it makes a lot of sense. All along, we knew that something was wrong with our mainstream media but we didn't know the motive. But that is no longer the case.In the video, Yuri says -

"You cannot subvert a nation that does not want to be subverted".

It is our job to educate people around us and to ensure that we don't add to the already demoralized state of our nation. In this post, there is very little original content, but I just wanted to compile everything in one post so that it is easy to share and read - instead of watching a 1.5+ hour video. If you have time, please go through the videos linked.

[1] - https://www.youtube.com/watch?v=l76kSsCLqTo
[2] - https://www.youtube.com/watch?v=T4YtgA2jnu4
[3] - https://www.youtube.com/watch?v=xFqShpJm_zc
[4] - https://www.youtube.com/watch?v=_gAxpQEm6Mk
[5] - https://www.youtube.com/watch?v=YHIjaa4dfJU

Goodbye Los Angeles, Namaskara Bengaluru

Looks like I just graduated from USC with a masters in Computer Science and I will be heading back to Bangalore to continue working on SMERGERS. An excerpt from the chat I had with Vishal on 25th May 2013 -

Vishal Devanath: By the time you finish, and smergers still exists and making money I would want you to come back
Krishna Bharadwaj: Sure. Hopefully you will be making a lot of money by then.
Vishal Devanath: Of course, only if I feel you can draw enough salary
Krishna Bharadwaj: Even otherwise, I will work for an year, repay the loan and come back.

SMERGERS has been doing reasonably well and though I may not be able to draw a significant salary immediately. I still feel that I will be very happy working on it. More than anything else, it is the impact which made me take this decision. We are solving the fund raising process for SMEs. Which often gets ignored by all the big investment banks.

I got this question asked several times in the last one and half year. Why MS after starting a company? Honestly, I never wanted to start another company after Refer a Geek(Employment status - It's complicated). I thought i should just work at other startups and build good software. That's what led me to join BlockBeacon and a few other startups. When Vishal approached me regarding SMERGERS, i said, what you are asking for is fairly straightforward, let me just build it in my spare time.

Vishal initially managed most of the work with the initial prototype i had built, but that is rarely the case with software. It needs constant tinkering. You have to try out new workflows every now and then, retain what works for you and throw away things which don't. I had started liking whatever i was doing for SMERGERS, but it was too late to call off my masters plan. So i came to the US and completed my masters. During the same time, we had Sagar interning with us. I can't stress how helpful it was for us. He is quick and super smart. We were very lucky to have him with us. I continued to be an advisor to the company helping Sagar build SMERGERS. He also liked what we were building, so he declined an offer from Adobe to join us full time after graduation. Which was great and we were very happy to have him with us.

Was it a good decision to come for masters?, I really don't know. But there has been a lot of learning in the past one and half year, some of the courses were good, I ended up working at USC Information Sciences Institute with a professor and I interned with Google during summer. It has made me a lot more confident than what I was. And this was the first time I stayed away from home, it was a different experience and it makes you a better person at the end of the day.

I will be leaving Los Angeles in about 2 days and I plan to spend a couple of weeks in bay area before I move to India. I will be missing some great friends and the city of Los Angeles. I look forward to a good time in Bangalore.

Employment status - It's complicated

A very small subset of my friends knew what I was actually doing for the past 2 years. In June 2011, I quit National Instruments(NI) to join a startup, but I left that within a month to pursue some of my ideas. The journey since then has been pretty good. I thought of sharing the same with others :)

I was very excited that I will be starting a company along with Arjun (ex-colleague from NI) - Refer a Geek. It was a crowd sourcing platform to find talented engineers. In recruitment, referral model has proven to be the best mode so far for all companies. Our idea was to take this referral model beyond any one company. When I discussed this with a lot of people, the feedback was positive. I started building the web app and hosted it on a Linode instance (they are pretty good). We released it on Ganesh Chaturthi (September 5th). I started sending out invitations and I was eagerly waiting for people to accept the invites and in turn, invite their friends. I did not sleep that night. Tracking numbers was really exciting, This went on for several days. Whenever I was not at home, I used my mobile to check the user stats. I used to be very happy whenever there was a steep slope and equally sad when the numbers were stagnant.

I can say that I was paranoid about the status of the server. I used to check if the server was up or not every now and then. If I look back, I tend to laugh at it :) In the meanwhile, I was getting constant feedback from users of the site. Many felt that the concept was great and many others simply loved the UI. I was happy that many were liking it. Till then there were no companies associated with Refer a Geek. This was a chicken and egg problem. Unless there are enough people in the network, companies would not be interested and unless there are enough companies associated, users would not be keen on joining the network. So I was waiting for the member count to reach a figure so that I could start talking to companies about Refer a Geek. I had no clue about how the next few weeks would be.

I started talking to several product companies. This was the first time I realized that HR in most of the companies are not approachable at all. Getting to talk to them was like a privilege. They would reply to emails after a week or two. They would ask me to get back to them after a few days every single time I called them. I was lucky enough to talk to some startups where I could directly talk to the founders and they understood the concept better and I must say it was a good starting point. I had created a job board where companies can post their openings. I created logins for some of the startups which signed up for Refer a Geek. Struggle with big companies continued to go on for several weeks. Many of my friends helped me get in touch with recruiters at their companies, but only a handful of them responded. I was running out of connections and there were not enough companies on the job board yet. I was waiting for decisions from several comapanies. In the mean time, some of the members started applying for jobs listed in Refer a Geek. I was happy about it, but it didn't last for long. Some of the companies insisted that we schedule the interviews with candidates as well. I didn't want to do it initially, but I convinced myself that there is nothing wrong in doing it since the numbers were small initially and if the numbers grew drastically, I could hire someone to do the same. I started scheduling interviews for candiadates who applied for some openings, very little did I realize that applicants can take you for a ride. If they have other/better offers, they tend to take subsequent interviews very lightly, they are not punctual w.r.t time, they don't respond properly, they don't show any interest in the company. I was totally clueless about all these until I saw them myself. For them it is just another company, but for Refer a Geek, reputation was at stake. Not to forget, before having any offer, these very guys write to you several times!

There was another problem at hand, several companies would judge candidates entirely based on resume / CV. In spite of us stressing on the fact that a candidate is good but he/she does not have the tags(It can be IIT, NIT or some other company previously worked for) they are looking for, they were not willing to talk to them. It was very frustrating. The same folks who were not considered good at one company because of the lack of previously mentioned tags, ended up working for better companies. I really appreciate Google, Facebook and the likes who do not care where you come from. If they feel that a candidate is good, they do everything to take you on board. Adding to that, if some organization states that they do not have the time to interview a lot of candidates, they can use online code checking tools like interview street which do a good level of filtering.

Several months had passed, Refer a Geek was not turning out to be as expected. It was my 5th month without any earnings and my bank balance was coming down at a constant rate :P I had struck a deal with my parents - if I don't earn enough by March 2012, I will start working somewhere. I was trying to extend that period by earning a little. The first thing that came to my mind was to do some free lancing. So I created a profile on Elance. We generally have to bid for projects.The person who has posted the project will review all the candidates and then assign the project to one of them. So building a profile is very important here. When I started, I could not get any large projects because of no history of projects/rating, which others had. I did bid for some large projects but the attempt was futile. So I had to start small. I went through all the postings and found someone asking for some help in his Python assignment. Sent him a proposal. He was confident enough to assign the project in spite of me having no track record on Elance. I finished the assignment in a matter of few hours and I see a 5 star rating on my profile. He was happy. I continued bidding for projects. Within a day or two, a PhD student from Australia wanted an image processing tool written in Python and Qt with some filters. I finished this in about two days. With these two projects, I had earned about $200 that month. Even though it was like 5 - 10 times less than my previous salary, I was happy with that.

W.r.t. Refer a Geek, many HR folks were on leave during December and January. I wanted to utilize this time properly. So I continued to bid for a few more projects. On one fine day, I got a reply for one of my bids. I just saw that the person who had submitted the project had provided his email address and he preferred communication over email as compared to the Elance interface. I was a little skeptical to deal outside of Elance since there are many instances of freelancers getting cheated. Elance has a way to ensure that one gets paid for whatever work they have done. I wanted to know if this guy had any online profile which I could see and know more about him. So I did an email search on google but it returned no results. So I sent a reply to the person asking him if we are dealing outside of Elance. I did not receive a mail for a day or two. I was looking forward to it and just out of curiousity, I searched for the same email address on Facebook. I had a mild heart attack when I saw the about section of his profile, which read - "Technical Assistant to Mark Zuckerberg". I was a lot more confident after seeing that! He got back to me and said that he is fine with transactions on Elance, he went on to say that he would like to have a conversation with me on skype before assigning the project, but none of that happened and I was hired for his project - PricePoint.

I was not happy with the progress on Refer a Geek front. I was actually in a helpless situation. Without thinking much, I decided to take up some more work. If some freelancer tells you that they don't have a boss, don't believe them! They probably have 5 - 10 different managers and each one of them will be constantly asking for status. Its not easy to manage all the work parallely. For about 3 - 4 months, I have worked on all 7 days. I had forgot the meaning of a weekend. All days were same. And I was almost following US timings. I used to sleep at 6 - 7 in the morning and wake up at around 5PM in the evening (It feels awful when you realize that the day is already over!). All this time, I used to ensure that I go for a walk in the evening. That was the only thing which kept me sane for so long. My social life had gone for a toss. I missed office very much in the first few months, got used to it after sometime.

Amidst all this, I got a call from Facebook for an opening in their Palo Alto office. I was happy but did not consider myself so good for Facebook. So I never replied to them. When my friends came to know about it, they insisted that I just give it a shot. I did the same. At least it would help me know where I stand and how facebook interviews generally are. I replied to the recruiter and I received an interviewstreet link where I was supposed to write code for a problem stated. I submitted my solution and it cleared all the test cases. Soon I was contacted by the recruiter to brief me more about the upcoming interviews. I had 3 more interviews and I was knocked out in round 4. I realized I could do much better if I had prepared well. I liked the overall interview experience.

During christmas, one of my seniors Nithish, was in India. I met him and he was talking to me about his work and I told him about whatever I was doing. He forwarded many of the projects he would get to me. He introduced me to one of his friend Justin who had some work for me. I worked with him on a project. Though he was not from a programming background, he was very keen on learning it. He had started with PHP and I insisted that he should learn Python and Django. He loved it and mastered it in a span of few months. Recently, He raised more than $50k on kickstart - Coding for Entrepreneurs . Felt great to see him do this.

Sometime during March 2012, Nithish asked me if I would like to work with BlockBeacon where he was currently working. I was a little hesitant initially but after talking to the founders, Brandon and Darshan, I was convinced that they are really focused on connecting local businesses with local consumers and I accepted the offer. Our web application was used by several businesses to get customers and it just got better with the launch of our iPhone app which was featured on TechCrunch. The team at BlockBeacon was really awesome. Everyone was very enthusiastic and I learned a lot from them - Jason was literally a coding machine and he wrote some brilliant Javascript. Recently, his app Codassium was also featured on TechCrunch.

After a few months, BlockBeacon was acquired by Dunn & Bradstreet credibility corporation. It was comparatively a large organization and did not have policies for remote employees in place. So I decided to take a break for couple of months before deciding what to do next.

I did consider pursuing masters since it is something I was keen on from sometime. So I gave my GRE and TOEFL and started applying for some of the Universities in US. Around the same time frame, my friend from NI - Vishal was looking to startup. After his MBA from IIM Bangalore, he worked with Avendus for sometime and he wanted to start a Mergers and Acquisitions platform for Small and Medium Businesses in India. He asked me if I would be interested in developing the product. Having worked with him at NI previously in the same team, I knew him well and I was convinced with the idea too. So, I decided to go ahead with it. It's been quite sometime since we started SMERGERS. It is doing well at the moment and we have a lot of expectations from it :) Hoping for the best.

Refer a Geek is currently in a Zombie state. I continue to connect students with startups. I have seen that it benefits both of them immensely. I hope some day, I am in a position to revive it and take it to the next level. If I look back, I am glad that I took this route. I have committed several mistakes in due course and these very mistakes have taught me lessons that I will never forget. I believe that all this will help me a lot in the future. I would like to thank all my friends who helped me during this period. It would have been very difficult without all the support from them.

I will be heading to University of Southern California for my masters in Computer Science this fall. I am very excited about getting back to school after 4 years :) and I will update by blog frequently from now on :)

Facebook Hacker Cup Qualifiers 2013

Hacker cup has got a lot better than what it used to be a few years back. I did like the problem set. It was good for a qualifying round. There is one significant rule which bothers me to some extent :P We are not allowed to make multiple submissions after the 6 minute timeline even if the contest is still on. This is different from every other programming competition I know of.

1. TopCoder - We can change our solution even after submission, it attracts a penalty, but its better than submitting a wrong answer.
2. CodeChef - We are notified about the correctness of the solution right then and we can always correct it. Penalty is the number of attempts.
3. CodeForces - Here, we can lock a solution if we are confident. Otherwise, we can continue to resubmit it any number of times.

I made a mistake in the second problem but I could not correct it due to the single submission rule. One of my friend had swapped the source and output files by mistake and there was no error thrown. Hope these things are taken care of in the subsequent years. Here are my solutions for the problems.

Beautiful Strings

When John was a little kid he didn't have much to do. There was no internet, no Facebook, and no programs to hack on. So he did the only thing he could... he evaluated the beauty of strings in a quest to discover the most beautiful string in the world.

Given a string s, little Johnny defined the beauty of the string as the sum of the beauty of the letters in it.

The beauty of each letter is an integer between 1 and 26, inclusive, and no two letters have the same beauty. Johnny doesn't care about whether letters are uppercase or lowercase, so that doesn't affect the beauty of a letter. (Uppercase 'F' is exactly as beautiful as lowercase 'f', for example.)

You're a student writing a report on the youth of this famous hacker. You found the string that Johnny considered most beautiful. What is the maximum possible beauty of this string?

Input
The input file consists of a single integer m followed by m lines.
Output
Your output should consist of, for each test case, a line containing the string "Case #x: y" where x is the case number (with 1 being the first case in the input file, 2 being the second, etc.) and y is the maximum beauty for that test case.
Constraints
5 ≤ m ≤ 50
2 ≤ length of s ≤ 500

Balanced Smileys

Your friend John uses a lot of emoticons when you talk to him on Messenger. In addition to being a person who likes to express himself through emoticons, he hates unbalanced parenthesis so much that it makes him go :(

Sometimes he puts emoticons within parentheses, and you find it hard to tell if a parenthesis really is a parenthesis or part of an emoticon.

A message has balanced parentheses if it consists of one of the following:

- An empty string ""
- One or more of the following characters: 'a' to 'z', ' ' (a space) or ':' (a colon)
- An open parenthesis '(', followed by a message with balanced parentheses, followed by a close parenthesis ')'.
- A message with balanced parentheses followed by another message with balanced parentheses.
- A smiley face ":)" or a frowny face ":("
Write a program that determines if there is a way to interpret his message while leaving the parentheses balanced.

Input
The first line of the input contains a number T (1 ≤ T ≤ 50), the number of test cases.
The following T lines each contain a message of length s that you got from John.

Output
For each of the test cases numbered in order from 1 to T, output "Case #i: " followed by a string stating whether or not it is possible that the message had balanced parentheses. If it is, the string should be "YES", else it should be "NO" (all quotes for clarity only)

Constraints
1 ≤ length of s ≤ 100

Find the Min

After sending smileys, John decided to play with arrays. Did you know that hackers enjoy playing with arrays? John has a zero-based index array, m, which contains n non-negative integers. However, only the first k values of the array are known to him, and he wants to figure out the rest.

John knows the following: for each index i, where k <= i < n, m[i] is the minimum non-negative integer which is *not* contained in the previous *k* values of m.

For example, if k = 3, n = 4 and the known values of m are [2, 3, 0], he can figure out that m[3] = 1.

John is very busy making the world more open and connected, as such, he doesn't have time to figure out the rest of the array. It is your task to help him.

Given the first k values of m, calculate the nth value of this array. (i.e. m[n - 1]).

Because the values of n and k can be very large, we use a pseudo-random number generator to calculate the first k values of m. Given non-negative integers a, b, c and positive integer r, the known values of m can be calculated as follows:

m[0] = a
m[i] = (b * m[i - 1] + c) % r, 0 < i < k

Input
The first line contains an integer T (T <= 20), the number of test cases.
This is followed by T test cases, consisting of 2 lines each.
The first line of each test case contains 2 space separated integers, n, k (1 <= k <= 10^5, k < n <= 10^9).
The second line of each test case contains 4 space separated integers a, b, c, r (0 <= a, b, c <= 10^9, 1 <= r <= 10^9).
Output
For each test case, output a single line containing the case number and the nth element of m.

Dynamic Programming

Dynamic Programming tutorial on TopCoder is very good. I got started with solving some problems listed as exercises in the article. I think dynamic programming can be learnt only by practicing a lot. Here are my solutions for some of the problems listed. Longest Increasing sub sequence is a good place to start learning DP. I have explained the logic in the form of comments.

Longest Increasing subseqence

Given an array, find the length of the longest monotonically increasing sub sequence.
For example: Given 1, 4, 2, 3 -> the answer is 3 because of the sequence 1, 2, 3.

ZigZag Sequence

A sequence of numbers is called a zig-zag sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a zig-zag sequence.

For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because its first two differences are positive and the second because its last difference is zero.

Given a sequence of integers, sequence, return the length of the longest subsequence of sequence that is a zig-zag sequence. A subsequence is obtained by deleting some number of elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.

Bad Neighbors

The old song declares "Go ahead and hate your neighbor", and the residents of Onetinville have taken those words to heart. Every resident hates his next-door neighbors on both sides. Nobody is willing to live farther away from the town's well than his neighbors, so the town has been arranged in a big circle around the well. Unfortunately, the town's well is in disrepair and needs to be restored. You have been hired to collect donations for the Save Our Well fund.

Each of the town's residents is willing to donate a certain amount, as specified in the int[] donations, which is listed in clockwise order around the well. However, nobody is willing to contribute to a fund to which his neighbor has also contributed. Next-door neighbors are always listed consecutively in donations, except that the first and last entries in donations are also for next-door neighbors. You must calculate and return the maximum amount of donations that can be collected.

Solving the performance bottleneck

Often, we come across problems which need better and faster solutions. It may seem like we have tried out everything and we do not have anything else for the given scenario. But some solutions seem to be just amazing, I have come across some of them where these performance bottlenecks have been solved using very simple design.

1. HTTP reverse proxying

Apache is the most common web server used by many websites. Apache is very good for serving dynamic content, but it has some limitations. As load increases on the server, performance of apache starts going down, whereas some lightweight servers like nginx perform really well for static content.

An instance of apache thread is tied to a client and it is busy as long as the data transfer between the client and server is going on. This can be problematic if many clients are accessing the site from a slow connection. Slower the connection, more is the time needed to serve the data and free up the thread.

Client <-----> Server(Apache)

On the other hand, nginx uses a single thread to manage all the connections. Like apache, slower connections will not tie up the server. How do we take advantage of this? By placing an instance of nginx between the client and server, we can get some amazing performance boost and this technique is called as reverse proxying.

Client <-----> Nginx on port 80(Reverse proxy) <-----> Server(Apache on some other port)

Whenever we make a request to the server, Nginx listens to our request on port 80 and forwards it to apache which is listening on another port, which processes the request and returns the http response. Since both Nginx and Apache are running on the same machine, the data transfer is really fast between apache and nginx. Apache processes are released in no time. We are taking the best of the two servers, apache for serving the dynamic content and nginx for static content. More information about reverse proxying can be found Mark Maunders' blog.

2. Compression in MS SQL Database

When I attended one of the boot camps as a part of Microsoft Student Partner programme, Vinod Kumar spoke about MS SQL server, where he mentioned that data is compressed before saving it on disk and it has resulted in better performance. One may be surprised how doing something extra can speed up operations? It so happens that disk IO is far more time consuming that processor operations. So, transferring of compressed data is reducing a lot of time.

Transfer time of Compressed data + Decompression < Transfer time of Uncompressed data

This is analogous to us sending a zipped file to some of our friends via email. Internet speed is a bottle neck and we rely on the processing speed of our computers to compress and decompress the files which result in faster sending and receiving of data.

3. AWS Data transfers

This one was least expected but it truly happens. I attended the Hadoop summit last year and attended a talk by Simone Brunozzi. where he was talking about how one can perform map reduce on Amazon map reduce platform. During the QnA session, one of the delegates asked the following question:

Since map reduce deals with humongous amount of data, to even take advantage of the platform, we have to upload all the data to Amazon servers, which is very troublesome since it may take several weeks to transfer all the data.

And this was the answer

You can courier us your hard drives, we will plug them in our high speed data centers and you will have access to your data on our map reduce platform within 2 to 3 days.

Many were surprised, and some asked. What?! do you really do that?? and the answer was yes. Simone went on to quote an example where tanenbaum was asked to devise a backup solution for storing huge volumes of bank transaction details. Considering the connectivity available at that time, tanenbaum said:

"Never underestimate the power of bullock carts carrying hard drives on a highway!"

So, before we devise complex solutions, it is important to see if there is something simple and more elegant :-)

MVC in client side javascript using Backbone.js

As internet applications are getting more rich, designing user interfaces for the same gets complicated. Designing an application like GMail can be very complex since it is feature rich and one action is directly or indirectly related to several sections of the user interface.

I came across this javascript framework called "backbone.js" few months back, I could not appreciate it much till I wrote an application myself using backbone.js. I wanted to see the benefits of using backbone and I must say I am impressed with it.

Some background about how websites/applications function:

What we see in our browser consists of the following:

1. Data

All the information that we are interested in accessing. For example our mails. What we consume at the end of the day is the content of the email and the metadata associated with it, like sender, date and time when it was sent, people who are cc'd etc..

2. Display

Browser uses a markup language called as HTML to dispaly all the data. HTML controls the layout of a webpage. This can be thought of as a blue print of a building. We know where exactly a room is going to come.

3. Style

It would be boring to see all the above data without any styles applied, it is these small things which make a user actually choose some services. How many times have we moved away from websites saying, "the UI is really a turn off". If display is our blueprint, styling can be thought of as the work of an Interior decorator who makes buildings beautiful by applying some creativity w.r.t colors, images etc.

4. Events

In the initial days of interet, there used to be just pages linked between each other using hyperlinks. clicking on one link will take us to another page, along with some forms for entering data and posting it to the site. Nowadays, we are seeing more and more features on the browser which were only possible in desktop applications previously. This opens a whole range of possibilities, for example, facebook lets us view all photos in an album without actually moving away from the page. All these events are handeled by Javascript for us.

MVC

MVC stands for Model View Controller. It is a design pattern where we separate the data from the way it is defined, manipulated and displayed. One of the main reason why we use this design pattern is to ensure clean and organized code which makes maintaining a software comparatively easy.

MVC on server side

To understand how MVC has helped us organize the code better, lets take a look at this PHP script which reads a bunch of rows from the database and displays it on the screen.

If we notice clearly, this single script does it all, right from opening a connection to the database, to retrieving the records, then rendering the html for the respective records. As our program grows, it becomes extremely difficult for us to manage it, since making a change to some database queries will be on the same file and some minor changes to styling will also go to the same file. We are tying everything together. This way there is a lot of dependency between developers, designers and other stake holders. For a project to progress without bottlenecks like these, it is very important for us to decouple different segments and have a well defined interface for interaction between these blocks.

This is how we can remodel the design using MVC.

1. models.py file consists of code which deals with data only.

2. views.py consists of code which is used to fetch the records from the model and render it to the template.

3. template.html consists of the markup with variables embedded in it.

There by structuring the code to a great extent.

MVC on client side

Lets look at this application:

Model - Mail data represented in the data.js file.

View - the html display of each of the mail and the side menu.

Some advantages of using MVC design on the client side:

1. Streamlined Event handling

All our operations are on the models, we manipulate the data directly and we add hooks such that, whenever there is a change in the data, the view automatically renders the html which contains the latest data.

In this application, the moment we 'star' any mail, the 'star' field in the model gets modified which triggers the callback 'render' method. Similarly, we add hooks to reflect the change in models for the inbox details, like number of unread mails, number of starred mails etc.

2. Reduced data transfer

The possibilities are vast when we are delegating some processing to the browser. Lets take this example. We have a table which consists of 10 records and we are interested in sorting the records based on different fields in the table. We can get a sorted table using the SQL Query

SELECT * from persons ORDER BY '<somefield>'"

but it would mean, more interaction with the server, one more hit to the database, the complexity of sorting the records adds up.

We know that javascript can be used to manipulate data in the browser, we can just use the clients computing power to sort the table. Isn't it reducing a lot of delay for the user (Request -> Database -> Rendering -> Response )? From the infrastructure perspective, we need less processing power on the server side.

Lets take the example of rendering a template on the server:

Length of this template syntax: 258 Characters

players = [ {'name': 'A' , 'games' : [10, 20, 30]} , { 'name': 'B', 'games': [30, 50,60] } ]

Length of the data: 82 Characters

after rendering the template using the data provided above, we get the following hypertext:

Length of the rendered HTML : 426 characters.

Length(Our initial template + Data) = 258 + 82 = 340 characters!

We are including a lot of markup in between the data when we are rendering the template. All the words <li>, <div>, scored, runs, Satistics is adding up to the amount of html which will be sent to the client from server.

Is embedding of data in between the html elements something that cannot be done by the browser?? Definitely not, it can be done. and we get a lot of improvement in terms of speed.

3. Caching templates

Some websites load amazingly fast, don't they? Like facebook. The header, the side bar and few other segments load in no time, which is followed by all the posts. One great advantage of separating data from markup is caching. We can cache templates, scripts, stylesheets and they can be served from a CDN which will make loading of websites amazingly fast.

Looking forward to use backbone.js in some of my future projects.
Demo and Source

Porting to Django

I recently came across a job posting by Kyle of Justin.tv. In the second line, it read

"We are porting the justin.tv website from RoR to Django"

what?! That is probably the first time someone is actually porting their application from RoR to Django. at least the first one I am coming across. I really don't know the reason why justin.tv is doing that. But I am happy to know that Django is being taken seriously by a lot of companies which are serving heavy traffic.

Justin.tv is a YCombinator funded startup and it is doing a fantastic job w.r.t streaming Videos. Some other companies which are serving humongous amount of traffic using Django include Disqus (A commenting framework), Spotify( Music sharing on social networks) etc..

Not just this, an Indian company which is doing great in the recent times, inMobi is porting a bunch of its Java applications to Python. One of the architect there talks about it. I am quoting it from his linkedin profile :

Movement into Python from incumbent technology platform - Java, is the company's strategic initiative with foresight to enable better maintainability of software, faster turn around time for new requirements and most of all, to keep developers happy.

I would be interested to know if anyone else has migrated to Python/Django recently from other frameworks. and also what made them chose Django over other options available.

strtok and thread safety!

Recently, I stumbled upon this method "strtok" in C which is used to split a string based on a delimiter. This is how it is used:

1. If str is a string, start from the beginning of the new string.
2. If str is NULL, start from the place where it had left in the last call.

What this implies is, you simply cannot split two strings in parallel. Imagine the following scenario. Two threads executing simultaneously, one of them is splitting the string str1 and another one is splitting the string str2.

let us consider the following order for execution:

strtok(str1, ",") // thread 1
strtok(str2, ",") // thread 2

token = strtok(NULL, delim); // thread 1
token = strtok(NULL, delim); // thread 2

We will get only the first token from str1 since the buffer of strtok is overwritten the moment we call strtok(str2, ",") in the second thread. What's worse is, strtok alters the input string in order to keep track of the position of the next token. I don't know why this was so horribly designed, anyone?

Update: Thanks to Vijay and Debarshi for pointing out strtok_r which is thread safe. I wasn't aware of this.. Thanks guys..

Deploying Django with Fabric

I have been using Django for quite sometime now. Deploying the application on a production server is a lot of effort, right from installing all the required packages, configuring mysql, apache, syncing the application from the repository etc. Doing this the first time may not be irritating but subsequent installations are very frustrating.

Writing a shell script is something many would think of, but that is old! Fabric lets us write a lot of code in python for automating the boring tasks. I got started with it, as and when I installed the packages on my server , I was compiling the script needed for fabric. Once I was done with the setup, even my fabric script was ready! Ran that on a clean machine by changing the ip, worked like a charm. The best part about fabric is you don't have to leave your machine at all, no ssh.. just $fab command from your shell.

I found this awesome video by Jacob Kaplan Moss. He starts off with deploying on a single instance, then using a separate instance for database and finally adds a fail over application server. Its pretty long ( 3 hours ) but contains a lot of useful information. Do watch it.

If you use it once, I am pretty sure. you will never look back :-)