techinterviewquestion.com
BAN USERMy Java solution, complexity O(n), space O(n).
public String interchange(String s) {
String vowels = "aeiouy";
// array counter for count amount of each vowels in s
int[] counter = new int[300];
for (char c : s.toCharArray()) {
if (vowels.contains(c + "")) {
counter[c]++;
}
}
// build answer
StringBuilder builder = new StringBuilder();
for (char c : s.toCharArray()) {
// if c is vowels, search remain vowels in
// counter from 'a' to 'z' and append to answer
if (vowels.contains(c + "")) {
for (char x = 'a'; x <= 'z'; x++) {
// counter[x] > 0 mean vowels x is available
if (counter[x] > 0) {
builder.append(x);
counter[x];
break;
}
}
} else { // append other character to answer
builder.append(c);
}
}
return builder.toString();
}

techinterviewquestion.com
July 11, 2017 You can use this python code to generate all permutation of an array. Complexity O(n!).
def permute(xs, low=0):
if low + 1 >= len(xs):
yield xs
else:
for p in permute(xs, low + 1):
yield p
for i in range(low + 1, len(xs)):
xs[low], xs[i] = xs[i], xs[low]
for p in permute(xs, low + 1):
yield p
xs[low], xs[i] = xs[i], xs[low]
# generate permuation of array [1,2,3]
for p in permute([1, 2, 3]):
print p

techinterviewquestion.com
July 10, 2017 I think the best option is not using '+' because the result from '+' two number always smaller than '*' (except + 0 and * 0) so the problem will become: add '*' to a string such that the result is largest.
 techinterviewquestion.com July 09, 2017Hi, you can use moving window algorithm to solve this problem, the complexity is O(n). Here's Java code.
public Set<String> findAnagrams(String a, String b) {
// create two array for counter
// number of each letter in String a and Substring b
char[] aCounter = new char[300];
char[] bCounter = new char[300];
// count number of each letter in String a
for (char c : a.toCharArray()) {
aCounter[c]++;
}
Set<String> answer = new HashSet<>();
// create two variable for moving window
int left = 0;
int right = 0;
while (right < b.length()) {
// update counter letter of window
bCounter[b.charAt(right)]++;
// if window length equal a length,
// check if this window same letter with a or not
if (right  left + 1 == a.length()) {
if (isSame(aCounter, bCounter)) {
// if this window same letter with a,
// add substring from left to right to answer
answer.add(b.substring(left, right + 1));
}
// moving window to right
bCounter[b.charAt(left)];
left++;
}
right++;
}
return answer;
}
private boolean isSame(char[] aCounter, char[] bCounter) {
for (char c = 'a'; c <= 'z'; c++) {
if (aCounter[c] != bCounter[c]) {
return false;
}
}
return true;
}

techinterviewquestion.com
July 09, 2017 My solution, using backtracking:
def findPercent(word, glossary):
answer = 0
for i in range(1, len(word) + 1):
sub = word[:i]
if sub in glossary:
answer = max(answer, len(sub) + findPercent(word[i:], glossary))
else:
answer = max(answer, findPercent(word[i:], glossary))
return answer
if __name__ == '__main__':
word = "catdog"
glossary = ["dog", "frog", "cat", "c"]
print findPercent(word, glossary) * 100.0 / len(word)

techinterviewquestion.com
June 08, 2016 Try my code:
def findFactor(x, prev, outStr):
for i in range(x, 1, 1):
if x % i == 0 and prev >= i:
findFactor(x / i, i, outStr + (" * " if outStr != "" else "") + str(i))
if x == 1:
if "*" not in outStr:
outStr += " * 1"
print outStr
if __name__ == '__main__':
findFactor(24, 24, "")

techinterviewquestion.com
June 08, 2016 Java solution, the complexity is O(n):
private String encode(String s) {
StringBuilder builder = new StringBuilder();
char[] A = s.toCharArray();
int i = 0;
while (i < A.length) {
char c = A[i];
int counter = 0;
while (i < A.length && A[i] == c) {
i++;
counter++;
}
if (counter > 1) {
builder.append(counter).append('x').append(c);
} else {
builder.append(c);
}
}
return builder.toString();
}

techinterviewquestion.com
May 23, 2016 Java solution, complexity is O(n):
private String countDuplicate(String s) {
StringBuilder result = new StringBuilder();
// count letters
int[] counter = new int[300];
for (char c : s.toCharArray()) {
counter[c]++;
}
// build answer
boolean[] isProcessed = new boolean[300];
for (char c : s.toCharArray()) {
if (isProcessed[c]) {
continue;
}
isProcessed[c] = true;
result.append(c).append(counter[c]);
}
return result.toString();
}

techinterviewquestion.com
May 23, 2016 Java solution, complexity O(n * k):
private int[] reverseArray(int[] A, int k) {
for (int i = 0; i < A.length; i += k) {
int left = i;
// in case right larger than A.length
int right = Math.min(i + k  1, A.length  1);
// reverse sub array
while (left < right) {
int temp = A[left];
A[left] = A[right];
A[right] = temp;
left++;
right;
}
}
return A;
}

techinterviewquestion.com
May 23, 2016 def someoneWon(table):
for i in range(3):
table[i] = list(table[i])
isWon = False
# check rows and columns
for i in range(3):
if table[i][0] != '.' and table[i][0] == table[i][1] == table[i][2]:
isWon = True
if table[0][i] != '.' and table[0][i] == table[1][i] == table[2][i]:
isWon = True
# check two diagonals
isWon = (table[0][0] != '.' and table[0][0] == table[1][1] == table[2][2])
isWon = (table[0][2] != '.' and table[0][2] == table[1][1] == table[2][0])
return isWon
if __name__ == '__main__':
table = ["XO.",
".X.",
"OOX"]
print someoneWon(table)

techinterviewquestion.com
May 12, 2016 My answer for n < 10^18. Complexity is O(numbersDigits(n))
def count2(n):
total2 = [0 for i in range(0, MAX_DIGIT)]
# total 2s from 0 to 9
total2[1] = 1
# continue calculate 2s from 0 to 99, 0 to 999, etc...
for i in range(2, MAX_DIGIT):
total2[i] = total2[i  1] * 10 + 10**(i  1)
answer = 0
# example: 123 = 1 * total2[2] + 2 * total2[1] + 23 + 3 * total2[0] + 10^0
for i in range(len(n)):
# calculate number of 2 exists
value = int(n[i])
digits = len(n)  i  1
answer += value * total2[digits]
# if this digits is 2, increase answer by all remains value
if value == 2:
answer += int("0" + n[i + 1:len(n)]) + 1
# if this digits is larger than 2, increase answer by 10**digits
if value > 2:
answer += 10**digits
return answer

techinterviewquestion.com
May 12, 2016 My solution:
Complexity O(n)
Space O(n)
public int findMaxSubArray(int[] A, int S) {
int n = A.length;
// array store minimum index of a value
int[] minIndex = new int[n + 1];
// array store maximum index of a value
int[] maxIndex = new int[n + 1];
// initial arrays value
for (int i = 0; i <= n; i++) {
minIndex[i] = Integer.MAX_VALUE;
maxIndex[i] = 0;
}
minIndex[0] = 0;
int sum = 0;
for (int i = 0; i < n; i++) {
sum += A[i];
minIndex[sum] = Math.min(minIndex[sum], i + 1);
maxIndex[sum] = Math.max(maxIndex[sum], i + 1);
}
int answer = 0;
for (int i = 0; i <= n  S; i++) {
// maxIndex[i + S]  minIndex[i] is the maximum length of value i
answer = Math.max(answer, maxIndex[i + S]  minIndex[i]);
}
return answer;
}

techinterviewquestion.com
March 02, 2016 My code:
private boolean isValidParenthesis(char[] s) {
// assume we have a map contains all type of parenthesis
Map<Character, Character> parenthesisType = new HashMap<Character, Character>();
parenthesisType.put('{', '}');
parenthesisType.put('(', ')');
parenthesisType.put('[', ']');
// initial a stack
Stack stack = new Stack();
for (int i = 0; i < s.length; i++) {
// if s[i] is a valid open parenthesis, push to stack
if (parenthesisType.containsKey(s[i])) {
stack.push(s[i]);
}
// if not, this may be a close parenthesis, so
// check the top of stack, if it's same type
// with s[i], remove this top open parenthesis
else if (!stack.empty() && parenthesisType.get(stack.peek()) == s[i]) {
stack.pop();
}
// if this parenthesis not exist or stack is empty, return false
else {
return false;
}
}
// if our stack is empty, this mean s is valid parenthesis
return stack.isEmpty();
}

techinterviewquestion.com
February 29, 2016 I think the answer is 116, if we replace 116 by 18 we will have all number from 1 to 9
 techinterviewquestion.com February 28, 2016My solution:
Complexity: O(n^2)
Space: O(n)
public class Node {
public Node left;
public Node right;
public int index;
public int value;
public Node(Node left, Node right, int value) {
this.left = left;
this.right = right;
this.value = value;
}
}
private int minLeft = 0;
private int maxRight = 0;
public void showTree(Node root) {
// set index to all node in tree
// and save left most and right most index
// note that index may be negative
root.index = 0;
setIndex(root);
// from left most to right most index
// we using bfs to go through the tree
// if a node index have same index,
// print this node's value
for (int i = minLeft; i <= maxRight; i++) {
// we init a queue
Queue<Node> queue = new ArrayDeque<Node>();
queue.add(root);
while (!queue.isEmpty()) {
Node top = queue.poll();
if (top.index == i) {
System.out.print(top.value + " ");
}
if (top.left != null) {
queue.add(top.left);
}
if (top.right != null) {
queue.add(top.right);
}
}
}
}
private void setIndex(Node current) {
minLeft = Math.min(minLeft, current.index);
maxRight = Math.max(maxRight, current.index);
// left node's index = father's index  1
if (current.left != null) {
current.left.index = current.index  1;
setIndex(current.left);
}
// right node's index = father's index + 1
if (current.right != null) {
current.right.index = current.index + 1;
setIndex(current.right);
}
}

techinterviewquestion.com
February 26, 2016 My solution using python
def addValue(A, value):
# for i from len(A)  1 to 0
for i in range(len(A)  1, 1, 1):
value += A[i]
A[i] = value % 10
value /= 10
# if the remain value is still larger than 0
# add it to index 0 of array A
if value > 0:
A = [value] + A
return A

techinterviewquestion.com
February 26, 2016 My solution:
Time: O(1)
Space: O(1)
public class Statistics {
private int[] counter;
private long sum;
private int n;
public Statistics() {
// initial an array for counter number of
// existed of each value in [0999]
counter = new int[1000];
// sum all insert value
sum = 0;
// n is number of value
n = 0;
}
public void insert(int value) {
// if insert value not in range [0999], return
if (value >= 1000  value < 0) {
return;
}
// increase counter in this value
counter[value]++;
// calculate sum
sum += value;
// increase number of value
n++;
}
public double getMean() {
return (double)sum / n;
}
// examples we have:
// value: 3 9 11
// counter: 1 3 20
// n = 1 + 3 + 20 = 24
// so median will be value at position 24 / 2 = 12
// we will count until meet value at position 12
// result is 11
public int getMedian() {
int medianIndex = (n + 1) / 2;
// counter variable
int idx = 0;
for (int value = 0; value < 1000; value++) {
idx += counter[value];
if (idx >= medianIndex) {
return value;
}
}
return 1;
}
}

techinterviewquestion.com
February 16, 2016 Hi chenm, as I understand abaaca is invalid because there're two 'a' adjacent.
Hi elena.nur88, I don't understand why aba is invalid.
If you want the complexity O(n^2 logn), instead of using HashMap, you store all cotangent value in a list and sort this list. After that, using a loop to find the longest continues equal value, this is the answer.
 techinterviewquestion.com February 13, 2016Actual my solution has the complexity is O(n^2) because in the worst case there will be n ^ 2 middle points generated and I use a HashMap for counting all cotangent value with cost only O(1).
 techinterviewquestion.com February 13, 2016A pair is valid when a line connects the origin point and the middle point of this pair is also midperpendiculars, so the problem will become finding a line go through origin point and also midperpendiculars of as much as possible pairs.
So we will solve this problem by following below steps:
+ Find all middle of two points have equal distance from origin.
+ Two points is line up if they cotangent is equal, so we will find the maximum number of points have equal cotangent, this is the result
public class Point {
public double x;
public double y;
public Point(double x, double y) {
this.x = x;
this.y = y;
}
// calculate distance without sqrt
public double distance(Point other) {
return (this.x  other.x) * (this.x  other.x) + (this.y  other.y) * (this.y  other.y);
}
}
public int countPairs(Point[] points) {
// create a counter
Map<Double, Integer> counter = new HashMap<Double, Integer>();
int n = points.length;
Point origin = new Point(0.0, 0.0);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// get the middle point if point[i] and point[j] have equal distance with origin
if (points[i].distance(origin) == points[j].distance(origin)) {
Point middle = new Point((points[i].x + points[j].x) / 2, (points[i].y + points[j].y) / 2);
double cot = middle.x / middle.y;
if (cot == 1.0) {
int x = 0;
}
int value = 0;
if (counter.containsKey(cot)) {
value = counter.get(cot);
}
counter.put(cot, value + 1);
}
}
}
// finding the maximum middle point have same cotangent value
int answer = 0;
for (double key : counter.keySet()) {
answer = Math.max(answer, counter.get(key));
}
return answer;
}

techinterviewquestion.com
February 12, 2016 Thanks you, I'll assume that we can only fold one time and this line must go through the origin.
 techinterviewquestion.com February 12, 2016Hi ritikashah017, please try to input as my code below for testing your example. In my machine, it's show result is 11 too.
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int count = sc.nextInt();
Person[] persons = new Person[count];
for (int i = 0; i < count; i++) {
int type = sc.nextInt();
double height = sc.nextDouble();
if (type == 7) {
persons[i] = new Person(height, PersonType.SEVEN_YEAR_OLD);
} else if (type == 8) {
persons[i] = new Person(height, PersonType.EIGHT_YEAR_OLD);
} else {
persons[i] = new Person(height, PersonType.TEACHER);
}
}
System.out.println(numberOfSwap(persons));
}

techinterviewquestion.com
February 12, 2016 Hi ritikashah017, please input as code below. It's return 11 as your example.
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int count = sc.nextInt();
Person[] persons = new Person[count];
for (int i = 0; i < count; i++) {
int type = sc.nextInt();
double height = sc.nextDouble();
if (type == 7) {
persons[i] = new Person(height, PersonType.SEVEN_YEAR_OLD);
} else if (type == 8) {
persons[i] = new Person(height, PersonType.EIGHT_YEAR_OLD);
} else {
persons[i] = new Person(height, PersonType.TEACHER);
}
}
System.out.println(numberOfSwap(persons));
}

techinterviewquestion.com
February 12, 2016 You will realize that when you want to move a person in position j to position i, our problem will become remove a person in position j and add it to position i with cost is abs(i  j). This means we can use insert sort to solve this problem.
We can solve this problem by following steps below:
+ Take all seven year old students and the teacher to the left and arranged them.
+ Store all remains eight year old students and arranged latter.
Example:
The initial class:
(1, E) (3, S) (1, T) (9, S) (2, S) (1, E) (2, E)
Add student 2 to 1
(3, S) (1, E) (1, T) (9, S) (2, S) (1, E) (2, E)  cost: 1
Add student 4 to 2
(3, S) (9, S) (1, E) (1, T) (2, S) (1, E) (2, E)  cost: 2
Add student 5 to 2
(2, S) (3, S) (9, S) (1, E) (1, T) (1, E) (2, E)  cost: 4
Add teacher to end of seven year old students
(2, S) (3, S) (9, S) (1, T) (1, E) (1, E) (2, E)  cost: 1
Add student 7 to 5
(2, S) (3, S) (9, S) (1, T) (2, E) (1, E) (1, E)  cost: 2
Final answer is: 10
// create enum person type for teacher,
// seven year old students, eight year old students
public enum PersonType {
TEACHER, SEVEN_YEAR_OLD, EIGHT_YEAR_OLD;
}
// create class Person. A person can be teacher,
// 7 year old student or 8 year old student
public class Person {
public int height;
public PersonType type;
public Person(int height, PersonType type) {
this.height = height;
this.type = type;
}
}
public int numberOfSwap(Person[] persons) {
// let use example (1, E) (3, S) (1, T) (9, S) (2, S) (1, E) (2, E)
// for easy understand
// init two list:
// + one for arranging all 7 year old students
// + one for store all remains 8 year old students
List<Person> arrangedStudent7 = new ArrayList<Person>();
List<Person> notArrangedStudent8 = new ArrayList<Person>();
int n = persons.length;
int answer = 0;
// for determine we have met teacher
boolean meetTeacher = false;
// in this step we will swap all student year old to
// the left of teacher and arranged them.
// This mean after this loop we will have:
// (2, S) (3, S) (9, S) (1, T) (1, E) (1, E) (2, E).
//
// List arrangedStudent7 will store: (2, S) (3, S) (9, S)
// List notArrangedStudent8 will store: (1, E) (1, E) (2, E)
for (int i = 0; i < n; i++) {
if (persons[i].type == PersonType.SEVEN_YEAR_OLD) {
// if list arrangedStudent7 is empty,
// add the first student to position 0
if (arrangedStudent7.isEmpty()) {
answer += i;
arrangedStudent7.add(persons[i]);
}
// if not we use binary search to insert current student to list
else {
int left = 0;
int right = arrangedStudent7.size()  1;
while (right  left > 1) {
int mid = (right + left) / 2;
if (persons[mid].height > persons[i].height) {
right = mid;
} else {
left = mid;
}
}
if (persons[right].height <= persons[i].height) {
answer += i  right  1;
arrangedStudent7.add(right + 1, persons[i]);
} else if (persons[left].height <= persons[i].height) {
answer += i  left  1;
arrangedStudent7.add(left + 1, persons[i]);
} else {
answer += i;
arrangedStudent7.add(0, persons[i]);
}
}
// if we met teacher, this mean current 7 year old student is in the right
// of teacher then we must swap to the left of teacher, so the answer increase by one.
if (meetTeacher) {
answer++;
}
} else if (persons[i].type == PersonType.EIGHT_YEAR_OLD) {
notArrangedStudent8.add(persons[i]);
// if we still not meet teacher, this mean current 8 year old student is in the left
// of teacher then we must swap to the right of teacher, so the answer increase by one.
if (!meetTeacher) {
answer++;
}
} else {
meetTeacher = true;
}
}
// currently we arranged all 7 year old students and the teacher
// the remain task is arrange all 8 year old students by using
// binary search as above.
List<Person> arrangedStudent8 = new ArrayList<Person>();
for (int i = 0; i < notArrangedStudent8.size(); i++) {
Person currentStudent = notArrangedStudent8.get(i);
if (arrangedStudent8.isEmpty()) {
arrangedStudent8.add(currentStudent);
} else {
int left = 0;
int right = arrangedStudent8.size()  1;
while (right  left > 1) {
int mid = (right + left) / 2;
if (notArrangedStudent8.get(mid).height < currentStudent.height) {
right = i;
} else {
left = i;
}
}
if (notArrangedStudent8.get(right).height >= currentStudent.height) {
answer += i  right  1;
} else if (notArrangedStudent8.get(left).height >= currentStudent.height) {
answer += i  left  1;
} else {
answer += i;
}
}
}
return answer;
}

techinterviewquestion.com
February 12, 2016 Excuse, I have some questions. We can fold many times or only one time? Is it required the folding line must go through the origin or not?
 techinterviewquestion.com February 12, 2016Excuse, can you explain why the output like that? I don't understand.
 techinterviewquestion.com February 12, 2016Let's check the examples again, as you see our string can shuffle when the maximum existed character in s is less than (the length of s + 1) / 2.
For examples:
apple => aplpe => valid
apppe => papep => valid
appp => invalid
My solution:
Time: O(n)
Mem: O(1)
public boolean canShuffle(char[] s) {
// initial counter array
int[] counter = new int[300];
// count the number of character in s
for (char c : s) {
counter[c]++;
}
// get the maximum from counter
int maxExistedCharacter = 0;
for (char c = 'a'; c <= 'z'; c++) {
maxExistedCharacter = Math.max(counter[c], maxExistedCharacter);
}
// s can shuffle when the maxExistedCharacter
// less than (length of s + 1) / 2
return maxExistedCharacter <= (s.length + 1) / 2;
}

techinterviewquestion.com
February 12, 2016 Hi nmathur, my program will return false immediately when it meets an invalid brace because this mean string s will be an invalid parenthesis sequence too.
 techinterviewquestion.com February 06, 2016I don't understand what you mean, can you give an example?
 techinterviewquestion.com February 03, 2016Thanks Fred, my solution doesn't correct, I will correct this soon.
 techinterviewquestion.com February 02, 2016Base on your code (Edited as suggestion of Fred):
public static void main (String[] args) {
// When initial value for min, max, SecondMax, SecondMin
// I think it's better if we using 0 (break number)
// than using Integer.MAX_VALUE and Integer.MIN_VALUE
// because there value my be using for input and
// we never meet 0 so it's more easy for us checking is there
// exist the answer or not in the end.
int min = 0;
int max = 0;
int SecondMax = 0;
int SecondMin = 0;
Scanner s = new Scanner(System.in);
while (true) {
System.out.print("Enter a Value: ");
int val = s.nextInt();
if (val == 0) {
break;
}
// when a value less than or equal min val,
// this value will be new min and current min value
// may be second min value.
// Be careful with equals value as: 2 2 3 3 3
// so we using equal there.
if (min == 0  val <= min) {
if (SecondMin == 0  SecondMin > min) {
SecondMin = min;
}
min = val;
} else if (SecondMin == 0  (val >= min && val < SecondMin)) {
SecondMin = val;
}
// as min value
if (max == 0  val >= max) {
if (SecondMax == 0  SecondMax > max) {
SecondMax = max;
}
max = val;
} else if (SecondMax == 0  (val <= max && val > SecondMax)) {
SecondMax = val;
}
}
// be careful with edge case, there is less than 2 element
// in this case we don't have second smallest and largest
// and may be we don't have smallest and largest.
if (min != 0) {
System.out.println("The smallest number is: " + min);
} else {
System.out.println("We don't have smallest number.");
}
if (max != 0) {
System.out.println("The largest number is: " + max);
} else {
System.out.println("We don't have largest number.");
}
if (SecondMin != 0) {
System.out.println("The second smallest number is: " + SecondMin);
} else {
System.out.println("We don't have second smallest number.");
}
if (SecondMax != 0) {
System.out.println("The second largest number is: " + SecondMax);
} else {
System.out.println("We don't have second largest number.");
}
}

techinterviewquestion.com
February 02, 2016 Yes. I think so.
 techinterviewquestion.com February 01, 2016public class Node {
public Node left = null;
public Node right = null;
public Node(Node left, Node right) {
this.left = left;
this.right = right;
}
}
public int maxHeight(Node x) {
if (x == null) {
return 0;
}
return Math.max(maxHeight(x.left), maxHeight(x.right)) + 1;
}

techinterviewquestion.com
January 31, 2016 As I understand the problem is:
You're given an array has n elements and a number k. Output all the combination such that sum is equal k and each element is used at most one time.
Examples:
Input:
array = {6, 4, 4, 3, 1, 7}
k = 10
Output (any order):
6 4
6 3 1
3 7
We can use a data structure stack to solve this problem. My Java code:
Time O(n)
Space O(n)
private boolean isValidParenthesis(char[] s) {
// assume we have a map contains all type of parenthesis
Map<Character, Character> parenthesisType = new HashMap<Character, Character>();
parenthesisType.put('{', '}');
parenthesisType.put('(', ')');
parenthesisType.put('[', ']');
// initial a stack
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < s.length; i++) {
// if s[i] is a valid open parenthesis, push to stack
if (parenthesisType.containsKey(s[i])) {
stack.push(s[i]);
}
// if not, this may be a close parenthesis, so
// check the top of stack, if it's same type
// with s[i], remove this top open parenthesis
else if (!stack.empty() && parenthesisType.get(stack.peek()) == s[i]) {
stack.pop();
}
// if this parenthesis not exist or stack is empty, return false
else {
return false;
}
}
// if our stack is empty, this mean s is valid parenthesis
return stack.isEmpty();
}

techinterviewquestion.com
January 31, 2016 Open Chat in New Window
My Java solution.
 techinterviewquestion.com July 11, 2017