Find union of two sets in O(1)

Use bit-map

Palindrome in LinkedList

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

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

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!

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

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

(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

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

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

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?

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

Team Photo Problem

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

Find out if there is cycle in a given graph?

Knapsack Problem Variation

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

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 !

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

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

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

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

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

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)

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

Find nth fibonacci number

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

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

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

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

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

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

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

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

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

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

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

Implementation of an efficient MRU Cache in Java

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

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

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

Find if the given integer is even or odd

Use of division is not permissible.

Bit Twiddling

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

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

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

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

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

(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

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

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

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

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

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

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

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

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

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