Simplicity

How would you define an unsigned int of 32 bits (you can imagine about 64 bits) to be infinite?

some might

const unsigned int kMaxUnsignedInt = 0xFFFFFFFF;

Others (shifting lovers) may

const unsigned int kMaxUnsignedInt =  (((1<<30) - 1) << 2 ) | 3;

Few may

const unsigned int kMaxUnsignedInt = ~0;

I did

const unsigned int kMaxUnsignedInt = -1;

What would you do?

On a side note
What would the following code do?

const unsigned int kMaxUnsigndInt = (1<<31) - 1;

The Just Shall Live By Faith :D

I had posted something about fast encoding and decoding of integer array previously here. So here is something (maybe) more frequently used. A fast way to save space when you need to store large number of unsigned integers. I came up with two methods, one the evil but faster (exploiting the C features of C++) and the other which is more elegant, with similar performance in space but (might) slow down marginally. I’ll prefer the second, but C++ allows you to shoot yourself in the foot, so eager geeks go ahead

Using (non-recommended) C style type-casting:

#include <iostream>
#include <string>

using namespace std;

void EncodeNumber(unsigned int num, string* num_str) {
  unsigned char buf[4];
  unsigned char* ptr = (unsigned char*)&num;
  buf[0] = ptr[0];
  buf[1] = ptr[1];
  buf[2] = ptr[2];
  buf[3] = ptr[3];
  num_str->assign((const char*)buf, 4);
}

void DecodeNumber(const string& num_str, unsigned int* num) {
  const unsigned int* a = (const unsigned int*)num_str.c_str();
  *num = *a;
}

int main() {
  unsigned int num;
  cin >> num;
  string num_str;
  EncodeNumber(num, &num_str);
  cout << "String format of number: " << num_str << endl;
  DecodeNumber(num_str, &num);
  cout << "Decoded number: " << num << endl;
  return 0;
}

The one using (recommended) C++ style type-casting:

#include <iostream>
#include <string>

using namespace std;

void EncodeNumber(unsigned int num, string* num_str) {
  unsigned char buf[4];
  buf[3] = num >> 24; num <<= 8; num >>= 8;
  buf[2] = num >> 16; num <<= 16; num >>= 16;
  buf[1] = num >> 8; num <<= 24; num >>= 24;
  buf[0] = num;
  num_str->assign(reinterpret_cast<const char*>(buf), 4);
}

void DecodeNumber(const string& num_str, unsigned int* num) {
  const unsigned int* a
      = reinterpret_cast<const unsigned int*>(num_str.c_str());
  *num = *a;
}

int main() {
  unsigned int num;
  cin >> num;
  string num_str;
  EncodeNumber(num, &num_str);
  cout << "String format of number: " << num_str << endl;
  DecodeNumber(num_str, &num);
  cout << "Decoded number: " << num << endl;
  return 0;
}

PS1: The encoding and decoding is assured to work if both are done on machines with same endianness and will break if different for encoding and decoding.
PS2: All this was done while waiting for a computationally intensive task to complete. Unfortunately this can’t speed it up . Hope (at least) someone finds some use of this

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

Zeros and Ones .. One Pass

Have heard this question a lot and wanted to code it. I initially always used the version 1 (described below) of this code to form solutions, but I figured an optimization and the version 2 is actually a one-pass algorithm.

Version 1: ( debatable one pass)

#include <iostream>
#include <vector>

using namespace std;

int main() {
  int n;
  cin >> n;
  // containing 0s and 1s
  vector<int> binaries;
  for (int i = 0, t = -1; i < n; ++i) {
    cin >> t;
    binaries.push_back(t);
  }

  vector<int>::iterator back_iter = binaries.begin();
  vector<int>::iterator front_iter = binaries.begin();

  for (; front_iter != binaries.end(); ++front_iter) {
    if (*front_iter == 0) {
      // find the localtion of the back pointer which is pointing to a 1
      while (back_iter != front_iter && *back_iter == 0) {
        ++back_iter;
      }
      if (back_iter != front_iter) {
        // found a place to replace
        iter_swap(back_iter, front_iter);
      }
    }
  }

  for (int i = 0; i < binaries.size(); ++i) {
    cout << binaries[i] << " ";
  }
  cout << "\n";
  return 0;
}

Version 2: Definitely one – pass

#include <iostream>
#include <vector>

using namespace std;

int main() {
  int n;
  cin >> n;
  // containing 0s and 1s
  vector<int> binaries;
  for (int i = 0, t = -1; i < n; ++i) {
    cin >> t;
    binaries.push_back(t);
  }

  vector<int>::iterator front_iter = binaries.begin();
  vector<int>::iterator back_iter = binaries.end() - 1;

  for (; front_iter != binaries.end() && front_iter != back_iter; ) {
    if (*front_iter) {
      iter_swap(front_iter, back_iter);
      --back_iter;
    } else {
      ++front_iter;
    }
  }

  for (int i = 0; i < binaries.size(); ++i) {
    cout << binaries[i] << " ";
  }
  cout << "\n";
  return 0;
}

Finally I coded this.

Another simple solution

Am getting lesser and lesser time to maintain this blog .. anyways a friend of mine asked me a problem to solve recently and as soon as I got time (with some outside help ) I was able to come to a very elegant looking simple solution. Sometimes we forget the basic properties of some algorithms which surprisingly can solve classic problems.

Problem: Given an array of elements find the largest possible number that can be formed by using the elements of the array.
eg: 10 9
ans: 910
eg: 2 3 5 78
ans: 78532

Solution:

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

// Uncomment the commented code to see the behaviour

long long int NumberConcater(int a, int b) {
  char str_num[100];
  int sizea = sprintf(str_num, "%d", a);
  // cout << "1 : " << str_num;
  sprintf(str_num + sizea, "%d", b);
  // cout << "   2 : " << str_num;
  long long int option_number = atoll(str_num);
  // cout << "   Number : " << option_number << "\n";
  return option_number;
}
static bool MySorter(int a, int b) {
  long long int o1 = NumberConcater(a, b);
  long long int o2 = NumberConcater(b, a);
  return o1 > o2;
}

int main() {
  int n;
  cin >> n;
  vector<int> nums;
  for (int i = 0, t = 0; i < n; ++i) {
    cin >> t;
    nums.push_back(t);
  }
  sort(nums.begin(), nums.end(), MySorter);
  for (int i = 0; i < n; ++i) {
    cout << nums[i] << "\n";
  }
  return 0;
}

Using the concept of ordering, (I believe) this problem can be solved like this. Which is kinda cool

A simple integer array encoder with a very fast decoder

The post heading is enough for the explanation of the code I guess . This, surprisingly is a very nice technique given that you are constrained to use a c/c++ string for encoding an integer/floating point array. Comments are welcome as usual.

#include <cstdio>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

void decoder(const char* ptr) {
  int *p = (int *)ptr;
  int size = *p;
  for (int i = 0; i < size; ++i) {
    ++p;
    printf("%d\n",*p);
  }
}

void encoder(const vector<int>& input, string *out) {
  int *arr = new int[input.size() + 1];
  arr[0] = input.size();
  for (int i = 0; i < input.size(); ++i) {
    arr[i + 1] = input[i];
  }
  const int size = arr[0] + 1;
  char encode[size * sizeof(int)];
  memcpy(encode, arr, size * sizeof(int));
  string encoder;
  for (int i = 0; i < size * sizeof(int); ++i) {
    encoder += encode[i];
  }
  out->assign(encoder);
  delete arr;
}

int main(int argc, char *argv[]) {
  vector<int> input;
  cout << "Enter the numbers. Enter -1 to stop.\n";
  int tmp = 0;
  while (1) {
    std::cin >> tmp;
    if (-1 == tmp) break;
    input.push_back(tmp);
  }
  string result;
  encoder(input, &result);
  std::cout << "Size of array now: " << result.size() << "\n";
  decoder(result.c_str());
  return 0;
}

Will try to add another code with a fast/size efficient encoder and possibly (intuitively) slower decoder.

Change

Never thought people (me for that matter) change so quickly. Not long ago I posted here about how I don’t enjoy computers much but just barely make up with them. Yesterday I had to travel to my parents and I was shocked at how badly I was bored when I was not coding. I had to stop listening to music and open a terminal and start coding. I guess when one does something everyday, it becomes difficult to hate it (arranged marriages? ). Wanted to start on a task which I could complete so wrote the complete code for reversing all the words in a given string (ya ya … I know .. I know its too easy ).
Re-wrote all the library functions, have to confirm their behaviour though . Do let me know if there are any obvious/major bugs.

#include <stdio.h>
#include <stdlib.h>

#define _DEBUG_HAULT_ scanf("%*d");
#define STR_TERM '\0'
#define MAX_INPUT_LENGTH 1000
#define DELIMITERS " ,.':;"

int my_strlen(const char* str) {
  register int len = -1;
  for (;*(str + ++len););
  return len;
}

char* my_strchr(const char* s, int ch) {
  if (NULL == s) return NULL;
  for (; STR_TERM != *s && *s != ch; ++s);
  return STR_TERM == *s ? NULL : (char *)s;
}

char* my_strrev(const char* str, register int l) {
  register int i = -1;
  char *retVal = (char *)malloc(sizeof(char) * l);
  retVal[0] = retVal[l] = STR_TERM;
  for (; l; retVal[++i] = str[--l]);
  return retVal;
}

char* my_strtok(char *buf, const char* delim) {
  static char* record;
  record = (buf == NULL) ? record : buf;
  if (*record == STR_TERM || NULL == record) return NULL;
  char* temp = record;
  while ((STR_TERM != *record) && (NULL == my_strchr(delim, *record))) {
    ++record;
  }
  if (STR_TERM == *record) return temp;
  while ((STR_TERM != *record) && (NULL != my_strchr(delim, *record))) {
    *record = STR_TERM;
    ++record;
  }
  return temp;
}

// Removes all the punctuations (marked in constant DELIMITERS) and inserts
// only 1 space between words.
int main(int argc, char *argv[]) {
  char input[MAX_INPUT_LENGTH], output[MAX_INPUT_LENGTH];
  input[0] = output[0] = STR_TERM;
  scanf("%[^\n]", input);
  register int len = 0, temp = 0;
  register char* ptr = NULL;
  for (ptr = my_strtok(input, DELIMITERS);
       ptr;
       ptr = my_strtok(NULL, DELIMITERS)) {
    temp = my_strlen(ptr);
    sprintf(output + len, "%s ", my_strrev(ptr, temp));
    len += (temp + 1);
  }
  output[len - 1] = STR_TERM;
  printf("%s\n", output);
  printf("%s\n", my_strrev(output, my_strlen(output)));
  return 0;
}

After I was done, I found out about strsep

DP after a long time :)

At work it seems I will be shifting from Java to C++ now. I have never coded in C++ before, whenever I have it was solely for the purpose to use their beautiful vector, map, string and all libraries. So I guess I should start doing some C++ coding too. A step towards it, I wrote a C code after a looong time. Obviously, a DP problem to target . It is a typical interview problem, just that the O(n) is also possible, and I feel it’s the best one can do.

Problem: Given an array of integers, each element represents the max number of jumps can make forward. What is the minimum number of element selections to reach the end of the array (starting from the first element).
Example: arr = 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9
Here the min # of selections is : 3
with the sequence : 1-> 3 -> 8 ->9
First element is 1, so can only go to 3.
Second element is 3, so can make at most 3 jumps: eg to 5 or 8 or 9.
If an element is 0, then cannot make any jumps

PS: Have not checked for corner cases. Laziness again

#include<stdio.h>
#include<stdlib.h>

#define MAX 0x7fffffff

inline int min(int a, int b) {
  return a >= b ? b : a;
}

int find_min_steps(int const * const input, const int n) {
  int min_steps_dp[n], i, temp, next_vacant;
  for (i = 0; i < n; min_steps_dp[i++] = MAX);

  min_steps_dp[0] = 0;
  next_vacant = 1; // Is the index in the array whose min_steps needs to be updated
                   // in the next iteration.
  for (i = 0; i < n && min_steps_dp[n - 1] == MAX; i++) {
    temp = i + input[i];
    if (temp >= n) {
      min_steps_dp[n - 1] = min(min_steps_dp[n - 1], min_steps_dp[i] + 1);
      temp = n - 1;
    } else {
      printf("Updating min[%d] to %d \n", i + input[i], min_steps_dp[i] + 1);
      min_steps_dp[temp] = min(min_steps_dp[temp], min_steps_dp[i] + 1);
    }
    if (temp > next_vacant) {
      for (; next_vacant < temp; next_vacant++) {
        min_steps_dp[next_vacant]
          = min(min_steps_dp[temp], min_steps_dp[next_vacant]);
      }
    }
  }
  for (i=0;i<n;printf("%d ",min_steps_dp[i++]));printf("\n");
  return min_steps_dp[n-1];
}

int main() {
  int n, *input, i;
  scanf("%d",&n);
  if ((input = (int *)malloc(n * sizeof(int))) == NULL) {
    return -1;
  }
  for (i = 0;i < n; scanf("%d",&input[i++]));
  printf("Minimum steps: %d\n",find_min_steps(input, n));
  return 0;
}

Another Greedy solution provided by Abhishek in O(n) time and O(1) space.

#include <iostream>
#include <vector>

using namespace std;

int find_min_steps(vector<int>& input) {
   int start, end, next_start;
   vector<int> result;
   start = end = 0;
   int n = input.size();

   while (end < n-1) {
     int max = -1;
     for(int w = 0; start <= end ; w++, start++){
       if(input[start] + w > max) {
         max = input[start] + w ;
         next_start = start;
       }
     }
     start = end + 1;
     end = next_start + input[next_start];
     result.push_back(input[next_start]);
   }
   cout << endl << "steps are : ";
   for(int i =0; i< result.size(); ++i)
     cout << endl << result[i];
   cout << endl;
   return result.size();
}

int main() {
  vector<int> input;
  int t = -1;
  cout << endl << "enter input values.. (-1) to end" << endl;
  do {
   cin >> t;
   input.push_back(t);
  } while(t != -1);
  input.resize(input.size() -1); //remove last pushed -1.
  cout << endl << "Minimum steps: "<< find_min_steps(input) << endl;
  return 0;
}

An old question

Not that it has been long since I left college, but I remember once when I was preparing for my placements, I came across an interesting problem which is:
An array {A1,A2,A3,….,An,B1,B2,……,Bn} is given and we have to rearrange it as {A1,B1,A2,B2……} .Give an algo with minimum time and space complexity

I got it here, this is an awesum forum BTW, I really liked it and definitely plan on following it soon.

I remember spending a lot of time on it and discovering a pattern in the solution. Today, I saw this problem somewhere else and I remembered to have done some investigation over it. Luckily I found the code for it which I had written then, but unfortunately, I forgot the pattern and now I am too lazy to pick up the pen and paper and start all over again. I’l post the code here, I feel it’s O(1) space and O(n) time, but looking at the level of discussion at the forum I pointed to I feel something is wrong in the code. Can you find it for me ??

Also looking at this code of mine, for the first second, I couldn’t make out any sense of it and suddenly I realized the importance of comments and clean code.

#include <stdio.h>

int main() {
  int n, i, j , k, t1, l;
  scanf("%d",&n);
  int arr[n<<1 + 1];
  for (i=1,j=n<<1,k=-1,l=0;i <= j ; i++ ) {
    if ( i <= n )
      arr[i] = k+=2; // 1 3 5 7
    else
      arr[i] = l+=2;
  }
  arr[0]=0;

  printf("\n\nBefore Shuffling ..\n");
  for (i = 0;i <= n<<1; i++) printf("%d ", arr[i]);
  printf("\n\nShuffling Now ..\n");

  // Shuffleing starts 
  i = 1;
  int chk[j+1]; // To check if each element was visited only once
  for (i=0;i<=j;i++) chk[i]=0;
  i = 1;
  while (i <= j) {
    while (i<=j && arr[i] == i) {
      chk[i]++;
      i++;
    }
    if (i >j)
      break;
    t1 = arr[i];   // swap with temp
    k = i; // note the curr. loc in array
    l = i;
    printf("%d   : Value of i entering loop\n",i);
    while (1) {
      k = k & 1 ? (k + 1) / 2 : n + k / 2;
      chk[k]++;
      if (k == i) break;
      arr[l] = arr[k];
      l = k;
    }
    arr[l] = t1;
  }
  for (i = 0;i <= j;i++) printf("%d ",arr[i]);
  printf("\n Checking which element was processed how many times.\n");
  for (i = 0; i <= j; i++)
    printf("%d  %d\n",i,chk[i]);
  return 0;
}

Solutions to Interview Questions 2

This post provides the solutions/approaches to the problems provided by me in the Interview Problems 2.

If you have better approaches do share as comments.

Question 1: You are given 2 arrays of size ‘n’ each. You need to stable-merge these arrays such that in the new array sum of product of consecutive elements is maximized and the relative ordering of elements of A and B in C is not reversed.
eg
A= { 2, 1, 3}
B= { 3, 7, 9}
Stable merging A and B will give an array C with ’2n’ elements say C={c1, c2, c3, c4, c5, c6}
You need to find a new array C by merging (stable) A and B such that sum= c1*c2 + c3*c4 + c5* c6….. n terms is maximum.

Solution 1: A simple DP problem with the following recurrence
Condition : S[i+j-1] + max ( A[i] * A[i+1], A[i] * B[j], B[j]*B[j+1])
If in the above condition, the max is due to A[i]*A[i+1], then the merged array will have A[i] in (i+j)th place and A[i+1] at (i+j+1)th place and i will be i+=2, similarly if max is due to A[i]*B[j], then merged array will have A[i] in (i+j)th place and B[j] in (i+j+1)th place and same for the third one.
i is the index of the elements in A array and j in B array and S[i+j-1] is the max sum upto the current state.

A code is worth a million explanations, so here is it.

const int Max = 1000;
vector<int> a,b;
int n;

int memo[Max][Max];


int solve(int i,int j) {

   if(i == n) {
      int ret = 0;
      for (int k=j;k<n;k++) {
	 ret += b[k] * b[k+1];
	 ++k;
      }
      return ret;
   }
   if(j == n) {
      int ret = 0;
      for (int k = i; k < n; k++) {
	 ret += a[k] * a[k+1];
	 ++k;
      }
      return ret;
   }

   int&ret = memo[i][j];
   if(ret != -1) return ret;

   ret = -INF;
   // Three possibilities.
   // (i,i+1) ; (j,j+1) ; [(i,j) == (j,i)]
   if(i + 1 < n) {
      ret = max(ret, a[i] * a[i+1] + solve(i+2,j));
   }
   if(j + 1 < n) {
      ret = max(ret, b[j] * b[j+1] + solve(i,j+2));
   }
   ret = max(ret, a[i]*b[j] + solve(i+1,j+1));
   return ret;
}
int main() {


   scanf("%d",&n);
   a.resize(n); b.resize(n);

   for (int i=0;i<n;i++) scanf("%d",&a[i]);
   for (int i=0;i<n;i++) scanf("%d",&b[i]);

   memset(memo, -1, sizeof memo);
   printf("%d\n",solve(0,0));
   return 0;

}

Question 2: Write code for aligned malloc and free.
Solution 2: See The C programming Language by Brian Kernighan and Dennis Ritchie. It has the implementation of malloc and free. But for this question you will need to make an additional structure and record the actual starting address returned by the malloc call and you will return the aligned pointer. When the call to aligned_free is made, you only pass the recorded address as argument to the actual free function. [I'll code this only on request :lazy]

Question 3: Our cell phones have T9 dictionary embedded for message writing…How this dictionary is implemented? State any other way to optimize complexity.Mechanism of Addition of new words in that dictionary.
Solution 3: See T9 Dictionary and the tutorial on the DS used is here, here and this is a tutorial on the best DS (optimized for better performance) used for this type of situation. [Tries and Compressed Tries]

Question 4: Given an array of integers(both positive and negative) divide the array into two parts(sub-arrays) such that the difference between the sum of elements in each array is minimum?
Solution 4: A simple interview problem on O(n) space and O(n) time

Question 5: Write a program to shuffle an pack of cards in the most efficient way.
Solution 5: Knuth Shuffle is the best.

Question 6: Sort an array of 0s, 1s and 2s in O(n) time and O(1) space.
Solution 6: Here is my code for the problem and this is a link shared by spsneo in the comments.

#include<stdio.h>

int main()
{
	int n, i;
	scanf("%d",&n);
	int arr[n];
	for (i=0;i<n;i++)
		scanf("%d",&arr[i]);
	int p_0 = 0, p_2 = n-1, p_1 = -1;
	while (p_1 < p_2 )
	{
		while (p_0 < p_2 && arr[p_0] == 0)
			p_0++;
		while (p_0 < p_2 && arr[p_2] == 2)
			p_2--;
		if (arr[p_0] == 2 || arr[p_2] == 0)
		{
			arr[p_0]^=arr[p_2]^=arr[p_0]^=arr[p_2];
			continue;
		}
		if (p_1 == -1 )
			p_1 = p_0 + 1;
		while (p_1 <= p_2 && arr[p_1] == 1 )  p_1++;
		if (p_1 > p_2)
			break;
		if ( arr[p_1] == 0 )
		{
			arr[p_1]^=arr[p_0]^=arr[p_1]^=arr[p_0];
			p_0++;
		}
		else if ( arr[p_1] == 2 )
		{
			arr[p_1]^=arr[p_2]^=arr[p_1]^=arr[p_2];
			p_2--;
		}
	}
	for (i=0;i<n;i++)
		printf("%d ",arr[i]);
	return 0;
}

Another trivial solution can be to just count the number of 0s,1s and 2s and create the array again.