50 Algorithms 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?

Ads

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.

Ads

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.

Read More Algorithms Interview Questions