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?

Advertisements

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.

Interview Questions 17

1. Given that you have one string of length N and M small strings of length L . How do you efficiently find the occurrence of each small string in the larger one ? [Hint: This is a nice link to go through]

2. [Old school tricks :D] You are given have a datatype, say X in C. Determine the size of the datatype, without declaring a variable or a pointer variable of that type, and, of course without using the sizeof operator!

3. Reverse a string using only bitwise operators and without temporary storage.

4. Two rectangles are given. As a struct having {bottomleft-x, bottomleft-y, topright-x, topright-y}. You are given two rectangles R1, R2, determine if they intersect.[ Basic Geometry]

5. Write a Generic Swap Macro in C.

6. Given a list of machines where each machine has a hard disk limit and memory capacity and given a list of processes where each process requires certain hard disk space and memory, write an efficient algorithm to match processes to machines. (You may assume process to server mapping is 1:1).

7. A container is filled up with balls. Each ball has a value. Red = 7, Yellow = 5, Green = 2, Blue 2. Some balls are removed from the container and the product of their value is 147,000. How many red balls have been removed?

8. Find out Non-Decreasing subsequence of length k with maximum sum in an array of n integers ? [ Hint: here].

9. You have 21 chocolates and 91 roses, how many bouquets can you make without discarding neither a rose nor a chocolate. All the bouquets must have the same number of chocolates and roses for you.

10. If you want to search for a friend on Facebook, what are the possible strategies that you could use. You are a programmer and can also access Facebook’s Social Graph API. Make your own assumptions. How could you make it a ‘Friend Finder’ app?

Interview Questions 16

1. There is a linked list of numbers of length N. N is very large and you don’t know N. You have to write a function that will return k random numbers from the list. Numbers should be completely random.

2. A file is given with many 0s stored in continuous way , store it in another file such that when you store try saving the space by using minimum amount of space. When you want to create the original file , you should be able to do so with the new file created.

3. Propose a data structure that would store numbers, without any knowledge about them, and allow to perform the operations: insert, get median, as efficiently as possible. Modify/optimize your design, only this time the numbers are from a group V, which is |V|<<n. [Hint: O(logn), O(logn)]

4. Given N computers networked together, with each computer storing N integers, describe a procedure for finding the median of all of the numbers. Assume that a computer can only hold O(N) integers (i.e. no computer can store all N^2 integers). Also assume that there exists a computer on the network without integers, that we can use to interface with the computers storing the integers.

5. [Interesting] Calculate the Resistance in ohm’s that a knights move would require on an infinite plane of resistors of unit resistance.

6. Given a binary tree with the following constraints: a) A node has either both a left and right child OR no children b) The right child of a node is either a leaf or NULL write code to invert this tree.

7. Suppose you are getting an infinite binary stream of characters then after any point of time you need to print whether the no is divisible by 3 or not, how will you do that? [Hint: A nice example of finite automata based algorithm design :)]

8. An array is of size N with integers between 0 and 1024(repetitions allowed). Another array of integers is of size M with no constraints on the numbers. Find which elements of first array are present in the second array.

9. Design a datastructure to represent the movement of a knight on a chess board.

10. On a empty chessboard, a horse starts from a point( say location x,y) and it starts moving randomly, but once it moves out of board, it cant come inside. So what is the total probability that it stays within the board after N steps.

Interview Questions 15

1. Input Data : {[1,3],[2,4],[10,11],[4,6]}
Output: {[1,6],[10,11]}
We have to merge all the ranges that are overlapping. You can consider Input data as any Data structure.

2. Given a char array with words in it, find all ‘a’ characters and replace with xyz. Modify the input array, do not create a copy of the array.

3. How do you output the nodes from a binary search tree given a range

4. Implement a function
public long[] GetMultiplesOfTwoLessThan(int num)
eg if num is given as 30, output array should contain {1,2,4,8,16}. It shouldn’t contain 32 since 32 is more than the given number.

Another exp: if num is 300 then output will be {1,2,4,8,16,32,64,128,256}
Super optimized solution desired

5. Write a program to arrange numbers from 1 to 16 such that the sum of two consecutive numbers is a perfect square.

6. Print all edge nodes of a complete binary tree anti-clockwise.
That is all the left most nodes starting at root, then the leaves left to right and finally all the rightmost nodes.
In other words, print the boundary of the tree.

Variant: Print the same for a tree that is not complete.

7. Given 3 product categories and a respective file of a huge size containing only the list of order numbers in sorted manner. Write an algorithm (best possible time complexity to be achieved) which can find common order numbers in all 3 files.

8. Implement boolean ValidateIP(string inpIP)

9. Given a file in which the data is stored in the form

ABC
_DEF
_GEH
XYZ
_PQR
__STY

Construct an nary tree out of it in O(n) time such that DEF and GEH are the children of ABC and XYZ is the sibling of ABC, PQR is child of XYZ and STY is child of PQR. The spaces after the beginning of a line specify the relation of a node to its predecessors.

10. Why auto variables are not stored in heap?

11. Each cell of an N x N grid is either a 0 or a 1. You are given two such N x N grids, the initial grid and the final grid. There is a button against each row and each column of the initial N x N grid. Pressing a row-button toggles the values of all the cells in that row, and pressing a column-button toggles the values of all the cells in that column. You are required to find the minimum number of button presses required to transform the grid from the initial configuration to the final configuration, and the buttons that must be pressed in order to make this transformation.

%d bloggers like this: