C Program : Rank of a word

Rank of a word is the position of the word when all the permutations of the letters in the word are listed in dictionary order. So for example "cat" is the word, then, various permutations in dictionary order are-

1. act
2. atc
3. cat
4. cta
5. tac
6. tca

Hence the rank of "cat" is 3.
Here is the logic in short-

Sort the word, find number of permutations that can be formed with letters which come before i^th letter in original word.

So for i = 0, i^th letter is 'c' and the sorted word is "act", so we need to find all permutations starting with 'a' and so on.

Below is the program that takes care of duplicates as well.

#include <stdio.h>
#include <string.h>

long fact(int n)
{
 long f = 1;
 while (n > 0)
 {
  f *= n;
  n--;
 }
 return f;
}

int find_rank(char s[], int len)
{
 long rank = 1;
 int i, j, k, l, fr[26], f; //fr is frequency
 char sorted[100], cur, t, pre;

 for (i = 0; i < len -1 ; ++i)
 {
  cur = s[i];
  strcpy(sorted, s + i);
  l = len - i;
  memset(fr, 0, sizeof(fr));
  fr[sorted[0] - 'a']++;
  for (j = 1; j < l; ++j)
  {
   t = sorted[j];
   fr[t-'a']++;
   for (k = j-1; k >=0 && sorted[k] > t; --k)
    sorted[k+1] = sorted[k];
   sorted[k+1] = t;
  }
  pre = 1;
  for (k = 0; sorted[k] != cur ;++k)
  {
   if (sorted[k] == pre)
    continue;
   pre = sorted[k];

   f = fact(l - 1);
   fr[pre - 'a']--;
   for (j = 0; j < 26; ++j)
    if (fr[j])
     f /= fact(fr[j]);
   rank += f;
   fr[pre - 'a']++;
  }
 }
 return rank;
}

int main()
{
 char s[100];
 
 scanf("%s", s);
 printf("%d", find_rank(s, strlen(s)));
 return 0;
}

C++ Program - Finding the kth element in a dynamic sorted list

A common programming problem goes something like -

To find the k^th minimum(/maximum) element in a dynamic list, which is kept sorted.

The catch here is that, the list is dynamic, i.e. the list is increasing in size (due to insertion of element), and at any instant, you may be asked to report the k^th minimum element.

There are in general 3 approaches (considering we have 'n' elements at any instant)-

1. To have O(1) insertion, i.e insert at the end of the list. And O(n log n) search, i.e when asked to give k^th element, sort the list and output the element at k^th offset. As is evident, if the queries are frequent this approach is not going to be efficient.
2. To have O(n) insertion, i.e insert the new element at its correct position in sorted list by shifting all elements from  k^th to  n^th offset by 1. And to have O(1) output. Again this is not very efficient as it is O(n²) overall.
3. To have O(log n) insertion and O(1) output time. Now this seems rather efficient! This is overall O(n log n). This is the method I am discussing below.

The difference in second and third approach is that we use a array in former and 2 heaps in later.

Using 2 heaps-

If we need the  k^th minimum element, we will need 2 heaps. One is a MIN heap other is a MAX heap. And at any time we need to ensure that MAX heap has exactly 'k' elements and MIN heap has the rest (N-K). Then the  k^th element is at the top of MAX heap at any time. Let me illustrate with an example, followed by a C++ program.

Consider a stream of insertion and queries (?), for k = 4 - 

9 5 4 7 ? 6 2 ? 1 ? 2 ?

Stream	MIN heap	MAX heap	Output
9		9
5		9 5
4		9 5 4
7		9 7 5 4
?		9 7 5 4	9
6	9	7 6 5 4
2	7 9	6 5 4 2
?	7 9	6 5 4 2	6
1	6 7 9	5 4 2 1
?	6 7 9	5 4 2 1	5
2	5 6 7 9	4 2 2 1
?	5 6 7 9	4 2 2 1	4

Now there are several points to be noted -

• For first k insertions, we are not able to maintain the size of MAX heap as k. But we insert all of the first k elements in MAX heap.
• After k elements are inserted, and we have new element "x", then we compare x with MAX heap's top "t". If x > t, we insert x in MIN heap, else we delete t from MAX heap, and put it in MIN heap, and then insert x in MAX heap.
• Do we really need MIN heap? This is a question that should come in your mind. Answer is No! Just throw the numbers being inserted in MIN heap. This method is so general that it can be easily adapted for problems in which k is not a number but a fraction. Like to output the 1/3th element. In that case just maintain size of MAX heap to 1/3 of total. In this you may have to transfer elements from MIN heap to MAX heap as well.
• C++ does not have Heap data structure, at least not with the name "heap". Either you can create your own, or use Priority Queue in STL. 

So here is the program-

#include <iostream>
#include <queue>

using namespace std;

class Rlong //Reverse Long
{
 long m_l;
public:
 Rlong(long l) : m_l(l)
 { }
 operator long const &() const
 { return m_l; }
 bool operator<(Rlong const &right) const
 { return m_l > right.m_l; }
};

int main()
{
 long n, k, x, y, i;

 priority_queue<Rlong> minpq;
 priority_queue<long>  maxpq;

 cin >> n >> k;

 for (i = 0; i < k; ++i)
 {
  cin >> x;
  maxpq.push(x);
 }
 for (; i < n; ++i)
 {
  cin >> x ;
  if (x != -1) // assuming -1 as '?'
  {
   if (x < maxpq.top())
   {
    y = maxpq.top();
    maxpq.pop();
    maxpq.push(x);
    minpq.push(y);
   }
   else
   {
    minpq.push(x);
   }
  }
  else
  {
   x = maxpq.top();
   cout << x;
  }
 }
 return 0;
}

Eliminate duplicates and sort the list

Recently I received a List of zipcodes from a carrier. The zipcodes were duplicated and were not sorted. So I just wrote a small C++ code to sort and eliminate the duplicates from the list of zipcodes.

The program simply uses the set container in C++ STL, for the task. The set has the property that, it doesn't store duplicates. So, all we need to do is, insert all the elements (from the input file), into the set. And since set is also ordered in nature (implemented as a Red Black Tree), we can iterate over it to yield a sorted list. Below is the code-

#include <fstream>
#include <sstream>
#include <string>
#include <set>

using namespace std;

inline int convert(string &s)
{
 int out;
 istringstream ss(s);
 ss >> out;
 return out;
}

int main()
{
 ifstream infile("input.txt");
 ofstream outfile("output.txt");

 string line;
 int zipcode;  //zipcode is just a integer

 set<int> zipcodes;

 while (getline(infile, line))
 {
  zipcode = convert(line);
  zipcodes.insert(zipcode);
 }

 for (auto i = zipcodes.begin(); i != zipcodes.end(); i++)
  outfile << *i << '\n';

 infile.close();
 outfile.close();

 return 0;
}

To some, one keyword might have confused, that is "auto", in the for loop as -

auto i = zipcodes.begin() ;

Well, it was introduced in C++11 standard, to let the programmer omit typing the type of variable. The compiler well deduce the type by looking at the type of RHS. And I believe it is rather nice introduction, seeing how it can save you from rather ugly expressions. If you are using gcc with version prior to 4.7, you need to add a flag -std=c++0x while compiling in terminal or enable this flag in your IDE (if it is not already).

The stack that could give minimum in O(1)

This is one of my favorite interview question-

You have to create a stack which gives the smallest element in constant (or O(1)) time. 

You can be asked for the largest element instead of smallest also.

Take some time to think. Or read the grayed hint below, followed by the solution and explanation-

You can use linear amount of (extra) memory.

Ok now the solution. You take a separate stack, call it min-stack. The other stack is the main-stack. 

When you push a element in main-stack, compare the new element with top (using peek, not pop) of min-stack. Following cases are possible-

1. The min-stack is empty => simply push the new element in min-stack as well.
2. The min-stack top is smaller => do nothing.
3. The min-stack top is larger => push the new element in min-stack as well.
4. The min-stack top is equal => push the new element in min-stack as well. 

When you pop the element from the main-stack, again compare the popped element with the min-stack top. There are only 2 cases now-

1. The min-stack top is equal => pop from min-stack as well.
2. The min-stack top is not equal => do nothing

When the time comes for get minimum, just return the top of min-stack (taking care of underflow).

For completeness, here is the C++ code

void stack::push(int a)
{ 
    main_stack.push(a);   

    if (min_stack.is_empty())
        min_stack.push(a); 
    else if (a <= min_stack.top()) 
        min_stack.push(a);
}

int stack::pop()
{
    //take care of underflow here

    int e = main_stack.top();     
    if (min_stack.top() == e)
        min_stack.pop();

    return e;
}

int stack::minimum()
{
    //take care of underflow here

    return min_stack.top();
}