Solution for a problem!

help
, , ,
1

So I got a problem in a placement coding test, and I couldn’t solve it! I couldn’t find that particular problem on the internet, but I have an idea as to how to approach it, but I can’t code it! Here is the problem.

There is a list of unique n natural numbers in a particular order.
For every number Ni a card is made with two numbers written on it, one is the number before Ni i.e. Ni-1 and another is the number after Ni i.e. Ni+1.
For N1 and Nn, the corresponding cards are written with zeros, i.e. (0, N2) and (Nn-1,0).
You will have to print the numbers in the list in the correct order.

INPUT
The first line is a single integer n, denoting the number of numbers in the list.
Next n lines contain a pair of integers denoting the numbers written on the n cards.

OUTPUT
A single line containing n space-separated numbers.

Eg.

INPUT

3
0 102
102 0
101 103

OUTPUT

101 102 103

INPUT

4
0 2
2 4
1 3
3 0

OUTPUT

1 2 3 4

One feature I noticed is, the first and last numbers in the list are stated only once each, while all the other ones are stated twice every time in the input. It is like a graph problem, in this case, the graph is a single line with no branches!

Thanks in advance.

2

If you get an input as (0,X) this implies X=N2.
So, the first element of your output should be X - 1 which is N1

If you get an input as (X,0) this implies X=Nn-1.
So, the last element of your output should be X+1 which is Nn

So, you should output all the natural numbers from N1 to Nn (both inclusive)

3

I think @rajduino is actually referring Ni-1 as N[i-1] and Ni+1 as N[i+1]

4

You can get the first number(and last number) easily just by seeing the frequency of each number.
Third number of list is attached to first number , fifth number is attached to third number and so on. So you have completed the list with odd indices.
For even indices, you can determine second element easily(by checking which element is attached to 0) and thereafter you can determine 4th element (as it is attached with second element) and then 6th element(which is attached to 4th element) and so on.
So you can determine the whole list in this way.

5

Yeah, I understand this solution, this would have a complexity of about n², is there no other way with lower complexity!?

6

It has complexity of nlogn .You can make vector of pairs and sort them . Then searching for any number will take logn time . So complexity will be nlogn