Remove friends problem

[iamadeveloperinsg]

how to solve this linked list problem with javascript?
i'm getting time limit exceeded


https://www.hackerearth.com/practic...practice-problems/algorithm/remove-friends-5/

 

[davidktw]

how to solve this linked list problem with javascript?
i'm getting time limit exceeded


https://www.hackerearth.com/practic...practice-problems/algorithm/remove-friends-5/

Good question!

Here is the Java codes, you should adapt it to your Javascript.

Before you look at the result. You will want to consider a doubly linked list instead. I wonder if a Singly link list works. Actually an 2D array might works too.

Spoiler

import java.util.*;
import java.io.IOException;

class TestClass {
	
	static class Node {
		int i;
		Node n, p = null;
	}
	
        //Scanner is SLOW...
	static int getInt() throws IOException {
		boolean found = false;
		int num = 0;
		while (true) {
			int b = System.in.read();
			if (b >= '0' && b <= '9') {
				num = num * 10 + b - '0';
				found = true;
			}
			else {
				if (found) break;
			}
		}
		return num;
	}
	
	static void printlist(Node r) {
		System.out.print(">>>>>> ");
		while (r != null) {
			System.out.print(r.i + " ");
			r = r.n;
		}
		System.out.println();
	}
	
	public static void main(String args[] ) throws Exception {

		int noOfTestcases = getInt();
		
		for (int i = 0; i < noOfTestcases; i++) {
			
			// read input
			int noOfFrds	  = getInt();
			int noOfFrdsToDel = getInt();
			
			// read in all friends
			Node frdsPopularity = new Node(); //root
			Node c			= frdsPopularity;
			for (int j = 0; j < noOfFrds; j++) {
				c.n = new Node();
				c.n.i = (byte)getInt();
				c.n.p = c;
				c = c.n;
			}
	   
			// perform deletion
			int deleted = 0;
			for (c = frdsPopularity;
			     deleted < noOfFrdsToDel && c.n != null && c.n.n != null;) {
			     
			     //printlist(frdsPopularity);
				  
				// perform comparison and removal
				if (c.n.i < c.n.n.i) {
					deleted++;
					Node d = c.n;
					c.n = d.n;
					d.n.p = c;
					if (c.p != null) c = c.p;
					d.p = d.n = null;
				}
				else {
					c = c.n;
				}
			}
			  
			for (c = frdsPopularity.n; c != null; c = c.n) {
				System.out.print(c.i);
				if (c.n != null)
					System.out.print(" ");
			}
			System.out.println();
		}
	}
}

An optimised version (1)

Spoiler

import java.util.*;
import java.io.*;

class TestClass {
	
	static int getInt() throws IOException {
		boolean found = false;
		int num = 0;
		while (true) {
			int b = System.in.read();
			if (b >= '0' && b <= '9') {
				num = num * 10 + b - '0';
				found = true;
			}
			else {
				if (found) break;
			}
		}
		return num;
	}
	
	public static void main(String args[] ) throws Exception {

		int noOfTestcases = getInt();
		
		StringBuilder s = new StringBuilder();
		
		while (noOfTestcases > 0) {
			noOfTestcases--;
			
			// read input
			int noOfFrds	  = getInt();
			int noOfFrdsToDel = getInt();
			
			// read in all friends
			byte[] arr = new byte[noOfFrds];
			int[] next = new int[noOfFrds];
			int[] prev = new int[noOfFrds];
			for (int j = 0; j < noOfFrds; j++) {
				arr[j]  = (byte)getInt();
				prev[j] = j - 1;
				next[j] = j + 1;
			}
			next[noOfFrds - 1] = -1;
	   
			// perform deletion
			int root    = 0;
			int c       = 0;
			while (noOfFrdsToDel > 0) {
			
				int n = next[c];
				  
				// perform comparison and removal
				if (arr[c] >= arr[n]) {
					c = n;
				}
				else {
					noOfFrdsToDel--;
					int p = prev[c];
					if (p >= 0) {
						next[p] = n;
						prev[n] = p;
						c = p;
					}
					else {
						root = c = n;
						prev[c] = -1;
						
					}				
				}
			}
			 
			for (c = root; c >= 0; c = next[c]) {
				s.append(arr[c]).append(' ');
			}
			s.append("\n");
		}
		
		System.out.println(s);
	}
}

 

[davidktw]

Off my head, I think the approach of a singly inked list is using a Stack. That could be a very optimised solution. Though I will need to do some testing

Okay. There you go, you can implement your stack using a linked list, but I prefer just using a simple 1D array.

Spoiler

import java.util.*;
import java.io.*;

class TestClass {

	static BufferedInputStream r = new BufferedInputStream(System.in);
	
	static int getInt() throws IOException {
		boolean found = false;
		int num = 0;
		while (true) {
			int b = r.read();
			if (b >= '0' && b <= '9') {
				num = b - '0' + num * 10;
				found = true;
			}
			else {
				if (found) break;
			}
		}
		return num;
	}
	
	public static void main(String args[] ) throws Exception {

		int noOfTestcases = getInt();
		
		StringBuilder s = new StringBuilder();
		
		int[] stack = null;
		int t       = 0;
		
		while (noOfTestcases-- > 0) {
			
			// read input
			int noOfFrds	   = getInt();
			int noOfFrdsToDel  = getInt();
			int frdsFound      = 0;
			
			if (stack == null || noOfFrds > stack.length)
				stack = new int[noOfFrds];
			t = 0;
	   
			while (noOfFrdsToDel > 0 && frdsFound < noOfFrds) {
			
				int p = getInt();
				++frdsFound;
				  
				if (t == 0) { //empty stack
				    stack[t] = p;
				}
				else {
				    while (noOfFrdsToDel > 0 && t > 0 && stack[t - 1] < p) {
				        t--;
				        noOfFrdsToDel--;
				    }
				    stack[t] = p;
				}
				++t;
			}
			
			for (int i = 0; i < t; i++)
			    s.append(stack[i]).append(' ');
			for (int i = noOfFrds - frdsFound; i > 0; i--)
			    s.append(getInt()).append(' ');
			s.append("\n");
		}
		
		System.out.println(s);
	}
}