gzyeli123
 0of 0 votes
AnswersThere are two integer array arrayA and arrayB in the same size and two integer countA and countB. If arrayA[i] > arrayB[i], then we increase countA by 1, if arrayB[i]>arrayA[i], then we increase countB by 1. We will do nothing otherwise. Now you are given arrayA and arrayB, write a function to shuffle arrayA and so you can get countA > countB. Assume the input array are always valid, not empty and the input is guaranteed to have answer.
 gzyeli123 in United States
For example:
arrayA = [12, 24, 8, 32]
arrayB = [13, 25, 32, 11]
After shuffle:
arrayA = [24, 32, 8, 12]
arrayB = [13, 25, 32, 11] Report Duplicate  Flag
Microsoft SDE1 Algorithm  0of 0 votes
AnswersI was having an interview and here is the question:
 gzyeli123 in United States
If there are different pairs of characters, each pair of the characters means the two matching characters are the same. Print out all the identical characters.
For example:
if you have pairs:
AB
CD
EF
GH
AD
FG
you should print out:
{A, B, C, D} are the same characters.
{E, F, G, H} are the same characters.
Does anyone know how to solve this problem by not using brutal force? Report Duplicate  Flag
Lab126 Software Engineer / Developer Algorithm
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.
 gzyeli123 July 05, 2014I 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 keyvalue 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[(sumarr[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;
}

gzyeli123
July 05, 2014 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<m1; i++)
{
if(i >= mi)
{
pa[i] = 0;
}
else
{
if(pa[2*idi] < pa[id]+idi)
{
pa[i] = pa[2*idi];
continue;
}
else
{
pa[i] = pa[id]+idi;
}
}
while(ms[ipa[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;
}

gzyeli123
July 05, 2014 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(i1)+fibonacci(i2);
}
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+" ");
}
}
}
}

gzyeli123
July 01, 2014 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 notzero 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();
}
}

gzyeli123
June 29, 2014 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).
 gzyeli123 June 28, 2014If 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.");
}
}

gzyeli123
June 09, 2014 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.length1; i>=0; i)
{
if(i==0)
System.out.print(stringArray[i]);
else
System.out.print(stringArray[i]+" ");
}
System.out.print("\"");
}
}

gzyeli123
June 07, 2014 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();
}
}
Open Chat in New Window
BTW, I missed one condition, the given array could be large so brutal force or permutation cannot be used because of the performance issue.
 gzyeli123 March 20, 2017