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.