Career Center Interview Questions
Algorithms Interview Questions
1 What is the fastest way to count the number of ones in a given number represented in a binary form. You can assume that you have infinte run time memory and the response time should be O(1) always. Can you optimize the memory used?
2 What will be the complexity of finding the duplicates in an array?
3 You are given a stack of punched cards, each with m rows and n columns. Come up with a algorithm to punch holes so that you can find the missing cards (their sequences) in O(1) time. You can assume that you are looking for a missing card and only one is missing out of
all possibilities.
4 Write the binary search function in a C language.
5 In the given array, find the subsequence with maximum sum and minimum length.
E.g. [10,25,-23,40,-12,39,7] - The subsequence [39,7] has sum of 46 with length 2.
6 Reverse a linked list
7 Write an algorithm to compress a text file
8 How would you implement a BigInt class?
9 If you are given x punched cards each with m rows and n
columns, can u come up with a number scheme to identify missing
patterns.
10 An absolute number is defined as one in which each digit is
strictly smaller than the digit to its right (if any). For e.g. 123,
478, 369 are all absolute numbers. 205, 485 are not. Write a program
to calculate these.
1 You are given a list of strings of 0s and 1s. E.g. 10, 110, 01001, ...
Devise an algorithm to check if any of the string is a prefix of another one.
2 Given 2 strings, both the strings are again a sequences of 0s and
1s, write an algorithm to find if one is a substring of another.
3 You are given an undirected graph. Each node in the graph is also
assigned a type (say A, B, C, D). There are n nodes in the graph and
there are m possible types that can be associated with each node. You
need to find all the walks from a given source node (say N1) to a
given destination node (sat D1) such that the walk contains a node of
type A. What datastructures would you use? Write the algorithm?
4 Write an algorithm for finding the word count in a string / file
5 Write a sorting algorithm that whose complexity is less than O(n
* log n). Should we make any assumptions on the actual data to achieve
this?
6 Assume that we have a table of name value pairs. The only
accesses are through methods value_t read(key_t) and void write(key_t,
value_t). We need to support the transactions (as understood in
database world) for just this single table. There are no concurrent
writes but different processes can read / write at different instants
of time. Simply put, don't bother about locking for now.
What datastructures would you use? Write pseudo code for Start
Transaction and Close Transaction? Test it for valid uses cases (some
are given below)
Process time line ----------------------------->
P1 OP X; OP X; ST; OP X; OP X; OP X; read(1); write(1, 102); OP X; CT
P2 OP X; OP X; OP X; OP X; OP X; ST; OP X; OP X; OP X; read(1); OP X; CT
OP X is any random operation. read(x) means read key x; write (x, y)
means update table with value y for key x.
Other valid use cases include, transactions staring after P1 closing
transaction, transactions starting before P1 starts its transaction
and processing changing values in their transaction. As explained
earlier, you can assume that any transaction updating values will have
exclusive rights for that value alone till the end of that
transaction.
1 Write a program to find word count
2 You have 2 lists - X and Y, each containing strings. Write a
SCRIPT that would list all the elements of List X which are not in
List Y. Improve the performance when you know that list X is very
small compared to list Y.
3 In a distributed system, each machine has a sequence of
numbers (integers). We don't know anything about the distribution of
these sequences. Each distributed component implements 2 remote
procedure calls - getMedian and getNumElementsBelow(int value). Write
a master program that would query the individual machines and find the
combined median of all the sequences, in the the most optmized way.
E.g. If there are 2 sequences - (1,2,3) and (4,5,6), median of (1,2,3)
= 2 and median of (4,5,6) is 5. In your master program, you can ask
the components - getMedian and getNumElementsBelow(int num) in some
sequence and find out that the median is [3,4] or [3.5].
4 How would you implement a queue only with stacks?
hint: use as many stacks as you want.
5 You are implementing a vector - an expandable container. The
two possible choices on how to increase the size when the vector is
full are - 1. Double the size, copy over the elements to the new
vector. 2. Increase the size by a constant k (system default and user
cannot configure this). Compare the 2 implementations
6 You have a binary tree and the nodes contain an additional
information - the number of elements in that tree (including itself).
E.g.
-------------
| 2 | count = 3
-------------
/
/
/
/
----------- ------------
count=1 | 1 | | 3 | count=1
----------- ------------
Write the function - nth(tree * t, int n) which would return the node
which would be the nth node on an in-order traversal. Use the extra
information (node count, stored as part of each node)
7 You have a list of numbers X1, X2, X3, ... Xn
Populate the list Y with numbers Y1, Y2, Y3,...Yn, where Yi is the
product of Y1 * Y2 * .. Y(i-1) * Y(i+1) * Y(i+2)...Yn
What if you were not allowed to use division operator? Can you still
compute the results in O(n * log n)? How about O(n)?
8 Given 2 lists L1 and L2, write a function intersect which
would return the element common in both L1 and L2. The individual
lists L1 and L2 are sorted, integer arrays. Whats is sizeof(L1) <<
sizeof(L2)
9 Given n points (X1,Y1,Z1), (X2,Y2,Z2),
(X3,Y3,Z3),...(Xn,Yn,Zn), find k points that are closest to the origin
(0,0,0). How about finding K points closest to each other?
10 Given a sentence (e.g. "i like green applies"), write a program
to reverse the words in the sentence (result: "apples green like i").
The optimal solution is O(n)
1 Write a function to check if a given string is a palindrome?
2 Modify the above function to check if there are any
substrings (length >= 2) that are a palindrome?
3 Write a function to insert integers into a linked list in a
sorted manner?
4 Given two strings, write a function that would print
characters in the first string that are not in the second string and
also print characters in the second string that are not in the first
string.
5 Modify the above function to handle sorted strings
6 Write a function to delete a node from a binary search tree?
7 Write a function to reverse the words in a sentence?
Generate test cases and walk through.
8 You are given a plotter which can plot points given as x and y coordinates? Given a list of points, write a program that will sort the points in such a way that the plotter hand will move the least.
