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;

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

Finally I did it !!

A friend of mine referred me to a problem from my own blog (i.e. here ) 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;
}

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.

Interview Problems 24

1. Given a linked list structure where every node represents a linked list and contains two pointers of its type:
(i) pointer to next node in the main list.
(ii) pointer to a linked list where this node is head.
Write a C function to flatten the list into a single linked list. (from here)

2. Hundred of millions of irregular shape objects are moving in random direction. Provide data structure and algo to detect collision. (from here)

3. You are given an array of integer A[1..n] and a maximum sliding window of size w. you need to output an array B where B[i] is the maximum in A[i, i+w-1]. (from here)

4. [Design] Find duplicate profiles in Facebook.

5. You have an array of 0s and 1s and you want to output all the intervals (i, j) where the number of 0s and numbers of 1s are equal. (from here)

6. You have a stream of random numbers that are inserted into an expanding array. How can you maintain the current median and what is the complexity.

7. Given n arrays, find n number such that sum of their differences is minimum. For e.g. if there are three arrays

A = {4, 10, 15, 20}
B = {1, 13, 29}
C = {5, 14, 28}

find three numbers a, b, c such that |a-b| + |b-c| + |c-a| is minimum. Here the answer is a = 15, b = 13, and c = 14

8. [Coding] Write a C/C++ program to create a bitmap of any size as determined by user. Say user says 64k bitmap, then create 64k long bitmap. Have set and unset methods.

9. Reorder 1st string based on 2nd string.
eg: (tractor,car)
output: carrtto or carrott or carrtot.

10. There is a straight roads with ‘n’ number of milestones. You are given an array with the distance between all the pairs of milestones in some random order. Find the position of milestones.
Example:
Consider a road with 4 milestones(a,b,c,d) :
a bcd
Distance between a and b = 3
Distance between a and c = 8
Distance between a and d = 10
Distance between b and c = 5
Distance between b and d = 7
Distance between c and d = 2
All the above values are given in a random order say 7, 10, 5, 2, 8, 3.
The output must be 3,5,2 or 2,5,3

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.

Interview Problems 23

1. A question set is given to you and you have to generate (question numbers are in an array) generate different set of question paper for k students.

2. Given an array of integers, find out number of ways in which you can select increasing subsequences of length k(k “abcababceced” (2 ‘c’ are removed)
After removing repeated substring of length 2: “abcababceced” –> “abcabceced” (substring “ab” is removed) and so on.

3. You are given a 1D array of integers, such as:
int[] array = [3,4,7,2,2,6,0,9];
Suppose you need to treat this array as a 2D table with a given number of rows.
You want to sum the columns of the table.
One value of numRows is 4..in that case the resultant array would look like
what if numRows==4?
3 4
7 2
2 6
0 9
—-
12 21

4. Given an unsorted array, find the longest consecutive elements sequence.
Ex: 5 7 3 4 9 10 1 15 12
Ans: 3 4 5

5. You have to create a graph in most efficient way from relationship of nodes read from txt file.
text file contains information like:
node_id weight node_id
node_id weight node_id
…..
// which means two nodes are connected with some weight. (undirected)
There are around 600K such information for about 65000 nodes.
Aim is to create a a subgraph for a given node_id. i.e for that node_id find ALL successor nodes with level mentioned i.e form a subgraph for that node.

6. Given ‘n’ no of sets and each set is of a variable size. Find out the cross product of these ‘n’ of sets.
For eg. {1,2} , {3,4} , {5,6,7} these are the three sets.The cross product of these sets would be as below.
{1,3,5},{1,3,6},{1,3,7},{1,4,5},{1,4,6},{1,4,7},{2,3,5},{2,3,6},{2,3,7},{2,4,5},{2,4,6},{2,4,7}.

7. Given an array of integers, find out number of ways in which you can select increasing subsequences of length k(k<=n).
eg array is 1 4 6 2 5 & k=3
Output: 3
Sequences: 1 4 6, 1 4 5, 1 2 5

8. Sorry posted this question as a repetition of question 1.

9. Given a binary matrix of N X N of integers , you need to return only unique rows of binary arrays
eg:
0 1 0 0 1
1 0 1 1 0
0 1 0 0 1
1 1 1 0 0
ans:
0 1 0 0 1
1 0 1 1 0
1 1 1 0 0

10. Given an array of size n wherein elements keep on increasing monotonically upto a certain location after which they keep on decreasing monotonically, then again keep on increasing, then decreasing again and so on. Sort the array in O(n) and O(1).

Interview Questions 22

1. Given an integer array, sort the integer array such that the concatenated integer of the result array is max. e.g. [4, 94, 9, 14, 1] will be sorted to [9,94,4,14,1] where the result integer is 9944141

2. I have a card pack of 313 cards. I remove the topmost card from card pack and place it on desk and I remove the next one and put it below the pack of cards(that you are holding). keep doing this till all the cards are on desk. Pick up the card stack from desk and repeat these steps till you find retrieve the original cards order.

3. [Design + Graph Traversal] Assume you have a set of 1500 independent pieces of code. We’ll call them projects. Each project can either be:
1) completely independent
2) dependent on other projects
3) dependent on other projects and have other projects dependent on it
The combined build times of all 1500 projects is 24 hours(so build project 1, when it finished, build project 2, etc). A build consists of compiling and linking all the requisite code. You can assume you don’t have to worry about a budget. If there’s a tool that would help you out, you can use it if you can describe how it works. How would you speed up the build process?

4. Given a BST in a language where memory must be handled manually, how do you completely remove BST from memory? Recursion is not allowed. [O(N), O(1)]

5. [Don't vomit out TRIE] You are developing a system for a cell phone which will automatically predict what word a user is typing. Talk about the data structures and algorithms you would use to make this, keeping in mind that cell phones have limited memory/CPU power.

6. There are N web servers. Each web server has a huge file containing random 1 million numbers (numbers can repeat). Find the median of these N million numbers given that only 1 million numbers can be brought into memory at a time.

7. Many irregular shape objects are moving in random direction. provide data structure and algo to detect collision. Remember that objects are in million.

8. A complete ternary tree is a tree in which each and every node has either 0 or 3 children . Given preorder of a complete ternary tree , construct the tree . Preorder will be a string containing characterd i and l where i represents an internal node and l represent a leaf node .

9. [Math] Find the number of strings of length n having u distinct uppercase letters , l distinct lowercase letters and d distinct digits.

10. Given a sorting order string, sort the input string based on the given sorting order string.
Ex. sorting order string -> dfbcae
Input string -> abcdeeabc
output -> dbbccaaee

Interview Questions 21

1. 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.

2. Store 100 million phone numbers, with minimal memory space. Search must be efficient.

3. [Pure Math] You have a set of ants moving on an horizontal segment of length n. Each ant can randomly move either right or left. When an ant takes a direction, she stays in that direction until she either drops out of the segment or it bumps with another ant. In this case, the ant changes her direction. Can you formalize the system and describe what will happen after t iterations?

4. Given an unsorted array arr[0..n-1] of size n, find the minimum length subarray arr[s..e] such that sorting this subarray makes the whole array sorted.

5. Given n distinct elements, how many Young tableaus can you make?

Interview Questions 20

Most problems in this post are adopted from Antonio Gulli’s coding playground.

1. Write a function that output the size of highest sub square matrix of 1s in matrix of 0s and 1s
For ex:
0 1
0 0
Output: 1

0 0 0
0 1 1
0 1 1
Output: 2

2. Input: Array of integers, A[0], A[1], …, A[n]
An operation is defined to have all A[i] altered by 1, i.e., A[i]++/A[i]–. Note whether A[i] is increased or decreased is independent from other elements in A.
Question: return the minimum number of operations to make all elements in A[i] be equal. If it is impossible, return -1;

3. Given N arrays containing values between 0 to x, what data structure would you use to store these arrays so that when given a test array ‘t’ find the closest array in N that has highest number of elements in ‘t’? Also what algorithm would you use to find the closest array. N could be in the order of 1000. x could be between [100,1000]

4. Given a triangle ABC and a point P, device an algorithm for understanding whether P is inside or outside the triangle.

5. Given an Array A, with very large size N find the element which appears 5/8 of times.

6. Device an infrastructure for storing data in Facebook. There are 500M users and let’s assume the average number of friends is 100. Each user can post a message, or can read all the fresh messages produced by her friends.

7. Devise an algorithm for suggesting friends in Facebook.

8. You are given a blue segment S of length n. There are n points p_i (0 <= i < n) distributed uniformly at random. You mark in red all the segments connecting points p_i and p_j what would be the predominant colour in S after that?

9. A 'Document' is defined as a collection of 'Fields'. Some fields can be optional. A 'Field' can be a first-order type (int, char, float), or an array of first order types.
Write the code to serialize and de-serialize a collection of 'Documents'

10. Given an expression E of n numbers with *, + operations and no precedence among the operators, identify the set of parenthesis which maximize the results for E.