INTERVIEW QUESTIONS - PROGRAMMING
AN - Analytical/Puzzle
AL - Algorithms
JP - Java Programming
AN /ALIn a party, every guest knows somebody else. A celebrity arrives at the party.
Everyone knows the celebrity, but he doesn’t know anyone. Write a O(N) efficient program to
find out who is the celebrity among all the guests.
HINT Let F be a NxN boolean 2D array, representing if a guest knows another guest. F[i][j] is true if
i knows j. If F[i][j] is false, we know that j is not the celebrity and i is still a possible celebrity.
We can exclude j from future checks. Similarly, if F[i][j] is true, we can eliminate i as the
celebrity.
SOLN int findCelebrity(boolean [][] F) {
int i = 0; j = 1;
while(j < [Link]) {
if(F[i][j] == true)
i = j++;
else
++j;
}
return i;
}
AN There is a horse-race competition in which 25 horses are participating. The size of the race
track permits only 5 horses to run at the same time. What is the minimum no of races needed
to find the top 3 fastest horses.
SOLN Let’s start with 5 races in which each horse participates only once. Let the horses in each race
be in the following order - (A1, A2, A3, A4, A5), (B1, B2, B3, B4, B5), (C1, C2, C3, C4, C5),
(D1,D2,D3,D4,D5) AND (E1,E2,E3,E4,E5) where is the first horse is the fastest in rach
combination. With this result, we can eliminate A4,A5,B4,B5,C4,C5,D4,D5,E4,E5. Now let’s
race the winners of each race (A1,B1,C1,D1,E1). With this result, we can eliminate D1, E1 and
also D2,D3,E2,E3(W/o loss of generality). Since C1 was third, we can eliminate C2 and C3.
Similarly we can also eliminate B3. Now we have the find the 2 horses from A2, A3,
B1, B2 and C1. The final order would be A1 and 2 winners of the final race. Total no of races
needed are 7
AL WAP such that if an element in a MxN matrix is 0, its entire rows and columns are set to 0.
HINT Blindly setting each row and column to 0, whenever a 0 is encountered will soon make the
entire matrix set to 0. There should be a way to track the 0 in the original matrix. We need a
second matrix boolean F[m][n] which will keep track of of 0. But this will entail O(mn) space.
This can be reduced further by using 2 boolean arrays - one each for storing 0 in rows and
columns. This will take only O(m+n) space.
SOLN public void setZeroes(int[][] matrix) {
boolean[] row = new boolean[[Link]];
boolean[] column = new boolean[matrix[0].length];
for(int i = 0; i < [Link]; i++) {
for(j = 0; j < matrix[0].length; j++) {
if(matrix[i][j] == 0) {
row[i] = true;
column[j] = true;
}
}
}
for(int i = 0; i < [Link]; i++) {
for(j = 0; j < matrix[0].length; j++) {
if(row[i] || column[j])
matrix[i][j] = 0;
}
}}
AL How do you remove duplicate elements from a Linked List
HINT If extra space is allowed, we can use a Hash Table to keep track of duplicates. We iterate
through the list, adding each element to the hash table. When we discover a duplicate
element, we remove the element and continue iterating.
If extra space is NOT allowed, we can use 2 pointers - current and runner. current pointer
iterates the linked list and runner checks all subsequent nodes for duplicates. O(n^2)
A third approach is to sort the given list using Merge Sort and then run a single loop and remove
duplicate elements by checking the next element. This approach doesn’t preserve the order of
elements. O(Log n) + n
SOLN Using a hash table
public static void deleteDuplicates(Node n) {
Hashtable hash = new Hashtable();
Node prev = null;
while(n != null) {
if([Link]([Link]))
[Link] = [Link];
else {
[Link]([Link], true);
prev = n;
}
n = [Link];
}}
Using 2 pointers
public static void deleteDuplicates(Node n) {
Node current = n;
while(current != null) {
Node runner = current;
while([Link] != null) {
if([Link] == [Link])
[Link] = [Link];
else
runner = [Link];
}
current = [Link];
}}
AL/JP A 2D plane contains n points on it. FInd a line which passes through most no of points
HINT Represent a line using a Line class. Identical lines will be have the same slope and
y-intercept. Loop through the points and store each line in a hashmap with its
occurence as the value. Return the line with maximum no of occurences
SOLN public static Line findBestLine(Points[] points) {
Line bestLine = null;
Map<Line, Integer> lineCountMap = new HashMap<>();
for(int i = 0; i < [Link]; i++) {
for(j = i + 1; j < [Link]; j++) {
Line line = new Line(points[i], points[j]);
if()
[Link](line, 0);
[Link](line, [Link](line) + 1);
if(bestLine == null || [Link](line) >
[Link](bestLine )
bestLine = line;
}
}
return bestLine;
}
public class Line {
double slope;
double intercept;
Line(Point p1, Point p2) {
slope = (p2.y - p1.y) / (p2.x - p1.x);
intercept = p1.y - slope * p1.x;
}
public int hashCode() {
//some function of slope & intercept;
}
public boolean equals(Object o) {
//both slope and intercept should equal
}
}
AL Given a MxN matrix in which each row & column is sorted in ascending order. WAP to find if
an element exists in the matrix or not.
15 20 40 85
20 35 80 95
30 55 95 105
40 80 100 120
SOLN public static boolean findElement(int[][] matrix, int element) {
int row = 0;
int col = matrix[0].length - 1;
while(row < [Link] && col >= 0) {
if(matrix[row][col] == element)
return true;
else if(matrix[row][column] > element)
col--;
else
row++;
}
return false;
}
AL A magic index i in an array A[n] is defined to be an index such that A[i] = i. Given an sorted
array of distinct integers, write a method to find a magic index, if it exists.
0 1 2 3 4 5 6 7 8 9 10
-40 -20 -1 1 2 3 5 7 9 12 13
HINT A brute force solution is to run a loop through the entire array and check if an element
matches the index. The complexity is O(n). But since the array is sorted, we can solve it faster.
The solution works very similar to a binary search problem. We can start by looking at the
middle element 3 . Since the index is 5 and the array is sorted, the magic index must be
towards the right.
SOLN public static int magixIndex(int[] array, int start, int end) {
int mid = (start + end) /2;
if(array[mid[]) == mid)
return mid;
else if(array[mid] > mid)
return magixIndex(array, start, mid - 1);
else
return magicIndex(array, mid + 1, end);
}
public staic int magicIndex(int[] array) {
return magicIndex(array, 0, [Link] - 1);
}
AL Check if any permution of a string is a palindrome
HINT In a palindrome, at most one character can appear odd no of times. Use a hashmap to store
occurences of each character. If more than character occurs odd no of times, it’s not a palindrome.
If space is a constraint, sort the string first. Loop through it, check occurrence of ith and i-1th character.
Check if more than 1 character appear odd no of times.