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.

Interview Questions 19

1. Given a set of distinct integers {a1, a2, a3, a4, a5, …} and a set of exclusion rules: R = {{a1, a3}, {a2, a4, a10}, …} can you print out all the valid subsets?
Example:
what is a valid subset? {a1, a4}
what is an invalid subset? {a1, a2, a4}

2. How to compare two version numbers?
eg. 1.2.30.112 @ 2.12.11.09

3. Given an array arr of size M containing distinct integers, randomly select N distinct integers and output them. You are given the rand() function and N < M.

4. Telephone Dir lookup:
Given mapping: number to letters (just like on the telephone buttons)
input: digit string e.g. "1234"
1. output: all possible letter strings based on the mapping.
2. output only those strings that are in a given dictionary. (and length of the dictionary is small.)

5. Given n cities with their populations, suggest an algorithm to pick up one of the cities randomly such that more the population of city is more chance it stands to be picked. Assume you can use an inbuilt random generator function from the language library.

6. Convert an ASCII representation of a positive integer to it's numeric value.

7. Sort an input string according to the given order string. There might be characters in input string that are not present in the order string and vice-versa. The characters of input string that are not present in the order string should come at the end of the output string in any order. Write code.
Example: Sort("abdcdfs","dacg");
output: ddacfbs

8. Given a sorted array with duplicates and a number, find the range in the form of (startIndex, endIndex) of that number. For example, given 0 2 3 3 3 10 10 and 3, return (2,4). Given the same array and 6, return (-1,-1).
Further: Do better than linear scan, which is O(n).

9. Given a very large array of n integers, find the kth largest value in the array efficiently. You may assume that k is much smaller than n.
e.g. the third largest (k=3) of [1,3,2,2] is 1.

10. A program to find cycle in a directed graph.If multiple cycles are found print any but starting with the smallest node number.

Interview Questions 18

1. Given a unordered array of numbers, remove the fewest number of numbers to produce the longest ordered sequence. Print count of fewest numbers to be removed, and the remaining sequence.
For example, if input is 1 2 3 4 5 6 7 8 9 10, no (zero) numbers are removed, and input is the longest sequence.
If input is, 1 2 3 8 10 5 6 7 12 9 4 0, then fewest number of elements to be removed is 5 is the fewest number to be removed, and the longest sequence is 1 2 3 5 6 7 12.

2. Given a positive integer n, write a function to print the nth row of Pascal’s triangle.

3. Write a program to print out all valid tic-tac-toe game moves.

4. [Design] Design and implement APIs for caching web pages.

5.

Class B {
  int b;
  public:
    void disp();
    void show();
};
Class D : public B {
  int d;
  public:
    void disp();
    void show(D &);
};

What is the size of the Base Class and Derived ?

6.

 
class Sample {
  public:
    Sample() { cout<<"const"<<endl; }
    ~Sample() {cout<<"destr"<<endl;delete this; }
};
int main() {
  Sample *obj = new Sample;
  delete obj;
  return 0;
}

what happens when u delete this in destructor?

7. Given two arrays A & B of length l, containing non negative integers, such that the sum of integers in A is the same as sum of integers in B.( The numbers need not be the same in both the arrays.)
Now if you start with an index ‘k’ in each array and do the following summation, SUMMATION (Ak-Bk), where Ak is the value at index k of array A, and Bk is the value at index k of array B, where ‘k’ increments and wraps back all the way to k-1, the final sum value will be zero.
Question: Find a suitable ‘k’ such that during any point in the summation, SUMMATION(Ak-Bk) is always non negative. Find such a ‘k’ in O(n) time.

8. Given set of n points (Xi, Yi), write a function to find k nearest points from origin.

9. How do you avoid dangling pointers and dangling references? Can you have a const reference to an object i.e. MyClass& const refToObj;? Does having a const* to an object guarantee safety from seg faults? What is the best alternative?

10. Write a code which return square of any number, but you can not use Star or carrot sign.