RG
BAN USERStudent
- -2of 2 votes
AnswersRearrange an array so that arr[i] becomes arr[arr[i]] with O(1) extra space
- RG in United States| Report Duplicate | Flag | PURGE
Software Engineer / Developer Algorithm
in Java:
public static String countCChar(String s) {
if(s == null || s.length() < 2) {
return null;
}
StringBuilder ans = new StringBuilder();
s = s.toUpperCase();
char c = s.charAt(0);
int count = 1;
for(int i=0; i< s.length()-1; i++) {
if(s.charAt(i) == s.charAt(i+1)) {
count++;
}
else {
ans.append(c);
ans.append(count);
//reset the counter
c = s.charAt(i+1);
count = 1;
}
}
//append the last char
ans.append(c);
ans.append(count);
return ans.toString();
}
public static String reverseString(String s) {
//base case
if(s == null || s.length() <= 1) {
return s;
}
char[] arr = s.toCharArray();
int k = arr.length-1;
int i = 0;
while(i < k) {
if(arr[i] >= '0' && arr[i] <= '9') { i++; }
if(arr[k] >= '0' && arr[k] <= '9') { k--; }
if (i < k) {
//swap the elements
char temp = arr[i];
arr[i] =arr[k];
arr[k] = temp;
}
i++; k--;
}
return String.valueOf(arr);
}
- RG March 19, 20141. Find sum of all the population. Let's say Total
2. Pick a number in the range 1 to Total randomly.
3. check in the array where this number is located and return the country accordingly.
For checking:
1. you can create a cummulative sum array.
2. you can sort the population first, then use any modified binary search to locate the Country
It is an association mining problem. There are many good algorithms such as "Apriori", "Frequent Pattern Mining". That could be used here.
General Idea:
1. List the items the user bought {X,Y,A,B,C} for each user in a separate line.
2. Count the subset {X,A,B,C} in all user transactions and then count the subset {X}.
3. Then you can calculate measures such as "support" and "Confidence" to measure the probability.
Java Code
public class BreakContiArray {
public static void getBreakEvenPoint(int[] arr) {
int first = 0;
int second = 0;
for(int i: arr) { second += i; }
for(int i=0; i < arr.length-1; i++) {
first = first + arr[i];
second = second - arr[i];
if(first == second ) {
System.out.println("Break even point is: "+i);
}
}
}
public static void main(String[] args) {
int[] arr = {1,0,-1,-1,1};
BreakContiArray.getBreakEvenPoint(arr);
}
}
- RG January 23, 2014
Java Code. Comments are welcome.
- RG April 08, 2014