Thursday, March 16, 2017

Implement Text Editor with Gap Buffer

Implement Text Editor with Gap Buffer

Gap Buffer is a data structure which can be used to implement text editor. The advantage is that insertion/deletion can be very efficient and the data structure is simple. The disadvantage is when cursor changes its location frequently or the gap is frequently full, there will be a lot of copying operation, which is costly. The following gives more details about gap buffer.

  • Basically gap buffer can be implemented as an array (or a dynamic array) with some pointers to differentiate three regions: the segment before the gap, the gap, the segment after the gap.
| the front segment  |   the gap  |  the back segment  |
  • The location of the cursor in the text editor decides the border between the front segment and the gap. A example is given here:
We had a [            ] big day
  • As the above example, "We had a" is the front segment, "[   ]" is the gap buffer and "big day" is in the back segment. 
  • When insertion, new text is filled in the gap buffer, the start pointer of the gap buffer also moves accordingly. If the gap is full, we need to create new gap buffer and we may also need to move all the content in the back segment backwards.
  • When deletion,  we only need to move the start pointer of the gap buffer forwards if we are deleting the text in the front segment or  the end pointer of the gap buffer backwards if we are deleting the text in the back segment.
  • If we move the cursor, for example, the cursor is between "We" and "had" now:  "We [     ] had a big day". We need to copy the "had a" which was originally in the front segment to the back segment.

Sunday, February 26, 2017

Preparing for Design questions

Many companies including Amazon have a system design round.
I have collected some material to prepare for the same :









Hope this helps!!

Friday, February 24, 2017

Saving contacts information using tries

Implementation for :

Code :
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

struct trie {
    int isleaf;
    int child_cnt;
    trie * t[26];

int index(char c) {
    return c-'a';
trie * new_node() {
    trie * node = (trie *)malloc(sizeof(trie));
    for (int i = 0; i<26; i++) {
        node->t[i] = NULL;
    node->isleaf = 0;
    int child_cnt = 0;
    return node;

void add (trie * root, string s) {
    int len = s.size();
    for (int i = 0; i< len; i++) {
        if (root->t[index(s[i])] == NULL) {
            root->t[index(s[i])] = new_node();
        root = root->t[index(s[i])];
    root->isleaf = 1;

int find(trie *root, string s) {
    int len = s.size();
    for (int i = 0; i< len; i++) {
        if (root->t[index(s[i])] == NULL) {
            return 0;
        root = root->t[index(s[i])];
    if (root) {
        return root->child_cnt;
    return 0;

int main(){
    int n;
    cin >> n;
    trie * root = new_node();
    for(int a0 = 0; a0 < n; a0++){
        string op;
        string contact;
        cin >> op >> contact;
        if (op == "add") {
            add(root, contact);
        } else {
            cout<<(find(root, contact))<<endl;
    return 0;

Friday, February 17, 2017

Here are 12 highlights of the Economic Survey 2017

Here are 12 highlights of the Economic Survey 2017:
* Demonetisation impact: The government says the adverse impact of demonetisation on GDP growth will be transitional. Real GDP growth in 2017-18 is projected to be in the range of 6.75 – 7.5 per cent, once the cash supply is replenished.
* Industrial growth to cool: Growth rate of the industrial sector estimated to moderate to 5.2 per cent in 2016-17 from 7.4% last fiscal. The agriculture sector to grow at 4.1 per cent in the current year up from 1.2 per cent in 2015-16
* Per-capita GSDP: Real per capita GSDP between 1983 and 2014 has shown across-the-board improvement
* Remonetisation: The Economic Survey 2017 has suggested quick remonetisation, push for digitisation, bringing land and real estate under GST ambit, reduction in taxes and stamp duties and an improved tax administration system as key reform measures to ensure long term economic benefits.
* States’ performance: There has been an improvement in the financial position of states over the last few years. The average revenue deficit has been eliminated, while the average fiscal deficit was curbed to less than 3 percent of GSDP. The average debt to GSDP ratio has also fallen. Centre’s Fiscal Responsibility and Budget Management (FRBM) Act, mirrored by Fiscal Responsibility Legislations (FRL) adopted in the States.
* NPAs: As per the Survey, gross NPAs has climbed to almost 12 per cent of gross advances for public sector banks at end-September 2016. At this level, India’s NPA ratio is higher than any other major emerging market, with the exception of Russia. The consequent squeeze of banks has led them to slow credit growth to crucial sectors-especially to industry and medium and small scale enterprises (MSMEs)-to levels unseen over the past two decades. As this has occurred, growth in private and overall investment has turned negative . A decisive resolution is urgently needed
* Asset rehabilitation: Survey suggests setting up of a centralised Public Sector Asset Rehabilitation Agency that will look after the largest, most difficult Cases, and make Politically Tough Decisions to reduce Debt .
* Poor targeting: According to the Survey, redistribution by the government is far from efficient in targeting the poor. The Survey points out that the capacity of the State in delivering essential services such as health and education is weak due to low capacity, with high levels of corruption, clientelism, rules and red tape. At the level of the states, competitive populism is more in evidence than competitive service delivery.
* Universal Basic Income: The Survey has advocated the concept of Universal Basic Income (UBI) as an alternative to the various social welfare schemes in an effort to reduce poverty. The Survey points out that the two prerequisites for a successful UBI are: (a) functional JAM (Jan Dhan, Aadhar and Mobile) system as it ensures that the cash transfer goes directly into the account of a beneficiary and (b) Centre-State negotiations on cost sharing for the programme.
* Property tax: A study done for the Survey shows that property tax potential is large and can be tapped to generate additional revenue at city level. Satellite imagery can be a useful tool for improving urban governance by facilitating better property tax compliance.
* Job creation: The Survey says Apparel and Leather industry are key to generation of formal and productive jobs: recommends reforms in labour and tax policies to make the Apparel and Leather sector globally competitive. The Survey adds that these sectors provide immense opportunities for creation of jobs for the weaker sections, especially for women, and can become vehicles for broader social transformation in the country.
* Labour migration: New estimates of labour migration in India have revealed that inter-state labour mobility is significantly higher than previous estimates. Relatively poorer states such as Bihar and Uttar Pradesh have high net out-migration. Seven states take positive CMM values reflecting net in-migration: Goa, Delhi, Maharashtra, Gujarat, Tamil Nadu, Kerala and Karnataka. Policy actions to sustain and maximise the benefits of migration include: ensuring portability of food security benefits, providing healthcare and a basic social security framework for migrants – potentially through an inter-state self-registration process.

IAS topper notes GS, eco and other topics

Download link :

Download 25 years civil services prelims exam papers

Download Link :

Tuesday, February 14, 2017

IAS interview experience - 5

Date – 30th April 2014
Board – Prof David R Syiemlieh
Detailed Application Form (DAF) – Akand Sitra's Repository - Google Docs

The attendant opened the door for me, there were five members including the Chairman sitting around a circular desk. My seat was opposite to the Chairman’s and I had two Members on either side. It was more of a discussion desk rather than an interview desk. Let us call the members as CM, M1, M2, M3 and M4.

A – May I come in Sir?

CM – Come in, come in.

A – Good morning Mr.Chairman, good morning sirs.

CM – Good morning Sitra, please take your seat. (My name is Akand!!)

A – Thank you sir. ( Sat comfortably, it was a very comfy chair)

CM -So, you were born in Anantapur? (Reading my DAF)

A – Yes, sir and my home town is Kurnool.

CM – Achcha, and you live in Bangalore right now?

A – Yes sir, I’am from Bangalore.

CM – Achcha, your hobby is cycling? How did that start?

A – Sir, back in college, cycling was a necessity. Hostels were far from classes and also far from mess. So, all of us used to cycle to all places. So, a necessity had transformed into a passion. We started going on long-distance cycling trips. We cycled till Mahabalipuram which is over 50 km away and also to Kovalam beach near Chennai.

CM – Hmmmm. Around two days ago, there was another candidate with a strange hobby. It was sparrow watching. Can you tell me why sparrow watching in big cities, like Delhi is declining?

A – (Why is he asking me questions on someone else’s hobby?! Maybe he is trying to make this into a stress interview) Sir, one of the main causes for decline of sparrow watching is due to the immense pollution that every city has these days. A few decades ago, sparrow watching would not be considered as a hobby as there were sparrows everywhere! It has become a “hobbby” now because they are almost endangered.

CM – Hmmmm.. Do you know who was the first sparrow watcher in India?

A- Smiled. I don’t know Sir.

CM – Who was the founder of the Indian National Congress?

A – (Why is he asking random unrelated questions!) Sir, Dadabhai Naoroji.

CM – Ummm, along with Mr. A.O.Hume.

A – Yes Sir.

CM – He was one of the first sparrow watcher in India. Not many know this side of him, many know him just for founding INC. He was an incredible bird watcher.

A – Smiled. Okay Sir. (No clue why he was saying all this)

CM – Achcha, you worked in this company called Sabre Holdings? As an Associate Product Specialist? What was your exact work there?

A – Sir, I had joined the job in July after writing Prelims in May. Within three months I quit the job because I couldn’t find time to prepare for Mains. So, they did not give me any solid work till then. I was still in basic training.

CM – Look Sitra. (My name is Akand!!) When you talk with your peers, you can use words like “Mains”, but when you come to important interviews like this you should not only be politically correct but also academically correct. Mains can be anything.

M4 – Yeah! It can be power mains or water mains too! So what Mains is it?

A – (I understood that this was one of the stupidest questions. They were just trying to make me uncomfortable and wanted to see whether I would panic) I grinned from ear to ear. True sir, Sorry. I meant Civil Services Mains. I should be more careful. Then gave a broad smile.

CM – Okay. Tell me three best qualities you think you have.

A – (I was blank, no quality was coming into my mind) Ummm Sir, Leadership. I had assumed many leadership roles in college and I think I did a fair job.

Ummm, second would be honesty. Smiled.

Third, let me think Sir. Nothing is coming into my mind.

CM – Your smile man! Your smile is your best quality. Never forget that.

A – Yes sir, my smile. Thank you sir. And gave a big grin again.

CM – Tell me your three negative qualities now.

A – Well sir, first would be I don’t know what to talk when. I should learn to be more diplomatic. Like just now, I should have said Civil Services Mains instead of Mains.

CM – Thats all right. You can always learn that in training. Second?

A – Ummmm, I always take too much in my plate.

CM – That is, you bite more than you can chew?

A – Yes sir, back in college, I tried to organize a lot of events simultaneously. I think, if I had taken them one by one, I could have done a much better job.

CM – And third?

A – (I thought for a while) I make friends very easily Sir. That is, I have trust issues. I am very trusting.

CM – Laughing. It’s okay. That is not a negative.

Then he asked M1 to continue.

M1 – You do yoga? Tell the different types of yoga.

A – (I totally forgot this answer) Sir, there is hatha yoga, kundalini yoga, meditation yoga etc. I dont remember others.

M1 – Meditation yoga??? Hmmmm.. What is transcendental meditation?

A – I am not sure of the answer, can I take a guess Sir?

M1 – No, leave it. You know Art of Living? Who is its founder?

A – Sri Sri Ravishankar… Ji.. Sir.

M1 – Hmmm.. Who was his guru?

A – Sorry Sir, I don’t know that.

M1 – (Irritated) Forget yoga. Are you thorough in anything?

A – Sorry sir, I have been doing very basic yoga under my school yoga master, Mr. Rawat. Very simple pranayamas and asanas like anulom-vilom, vrikshasana etc. I am not really thorough in the theoretical aspects of yoga as I had always concentrated only on its practical uses.

M1 – You didn’t get me. Let me repeat myself. Are you thorough in anything?

A – Sir, biotechnology sir.

M1 – What biotech did you learn? Industrial or research?

A – Sir, we had courses on both industrial biotech like reaction engineering and also on research biotech like cell biology and tissue engineering. I did two internships, one in an industry and one in an research institute, IMSc.

M1 – What is the difference between industrial biotech and research biotechnology?

A – Gave a long textbook definition.

M1 -You know WTO?(Yes, Sir) What is TRIPS?

A – Trade related aspects of intellectual property rights is a policy… blah blah.. talked about traditional knowledge… blah blah.. patenting healing properties of turmeric powder, yogic postures, bad for indigenous growth…. etc etc.

M1 – But, how is patenting turmeric illegal? It is mere documentation of process, right?.

A – No sir. When a western company patents the healing properties of turmeric powder, it gains the sole right for all its properties and its commercialization. In countries like India, turmeric powder is in use for centuries. After such a patent, any traditional use will be illegal and all Indians should start paying royalty for using their own indigenous product. So intellectual properties must be regulated hence the necessity of TRIPS.

M1 – Okay, tell me the three requirements for patents.

A – Ummmm, originality? Innovation?

M1 – No. It’s novelty.

A – Okay sir. ( I thought my interview was very bad till now. I had to gain the upper ground soon or else I would get very average marks. It seemed like M1 hated me and now I had to answer more carefully. They had manipulated me enough, it was my time to manipulate them)

M2 – Tell me the difference between botany and biotechnology.

A – Sir, botany is the study of plants and organisms whereas biotechnology is the study of usage of modified living organisms for economical purposes for humans, like GM crops, drugs etc.

M2 – Okay, tell me a 20 th century Indian botany scientist.

A – Ummmm, Sir, Jagadish Chandra Bose?

M2 – Correct, can you tell me his achievements?

A – He was the first to discover that plants could communicate with each other.

M2 – Okay, any other discoveries?

A – Also something related to radio waves.

M2 – No, that is in physics, I’am asking in botany.

A – I think that’s all sir.

M2 – He also discovered that plants were living things like us too. Yes, as you said, they can communicate too. Do you know any English 20th century botanist?

A – Umm sorry sir, I cant recall any.

M2 – Ever heard of Luther Burbank?

A – Yes sir, the name is familiar but I don’t recall anything else about him.

M2 – He was a great botanist too. Without using biotechnology like in recent days, he used to make better crops. Can you tell me how?

A – By cross-breeding between two different species of the crop sir. In-breeding.

M2 – Yes, correct. He also invented something called “edible cactus”. Can you explain what that is and how he could have done it?

A – Hmmmm. Sir, usually cactii have thorns on them to protect themselves from animals which try to eat them. Maybe, Burbank tried to communicate with the cactus and tried to tell it that the surrounding is safe for it. There are no animals in the area to eat it. This made the cactus not grow the thorns, thus using communication he got cactus without thorns which can be edible.

M2 – Yes, correct. On a totally unrelated note, can you tell me who said this quote? “I am not an Athenian or Greek, I am a world Citizen”

A – Ummm, Socrates??

M2 – No, it was Aristotle. (It is Socrates actually) Can you tell me what you understood from it?

A – In today’s globalized world, the whole world is becoming one global village. The boundaries between different states, nationalities are eroding day by day. With communication technology, one can contact any part of the world instantly. Every country is becoming more and more similar with common companies like McDonalds etc. So, distinguishing ourselves through countries is being replaced by becoming a global citizen. Who knows Sir, in the near future all countries might become one and literally replace with world citizenship as prophesized by Aristotle. (It was Socrates)

M2 – Hmm. You are partially correct. But, according to me I think he was saying that we all are humans first. Let’s be human beings before dividing ourselves into various countries.

A – Yes Sir. But he used the term “world citizen”, so I think it is much more than just being a human being.

M2 – Yes, Sitra. You are right. (My name is Akand!!!)

CM – What are your preferences?

A – First, the administrative services Sir, then the police services..

CM – Administrative? For which country? British eh? Bhutan eh?

A – I am sorry Sir. I did it again. I should be more academically correct. I meant the Indian Administrative Services. (He was trying to stress me out again.)

CM – Achcha, always be diplomatic and think before you answer. (Yes Sir) What are your state preferences?

A – Sir, I don’t mind working in any part of the country, every state has its own problems. But, since the choice of preference was given I would take Andhra Pradesh, because of familiarity with ground problems.

CM – Hmmm, next? (Sir, Karnataka). Next? (Tamil Nadu) Next? (Kerala). (He was testing me whether I had actually remembered my state preferences. Many people just allocate them randomly, but thankfully I remembered all the South Indian states)

M3 – You said your first positive quality is Leadership. Can you tell me the difference between a leader and an administrator.

A – Sir, a leader should be a person who can enthuse his subordinates anytime so that they are willing to work for the profit of the organization. An administrator is more a mix of a manager and a leader. A manager just needs to facilitate and give directions. So, an administrator should be an efficient leader and an effective manager.

M3 – What is this S-Net ambassador? What have you done there?

A – Sir, Sustainability Network is an organization in IIT Madras, which takes care of the sustainability of the energy resources we use. My work as a S-Net ambassador was to calculate the total energy consumption in my hostel and also to calculate the unnecessary wastage going through. I was also asked to calculate the area on the roof where a solar water heater could be established. I made a report with all my recommendations and observations in it.

M3 – Ok. Do you Food stability act?

M4 – He means Food Security Act.

A – The NFSA? Yes sir, the idea behind the act was that everybody should be comfortable regarding food. Noone should sleep on an empty stomach.

M4 – Everybody? Are you sure?

A – Yes sir, I was coming to the technical part. The govt gives subsidized food grains to 2/3rds of the population. 75% in the rural areas and 50% in the urban areas. So that everybody can be happy and not hungry.

M4 – Everybody?

A – Mostly, people below the poverty line Sir. But the core idea was everybody should be well-fed.

M4 – Everybody? Think harder. It is called the National Food Security Act.

A – (Then it dawns on me) No Sir, not everybody. Only Indians.

M4 – Yes correct. It is only for the Indian citizens and not the world population. You should be very careful in your choice of words. This is the third time. In one instant, you changed the beneficiaries from 1 billion to 7 billion!

A – (Gave a sheepish grin)(Smiled) Yes sir, sorry. I should be academically correct. ( Even M4 was playing with me like CM. Why is everyone trying to make me tense?)

M3 – Okay, you are from Andhra Pradesh. Tell me about the status.

A – Sir, recently after the division of Andhra Pradesh into Telengana and residual Andhra Pradesh, the future is going to be both grim and hopeful for the residual Andhra. With Hyderabad gone to Telangana, more than 60% of the revenue is gone. With most of the Godavari and Krishna running through Telangana, there will be water shortage for the residual Andhra too. Not only that, all educational institutions, offices, important colleges, everything is gone. I am not saying the division is a bad thing, the emotions of the Telangana people must be respected. But the repercussions on the residual Andhra are very high. It has nothing right now, that is the sole reason why I want to go the Andhra cadre. The IAS officers who join now will be pioneers in rebuilding the state. I want to bring a planned change in all districts and bring Andhra back to its former glory. And the whole Andhra is united this time to bring back enormous developmental change. So, even when the situation is very bad everyone is hopeful of starting everything back from scratch Sir.

M3 – Okay, you said Hyderabad is gone to Telangana right? What other important cities are in Andhra now?

A – Sir, Vishakhapatnam. Vijaywada, Tirupthi etc. Mostly all the district capitals, most of them are big towns not large metropolitan commercial cities like Hyderabad.

M3 – Okay, and these cities are in residual Andhra?

A – Yes Sir.

M4 – (Reading the Accomplishments section in my DAF) What is this NCO? AIR 225?

A – NCO is National Cyber Olympiad where “Indian” students from all over the country had participated. It was mostly an online exam which tests our computer skills. I got rank 225 all India.

M4 – What is cyber crime?

A – Any crime made through computer technology and the internet is cyber crime Sir. Like hacking govt websites, online transactions of money etc.

M4 – KVPY. “Offered” to join IISER? I didnt understand. You were offered to join an institution?

A – Yes Sir, Kishore Vaigyanik Prothsahith Yojana is a govt scheme where exams are conducted to take students into basic sciences. I wrote the exam in my 12th std and I was offered to join IISER with a stipend after I cleared it. But then, I got through IITJEE also, so I declined this offer to join IIT Madras.

M4 – Hmmm. Good. What is this Al Gore Sustainable thing?

A – Sir, Al Gore Sustainability Technology Venture Competition was an event founded by a Professor in Carnegie Mellon University. She had come to IITM and she said she wanted volunteers to organize this event and I was one of the volunteers. We organized it in a grand scale. It is basically a competition for sustainable business plans for upcoming start-ups. I saw many astonishing designs which can be put for use in rural India.

M4 – Okay, who was Al Gore.

A – He was the ex-Vice President of the US.

M4 – Yes, he was into politics too and not only the environment. Did he win a Nobel Prize?

A – Yes sir, he won one.

M4 – Are you sure? No he did not.

A – I think he did Sir. Smiled.

M4 – You have Marathons in your DAF too? Tell me where the word marathon is derived from.

A – I am sorry Sir, I dont know. I think it is another Greek word.

M4 – You and your friends used to run marathons but never discussed about the origin of the name?

A – Smiling. Yes sir, sorry sir. We were more worried about completing the marathon only. He laughed.

M4 – What is this Eureka run?

A – It was the name of an NGO which organized a run Sir. After running, whatever money we contributed, they would make a good use of it.

M4 – Okay, tell me how the word “Eureka” originate?

A – (Trying to remember.) Sir, I know the story. There was a guy sitting in his bath tub and he came out crying Eureka after discovering a scientific principle.

CM – “Guy”!? A guy? Was he wearing jeans? Was he listening to his iPod?

A – Oops Sorry Sir. I did it again. (Smiling)(He was smiling too) I should be more academically correct in my statements. A respected scientist came out running into the streets after discovering buoyancy sir.

M4 – What was his name?

A – (Tried hard to think but forgot this simple fact.) Sorry sir, I don’t remember.

M4 – No, you cant say I don’t knows anymore. (Laughing) Take a guess.

A – Sir, Aristotle. :P
M4 – No, it was Archimedes.

A – Yes sir!  (With a sudden emotion of recognizing the simple answer)

M4 – So you play Kho Kho and Kabaddi too? Nobody plays these games anymore.

A – Yes sir, I used to play back in school. I was in Kendriya Vidyalaya so all these games were compulsory.

M4 – But, isn’t Kho Kho a girl’s game?

A – No Sir! It is played by boys too. We have a national boys kho kho team in our school.

M4 – Good good. ( I don’t know why he was impressed when I said my school had a team. I had nothing to do with it :P)

M4 – Sitra, you have done so many things! And you are not even 23 yet!

CM – Yes yes, he is too young. You can see that on his face itself.

M4 – I think he is one of the youngest we have seen in this stage right?

A – (Smiled) Thank you sir.

M4 – Okay, tell me about biodiversity. How does it harm humans?

A – Sir, biodiversity is the variety of living organisms in the surroundings. But sir, people keep saying if we destroy the biodiversity, “nature” will be destroyed. I think it is the other way round. Nature will always be there. It was there in the past, it is there now and it will continue to be in the future. When humans try to harm the environment through pollution etc., they are not harming nature. But they are harming themselves. It is their species which is going to get destroyed and not nature. Through usage of too many polluting chemicals, global warming, melting of polar caps, submerging of coastal areas, nothing serious is happening to nature. It is our survival that we should be worried about.

(I was on a high when I was saying this)

M4 – Okay. But can you be more specific how biodiversity changes can affect humans?

A – There would be adverse effects on the food chain. The whole biodiversity is a large web Sir. Even if there is a disturbance in one end, the whole web can get affected. Every species has a specific function in nature, if we destroy that species, we are harming ourselves and the whole fabric Sir.

M4 – Okay. Tell me which is better. Small states or big states? Small states like Goa have been developed too and large states like Gujarat are developed too. So should we have many small states or should we have very few large states??

A – Sir, every issue has both pros and cons. If we have large states, the ground level administration can become tough, but large states send a large number of MP s to the Parliament and they have the numbers to bring in state-specific policies. Whereas, small states can be administered very well because of less area and less population, but they send only 1 or 2 MP s. 1 MP doesnt make much difference in 545 other MP s Sir. So, I would say it should be in middle. The state should be small enough to be managed well and also large enough to get enough attention in the Parliament.

M4 – Haha so you took the middle ground. Safest approach.

CM – Thank you Sitra, your interview is over. (My name is Akand!!)

A – Thank you Sir. ( I got up and was about to leave)

M4 – What is the meaning of your name, Sitra?

A – Sir, my name is Akand. Sitra is just a family name. :)

CM – Achcha, makes more sense now.

A – Thank you Sir.

And left. Came out at 10 45. Half an hour exact.