CareerCup

*x -> delete star -> RPN

Not less than O(n).

less than O(n). Your algorithm is O(nlgn).

I assume the dictionary is given with trie data structure.
Backtrack/BFS/DFS would give you the best result. You go from one state to another state if there is a letter that can be appended to the current string.

O(n^3)

This question is not about how to change infix to postfix! Input can be any random string of xs and *s! What is the minimum number of delete, replace, and insert to make the given string postfix!

Yes it was asked in the programming interview. I had two hours, and I failed :D

I see. Well, I have written my idea in the next comment. You can read it. I had the same idea as your idea, but my friend revised it to a dynamic programming approach which works way better.

You can find your answer here:

slacksite.com/other/ftp.html

INNER JOIN: Returns all rows when there is at least one match in BOTH tables
LEFT JOIN: Return all rows from the left table, and the matched rows from the right table
RIGHT JOIN: Return all rows from the right table, and the matched rows from the left table
FULL JOIN: Return all rows when there is a match in ONE of the tables

From W3Schools website.

He is right. The TTL starts with 1. Until packets are dropped, it increases TTL. Eventually the destination is found with TTL = x.

wikipedia: The raw maximum transfer rate of 3 1⁄2-inch HD floppy drives and interfaces, disregarding overheads, is as much as 1000 kilobits/s.

1000Kb = 125KB

wikipedia: 3 1⁄2-inch HD Capacity 1.44 MB (2.0 MB unformatted)

1.44MB/125KB = 1.44 * 1024 (M = 1024K not 1000K) / 125 = 11.80s approximately 12s

by adding int[] parent, you can run BFS from the start. Set all nodes' parent to -infinity, and start to 0. Whenever you visit a node because it is adjacent to another already visited node and its parent is not set, set the parent to the current node.

At the end, by finding end's parent, end's parent's parent's , .... you have the path backward. Reverse it.

One of my friends helped me to solve this problem. The idea is dynamic programming!

Step A: for having RPN, it is enough to have (RPN)(RPN)*, so find the best K where (0,1,...K),(K+1,....,N-1)* is RPN (N is the length of the string).

If the last character is x, you can delete it and find the best answer for (0,....,N-1)
or replace it with an asterisk and go to Step A,
or add an asterisk to the end and find the best K where (1,0,...K),(K+1,....N)* is RPN.

I have written the code for it and works perfectly even for the string size 200. Here is the code:

import java.util.ArrayList;
import java.util.Scanner;


// Used dynamic programming.
// Step A: for having RPN, it is enough to have (RPN)(RPN)*, so find the best K where (0,1,...K),(K+1,....,N-1)* is RPN (N is the length of the string).
// if the last character is x, you can delete it and find the best K for (0,1,...K),(K+1,....N-2)*
// or replace it with an asterisk and go to Step A,  
// or add an asterisk to the end and find the best K where (1,0,...K),(K+1,....N)* is RPN.
public class Solution2 {
	ArrayList<String> strs = new ArrayList<String>();
	int[][] valueArray;
	
	public static void main(String[] args) {
		Solution2 solution = new Solution2();
		Scanner scanner = new Scanner(System.in);
		int num = Integer.parseInt(scanner.nextLine());
		for (int i = 0; i < num; i++) {
			solution.strs.add(scanner.nextLine());
		}
		for (int i = 0; i < num; i++) {
			solution.makeEmptyArray(i);
			int res = solution.solve(i);
			System.out.println(res);	
		}
		
	}

	private int solve(int index) {
		return solve(strs.get(index),0,this.strs.get(index).length()-1);
		
	}
	private int solve(String str, int begin, int end){
		//already this branch is solved!
		if(valueArray[begin][end] != Integer.MAX_VALUE){
			return valueArray[begin][end];
		}
		
		// length 1
		if( begin == end ){
			if(str.charAt(begin) == '*'){
				valueArray[begin][end] = 1;
				return valueArray[begin][end];
			}else{
				valueArray[begin][end] = 0;
				return valueArray[begin][end];
			}
		}
		
		// length 2
		if(begin == end -1){
			String temp = str.substring(begin, end+1);
			if(temp.equals("xx")){
				valueArray[begin][end] = 1;
				return valueArray[begin][end];
			}
			if(temp.equals("x*")){
				valueArray[begin][end] = 1;
				return valueArray[begin][end];
			}
			if(temp.equals("**")){
				valueArray[begin][end] = 2;
				return valueArray[begin][end];
			}
			if(temp.equals("*x")){
				valueArray[begin][end] = 1;
				return valueArray[begin][end];
			}
			System.out.println("Error in solve");
			return -1;
		}
		
		// find the best k where solve(begin,k) + solve(k+1,end-1) is the best
		if(str.charAt(end) == '*'){
			int min = Integer.MAX_VALUE;
			for (int i = begin; i < end-1; i++) {
				int temp = solve(str,begin,i) + solve(str,i+1,end-1);
				if(temp < min)
					min = temp;
			}	
			valueArray[begin][end] = min;
			return min;
		}
		else{ // str.charAt(end)='x'
			int min = Integer.MAX_VALUE;
			
			//replace it with *: similar to the previous, except that there is the cost of 1 for replacement of x with *.
			for (int i = begin; i < end-1; i++) {
				int temp = solve(str,begin,i) + solve(str,i+1,end-1) + 1;
				if(temp < min)
					min = temp;
			}
			
			//insert, insert an asterisk at the end and try to find the best k where solve(begin,k) + solve(k+1,end) is the best
			//since an asterisk is added, the last character has to be involved in the following calculations.
			for (int i = begin; i < end; i++) {
				int temp = solve(str,begin,i) + solve(str,i+1,end) + 1;
				if(temp < min)
					min = temp;
			}
			
			//delete x and solve the problem for the rest.
			int temp = solve(str,begin,end-1) + 1;
			if(temp < min)
				min = temp;
			
			valueArray[begin][end] = min;
			return min;
		}
		
		
	}

	public void makeEmptyArray(int index) {
		valueArray = new int[strs.get(index).length()][strs.get(index).length()];
		for (int i = 0; i < valueArray.length; i++) {
			for (int j = 0; j < valueArray.length; j++) {
				valueArray[i][j] = Integer.MAX_VALUE;
			}
			
		}
	}
	
	
}

Would you please explain how your code works? Also please let me know if it works fast enough for length 100.

I almost did the same thing, but when it comes to 75 or 100, this way is too slow. Time limit was 5 seconds I guess (They did not tell me what was the time limit, but I could see my program fails after almost 5 seconds).

Making all valid RPN from right to left using backtrack is exponential....
I guess this question was one of the hard ones.

1) Yes, they are all the same operand. *'s are all the same operations!
2) There is no unique postfix RPN form. Your algorithm should find the closest one.
All inputs can be transformed into RPN: for example delete all x's and *'s and insert a x which costs (String's length + 1) is one way to make RPN from all inputs.

The challenge is to find the minimum number of insertion, deletion, and replacements needed to make the input ًcorrect postfix form.

I guess you misunderstood. The given string is neither postfix nor infix. It is just a random string which contains x's and *'s. Your algorithm should take that and then make it postfix using delete, replace, and insert. The minimum number of these operations is the output of the program.

K is an integer and (0< !K) returns boolean. !K is equal to zero for all non zero values and is one when K is zero. Therefore, !-7 is 0 and (0<0) is false. False in C is 0 and true is a non zero value. As a result, the output has to be zero since 0<0 is false.

DFS from only one vertex! If there is no back edge and all of the vertices become black, the graph is tree.!

There is a way to change a recursive method to a non-recursive method by stack!

Not considering that, I suggest this:

Node n = extractMin(root);
	while(n != null){
		System.out.println(n.value);
		n = successor(n);
	}

If you need to know how extractMin() and successor() works, let me know.

Calculate distance of each point from the origin. Sort them based on the distance. Return first n numbers.

public void inorder(Node n){
	if(n.left != null){
		inorder(n.left);
	}
	System.out.printlin(n.value);
	if(n.right != null){
		inorder(n.right);
	}
}

I used a combination of backtrack and DFS idea :

public class WordMatrix {
	private char[][] board = { 
			{ 'a', 'b', 'c', 'd' }, 
			{ 'e', 'f', 'g', 'h' },
			{ 'i', 'j', 'a', 'b' }, 
			{ 'm', 'n', 'c', 'c' },
	};

	String word = "abc";

	public void search() {
		// from each cell of the matrix, search for the pattern!
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[i].length; j++) {
				int traverse[][] = initializeTraverseBoard();
				search(0, i, j, traverse);
			}
		}
	}

	private void search(int depth, int row, int column, int[][] traverse) {
		if (board[row][column] != word.charAt(depth))
			return;
		
		depth++;
		if (depth == word.length()) { // if the word has been found
			traverse[row][column] = depth;
			printCoordinates(traverse);
			traverse[row][column] = 0;
			System.out.println();
			// System.out.println(word);
			return;
		} else { // if the word has not been found, but a suffix is found, go to its neighbours which are not discovered yet!
			traverse[row][column] = depth;
			if ((row - 1) >= 0 && (column - 1) >= 0
					&& traverse[row - 1][column - 1] == 0) {
				search(depth, row - 1, column - 1, traverse);
			}
			if (column - 1 >= 0 && traverse[row][column - 1] == 0) {
				search(depth, row, column - 1, traverse);
			}
			if (row + 1 < traverse.length && column - 1 >= 0
					&& traverse[row + 1][column - 1] == 0) {
				search(depth, row + 1, column - 1, traverse);
			}
			if (row + 1 < traverse.length && traverse[row + 1][column] == 0) {
				search(depth, row + 1, column, traverse);
			}
			if (row + 1 < traverse.length && column + 1 < traverse.length
					&& traverse[row + 1][column + 1] == 0) {
				search(depth, row + 1, column + 1, traverse);
			}
			if (column + 1 < traverse.length
					&& traverse[row][column + 1] == 0) {
				search(depth, row, column + 1, traverse);
			}
			if (column + 1 < traverse.length && row - 1 >= 0
					&& traverse[row - 1][column + 1] == 0) {
				search(depth, row - 1, column + 1, traverse);
			}
			if (row - 1 >= 0 && traverse[row - 1][column] == 0) {
				search(depth, row - 1, column, traverse);
			}
			traverse[row][column] = 0;
		}

	}

	private void printCoordinates(int[][] boolBoard) {
		int start = 1;
		int end = word.length()+1;

		for (int count = start; count < end; count++) {
			for (int i = 0; i < boolBoard.length; i++) {
				boolean isFound = false;
				for (int j = 0; j < boolBoard[i].length; j++) {
					if(boolBoard[i][j] == count){
						System.out.print("(" + i + "," + j + ") ");
						isFound = true;
						break;
					}
				}
				if(isFound)break;
			}
		}
	}

	private int[][] initializeTraverseBoard() {
		int[][] res = new int[board.length][board.length];
		for (int i = 0; i < res.length; i++) {
			for (int j = 0; j < res[i].length; j++) {
				res[i][j] = 0;
			}
		}
		return res;
	}

	public static void main(String[] args) {
		WordMatrix wm = new WordMatrix();
		// wm.word = "aba";
		wm.search();
	}
}

Without the built-in split function, I would solve it recursively:

import java.util.ArrayList;

public class StringReverse {
	String str = "";

	public StringReverse(String str) {
		this.str = str;
	}
	
	//first reverse the string and save in an arraylist.
	//use the string builder to append them altogether.
	public String reverse(){
		ArrayList<String> res = reverseAndSplit(this.str);
		StringBuilder sb = new StringBuilder();
		
		for (int i = 0; i < res.size(); i++) {
			sb.append(res.get(i) + " ");
		}
		return sb.toString();
	}

	//Find the first space and save the word before that in beforeSpace.
	//Reverse the string after the first space recursively.
	//append beforeSpace to the end of array.
	public ArrayList<String> reverseAndSplit(String str) {
		str = str.trim();
		if (str.indexOf(' ') == -1) {
			ArrayList<String> res = new ArrayList<String>();
			res.add(str);
			return res;
		} else {
			String beforeSpace = str.substring(0, str.indexOf(' '));
			ArrayList<String> res = reverseAndSplit(str.substring(str
					.indexOf(' ') + 1));
			res.add(beforeSpace);
			return res;
		}
	}

	public static void main(String[] args) {
		StringReverse sr = new StringReverse("I am in the river");
		String str = sr.reverse();
		System.out.println(str);
	}

}

public class StringReverse {
	String str = "";
	public StringReverse(String str){
		this.str = str;
	}
	public String reverse() {
		String[] strings = str.split(" ");
		StringBuilder sb = new StringBuilder();
		for (int i = strings.length-1; i >=0 ; i--) {
			sb.append(strings[i] + " ");
		}
		return sb.toString();
	}
	
	public static void main(String[] args) {
		StringReverse sr = new StringReverse("I am in the river");
		String str = sr.reverse();
		System.out.println(str);
	}
	
}

Your algorithm is correct. In your algorithm, the worst case scenario which the actual list is sorted and your are looking for the maximum takes O(n^2). The selection algorithm takes O(n), although it is much harder to implement.

We have 2 choices for choosing a coin or not choosing it: 2^8

The situation that (3paisa is chosen and 1paisa and 2 paisa is not chosen) or (3paisa is not chosen and 1 paisa and 2 paisa is chosen) is counted twice: each situation: 2^5 ( since 1paisa, 2paisa, and 3 paisa does not have the choice. they are already set!)

2^8 - 2^5 is the answer!

[2,10]
[3,7]

Your answer is Range(3,7) which is wrong.

import java.util.ArrayList;
import java.util.Iterator;

public class Problem<E> implements Iterator<E> {
	Iterator<Iterator<E>> iter;
	Iterator<E> iter2;

	Problem(Iterator<Iterator<E>> iter) {
		this.iter = iter;
		if (iter.hasNext())
			this.iter2 = iter.next();
	}

	@Override
	public boolean hasNext() {
		if (iter2 != null) {
			if (iter2.hasNext())
				return true;
		}
		while (iter.hasNext()) {
			iter2 = iter.next();
			if (iter2.hasNext())
				return true;
		}
		return false;
	}

	@Override
	public E next() {
		if (iter2 != null) {
			if (iter2.hasNext())
				return iter2.next();
		}
		if (iter.hasNext()) {
			iter2 = iter.next();
			return this.next();
		}
		return null;
	}

	@Override
	public void remove() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		// I am making an iterator of iterator here.
		ArrayList<ArrayList<Integer>> integers = new ArrayList<ArrayList<Integer>>();
		for (int i = 0; i < 10; i++) {
			ArrayList<Integer> temp = new ArrayList<Integer>();
			for (int j = 0; j < i; j++) {
				temp.add(i);
			}
			integers.add(temp);
		}
		ArrayList<Iterator<Integer>> iter = new ArrayList<Iterator<Integer>>();
		for (int i = 0; i < integers.size(); i++) {
			iter.add(integers.get(i).iterator());
		}
		Iterator<Iterator<Integer>> iterator = iter.iterator();

		// Now I pass the iterator of iterator to the class problem. Problem is
		// actually an iterator since I implement Iterator<Integer>
		@SuppressWarnings({ "rawtypes", "unchecked" })
		Problem p = new Problem(iterator);
		while (p.hasNext()) {
			System.out.println(p.next());
		}
	}

}

How do you guarantee that a number between (stopNum_i,startNum_i) and a number between (stopNum_i +1, startNum_i +1) is not the range we are looking for?

Well, in that case, keeping only one class to manage everything is inevitable. If you know the whole hierarchy you can make all classes and do what I did. For now I propose this method to handle the scenario that you do not know the whole hierarchy.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace MS_Question
{
    class Program
    {
        Human ceo;
        Program()
        {
            Human w1 = new Human(Human.humanType.EM, Human.humanType.Nothing); w1.name = "w1";
            Human w2 = new Human(Human.humanType.EM, Human.humanType.Nothing); w1.name = "w2";
            Human w3 = new Human(Human.humanType.EM, Human.humanType.Nothing); w1.name = "w3";
            Human w4 = new Human(Human.humanType.EM, Human.humanType.Nothing); w1.name = "w4";
            Human w5 = new Human(Human.humanType.EM, Human.humanType.Nothing); w1.name = "w5";
            Human w6 = new Human(Human.humanType.EM, Human.humanType.Nothing); w1.name = "w6";
            Human w7 = new Human(Human.humanType.EM, Human.humanType.Nothing); w1.name = "w7";
            Human w8 = new Human(Human.humanType.EM, Human.humanType.Nothing); w1.name = "w8";

            Human gm1 = new Human(Human.humanType.GM, Human.humanType.EM); gm1.name = "gm1";
            gm1.directUnderneath.Add(w1); gm1.directUnderneath.Add(w2);
            Human gm2 = new Human(Human.humanType.GM, Human.humanType.EM); gm2.name = "gm2";
            gm2.directUnderneath.Add(w3); gm2.directUnderneath.Add(w4);
            Human gm3 = new Human(Human.humanType.GM, Human.humanType.EM); gm3.name = "gm3";
            gm3.directUnderneath.Add(w5); gm3.directUnderneath.Add(w6);
            Human gm4 = new Human(Human.humanType.GM, Human.humanType.EM); gm4.name = "gm4";
            gm4.directUnderneath.Add(w7); gm4.directUnderneath.Add(w8);

            Human vp1 = new Human(Human.humanType.VP, Human.humanType.GM); vp1.name = "vp1";
            vp1.directUnderneath.Add(gm1); vp1.directUnderneath.Add(gm2);
            Human vp2 = new Human(Human.humanType.VP, Human.humanType.GM); vp2.name = "vp2";
            vp2.directUnderneath.Add(gm3); vp2.directUnderneath.Add(gm4);

            Human ceo1 = new Human(Human.humanType.CEO, Human.humanType.VP); ceo1.name = "ceo1";
            ceo1.directUnderneath.Add(vp1); ceo1.directUnderneath.Add(vp2);
            this.ceo = ceo1;
        }

        public Human findWorker(Human h, String name){
            
            
                if(h.name.Equals(name))
                    return h;
                else
                {
                    
                    IEnumerable<Human> res = h.directUnderneath.Select(i => i).Where( i => i.name.Equals(name));
                    foreach (Human human in res)
                    {
                        return human;
                    }
                    if (h.directUnderneath.Count != 0)
                    {
                        foreach (Human human in h.directUnderneath)
                        {
                            return findWorker(human, name);
                        }
                    }
                }
                    
            return null;
        }

        static void Main(string[] args)
        {
            Program p = new Program();
            Human h = p.findWorker(p.ceo, "w8");
            if (h != null)
            {
                Console.WriteLine(h.name + " Exists.");
            }
            else
            {
                Console.WriteLine("No such person exists.");
            }
            Console.ReadKey();
        }
    }
    class Human{
        public enum humanType {CEO,VP,GM,EM,Nothing};
        public humanType myType;
        public humanType myArrayType;

        public string name="";
        public List<Human> directUnderneath = new List<Human>();
        public Human()
        {

        }
        public Human(humanType mine, humanType myarr)
        {
            this.myType = mine;
            this.myArrayType = myarr;
        }
    }
    
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace MS_Question
{
    class Program
    {
        CEO ceo;
        Program()
        {
            Employee w1 = new Employee(); w1.name = "w1";
            Employee w2 = new Employee(); w1.name = "w2";
            Employee w3 = new Employee(); w1.name = "w3";
            Employee w4 = new Employee(); w1.name = "w4";
            Employee w5 = new Employee(); w1.name = "w5";
            Employee w6 = new Employee(); w1.name = "w6";
            Employee w7 = new Employee(); w1.name = "w7";
            Employee w8 = new Employee(); w1.name = "w8";

            GM gm1 = new GM(); gm1.name = "gm1";
            gm1.workers.Add(w1); gm1.workers.Add(w2);
            GM gm2 = new GM(); gm2.name = "gm2";
            gm2.workers.Add(w3); gm2.workers.Add(w4);
            GM gm3 = new GM(); gm3.name = "gm3";
            gm3.workers.Add(w5); gm3.workers.Add(w6);
            GM gm4 = new GM(); gm4.name = "gm4";
            gm4.workers.Add(w7); gm4.workers.Add(w8);

            VP vp1 = new VP(); vp1.name = "vp1";
            vp1.mgs.Add(gm1); vp1.mgs.Add(gm2);
            VP vp2 = new VP(); vp2.name = "vp2";
            vp2.mgs.Add(gm3); vp2.mgs.Add(gm4);

            CEO ceo1 = new CEO(); ceo1.name = "ceo1";
            ceo1.vps.Add(vp1); ceo1.vps.Add(vp2);
            this.ceo = ceo1;
        }

        public Human findWorker(Human h, String name){
            if (h is CEO)
            {
                if(h.name.Equals(name))
                    return h;
                else
                {
                    
                    IEnumerable<VP> res = ((CEO)h).vps.Select(i => i).Where( i => i.name.Equals(name));
                    foreach (VP vp in res)
                    {
                        return vp;
                    }
                    foreach (VP v in ((CEO)h).vps)
                    {
                        return findWorker(v, name);
                    }
                }
                    
            }
            if (h is VP)
            {
                IEnumerable<GM> res = ((VP)h).mgs.Select(i => i).Where(i => i.name.Equals(name));
                foreach (GM mg in res)
                {
                    return mg;
                }
                foreach (GM m in ((VP)h).mgs)
                {
                    return findWorker(m, name);
                }
            }

            if (h is GM)
            {
                IEnumerable<Employee> res = ((GM)h).workers.Select(i => i).Where(i => i.name.Equals(name));
                foreach(Employee w in res){
                    return w;
                }
            }

            return null;
        }

        static void Main(string[] args)
        {
            Program p = new Program();
            Human h = p.findWorker(p.ceo, "ceo2");
            if (h != null)
            {
                Console.WriteLine(h.name + " Exists.");
            }
            else
            {
                Console.WriteLine("No such person exists.");
            }
            Console.ReadKey();
        }
    }
    class Human{
        public string name="";
    }
    class CEO:Human
    {
        public List<VP> vps = new List<VP>();
    }
    class VP:Human
    {
        public List<GM> mgs = new List<GM>();
    }
    class GM:Human
    {
        public List<Employee> workers = new List<Employee>();
    }
    class Employee : Human
    {

    }
}

I used divide and conquer strategy and it works. Yet, there can be one improvement and that is optimizing the size of nums array.

import java.util.ArrayList;


public class Main {
	ArrayList<Integer[]> arrays;
	int[] nums;
	Range bestRange;
	
	public Main(ArrayList<Integer[]> arrays) {
		this.arrays = arrays;
	}

	private void solve() {
		int min = findMin(arrays);
		int max = findMax(arrays);
		nums = new int[max-min+1];
		for (int i = min; i <= max; i++) {
			nums[i-min] = i;
		}
		
		bestRange = setBestRange(0,nums.length-1);
		System.out.println(bestRange.min + "\t" + bestRange.max);
	}
	
	//divide and conquer
	private Range setBestRange( int first, int last) {
		
		if(first == last){
			Range r = new Range(nums[first],nums[first]);
			if(doesAllArraysHave(r)){
				return r;
			}else
				return null;
		}
		
		if(first == last -1){
			Range r = new Range(nums[first],nums[last]);
			if(doesAllArraysHave(r)){
				return r;
			}else
				return null;
		}
		
		if(doesAllArraysHave(new Range(nums[first],nums[last])) == false){
			return null;
		}
		
		int mid = (last - first) / 2 + first;
		Range firstRange = setBestRange(first, mid);
		Range secondRange = setBestRange(mid+1, last);
		int p = mid;
		int q = mid+1;
		
		Range combination = new Range(first,last);
		for (int i = mid; i >= first ; i--) {
			for (int j = mid+1; j <= last; j++) {
				Range temp = new Range(nums[i],nums[j]);
				if(doesAllArraysHave(temp) && temp.getRange() < combination.getRange()){
					combination = temp;
				}
			}
		}
		
		return minRangeofThree(firstRange, secondRange, combination);
		
	}
	
	// In the divide and conquer strategy, which division is better?
	public Range minRangeofThree(Range r1, Range r2, Range r3){
		if(r1 == null && r2==null && r3==null) return null;
		int r1GetRange = (r1 == null ? Integer.MAX_VALUE : r1.getRange());
		int r2GetRange = (r2 == null ? Integer.MAX_VALUE : r2.getRange());
		int r3GetRange = (r3 == null ? Integer.MAX_VALUE : r3.getRange());
		
		int min;
		if(r1GetRange < r2GetRange){
			min = r1GetRange;
		}else{
			min = r2GetRange;
		}
		
		if(r3GetRange < min){
			min = r3GetRange;
		}
		
		if(min == r1GetRange) return r1;
		if(min == r2GetRange) return r2;
		if(min == r3GetRange) return r3;
		return null;
	}

	private boolean doesAnArrayHave(Integer[] ints, Range r){
		for (int i = 0; i < ints.length; i++) {
			if( ints[i] >= r.min && ints[i] <= r.max)
				return true;
		}
		return false;
	}
	
	private boolean doesAllArraysHave(Range r){
		for (int i = 0; i < arrays.size(); i++) {
			if(!doesAnArrayHave(arrays.get(i), r))
				return false;
		}
		return true;
	}
	

	private int findMin(ArrayList<Integer[]> arrays) {
		int min = arrays.get(0)[0];
		for (int i = 0; i < arrays.size(); i++) {
			if(arrays.get(i)[0] < min)
				min = arrays.get(i)[0];
		}
		return min;
	}

	private int findMax(ArrayList<Integer[]> arrays) {
		int max = arrays.get(0)[arrays.get(0).length-1];
		for (int i = 0; i < arrays.size(); i++) {
			if(arrays.get(i)[arrays.get(i).length-1] > max)
				max = arrays.get(i)[arrays.get(i).length-1];
		}
		return max; 
	}
	

	public static void main(String[] args) {
		ArrayList<Integer[]> arrays = new ArrayList<Integer[]>();
		Integer arr1[] = new Integer[]{ 20,30,40,50};
		Integer arr2[] = new Integer[]{12,49,100};
		Integer arr3[] = new Integer[]{5,15,100};
		
		arrays.add(arr1);
		arrays.add(arr2);
		arrays.add(arr3);
		
		Main m = new Main(arrays);
		m.solve();
	}
}

public class Test {
		//add this line
		public static int count = 0;
		public static void main(String [] args){
			printParenthesis(3);
		}
		public static void printParenthesis(int n){
			char buffer[] = new char[n*2];
			printP(buffer,0,n,0,0);
		}
		public static void printP(char buffer[], int index, int n, int open, int close){
			if(close == n){
				// change System.out.println(new String(buffer)); to the following line
				System.out.println(++count+"." + new String(buffer));
			}else{
				if(open > close){
					buffer[index] = ']';
					printP(buffer, index+1, n, open, close+1);
				}
				if(open < n ){
					buffer[index] = '[';
					printP(buffer,index+1,n,open+1,close);
				}
			}
		}
	}

I have to correct myself. It is not applicable since a[n] in array can be reached in O(1) while linked_list.get(n) is applicable in O(n). The good way maybe is to use toArray function before using the selection algorithm.

It is hard to provide the whole description of selection algorithm. The idea is to divide the whole array to subarrays of size 5. Then use insertion sort on them. pick the median of each. use the same strateghy for the medians to find the median of medians. use partition of quick sort and the pivot is the median of medians. Now if the median of median is the k-th element after the partition, return, otherwise based on k > median of medians position or k< median of medians, find the K-th biggest in either sides of the array.

import java.util.ArrayList;
import java.util.Iterator;


public class Problem {
	public static void main(String[] args) {
		ArrayList<ArrayList<Integer>> integers = new ArrayList<ArrayList<Integer>>();
		for (int i = 0; i < 10; i++) {
			ArrayList<Integer> temp = new ArrayList<Integer>();
			for (int j = 0; j < i; j++) {
				temp.add(i);
			}
			integers.add(temp);
		}
		ArrayList<Iterator<Integer>> iter = new ArrayList<Iterator<Integer>>();
		for (int i = 0; i < integers.size(); i++) {
			iter.add(integers.get(i).iterator());
		}
		Iterator<Iterator<Integer>> iterator = iter.iterator();
		
		ArrayList<Integer> arrInts = new ArrayList<Integer>();
		
		
		while(iterator.hasNext()){
			Iterator<Integer> i = iterator.next();
			while(i.hasNext()){
				int j = i.next();
				arrInts.add(j);
			}
		}
		
		
		for (int i = 0; i < arrInts.size(); i++) {
			System.out.println(arrInts.get(i));
		}
		
	}
}

public class AtoF {
	String str;
	float result;
	
	public AtoF(String s) throws Exception{
		this.str = s.trim();
		result = solve(str);
	}
	
	public float solve(String str) throws Exception{
		int indexOfE = str.indexOf('E');
		if(indexOfE == -1)
			indexOfE= str.indexOf('e');
		if(indexOfE == -1){
			return withoutE(str);
		}else{
			return (float) (withoutE(str.substring(0, indexOfE))*
					Math.pow(10, withoutE(str.substring(indexOfE+1))));
		}
	}
	

	private float withoutE(String s) throws Exception{
		if(s.charAt(0) == '-'){
			return -withoutE(s.substring(1));
		}
		int indexOfPeriod = s.indexOf('.');
		if(indexOfPeriod == -1){
			return makeInt(s);
		}else{
			float beforePeriod = makeInt(s.substring(0,indexOfPeriod));
			float afterPeriod = makeInt(s.substring(indexOfPeriod+1));
			float temp = afterPeriod;
			int countDigit = 0;
			while(temp > 10){
				countDigit ++;
				temp /=10;
			}
			countDigit++;
			
			return (float)(beforePeriod + Math.pow(10, -countDigit)*afterPeriod);
		}
		
	}
	

	private float makeInt(String s) throws Exception{
		if(s.length() == 0)
			return 0;
		float res = 0f;
		for (int i = 0; i < s.length(); i++) {
			// for example 234 = ((2*10)+3)*10+4;
			res = res*10 + makeDigit(s.charAt(i));
		}
		return res;
	}
	
	
	private float makeDigit(char charAt) throws Exception {
		switch(charAt){
		case '0':
			return 0;
		case '1':
			return 1;
		case '2':
			return 2;
		case '3':
			return 3;
		case '4':
			return 4;
		case '5':
			return 5;
		case '6':
			return 6;
		case '7':
			return 7;
		case '8':
			return 8;
		case '9':
			return 9;
		default:
			throw new Exception();
				
		}
	}

	public static void main(String[] args) throws Exception {
		AtoF a = new AtoF("3.2");
		System.out.println(a.result);
	}
}

I would use (LCS) longest common subsequence which is a dynamic programming approach. Its running time is s1.size*s2.size.

The idea is like this:
X = x_1 x_2 ... x_m
Y = y_1 y_2 ... y_n
if( x_m == y_n) then find LCS of x_(m-1) & y_(n-1) and concat x_m to it.
if( x_m != y_n) then find max LCS of { (x_m & y_(n-1)) , (x_(m-1) &y_n)

This program is fortunately working, though I spent a few hours writing it. To add readability to the code, I have added some comments.

The tricky part is when you want to delete a node which has two children (right and left) without having a child which has the same value as the current node has. First find the successor, then swap the node with its successor and after that delete the node ( which you are sure it has at most one child).

public class Tree {
	private Node root;
	
	public void insert(int x){
		Node n = new Node(x);
		this.insert(n);
	}
	public void insert(Node n){
		if(root == null){
			root = n;
			return;
		}else{
			this.insert(root,n);
		}
	}
	private void insert(Node curRoot, Node n){
		if(curRoot.value == n.value){
			Node temp = curRoot;
			while(temp.below!= null){
				temp = temp.below;
			}
			temp.below = n;
			n.parent = temp;
			return;
		}
		
		if(curRoot.value > n.value){
			if(curRoot.left != null){
				insert(curRoot.left,n);
				return;
			}else{
				curRoot.left = n;
				n.parent = curRoot;
				return;
			}
		}else{ // curRoot.value < n.value
			if(curRoot.right != null){
				insert(curRoot.right,n);
				return;
			}else{
				curRoot.right = n;
				n.parent = curRoot;
				return;
			}
		}
	}
	
	public void printRoot(){
		if(root != null)
			System.out.println("Root value: "+root.value);
		else
			System.err.println("Root is null.");
	}
	public void print(){
		if(root == null){
			System.out.println("No tree!");
		}
		else{
			print(root);
		}
	}
	private void print(Node n){
		if(n.left!= null){
			print(n.left);
		}
		
		//current node and all nodes with the equal value
		System.out.println(n.value);
		if(n.below != null){
			print(n.below);
		}
		
		if(n.right != null){
			print(n.right);
		}
	}
	// get the min Node in the subtree of cur (includes cur)
	// if two values are the least, it returns the parent!
	public Node getMin(Node cur){
		Node temp = cur;
		while(temp.left != null){
			temp = temp.left;
		}
		return temp;
	}
	
	// if there is a node with the same value below current node, that is the successor.
	// if there is a right child for current node, run the getMin() on the right node.
	// if there is not a right child, while this child is in the right side of its parent go upward. If you reach the situation that the parent's
	// left child is current node, return it. otherwise return null.
	public Node successor(Node cur){
		if(cur == null){
			System.err.println("Node is null in successor funtion!");
			return null;
		}
		
		if(cur.below != null){
			return cur.below;
		}
		
		if(cur.right != null){
			return getMin(cur.right);
		}else{
			Node temp = cur;
			while(temp.parent != null && temp.parent.right == temp){
				temp = temp.parent;
			}
			if(temp.parent == null){
				return null;
			}else{
				return temp.parent;
			}
		}
		
	}
	
	public void delete(Node n){
		System.out.println("I am gonna delete " + n.value);
		if(n.below != null){
			deleteIfBelowIsNotNull(n);
			return;
		}
		if(n.right == null && n.left == null){
			
			if(n.parent != null){
				if(n.parent.right == n)
					n.parent.right = null;
				else if(n.parent.left == n)
					n.parent.left = null;
				else if(n.parent.below == n)
					n.parent.below = null;
			}else{
				root = null;
			}
			n = null;
			return;
		}
		if(n.right == null || n.left == null){
			deleteWithOneChild(n);
			return;
		}
		
		if(n.right != null && n.left != null){
			deleteWithTwoChildren(n);
		}
		
	}
	private void deleteIfBelowIsNotNull(Node n){
		n.below.parent = n.parent;
		n.below.right = n.right;
		n.below.left = n.left;
		if(n.parent == null){ // n == root!
			root = n.below;
			n = null;
			return;
		}else if(n.parent.right == n){
			n.parent.right = n.below;
			n = null;
			return;
		}else if(n.parent.below == n){
			n.parent.below = n.below;
			n=null;
			return;
		}else if(n.parent.left== n){
			n.parent.left = n.below;
			n = null;
			return;
		}
		System.err.println("An error occured in deleteIfBelowIsNotNull");
		return;
	}
	

	private void deleteWithOneChild(Node n) {
		if(n.right == null){
			if(n.parent == null){ // n == root
				root = n.left;
				n.left.parent = null;
				n = null;
				return;
			}
			else if(n == n.parent.right){
				n.parent.right = n.left;
				n.left.parent = n.parent;
				n = null;
				return;
			}else if(n == n.parent.left){
				n.parent.left = n.left;
				n.left.parent = n.parent;
				n = null;
				return;
			}else if(n == n.parent.below){
				System.err.println("There has to be something wrong in deleteWithOneChild function.");
				return;
			}
		}
		
		if(n.left == null){
			if(n.parent == null){ // n == root
				root = n.right;
				n.right.parent = null;
				n = null;
				return;
			}else if(n == n.parent.right){
				n.parent.right = n.right;
				n.right.parent = n.parent;
				n = null;
				return;
			}else if(n == n.parent.left){
				n.parent.left = n.right;
				n.right.parent = n.parent;
				n = null;
				return;
			}else if(n == n.parent.below){
				System.err.println("There has to be something wring in deleteWithOneChild function.(2)");
				return;
			}
		}
		
		System.err.println("There has to be something wring in deleteWithOneChild function.(3)");
		return;
	}
	//swap the node with its successor. successor is the minimum in the right children since we are sure that 
	// there is a child on right and also there is no node below current node. 
	//After the swap, delete n since we know it has at most one child.
	private void deleteWithTwoChildren(Node n) {
		
		Node successor = this.successor(n);
		
		//Copy all tree relationship of successor into temp variable.
		Node temp = new Node(successor.value);
		temp.parent = successor.parent;
		boolean isTempLeftChild = false;
		if(successor.parent.right == successor){
			successor.parent.right = temp;
		}else{
			successor.parent.left = temp;
			isTempLeftChild = true;
		}
		temp.right = successor.right;
		temp.left = successor.left;
		
		//Replace n with its successor
		successor.parent = n.parent;
		if(n.parent == null){
			successor.parent = null;
			root = successor;
		}else if(n.parent.left == n){
			n.parent.left = successor;
		}else{
			n.parent.right = successor;
		}
		successor.right = n.right;
		if(successor.right != null)
			successor.right.parent = successor;
		successor.left = n.left;
		if(successor.left != null)
			successor.left.parent = successor;
		
		
		
		// if successor was a direct child of n, set n's parent to successor. Otherwise n's parent is former successor's parent.
		if(temp.parent != n){
			n.parent = temp.parent;
		}else{
			n.parent = successor;
		}
		n.left = temp.left;
		n.right = temp.right;
		
		// If successor was the left child of its parent, set the left child of its parent to n.
		if(isTempLeftChild == true){
			if(temp.parent != n){
				temp.parent.left = n;
			}else{// when successor is the immediate child of n.
				successor.left = n;
			}
		// If successor was the right child of its parent, set the right child of its parent to n.	
		}else{
			if(temp.parent != n){
				temp.parent.right = n;
			}else{// when successor is the immediate child of n.
				successor.right = n;
			}
		}
		temp = null;
		
		// Now n and its successor are completely swapped. Time to delete n since we are sure that n does not have a child in its below
		// and we are sure that n will have no child or only one child.
		if(n.left == null && n.right == null){
			if(n.parent.left == n){
				n.parent.left = null;
			}else{
				n.parent.right = null;
			}
			n = null;
			return;
		}else{ // n has at most one child (on its right)
			
			deleteWithOneChild(n);
		}
		
	}

	
	
	public static void main(String[] args) {
		Tree t = new Tree();
		Node node = t.new Node(1);
		Node node2 = t.new Node(3);
		Node node3 = t.new Node(2);
		Node node4 = t.new Node(4);
		Node node5 = t.new Node(5);
		Node node6 = t.new Node(0);
		Node node7 = t.new Node(-1);
		Node node8 = t.new Node(1);
		Node node9 = t.new Node(1);
		
		t.print();
		t.insert(node);
		t.insert(node2);
		t.insert(node3);
		t.insert(node4);
		t.insert(node5);
		t.insert(node6);
		t.insert(node7);
		t.insert(node8);
		t.insert(node9);
		
		t.delete(node8);
		t.delete(node);
		t.delete(node9);
		
		t.print();
		t.printRoot();
		
	}
	
	
	
	public class Node {
		Node left;
		Node right;
		Node below;
		Node parent;
		int value;
		public Node(){
			this(Integer.MAX_VALUE);
			
		}
		public Node(int x){
			left = null;
			right = null;
			parent = null;
			value = x;
			
		}
	}
}

ُThe running time of max heap for extracting k Max is O(Klgn) It might not help if K is O(n).

I would use partition idea in the quick sort. A pointer at the beginning and a pointer at the end. Whenever the beginning pointer encounters a zero, swap the first pointers value with the second one. Then while there is an immediate zero before the second pointer move the second pointer back. Do it while (first pointer < second pointer).

Selection algorithm is applicable on linked lists.

In O(n) we can realize that do we have a positive number or not.

If not: 
	If there is a zero and L is odd, select it and done!
	If L is odd and no zero, sort in O(nlgn) and choose the L lowest absolute values.
	If L is even, sort in O(nlgn) and choose the L biggest absolute values.

If we do have positive numbers, we can sort the array based on the absolute values O(nlgn) and choose the L biggest absolute values.

If the result is negative we do have two options:
1. Remove a negative value and add a positive value
2. Remove a positive value and add a negative value
Based on the current selected lowest positive and negative absolute values and the next positive and negative values, we can decide which one is better.