CareerCup

BTW, I missed one condition, the given array could be large so brutal force or permutation cannot be used because of the performance issue.

I never say to use merge sort...

Oh, I forgot to mention that in the second step, 2+13 = 15, how ever, there is not 13 in the array, so we will not query this pair. Which means that when we see 2 in the array, we cannot find any pair in the hashmap. So we can only find 4 and 11 pair in the hashmap.

I think I can find an algorithm in O(n) time.

If the array can be separate into two parts, which is S1 = S2, and S1 = a + b, and S2 = summation of the rest element. We can process the array in this way:

First, get the sum of the array, in the example, sum{2,11,5,1,4,7} = 30. Then we can let it divided by 2, so it becomes 30/2 = 15.

Second, this problem becomes that whether we can find two elements in the array, and the summation is 15. So we need a hashmap to store all the subtraction of 15 and elements in the array. The key will be the subtraction and the value will be the element's index. So in this example, the hashmap will have the key-value pairs like this: {(4, 1),(8, 5),(10, 2),(11, 4),(13, 0),(14, 3)}. You can see that there is one pair: (13, 0), it means that the 0th element in the array, which is 2, 2+13 = 15. So, the 1st element in the array is 11 and 4+11 = 15.

Third, after we have the hashmap, we can traverse the array from left to right. When we meet the element in the array, we check if we can find the same number in the hashmap by key value. For example, we the first element in the arrray is 2, and we cannot find this key value in the hashmap. Then we 11, and we can find 11 in the hashmap and the value is 4, it means that in the array 11 puls the 4th element in the array equals to 15. The 4th element in the array is 4, which is correct. So if we can find the array and the hashmap share the same number, it means we can find 2 elements in the array with the sum equals to the sum of the rest elements in the array.

In the algorithm, get sum and divide it by 2 requires O(n) time, create the hashmap needs O(n) time, and traverse the array still needs O(n) time. The total complexity will be O(n).

#include <iostream>
#include <map>

using std::cin;
using std::endl;
using std::cout;
using std::map;

class demo
{
private:
	int *arr;
	int length;

public:
	demo(int a[], int n)
	{
		arr = new int[n];
		length = n;

		for(int i=0; i<n; i++)
		{
			arr[i] = a[i];
		}
	}

	~demo()
	{
		delete [] arr;
		cout<<"Array deleted..."<<endl;
	}

	bool twoSum()
	{
		int sum = 0;
		map<int, int> sub;
		bool result = false;

		for(int i=0; i<length; i++)
		{
			sum = sum + arr[i];
		}

		sum = sum/2;
		for(int i=0; i<length; i++)
		{
			sub[(sum-arr[i])] = i;
		}

		for(int i=0; i<length; i++)
		{
			if(sub.find(arr[i]) != sub.end())
			{
				result = true;
				return result;
			}
			else
			{
				result = false;
			}
		}

	}
};

int main(int argc, const char * argv[])
{
    

    
    // insert code here...
	int a[] = {2, 11, 5, 1, 4, 7};
	demo d(a, 6);
	if(d.twoSum()){
		cout<<"The result is true..."<<endl;
	}
	else{
		cout<<"The result is false..."<<endl;
	}
	system("pause");
    return 0;
}

I don't remember to do that by recursion! Sorry about that!!!!!

I think my code will works and I use Manacher's algorithm. For more information, search this algorithm and you will know how it works.

#include <iostream>
#include <string>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;

class LGSTPalinddromeFinder
{
public:
    string longestPalindrome(string s)
    {
        size_t n = s.length();
        if(n<=1)
        {
            return s;
        }
        
        string ms = "$#";
        for(int i=0; i<n; i++)
        {
            ms.append(1, s[i]);
            ms.append(1, '#');
        }
        
        int m = (int)n*2+2;
        vector<int> pa(m, 0);
        
        int maxi=0, id=0, mi = id+pa[id];
        
        for(int i=1; i<m-1; i++)
        {
            if(i >= mi)
            {
                pa[i] = 0;
            }
            else
            {
                if(pa[2*id-i] < pa[id]+id-i)
                {
                    pa[i] = pa[2*id-i];
                    continue;
                }
                else
                {
                    pa[i] = pa[id]+id-i;
                }
            }
            
			
			while(ms[i-pa[i]-1] == ms[i+pa[i]+1])
			{
				pa[i]++;
				if((i+pa[i]+1) >= ms.size())
				{
					break;
				}
			}
            
            if(i+pa[i]>mi)
            {
                id = i;
                mi = id + pa[id];
            }
            
            if(pa[i]>pa[maxi])
            {
                maxi = i;
            }
        }
        
        string r;
        int left = maxi - pa[maxi], right = maxi + pa[maxi];
        
        for(int i = left; i<=right; i++)
        {
            if(ms[i] != '$' && ms[i] != '#')
                r.append(1, ms[i]);
        }
        
        return r;
        
    }
};

int main(int argc, const char * argv[])
{
    

    
    // insert code here...
    string s;
    cin >> s;
    LGSTPalinddromeFinder so;
    string r = so.longestPalindrome(s);
    cout<<r<<endl;
    return 0;
}

You can generate the Fibonacci number by recursion, then just test if the number going to be printed out is an even number or not.

public class test {

	public static int fibonacci(int i)
	{
		if(i == 1 || i == 2)
			return 1;
		else
			return fibonacci(i-1)+fibonacci(i-2);
	}
	
	
	
	public static void main(String[] args) {
		
		int n;
	   for(int i = 1; i< 11; i++)
	   {
		   n = fibonacci(i);
		   if(n%2 == 0)
		   {
			   System.out.print("# ");
		   }
		   else
		   {
			   System.out.print(n+" ");
		   }
	   }
	}
}

I am not sure if my solution is good or not. But I only create another array with all 0. Then I scan the given array, once I reach a not-zero element, I put it in the new array. It is O(n). But it needs an extra array.

import java.util.Arrays;

class numshift
{
	private int[] array;
	
	
	public numshift(int[]  a)
	{
		array = a;
	}
	
	
	
	public void swap(int[] a, int i, int j)
	{
		int b = a[i];
		a[i] = a[j];
		a[j] = b;
	}
	
	public int[] shift()
	{
		int[] result = new int[array.length];
		
		Arrays.fill(result, 0);
		
		int index  = 0;
		for(int i=0; i<array.length; i++)
		{
			if(array[i] != 0)
			{
				result[index] = array[i];
				index++;
			}
		}
		
		return result;
		
	}
}




public class Main {
	
	public static void main(String args[])
	{
		int[]  a = {1,0,2,0,0,3,4};
		
		numshift n = new numshift(a);
		a = n.shift();
		
		for(int i=0; i<a.length; i++)
		{
			System.out.print(a[i]);
			System.out.print(" ");
		}
		System.out.println();
	}

}

I am not sure if I am correct. My algorithm is that first, calculation all the distance between the hotels and the user's point, it takes O(n). Then use the quick sort to make the list, it takes O(log n) in general case, but it takes O(n^2) in the worst case. So the total time complexity in general should be O(n+log n).

If I am wrong please correct me.

I use KMP algorithm to match all the occurrences and replace them one by one.

public class test {
	
	public static void main(String[] args) {

		String thestring = "Microsoft";
		String occur = "ic";
		String replace = "MSFT";
		int count = 0;
		
		int i=0, m;
		int length = thestring.length();
		while(i<length)
		{
			length = thestring.length();
			m=0;
			if(thestring.charAt(i)!=occur.charAt(m))
			{
				i++;
			}
			else
			{
				int oldi = i;
				
				while(thestring.charAt(oldi) == occur.charAt(m))
				{
					oldi++;
					m++;
					
					if(m>=occur.length()-1)
					{
						break;
					}
				}
				
				if(m<occur.length()-1)
				{
					i = oldi+m+1;
				}
				else
				{
					count++;		
					thestring = thestring.substring(0, i) + replace + thestring.substring(i+occur.length());
					i = oldi+occur.length();
				}
			}
		}
		
		System.out.println("The string: "+thestring);
		System.out.println("replaces "+count+" occurrences.");
	}
}

If I am wrong, pls correct me. The time complexity is O(n);

I use a stack to reverse the whole sequence of the string then split them by space.

input: @"the boy ran"

output: @"eht yob nar"

import java.util.Scanner;
import java.util.Stack;



public class test {
	
	public static void main(String[] args) {
		
		Scanner input = new Scanner(System.in);
		String thestring = input.nextLine();
		input.close();
		
		thestring = thestring.substring(2, thestring.length()-1);
		
		Stack<Character> st = new Stack<Character>();
		
		for(int i=0; i<thestring.length(); i++)
		{
			st.push(thestring.charAt(i));
		}
		
		
		thestring = "";
		while(!st.empty())
		{
			thestring = thestring + st.peek();
			st.pop();
		}
		
		String[] stringArray = thestring.split(" ");
		
		System.out.print("@\"");
		for(int i=stringArray.length-1; i>=0; i--)
		{
			if(i==0)
				System.out.print(stringArray[i]);
			else
				System.out.print(stringArray[i]+" ");
		}
		
		System.out.print("\"");
	}
}

I think my code will works.

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

class Replace
{
private int[] number;
private List<Integer> indexlist;
char[] thestring;

public Replace(String s)
{
indexlist = new LinkedList<Integer>();
thestring = s.toCharArray();
int count = 0;
for(int i=0; i<thestring.length; i++)
{
if(thestring[i] == '?')
{
count++;
}
}

number = new int[count];

for(int i=0; i<count; i++)
{
number[i] = 0;
}

for(int i = 0; i<thestring.length; i++)
{
if(thestring[i] == '?')
{
indexlist.add(i);
}
}

}

public void output(char[] a)
{
System.out.println(a);
}

public void RemoveQ(int[] array, int start, int end)
{
if(start == end)
{
char[] result = new char[thestring.length];
int i = 0;
result = thestring.clone();
Iterator<Integer> iter = indexlist.iterator();
while(iter.hasNext())
{
result[iter.next()] = (char)(array[i]+48);
i++;
}

output(result);
return;
}
else
{
array[start] = 0;
RemoveQ(array, start+1, end);
array[start] = 1;
RemoveQ(array, start+1, end);
}
}


public void run()
{
int[] temp = new int[number.length];
temp = number.clone();
RemoveQ(temp, 0, temp.length);
}

}






public class Main {

public static void main(String args[])
{
Scanner in = new Scanner(System.in);
String instring = in.nextLine();
in.close();
Replace R = new Replace(instring);
R.run();
}

}

I think my code will works.

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

class Replace
{
private int[] number;
private List<Integer> indexlist;
char[] thestring;

public Replace(String s)
{
indexlist = new LinkedList<Integer>();
thestring = s.toCharArray();
int count = 0;
for(int i=0; i<thestring.length; i++)
{
if(thestring[i] == '?')
{
count++;
}
}

number = new int[count];

for(int i=0; i<count; i++)
{
number[i] = 0;
}

for(int i = 0; i<thestring.length; i++)
{
if(thestring[i] == '?')
{
indexlist.add(i);
}
}

}

public void output(char[] a)
{
System.out.println(a);
}

public void RemoveQ(int[] array, int start, int end)
{
if(start == end)
{
char[] result = new char[thestring.length];
int i = 0;
result = thestring.clone();
Iterator<Integer> iter = indexlist.iterator();
while(iter.hasNext())
{
result[iter.next()] = (char)(array[i]+48);
i++;
}

output(result);
return;
}
else
{
array[start] = 0;
RemoveQ(array, start+1, end);
array[start] = 1;
RemoveQ(array, start+1, end);
}
}


public void run()
{
int[] temp = new int[number.length];
temp = number.clone();
RemoveQ(temp, 0, temp.length);
}

}






public class Main {

public static void main(String args[])
{
Scanner in = new Scanner(System.in);
String instring = in.nextLine();
in.close();
Replace R = new Replace(instring);
R.run();
}

}