Kevin
BAN USER- 3of 3 votes
AnswersImplement LookAndSay function. For example, first, let user input a number, say 1. Then, the function will generate the next 10 numbers which satisfy this condition:
- Kevin in United States
1, 11,21,1211,111221,312211...
explanation: first number 1, second number is one 1, so 11. Third number is two 1(previous number), so 21. next number one 2 one 1, so 1211 and so on...| Report Duplicate | Flag | PURGE
Epic Systems Software Engineer / Developer Algorithm
Still Use QuickSort. The only difference is comparison condition.
public class ConcatSort {
public static void quickSort(int[] array) {
quickSortT(array, 0, array.length - 1);
}
public static void quickSortT(int[] array, int left, int right) {
if (left < right) {
int pivotIdx = (int) (Math.random() * (right - left)) + left;
int newPivotIdx = partition(array, left, right, pivotIdx);
quickSortT(array, left, newPivotIdx - 1);
quickSortT(array, newPivotIdx + 1, right);
}
}
private static int partition(int[] array, int left, int right, int pivotIdx) {
int pivotValue = array[pivotIdx];
swap(array, right, pivotIdx);
int storedIdx = left;
for (int i = left; i < right; i++) {
// only different part with normal quick sort partition
int result = compAfterExpand(array[i], pivotValue);
if (result == -1) {
// array[i] < pivotValue
swap(array, i, storedIdx);
storedIdx++;
}
}
swap(array, storedIdx, right);
return storedIdx;
}
private static int compAfterExpand(int num, int pivotValue) {
String numStr = String.valueOf(num);
String pivotStr = String.valueOf(pivotValue);
int diff = pivotStr.length() - numStr.length();
if (diff < 0) {
// expand pivotStr
int n = -diff;
while (n > 0) {
pivotStr = pivotStr.concat(""
+ pivotStr.charAt(pivotStr.length() - 1));
n--;
}
} else if (diff > 0) {
// expand numStr
int n = diff;
while (n > 0) {
numStr = numStr.concat("" + numStr.charAt(numStr.length() - 1));
n--;
}
}
if (Integer.parseInt(numStr) > Integer.parseInt(pivotStr)) {
return -1;
}
return 0;
}
private static void swap(int[] array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
public static void sortByConcat(int[] array) {
if (array == null || array.length <= 1) {
return;
}
quickSort(array);
}
public static void main(String[] args) {
int[] array = { 4, 94, 9, 14, 1 };
sortByConcat(array);
for (int i : array) {
System.out.print(i + "\t");
}
}
}
public class StarPattern {
public static boolean isMatch(String string, String pattern) {
boolean isMatch = true;
String[] patterns = pattern.split("\\*");
int index = 0;
int i;
for (i = 0; i < patterns.length; i++) {
if (string.substring(index).indexOf(patterns[i]) == -1) {
isMatch = false;
return isMatch;
}
index += string.substring(index).indexOf(patterns[i])
+ patterns[i].length();
}
if (i != patterns.length) {
isMatch = false;
}
// corner case detection
if (pattern.charAt(0) != '*') {
isMatch = string.startsWith(patterns[i-1]);
}
if (pattern.charAt(pattern.length() - 1) != '*') {
isMatch = string.endsWith(patterns[i-1]);
}
return isMatch;
}
public static void main(String[] args) {
String string = "adsfabcxyzdefgh.docx";
// String string = "adsfabcxyzdefgh.do.docxyz";
String pattern = "*abc*def*.doc*";
// String string = "abcdeabchiabc";
// String pattern = "*abc";
System.out.println(isMatch(string, pattern));
}
}
import java.util.LinkedList;
import java.util.Stack;
public class Logs {
LinkedList<LogEntry> entries;
public class LogEntry {
String funName;
int timestamp;
String type;
public LogEntry(String funName, int timestamp, String type) {
super();
this.funName = funName;
this.timestamp = timestamp;
this.type = type;
}
@Override
public String toString() {
return funName + " " + timestamp + " " + type;
}
}
public Logs() {
super();
entries = new LinkedList<LogEntry>();
LogEntry e1 = new LogEntry("foo", 1, "start");
LogEntry e2 = new LogEntry("foo2", 3, "start");
LogEntry e3 = new LogEntry("foo", 5, "start");
LogEntry e4 = new LogEntry("foo", 8, "end");
LogEntry e5 = new LogEntry("foo2", 12, "end");
LogEntry e6 = new LogEntry("foo", 20, "end");
entries.add(e1);
entries.add(e2);
entries.add(e3);
entries.add(e4);
entries.add(e5);
entries.add(e6);
}
public int calElapse(String functionName) {
int elapse = 0;
Stack<LogEntry> stack = new Stack<LogEntry>();
for (int i = 0; i < entries.size(); i++) {
LogEntry entry = entries.get(i);
if (!stack.isEmpty() && stack.peek().funName.equals(functionName)) {
elapse += (entry.timestamp - entries.get(i - 1).timestamp);
}
if (entry.type.equals("end") && stack.peek().type.equals("start")
&& entry.funName.equals(stack.peek().funName)) {
stack.pop();
} else {
stack.push(entry);
}
}
return elapse;
}
public static void main(String[] args) {
Logs logs = new Logs();
System.out.println(logs.calElapse("foo"));
}
}
Based on @eugene.yarovoi's way. I think we could get further answer.
if( a<p && b < q ){
return (p+q)!/(p!q!) - (a+b)!/(a!b!)
}else if(a == p && b < q){
return (p+q)!/(p!q!) - (p+q-b)!/(p!(q-b)!)
}else if( a < p && b == q){
return (p+q)!/(p!q!) - (p+q-1)!/(q!(p-a)!)
}else{
//remove all the matrix. We only have one left way.
return 1;
}
import java.util.Stack;
public class QueueByStacks {
Stack<Integer> master;
Stack<Integer> slave;
public QueueByStacks() {
super();
master = new Stack<Integer>();
slave = new Stack<Integer>();
}
public void enque(int element){
master.add(element);
}
public Integer deque(){
if(slave.isEmpty()){
while(!master.isEmpty()){
slave.add(master.pop());
}
}else{
return slave.pop();
}
if(slave.isEmpty()){
return null;
}else{
return slave.pop();
}
}
public static void main(String[] args) {
QueueByStacks queue = new QueueByStacks();
queue.enque(3);
queue.enque(4);
System.out.println(queue.deque());
queue.enque(5);
System.out.println(queue.deque());
System.out.println(queue.deque());
System.out.println(queue.deque());
}
}
My Solution:
I still use 93,143,913 => (5,141,67,105)
93143913 = 5*2^24+141*2^16+67*2^8+105*2^0
we calculate 93,143,913 % 20
start from right(because we could reuse 2^8%20):
105%20 = 5 2^0%20 = 1, so for 105*2^0, the remainder should be 5*1 = 5
67%20 = 7 2^8%20 = 16, so for 67*2^8, the remainder should be (7*16)%20 = 12
141%20 = 1 2^16%20 = 16, so for 141*2^16, the remainder should be (1*16)%20 = 16
5%20 = 5 2^24%20 = 16, so for 5*2^24, the remainder should be (5*16)%20 = 0
at last, (0+16+12+5)%20 = 13
It is equal with original number modulo 20;
Please verify it!
What's the time complexity time of my code?
public class RemoveWhiteSpace {
public static void removeSpace(char[] string) {
int spacePtr = 0;
while(spacePtr < string.length && string[spacePtr] != ' '){
spacePtr++;
}
int index = 0;
for(index = spacePtr;index < string.length; index++){
if(string[index] == ' '){
continue;
}else{
swap(string,spacePtr,index);
while(spacePtr < string.length && string[spacePtr] != ' '){
spacePtr++;
}
}
}
while(spacePtr < string.length){
string[spacePtr] = 0;
spacePtr++;
}
for(char c:string){
System.out.print(c);
}
System.out.println();
}
private static void swap(char[] string, int spacePtr, int index) {
char tmp = string[spacePtr];
string[spacePtr] = string[index];
string[index] = tmp;
}
public static void main(String[] args) {
removeSpace(" ab bc d".toCharArray());
removeSpace("ab ed d d".toCharArray());
}
}
- Kevin March 02, 2013This is one of the interview question I met before. The interviewer needs me to implement an algo with O(1) space complexity. I think my solution is O(1) now; Yet it seems the time complexity is O(N).
public class ReverseWord {
public static void reverseWords(char[] words) {
int head = 0;
int tail = 0;
while (tail < words.length) {
while (tail<words.length && words[tail] != ' ') {
tail++;
}
reverseWord(words,head,tail-1);
tail++;
head = tail;
}
}
private static void reverseWord(char[] words,int head,int tail) {
if (words == null || words.length == 0) {
return;
}
while(head < tail){
char tmp = words[head];
words[head++] = words[tail];
words[tail--] = tmp;
}
}
public static void main(String[] args) {
reverseWords("This is a cat".toCharArray());
}
}
import java.util.Stack;
public class ReverseLinkedListInParts {
Node head;
int size;
class Node {
int value;
Node next;
public Node(int value) {
super();
this.value = value;
this.next = null;
}
}
public ReverseLinkedListInParts() {
super();
head = null;
size = 0;
}
public void add(int e) {
Node newnode = new Node(e);
if (head == null) {
head = newnode;
size++;
return;
}
Node ptr = head;
while (ptr.next != null) {
ptr = ptr.next;
}
ptr.next = newnode;
size++;
}
public void reverseInPart(int parts) {
if (parts > size || parts < 1) {
System.out.println("The part is out of range. Cannot reverse");
return;
}
Node headPtr = head;
while (headPtr != null) {
int n = parts;
Node tailPtr = headPtr;
while (n > 1 && tailPtr.next != null) {
tailPtr = tailPtr.next;
n--;
}
reverse(headPtr,tailPtr);
headPtr = tailPtr.next;
}
}
private void reverse(Node headPtr, Node tailPtr) {
Stack<Integer> stack = new Stack<Integer>();
Node ptr = headPtr;
while(ptr != tailPtr){
stack.push(ptr.value);
ptr = ptr.next;
}
stack.push(tailPtr.value);
ptr = headPtr;
while(ptr != tailPtr){
ptr.value = stack.pop();
ptr = ptr.next;
}
tailPtr.value = stack.pop();;
}
public void print() {
Node ptr = head;
while (ptr != null) {
System.out.print(ptr.value + "\t");
ptr = ptr.next;
}
System.out.println();
}
public static void main(String[] args) {
ReverseLinkedListInParts ll = new ReverseLinkedListInParts();
ll.add(3);
ll.add(1);
ll.add(5);
ll.add(7);
ll.add(2);
ll.add(4);
ll.add(6);
ll.print();
ll.reverseInPart(8);
ll.print();
}
}
My idea is : use a hashtable.
Key : Value:
Node.Value Node.address
Do in-order traverse. At the same time, we store corresponding key and value pair into hashtable.
After that: we have a list L like 123455555(6)6677
We have known the address of that Node N, we want its successor.
We compare the address in L until we find it, then we return the next one.
You could change denomination array as you want. Please test it. Thank you:)
public class VendingMachine {
static int[] deno = {20,15,10,5,2,1};
public static void change(int amount){
int[] tab = new int[amount + 1];
tab[0] = 0;
for(int i=1;i<=amount;i++){
int min = Integer.MAX_VALUE;
for(int k=0;k<deno.length;k++){
if(i - deno[k]>=0){
int tmp = tab[i-deno[k]] + 1;
if(tmp < min){
min = tmp;
}
}
}
tab[i] = min;
}
System.out.println(tab[amount]);
return;
}
public static void main(String[] args) {
change(30);
}
}
public class SortedLinkedList {
Node head;
class Node{
int value;
Node next;
public Node(int value) {
super();
this.value = value;
this.next = null;
}
}
public void add(int value){
Node newnode = new Node(value);
if(head == null){
head = newnode;
return;
}
Node ptr = head;
Node prev = null;
while(ptr != null && value > ptr.value){
prev = ptr;
ptr = ptr.next;
}
if(ptr == head){
newnode.next = head;
head = newnode;
return;
}
if(ptr == null){
prev.next = newnode;
return;
}
newnode.next = ptr;
prev.next = newnode;
}
public void print(){
Node ptr = head;
if(ptr == null){
return;
}
while(ptr != null){
System.out.print(ptr.value);
ptr = ptr.next;
}
}
/**
* @param args
*/
public static void main(String[] args) {
SortedLinkedList ll = new SortedLinkedList();
ll.add(3);
ll.add(9);
ll.add(6);
ll.add(7);
ll.add(3);
ll.print();
}
}
import java.util.Stack;
public class CheckBalance {
public static boolean check(String str) {
if (str == null || str.length() == 0) {
return true;
}
char[] strs = str.toCharArray();
Stack<Character> stack = new Stack<Character>();
for (char c : strs) {
if(!check(c)){
return false;
}
if(checkOpeningSymbol(c)){
stack.push(c);
}
if(checkEndingSymbol(c)){
stack.push(c);
if(stack.size() < 2)
return false;
char right = stack.pop();
char left = stack.pop();
if(!match(right,left)){
return false;
}
}
}
if(stack.isEmpty()){
return true;
}
return false;
}
private static boolean match(char right, char left) {
if(right == ')' && left == '(' ){
return true;
}
if(right == '}' && left == '{' ){
return true;
}
if(right == ']' && left == '[' ){
return true;
}
return false;
}
private static boolean check(char c) {
if (c == ')' || c == '}' || c == ']' || c == '{' || c == '['
|| c == '(') {
return true;
}
return false;
}
private static boolean checkEndingSymbol(Character peek) {
if (peek == ')' || peek == '}' || peek == ']') {
return true;
}
return false;
}
private static boolean checkOpeningSymbol(Character peek) {
if (peek == '{' || peek == '[' || peek == '(') {
return true;
}
return false;
}
public static void main(String[] args) {
// String str = "{()[]}";
// String str = "(({)})";
String str = "{())";
System.out.println(check(str));
}
}
Use binary search tree is the most efficient way to solve this problem.
In Java, we have TreeSet.
You could also implement your own binary tree and add data into this tree.
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;
import java.util.TreeSet;
public class MergeSet {
public static Set<Integer> mergeSets(LinkedList<Integer> set1, LinkedList<Integer> set2){
Set<Integer> resultSet = new TreeSet<Integer>();
for(int i=0;i<set1.size();i++){
int value = set1.get(i);
if(value > 0){
resultSet.add(value);
}
}
for(int i=0;i<set2.size();i++){
int value = set2.get(i);
if(value > 0){
resultSet.add(value);
}
}
return resultSet;
}
public static void main(String[] args){
LinkedList<Integer> set1 = new LinkedList<Integer>();
set1.add(3);
set1.add(4);
set1.add(-1);
set1.add(0);
LinkedList<Integer> set2 = new LinkedList<Integer>();
set2.add(3);
set2.add(2);
set2.add(-3);
set2.add(4);
Set<Integer> result = mergeSets(set1,set2);
System.out.println(result);
}
}
case1: null (return -1)
case2: ""(empty) (return -1)
case3: "aaabbbbbbcddccc" (return 3)
case4: "vfdaaafgggbbb" (same largest block, return start position of first block)
public class RepeatedChar {
//given a string, return start position of largest repeated characters
public static int posOfLargestRepeatedChars(String string){
if(string == null || string.length() == 0){
return -1;
}
char[] str = string.toCharArray();
int start = 0;
int potential_start = 0;
int count = 1;
int maxCount = 1;
for(int i=1;i<str.length;i++){
if(str[i] == str[i - 1]){
count++;
if(count > maxCount){
maxCount = count;
start = potential_start;
}
}else{
potential_start = i;
count = 1;
}
}
return start;
}
public static void main(String[] args) {
// String string = "aaaaabbbbbbbbbbbbbbefxsscc";
String string = "abaacabb";
System.out.println(posOfLargestRepeatedChars(string));
}
}
import java.util.Stack;
public class BoolMatrix {
int M;
int N;
Square matrix[][];
class Square{
boolean bool;
int x;
int y;
boolean isVisited;
public Square(boolean bool, int x, int y) {
super();
this.bool = bool;
this.x = x;
this.y = y;
this.isVisited = false;
}
@Override
public String toString(){
if(bool){
return "T";
}else{
return "F";
}
}
}
public BoolMatrix(int m, int n) {
super();
M = m;
N = n;
matrix = new Square[M][N];
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (Math.random() < 0.5) {
matrix[i][j] = new Square(true,i,j);
} else {
matrix[i][j] = new Square(false,i,j);
}
}
}
}
public void print() {
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
System.out.print(matrix[i][j] + "\t");
}
System.out.println();
}
}
public int countRegion() {
int count = 0;
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if(!matrix[i][j].isVisited){
if(matrix[i][j].bool){
count++;
Stack<Square> stack = new Stack<Square>();
stack.push(matrix[i][j]);
while(!stack.isEmpty()){
Square s = stack.pop();
Square[] neighbors = getNeighbors(s);
for(Square squ:neighbors){
if(squ != null && !squ.isVisited){
stack.push(squ);
squ.isVisited = true;
}
}
}
}else{
matrix[i][j].isVisited = true;
}
}
}
}
System.out.println(count);
return count;
}
private Square[] getNeighbors(Square s) {
Square[] neighbors = new Square[4];
for (int k = 0; k < 4; k++) {
neighbors[k] = null;
}
if (s.x - 1 >= 0 && matrix[s.x - 1][s.y].bool) {
//top
neighbors[0] = matrix[s.x - 1][s.y];
}
if (s.x + 1 < M && matrix[s.x + 1][s.y].bool) {
//bottom
neighbors[1] = matrix[s.x +1][s.y];
}
if (s.y - 1 >= 0 && matrix[s.x][s.y - 1].bool) {
//left
neighbors[2] = matrix[s.x][s.y - 1];
}
if (s.y + 1 < N && matrix[s.x][s.y + 1].bool) {
//left
neighbors[3] = matrix[s.x][s.y + 1];
}
return neighbors;
}
public static void main(String[] args) {
BoolMatrix bm = new BoolMatrix(4, 5);
bm.print();
bm.countRegion();
}
}
import java.util.HashSet;
import java.util.Set;
public class RemoveChar {
public static void remove(char[] string, Set<Character> set) {
int currPtr = 0;
int ptr = 0;
for(currPtr = 0;currPtr < string.length;currPtr++){
if(set.contains(string[currPtr])){
ptr++;
}else{
string[currPtr - ptr] = string[currPtr];
}
}
while(ptr > 1){
string[currPtr - ptr] = 0;
ptr--;
}
string[currPtr - ptr] = 0;
}
public static void main(String[] args) {
Set<Character> set = new HashSet<Character>();
set.add('a');
set.add('i');
// char[] string = { 'a', 'b', 'c', 'i', 'a', 'b', 'c' };
char[] string = { 'a', 'i', 'a'};
remove(string, set);
for (char c : string) {
System.out.print(c + " ");
}
}
}
import java.util.LinkedList;
public class CombineLinkedList {
public static LinkedList<Integer> combine(LinkedList<Integer> l1,
LinkedList<Integer> l2) {
if (l1 == null && l2 == null) {
return null;
} else if (l1 == null) {
return l2;
} else if (l2 == null) {
return l1;
}
// handle common cases
LinkedList<Integer> result = new LinkedList<Integer>();
int size1 = l1.size();
int size2 = l2.size();
int size = size1 < size2 ? size1 : size2;
for (int i = 0; i < size; i++) {
result.add(l1.get(i));
result.add(l2.get(i));
}
if (size1 < size2) {
for (int i = size1; i < size2; i++) {
result.add(l2.get(i));
}
} else if (size1 > size2) {
for (int i = size2; i < size1; i++) {
result.add(l1.get(i));
}
} else {
;
}
return result;
}
public static void main(String[] args) {
LinkedList<Integer> list1 = new LinkedList<Integer>();
list1.add(1);
list1.add(2);
list1.add(3);
list1.add(4);
LinkedList<Integer> list2 = new LinkedList<Integer>();
list2.add(5);
list2.add(6);
list2.add(7);
LinkedList<Integer> list = combine(list1, list2);
System.out.println(list);
}
}
public class LargestBSTSubTree {
class BinaryTree {
int data;
BinaryTree left;
BinaryTree right;
}
public BinaryTree findLagestSubTree(BinaryTree root) {
BinaryTree largestBST = null;
Integer min = Integer.MAX_VALUE;
Integer max = Integer.MIN_VALUE;
Integer maxNodes = Integer.MIN_VALUE;
findLargestBSTSubTreeUtil(root, min, max, maxNodes, largestBST);
return largestBST;
}
private int findLargestBSTSubTreeUtil(BinaryTree root, Integer min,
Integer max, Integer maxNodes, BinaryTree largestBST) {
if (root == null) {
return 0;
}
boolean isBST = true;
int leftBSTNodes = findLargestBSTSubTreeUtil(root.left, min, max,
maxNodes, largestBST);
int currMin = (leftBSTNodes == 0) ? root.data : min;
if (leftBSTNodes == -1 || (leftBSTNodes != 0 && root.data <= max)) {
isBST = false;
}
int rightBSTNodes = findLargestBSTSubTreeUtil(root.right, min, max,
maxNodes, largestBST);
int currMax = (rightBSTNodes == 0) ? root.data : max;
if (rightBSTNodes == -1 || (rightBSTNodes != 0 && root.data >= min)) {
isBST = false;
}
if (isBST) {
min = currMin;
max = currMax;
int totalNodes = leftBSTNodes + rightBSTNodes + 1;
if (totalNodes > maxNodes) {
maxNodes = totalNodes;
largestBST = root;
}
return totalNodes;
} else {
return -1;
}
}
public static void main(String[] args) {
}
}
public class RandList {
private static int Random(int n) {
return (int) (Math.random() * n + 1);
}
public static void printRandList(int n) {
int[] array = new int[n];
for (int i = 0; i < n; i++) {
array[i] = i;
;
}
// shuffle array
for (int i = 0; i < n; i++) {
int index = (Random(n) + i) % n;
int tmp = array[i];
array[i] = array[index];
array[index] = tmp;
}
for (int i : array) {
System.out.print(i + "\t");
}
System.out.println();
}
public static void main(String[] args) {
printRandList(5);
}
}
import java.util.ArrayList;
public class SubMatrix {
int[][] matrix;
int M;
public SubMatrix(int m) {
super();
M = m;
matrix = new int[M][M];
for (int i = 0; i < M; i++) {
for (int j = 0; j < M; j++) {
matrix[i][j] = (int) (Math.random() * 10 + 1);
}
}
}
public void subMatrix(int subNum) {
if (subNum <= 0 || M % subNum != 0) {
System.out.println("cannot extract individal blocks");
return;
}
int blockSize = M / subNum;
ArrayList<Integer>[] lists = new ArrayList[blockSize * blockSize];
for (int i = 0; i < blockSize * blockSize; i++) {
lists[i] = new ArrayList<Integer>();
}
for (int index = 0; index < blockSize * blockSize; index++) {
for (int k = 0; k < subNum * subNum; k++) {
int row = index / blockSize * subNum + k / subNum;
int column = index % blockSize * subNum + k % subNum;
lists[index].add(k, matrix[row][column]);
}
}
for (int index = 0; index < blockSize * blockSize; index++) {
System.out.println(lists[index]);
}
}
public void print() {
for (int i = 0; i < M; i++) {
for (int j = 0; j < M; j++) {
System.out.print(matrix[i][j] + "\t");
}
System.out.println();
}
}
public static void main(String[] args) {
SubMatrix sm = new SubMatrix(6);
sm.print();
sm.subMatrix(3);
}
}
I think this solution is correct. Please test it.
public class AppendLinkedList {
int size;
Node head;
Node tail;
class Node {
int value;
Node next;
public Node(int value) {
super();
this.value = value;
this.next = null;
}
}
public void add(int value) {
Node n = new Node(value);
if (head == null) {
head = n;
tail = n;
}
tail.next = n;
tail = n;
size++;
}
public void append(int n) {
if (n > size || n < 0) {
System.out.println("n is out of range!");
return;
}
Node ptr = head;
int index = size - n - 1;
if(index == -1){
return;
}
while (index > 0) {
ptr = ptr.next;
index--;
}
tail.next = head;
head = ptr.next;
tail = ptr;
ptr.next = null;
}
public void print() {
Node ptr = head;
while (ptr != null) {
System.out.print(ptr.value + "\t");
ptr = ptr.next;
}
System.out.println();
}
public static void main(String[] args) {
AppendLinkedList l = new AppendLinkedList();
l.add(1);
l.add(2);
l.add(3);
l.add(4);
l.add(5);
l.add(6);
l.print();
l.append(0);
l.print();
}
}
Perfect solution
import java.util.LinkedList;
import java.util.Queue;
public class BinarySearchTree {
TreeNode root;
class TreeNode {
double value;
TreeNode left;
TreeNode right;
public TreeNode(double value) {
super();
this.value = value;
left = null;
right = null;
};
}
public void insert(double value) {
root = insertT(root, value);
}
public TreeNode insertT(TreeNode root, double value) {
if (root == null) {
TreeNode r = new TreeNode(value);
return r;
}
if (value > root.value) {
// right
root.right = insertT(root.right, value);
} else if (value < root.value) {
root.left = insertT(root.left, value);
}
return root;
}
public void inorder() {
inorderT(root);
System.out.println();
}
private void inorderT(TreeNode root) {
if (root == null) {
return;
}
inorderT(root.left);
System.out.print(root.value + "\t");
inorderT(root.right);
}
public int MaxLevel() {
return MaxlevelT(root);
}
private int MaxlevelT(TreeNode root) {
int maxLevel = 0;
if (root == null) {
return maxLevel;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
Queue<TreeNode> slave = new LinkedList<TreeNode>();
maxLevel = 1;
queue.offer(root);
while (!queue.isEmpty()) {
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
slave.offer(node);
}
if (slave.size() > maxLevel) {
maxLevel = slave.size();
}
while (!slave.isEmpty()) {
TreeNode node = slave.poll();
if (node.left != null)
queue.offer(node.left);
if (node.right != null)
queue.offer(node.right);
}
}
return maxLevel;
}
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
bst.insert(5);
bst.insert(4);
bst.insert(2);
bst.insert(6);
bst.insert(3);
bst.insert(1);
bst.insert(7);
bst.insert(8);
bst.insert(4.5);
bst.insert(5.5);
bst.inorder();
System.out.println(bst.MaxLevel());
}
}
@showell30
Hi,
I think 3 children is better than 2 children. Generally speaking, if we have N nodes, a master with N-1 slaves are maybe the best solutions.
For instance, we have N=12 nodes;
binary tree:
1 -- 2 -- 4 -- 8
-- 9
-- 5 -- 10
-- 11
-- 3 -- 6 -- 12
-- 7
Triple tree:
1 -- 2 -- 5
-- 6
-- 7
-- 3 -- 8
-- 9
-- 10
-- 4 -- 11
-- 12
We assume computation time for adding two number is t
Ignore latency.
for binary tree:
T(4) = T(5) = 2 T(6) = 1 T(7) = 0
T(2) = 4 T(3) = 3
T(1) = 6
for triple tree:
T(2) = T(3) = 3
T(4) = 2
T(1) = 6
So the total is the same. Generally speaking, the time should be similar.
Yet the assumption is that we ignore transfer latency.
If we consider latency,triple tree will be better. Because much more data could be transferred concurrently.
Hey Vik,
32 bit doesn't consume 512MB memory if you just use 32 bit to represent integer caz integer just need 32 bit, right?
My idea is like this:
{1,4,2,4,3,2,4,4,5,3,3,2}
each time we receive a new int, we scan the whole array from start to end. We use bit vector to indicate which number is monitoring now and another bit to indicate odd or even. Totally, 33 bit.
eg:
1,4,2,4 last number is 4.
we set bit vector to 28's 0+0100, EvenOddBit = 0
we come across the first 4, EvenOddBit = 1;
we come across the second 4, EvenOddBit = 0;
at last EvenOddBit = 0, no beep;
in the heap, we have a hash table which includes the size of this new address space. So when we free this space, we will know how many space do we need to free.
Address malloc(Byte size){
Address entryAddr = null;
try{
entryAddr = getSizeMemFromHeap(size);
}catch(Exception e){
print(e.getMessage);
System.exit(e.errorCode);
}
HashTable ht = getHashTableEntry();
ht.add(entryAddr,size);
claimAddrNotAvaialble(addr,size);
return entryAddr;
}
void free(Address addr){
if(addr == null){
return;
}
HashTable ht = getHashTableEntry();
Byte size = ht.get(addr);
//tell OS that from addr to addr+size, this address space is available
//we don't need to delete them, just claim it
claimAddrAvaialble(addr,size);
}
smart method(O(n)):
static int NO_NODES_FOUND = 0;
static int ONE_NODES_FOUND = 1;
static int TWO_NODES_FOUND = 2;
public int covers(TreeNode root, treeNode p, TreeNode q){
int ret = NO_NODES_FOUND;
if(root == null){
return ret;
}
if(root == p || root == q){
ret += 1;
}
ret += covers(root.left,p,q);
if(ret == TWO_NODES_FOUND){
return ret;
}
return ret+covers(root.right,p,q);
}
public TreeNode commonAncestor(TreeNode root, TreeNode p, TreeNode q){
if( (p == q) && (root.left == p || root.right == q)){
return root;
}
int nodesFromLeft = covers(root.left,p,q);
if(nodesFromLeft == TWO_NODES_FOUND){
if(root.left == p || root.left == q){
return root.left;
}else{
return commonAncestor(root.left,p,q);
}
}else if(nodesFromLeft == ONE_NODES_FOUND){
if(root == p){
return p;
}else if(root == q){
return q;
}
}
int nodesFromRight = covers(root.right,p,q);
if(nodesFromRight == TWO_NODES_FOUND){
if(root.right == p || root.right == q){
return root.right;
}else{
return commonAncestor(root.right,p,q);
}
}else if(nodesFromRight == ONE_NODES_FOUND){
if(root == p){
return p;
}else if(root == q){
return q;
}
}
if(nodesFromLeft == ONE_NODES_FOUND && nodesFromRight == ONE_NODES_FOUND){
return root;
}else{
return null;
}
}
Stupid method:
public TreeNode commonAncestor(TreeNode root, TreeNode p, TreeNode q){
if(covers(root.left,p) && covers(root,q)){
return commonAncestor(root.left, p , q);
}
if(covers(root.right, p) && covers(root.right, q)){
return commonAncestor(root.right, p , q);
}
return root;
}
public boolean covers(TreeNode root, TreeNode n){
if(root == null){
return null;
}
if(root == n){
return true;
}
return covers(root.left,n) || covers(root.right,n);
}
All test cases provided by author succeeds.
public static void expand(char[] chars) {
int currPtr = 0;
while (currPtr < chars.length && chars[currPtr] != 0) {
if (Character.isDigit(chars[currPtr])) {
int tmp = currPtr;
StringBuilder sb = new StringBuilder();
while (tmp<chars.length && Character.isDigit(chars[tmp])) {
sb.append(chars[tmp]);
tmp++;
}
int shift = Integer.parseInt(sb.toString());
char c = chars[currPtr - 1];
if (shift == 1) {
tmp = currPtr;
while (chars[tmp] != 0 && tmp < chars.length - 1) {
chars[tmp] = chars[tmp + 1];
tmp++;
}
chars[tmp] = 0;
} else {
tmp = currPtr + String.valueOf(shift).length();
shift -= 2;
// shift right 'shift' position, make room
if (shift > 0) {
shiftP(chars, tmp, shift);
}
for (int i = currPtr - 1; i <= currPtr + shift; i++) {
chars[i] = c;
}
}
}
currPtr++;
}
}
private static void shiftP(char[] chars, int head, int shift) {
int ptr = 0;
while (chars[ptr] != 0) {
ptr++;
}
ptr--;
for (int i = ptr; i >= head; i--) {
chars[i + shift] = chars[i];
}
}
Still Use Odometer
import java.util.ArrayList;
import java.util.List;
public class Cartesian {
public static void generateCartesian(String[] strs) {
int K = strs.length;
int[] sizes = new int[K];
for (int i = 0; i < sizes.length; i++) {
sizes[i] = strs[i].length();
}
List<Integer> odometer = new ArrayList<Integer>();
for (int index = 0; index < K; index++) {
odometer.add(index, 0);
}
List<Integer> max_indexes = new ArrayList<Integer>();
for (int index = 0; index < K; index++) {
max_indexes.add(index, sizes[index]);
}
while (true) {
// output based on current odometer
for (int index = 0; index < odometer.size(); index++) {
int pos = odometer.get(index);
System.out.print(strs[index].charAt(pos));
}
System.out.println();
// advance odometer
if (!advance_odometer(odometer, max_indexes)) {
break;
}
}
}
private static boolean advance_odometer(List<Integer> odometer,
List<Integer> max_indexes) {
int i = odometer.size() - 1;
while (i >= 0) {
odometer.set(i, odometer.get(i) + 1);
if (odometer.get(i) < max_indexes.get(i)) {
return true;
} else {
// roll over to next index
odometer.set(i, 0);
i = i - 1;
if (i < 0) {
return false;
}
}
}
return false;
}
public static void main(String[] args) {
String[] strs = { "ABCD", "123", "ZX" };
generateCartesian(strs);
}
}
I think this is simple。 Why do we need to consider stable sort or blablabla...
import java.util.Arrays;
class Test implements Comparable<Test> {
String value1;
String value2;
public Test(String value1, String value2) {
super();
this.value1 = value1;
this.value2 = value2;
}
@Override
public int compareTo(Test o) {
if (this.value1.compareTo(o.value1) == 0) {
return this.value2.compareTo(o.value2);
} else {
return this.value1.compareTo(o.value1);
}
}
@Override
public String toString() {
return "value1: " + value1 + " value2:" + value2;
}
}
public class SecondarySorting {
public static void main(String[] args) {
Test[] tests = new Test[10];
tests[0] = new Test("a", "b");
tests[1] = new Test("a", "a");
tests[2] = new Test("a", "b");
tests[3] = new Test("d", "c");
tests[4] = new Test("d", "d");
tests[5] = new Test("d", "a");
tests[6] = new Test("b", "a");
tests[7] = new Test("b", "e");
tests[8] = new Test("c", "a");
tests[9] = new Test("c", "r");
Arrays.sort(tests);
for (Test t : tests) {
System.out.println(t);
}
}
}
public class ReverseWords {
public static void reverseWords(String words){
if(words.length() == 0 || words == null){
return;
}
String[] words_array = words.split(" ");
for(int i=words_array.length - 1;i>=0;i--){
System.out.print(words_array[i]+" ");
}
System.out.println();
}
/**
* @param args
*/
public static void main(String[] args) {
reverseWords("This is a word");
}
}
If there is something wrong, please let me know. Open to test!
import java.util.ArrayList;
import java.util.Stack;
public class LongestIncreasingSequence {
int M;
int N;
Square[][] matrix;
int[][] tab;
class Pair {
int x;
int y;
public Pair(int x, int y) {
super();
this.x = x;
this.y = y;
}
public Pair() {
// TODO Auto-generated constructor stub
}
}
class Square {
private int num;
boolean isVisited;
Square parent;
public int getNum() {
return num;
}
public Square(int num) {
super();
this.num = num;
isVisited = false;
parent = null;
}
@Override
public String toString() {
return String.valueOf(num);
}
}
public LongestIncreasingSequence(int m, int n) {
super();
M = m;
N = n;
matrix = new Square[M][N];
matrix[0][0] = new Square(2);
matrix[0][1] = new Square(3);
matrix[0][2] = new Square(4);
matrix[0][3] = new Square(5);
matrix[1][0] = new Square(4);
matrix[1][1] = new Square(5);
matrix[1][2] = new Square(10);
matrix[1][3] = new Square(11);
matrix[2][0] = new Square(20);
matrix[2][1] = new Square(6);
matrix[2][2] = new Square(9);
matrix[2][3] = new Square(12);
matrix[3][0] = new Square(6);
matrix[3][1] = new Square(7);
matrix[3][2] = new Square(8);
matrix[3][3] = new Square(40);
tab = new int[M][N];
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
tab[i][j] = -1;
}
}
}
public void findLongestIncreasingSeq() {
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
int max = returnLargestNeighbor(i, j);
if (max != -1) {
tab[i][j] = max + 1;
} else {
int len = recursiveFind(i, j);
tab[i][j] = len;
}
}
}
}
private int recursiveFind(int i, int j) {
ArrayList<Pair> allneighbors = getSatisfiedNeighbor(i, j);
if (allneighbors.size() == 0) {
return 1;
}
int[] lens = { 0, 0, 0, 0 };
int k = 0;
for (Pair neighbor : allneighbors) {
lens[k++] = 1 + recursiveFind(neighbor.x, neighbor.y);
}
int max = Integer.MIN_VALUE;
for (int len : lens) {
if (len > max) {
max = len;
}
}
if (max == Integer.MIN_VALUE) {
matrix[i][j].parent = null;
} else if (max == lens[0]) {
// top
matrix[i][j].parent = matrix[i - 1][j];
} else if (max == lens[1]) {
// bottom
matrix[i][j].parent = matrix[i + 1][j];
} else if (max == lens[2]) {
// right
matrix[i][j].parent = matrix[i][j + 1];
} else {
// left
matrix[i][j].parent = matrix[i][j - 1];
}
return max;
}
private ArrayList<Pair> getSatisfiedNeighbor(int i, int j) {
ArrayList<Pair> pairs = new ArrayList<Pair>();
if (i - 1 >= 0
&& matrix[i - 1][j].getNum() + 1 == matrix[i][j].getNum()) {
// top
pairs.add(new Pair(i - 1, j));
}
if (i + 1 < M && matrix[i + 1][j].getNum() + 1 == matrix[i][j].getNum()) {
// bottom
pairs.add(new Pair(i + 1, j));
}
if (j + 1 < N && matrix[i][j + 1].getNum() + 1 == matrix[i][j].getNum()) {
// right
pairs.add(new Pair(i, j + 1));
}
if (j - 1 >= 0
&& matrix[i][j - 1].getNum() + 1 == matrix[i][j].getNum()) {
// left
pairs.add(new Pair(i, j - 1));
}
return pairs;
}
private int returnLargestNeighbor(int i, int j) {
int max = -1;
if (i - 1 >= 0) {
// top
if (matrix[i][j].getNum() == matrix[i - 1][j].getNum() + 1
&& tab[i - 1][j] != -1) {
if (tab[i - 1][j] > max)
max = tab[i - 1][j];
}
}
if (i + 1 < M) {
// bottom
if (matrix[i][j].getNum() == matrix[i + 1][j].getNum() + 1
&& tab[i + 1][j] != -1) {
if (tab[i + 1][j] > max)
max = tab[i + 1][j];
}
}
if (j + 1 < N) {
// right
if (matrix[i][j].getNum() == matrix[i][j + 1].getNum() + 1
&& tab[i][j + 1] != -1) {
if (tab[i][j + 1] > max)
max = tab[i][j + 1];
}
}
if (j - 1 >= 0) {
// left
if (matrix[i][j].getNum() == matrix[i][j - 1].getNum() + 1
&& tab[i][j - 1] != -1) {
if (tab[i][j - 1] > max)
max = tab[i][j - 1];
}
}
return max;
}
public void print() {
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
System.out.print(matrix[i][j] + "\t");
}
System.out.println();
}
}
public void printTab() {
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
System.out.print(tab[i][j] + "\t");
}
System.out.println();
}
}
public void output() {
System.out.println();
Stack<Square> stack = new Stack<Square>();
Pair pair = maxLength();
while (pair != null) {
stack.push(matrix[pair.x][pair.y]);
pair = nextSmallNum(pair);
}
while (!stack.isEmpty()) {
Square s = stack.pop();
System.out.print(s.getNum() + "\t");
}
System.out.println();
}
private Pair nextSmallNum(Pair pair) {
if (tab[pair.x][pair.y] == 1) {
return null;
}
Pair newpair = new Pair();
if (pair.x - 1 >= 0
&& tab[pair.x - 1][pair.y] + 1 == tab[pair.x][pair.y]) {
// top
newpair.x = pair.x - 1;
newpair.y = pair.y;
}
if (pair.x + 1 < M
&& tab[pair.x + 1][pair.y] + 1 == tab[pair.x][pair.y]) {
// bottom
newpair.x = pair.x + 1;
newpair.y = pair.y;
}
if (pair.y + 1 < N
&& tab[pair.x][pair.y + 1] + 1 == tab[pair.x][pair.y]) {
// right
newpair.x = pair.x;
newpair.y = pair.y + 1;
}
if (pair.y - 1 >= 0
&& tab[pair.x][pair.y - 1] + 1 == tab[pair.x][pair.y]) {
// left
newpair.x = pair.x;
newpair.y = pair.y - 1;
}
return newpair;
}
private Pair maxLength() {
Pair pair = new Pair();
int max = Integer.MIN_VALUE;
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (tab[i][j] > max) {
max = tab[i][j];
pair.x = i;
pair.y = j;
}
}
}
return pair;
}
public static void main(String[] args) {
LongestIncreasingSequence seqMatrix = new LongestIncreasingSequence(4,
4);
seqMatrix.print();
seqMatrix.findLongestIncreasingSeq();
System.out.println();
seqMatrix.printTab();
seqMatrix.output();
}
}
RepPacheTanley, Associate at Adobe
Hi , I am Conference service coordinator for the KB Toys company. I Build and maintain relationships with meeting planners and ...
RepHi, I’m Jamie from the Portsmouth USA and I am working as an account manager. I work for a ...
RepErmanStern, Applications Developer at ADP
I am Erman . I am metal finishing-, plating- and coating-machine operators operate and monitor equipment which finishes, plates and coats ...
Repammiwilson5, Personnel at BMO Harris Bank
Hi I am Ammy from Served on a research team for improved customer satisfaction survey process,Moderated focus groups to ...
RepJanie Margreta, Android Engineer at Achieve Internet
JanieMargreta works as a plant operator, an employee who supervises the operation of an industrial plant. Where I have to ...
Repjanicepdaniels1, Backend Developer at Accenture
I decided to become an entrepreneur and work for myself because I wasn't making the money I wanted to ...
RepMariaHobbs, Consultant at Adobe
Hi, I am Maria Hobbs from NewYork.Teach career development courses for designated areas. Develop, evaluate and revise course materials ...
RepShirleyMHansen, Project Leader at Chelsio Communications
I am Physical Therapy Aide with 3 years experience in hospital. I like to build up my knowledge of various ...
Repanneabush, AT&T Customer service email at Accolite software
Hello, I am Anne and I live in Tampa, USA. I am working in a company as a caretaker. I ...
Repmerrittmonique9, Android Engineer at AMD
I am Monique and working in high court from last 20 years.Handel many cases in my career.Build and ...
Repsarahchannah745, Android Engineer at ASAPInfosystemsPvtLtd
Hello, I am an information records clerk.We are responsible for maintaining their company records in a complete and orderly ...
Repritahmixon, Analyst at ADP
Hi, I am a physiotherapy to help people handle everyday problems. I also assist peoples who have issues caused by ...
RepFanieGoode, Consultant at Achieve Internet
I am a Media Library Assistant that provides integrated support for two popular “Multi Language/ Multilingual/ Internationalization” plugins; WPML and ...
Repgoamgivheler, Accountant at Lava
I am working as a nurse in Bali Boer Cafarius. I enjoy relationships with patients and their families. It has ...
@cristian.botau
- Kevin March 03, 2013Your solution is right.
Yet I still cannot deque solution. It seems like a sliding window.
Could you give further explanation for this by using some picture? Thank you.