jaguar - 2 months ago 15

Java Question

I am stuck on this problem. My code passes all the testcases given in the example but there is some error in the code. Kindly point out the error.

Problem Statement (https://www.hackerearth.com/problem/algorithm/remove-friends-5)

After getting her PhD, Christie has become a celebrity at her university, and her facebook profile is full of friend requests. Being the nice girl she is, Christie has accepted all the requests.

Now Kuldeep is jealous of all the attention she is getting from other guys, so he asks her to delete some of the guys from her friend list.

To avoid a 'scene', Christie decides to remove some friends from her friend list, since she knows the popularity of each of the friend she has, she uses the following algorithm to delete a friend.

Algorithm Delete(Friend):

`DeleteFriend=false`

for i = 1 to Friend.length-1

if (Friend[i].popularity < Friend[i+1].popularity)

delete i th friend

DeleteFriend=true

break

if(DeleteFriend == false)

delete the last friend

Input:

First line contains T number of test cases. First line of each test case contains N, the number of friends Christie currently has and K ,the number of friends Christie decides to delete. Next lines contains popularity of her friends separated by space.

Output:

For each test case print N-K numbers which represent popularity of Christie friend's after deleting K friends.

NOTE

Order of friends after deleting exactly K friends should be maintained as given in input.

My Solution

`class TestClass {`

static class Node

{

int data;

Node next;

Node(int d)

{

data = d;

next = null;

}}

static Node head = null;

public static void main(String args[] ) throws Exception {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

String line = br.readLine();

int cases = Integer.parseInt(line);

for (int i = 0; i < cases; i++) {

line = br.readLine();

int friends = Integer.parseInt(line);

line = br.readLine();

int delete = Integer.parseInt(line);

head = null;

Node p =null;

for(int j=0;j < friends;j++){

line = br.readLine();

int temp = Integer.parseInt(line);

if(head == null){

head = new Node(temp);

p = head;

}

else{

Node q = new Node(temp);

p.next = q;

p = q;

}}

delete_friend(head , delete);

print_list(head);

}}

static void delete_friend(Node h, int delete){

Node p = head;

Node q = null;

int flag = 0;

for (int x = 1; x<=delete;x++){

p = head;

flag = 0;

q = p.next;

while(p.next != null){

q = p.next;

if(p.data < q.data){

p.data = q.data;

p.next = q.next;

flag=1;

p = head;

break;

}

if (flag == 0 && q.next == null){

if (p.data >= q.data) {

p.next = null;

break;

}}

p = p.next;

}}}

static void print_list(Node head){

Node tnode = head;

while (tnode != null)

{

System.out.print(tnode.data+" ");

tnode = tnode.next;

}

System.out.println();

}}

Answer

The way you read the input data is flawed: your implementation assumes one integer per line, but this doesn't match the problem description:

First line of each test case contains N, the number of friends Christie currently has and K ,the number of friends Christie decides to delete. Next lines contains popularity of her friends separated by space.

Instead of using a `BufferedReader`

,
I suggest to try using a `Scanner`

instead, it's simpler,
something like this:

```
Scanner scanner = new Scanner(System.in);
int t = scanner.nextInt();
for (int i = 0; i < t; i++) {
int friendsNum = scanner.nextInt();
int toDeleteNum = scanner.nextInt();
// ...
for (int j = 0; j < friendsNum; j++) {
int current = scanner.nextInt();
// ...
}
// ...
}
```

After you fix the input parsing, some of the tests will pass.

But many of them will still fail, due to a different problem, *time limit exceeded*.
That's because your algorithm is not efficient enough.
In the worst case, for each friend to delete, it will iterate until the end of the list of friends.

A different algorithm is possible:

- For each friend
- While we still need to delete more friends, and the current friend is more popular than the previous, delete the previous
- Add current friend to stack

- While we still need to delete more friends, remove the last from the stack

Here's the meat of it:

```
for (int j = 0; j < friendsNum; j++) {
int current = scanner.nextInt();
while (deleted < toDeleteNum && !stack.isEmpty() && stack.peek() < current) {
stack.pop();
deleted++;
}
stack.push(current);
}
while (deleted < toDeleteNum) {
stack.pop();
deleted++;
}
```

Source (Stackoverflow)

Comments