sh88990
BAN USER- 0of 0 votes
Answers
- sh88990 in United States/* This class will be given a list of words (such as might be tokenized * from a paragraph of text), and will provide a method that takes two * words and returns the shortest distance (in words) between those two * words in the provided text. * Example: * WordDistanceFinder finder = new WordDistanceFinder(Arrays.asList("the", "quick", "brown", "fox", "quick")); * assert(finder.distance("fox","the") == 3); * assert(finder.distance("quick", "fox") == 1); * /
| Report Duplicate | Flag | PURGE
Linkedin Software Engineer / Developer
/*
Find minimum distance between two words (order preserved) in a big string.
For e.g 1. "hello how are you" - distance between "hello" and "you" is 3.
e.g 2. "hello how are hello you" - distance is 1
e.g 3. "you are hello" - distance is -1. Order of "hello" and "you" should be preserved.
e.g 4. "hello how are hello" - distance is -1 since "you" didnt occur even once.
*/
//S is the big string. order A....B
public int findMinDistanceBtwWords(String S, String A, String B){
int posCount = 0;
int start = 0;
int posA=0;
int posB=0;
int minDistance=-1;
//counting position based on the spaces we encounter. append a space to the last wordrd
S = S.concat(" ");
for(int i=0;i<S.length();i++){
if(S.charAt(i)==' '){
posCount++;
//see if substring at (start, i-1) matches any of A or B
if(S.substring(start,i).equals(A)){
posA = posCount;
}
if(S.substring(start,i).equals(B)){
posB = posCount;
}
if((posB!=0 && posA!=0) && posB-posA>0){
if(minDistance == -1){
minDistance = posB-posA;
}else{
minDistance = Math.min(posB-posA,minDistance);
}
}
//update start
start = i+1;
}
}
return minDistance;
}
do a modified binary search O(logn)
public char modBS(char[]input,int left, int right, char target){
if(left > right){
return input[left%input.length];
}
int mid = (left + right)/2;
if(input[mid] == target){
return input[(mid+1)%input.length];
}else if(input[mid] < target){
return modBS(input,mid+1,right,target);
}else{
return modBS(input,left,mid-1,target);
}
}
public char findCharacter(char[] input, char target){
return modBS(input,0,input.length-1,target);
}
only allocate one array instead of two arrays in some of the solutions above. also handles 0.
public int[] selfExcludingProduct(int[] input) {
// implementation...
int [] front = new int[input.length];
front[0] = 1;
for(int i =1;i<front.length;i++){
front[i] = front[i-1]*input[i-1];
}
int temp = 1;
for(int i =front.length-1;i>=0;i--){
front[i] = front[i]*temp;
temp*=input[i];
}
return front;
}
- sh88990 April 29, 2014I personally like the regex solution but wonder if that's what the interviewers are looking for...so i just implement a function to check if a string is a number.
public static boolean isDigit(char c){
if(c>='0' && c<='9'){
return true;
}else{
return false;
}
}
public static boolean isNumber(String s){
if(s.length() == 0){
return false;
}
boolean dotUsed = false;
for(int i=0;i<s.length();i++){
if(i==0){
//first digit can only be -, ., or 0-9
if(s.charAt(i) == '-'){
continue;
}
if(s.charAt(i) == '.'){
dotUsed = true;
continue;
}
if(!isDigit(s.charAt(i))){
return false;
}
}else{
//only one dot allowed
if(s.charAt(i) == '.'){
if(dotUsed){
return false;
}else{
//dont allow "10."
if(i==s.length()-1){
return false;
}else{
dotUsed = true;
continue;
}
}
}
//dont allow cases like 0000002
if(i==1 && s.charAt(0) == '0' && s.charAt(1)=='0'){
return false;
}
if(!isDigit(s.charAt(i))){
return false;
}
}
}
return true;
}
- sh88990 April 29, 2014Minor correction:
in if statement
if(a[m]==target){}
if( m==right || (m<right && a[m+1] != a[m])){
if(right > bound[1]){
bound[1] = right;
}
}
should be
if( m==right || (m<right && a[m+1] != a[m])){
if(m > bound[1]){
bound[1] = m;
}
}
and
if(m==left || (m>left && a[m-1] != a[m])){
if(left < bound[0]){
bound[0] = left;
}
}
should be
if(m==left || (m>left && a[m-1] != a[m])){
if(m < bound[0]){
bound[0] = m;
}
}
Use modified binary search
public void modifiedBS(int left, int right, int [] a, int [] bound, int target){
if(left>right){
return;
}
int m = (left+right)/2;
if(a[m] == target){
if( m==right || (m<right && a[m+1] != a[m])){
if(right > bound[1]){
bound[1] = right;
}
}
if(m<right && a[m+1]==target){
modifiedBS(m+1,right,a,bound,target);
}
if(m==left || (m>left && a[m-1] != a[m])){
if(left < bound[0]){
bound[0] = left;
}
}
if(m>left && a[m-1] == a[m]){
modifiedBS(left,m-1,a,bound,target);
}
}else if(a[m] < target){
modifiedBS(m+1,right,a,bound,target);
}else{
modifiedBS(left,m-1,a,bound,target);
}
}
public int [] findBound(int []a, int target){
int bound[] = new int[2];
if(a.length == 0){
bound[0] = -1;
bound[1] = -1;
return bound;
}
bound[0] = a.length-1;
bound[1] = 0;
modifiedBS(0,a.length-1,a,bound, target);
if(bound[0] == a.length-1 && bound[1] == 0 ){
bound[0] = -1;
bound[1] = -1;
}
return bound;
}
This is just brute force method. Should exist a more efficient way to do it.
public boolean isWordPresent(int i, int j, String target, boolean[][]visited, char[][]matrix){
if(i<0 || i>=matrix.length || j<0 || j>=matrix[0].length){
return false;
}
if(visited[i][j]){
return false;
}
if(matrix[i][j] != target.charAt(0)){
return false;
}else{
visited[i][j] = true;
//the last char matches
if(target.length()==1){
return true;
}else{
return isWordPresent(i-1,j-1,target.substring(1),visited,matrix)||
isWordPresent(i-1,j,target.substring(1),visited,matrix)||
isWordPresent(i-1,j+1,target.substring(1),visited,matrix)||
isWordPresent(i,j-1,target.substring(1),visited,matrix)||
isWordPresent(i,j+1,target.substring(1),visited,matrix)||
isWordPresent(i+1,j-1,target.substring(1),visited,matrix)||
isWordPresent(i+1,j,target.substring(1),visited,matrix)||
isWordPresent(i+1,j+1,target.substring(1),visited,matrix);
}
}
}
public boolean findWord(String target, char [][]matrix){
//first check valid word and matrix
if(target.equals("") || target==null){
return false;
}
if(matrix.length==0){
return false;
}
//loop
boolean flag = false;
for(int row =0; row<matrix.length;row++){
for(int column=0;column<matrix[0].length;column++){
boolean [][]visited = new boolean[matrix.length][matrix[0].length];
flag = isWordPresent(row,column,target,visited,matrix);
if(flag){
return true;
}
}
}
return false;
}
Recursion:
boolean OneEditApart(string s1, string s2) {
return isOneEditApart(s1, s2, 0);
}
public boolean isOneEditApart(String a, String b, int editCount){
if(Math.abs(a.length()-b.length()) > 1 || editCount >1){
return false;
}
if(a.equals("") || b.equals("")){
if(a.equals("") && b.equals("")){
if(editCount == 0){
return false;
}else{
return true;
}
}else if(editCount == 0){
return true;
}else{
return false;
}
}
if(a.charAt(0) == b.charAt(0)){
return isOneEditApart(a.substring(1),b.substring(1),editCount);
}else{
++editCount;
return isOneEditApart(a.substring(1),b.substring(1),editCount) ||
isOneEditApart(a.substring(1),b.substring(0),editCount) ||
isOneEditApart(a.substring(0),b.substring(1),editCount);
}
}
Non-recursive, the code can probably be way more concise.
public boolean oneEditApart(String s1, String s2){
if(Math.abs(s1.length() - s2.length())>1){
return false;
}
if(s1.length() == s2.length()){
int count = 0;
for(int i = 0; i<s1.length();i++){
if(s1.charAt(i) != s2.charAt(i)){
count++;
if(count > 1){
break;
}
}
}
if(count == 1){
return true;
}else{
return false;
}
}else{
int cur_short = 0;
int cur_long = 0;
String shortString = null;
String longString = null;
int shortLen = 0;
int count = 0;
if(s1.length()>s2.length()){
longString = s1;
shortString = s2;
shortLen = s2.length();
}else{
longString = s2;
shortString = s1;
shortLen = s1.length();
}
while(cur_short< shortLen){
if( shortString.charAt(cur_short) != longString.charAt(cur_long) ){
cur_long++;
count++;
if(count>1){
break;
}
}else{
cur_short++;
cur_long++;
}
}
if(count <= 1){
return true;
}else{
return false;
}
}
}
use hashmap to form one-to-one relationship btw 2 chars
- sh88990 May 01, 2014