Algos, Puzzles and Programming Questions

Searching and sorting in a 2-d array

2010-01-21T13:39:00.000+05:30

Suppose you have a 2-d array with integers sorted both horizontally and vertically.
a) Search for the occurrence of a value in the array
b) Sort the array into a single-dimensional array

Find the number of negative elements in most efficient way

2010-01-18T11:14:00.000+05:30

Given an n X n array with rows sorted and cols sorted, find the number of negative elements in most efficient way.

Sort a ordered linkedlist

2009-12-31T11:37:00.001+05:30

A singly LL is given such that there is alternate ordering between the elements.

Ex: 1->2->13->14->11->5->4->null

Give an efficient O(n) algo to sort such a LL. There can be multiple such orderings in the given LL.

find height of a node in BST

2009-12-19T17:08:00.000+05:30

Given a BST T and a node N in T such that all leaf nodes are connected in doubly linkedlist fashion, find height of the node N in T.

Given two strings, find the minimum no. of steps required to covert one to the other?

2009-09-28T23:48:00.002+05:30

Birthday Calendar

2009-09-08T22:50:00.000+05:30

Implement the birthday diary calendar to keep records of all birthdays of your friends
1) what underlying data structure(s) you will use so that the memory consumption should be optimum [i.e if you have only 12 birthday entries you should not hold memory for all 365 days of the year].

2) You should be able to view the data (birthdays) with closest birthday first [i.e 7th July should come before 11 Aug].

3) How will you keep this data sorted (for question 2), everytime you insert a new birthday entry. This sorting should be as optimum as possible [mergesort etc will not be very beneficial bcoz ideally you won't have thousands or millions of birthday]

4) How will you handle 2 or N number of birthdays on same day

Given a string of n characters, find the longest palindrome in the string.

2009-09-08T22:41:00.000+05:30

O(n2) is simple, O(n) is nice

Given an undirected graph G(V,E), design an algo to detect whether there is a triangle in the graph?

2009-09-08T22:35:00.002+05:30

Find the minimum substring containing all unique characters atleast once in the given string

2009-08-30T03:37:00.002+05:30

Find pairs from the given array

2009-08-30T02:56:00.000+05:30

Given an array X, find tuples (xi, xj) such that j>i and xj is the immediate number greater than xi in the given array?

Ex Problem: X: {5, 4, 1, 3, 7}
Solution:
{5, 7}
{4, 7}
{1, 3}
{3, 7}

Random Number Generation - II

2009-08-30T00:09:00.006+05:30

Given a function rand5() which generates values between 0-5 with equal probablities, how would you create another function rand7() which generates values between 0-7?

For that matter given a function randM() which generates numbers between 0-M, how would you create another function randN() which generates numbers between 0-N with equal probabilities? Is it possible for every value of M,N?

PS: I'm calling this "Random Number Generation - II" because we already have another version of this problem here.

Think in terms of possible values being generated by the given randX() function and map to all the possible values to be generated by the target randY() function

Find union of two sets in O(1)

2008-11-11T21:48:00.001+05:30

Use bit-map

Palindrome in LinkedList

2008-09-05T20:47:00.004+05:30

Given a linked list with node as given below:

struct node
{
char info;
struct node *next;
}

Give an O(n) algorithm to find if its a palindrome or not? You can not use more than O(1) space.

Two pointers to explore the list, reach the mid-point reverse the first half and compare the two halves

Maze Searching

2008-09-05T20:41:00.003+05:30

Given a 2-d maze of characters, find if there exists a word "Algorithms" in the maze. By exists we mean it exists in a row, a column or like snakes (diagonals prohibited though)?

By snakes, we mean like following

A . . . M S
L G . T H .
. O R I . .
Use DFS and explore the maze as and when letters are found

Generating Graphs

2008-06-16T10:31:00.001+05:30

Given n nodes,

1. generate all possible directed subgraphs.
2. generate all possible undirected subgraphs.

Easier version:

Given n nodes,
1. generate all possible directed subgraphs of n nodes,
2. generate all possible undirected subgraphs of n nodes,

PubTrivia - a pub where algos are served alongwith drinks!

2008-06-14T20:20:00.004+05:30

You and your friends have gotten together for a Trivia night at a local pub.There are N questions asked during the night.Each question is worth a number of points; the i-th element of the points array corresponds to the score received by you if you correctly answer the i-th question, but you lose that many points if you answer that incorrectly. The questions are given in the order specified and you must answer each question before the next is asked. In addition, after each correct answer you will receive a token. If you then have tokensNeeded tokens, the pub will immediately take all of your tokens and award you additional bonus points. However, if you get the question wrong, the pub will take away all of your tokens without giving you any bonuses. The element i of the bonuses array corresponds to the bonus you receive if you win the bonus on question i.
Note that it is possible to win multiple bonuses during the game.
You know the answer to all the questions and want to maximize the number of points you receive.
Give an algorithm to obtain the maximum points that you can receive if you correctly choose which questions to answer.

Inputs :
N
tokensNeeded
p - array of points
b - array of bonuses

Calendar Cubes

2008-05-21T13:37:00.003+05:30

A corporate businessman has two cubes on his office desk. Every day he arranges both cubes so that the front faces show the current day of the month. What numbers are on the faces of the cubes to allow this?

I have come up with a solution which I would call "sly" and really "unfair"!

Difference between Singleton and Static implementations

2008-05-07T10:25:00.006+05:30

(1) Static implementations cannot be extended(only static fields and methods can be extended) whereas Singleton implementations can be extended and its methods can be overridden.
(2) Static implementations cannot extend other class's instance fields/methods while Singleton implementations can.
(3) Static implementations must be initialized at the class loading time however Singleton implementations can be lazy initialized or asynchronously initialized.
(4) Static implementations cannot be initialized with a STATE (parameter), whereas Singleton implementations can be.
(5) Static implementations can still have instances (unwanted instances) whereas Singleton implementations prevents it.

Exchange problem

2008-04-16T18:51:00.003+05:30

Its new year time and your company has sent T-Shirts of varying sizes from HQ (read US). The problem is that the sizes in US and the sizes in India don't really match. So a guy with L size in India would like to settle for M size in US, one with XXL in India would like to go for XL and so on. Employees in India are bugged up and want to exchange it with appropriate sized T-Shirt. Now that the management didn't take care of it before sending the T-Shirts to India, you have been assigned by the Indian management to arrange an exchange between the employees. How would you go about it? Also describe your algorithm. If all this information is stored in the database, write a query that would do the job.

Random Number Generation

2008-04-16T11:24:00.003+05:30

Given a function random(0,1) which randomly generates 0 or 1 with equal probabilities, extend its functionality to generate random numbers for an interval [a,b], i.e. implement random(a,b), for all 0 =< a < b. Prove that the strategy is uniformly random or would you like to put some conditions on a and b?

Another version: Given a random function random() which generates 0,1 but with uneven probabilities, create a random function newrandom() which generates 0,1 with even probabilities. Uneven probabilities mean if probability of getting 0 from random is p, that of 1 is (1-p) but p!=(1-p)!=1/2

array question again

2008-04-15T11:23:00.000+05:30

Suppose you are having an array of n integer. All the elements in the array are unique
except one element. That one special element in array is repeating in array in order of power two(means even repetition)

example - 1 2 3 4 5 6 5 7 8

all element in this array are unique except 5.. and 5 is repeating 2 times (power of 2).
we need an algo to find this special element in array

Why is String immutable in Java or are they?

2008-04-05T16:27:00.002+05:30

Ref: http://www.javaspecialists.eu/archive/Issue014.html

Team Photo Problem

2008-04-01T23:45:00.004+05:30

Since three guys (Ghoida, Nini and Dinu Kaka) from our team have decided to move on, its time to take a team photo. Camera man proposed that for a nice photo people should arrange themselves in such a way that the height difference between two adjacent guys are minimum. Since Dinu Kaka is the senior most of all three, we decided to keep him at the center and Nini and Ghoida will be at either ends (one at left and the other at right). Nini being so enthusiastic about his analytical skills decides to write an algorithm that will ensure that average height gaps of the arrangement is minimum. Any idea how he would do it? If there are even team members, Dinu Kaka may choose any of the two mid positions as he wish (and since he is a nice guy, he would accept any of the two positions that Nini tells him to go to).

another graph problem

2008-04-01T16:03:00.003+05:30

Find out if there is cycle in a given graph?

Knapsack Problem Variation

2008-04-01T00:13:00.004+05:30

Given infinite supply of "n" denominations of coins and a change amount "A", give an algorithm to use minimum number of coins to do the transaction?

Find minimum steps required

2008-03-31T23:56:00.003+05:30

Given a 2-d space with origin (0,0); find in how many minimum steps can a knight reach to a point (x,y) from (0,0)? Is it possible to traverse to any such point in the space from (0,0) or we have some specific conditions on x, y for such a path to exist? Prove your arguments.

Would your algorithm be still valid if traversing in x-axis direction is cheaper than traversing in y-axis direction or vice versa?

PS: a knight walks 2 units in X-axis and 1 unit in Y-axis or 2 units in Y-axis and 1 unit in X-axis in one move.

Some java fun !

2008-03-28T17:26:00.003+05:30

What will be the output of this simple program?

pretty simple, isn't it? :)

public class A
{

public void f(Exception e)
{
System.out.println("A");
}

public static void main(String args[])
{
A a = new B();
a.f(new RuntimeException());
}

static class B extends A {

public void f(RuntimeException e)
{
System.out.println("B");
}

}
}

some more stupid array questions

2008-03-28T16:39:00.003+05:30

1. an array has n/2 distinct elements and one element which is repeated n/2 times.. find out that element.. ofcourse.. in O(n)

2. there is an array of size n. it has n-1 distinct elements, each of lying in the range from 1 to n.. find out the element that has been repeated once.. do that in O(1) extra space..

a different doubly linked list

2008-03-24T15:32:00.003+05:30

A doubly linked list is defined as follows:
one link points to next neighbor and other link to any random node in the list.
How will you generate clone , given a linked list which follows above definition?
The list can be traversed only once.

largest common structurally similar sub tree

2008-03-19T14:54:00.003+05:30

Given two trees as input, find the largest common structurally equivalent sub tree between the two trees. (The largest common sub tree corresponds to the common sub tree having the maximum number of total nodes ).

Find two non repeated numbers

2008-03-18T22:09:00.000+05:30

Given an array of size 2n+2 of which there are n pairs and remaining two are unique. How to find them in O(n) time and constant space.

simple array qusetions

2008-03-18T19:33:00.003+05:30

Two easy puzzles .. and my first post too.. baki uncles will be happy to see it finally ;)

1. you have a sorted array. it has been rotated at an unknown index.. suggest an algorithm to find out an element from the rotated array... ex.. the array 561234 was made by rotating 123456 at the 4th index.. so how would you go about finding any number from the rotated array?

2. you have an array of the form a0a1a2...anb0b1b2....bn . how will you convert it into a0b0a1b1..anbn?? use O(1) memory and ofcourse come up with an O(n) running time complexity solution

3. an array has n/2 unique elements and one other element which has been repeated n/2 times... suggest different ways to find the repeated element.. O(n) solution can be achieved in multiple ways

find nth max element in BST(Binary search tree)

2008-03-17T12:13:00.003+05:30

Without using any extra space. Tree can be traversed only once.

Find nth fibonacci number

2008-03-16T22:22:00.001+05:30

Write an algo for finding nth fibonacci number.

Hint: Recursive solution is not acceptable :D O(n) is obvious :D, We are talking about O(logn) solution :)

Randomized Shuffling Problem

2008-03-13T20:44:00.002+05:30

How would you randomize an array of 52 values, from 0 to 51 with no repeats, such as you might want for a deck of cards? Prove that this really is random.

partition

2008-03-13T12:53:00.000+05:30

Algorithm to partition set of numbers into two such that difference between their
sum is min and they have equal number of elements

median problem

2008-03-13T12:49:00.001+05:30

you have n machines ,each having n integers.now u have to find the median of these n^2 numbers,but u can load only 2n integer at a time in memory.

Smallest subsequence

2008-03-13T12:43:00.000+05:30

A file contains a sequence of charaters. Each character can be repeated any number of times in a file. Find a smallest subsequence which contains all the characters in the file atleast once.

extra paranthesis

2008-03-13T12:41:00.001+05:30

how to remove unnecessary brackets from the given expression, without creating any ambiguity.
e.g. (1+2) * (3) .. this can be written as (1+2) * 3

Adobe face to face interviews

2008-03-13T12:22:00.002+05:30

1. n/2 repeated numbers from n numbers, all the other numbers are distinct . Find tht no
2. 3 containers .. take 1 ball frm 2 containers and place in the 3rd. repeat these steps such that finally all the balls are in 1 container (Hint: multiple of 3)
3. implement cron job in java
4. implement MRU cache data structure (Hint: LinkedHashSet)
5. implement HashSet (rehashing ...improvements)
6. JVM ... how does class data and methods are stored
7. find a circle in a linked list ... i gave the answer tht we can take 2 pointers ... move 1 ptr by 1 dist and the other by 2 dist .. why not move the other ptr by 3 dist
8. socket programming -- .. bind, connect, listen, accept, SELECT - when to use it ...
9. composition and inhertitance
8. n/w address translation table --- implement it
9. general TCP questions

Merge point in two linked lists

2008-03-11T10:03:00.004+05:30

Given two link list, find out do they merge ? if yes, find the merge point. What will you do if the link list have loop at the end ? What if the lists connect at an oval like shown below?

Find possible parenthesizing

2008-03-02T23:34:00.003+05:30

Given an input n write a program to generate all possible parenthesizing.

For ex: if n=3, then following is the result

((()))
(())()
()()()
(()())
()(())

Number of such elements is represented as Catalan Number. For more details, see http://en.wikipedia.org/wiki/Catalan_number

A similar problem asks to find all possible permutations of given elements with following two variations:

1. There might be repetitions
2. All elements are unique

Stack with findMin() in O(1) worst case

2008-03-01T15:52:00.004+05:30

Implement a data structure which provides all stack operations in O(1)(e.g. push(), pop()) and also provides findMin() in O(1) in worst case.

Difference b/w Collection and Collections

2008-02-26T14:07:00.002+05:30

Collections provide you views (annoymous class instances) for read-only

Implementation of an efficient MRU Cache in Java

2008-02-25T20:46:00.005+05:30

LinkedHashMap with doubly linked list to keep the most recently accessed element at the head/tail of the list. Every bucket's list keeps its own elements in the singly linked list and the same elements are doubly linked as well

Difference between Comparable and Comparator

2008-02-25T20:41:00.006+05:30

Comparator implementations can be used to define custom sorting even for Objects which already implement Comparable interface in TreeSet, HashSet

Find modulo (1 << k) division without using division

2008-02-23T00:32:00.006+05:30

m = n & (d - 1); where d= (1 << k)

Find if the given integer is even or odd

2008-02-23T00:08:00.003+05:30

Use of division is not permissible.

Bit Twiddling

2008-02-23T00:02:00.003+05:30

Find the minimum and maximum of two numbers without any branching. Prohibiting branching means (a>b)?b:a is also prohibited.

Sorting for large data sizes

2008-02-22T21:04:00.002+05:30

I have a computer file containing 1,000,000 non-negative integers, in no particular order. Imagine that they are the membership numbers of people who are enrolled in my internet club. A new person wants to join the club, and we need to find an unused number to allocate to them. How would you find, in a reasonable time, a number that was not already in the file?

Hint: Use Selection trees for finding the first missing integer among those 1,000,000 integers. The in memory amount of data that we have to keep is very small.

Reference: http://www.cse.ohio-state.edu/~gurari/course/cis680/cis680Ch6.html

Digits in a factorial

2008-02-21T22:05:00.003+05:30

Find the "number of digits in the factorial of a number" without finding the factorial??

Hint: Algorithm should not take more than O(lg N) where lg = log10

1-0 array problem

2008-02-18T21:19:00.006+05:30

Given an array A (n X n), which takes values from set {0, 1}; i.e.

A[i][j]= 0 or 1 for all i,j between 0 and n

Find a row i such that all elements in the row are 1s and a column j such that all elements are 0 except the intersecting element A[i][j] which is 1.

Another version of the same problem goes like this:
Given that every row of the array has all 1s and 0s together and 0s follow only after 1s in the row, find the maximum number of 1s in a row in the array.

Hint: O(n2) is a naive algorithm and O(n) is nice.

Finding repeated numbers in two arrays

2008-02-17T11:59:00.004+05:30

Given two sorted integer arrays (array size may differ).

Find the number of values that appear in both arrays.

For example, given:

A: 1, 3, 5, 8, 10. 14, 16, 25, 28, 47
B: 2, 4, 7, 8, 11, 12, 14, 17, 47, 56, 64

The result should be 3, since value 8, 14, 47 appear in both array.

Hint: A simple approach would take O(m+n) however it can be done in O(nlogm) (a better bound if n is very small as compared to m)

Blogs, Tagging and Summary Problem

2008-02-17T11:26:00.004+05:30

(Originally mentioned by Ghai uncle, this is an extended problem of the same kind)

A blogger just wrote a review on movie "Shivaji" starring Rajnikant and tagged it as "Rajnikant movie, Shivaji, movie review". For better surfing experience of the blogger, the blogging portal (your firm) wants to develop following features:

1. The moment the blogger posts his review, he is shown a list of other reviews on this movie. (To make it simple, the list contains links to blogs from his friends only)

2. There is an option to list all such blogs in a page. The listing page contains a shortest summary from each link containing all the tags and the tags highlighted properly in different colors in the summary. So for example, "Rajnikant movie" will be colored red, "Shivaji" would be colored blue, "movie review" will be colored green in the summary; however "Rajnikant" merit no coloring and "shivaji movie" merit coloring of "shivaji" only and likewise.

How would you do it?

Hint: There are essentially three problems:
1. finding blog links with similar tags.
2. finding shortest summary of text from a document containing all the tags in it.
3. finding out occurrences of a set of keywords/tags in a document.

Adobe Written interview questions

2008-02-09T19:12:00.006+05:30

1. Write an algo to print all paths in a binary tree.
2. Write an algo to determine if 2 rectangles intersect.
3. If an identifier is defined as follows
letter followed any number of letters and digits then write its regular expression.
4. x=b, z=1;k=n; // n is constant
while(k!=0)
{
if(k is odd) z=z*x;

x=x*x;
k=floor(k/2);
}
what is z at the end in terms of b and n?
5. What is synchronized statement, synchronized function, transient, wait(), notify(), notifyAll();
6. String s = "Hello";
String t = s.append(" Dolly");
Which string do s and t point to ?
7. What is advantage of entity beans over session beans?

8. What are J2EE components?
9. What is multi-tier architecture ? In which layer does browser fits in ?

Count the number of set bits in a byte/int32

2008-01-29T20:19:00.002+05:30

Hint: there are atleast 7 solutions each with varying runtime complexities. Popular ones are O(no. of bits), O(no. of set bits), O(no. of unset bits)

10 coins, 1 lighter coin

2008-01-29T20:17:00.001+05:30

Out of 10 coins, one weighs less then the others. You have a scale.

How can you determine which one weighs less in 3 weighs?
Now how would you do it if you didn't know if the odd coin weighs less or more?

Coins puzzle

2008-01-24T19:39:00.001+05:30

There are infinite number of coins in a dark room with exactly 129 coins facing heads.You need to divide the coins into 2 parts such that number of coins facing heads are equal in the 2 parts.

Puzzle Time: 2 egg problem

2008-01-18T11:35:00.001+05:30

You have 2 eggs and a multi-storeyed building with you[:) ..yes the building is yours!]
Tolerance level of an egg is defined as the minimum height from which dropping the egg would break it!In other words, if tolerance level of an egg is say 15 it means if the egg is dropped from floor no. >= 15 it would break.
Both the eggs have equal tolerance levels.
What is the minimum number of attempts you need to correctly determine the tolerance level of the eggs.

What if there are 3 eggs?

Linked List

2008-01-17T14:46:00.001+05:30

Find whether a circle exists in a Linked List. If yes then find the node where the circle begins. Can be done in O(n) time.

Repeated Number in an array

2008-01-17T14:43:00.002+05:30

An array of length n+1 is given which is filled with the numbers 1... n such that only 1 number is repeated. Find the repeated number.

Another variation of the problem asks to find repeated numbers if there are two such repetitions.

Linked List Intersection

2008-01-17T14:39:00.001+05:30

Suppose you have 2 Singly Linked List that intersect at a Node.
Find that node in O(n) time complexity and O(1) space.

3 Array Problem

2008-01-17T14:36:00.001+05:30

There are 3 unsorted arrays with negative and positive numbers. Find 3 numbers one from each array such that their sum total is 0.
e.g. A, B, C are three arrays
then A[i] + B[j] + C[k] = 0