कहना सच्ची है मधुशाला

Featured

कहना सच्ची है मधुशाला

अपने युग में सबको अनुपम ज्ञात हुई अपनी हाला,
अपने युग में सबको अदभुत ज्ञात हुआ अपना प्याला,
फिर भी वृद्धों से जब पूछा एक यही उत्तर पाया -leader
अब न रहे वे पीनेवाले, अब न रही वह मधुशाला!।१२५।

एक बरस में, एक बार ही जलती होली की ज्वाला,
एक बार ही लगती बाज़ी, जलती दीपों की माला,
दुनियावालों, किन्तु, किसी दिन आ मदिरालय में देखो,
दिन को होली, रात दिवाली, रोज़ मनाती मधुशाला।।२६।

मुसलमान औ’ हिन्दू है दो, एक, मगर, उनका प्याला,
एक, मगर, उनका मदिरालय, एक, मगर, उनकी हाला,
दोनों रहते एक न जब तक मस्जिद मन्दिर में जाते,
बैर बढ़ाते मस्जिद मन्दिर मेल कराती मधुशाला!।५०।

यम आयेगा साकी बनकर साथ लिए काली हाला,
पी न होश में फिर आएगा सुरा-विसुध यह मतवाला,
यह अंतिम बेहोशी, अंतिम साकी, अंतिम प्याला है,
पथिक, प्यार से पीना इसको फिर न मिलेगी मधुशाला।८०।

मेरे अधरों पर हो अंतिम वस्तु न तुलसीदल प्याला
मेरी जीव्हा पर हो अंतिम वस्तु न गंगाजल हाला,
मेरे शव के पीछे चलने वालों याद इसे रखना
राम नाम है सत्य न कहना, कहना सच्ची मधुशाला।।८२।

मेरे शव पर वह रोये, हो जिसके आंसू में हाला
आह भरे वो, जो हो सुरिभत मदिरा पी कर मतवाला,
दे मुझको वो कान्धा जिनके पद मद डगमग होते हों
और जलूं उस ठौर जहां पर कभी रही हो मधुशाला।।८३।

और चिता पर जाये उंडेला पात्र न घृत का, पर प्याला
कंठ बंधे अंगूर लता में मध्य न जल हो, पर हाला,
प्राण प्रिये यदि श्राध करो तुम मेरा तो ऐसे करना
पीने वालों को बुलवा कऱ खुलवा देना मधुशाला।।८४।

– बच्चन

The above poem in Amitabh Bachchan’s voice. कहना सच्ची है मधुशाला.

Featured

My First interview

It sounds very simple but when the first ever (technical) interview of your life is being taken by a Microsoft employee, things really get tensed. I considered myself a calm headed guy, certain friends might contradict, but I felt I could handle any sort of pressure until that interview. I went in the room very confident as I believed I was good at programming. The first question I got was about finding an element in a rotated sorted array. I don’t know why as soon as I saw my interviewer explain me the question, I started getting an intense feeling that “It’s all ruined”. I don’t know where it came from but it was strong and persistent throughout the time when I was trying to obtain a solution. My mind could think of a million reasons why I believed that I would ruin my interview but could not think of a very trivial solution to that problem. Anyhow, I managed an approach and told him half-heartedly. He simply asked to code and not explain the algorithm. I began coding, I had read somewhere that these guys see the way you write your code also, so I quickly wrote the code without any hesitation and showed it to him. He had not even completely read the code and wrote a test case for which it failed. Alas !!! I knew my approach was correct but I had messed up while coding. I was told just before entering the room that, “.. M$ guys love you if you write the code correct in the first attempt..” … imagine the state of my mind as soon as I found that the first code I wrote was wrong. I turned back and in remorse and repenting on my stupendous mistake I reviewed my code and after the first flaw I saw I knew that it was the culprit which caused my drown. I corrected it and then gave it back to the interviewer as if now the interview was just a formality for me. I think of myself at that point and really I could compare myself with a soldier fighting alone against the US army with a 3-NOT-3 rifle. And what follows, he went through my code again and wrote another test case where it broke. I don’t have enough knowledge of english language to express what went through my head when I dry ran that case on my code. But this time I don’t know what came to my mind and I thought to myself, “..abe ab kas to gayi hai hi.. hona to hai nhi.. to saale iske mu par code maaro.. abki galti nikal k dikha saale code main…” .. and that was me. I took the code, went over it, in one go I corrected all the mistakes I could se and in next view I tested it on 2-3 test cases which I had generated in my mind at the speed of light. Then I handed over the paper to him and rolled back on my chair. This time I had done it, he found no mistake in it and just said .. “ye chal jaega”. Now I was charged up because of the thought that had went past my mind and now I was like a free bird ready for anything. He posted another problem about the knight’s tour and before he could complete the problem I had written a recursive code for it and again tested it on my “lighting-speed” generated test cases, he asked to optimize it and I gave him the method which could be used to optimize it. Speechless, as he was, seeing the vibrant change in my attitude. Guys, really, when you have nothing to loose, whatever you do, you only gain. And though I was so distressed that after he relieved me, I came out with 1/10^100th the enthusiasm with which I had entered that room. I was sure that I had lost my chance and was waiting for the HR official to show me the way out. How fast my brain analyzed my interview and drew a zillion reasons of how I had screwed my interview was a thought I can never forget. And still I was there, waiting for the official denial, but a kindle of hope somewhere in the heart with a feeling that “..kya pata apni shakal achhi lagi ho sale ko.. aise nhi to waise hi pass kar de sala ..”, I stood there. And there she came out and called my name ….. and uttered the words “Avi, you have been scheduled for the next round of interview”.

Stay tuned to know what happened in that interview.

Given two strings a and b, find whether any anagram of string a is a sub-string of string b

I know this is a fairly (old and) simple question. But what people do not realize is that it has a catch! I saw this question here and browsed through most of the solutions. Almost all of them (except the crazy ones where folks wanted to do brutal force search) would fail on a very simple case. And this question, is all about just that case

#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main() {
  string src, tgt;
  std::getline(cin, src);
  std::getline(cin, tgt);
  vector<int> buf(256, 0);
  const int tot = src.size();
  for (int i = 0; i < src.size(); ++i) {
    buf[src[i]]++;
  }
  vector<int> tmp(256, 0);
  int start = -1, tmp_tot = 0, end = 0;
  for (int i = 0; i < tgt.size(); ++i) {
    const unsigned char ch = tgt.at(i);
    if (buf[ch] > 0) {
      if (tmp[ch] == buf[ch]) {
        if (tmp_tot > 256) {
          tmp.clear();
          tmp.resize(256, 0);
        } else {
          while (tmp_tot > 0) tmp[tgt[i - tmp_tot--]]--;
        }
        start = i;
        tmp[ch]++;
        tmp_tot = 1;
      } else {
        if (start == -1) start = i;
        tmp[ch]++;
        ++tmp_tot;
        if (tmp_tot == tot) end = i;
      }
    }
  }
  if (end > 0) {
    cout << start << "    " << end << std::endl;
  } else {
    cout << "Not found\n";
  }
  return 0;
}

Find the longest sequence of prefix shared by all the words in a string

Source (I guess) This version has the minimum comparisons required for the solution.

#include&lt;algorithm&gt;
#include&lt;iostream&gt;
#include&lt;string&gt;
#include&lt;vector&gt;
using namespace std;
int main() {
  int n;
  cin &gt;&gt; n;
  vector&lt;string&gt; strs;
  while (n--) {
    string tmp;
    cin &gt;&gt; tmp;
    strs.push_back(tmp);
  }
  int len = 0;
  while (len < strs[0].size()) {
    char cur = strs[0].at(len);
    if (std::all_of(strs.begin() + 1,
                    strs.end(),
                    [len,cur](const string&amp; t) {
                        return len &lt; t.size() &amp;&amp; t.at(len) == cur; })) {
      ++len;
    } else {
      break;
    }
  }
  cout &lt;&lt; len &lt;&lt; std::endl;
  return 0;
}

Cocktail Sort!

Cocktail Sort is something I came to know of recently. Its much better alternative to Bubble Sort and performs much better.

Most folks should be aware that, sorting algorithms have a fancy property. For relatively small input (<20 maybe) elements the naive algorithms, like Bubble, Insertion and now Cocktail can outperform QuickSort and MergeSort etc. And if you don’t know why so, try to figure out 🙂 So how much can we save by using them in QuickSort ?

So I wrote a small program which takes a bunch of randomly generated numbers and records the run time of sorting them with different algorithms viz. std::sort of C++, qsort of C and my own written Cocktail Sort (I did test my code extensively and it seems to work 😀 ). It does seem that Cocktail outperforms Quick and std::sort for <25 elements. Repeatedly running the experiment does confirm this. But I guess the complexity of incorporating this in qsort or std::sort is more painful than the gain 🙂

Plus this is the first C++11 program of my blog! From now on, I will try to use as much as C++11 as I can but not excessive 😀

// You need C++11 for this to compile!
// You should be having it, so compile this with 'g++ -std=c++11 filename.cc -O3'
// ./a.out N1 N2
// where N1 < N2 and the test will run for array sizes of N1, N1 + 1, ... N2
// and produce result for all the iterations.

#include <algorithm>
#include <chrono>
#include <iostream>
#include <random>
#include <vector>

#include <cassert>
#include <cstdlib>
#include <climits>

void CocktailSort(std::vector<int>& num, int start, int end) {
  const int i_end = end - 1;
  bool swapped = false;
  do {
    for (int i = start; i <= i_end; ++i) {
      if (num[i] > num[i + 1]) {
        std::swap(num[i], num[i + 1]);
        swapped = true;
      }
    }
    if (!swapped) break;
    swapped = false;
    for (int i = end - 1; i >= start; --i) {
      if (num[i] > num[i + 1]) {
        std::swap(num[i], num[i + 1]);
        swapped = true;
      }
    }
  } while (swapped);
}

// This sort works by following a simple invariant. Every time the inner
// for loop completes, we place the min and max elements of the iterated
// subarray at the two ends. We need to do this exactly n / 2 times,
// since with each iteration we place 2 elements correctly.
// I saw the animation on wiki page of Cocktail sort and without reading
// the pseudo code thought of this algorithm and 'assumed' this should be
// Cocktail sort. Well, it is not. But for the ~10k runs of comparison, this
// out performs Cocktail sort, so will use this in QSort.
// Above Cocktail is for demo!
void MyBadSort(std::vector<int>& num, const int start, const int end) {
  const int nelem = end - start + 1;
  if (nelem == 1) return;
  if (nelem == 2) {
    if (num[start] > num[end]) std::swap(num[start], num[end]);
    return;
  }
  int found = start;
  const int n_iter = nelem / 2;
  for (int ix = 0; ix < n_iter; ++ix) {
    const int loc = end - ix;
    int min = num[found];
    int max = num[loc];
    if (min > max) {
      std::swap(min, max);
      std::swap(num[found], num[loc]);
    }
    const int upto = end - ix;
    for (int i = found + 1; i < upto; ++i) {
      if (num[i] < min) {
        min = num[i];
        std::swap(num[found], num[i]);
      }
      if (num[i] > max) {
        max = num[i];
        std::swap(num[loc], num[i]);
      }
    }
    ++found;
  }
}

void MyQSortNaive(std::vector<int>& num, const int start, const int end) {
  const int nelem = end - start + 1;
  if (nelem == 1) return;
  if (nelem == 2) {
    if (num[start] > num[end]) std::swap(num[start], num[end]);
    return;
  }
  const int pivot = num[start];
  int pos = start;
  for (int i = start; i <= end; ++i) {
    if (num[i] < pivot) {
      std::swap(num[pos], num[i]);
      ++pos;
    }
  }
  if (pos > start) MyQSortNaive(num, start, pos - 1);
  for (int i = pos; i <= end; ++i) {
    if (num[i] == pivot) {
      std::swap(num[pos], num[i]);
      ++pos;
    }
  }
  if (pos < end) MyQSortNaive(num, pos, end);
}

void MyQSort(std::vector<int>& num, const int start, const int end) {
  const int nelem = end - start + 1;
  if (nelem == 1) return;
  if (nelem == 2) {
    if (num[start] > num[end]) std::swap(num[start], num[end]);
    return;
  }
  if (nelem == 3) {
    if (num[start] > num[start + 1]) std::swap(num[start], num[start + 1]);
    if (num[start + 1] > num[end]) std::swap(num[start + 1], num[end]);
    if (num[start] > num[start + 1]) std::swap(num[start], num[start + 1]);
    return;
  }
  if (nelem <= 10) {
    MyBadSort(num, start, end);
    return;
  }
  const int pivot = num[start];
  int pos = start;
  for (int i = start; i <= end; ++i) {
    if (num[i] < pivot) {
      std::swap(num[pos], num[i]);
      ++pos;
    }
  }
  if (pos > start) MyQSort(num, start, pos - 1);
  for (int i = pos; i <= end; ++i) {
    if (num[i] == pivot) {
      std::swap(num[pos], num[i]);
      ++pos;
    }
  }
  if (pos < end) MyQSort(num, pos, end);
}

int main(int argc, char** argv) {
  assert(argc == 3);
  const int MOD_VALUE = 1000;  // INT_MAX
  unsigned long long int std_qsort = 0, my_qsort_naive = 0, my_qsort = 0;
  for (int run = std::stoi(argv[1]); run <= std::stoi(argv[2]); ++run) {
    unsigned seed1 = std::chrono::system_clock::now()
        .time_since_epoch().count();
    std::mt19937 rnd(seed1 + run * 1000);
    int N = run;
    std::cout << "\n\nRunning comparison with " << run
              << " elements to sort\n";
    std::vector<int> num;
    num.reserve(N);

    // C++ std::sort
    num.clear();
    for (int i = 0; i < N; ++i) num.push_back(rnd() % MOD_VALUE);
    std::shuffle(num.begin(), num.end(), rnd);
    auto start = std::chrono::high_resolution_clock::now();
    std::sort(num.begin(), num.end());
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast
      <std::chrono::microseconds>(end - start);
    assert(std::is_sorted(num.begin(), num.end()));
    std_qsort += elapsed.count();
    // std::cout << "Time spent in std::sort: " << elapsed.count() << "\n";

    // My QSort implementation without the Cocktail support
    num.clear();
    for (int i = 0; i < N; ++i) num.push_back(rnd() % MOD_VALUE);
    std::shuffle(num.begin(), num.end(), rnd);
    start = std::chrono::high_resolution_clock::now();
    // qsort(&num[0], num.size(), sizeof(num[0]), cmp);
    MyQSortNaive(num, 0, num.size() - 1);
    end = std::chrono::high_resolution_clock::now();
    elapsed = std::chrono::duration_cast
      <std::chrono::microseconds>(end - start);
    assert(std::is_sorted(num.begin(), num.end()));
    // std::cout << "Time spent in Naive Qsort: " << elapsed.count() << "\n";
    my_qsort_naive += elapsed.count();

    // My QSort with Cocktail support
    num.clear();
    for (int i = 0; i < N; ++i) num.push_back(rnd() % MOD_VALUE);
    std::shuffle(num.begin(), num.end(), rnd);
    start = std::chrono::high_resolution_clock::now();
    MyQSort(num, 0, num.size() - 1);
    end = std::chrono::high_resolution_clock::now();
    elapsed = std::chrono::duration_cast
      <std::chrono::microseconds>(end - start);
    assert(std::is_sorted(num.begin(), num.end()));
    // std::cout << "Time spent in MyQsort with sorter: " << elapsed.count() << "\n";
    my_qsort += elapsed.count();
  }
  std::cout << "\n\n";
  std::cout << "Total time taken for std::sort: " << std_qsort << "\n";
  std::cout << "Total time taken for naive myqsort: " << my_qsort_naive << "\n";
  std::cout << "Total time taken for myqsort: " << my_qsort << "\n";
  return 0;
}

You should try to run this for small N eg. ./a.out 10 12 or ./a.out 12 15 etc.

Knuth Morrison Pratt (KMP) String Matching Algorithm

I have always wanted to understand the KMP Algorithm and write a program for it and finally I got around doing it. I had this big misconception that its a very tedious algorithm and does some black magic but, as with all other Knuth’s algorithms, this is a beauty 🙂

Following is a working 😀 program, which does not handle corner cases, empty strings and UTF-8 etc. But works for sane inputs.

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
using namespace std;

vector<int> BuildLookupTable(const string& needle) {
  vector<int> ret_val;
  ret_val.resize(needle.length());
  size_t pos = 2, prefix_pos = 0;
  ret_val[0] = -1;
  ret_val[1] = 0;
  while (pos < needle.length()) {
    if (needle.at(pos - 1) == needle.at(prefix_pos)) {
      ret_val[pos++] = ++prefix_pos;
    } else if (prefix_pos > 0) {
      prefix_pos = ret_val[prefix_pos];
    } else {
      ret_val[pos++] = 0;
    }
  }
  return ret_val;
}

string FindNeedleInHaystackUsingKMP(const string& needle,
                                    const string& haystack) {
  vector<int> lookup_table = BuildLookupTable(needle);
  size_t haystack_index = 0;
  size_t needle_index = 0;
  while (haystack_index + needle_index < haystack.length()) {
    if (haystack.at(haystack_index + needle_index)
        == needle.at(needle_index)) {
      ++needle_index;
      if (needle_index == needle.length()) return "Found.";
    } else {
      haystack_index = haystack_index + needle_index
          - lookup_table[needle_index];
      if (lookup_table[needle_index] == -1) {
        needle_index = 0;
      } else {
        needle_index = lookup_table[needle_index];
      }
    }
  }
  return "Not Found.";
}

int main() {
  string needle, haystack;
  cout << "Enter the needle: ";
  getline(std::cin, needle);
  cout << "Enter the haystack: ";
  getline(std::cin, haystack);
  cout << FindNeedleInHaystackUsingKMP(needle, haystack) << "\n";
  char* ret_val = strstr(haystack.c_str(), needle.c_str());
  if (ret_val == NULL) {
    cout << "(Verifier) : Not Found\n";
  } else {
    cout << "(Verifier) : Found\n";
  }
}

Largest sum subarray

Recursion: M[i] = max sum subarray ending here

M[i] = max(M[i-1] + a[i], a[i])

Loved this code 🙂

#include<algorithm>
#include<iostream>

using namespace std;

int main() {
  int n;
  cin >> n;
  int max_sum = 0, run_sum = 0;
  for (int i = 0, t = -1; i < n; ++i) {
    cin >> t;
    run_sum = max(run_sum + t, t);
    max_sum = max(run_sum, max_sum);
  }
  cout << max_sum << endl;
  return 0;
}

A night out after long :)

So found the following question here (Antonio is awesum 🙂 ) and worked out a O(n) time solution BUT with O(n) space. I claim the space usage can be brought down to O(1). Anyone game enough to post the O(1) space version?

Problem:

Given an array A of numbers, find a pair of numbers A[i] and A[j], such that A[i] < A[j] and j-i is maximized.

O(n) time O(n) space code

#include <iostream>
#include <string>
#include <utility>
#include <vector>

using namespace std;

int main() {
  vector<int> numbers;
  int n;
  cin >> n;
  numbers.resize(n);
  for (int i = 0, t; i < n; ++i) {
    cin >> t;
    numbers[i] = t;
  }
  vector<pair<int, int> > decr;
  decr.push_back(make_pair(numbers[0], 0));
  for (int i = 1; i < numbers.size(); ++i) {
    if (numbers[i] < decr.back().first) {
      decr.push_back(make_pair(numbers[i], i));
    }
  }
  vector<pair<int, int> > incr;
  incr.push_back(make_pair(numbers[n-1], n-1));
  for (int i = n - 2; i >= 0; --i) {
    if (numbers[i] > incr.back().first) {
      incr.push_back(make_pair(numbers[i], i));
    }
  }
  reverse(incr.begin(), incr.end());
  int iter = min(incr.size(), decr.size());
  int max_diff = -1, s_i = -1, s_j = -1;
  int i_i = 0, d_i = 0;
  for (; i_i < incr.size() && d_i < decr.size();) {
    if (incr[i_i].first > decr[d_i].first) {
      int tmp_diff = incr[i_i].second - decr[d_i].second;
      if (tmp_diff > max_diff) {
        max_diff = tmp_diff;
        s_i = decr[d_i].second;
        s_j = incr[i_i].second;
      }
      i_i++;
    } else if (incr[i_i].first < decr[d_i].first) {
      d_i++;
    } else {
      i_i++;
      d_i++;
    }
  }
  cout << "i: " << s_i << "  j: " << s_j << endl;
  return 0;
}

जाग तुझको दूर जाना!

An awesome composition by a Hindi poet, महादेवी वर्मा

चिर सजग आँखें उनींदी आज कैसा व्यस्त बाना!
जाग तुझको दूर जाना!

अचल हिमगिरि के हॄदय में आज चाहे कम्प हो ले!
या प्रलय के आँसुओं में मौन अलसित व्योम रो ले;
आज पी आलोक को ड़ोले तिमिर की घोर छाया
जाग या विद्युत शिखाओं में निठुर तूफान बोले!
पर तुझे है नाश पथ पर चिन्ह अपने छोड़ आना!
जाग तुझको दूर जाना!

बाँध लेंगे क्या तुझे यह मोम के बंधन सजीले?
पंथ की बाधा बनेंगे तितलियों के पर रंगीले?
विश्व का क्रंदन भुला देगी मधुप की मधुर गुनगुन,
क्या डुबो देंगे तुझे यह फूल दे दल ओस गीले?
तू न अपनी छाँह को अपने लिये कारा बनाना!
जाग तुझको दूर जाना!

वज्र का उर एक छोटे अश्रु कण में धो गलाया,
दे किसे जीवन-सुधा दो घँट मदिरा माँग लाया!
सो गई आँधी मलय की बात का उपधान ले क्या?
विश्व का अभिशाप क्या अब नींद बनकर पास आया?
अमरता सुत चाहता क्यों मृत्यु को उर में बसाना?
जाग तुझको दूर जाना!

कह न ठंढी साँस में अब भूल वह जलती कहानी,
आग हो उर में तभी दृग में सजेगा आज पानी;
हार भी तेरी बनेगी माननी जय की पताका,
राख क्षणिक पतंग की है अमर दीपक की निशानी!
है तुझे अंगार-शय्या पर मृदुल कलियां बिछाना!
जाग तुझको दूर जाना!

More compositions of महादेवी वर्मा can be found here