Sayings of Chanakya

Wanted to log these hence posting here. A brilliant collection.

1) “Learn from the mistakes of others… you can’t live long enough to make them all yourselves!!”

2)”A person should not be too honest. Straight trees are cut first and Honest people are screwed first.”

3)”Even if a snake is not poisonous, it should pretend to be venomous.”

4)”There is some self-interest behind every friendship. There is no friendship without self-interests. This is a bitter truth.”

5)” Before you start some work, always ask yourself three questions – Why am I doing it, What the results might be and Will I be successful. Only when you think deeply and find satisfactory answers to these questions, go ahead.”

6)”As soon as the fear approaches near, attack and destroy it.”

7)”The world’s biggest power is the youth and beauty of a woman.”

8)”Once you start a working on something, don’t be afraid of failure and don’t abandon it. People who work sincerely are the happiest.”

9)”The fragrance of flowers spreads only in the direction of the wind. But the goodness of a person spreads in all direction.”

10)”God is not present in idols. Your feelings are your god. The soul is your temple.”

11) “A man is great by deeds, not by birth.”

12) “Never make friends with people who are above or below you in status. Such friendships will never give you any happiness.”

13) “Treat your kid like a darling for the first five years. For the next five years, scold them. By the time they turn sixteen, treat them like a friend. Your grown up children are your best friends.”

14) “Books are as useful to a stupid person as a mirror is useful to a blind person.”

15) “Education is the best friend. An educated person is respected everywhere. Education beats the beauty and the youth.”

Advertisements

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

Finally I did it !!

A friend of mine referred me to a problem from my own blog (i.e. here :D) and I must say I enjoyed every aspect of the problem. From designing its awesum O(nlogn) solution to coding it with handling all the minor details. It’s about to be 6 A.M. now and I can’t sleep without posting the code 😀

Problem Statement: You are given 2 arrays A, B sorted in decreasing order of size m and n respectively and a number k, such that 1 <= k <= m * n. You need to fine the kth largest sum(a+b) possible where a in A, and b in B.

The only caveat is that I did it for kth smallest, I find ascending order to be more natural 🙂

#include<iostream>
#include<vector>

using namespace std;

#define MID(min, max) ((min) + (((max) - (min)) / 2))

int GetSmallerPairsCount(const vector<int>& A,
                         const vector<int>& B,
                         const int sum) {
  int num_smaller_pairs = 0;
  int temp = 0;
  // O(n) loop
  for (int A_index = A.size() - 1, B_index = 0; A_index >= 0; --A_index) {
    for (; B_index < B.size(); ++B_index) {
      if (A[A_index] + B[B_index] <= sum) {
        ++temp;
      } else {
        break;
      }
    }
    num_smaller_pairs += temp;
  }
  return num_smaller_pairs;
}

bool CheckIfSumExists(const vector<int>& A, const vector<int>& B, int sum) {
  // O(n) loop
  for (int a = A.size() - 1, b = 0; a >= 0 && b < B.size();) {
    if (A[a] + B[b] == sum) return true;
    if (A[a] + B[b] < sum) {
      ++b;
    } else {
      --a;
    }
  }
  return false;
}

int FindNextLargestSum(const vector<int>& A,
                       const vector<int>& B,
                       const int sum) {
  int new_sum, n_l = A.back() + B.back();
  // O(n) loop
  for (int A_index = A.size() - 1, B_index = 0;
      A_index >= 0 && B_index < B.size();) {
    new_sum = A[A_index] + B[B_index];
    if ((n_l > new_sum) && (new_sum > sum)) {
      n_l = new_sum;
    }
    if (new_sum <= sum) {
      ++B_index;
    } else {
      --A_index;
    }
  }
  return n_l;
}

int FindPreviousSmallestSum(const vector<int>& A,
                            const vector<int>& B,
                            const int sum) {
  int new_sum, p_s = A.front() + B.front();
  // O(n) loop
  for (int A_index = A.size() - 1, B_index = 0;
      A_index >= 0 && B_index < B.size();) {
    new_sum = A[A_index] + B[B_index];
    if ((p_s < new_sum) && (new_sum < sum)) {
      p_s = new_sum;
    }
    if (new_sum < sum) {
      ++B_index;
    } else {
      --A_index;
    }
  }
  return p_s;
}

// O(n*log(n)) order with O(1) extra space
int KthSmallestPairSum(const vector<int>& A,
                       const vector<int>& B,
                       const int k) {
  int max = A.back() + B.back();
  int min = A.front() + B.front();
  // O(log(n)) loop
  while (1) {
    int curr_mid = CheckIfSumExists(A, B, MID(min, max)) ? MID(min, max) : FindNextLargestSum(A, B, MID(min, max));
    int prev_mid = FindPreviousSmallestSum(A, B, curr_mid);
    int next_mid = FindNextLargestSum(A, B, curr_mid);

    int curr_mid_smaller = GetSmallerPairsCount(A, B, curr_mid);
    int prev_mid_smaller = GetSmallerPairsCount(A, B, prev_mid);
    int next_mid_smaller = GetSmallerPairsCount(A, B, next_mid);

    if (k == prev_mid_smaller) return prev_mid;
    if (prev_mid_smaller < k && next_mid_smaller >= k) {
      if (curr_mid_smaller < k) return next_mid;
      return curr_mid;
    }

    if (prev_mid_smaller > k) {
      max = FindPreviousSmallestSum(A, B, prev_mid);
    } else if (next_mid_smaller < k) {
      min = FindNextLargestSum(A, B, next_mid);
    } else {
      cout << "BUG\n";
      exit(0);
    }
  }
  return -2;
}

int main() {
  int size;
  cout << "Length of first array: " ;
  cin >> size;
  cout << "Enter the elements of first array\n";
  vector<int> A;
  for (int t = -1; size > 0; --size) {
    cin >> t;
    A.push_back(t);
  }
  cout << "Size of second array: ";
  cin >> size;
  vector<int> B;
  for (int t = -1; size > 0; --size) {
    cin >> t;
    B.push_back(t);
  }
  sort(A.begin(), A.end());
  sort(B.begin(), B.end());

  // Build the brute-force solution beforehand to compare
  // the results of our optimized method
  vector<int> brute;
  for (int i = 0; i < A.size(); ++i) {
    for (int j = 0; j < B.size(); ++j) {
      brute.push_back(A[i] + B[j]);
    }
  }
  sort(brute.begin(), brute.end());

  for (int kk = 1; kk <= A.size() * B.size(); ++kk) {
    int k = kk;
    if (k < 1 || k > A.size() * B.size()) {
      cout << "Invalid k. 1 <= k <= " << A.size() * B.size();
    } else {
      int result = KthSmallestPairSum(A, B, k);
      if (result != brute[k-1]) {
        cout << "Method broke. Wake up Avi !!";
        exit(0);
      }
      cout << k << "th smallest pair sum: " << result;
    }
    cout << endl;
  }
  cout << "All Iz Bhel !! " << endl;
  return 0;
}

Zero sum sub-array

Question: There is an array consisting of postive and negative integers. find the subarray whose sum is 0.

Solution:

#include<ext/hash_map>
#include<iostream>
#include<vector>

using namespace __gnu_cxx;
using namespace std;

int main() {
  int n;
  cin >> n;
  int prefix_sum = 0;
  hash_map<int, int> find_subarray;
  int start_index = -1, end_index = -1;
  for (int i = 0, t = -1; i < n; ++i) {
    cin >> t;
    if (!t) {
      start_index = i;
      end_index = i;
      break;
    }
    prefix_sum += t;
    if (!prefix_sum) {
      start_index = 0;
      end_index = i;
      break;
    }
    if (find_subarray.find(prefix_sum) == find_subarray.end()) {
      find_subarray[prefix_sum] = i;
    } else {
      start_index = find_subarray[prefix_sum] + 1;
      end_index = i;
      break;
    }
  }
  if (start_index != -1) {
    cout << "Zero sum subarray found. Start index : " << start_index
         << ". End Index: " << end_index << "\n";
  }
  return 0;
}

Truth beind Engineering

When you’re working with TBs and PBs of data you get some serious realizations. Beautifully put forth in the penultimate slide of this presentation.

All engineering solutions are transient.

Nothing’s perfect but some solutions are good enough for a while.

Scalability solutions aren’t magic. They involve partitioning, indexing and replication.

All data for real-time queries MUST be in memory.

Disk is for writes only.

Some problems can be solved by pre-computation, but a lot can’t.

Exploit locality where possible.

Source

Interview Problems 25

1. Given a set of KEY->VALUE pairs such that each KEY is unique, describe a method of storing these pairs on disk, and a method for accessing the corresponding VALUE given a KEY. Assume that RAM is fixed at 1gb and the set of pairs requires 40gb.

2. Consider there is an array with duplicates and you are given two numbers as input and you have to return the minimum distance between the two in the array with minimum complexity.

3. You are given an array of integers, say array1 of size n. You have to create another array (say array2) and fill its contents by following this rule: array2[i] will hold the value of the left-most integer from the range array1[i+1] to array1[n-1] such that it is greater than array1[i]. If no such element exists, assign -1.

4. An external system has an array. You are given 3 inbuilt functions which perform their operation in O(1) time.
a) get(i): returns ith element of array
b) length(): returns length of array
c) reverse(i, j): reverses elements of subarray starting from i and ending with j (both inclusive)

Write function SortArray() using these three functions.

5. Given a binary tree, find 2 leaf nodes say X and Y such that F(X,Y) is maximum where F(X,Y) = sum of nodes in the path from root to X + sum of nodes in the path from root to Y – sum of nodes in the common path from root to first common ancestor of the Nodes X and Y.

6. Given an array, A, find if all elements in the sorted version of A are consecutive in less than O(nlogn).
eg: A: 5 4 1 2 3 on sorting 1 2 3 4 5 all elements are consecutive — true
A: 1 9 2 22 on sorting 1 2 9 22 all elements are NOT consecutive — false

7. Given a string (assume there no spaces or punctuations), write a code that returns the max. length of the string that has repeated more than once.

%d bloggers like this: