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