coder145
BAN USER- 2of 2 votes
AnswersConvert a number to English representation.
- coder145 in United States
Ex: Input : 100
Output : One Hundred.| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 1of 1 vote
AnswersFind the anagrams from a list of strings
- coder145 in United States
Input : {"tea", "ate", "eat", "apple", "java", "vaja", "cut", "utc"}
Output : {"tea", "ate", "eat","java", "vaja", "cut", "utc"}| Report Duplicate | Flag | PURGE
Twitter Senior Software Development Engineer Algorithm
// return 1! - 2! + 3! - 4!... n!
public static int calculate(int n) {
int []factorial = new int[n];
factorial[0] = 1; //1!
int result = factorial[0];
for(int i=2;i<=n;i++) { // i = 1
factorial [i-1] = factorial[i - 2] * i;
if(n % 2 == 0) {
result -= factorial[i-1];
} else {
result += factorial[i-1];
}
}
return result;
}
Time Complexity : O(n) for iterations, O(1) - constant access for array
Space Complexity : Additional space of size n
public static void findOddlyRepeatedNumbers(int a[]) {
if (a == null || a.length == 0) {
return;
}
HashMap<Integer, Integer> map = new HashMap<>(a.length);
int count = 0;
for (int i = 0; i < a.length; i++) {
if (!map.containsKey(a[i])) {
map.put(a[i], 1);
} else {
count = map.get(a[i]);
map.put(a[i], ++count);
}
}
Iterator<Entry<Integer, Integer>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
Entry<Integer, Integer> entry = (Entry<Integer, Integer>) iterator.next();
int key = entry.getKey();
int value = entry.getValue();
if (value % 2 != 0) {
System.out.println(key + " repeated for " + value + " times");
}
}
}
public static void main(String []args) {
// input is an integer array - i can read it
int []array = input;
System.out.println("Incremented Number : " + outputArray(array));
}
public static int[] outputArray(int []inputArray) {
if(inputArray == null) return inputArray;
int arrLength = inputArray.length();
// check for all 9s
boolean all9s = true;
for(int i=0;i<arrLength && all9s;i++) { // 0(k) --> k is the first non 9
if(all9s && inputArray[i] == 9) {
all9s = true;
} else {
all9s = false;
}
}
if(all9s) {
int []newInputArray = new int[arrLength+1];
newInputArray[0] = 1; // 0(1)
for(int i=1;i<newInputArray;i++) { // 0(n)
newInputArray[i] = 0;
}
return newInputArray;
} else {
for (int i = arrLength-1; i > -1;i --) { // O(k+1) where is the first non 9
int k = inputArray[i];
if(k == 9) {
inputArray[i] = 0;
} else {
inputArray[i] = k++; // o(1)
return inputArray;
}
}
}
}
Time Complexity : o(n) Space Complexity : o(n) ; requires additional array of the same size
Another solution could be write an sorting algo in descending order.
public static void modifyArray(int []input) {
int []modifiedArray = new int[input.length];
int startIndex = 0;
int lastIndex = input.length -1;
for(int i =0;i<input.length;i++) {
if(input[i] == 0) {
modifiedArray[lastIndex--] = input[i];
} else {
modifiedArray[startIndex++] = input[i];
}
}
printArray(modifiedArray);
}
Linear Solution : Time Complexity o(n); No Additional Space required.
public static int[] getTargetArray(int[] input, int target) {
int startPos = 0;
int endPos = 0;
int length = input.length;
int sum = 0;
boolean subArrayFound = false;
for (int i = 0; i < length; i++) {
sum += input[i]; // 9
if (sum > target) {
while(sum > target) {
sum -= input[startPos++];
if (sum < 0)
sum = 0;
}
}
if (sum == target) {
endPos = i;
subArrayFound = true;
break;
}
}
if (!subArrayFound)
return null;
int[] subArray = new int[endPos - startPos + 1];
for (int k = 0; k < subArray.length; k++) {
subArray[k] = input[k+startPos];
}
return subArray;
}
public static int maxDrop(int []array) {
if(array == null || array.length < 2) {
return -1;
}
int leastValInArray = array[0];
int highestValInArray = array[1];
if(array[0] > array[1]) {
leastValInArray = array[1];
highestValInArray = array[0];
}
int arrayLength = array.length;
for(int i = 2;i<arrayLength;i++) {
if(leastValInArray > array[i]) {
leastValInArray = array[i];
}
if(highestValInArray < array[i]) {
highestValInArray = array[i];
}
}
return highestValInArray - leastValInArray;
}
Time Complexity : O(n-2) ;
- coder145 September 21, 2015
- coder145 October 07, 2016