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;
}

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.

%d bloggers like this: