Apurva
BAN USER- 0of 0 votes
AnswersYou are given a linked list. Apart from the normal "Next" pointer, there is one more pointer(random ptr) in each node which points to some random node of the list. How will you create a clone of such a list? (In less than O(n^2))
- Apurva in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures
Can be done in linear time. Use 2 pointer- 1 would move from top to bottom and other from left to right. Compare the elements pointed by 2 ptrs, push the smaller elt in the output array and increment this prt. I tried to implement it in Java. Below is the code:
public class SortMatrix {
public static void main(String[] args)
{
int[][] input = new int[][] {{5,10,11,12},{6,16,26,27},{7,22,27,36},{8,23,38,43}};
int[] op = sortMatrix(input);
{
for(int i:op)
{
System.out.print(i +", ");
}
}
}
public static int[] sortMatrix(int [][] collection)
{
int numOfColls = collection.length;
int numOfRows = collection[0].length;
int[] output = new int[numOfColls*numOfRows];
int a = 1;
int b = 0;
int c = 0;
int d = 1;
int opctr = 0;
output[0] = collection[0][0];
while(++opctr<output.length)
{
if(a==c && b==d) //both the ptr ponting to the same elt
{
output[opctr] = collection[a][b];
a++;
d++;
}
else if(collection[a][b]<collection[c][d])
{
output[opctr] = collection[a][b];
a++;
}
else
{
output[opctr] = collection[c][d];
d++;
}
if(a==numOfColls)
{
a = c;
b++;
}
if(d==numOfRows)
{
d = b;
c++;
}
}
return output;
}
}
Sorry to hear that. How did u come to know that u r rejected? Did they contact you? Actually my brother has appeared for interviews with Amazon and is still waiting for results from last 2 weeks. He is not sure whether they will tell the result in case if he is not selected. Just wanted to know how could you know ?
- Apurva January 18, 2012@Suman: Use elements in the array as keys. In first pass, for all the keys, set value = 1 (or you may increment this value if you encounter the same no. again in the array). In the second pass for each element 'elt' in array check whether there exists a value for key = (sum-elt). If there is one value then output 'elt' and "sum-elt" else move ahead. A little care must be taken in case of duplicates, still the logic remains the same. However, as I have mentioned above, this solution is good only if we want pairs of 2 elements. If we want a subset whose sum is equal to given value, we'll have to use dynamic programming.
- Apurva January 03, 2012A "Pair" always contain 2 elements. I am not sure whether you want the set of all pairs (pairs of 2 elements ofcourse) or you want the set of sets (may contain 2 or more elements). Because the solution of first case i.e., finding pairs that sum up to a certain value is trivial and this problem can be solved in O(n^2). In fact it can be solved in O(n) using hash table.
- Apurva January 03, 2012
- Apurva August 01, 2014