Adobe Interview Question Interns
Country: India
Interview Type: In-Person
Basically, this is the same problem of longest path in a binary tree but considering the required directions in the path string:
package problems;
import problems.auxiliar.BinaryTreeFactory;
import problems.auxiliar.BinaryTreeNode;
/**
* Created by fsantos on 3/7/17.
*/
public class Prob175 {
public static <T extends Comparable<T>> String longestPath(BinaryTreeNode<T> root, String steps) {
return longestPath(root, steps, 0, "");
}
private static <T extends Comparable<T>> String longestPath(BinaryTreeNode<T> node, String steps, int step, String path) {
if (node == null) {
return path.substring(0, path.length() - 1);
}
char chr = '?';
if (step < steps.length())
chr = steps.charAt(step);
String pathLeft = null;
String pathRight = null;
switch(chr) {
case 'L':
pathLeft = longestPath(node.left, steps, step + 1, path + "L");
break;
case 'R':
pathRight = longestPath(node.right, steps, step + 1, path + "R");
break;
case '?':
pathLeft = longestPath(node.left, steps, step + 1, path + "L");
pathRight = longestPath(node.right, steps, step + 1, path + "R");
break;
}
if (pathLeft != null && pathRight != null)
return pathLeft.length() > pathRight.length() ? pathLeft : pathRight;
else if (pathLeft != null) return pathLeft;
else return pathRight;
}
public static void main(String[] args) {
BinaryTreeNode<Integer> root = BinaryTreeFactory.makeBinaryTree();
String longestPath = longestPath(root, "?");
System.out.println(longestPath);
}
}
Tree used in the test:
1
2 3
4 5
6
Output:
LRR
Reread the question. It says
" Find the maximum distance from origin the robot can go AT ANY POINT OF TIME."
So it should be max distance it can achieve any time in between.
#include<iostream>
#include<string>
using namespace std;
int main(){
int maxlen = 0,dis=0;
int countl = 0,countr=0,countq=0;
int cmdcount ; //LLRRLLLL??LLL??RLR
string ch;
cin>>ch;
cmdcount = ch.length();
for (int i=0;i<cmdcount;i++){
if(ch[i]=='L'){
countl++;
}
if(ch[i]=='R'){
countr++;
}
if(ch[i]=='?'){
countq++;
}
dis = countr - countl;
if (dis < 0 )
dis = -dis;
dis += countq;
if(maxlen <= dis)
maxlen = dis;
}
cout<<maxlen;
return 0;
}
This is the write way. @rd22 confused me a lot.
public static int maxDistFromOrigin(String str){
if(str == null || str.length<1) return 0;
int numLeft = 0;
int numRight = 0;
int numLeftOrRight = 0;
int maxDist = 0;
for(char c : str.toCharArray()){
if(c == 'L')++numLeft;
if(c == 'R')++numRight;
if(c == '?')++numLeftOrRight;
maxDist = numLeftOrRight + Math.max(numLeft, numRight) - Math.min(numLeft, numRight) > maxDist
? numLeftOrRight + Math.max(numLeft, numRight) - Math.min(numLeft, numRight) : maxDist;
}
return maxDist;
}
public static int maxDistFromOrigin(String str){
if(str == null || str.length<1) return 0;
int numLeft = 0;
int numRight = 0;
int numLeftOrRight = 0;
int maxDist = 0;
for(char c : str.toCharArray()){
if(c == 'L')++numLeft;
if(c == 'R')++numRight;
if(c == '?')++numLeftOrRight;
maxDist = numLeftOrRight + Math.max(numLeft, numRight) - Math.min(numLeft, numRight) > maxDist
? numLeftOrRight + Math.max(numLeft, numRight) - Math.min(numLeft, numRight) : maxDist;
}
return maxDist;
}
public static int maxDistFromOrigin(String str){
if(str == null || str.length<1) return 0;
int numLeft = 0;
int numRight = 0;
int numLeftOrRight = 0;
int maxDist = 0;
for(char c : str.toCharArray()){
if(c == 'L')++numLeft;
if(c == 'R')++numRight;
if(c == '?')++numLeftOrRight;
maxDist = numLeftOrRight + Math.max(numLeft, numRight) - Math.min(numLeft, numRight) > maxDist
? numLeftOrRight + Math.max(numLeft, numRight) - Math.min(numLeft, numRight) : maxDist;
}
return maxDist;
public static int maxDistFromOrigin(String str){
if(str == null || str.length<1) return 0;
int numLeft = 0;
int numRight = 0;
int numLeftOrRight = 0;
int maxDist = 0;
for(char c : str.toCharArray()){
if(c == 'L')++numLeft;
if(c == 'R')++numRight;
if(c == '?')++numLeftOrRight;
maxDist = numLeftOrRight + Math.max(numLeft, numRight) - Math.min(numLeft, numRight) > maxDist
? numLeftOrRight + Math.max(numLeft, numRight) - Math.min(numLeft, numRight) : maxDist;
}
return maxDist;
}
public static int maxDistFromOrigin(String str){
if(str == null || str.length<1) return 0;
int numLeft = 0;
int numRight = 0;
int numLeftOrRight = 0;
int maxDist = 0;
for(char c : str.toCharArray()){
if(c == 'L')++numLeft;
if(c == 'R')++numRight;
if(c == '?')++numLeftOrRight;
maxDist = numLeftOrRight + Math.max(numLeft, numRight) - Math.min(numLeft, numRight) > maxDist
? numLeftOrRight + Math.max(numLeft, numRight) - Math.min(numLeft, numRight) : maxDist;
}
return maxDist;
}
The idea is to recursively solve the problem
1. Start with a count of zero, start position
2. if the next character is "L", reduce the count by 1
3. If the char is "R", increase the count by 1
4. If the char is "?" consider both the cases, left and right and pick the max.
//the function is called masDistance("LL?R", 0)
public static int maxDistance(String s, int count){
if(s.length() != 0){
if(s.charAt(0) == 'L')
return maxDistance(s.substring(1), --count);
else if(s.charAt(0) == 'R')
return maxDistance(s.substring(1), ++count);
else
return Math.max(maxDistance(s.substring(1), --count), maxDistance(s.substring(1), ++count));
}
else
return Math.abs(count);
}
I believe this should work and I feel it is pretty readable.
- Carson Bradshaw August 03, 2017public static int maxDistFromOrigin(String str){ if(str == null || str.length<1) return 0; int numLeft = 0; int numRight = 0; int numLeftOrRight = 0; int maxDist = 0; for(char c : str.toCharArray()){ if(c == 'L')++numLeft; if(c == 'R')++numRight; if(c == '?')++numLeftOrRight; maxDist = numLeftOrRight + Math.max(numLeft, numRight) - Math.min(numLeft, numRight) > maxDist ? numLeftOrRight + Math.max(numLeft, numRight) - Math.min(numLeft, numRight) : maxDist; } return maxDist; }