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();
}
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
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;
}
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)
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, "")
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();
}
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();
}
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;
}
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)
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
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;
}
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();
}
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);
}
}
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
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 [0-999]
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 [0-999], 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;
}
}
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;
}
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));
}
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));
}
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;
}
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;
}
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.");
}
}
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;
}
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();
}
My Java solution.
- techinterviewquestion.com July 11, 2017