Developer Interview Questions — Algorithm
The algorithm I am going to talk about is specifically around the big(O) notation, and in this passage we are more focus in time complexity
Recently, I took some interviews in developer jobs and algorithm related question is one of the hot topics I have been asked.
I am not good at that and I am not an expert in this field, but I think this is something necessary if you want to pass the job interviews especially in developer position
In this passage, I will try to summarize the basic concepts (I learned from different sites) about the big(O) and share the interview questions I faced with my answer.
If you got any suggestion about my answer, please feel free to comment
Some basic concepts about the big(O)
Based on the above chart, we are aim to O(log n) — O(n), Excellent —Fair
- O(1) means in constant time — independent of the number of items.
output() {
return n;
}2. O(log N) means a time proportional to log(N)
while (x > 0) {
x /= 2;
}3. O(N) means in proportion to the number of items.
for (int i=0; i<10; i++) {
result = result + i;
}
Reference from
1. https://stackoverflow.com/questions/1909307/what-does-on-mean/1909374
2. https://stackoverflow.com/questions/17122807/big-o-ologn-code-example
3. https://www.oreilly.com/library/view/javatm-how-to/9780133813036/ch19lev1sec9.html
Big-O summary for Java collections framework
Searching and sorting algorithms with Big O values.
Questions I faced during job interviews
My Git — https://github.com/fifithecat
1.
Given 2 arrays
String first[] = new String[]{"ABCD 300", "BCCR 250", "BSSP 890", "DABC 600"};
String second[] = new String[] {"A", "B", "C"};The “first” array contains certain Strings, each String is the combination of some alphabet and a positive value, with a space as a separator
Here is the expected result
The result is a String, contains certain key value pairs, the key is the elements in “second” array, the value is the sum of positive value based on the “first” array
In the “second” array, it contains “A”, “B”, “C”, so we have to search the element in “first” array which starts from A/B/C
“ABCD 300”
“BCCR 250” “BSSP 900” – 250 + 900 =1140
because “first” array does not contains anything starts with “C”, so C = 0
We ignore “DABC 600” becoz “second” array do not request “D”
"(A : 200) - (B : 1140) - (C : 0)"Here is my answer in Java
Probably not the best one, but I try to do it without any nested loop.
import java.util.Map;
import java.util.Map.Entry;
import java.util.logging.Level;
import java.util.logging.Logger;public class StockList {
static Logger logger = Logger.getLogger(StockList.class.getName());
// 1st parameter is the stocklist (L in example),
// 2nd parameter is list of categories (M in example) public static String stockSummary(String[] lstOfArt, String[] lstOf1stLetter) { //result String
String result = "";
//each value in stocklist - category and quantity
String catQty = "";
//result of splitting the category and quantity
String[] catQtySplit;
String catCapitalLetter = "";
Map<String, Integer> lstOf1stLetterMap = new LinkedHashMap<String, Integer>();
//convert the list of categories (array) to list of categories
//(Linkedhashmap) - category as key, quantity as value
for (int i=0; i<lstOf1stLetter.length; i++) {
lstOf1stLetterMap.put(lstOf1stLetter[i], 0);
}
//loop through the stocklist array
for (int i=0; i<lstOfArt.length; i++) {
catQty = lstOfArt[i];
catCapitalLetter = catQty.substring(0, 1);
//check whether the current value (category/quantity) is it
//something we want(inside the list of categories)
if (lstOf1stLetterMap.containsKey(catCapitalLetter)) {
catQtySplit = catQty.split(" ");
//sum the quantity if same category
try {
lstOf1stLetterMap.merge(catCapitalLetter, Integer.valueOf(catQtySplit[1]), (oldValue, newValue) -> oldValue + newValue);
} catch (ArrayIndexOutOfBoundsException|NumberFormatException arrayIndexOutOfBoundsException) {
lstOf1stLetterMap.merge(catCapitalLetter, 0, (oldValue, newValue) -> oldValue + newValue);
logger.log(Level.SEVERE, "Fail to retrieve the quantity value from stocklist item - " + catQty);
}
}
}
Iterator<Entry<String, Integer>> it = lstOf1stLetterMap.entrySet().iterator();
//loop through the map in order to ouput the result
while (it.hasNext()) {
Map.Entry<String, Integer> catQtyValPair = (Entry<String, Integer>)it.next();
result = result + "("+catQtyValPair.getKey() + " : " + catQtyValPair.getValue() + ")";
if (it.hasNext())
result = result + " - ";
}
return result;
}
}
2.
Given an int array
int[] val = new int[] {43, 26, 10, 92, 62, 60, 78, 53, 44, 80, 62, 57, 37, 19, 2, 50, 69, 20, 65, 90, 17, 30, 11, 29, 26, 66, 55, 76, 68, 91, 28, 26, 35, 81, 51, 24, 35, 5, 62, 26, 37, 75, 35, 77, 23, 34, 88, 93, 1, 9};Here is the expected result
You have two find a pair of number X and Y and Y > X, the difference between X and Y have to be the largest around other potential pair.
Larger no. : 93 | Smaller no.: 2 | Larger no. at Index: 47 | Smaller no. at Index: 14
Largest difference 91Here is my answer in Java
Probably not the best one, but I try to do it with only one loop and without any nested loop
package com.latitude.codingTest;
import java.util.Arrays;
public class Calculation
{
//the final result - differences between the larger and smaller
int bestProfit = 0;
//the larger num currently using to calculate the difference
int larger = 0;
//the last larger num using to calculate the difference
int oldLarger = 0;
//the smaller num currently using to calculate the difference
int smaller = 0;
//the last smaller num using to calculate the difference
int oldSmaller = 0;
//the larger num have chance to produce a larger difference, but not confirmed yet
int largerCandidate = 0;
//the smaller num have chance to produce a larger difference, but not confirmed yet
int smallerCandidate = 0;
//(array index of) the larger num currently using to calculate the difference
int largerIndex = -1;
//(array index of) the last larger num using to calculate the difference
int oldLargerIndex = 0;
//(array index of) the larger num have chance to produce a larger difference, but not confirmed yet
int largerCandidateIndex = -1;
//(array index of) the smaller num currently using to calculate the difference
int smallerIndex = -1;
//(array index of) the last smaller num using to calculate the difference
int oldSmallerIndex = 0;
//(array index of) the smaller num have chance to produce a larger difference, but not confirmed yet
int smallerCandidateIndex = -1;
//differences between the larger and smaller, temp result only
int tempResult = 0;
public int getMaxProfit(int[] stockPrices) {
larger = stockPrices[stockPrices.length - 1];
smaller = stockPrices[stockPrices.length - 2];
largerIndex = stockPrices.length -1;
smallerIndex = stockPrices.length -2;
tempResult = larger - smaller;
for (int i=stockPrices.length - 1; i>=0 ; i-- ) {
//check the current number (from array loop) is good
//enough to replace the larger number if (stockPrices[i] - smaller > tempResult && i > smallerIndex) {
updateLarger(larger, largerIndex, stockPrices[i], i);
tempResult = larger - smaller;
} //check the current number (from array loop) is good
//enough to become the candidate of the larger number if (stockPrices[i] > larger && stockPrices[i] > largerCandidate) {
updateLargerCandidate(stockPrices[i], i);
} //check the current number (from array loop) is good
//enough to replace the smaller number if (i > 0 && larger - stockPrices[i-1] > tempResult && largerIndex > i-1) {
updateSmaller(smaller, smallerIndex, stockPrices[i-1], i-1);
tempResult = larger - smaller;
} //check the current number (from array loop) is good
//enough to become the candidate of the smaller number if (smaller > stockPrices[i] && smallerCandidate > stockPrices[i]) {
smallerCandidate = stockPrices[i-1];
smallerCandidateIndex = i-1;
} //check both the larger and smaller candidate are good
//enough to replace the larger and smaller number if (largerCandidate > smallerCandidate && largerCandidateIndex > smallerCandidateIndex && largerCandidateIndex != -1 && smallerCandidateIndex != -1) {
updateLarger(larger, largerIndex, largerCandidate, largerCandidateIndex);
updateSmaller(smaller, smallerIndex, smallerCandidate, smallerCandidateIndex);
updateLargerCandidate(0, -1);
updateSmallerCandidate(0, -1);
}
//check larger number candidate is good enough to
//replace the larger number or not if (largerCandidate - stockPrices[i] > tempResult && largerCandidateIndex > i) {
updateLarger(larger, largerIndex, largerCandidate, largerCandidateIndex);
updateSmaller(smaller, smallerIndex, stockPrices[i], i);
tempResult = larger - smaller;
updateLargerCandidate(0, -1);
updateSmallerCandidate(0, -1);
}
//Look at the smaller number again, as the larger number
//may just updated
if (i > 0 && larger - stockPrices[i-1] > tempResult && largerIndex > i-1) {
updateSmaller(smaller, smallerIndex, stockPrices[i-1], i-1);
tempResult = larger - smaller;
}
}
bestProfit = larger - smaller;
if (!(larger > smaller && largerIndex > smallerIndex)) {
bestProfit = -1;
}
System.out.println(Arrays.toString(stockPrices));
if (bestProfit == -1) {
System.out.println("Unable to looking for positive difference in this array");
} else {
System.out.println("Larger no. : " + larger + " | " + "Smaller no.: " + smaller + " | " + "Larger no. at Index: " + largerIndex + " | " + "Smaller no. at Index: " + smallerIndex );
System.out.println("Best Profit " + bestProfit);
}
System.out.println("");
return bestProfit;
}
public void updateLarger(int oldLarger, int oldLargerIndex, int larger, int largerIndex) {
this.oldLargerIndex = oldLargerIndex;
this.largerIndex = largerIndex;
this.oldLarger = oldLarger;
this.larger = larger;
}
public void updateSmaller(int oldSmaller, int oldSmallerIndex, int smaller, int smallerIndex) {
this.oldSmallerIndex = oldSmallerIndex;
this.smallerIndex = smallerIndex;
this.oldSmaller = oldSmaller;
this.smaller = smaller;
}
public void updateLargerCandidate(int largeCandidate, int largeCandidateIndex) {
this.largerCandidate = largeCandidate;
this.largerCandidateIndex = largeCandidateIndex;
}
public void updateSmallerCandidate(int smallCandidate, int smallCandidateIndex) {
this.smallerCandidate = smallCandidate;
this.smallerCandidateIndex = smallCandidateIndex;
}
public void reset() {
this.bestProfit = 0;
this.larger = 0;
this.oldLarger = 0;
this.smaller = 0;
this.oldSmaller = 0;
this.largerCandidate = 0;
this.smallerCandidate = 0;
this.largerIndex = -1;
this.oldLargerIndex = 0;
this.largerCandidateIndex = -1;
this.smallerIndex = -1;
this.oldSmallerIndex = 0;
this.smallerCandidateIndex = -1;
this.tempResult = 0;
}
}
